6 ms·

Growing Buffers to Avoid Copying Data

42 points by ingve 2y ago

Dwedit 2y ago
In addition to growing pages using VirtualAlloc, it's also possible to have the same memory pages mapped at different locations by using memory mapped 'files' (even when the backing file is just the paging file). This means that if your new block isn't contiguous, you can remap the existing memory without a copy. However, system calls also have overhead (thanks Meltdown/Spectre mitigations), and you might not come ahead by avoiding memory copies.
- gpderetta 2y ago
  Any virtual memory manipulation will have massive overhead.
- dividuum 2y ago
  Is there another option besides memfd_create? I'm currently using those to implement a circular buffer that avoids having to reconstruct objects if they happen to cross the size boundary by mapping the same memory twice consecutively into the process space.
  - scottlamb 2y ago
    On Unix-like platforms? sysv shared memory (shmget, etc). https://github.com/gnzlbg/slice_deque/blob/045fb28701d3b674b5da413266ca84b3e5a70190/src/mirrored/sysv.rs#L125-L136 https://github.com/gnzlbg/slice_deque/blob/045fb28701d3b674b... does this. (Though that code looks racy to me; unmapping the second half's virtual address space before mapping again is wrong. I guess it does that because shmat's SHM_REMAP flag is Linux-specific. At least it will fail rather than silently overwrite some other mapping. edit: oh, and it retries too, so not bad.) Seems like you could use shm_open + mmap also. On Linux, you could probably also do some juggling with mremap + MREMAP_DONTUNMAP, but I don't know why you'd prefer this over memfd_create.
edoceo 2y ago
Way back in the ASP3/IIS days, we had these "big" pages and because of the engine building big strings was slow. So, I made this little COM library (Linum) which would simply pre-allocate a buffer for writing into. Yes, a StringBuffer. For those scripts the runtime improved like 500%. Memory usage was only like 10% worse.
- wfn 2y ago
  I have found that a general pattern of setting up a memory arena or anything of that kind does help, especially of course if one anticipates more frequent / heavier usage of heap. Helps with performance (e.g.: faster allocations), memory fragmentation (which itself also helps with performance indirectly of course) and other things. Can be very simple.[1] Or more complicated (if anticipating a lot of allocation work for very varying buffer sizes) - e.g. slab allocators. memcached is an example where this is used, a couple pictures explain the gist.[2] [1]: note: can be even simpler of course, but quick example of structs used: ``` typedef struct char *memory; size_t size; size_t used; } memory_arena_t; typedef struct { memory_arena_t *arenas; size_t arena_count; size_t max_arenas; size_t arena_size; size_t total_size; size_t total_used; } memory_allocator_t; ``` [2]: https://siemens.blog/posts/memcached-memory-model/ https://siemens.blog/posts/memcached-memory-model/ - I'm sure that when heap is visualised, it would show how this helps keeping fragmentation at bay as well (this helps wasting fewer memory pages, too).
xeonmc 2y ago
For win10+ here is also VirtualAlloc2 which permits reserving placeholders as well as a flag for allocating 64k pages.
- kazinator 2y ago
  Windows is no longer economically viable for the kind of work in which you would drop down to doing this kind of thing.
hummusandsushi 2y ago
This reminds me why I keep going back to C. C++ features often clash with each other (especially using object oriented features with classic C), but from the C programmer's point of view the additional features don't really add too much but end up massively constraining the user.
- eddd-ddde 2y ago
  The only thing I ever miss from C++ is a way of guaranteeing that some code is run at every exit path of a function. I guess this is why zig became so popular among C developers.
kazinator 2y ago
Before using realloc, you have to do this: void *sane_realloc(void *ptr, size_t size) { if (ptr == 0) { return malloc(size); } else if (size == 0) { free(ptr); return 0; } else { return realloc(ptr, size); } } ISO C realloc has braindamaged corner cases. Some implementations behave like the above, in which case you can just have #define sane_realloc realloc on those targets. With the above you can initialize a vector to null, with size zero, and use nothing but realloc for the entire lifetime management: growing it from zero to nonzero size allocates it, shrinking down to zero frees it. malloc(0) doesn't necessarily return null; it can return some non-null pointer that can be passed to free. We can get such a thing if we call sane_realloc(0, 0), and can avoid that if we change the malloc line to: return size ? malloc(size) : 0;
- e4m2 2y ago
  According to the standard `realloc(NULL, size)` should already behave like `malloc(size)`. You shouldn't need that special case unless you're working on a system with a very buggy/non-compliant libc.
- amavect 2y ago
  I think that you can omit the call to malloc, as realloc(NULL, size) does the same thing as malloc(size), and free(NULL) does nothing. void *sane_realloc(void *ptr, size_t size) { if (size == 0) { free(ptr); return 0; } else { return realloc(ptr, size); } } Unfortunately, when shrinking an array down to 0, you run into a complication. Detecting allocation failure now requires checking both size > 0 and sane_realloc returning 0. To simplify this further, just always allocate a non-zero size. void *saner_realloc(void *ptr, size_t size) { if (size == 0) { size = 1; } return realloc(ptr, size); }
  - kazinator 2y ago
    But the second sane_realloc now never frees. That's a problem shared by by the ISO C realloc. According to ISO C, size zero can behave like this: free(old) return malloc(0) and if malloc(0) allocates something, we have not achieved freeing. There are ways to implement malloc(0) such that it returns unique pointers, without allocating memory. Or at least not very much memory. For instance we can use the 64 bit space to have some range of (unmapped) virtual addresses where we allocate bytes, and use a compact bitmask (actually allocated somewhere) to keep track of them. Such a scheme was described by Tim Rentsch in the Usenet newsgroup comp.lang.c. If an implementation does such a thing, adjusting the size to 1 will defeat it; allocations of size 1 need real memory. (I can't fathom the requirement why we need malloc(0) to be a source of unique values, and why someone would implement that as efficiently as possible, when it's implementation-defined behavior that portable programs cannot rely on. Why wouldn't you use some library module for unique, space-efficient pointers.) I would never rely malloc(0) to obtain unique pointers at all, let alone pray that it is efficient for that purpose. I'd be happy with a malloc(0) which returns, for instance, ((void *) -1) which can be hidden behind some #define symbol. saner_realloc isn't realloc; it is our API, and we can make it do this: #define SANE_REALLOC_EMPTY ((void *) -1) void *sane_realloc(void *ptr, size_t size) { if (ptr == 0 || ptr == SANE_REALLOC_EMPTY) { return size ? malloc(size) : SANE_REALLOC_EMPTY; } else if (size == 0) { free(ptr); return SANE_REALLOC_EMPTY; } else { return realloc(ptr, size); } } Now, a null return always means failure. The shrink to zero, or allocate zero cases give us SANE_REALLOC_EMPTY which tests unequal to null, and we accept that value for growing or freeing. The caller can also pass in something returned by malloc(0) that is not equal to null or SANE_REALLOC_EMPTY.
wilted-iris 2y ago
I’m surprised that they only ran the measurements ten times. Hard to trust any data in this post given it is certainly deficient.
Animats 2y ago
There's a major concurrency problem in Wine, the Windows emulator for Linux, related to this, which I encountered several years ago. Wine has its own set of DLLs which provide malloc-level services. When you grow a buffer, but it can't be grown in place, a new buffer has to be allocated and the old buffer copied. The trouble is that the copying takes place while holding a spinlock on the entire buffer pool. I had a multi-thread Rust program go into futex congestion and drop performance by two orders of magnitude due to this. 20 threads were all stuck compute-bound trying to acquire the lock. There are several layers of locking involved, and they fight. Wine bug only; works OK on real Windows.[1][2] (bugs.winehq.org seems to be down) [1] https://forum.winehq.org/viewtopic.php?t=37688 https://forum.winehq.org/viewtopic.php?t=37688 [2] https://bugs.winehq.org/show_bug.cgi?id=54979 https://bugs.winehq.org/show_bug.cgi?id=54979
diffuse_l 2y ago
2^48 is 2^16*2^32 = 65536*4GB, not 256*4GB
blibble 2y ago
seems to miss the point that with the giant address space available on a 64-bit system you can mmap whatever size you want, because it's not actually allocated until you touch a byte in the page (including the page tables)
senderista 2y ago
I don't really understand the point of all this (on Linux). Just mmap(2) a virtual address range as large as you think you will ever need and let demand paging do the rest. No need to explicitly reallocate anything.
- remram 2y ago
  This means every buffer uses 4k (page size) minimum of RAM. Sounds very wasteful.
  - senderista 2y ago
    I mean, it depends...
jeffheard 2y ago
Oh man, I remember in 2000 when I first started working in the industry we had this database build process written in Java that took almost 30 days to run. The delivery schedule was monthly, and if anything went wrong we'd have to restart from checkpoint and the database build would be late. It also pegged a 32-CPU SMP DEC Alpha machine for the entire time, which was, well... CPUs would regularly (once every other build or so) cook the socket they were in and have to be replaced. The GS-320 would hot-swap (semi-reliably) so it wasn't a HUGE deal, but it would slow it down and inevitably the build would be a day or two late. Enter myself and a buddy of mine. First thing we discovered was that they were using regular java.lang.Strings for all the string manipulation, and it'd garbage collect for between 30 and 50 seconds every minute once the process got rolling. It used a positively criminal number of threads as well in our predecessor's desperate attempt to make it go faster. SO much time was spent swapping threads on CPUs and garbage collecting that almost no real work got done. Enter the StringBuffer rotation scheme. John and I decided to use the backup GS-160 as a hub to read source data and distribute it among 16 of our floor's desktop machines as an experiment. The hub was written in C++ and did very little other than read a series of fixed-length records from a number of source files and package them up into payloads to ship over socket to the readers. The readers gut-rehabbed the Java code and swapped out StringBuffer for String (and io for nio) to take the majority of garbage collection out of the picture. The trick we employed was to pre-allocate a hoard of StringBuffers with a minimum storage size and put them in a checkin/checkout "repository" where the process could ask for N buffers (generally one per string column) and it'd get a bunch of randomly selected ones from the repo. They'd get used and checked back in dirty. Any buffer that was over a "terminal length" when it was checked in would be discarded and a new buffer would be added in its place. We poked and prodded and when we were finally happy with it, we were down to one garbage collection every 10 minutes on each server. The final build was cut from 30 days to 2.8 and we got allocated a permanent "beowulf cluster" to run our database build.
LegionMammal978 2y ago
At least with glibc's allocator, realloc() will already go straight to mremap() if your buffer is on the order of megabytes. And if the objects in the buffer can't be moved bytewise (e.g., because they have pointers into themselves), then moving them with mremap() instead of realloc() is hardly going to help. Of course, C++ being C++, the language-level position is "it's all UB" either way (except for implicit-lifetime types), and even the proposals for trivial relocation make you go through a special function [0]. [0] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p2786r11.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p27...
hinkley 2y ago
The first time I encountered the memory fragmentation problem common in hashtables wasn't even in a hashtable implementation, it was in a program that used realloc heavily, and doubled the buffer size every time. This was causing massive problems trying to concurrently read a stream over the network and start parsing it, because the realloc had trouble finding appropriately sized fragments. Once I pointed it out to the lead dev he used a different strategy and cut the load time on a multi-megabyte file by a factor of ten. Much later on I would learn that he could have also solved the problem just by adjusting the growth factor to 1.5 instead of 2x.
ncruces 2y ago
Yeah, this is what I do for my Go SQLite driver: reserve a large amount of memory through a protected, private, anonymous mapping, then grow it as needed, hoping that's “free”: https://github.com/ncruces/go-sqlite3/blob/v0.25.0/internal/alloc/alloc_unix.go#L25 https://github.com/ncruces/go-sqlite3/blob/v0.25.0/internal/... The default was to reserve 4GB per connection, because each Wasm sandbox can allocate at most that, and each connection is its own sandbox. It works fine, until it doesn't and I get users complaining this messes up almost everything slightly more complicated than Linux on bare metal: https://news.ycombinator.com/item?id=42057378 https://news.ycombinator.com/item?id=42057378 Now I do mostly the same, but reserve 256MB (or even less) per connection. It works, but it's not free.

42 points by ingve 2y ago

In addition to growing pages using VirtualAlloc, it's also possible to have the same memory pages mapped at different locations by using memory mapped 'files' (even when the backing file is just the paging file). This means that if your new block isn't contiguous, you can remap the existing memory without a copy. However, system calls also have overhead (thanks Meltdown/Spectre mitigations), and you might not come ahead by avoiding memory copies.

gpderetta 2y ago
Any virtual memory manipulation will have massive overhead.
dividuum 2y ago
Is there another option besides memfd_create? I'm currently using those to implement a circular buffer that avoids having to reconstruct objects if they happen to cross the size boundary by mapping the same memory twice consecutively into the process space.
- scottlamb 2y ago
  On Unix-like platforms? sysv shared memory (shmget, etc). https://github.com/gnzlbg/slice_deque/blob/045fb28701d3b674b5da413266ca84b3e5a70190/src/mirrored/sysv.rs#L125-L136 https://github.com/gnzlbg/slice_deque/blob/045fb28701d3b674b... does this. (Though that code looks racy to me; unmapping the second half's virtual address space before mapping again is wrong. I guess it does that because shmat's SHM_REMAP flag is Linux-specific. At least it will fail rather than silently overwrite some other mapping. edit: oh, and it retries too, so not bad.) Seems like you could use shm_open + mmap also. On Linux, you could probably also do some juggling with mremap + MREMAP_DONTUNMAP, but I don't know why you'd prefer this over memfd_create.

edoceo 2y ago

Way back in the ASP3/IIS days, we had these "big" pages and because of the engine building big strings was slow. So, I made this little COM library (Linum) which would simply pre-allocate a buffer for writing into. Yes, a StringBuffer. For those scripts the runtime improved like 500%. Memory usage was only like 10% worse.

wfn 2y ago
I have found that a general pattern of setting up a memory arena or anything of that kind does help, especially of course if one anticipates more frequent / heavier usage of heap. Helps with performance (e.g.: faster allocations), memory fragmentation (which itself also helps with performance indirectly of course) and other things. Can be very simple.[1] Or more complicated (if anticipating a lot of allocation work for very varying buffer sizes) - e.g. slab allocators. memcached is an example where this is used, a couple pictures explain the gist.[2] [1]: note: can be even simpler of course, but quick example of structs used: ``` typedef struct char *memory; size_t size; size_t used; } memory_arena_t; typedef struct { memory_arena_t *arenas; size_t arena_count; size_t max_arenas; size_t arena_size; size_t total_size; size_t total_used; } memory_allocator_t; ``` [2]: https://siemens.blog/posts/memcached-memory-model/ https://siemens.blog/posts/memcached-memory-model/ - I'm sure that when heap is visualised, it would show how this helps keeping fragmentation at bay as well (this helps wasting fewer memory pages, too).

xeonmc 2y ago

For win10+ here is also VirtualAlloc2 which permits reserving placeholders as well as a flag for allocating 64k pages.

kazinator 2y ago
Windows is no longer economically viable for the kind of work in which you would drop down to doing this kind of thing.

hummusandsushi 2y ago

This reminds me why I keep going back to C. C++ features often clash with each other (especially using object oriented features with classic C), but from the C programmer's point of view the additional features don't really add too much but end up massively constraining the user.

eddd-ddde 2y ago
The only thing I ever miss from C++ is a way of guaranteeing that some code is run at every exit path of a function. I guess this is why zig became so popular among C developers.

kazinator 2y ago

Before using realloc, you have to do this: void *sane_realloc(void *ptr, size_t size) { if (ptr == 0) { return malloc(size); } else if (size == 0) { free(ptr); return 0; } else { return realloc(ptr, size); } } ISO C realloc has braindamaged corner cases. Some implementations behave like the above, in which case you can just have #define sane_realloc realloc on those targets. With the above you can initialize a vector to null, with size zero, and use nothing but realloc for the entire lifetime management: growing it from zero to nonzero size allocates it, shrinking down to zero frees it. malloc(0) doesn't necessarily return null; it can return some non-null pointer that can be passed to free. We can get such a thing if we call sane_realloc(0, 0), and can avoid that if we change the malloc line to: return size ? malloc(size) : 0;

e4m2 2y ago
According to the standard `realloc(NULL, size)` should already behave like `malloc(size)`. You shouldn't need that special case unless you're working on a system with a very buggy/non-compliant libc.
amavect 2y ago
I think that you can omit the call to malloc, as realloc(NULL, size) does the same thing as malloc(size), and free(NULL) does nothing. void *sane_realloc(void *ptr, size_t size) { if (size == 0) { free(ptr); return 0; } else { return realloc(ptr, size); } } Unfortunately, when shrinking an array down to 0, you run into a complication. Detecting allocation failure now requires checking both size > 0 and sane_realloc returning 0. To simplify this further, just always allocate a non-zero size. void *saner_realloc(void *ptr, size_t size) { if (size == 0) { size = 1; } return realloc(ptr, size); }
- kazinator 2y ago
  But the second sane_realloc now never frees. That's a problem shared by by the ISO C realloc. According to ISO C, size zero can behave like this: free(old) return malloc(0) and if malloc(0) allocates something, we have not achieved freeing. There are ways to implement malloc(0) such that it returns unique pointers, without allocating memory. Or at least not very much memory. For instance we can use the 64 bit space to have some range of (unmapped) virtual addresses where we allocate bytes, and use a compact bitmask (actually allocated somewhere) to keep track of them. Such a scheme was described by Tim Rentsch in the Usenet newsgroup comp.lang.c. If an implementation does such a thing, adjusting the size to 1 will defeat it; allocations of size 1 need real memory. (I can't fathom the requirement why we need malloc(0) to be a source of unique values, and why someone would implement that as efficiently as possible, when it's implementation-defined behavior that portable programs cannot rely on. Why wouldn't you use some library module for unique, space-efficient pointers.) I would never rely malloc(0) to obtain unique pointers at all, let alone pray that it is efficient for that purpose. I'd be happy with a malloc(0) which returns, for instance, ((void *) -1) which can be hidden behind some #define symbol. saner_realloc isn't realloc; it is our API, and we can make it do this: #define SANE_REALLOC_EMPTY ((void *) -1) void *sane_realloc(void *ptr, size_t size) { if (ptr == 0 || ptr == SANE_REALLOC_EMPTY) { return size ? malloc(size) : SANE_REALLOC_EMPTY; } else if (size == 0) { free(ptr); return SANE_REALLOC_EMPTY; } else { return realloc(ptr, size); } } Now, a null return always means failure. The shrink to zero, or allocate zero cases give us SANE_REALLOC_EMPTY which tests unequal to null, and we accept that value for growing or freeing. The caller can also pass in something returned by malloc(0) that is not equal to null or SANE_REALLOC_EMPTY.

wilted-iris 2y ago

I’m surprised that they only ran the measurements ten times. Hard to trust any data in this post given it is certainly deficient.

Animats 2y ago

There's a major concurrency problem in Wine, the Windows emulator for Linux, related to this, which I encountered several years ago. Wine has its own set of DLLs which provide malloc-level services. When you grow a buffer, but it can't be grown in place, a new buffer has to be allocated and the old buffer copied. The trouble is that the copying takes place while holding a spinlock on the entire buffer pool. I had a multi-thread Rust program go into futex congestion and drop performance by two orders of magnitude due to this. 20 threads were all stuck compute-bound trying to acquire the lock. There are several layers of locking involved, and they fight. Wine bug only; works OK on real Windows.[1][2] (bugs.winehq.org seems to be down) [1] https://forum.winehq.org/viewtopic.php?t=37688 https://forum.winehq.org/viewtopic.php?t=37688 [2] https://bugs.winehq.org/show_bug.cgi?id=54979 https://bugs.winehq.org/show_bug.cgi?id=54979

diffuse_l 2y ago

2^48 is 2^16*2^32 = 65536*4GB, not 256*4GB

blibble 2y ago

seems to miss the point that with the giant address space available on a 64-bit system you can mmap whatever size you want, because it's not actually allocated until you touch a byte in the page (including the page tables)

senderista 2y ago

I don't really understand the point of all this (on Linux). Just mmap(2) a virtual address range as large as you think you will ever need and let demand paging do the rest. No need to explicitly reallocate anything.

remram 2y ago
This means every buffer uses 4k (page size) minimum of RAM. Sounds very wasteful.
- senderista 2y ago
  I mean, it depends...

jeffheard 2y ago

Oh man, I remember in 2000 when I first started working in the industry we had this database build process written in Java that took almost 30 days to run. The delivery schedule was monthly, and if anything went wrong we'd have to restart from checkpoint and the database build would be late. It also pegged a 32-CPU SMP DEC Alpha machine for the entire time, which was, well... CPUs would regularly (once every other build or so) cook the socket they were in and have to be replaced. The GS-320 would hot-swap (semi-reliably) so it wasn't a HUGE deal, but it would slow it down and inevitably the build would be a day or two late. Enter myself and a buddy of mine. First thing we discovered was that they were using regular java.lang.Strings for all the string manipulation, and it'd garbage collect for between 30 and 50 seconds every minute once the process got rolling. It used a positively criminal number of threads as well in our predecessor's desperate attempt to make it go faster. SO much time was spent swapping threads on CPUs and garbage collecting that almost no real work got done. Enter the StringBuffer rotation scheme. John and I decided to use the backup GS-160 as a hub to read source data and distribute it among 16 of our floor's desktop machines as an experiment. The hub was written in C++ and did very little other than read a series of fixed-length records from a number of source files and package them up into payloads to ship over socket to the readers. The readers gut-rehabbed the Java code and swapped out StringBuffer for String (and io for nio) to take the majority of garbage collection out of the picture. The trick we employed was to pre-allocate a hoard of StringBuffers with a minimum storage size and put them in a checkin/checkout "repository" where the process could ask for N buffers (generally one per string column) and it'd get a bunch of randomly selected ones from the repo. They'd get used and checked back in dirty. Any buffer that was over a "terminal length" when it was checked in would be discarded and a new buffer would be added in its place. We poked and prodded and when we were finally happy with it, we were down to one garbage collection every 10 minutes on each server. The final build was cut from 30 days to 2.8 and we got allocated a permanent "beowulf cluster" to run our database build.

LegionMammal978 2y ago

At least with glibc's allocator, realloc() will already go straight to mremap() if your buffer is on the order of megabytes. And if the objects in the buffer can't be moved bytewise (e.g., because they have pointers into themselves), then moving them with mremap() instead of realloc() is hardly going to help. Of course, C++ being C++, the language-level position is "it's all UB" either way (except for implicit-lifetime types), and even the proposals for trivial relocation make you go through a special function [0]. [0] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p2786r11.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p27...

hinkley 2y ago

The first time I encountered the memory fragmentation problem common in hashtables wasn't even in a hashtable implementation, it was in a program that used realloc heavily, and doubled the buffer size every time. This was causing massive problems trying to concurrently read a stream over the network and start parsing it, because the realloc had trouble finding appropriately sized fragments. Once I pointed it out to the lead dev he used a different strategy and cut the load time on a multi-megabyte file by a factor of ten. Much later on I would learn that he could have also solved the problem just by adjusting the growth factor to 1.5 instead of 2x.

ncruces 2y ago

Yeah, this is what I do for my Go SQLite driver: reserve a large amount of memory through a protected, private, anonymous mapping, then grow it as needed, hoping that's “free”: https://github.com/ncruces/go-sqlite3/blob/v0.25.0/internal/alloc/alloc_unix.go#L25 https://github.com/ncruces/go-sqlite3/blob/v0.25.0/internal/... The default was to reserve 4GB per connection, because each Wasm sandbox can allocate at most that, and each connection is its own sandbox. It works fine, until it doesn't and I get users complaining this messes up almost everything slightly more complicated than Linux on bare metal: https://news.ycombinator.com/item?id=42057378 https://news.ycombinator.com/item?id=42057378 Now I do mostly the same, but reserve 256MB (or even less) per connection. It works, but it's not free.