Stack size Q

Stack as in the stack that's used to pas parameters to functions? I think in windows the default is 4kb. And the last time i checked, the stack is regular memory being pointed to by the esp register, but the processor might use a cache for the stack...

If it's the stack i think it is, if you're using visual C++, you should be able to get the pointer to the stack by

__asm mov *INSERT VAR TO HOLD STACK ADDRESS HERE*, esp

cool.
You know the "stack", when you declare local func/proc vars, is where these vars are stored <- that's the stack I mean, which should be the same memory space as used by passed params anyway, right, just tacked onto the end.
btw, i read something about the order of stack var allocation. If i declare:

procedure someproc;
var x,y,z:byte;
begin

end;

is the order of stack allocation x, y z or z,x,y? another words, vars that are closer to stack base (first stack address) would be quicker to access than those allocated down the line, so if I had:

var a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z:integer; // 4bytes

accessing a would be much quicker than accessing z if allocated in a-z order,
right?
any ideas?!

The stack is an area of memory reserved for program use. Programs
typically use it to push and pop parameters when calling functions.
That is, "Passing" parameters to functions.

The exact location is very system dependent. As kohlrak pointed out,
the stack is 4KB on Win32 machines. The 80x86 processor register ESP
points to the top of the stack, while SS points to the beginning
address of the stack.

You can get the addresses using inline assembly:

	static unsigned int iStackPointer=0;	__asm  mov [iStackPointer], esp

Now iStackPointer contains the address of the top of the stack.

Erm... Take this for example. Let's say you have a letter at memory address 0, and then another letter at memory address 1. It would take equal time to grab either one. Just because the number is higher or lower dosn't mean it's quicker or slower to access, unless you're accessing them with a push and pop interface. If you look at the assembly of your programs, you'll notice that most compilers just decrement the stack pointer (esp) by the size of the variable they want to allocate and just use the space that was left there. For example...

C/C++ (32 bit system):
int a;

ASM:
sub esp, 4

The compiler would remember where esp was before it subtracted it by 4, and use that as a static address to get the number... as seen below...

C/C++ (32 bit system):
a+=3;

ASM:
add [*INSERT NUMBER IN ESP BEFORE THE SUB OPERATION*], 3

As for the order... I'm not sure what language you're using and it dosn't look familiar... But for instance, the call would be like this...

C/C++:
function(param1, param2); //calls function with param1 and param2

ASM:
push param2
push param1
call function

Quote:

Original post by at_lowe procedure someproc; var x,y,z:byte; begin end; is the order of stack allocation x, y z or z,x,y? another words, vars that are closer to stack base (first stack address) would be quicker to access than those allocated down the line, so if I had: var a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z:integer; // 4bytes accessing a would be much quicker than accessing z if allocated in a-z order, right? any ideas?!

The order of stack allocation depends on the calling convention you are using.
For example, the default in C++ is __cdecl, which passes parameters left to
right (If I remember correctly.)

As for parameters passed (that are deeper in the stack) may not necessarily
be "quicker". It is not needed to pop anything from the stack to read from
it. For example, while ESP points to the last paramater, ESP-4
may point to the next parameter. Note the simple subtraction.

This is very compilier dependent, and how the compilier produces code, and
weather optomizations are enabled or not.

It would be quicker to pop them off rather than a mov then an add... Though, even better would be to not pop them off at all (unless you're using referance parameters) and you just access them and mov a copy to a temp variable (likely to be on the stack)... Though, as i've said, most compilers allocate most of the memory this way, but adding and subing ESP.

The stack size in Win32 is specified at thread creation time. In the case of a new process, it's read from the PE header in the EXE file. This paramter can be controlled via the linker; the usual default is 1 MB. The stack on Windows is not, too my knowledge resizable.

On many UNIX-alike systems, however, the stack will simply keep growing and growing as long as the system has memory left for it to grow into.

Note that this is a rough explanation, and ignores some of the mechanics of the stack. It's good enough for practical purposes, though.

[Edited by - Promit on August 1, 2007 4:07:35 AM]

Quote:

Original post by kohlrak It would be quicker to pop them off rather than a mov then an add... Though

If by 'them' you mean plural, you would be wrong.

Example 1:

mov eax, [esp]
mov ecx, [esp+4]
mov edx, [esp+8]
add esp, 12

thats notably faster than

Example 2:

pop eax
pop ecx
pop edx

A clever CPU could execute all 4 instructions of the first example simultaneously. Most CPU's are currently not that clever, but they are moving in that direction. You can currently, unless you computer is fairly old, expect your CPU to execute the first two or three instruction simultanously, and then the remaining one(s).

In the second example, its one big dependency chain. Expect each instruction to be executed all by itself. If you are lucky, code following the pop chain might get paired up by the out-of-order execution logic. Thats only if you are lucky. The pop-chain (or push chain) methodology is seriously inferior on modern CPU's and its not going to get any better (there is no good reason to)

---------------

Do not expect your compiler to be consistent about the order of local variable allocations. It is going to use its best judgement when it converts its optimized abstract syntax tree to opcodes.

As far as that variable 'z' being slow to access because its so far from the stack top - that will only be true if its not in a currently loaded cache line (its extremely rare when the stack top isnt loaded) - if that is the case, then you are eventualy going to pay for a cache miss when you eventualy do access it. You will either pay it now, or pay it as your code returns to the caller. It isnt anything to worry about.

Quote:

The stack size in Win32 is specified at thread creation time. In the case of a new process, it's read from the PE header in the EXE file. This paramter can be controlled via the linker; the usual default is 1 MB. The stack on Windows is not, too my knowledge resizable.

1 meg sounds a bit big...

Quote:

You can currently, unless you computer is fairly old, expect your CPU to execute the first two or three instruction simultanously,

I have one core, and one 4 byte bus... Unless you mean piplining, which in that case the pop will also be the same, for it's thrown in the pipeline as well.

Quote:

Original post by kohlrak Quote: You can currently, unless you computer is fairly old, expect your CPU to execute the first two or three instruction simultanously, I have one core, and one 4 byte bus... Unless you mean piplining, which in that case the pop will also be the same, for it's thrown in the pipeline as well.

The number of cores is irrelevant.
Having a 32-bit bus is irrelevant.
The pipeline is important.

Just about all modern processor can execute more than one instruction simultaneously, and can even do so out of order. Even the first pentium processor had multiple execution units. They are leveraging techniques like register renaming and dynamic allocation of execution units.

They cannot however pair up instructions that have a dependency between each other, and they cannot execute them out of order either.

The sequency of pops are decomposed by the processor (here, a p4) into micro-ops (u-ops), and basically looks like this:

(A) mov eax, [esp]
(B) add esp, 4
(C) mov ecx, [esp]
(D) add esp, 4
(E) mov edx, [esp]
(F) add esp, 4

It cannot execute (C) or (D) until esp is determined by instruction (B). That is a dependency.

It cannot execute (E) or (F) until esp is determined by (D). That is a dependency.

This is one big dependency chain from (B) to (D) to (F) - the allowed pairing here are A:B, C:D, and E:F ... at a minimum this code will consume the combined latency of each of the 3 additions, plus the latency of the last memory read .. I am educated-guessing that the minimum for this is (3 + 3) = 6 cycles on a P4 - thats assuming the first two memory fetches are completely free (the ideal)

For more information, refer to Agner Fog's optimization manuals (available online.)

Quote:

Original post by kohlrak Quote: The stack size in Win32 is specified at thread creation time. In the case of a new process, it's read from the PE header in the EXE file. This paramter can be controlled via the linker; the usual default is 1 MB. The stack on Windows is not, too my knowledge resizable. 1 meg sounds a bit big...

Like I said, there are mechanical details about how it's managed that I've omitted. For practical purposes, you can assume it's 1 MB. I can go into the details, but it's a bit confusing if you don't have a fairly strong grasp of virtual memory.

Oh well.

The stack starts with an initial allocation. I don't know what the size of this initial allocation is or if it varies (it may be part of the linker setup and PE fields, come to think of it); it could be as small as one page. The OS will reserve a full 1 MB of virtual memory space at thread start, but only the initial allocation is committed. The page immediately following the last committed page is marked as a guard page. When you spill past the end of your currently committed stack, you'll hit the guard page and and the hardware will generate a page fault. The OS will pick that up and extend the committed region. It simply continues like this until you hit the end of the reserved region, at which point you'll get an exception due to stack overflow.

Virtual memory can be reserved by an application without being "committed" - ie without being assigned a physical address (= capacitors on the memory silicon). Only committed memory is measured when you talk about how much memory a program is using.

IIRC, The 1MB reserved for the stack by windows will not make your program take up 1MB of your available memory immediately, instead it will be "committed" to real memory only when needed. This would be achieved silently by the OS page fault handler routines.

So you could still have 1000s of processes on a system with only 100MB without paging even if they each have 1MB of reserved virtual page space.


Linux may keep going reducing the stack pointer until the stack almost overlaps heap memory, but at this point it would have to crash.


The only ways you can really expect to use up lots of page space are:
1) Very deep recursion.
2) Extremely large function-owned arrays.
3) ASM code.


All this is IIRC though.

Quote:

For more information, refer to Agner Fog's optimization manuals (available online.)

I've been putting that off... XD

Quote:

Like I said, there are mechanical details about how it's managed that I've omitted. For practical purposes, you can assume it's 1 MB. I can go into the details, but it's a bit confusing if you don't have a fairly strong grasp of virtual memory.

With 1mb, I don't see the point of restricting you to 4096 bytes when you can use 1048572 bytes, giving you a maximum 4 bytes (8 total) for a net on the top and the bottom. Unless you're talking about 1meg for all the programs in windows, in which case you would have a maximum of 262144 threads possible (without a net). I'm referring the size for each thread. Actually... I just did a test with my junk asm file. It's a file i keep open to do completely random tests on the fly without trying an algorithem on my code and being unable to switch back because a power outage hits at random. Anyway.. Below was compiled wiht fasm...

Quote:

;JUNK FILE format PE console include '%fasminc%\win32ax.inc' entry start section '.code' readable writeable executable pausestring db "PAUSE", 0 rawrstring db "rawr", 0 pi dq 3.1415926535897932384626433832795f todegs dq 57.295779513082320876798154814105f torads dq 0.017453292519943295769236907684886f x dq 0f y dq -1f result dq 0f oneeighty dq 180f start: rawr: dec esp mov eax, [esp] ;to throw the exception jmp rawr cinvoke printf, <"%i-%i",10, 0>, esp, ebx cinvoke system, pausestring invoke ExitProcess, 0 section '.idata' readable import data library kernel, 'kernel32.dll', crt, 'crtdll.dll' import kernel, ExitProcess, 'ExitProcess' import crt, printf, 'printf', system, 'system'

ESP starts out with 0x0007FFC4... Ends with 0x00042FFF threw the exception... That means for that program, the stack was 249796 (Decimal) bytes... That's just down. This time starts out with 0x0007FFC4... Ends with 0x00081FFD throwing the exception. Result=8248... Add the two results together to get 258044. Interestingly enough, it's not aligned with 1024 at all. I think the most interesting part (which isn't the size), but the fact that as soon as the program starts, you can pop more than you can push. You shouldn't be able to pop anything when the program started cause there's nothing pushed there, right? I guess now i have another thing to add to the list of "the mysteries of windows."

What makes you think that nothing is on your stack when your processes entry point gets called?

(see the word 'called' ??)

Also, to be pedantic, your stack top is stored (under win32) at FS:[4]

mov eax, fs:[4]

This is not the same as the esp register when your main() gets called.

Edited to add: The exceptions that were thrown were not when the allocated stack was exceeded (up or down) but instead when a page fault occured (a point where your process no longer had read rights or where the memory address was not mapped)

(and by 'stack top' FS:[4] stores where your stack starts, and it grows downward .. it grows down to FS[8] .. and FS:[0] is the top of the structured exception handler)

Quote:

Original post by kohlrak Quote: For more information, refer to Agner Fog's optimization manuals (available online.) I've been putting that off... XD

Some other good resources are:
Intel IA32 Architecture Manual (Vol 1, 2, and 3)
Intel Optimization Guide
AMD Optimization Guide