4 ms·

In other words, use heap space and not stack space. This is pretty elementary in C programming.

IshKebab 5y ago
Sure, but 128 kB is really small even if you do that properly. Seems like it would be more sensible if the stack space could just grow when required. Surely not that difficult?
- viraptor 5y ago
  The main thread already does that. The thread stack does not. It probably made sense on 32b with relatively limited address space... But I'm curious why we're not applying that to all threads on 64b. Reserving a few 10MB of address space per thread shouldn't be a big issue, right? (Without actually mapping those pages)
  - megous 5y ago
    Mapping a lot of pages has some overhead, too. So if you have large stacks per thread you'll take a hit. If you use huge pages to alleviate that, you'll waste a lot of physical memory.
- tyingq 5y ago
  It is easy for a single threaded program, but since each thread has it's own part of the stack, it would be non-trivial for a multithreaded program.
- aidenn0 5y ago
  A typical stack frame is around a couple dozen words. Let's round that up to 32 words (256 bytes). 128K is enough for a 500 deep stack at that size. 128K is huge.
- CodesInChaos 5y ago
  Since standard OS stacks are contiguous and unmovable, you can't grow them once they run out of space. However while the address space for the maximum stack size gets reserved, each page only requires backing memory once it's first used. So as far as physical memory consumption is concerned, typical stacks act as growable with a fixed maximum size. Since address space is huge on 64-bit systems, choosing a large stack size is cheap on such systems (at least of they allow over-commit). For the main thread, a system can also try to keep other allocations far from the stack without committing to any particular size (heap grows upwards from the bottom of the address space, stack downwards from the top). But this doesn't scale to multiple threads and leads to an unpredictable maximum stack size, so I prefer the fixed reserved space approach.
- pjmlp 5y ago
  Enough for a full COM binary plus one overlay section. :)
- megous 5y ago
  Wait until you realize OS kernel thread stack size is 8 KiB or in that range, if you think 128 KiB is small. :))
viraptor 5y ago
I'd say "be aware of stack sizes". If you can get away with just the appropriately sized stack in a thread, that's a nice performance gain over dealing with multithreading heap allocators.
dnautics 5y ago
this is too reductive. Usually stack space is faster because you will have fewer cache misses. future languages will be able to suss this out at compile-time: https://github.com/ziglang/zig/blob/2ac769eab9b7dba4cd38e5de01dfa6400f7ebd5b/lib/std/Thread.zig#L183-L184 https://github.com/ziglang/zig/blob/2ac769eab9b7dba4cd38e5de...
- sys_64738 5y ago
  If speed issues then it sounds like this is critical code path that is sensitive to time. You'd be looking for alternative data structures at that point so this point would be moot.
ynik 5y ago
It's a bit ridiculous to complicate recursive algorithms just because the stack sizes haven't been increased in the past 3 decades. Nowadays we have at least 48bit virtual address space available; what's the harm in giving each thread a full GB of stack?
- sys_64738 5y ago
  Generally recursion is not something you want in production code. It's cute for academia when studying algorithms but where there's an iterative alternative that should be used.
- lonjil 5y ago
  If you need a bigger stack, you can get one. This stuff is merely the default.
kstenerud 5y ago
That might have been true in the old days when memory wasn't the bottleneck, but in today's world where a cache miss is catastrophic, it makes MUCH more sense to use stack space where you can. This also has the side effect of facilitating idempotent functions and function purity in general. No sense in clinging to old world ideals when they no longer make sense.
- ariadneconill 5y ago
  That is certainly a take. Storing small data, like function-local ints, pointers, etc, on the stack is beneficial due to L1$ prefetching semantics, but storing a 512KB scratchpad on the stack (which is what the article is about) will totally trash your L1$ and you'll have MORE cache misses than you would if that scratchpad was not on the stack.
- jlokier 5y ago
  I agree that using the stack instead of heap makes sense for cache reasons. But in the contemporary world, the trend is increasingly to transform functions to "async" forms where much of the functions' local state including return address is stored in heap-allocated space instead.

Sure, but 128 kB is really small even if you do that properly. Seems like it would be more sensible if the stack space could just grow when required. Surely not that difficult?

viraptor 5y ago
The main thread already does that. The thread stack does not. It probably made sense on 32b with relatively limited address space... But I'm curious why we're not applying that to all threads on 64b. Reserving a few 10MB of address space per thread shouldn't be a big issue, right? (Without actually mapping those pages)
- megous 5y ago
  Mapping a lot of pages has some overhead, too. So if you have large stacks per thread you'll take a hit. If you use huge pages to alleviate that, you'll waste a lot of physical memory.
tyingq 5y ago
It is easy for a single threaded program, but since each thread has it's own part of the stack, it would be non-trivial for a multithreaded program.
aidenn0 5y ago
A typical stack frame is around a couple dozen words. Let's round that up to 32 words (256 bytes). 128K is enough for a 500 deep stack at that size. 128K is huge.
CodesInChaos 5y ago
Since standard OS stacks are contiguous and unmovable, you can't grow them once they run out of space. However while the address space for the maximum stack size gets reserved, each page only requires backing memory once it's first used. So as far as physical memory consumption is concerned, typical stacks act as growable with a fixed maximum size. Since address space is huge on 64-bit systems, choosing a large stack size is cheap on such systems (at least of they allow over-commit). For the main thread, a system can also try to keep other allocations far from the stack without committing to any particular size (heap grows upwards from the bottom of the address space, stack downwards from the top). But this doesn't scale to multiple threads and leads to an unpredictable maximum stack size, so I prefer the fixed reserved space approach.
pjmlp 5y ago
Enough for a full COM binary plus one overlay section. :)
megous 5y ago
Wait until you realize OS kernel thread stack size is 8 KiB or in that range, if you think 128 KiB is small. :))

viraptor 5y ago

I'd say "be aware of stack sizes". If you can get away with just the appropriately sized stack in a thread, that's a nice performance gain over dealing with multithreading heap allocators.

dnautics 5y ago

this is too reductive. Usually stack space is faster because you will have fewer cache misses. future languages will be able to suss this out at compile-time: https://github.com/ziglang/zig/blob/2ac769eab9b7dba4cd38e5de01dfa6400f7ebd5b/lib/std/Thread.zig#L183-L184 https://github.com/ziglang/zig/blob/2ac769eab9b7dba4cd38e5de...

sys_64738 5y ago
If speed issues then it sounds like this is critical code path that is sensitive to time. You'd be looking for alternative data structures at that point so this point would be moot.

ynik 5y ago

It's a bit ridiculous to complicate recursive algorithms just because the stack sizes haven't been increased in the past 3 decades. Nowadays we have at least 48bit virtual address space available; what's the harm in giving each thread a full GB of stack?

sys_64738 5y ago
Generally recursion is not something you want in production code. It's cute for academia when studying algorithms but where there's an iterative alternative that should be used.
lonjil 5y ago
If you need a bigger stack, you can get one. This stuff is merely the default.

kstenerud 5y ago

That might have been true in the old days when memory wasn't the bottleneck, but in today's world where a cache miss is catastrophic, it makes MUCH more sense to use stack space where you can. This also has the side effect of facilitating idempotent functions and function purity in general. No sense in clinging to old world ideals when they no longer make sense.

ariadneconill 5y ago
That is certainly a take. Storing small data, like function-local ints, pointers, etc, on the stack is beneficial due to L1$ prefetching semantics, but storing a 512KB scratchpad on the stack (which is what the article is about) will totally trash your L1$ and you'll have MORE cache misses than you would if that scratchpad was not on the stack.
jlokier 5y ago
I agree that using the stack instead of heap makes sense for cache reasons. But in the contemporary world, the trend is increasingly to transform functions to "async" forms where much of the functions' local state including return address is stored in heap-allocated space instead.