21 ms·

I have recently implemented something remotely similar in a totally different way. Computers are 64-bit by now. For most practical applications, address space

I have recently implemented something remotely similar in a totally different way. Computers are 64-bit by now. For most practical applications, address space is unlimited. This means you can allocate let’s say 1TB of continuous address space at startup, and implement allocator on top that allocates and commits physical pages in that range, implementing a stack allocator. Not only it never moves the data, it also guarantees the complete memory is at continuous range of addresses. For instance, you can view that thing as an infinite std::vector() which never requires reallocations. I did it for Windows on top of VirtualAlloc() API. Linux has it too, mmap() with PROT_NONE protection flag to reserve address space, then mprotect() to allocate physical pages in that range.

eptcyka 5y ago
I can only imagine this working for applications that don't churn through memory or applications that are short lived. But in those cases, it would work really well.
- Const-me 5y ago
  My application is long-lived (at least hours) and uses gigabytes of memory. It works for me because I have distinct moments in time when the whole stack is no longer needed. I’m working on a CAM/CAE app where work is organized as a sequence of optimization passes. I only need to keep the data within 1 iteration. At the end of every optimization pass I simply reset the stack pointer to the very bottom, and on the next iteration the stack starts growing again from zero reusing these physical memory pages. BTW I’m using multiple of these stacks, one per thread. Helps with performance because no locks are needed, also L1 and L2 caches are inside cores, only the L3 is shared across the whole CPU.
  - Joker_vD 5y ago
    So basically, your use case is the extreme variant of the one described in Appel's "Garbage collection can be faster than stack allocation" paper.
    - Const-me 5y ago
      Not sure it deserves to be called garbage collector, too simple. The approach is pretty close to arena allocation https://en.wikipedia.org/wiki/Region-based_memory_management#Implementation https://en.wikipedia.org/wiki/Region-based_memory_management... The only twist, with modern 64-bit processors there’s no need for linked lists or multiple blocks, can instead add new physical pages into pre-allocated address space.
michielderhaeg 5y ago
This is what the Glasgow Haskell Compiler runtime does. If you run a Haskell application, you'll see it has uses 1TB of virtual memory. This way you never have to talk to the kernel if you need more memory.
- weavie 5y ago
  Also Clozure Common Lisp.
stefan_ 5y ago
Address space is unlimited but pages are still 4K.
- Const-me 5y ago
  Right, I thought about large pages for that, unfortunately on Windows they’re pretty much useless. They require an elevated process, and they are incompatible with swap file i.e. they never paged to disk even when there’s low memory: https://docs.microsoft.com/en-us/windows/win32/memory/large-page-support https://docs.microsoft.com/en-us/windows/win32/memory/large-...
- gpderetta 5y ago
  and TLB is also a scarce resource.
titzer 5y ago
Well, unfortunately, address space isn't unlimited. In my experience developing 64-bit wasm engines, the typical approach of reserving 8GB of memory for each Wasm memory leads to address space exhaustion after only about 1000 memories (regardless of how many actual pages those memories use). Therefore for a long living VM that might load and unload hundreds or even thousands of programs (on different webpages for example), it's really important to clean up those reservations promptly. In V8, cleaning up the reservations for Wasm memories is ultimately tied to garbage collection of the JS heap, since JS objects can root memory. That led to the somewhat clunky need to retry allocation in a loop, running a full GC if allocation fails the first few times (https://github.com/v8/v8/blob/master/src/objects/backing-store.cc#L366 https://github.com/v8/v8/blob/master/src/objects/backing-sto...). There are also fundamental kernel limitations on virtual memory size. They are system dependent but much lower than 2^64.
- Const-me 5y ago
  On modern windows the limit is 2^47 bytes: https://docs.microsoft.com/en-us/windows/win32/memory/memory-limits-for-windows-releases#memory-limits-for-windows-and-windows-server-releases https://docs.microsoft.com/en-us/windows/win32/memory/memory... With 8GB of virtual space per engine, should be enough for 16k of these engines. Interesting that you got OOM only after 1k engines, that’s 16x below the limit. Was that on Windows? Actual hardware or some VM substitute? In my use case, I was lucky as I only need an allocator per hardware thread. They never approach thousands. So far, the maximum is 256 hardware threads, like in dual-CPU EPYC 7713.
  - titzer 5y ago
    It seems to depend a lot on current conditions and is ultimately probabilistic. I.e. it would not fail 100% at 1000, but some large enough fraction of the time that that strategy was not shippable for Wasm. IIRC it might only have been 10% of the time, but it quickly increases to 100% along a sliding scale up to the hard limit. Part of that is fragmentation as well, because Chrome uses an allocator underneath that can carve out fairly large reservations that fragment the address space.

eptcyka 5y ago

I can only imagine this working for applications that don't churn through memory or applications that are short lived. But in those cases, it would work really well.

Const-me 5y ago
My application is long-lived (at least hours) and uses gigabytes of memory. It works for me because I have distinct moments in time when the whole stack is no longer needed. I’m working on a CAM/CAE app where work is organized as a sequence of optimization passes. I only need to keep the data within 1 iteration. At the end of every optimization pass I simply reset the stack pointer to the very bottom, and on the next iteration the stack starts growing again from zero reusing these physical memory pages. BTW I’m using multiple of these stacks, one per thread. Helps with performance because no locks are needed, also L1 and L2 caches are inside cores, only the L3 is shared across the whole CPU.
- Joker_vD 5y ago
  So basically, your use case is the extreme variant of the one described in Appel's "Garbage collection can be faster than stack allocation" paper.
  - Const-me 5y ago
    Not sure it deserves to be called garbage collector, too simple. The approach is pretty close to arena allocation https://en.wikipedia.org/wiki/Region-based_memory_management#Implementation https://en.wikipedia.org/wiki/Region-based_memory_management... The only twist, with modern 64-bit processors there’s no need for linked lists or multiple blocks, can instead add new physical pages into pre-allocated address space.

michielderhaeg 5y ago

This is what the Glasgow Haskell Compiler runtime does. If you run a Haskell application, you'll see it has uses 1TB of virtual memory. This way you never have to talk to the kernel if you need more memory.

weavie 5y ago
Also Clozure Common Lisp.

stefan_ 5y ago

Address space is unlimited but pages are still 4K.

Const-me 5y ago
Right, I thought about large pages for that, unfortunately on Windows they’re pretty much useless. They require an elevated process, and they are incompatible with swap file i.e. they never paged to disk even when there’s low memory: https://docs.microsoft.com/en-us/windows/win32/memory/large-page-support https://docs.microsoft.com/en-us/windows/win32/memory/large-...
gpderetta 5y ago
and TLB is also a scarce resource.

titzer 5y ago

Well, unfortunately, address space isn't unlimited. In my experience developing 64-bit wasm engines, the typical approach of reserving 8GB of memory for each Wasm memory leads to address space exhaustion after only about 1000 memories (regardless of how many actual pages those memories use). Therefore for a long living VM that might load and unload hundreds or even thousands of programs (on different webpages for example), it's really important to clean up those reservations promptly. In V8, cleaning up the reservations for Wasm memories is ultimately tied to garbage collection of the JS heap, since JS objects can root memory. That led to the somewhat clunky need to retry allocation in a loop, running a full GC if allocation fails the first few times (https://github.com/v8/v8/blob/master/src/objects/backing-store.cc#L366 https://github.com/v8/v8/blob/master/src/objects/backing-sto...). There are also fundamental kernel limitations on virtual memory size. They are system dependent but much lower than 2^64.

Const-me 5y ago
On modern windows the limit is 2^47 bytes: https://docs.microsoft.com/en-us/windows/win32/memory/memory-limits-for-windows-releases#memory-limits-for-windows-and-windows-server-releases https://docs.microsoft.com/en-us/windows/win32/memory/memory... With 8GB of virtual space per engine, should be enough for 16k of these engines. Interesting that you got OOM only after 1k engines, that’s 16x below the limit. Was that on Windows? Actual hardware or some VM substitute? In my use case, I was lucky as I only need an allocator per hardware thread. They never approach thousands. So far, the maximum is 256 hardware threads, like in dual-CPU EPYC 7713.
- titzer 5y ago
  It seems to depend a lot on current conditions and is ultimately probabilistic. I.e. it would not fail 100% at 1000, but some large enough fraction of the time that that strategy was not shippable for Wasm. IIRC it might only have been 10% of the time, but it quickly increases to 100% along a sliding scale up to the hard limit. Part of that is fragmentation as well, because Chrome uses an allocator underneath that can carve out fairly large reservations that fragment the address space.