13 ms·

Writing a simple pool allocator in C

307 points by 8dcc 2y ago

liontwist 2y ago
The pool struct Is two pointers, why are you allocating it with Malloc?
- o11c 2y ago
  Some people are allergic to `main() { Foo foo; foo_init(&foo); }` Admittedly, sometimes for good reason - it locks in the ABI.
  - MathMonkeyMan 2y ago
    Is that why some structs have "char reserved[16]" data members? I think I saw this in NGINX, though that might have been to allow module compatibility between the open source offering and the paid version.
    - o11c 2y ago
      Yes, that slightly improves ABI flexibility, though the fact that callers can still access fields limits that. An alternative is to make the only member `char opaque[16]` (IIRC some locale-related thing in glibc does this, also I think libpng went through a transition of some sort related to this?), but calculating the size can be difficult outside of trivial cases since you can't use sizeof/offsetof.
  - liontwist 2y ago
    ABI? Better make it an anonymous struct too. It’s a performance oriented custom memory allocator.
  - kazinator 2y ago
    Mainly just the size and alignment. If you make the structure oversized, and with strict alignment, it can be future proofed. Old binary clients will provide a structure big enough and aligned enough for the new version. The dynamic constructor API can allocate the structure exactly sized without the padding.
- unwind 2y ago
  Next question: why are there two calls to `malloc()`, one for the Pool structure and one for the Chunks? It is trivial to co-allocate them which removes the risk of memory fragmentation and is just generally a good idea if you're chasing performance. The answer might be "for clarity/simplicity" which I guess is fine in an informative article, but it could at least be highlighted in the text which I didn't see.
  - 8dcc 2y ago
    I will also take note of this, you are right.
  - jdnxbdn 2y ago
    It is certainly not trivial and would add little to the topic
  - kevin_thibedeau 2y ago
    He's targeting ANSI C, C89. Flexible array members are not supported officially until C99. 26 years later, it's time to stop clinging to outdated standards and crusty tooling. Even Linux had to read the room and adopt C11. A C11 implementation could go one step further and use _Alignas(max_align_t) to keep the pool array aligned with no manual effort. The double allocation does this implicitly.
    - liontwist 2y ago
      The pool needs to align every allocation anyway.
    - listeria 2y ago
      on the topic of alignment, the library (libpool) fails to align chunk_sz to allow storing a pointer when in the free_chunk list. This issue is sidestepped in TFA by using a union, which ensures appropiate alignment for all it's members, but in the library there's nothing which prevents me from asking for a chunk size of, say, 9 bytes, which would store pointers at misaligned addresses when creating the free-list.
- lyu07282 2y ago
  Couldn't this also just syscall mmap directly? I mean malloc itself is a memory allocator it feels a bit strange to use it in an allocator implementation, but perhaps I'm missing something.
keyle 2y ago
The parent article is quite interesting and slightly different being cpp [1]. There is also a post about writing a memory allocator [2]. [1]: http://dmitrysoshnikov.com/compilers/writing-a-pool-allocator/ http://dmitrysoshnikov.com/compilers/writing-a-pool-allocato... [2]: http://dmitrysoshnikov.com/compilers/writing-a-memory-allocator/ http://dmitrysoshnikov.com/compilers/writing-a-memory-alloca...
10000truths 2y ago
I recommend against using linked lists for bookkeeping the free blocks. It seems to be the data structure that every malloc/free implementation reaches for, and I don't know why - the slowness of pointer-chasing makes it terrible for almost any real-world use case. A balanced tree would be a much better idea, given that all the essential operations would take O(log n) time instead of O(n). Even if one insists on a linear search, a bitset is much more cache friendly than pointer-chasing and it can trivially benefit from SIMD optimizations.
- ben-schaaf 2y ago
  I don't think you understand how the allocator in the article works. Allocating and freeing are already O(1), creating and closing the allocator are necessarily O(n). There is no search being done here.
- o11c 2y ago
  For the `Chunk` list, this isn't one of the cases where linked lists are harmful. Each use only touches the top of the stack, never iterates. Also, linked lists are much easier to make thread-safe. For the `LinkedPtr` list, the bad case is only hit during the destruction of the pool, and then only if you allocate a lot of memory. And given the overhead of deallocation I'm not sure the array approach would measurably help. I don't see anywhere a binary tree search would be useful here, since there are no loops used for lookup (on allocation they're pushed in order, but when freed chunks are pushed in arbitrary order; this does mean no double-free protection).
  - harrison_clarke 2y ago
    why would you need to iterate on destruction? you free the whole pool at once, since you allocate it all at once
- DevelopingElk 2y ago
  The reason linked lists are used is for large enough allocations, there is no overhead. You use the space the application isn't using. In addition, if all allocations are the same size it is O(1), you just look at the head of the list. More sophisticated strategies bucket allocations by size, this has fixed overhead. You can also use balanced trees for more memory efficiency, but this is slower. For small allocations (8 bytes) that are too small to contain pointers allocators will allocate a block and use bitsets.
sour-taste 2y ago
Some interesting things that would be interesting to add to this: - thread safety ( not too hard to add on top of your liked list) - variable sized allocations. Ideally something more akin to malloc. Could be done wastefully by rounding up to the nearest chunk size - (as mentioned in the article) variable chunk sizes - zeroing of memory before handing it back to users - double free detection or even better full asan support
- 8dcc 2y ago
  I don't currently have much experience with thread safety, but it's something I should look into. Thank you.
kazinator 2y ago
If you write your own allocator in C, do yourself a favor and use the valgrind API inside it. Its use can be conditional so you can "compile it out". Or should I say it has to be, so you can build the code in an environment where there's no valgrind API.
- gopalv 2y ago
  +1 - this isn't even that hard, it is include a single header + annotate allocations/frees, with some redzones around the actual allocation to know when the user-code is writing into the pool pointer areas. https://developers.redhat.com/articles/2022/03/23/use-valgrind-memcheck-custom-memory-manager https://developers.redhat.com/articles/2022/03/23/use-valgri...
  - deleted 2y ago
    [deleted]
  - hooli_gan 2y ago
    https://en.wikipedia.org/wiki/Red_zone_(computing) https://en.wikipedia.org/wiki/Red_zone_(computing)
  - dsp_person 2y ago
    oof love on this page how scrolling hijacks the back button
  - swah 2y ago
    Thats with Claude, right?
    - gopalv 2y ago
      > with Claude The comment itself is AI generated or the code reference? Here's some of my old code https://github.com/php/pecl-caching-apc/blob/0dd2a69bab58822ba86a88445de06638a6a2456d/apc_pool.c#L221 https://github.com/php/pecl-caching-apc/blob/0dd2a69bab58822...
- 8dcc 2y ago
accelbred 2y ago
Note that using this will likely violate strict aliasing due to using the void pointer returned as one type, freeing it, and then getting that same chunk again and using it as another type. You'll probably want to compile with -fno-strict-aliasing to be safe. A good reference on strict aliasing: https://gist.github.com/shafik/848ae25ee209f698763cffee272a58f8 https://gist.github.com/shafik/848ae25ee209f698763cffee272a5...
- leni536 2y ago
  That's what allocators do. If C's object model doesn't allow users of the language to write their own allocators then that object model is broken. C++ relatively has fixes to allow allocators to work, it requires calls to std::launder.
  - dwattttt 2y ago
    I understand the C standard hides such actions behind a wall of "this is the allocator", and expected the compiler authors to also be the allocator authors, allowing them to know when/how they can break such rules (in the context of their own compiler)
    - unwind 2y ago
      No, allocators are not magic (in that regard) in C. There is nothing out of the ordinary going on with an allocator, the parent comment is simply mistaken (as pointed out by another answer).
      - dwattttt 2y ago
        Ah, I see that it's because the char type never violates Strict Aliasing. I was wondering how you could define a type such as Chunk, yet hand out a pointer to it to a user who will cast it to some other type.
        SleepyMyroslav 2y ago
8fingerlouie 2y ago
A long time ago, in a galaxy far far away, i wrote something similar for an embedded platform. I was implementing a WAP Browser at the time (yes, WAP, https://en.wikipedia.org/wiki/Wireless_Application_Protocol https://en.wikipedia.org/wiki/Wireless_Application_Protocol), and we needed dynamic memory allocation in an environment where everything was static due to realtime constraints. So i ended up with this : https://github.com/jinie/memmgr https://github.com/jinie/memmgr
openmarkand 2y ago
[flagged]
- oguz-ismail 2y ago
  > using GPL as the license for a library is kind of limiting That's the point of using GPL
- matheusmoreira 2y ago
  He should have used AGPLv3. Anyone who doesn't like it should contact him with a business proposal for a proprietary license.
- andrewmcwatters 2y ago
  Almost no one should be using the MIT or equivalent licenses anymore now that the industry has been overrun by commercial freeloaders. AGPL or GPLv2 and above.
guardian5x 2y ago
The Latin Modern font on this website does not look so good in Chrome, is it because of the font size, or is it just me? (Chrome)
- johnisgood 2y ago
  I was going to say this. Looks awful to me as well. It is the font-family.
- dmonitor 2y ago
  Sounds like a Windows issue based on other people in the thread. I'm on Firefox with the same issue. Removing Latin-modern from the CSS file made it much more readable for me.
9029 2y ago
Another (admittedly less portable) way to solve the resizing problem is to reserve a large virtual memory space using linux mmap with the PROT_NONE flag and then commit pages as needed using mprotect with PROT_READ|PROT_WRITE flags. I believe windows' VirtualAlloc/VirtualProtect also allows this
- jeffbee 2y ago
  You don't need to do anything with the flags. You can just mmap a huge virtual area and the pages will be realized whenever you first touch them.
  - 9029 2y ago
    Today I learned, thanks
cb321 2y ago
One aspect people don't tend to mention (and TFA does not because it has "general purpose" as a scope) about doing your own allocation arenas is that because a "pointer" is just the name (really number) of an allocated region, this also affords flexibility in the width of those numbers aka "pointer size" that decides your "address" space. So, for example, if you are willing to limit yourself to 64 KiNodes of equal sized objects, a pool like https://github.com/c-blake/bst/blob/main/POOL.c https://github.com/c-blake/bst/blob/main/POOL.c can use an unsigned short 2-byte pointer. This small address space specialization can give a full 4x space overhead optimization over modern 64-bit pointers. You could even use 8x less with 1-byte pointers if 256 nodes is enough or use bit fields or equivalents for even more fine-grained address space size selection. Admittedly, linked structures are usually less interesting for very small address space sizes, but this is sometimes useful. People may complain about arbitrary limits that relate to this kind of optimization, but the linked part could be "small by design" without compromising overall scale { such as for structure within a B-tree node or other multi-level indexing setups }. In any event, I think it is useful to highlight pointer size arbitrariness to junior engineers. It is often learned once & immediately forgotten behind an onslaught of general purpose-ness (& pointer type systems/syntax). Relocation ideas also relate. E.g., if all the pointers are implicitly indices into a (small?) array, and all the code needs a "base address" of that array to get a VMem address, then you can relocate the whole bundle of objects pretty easily changing only the base address.
- 8dcc 2y ago
  Yes, this is true. I didn't use that in the code because I thought it would make it less readable, though. I might mention it somewhere, thank you.
  - cb321 2y ago
    In many prog.lang's, it absolutely makes things less readable. This is not an accident, but because the PL itself specifically tries to syntactically support pointer types (i.e. to literally aid readability). Most PLs do so only for general purpose VMem pointers with user-defined pointers being afterthoughts (at best). You probably need (at least!) operator overloading to get the same level of readability as "PL-native" pointers { though "readability" is a bit subjective and powerful PL features can be divisive; Scare "quotes" for interpretation hazard :-) }. Anyway, you probably knew all that & I don't mean to suggest otherwise, but it made sense to write since HN loves PL talk.
matheusmoreira 2y ago
This is really informative. I wonder if there is a better solution for the reallocation problem, one that preserves pointers.
- kragen 2y ago
  You can keep the raw pointers inside your manager object for a particular object type and only hand out some kind of handle that requires an indirection step, such as an array index.
  - matheusmoreira 2y ago
    I've seen that design before. Base and offset easily allows relocations of data in memory. https://www.man7.org/linux/man-pages/man2/mremap.2.html https://www.man7.org/linux/man-pages/man2/mremap.2.html If the mapping is relocated, then absolute pointers into the old mapping location become invalid (offsets relative to the starting address of the mapping should be employed). I've always assumed that forcing an indirection causes a noticeable performance impact. I mean, everyone uses absolute pointers by default, right?
    - kragen 2y ago
      There are a lot of variations on it: - Unix file descriptors are small-integer array indices into, normally‚ arrays in kernel space. - Many Smalltalk implementations, especially on older machines, named objects in memory with small-integer indices into a global object table (typically shifted in some way to accommodate tagged SmallIntegers) which was implemented as an array of pointers to the real object locations. - Functions exported from DLLs on Windows can be identified by "ordinals" that index a table of all exported functions instead of by name. - PalmOS, Win16, and Pre-X MacOS identified allocations of memory from the operating system by "handles" which were, again, indices into a table of pointers, the master pointer block. To access the actual memory you would call HLock() (MacOS name) and index the table (yourself, on MacOS, or using the return value from the lock function on PalmOS or Win16) to get the physical address, which could change if the handle was unlocked. - Forth maintained an in-memory buffer cache of 1024-byte disk blocks, which it identified by ordinal number rather than, say, cylinder/head/sector tuples or inode+offset tuples. To get the memory address of block 53, you would say 53 block (Forth for "block(53)") and freely index into those 1024 bytes, which were guaranteed to remain resident until the next call to block or until you yielded the CPU with another I/O operation. If you modified the data there, you would call update to tell Forth the buffer was modified. If block 53 was not currently in memory, Forth would pause your task until it had loaded it, running other tasks meanwhile. If there was no free block buffer, Forth would free one up, by writing out a modified buffer to disk if necessary. This provided a sort of virtual memory in about 100 lines of code without requiring memory-mapping hardware. (The "BLOCK I/O" part of F83's KERNEL86.FS is 8 16-line screens long, but a fair bit of that is actually dealing with MS-DOS's file I/O functions.) - Because standard Pascal had no string type and no way to handle variable-length arrays of any kind, TeX uses indices into a string table as its string type. It inserts newly encountered strings in the string table. - Symbols in some Lisps. - Pretty much anything in any Fortran program. See http://www.the-adam.com/adam/rantrave/st02.pdf http://www.the-adam.com/adam/rantrave/st02.pdf on how to program Fortran in any language. How noticeable the performance impact is depends a lot on how often you have to traverse the extra level of indirection. (Doing a base+offset addition before each memory access could be a significant performance issue on things like a Commodore 64 or a TRS-80 but basically doesn't matter on 8086 or better hardware.)
kragen 2y ago
This is a very nice article! The diagrams in particular are very clear. (They seem to have been done in draw.io: https://github.com/8dcc/8dcc.github.io/blob/main/img/pool-allocator4.svg?short_path=a1a0364 https://github.com/8dcc/8dcc.github.io/blob/main/img/pool-al... which seems to be a pretty decent Apache-2.0 free software licensed diagram editor: https://github.com/jgraph/drawio/ https://github.com/jgraph/drawio/) I think it would be improved further if it began with the calling interface callers use to invoke the allocator, because it's easier to understand the implementation of some service such as pool allocation when you begin by knowing what service, exactly, is required. I began with the assumption that the author was describing an arena allocator under another name, rather than a fixed-size block allocator, both because the APR's influential arena allocator is called "apr_pool_t" and because one of the main headings in the table of contents (a greatly appreciated feature, like all the typography of the article) was "Closing the pool". It took me quite a while to figure out that I was mistaken. It's plausible that I only had this problem because I am an unusually stupid, ignorant, or pigheaded person (some would say all three), but, if not, many other people will have the same difficulty I had of taking several minutes to figure out what the topic of the article is. (I could have saved myself by clicking either of the first two links in the Introduction, but I didn't because I thought I already knew what it was.) The current top-voted comment on this thread is by someone who had the same reading comprehension problem I did, but never realized their erorr: https://news.ycombinator.com/item?id=42643951 https://news.ycombinator.com/item?id=42643951 and nobody had pointed out their mistaek until I did just now. So I think we can say with some confidence that many HN readers will have the same difficulty. I think that the article would also be improved by a few other small additions: - It says, "The pool allocator, however, is much faster than malloc", but doesn't provide any benchmarks or even an order of magnitude. - Probably when one benchmarks the implementation given, one will find that it is only slightly faster than jemalloc or even gnumalloc, because they both dispatch small allocations to a fixed-block allocator similar to this one, and the dispatch isn't very expensive. This can be fixed by inlining the allocation fast path and the deallocation function, which will then compile down to a few instructions each. A simple demonstration of how to do this is in my arena allocator kmregion in http://canonical.org/~kragen/sw/dev3/kmregion.h http://canonical.org/~kragen/sw/dev3/kmregion.h and http://canonical.org/~kragen/sw/dev3/kmregion.c http://canonical.org/~kragen/sw/dev3/kmregion.c (GPLv3+). The current implementation of 8dcc libpool is guaranteed to be unable to do this unless you're using link-time optimization or a so-called "unity" or "amalgamation" build process. - It's worth distinguishing between average-case performance (in which this allocator is slightly better than malloc) and worst-case performance (in which case malloc, generally speaking, isn't even in the running). - It may be worth mentioning that often such pool allocators are used in conjunction with initializing the objects in the pool to a valid state when the pool is created; that way you don't have to reinitialize objects to a valid state every time you deallocate and reallocate them, which is usually more work than malloc does to find the right free list. This does require not overwriting the user data with your freelist pointer, so it's a space/time tradeoff. - Maybe you should mention alignment, especially now that even on amd64 GCC has taken to using new instructions that require alignment. Even as it is, though, it's highly educational, visually pleasant, and very understandable (once I got over my initial misconception of having a totally wrong idea of what the article was about).
jll29 2y ago
This code is very beautifully written, thanks for sharing. However, you should consult the book "C: Interfaces and Implementations" by Dave Hanson, which has a library called "Arena" that is very similar to your "Pool"s, and it shows a few more tricks to make the code safer and easier to read (Chapters 5+6, 6 in particular). D. Hanson's book (written in the 'literary programming' style invented by Donal Knuth) also demonstrates having debugging and production implementations for the same C API to catch memory errors, and his book is from 1997: > Copyright © 1997 by David R. Hanson (He used to be a SE professor I Princeton before getting hired by Microsoft, I believe.)
- 8dcc 2y ago
  Thank you so much! I will definitely check it out. I also planned on writing an article about arena allocators soon.
- kragen 2y ago
  I think you mean "literate programming". The arena allocator in Hanson's chapter 6 is an arena allocator, not a "pool allocator" in the sense that 8dcc means, which is to say, a constant-time fixed-size-block allocator. It seems that you had the same reading comprehension problem that I did. The difference is that Hanson's arena allocator can make allocations of any size (his Arena_alloc takes an nbytes argument) and cannot deallocate individual allocations, only the entire arena (his Arena_free takes only an arena pointer as a parameter). A fixed-size-block allocator like the one we are discussing here can only make allocations of a fixed size, but can recycle them individually, not only all at once. (If Hanson's name sounds familiar, it might be because you've read the lcc book.) It may be worth noting that Donald Knuth also invented the font used in 8dcc's article.
  - actionfromafar 2y ago
    Honestly, "literary programming" does better explain how Knuth writes code.
    - kragen 2y ago
exDM69 2y ago
Here's another interesting O(1) memory allocator but with arbitrary sized allocations and low fragmentation. Negative side is relatively high memory overhead (a few dozen bytes per allocation). This kind of allocator is often used to suballocate GPU memory in game and graphics applications. I'm using a variant of this algorithm with added support for shrinkable and aligned allocations and flexible bin sizing. You can also extend this idea to two dimensions to create texture atlases, which is possible in O(1) for power of two sized allocations. Original: https://github.com/sebbbi/OffsetAllocator https://github.com/sebbbi/OffsetAllocator Rust port: https://crates.io/crates/offset-allocator https://crates.io/crates/offset-allocator
2rsf 2y ago
This bring old memories back, I implemented something similar on a motorola 68360 ages ago. Since the size of the buffer I used was not huge I skipped the pointers and simply enumerated each chunk, it was remarkably efficient and stable.
codr7 2y ago
I usually default to slab allocators if I have to write my own: https://github.com/codr7/libcbs#slab-allocation https://github.com/codr7/libcbs#slab-allocation
drysine 2y ago
Also "Arena allocator tips and tricks (nullprogram.com)" [0] [0] https://news.ycombinator.com/item?id=37670740 https://news.ycombinator.com/item?id=37670740
sylware 2y ago
It all depends on the load profile using the allocator. You never know, that said you cannot beat, in theory, a semantically specialized allocator for a specific load... in other words, the right way(TM). This means applications should bundle their own allocators for the various load types they have. The "generic" allocator is sort of an heresy for the lazy, short termists or those who are in hurry. Don't worry I still use such generic allocator, sometimes, but often I do mmap myself the memory and deal directly with it.
- astrange 2y ago
  The system allocator is the one that comes with all the system's memory debugging tools and security (or lack of it), so you'd better not mind losing those if you want to ditch it.
voctor 2y ago
There is a small series of posts on the BitSquid blog about memory allocation which is worth reading! http://bitsquid.blogspot.com/2015/08/allocation-adventures-3-buddy-allocator.html http://bitsquid.blogspot.com/2015/08/allocation-adventures-3...
8dcc 2y ago
Hello, I am the author. Thank you all for the instructive comments, I made some changes to the article since I first posted it: - Added a link to this HN post. - Renamed some variables and types in the code for readability. - Mention (in a footnote) that we could allocate the 'Pool' structure and the chunk arrays with a single call, or even return the 'Pool' on the stack. Suggested by 'liontwist' and 'unwind'. - Mention (in a footnote) that we don't always need to store the full address when building the linked list of free chunks. Suggested by 'cb321'. - Added valgrind support (also to my 'libpool' project). Suggested by 'kazinator'.
- cb321 2y ago
  FWIW, while it is true that a smaller pointer lets you have smaller minimum fixed size objects in your pool, as your new footnote suggests, the space concern I was mostly alluding to in [1] is all the references in your client code { such as the BST code I linked to where each binary search tree (BST) node has 2 pointers (or 3 if they have parent pointers to give BST nodes "doubly linked list-like autonomy") }. This can really add up. For example, like 20 years ago, I did a `print sizeof` in gdb for some g++ STL map node with a data payload of like 4 bytes and it was some obscene size approximately >= 1 order of magnitude bigger than necessary (like 80 bytes instead of, say 8 with 2Byte ptrs). While main memory is cheap, CPU cache memory is not and for "linky" structures, it often pays to be more cache-friendly. It's pretty easy to imagine a 10X smaller thing fitting into an L2 CPU cache where the larger thing would not even fit in L3, netting you a big latency boost (though the more root-ward levels of the tree likely always stay in caches in a hot loop). EDIT: Anyway, you don't have to believe me. Others did an x32 ABI for x86_64 mostly to have "merely 2X" smaller pointers: https://en.wikipedia.org/wiki/X32_ABI https://en.wikipedia.org/wiki/X32_ABI [1] https://news.ycombinator.com/item?id=42643410 https://news.ycombinator.com/item?id=42643410
- veltas 2y ago
  Also the font isn't incredibly easy to read on Windows. I'm assuming Georgia was selected? Which has been on Windows for years but renders so badly it looks like the font color isn't black, even though I think it is black? This isn't really your fault but I would have stuck to Times New Roman for Windows' sake.
jhallenworld 2y ago
A sometimes useful thing is to treat the pool as a stack and provide a call to free all recently allocated items up to a certain index. So you make a bunch of deep subroutine calls that use the pool allocator, and then on return free them all. It's like a secondary automatic storage class. Also sometimes useful to provide another call to promote an automatic item to a more permanent one so that it is excluded from being freed like this.
harrison_clarke 2y ago
you can avoid resizing and moving the pools if you allocate massive pools up front. most OSs let you overcommit memory, and most programs using memory pools only have a handful of them (on windows, you'd need to handle this with VirtualAlloc. osx and linux let you overcommit with malloc, and handle it with a copy-on-write page fault handler)
lelandbatey 2y ago
It seems like almost all of the complexity of this allocator comes from having to manage the fact that it's being implemented on top of the system allocator. I thought the whole point of using a custom allocator was to avoid the system allocator for exactly the problems they mention e.g. calling the system-provided realloc() might move your stuff around, having to track separate pool starts so you can call the system-provided free() on them, etc. Like, yeah you have to do that, but I thought the whole point of writing a custom allocator was to not use the system allocator beyond statically allocating a huge block of memory upfront and then managing that yourself, is it not?
- 8dcc 2y ago
  > I thought the whole point of writing a custom allocator was to not use the system allocator beyond statically allocating a huge block of memory upfront and then managing that yourself, is it not? Yes, that's what the article is basically about. The other problems you mention only happen when trying to expand an existing pool, which might not be necessary for some people.
alecco 2y ago
(related) LLFree Paper: LLFree: Scalable and Optionally-Persistent Page-Frame Allocation https://www.usenix.org/system/files/atc23-wrenger.pdf https://www.usenix.org/system/files/atc23-wrenger.pdf Video presentation: https://www.youtube.com/watch?v=yvd3D5VOHc8 https://www.youtube.com/watch?v=yvd3D5VOHc8 Implementation and benchmarks are well documented at the repos: Rust repo https://github.com/luhsra/llfree-rs https://github.com/luhsra/llfree-rs C repo https://github.com/luhsra/llfree-c https://github.com/luhsra/llfree-c
pajko 2y ago
ThreadX has pool allocators: https://github.com/eclipse-threadx/threadx/blob/master/common/src/tx_byte_allocate.c https://github.com/eclipse-threadx/threadx/blob/master/commo...
- kazinator 2y ago
  Everyone and his dog who has programmed C for a few decades has several as well. :)
- stefantalpalaru 2y ago
  [dead]
teo_zero 2y ago
What I find weird is that the chunk's size is fixed, while the caller must specify how many chunks a pool contains at pool creation. I would do exactly the dual: the chunk's size should be defined at pool creation, so that you can create multiple pools, each dedicated to one specific kind of object. (You need a third field in struct Pool, though.) Instead, the number of chunks per pool should not something the user needs to care about: if they knew in advance how many objects are required, they would simply allocate an array big enough! The library implementation should define a sensible number and stick to it. Similarly, I don't like exposing pool_expand(): too much burden on the user. Expansion should be automatically triggered by pool_alloc() whenever the current pool is exhausted. This would also allow a much simpler pool_new() that just initializes its pointers to NULL, leaving it to the first invocation of pool_alloc() to actually do the first allocation. This would avoid the duplication of code between pool_new() and pool_expand(). Another benefit of fixing the number of chunks is a possible simplification of ArrayStart: this could include a proper array instead of a pointer, avoiding a malloc(). Something like this: struct ArrayStart { struct ArrayStart *next; Chunk arr[CHUNKS_PER_ARRAY]; };
- 8dcc 2y ago
  > I would do exactly the dual: the chunk's size should be defined at pool creation, so that you can create multiple pools, each dedicated to one specific kind of object. This is supported in my 'libpool' project. I thought I mentioned it in the article, but now I am not so sure. https://github.com/8dcc/libpool/blob/main/src/libpool.h#L51 https://github.com/8dcc/libpool/blob/main/src/libpool.h#L51 > Similarly, I don't like exposing pool_expand(): too much burden on the user. Expansion should be automatically triggered by pool_alloc() whenever the current pool is exhausted. I feel like this shouldn't be too hard to do, but I actually did write a function for this in another project I am working on. https://github.com/8dcc/sl/blob/9ddd84d75ffc3b0ba1373bc13bc65b5ae5a73dee/src/expr_pool.c#L185-L191 https://github.com/8dcc/sl/blob/9ddd84d75ffc3b0ba1373bc13bc6... > This would also allow a much simpler pool_new() that just initializes its pointers to NULL, leaving it to the first invocation of pool_alloc() to actually do the first allocation. I didn't think of this, but I rather keep the two functions separate, specially for readability in the article.

307 points by 8dcc 2y ago

liontwist 2y ago

The pool struct Is two pointers, why are you allocating it with Malloc?

o11c 2y ago
Some people are allergic to `main() { Foo foo; foo_init(&foo); }` Admittedly, sometimes for good reason - it locks in the ABI.
- MathMonkeyMan 2y ago
  Is that why some structs have "char reserved[16]" data members? I think I saw this in NGINX, though that might have been to allow module compatibility between the open source offering and the paid version.
  - o11c 2y ago
    Yes, that slightly improves ABI flexibility, though the fact that callers can still access fields limits that. An alternative is to make the only member `char opaque[16]` (IIRC some locale-related thing in glibc does this, also I think libpng went through a transition of some sort related to this?), but calculating the size can be difficult outside of trivial cases since you can't use sizeof/offsetof.
- liontwist 2y ago
  ABI? Better make it an anonymous struct too. It’s a performance oriented custom memory allocator.
- kazinator 2y ago
  Mainly just the size and alignment. If you make the structure oversized, and with strict alignment, it can be future proofed. Old binary clients will provide a structure big enough and aligned enough for the new version. The dynamic constructor API can allocate the structure exactly sized without the padding.
unwind 2y ago
Next question: why are there two calls to `malloc()`, one for the Pool structure and one for the Chunks? It is trivial to co-allocate them which removes the risk of memory fragmentation and is just generally a good idea if you're chasing performance. The answer might be "for clarity/simplicity" which I guess is fine in an informative article, but it could at least be highlighted in the text which I didn't see.
- 8dcc 2y ago
  I will also take note of this, you are right.
- jdnxbdn 2y ago
  It is certainly not trivial and would add little to the topic
- kevin_thibedeau 2y ago
  He's targeting ANSI C, C89. Flexible array members are not supported officially until C99. 26 years later, it's time to stop clinging to outdated standards and crusty tooling. Even Linux had to read the room and adopt C11. A C11 implementation could go one step further and use _Alignas(max_align_t) to keep the pool array aligned with no manual effort. The double allocation does this implicitly.
  - liontwist 2y ago
    The pool needs to align every allocation anyway.
  - listeria 2y ago
    on the topic of alignment, the library (libpool) fails to align chunk_sz to allow storing a pointer when in the free_chunk list. This issue is sidestepped in TFA by using a union, which ensures appropiate alignment for all it's members, but in the library there's nothing which prevents me from asking for a chunk size of, say, 9 bytes, which would store pointers at misaligned addresses when creating the free-list.
lyu07282 2y ago
Couldn't this also just syscall mmap directly? I mean malloc itself is a memory allocator it feels a bit strange to use it in an allocator implementation, but perhaps I'm missing something.

keyle 2y ago

The parent article is quite interesting and slightly different being cpp [1]. There is also a post about writing a memory allocator [2]. [1]: http://dmitrysoshnikov.com/compilers/writing-a-pool-allocator/ http://dmitrysoshnikov.com/compilers/writing-a-pool-allocato... [2]: http://dmitrysoshnikov.com/compilers/writing-a-memory-allocator/ http://dmitrysoshnikov.com/compilers/writing-a-memory-alloca...

10000truths 2y ago

I recommend against using linked lists for bookkeeping the free blocks. It seems to be the data structure that every malloc/free implementation reaches for, and I don't know why - the slowness of pointer-chasing makes it terrible for almost any real-world use case. A balanced tree would be a much better idea, given that all the essential operations would take O(log n) time instead of O(n). Even if one insists on a linear search, a bitset is much more cache friendly than pointer-chasing and it can trivially benefit from SIMD optimizations.

ben-schaaf 2y ago
I don't think you understand how the allocator in the article works. Allocating and freeing are already O(1), creating and closing the allocator are necessarily O(n). There is no search being done here.
o11c 2y ago
For the `Chunk` list, this isn't one of the cases where linked lists are harmful. Each use only touches the top of the stack, never iterates. Also, linked lists are much easier to make thread-safe. For the `LinkedPtr` list, the bad case is only hit during the destruction of the pool, and then only if you allocate a lot of memory. And given the overhead of deallocation I'm not sure the array approach would measurably help. I don't see anywhere a binary tree search would be useful here, since there are no loops used for lookup (on allocation they're pushed in order, but when freed chunks are pushed in arbitrary order; this does mean no double-free protection).
- harrison_clarke 2y ago
  why would you need to iterate on destruction? you free the whole pool at once, since you allocate it all at once
DevelopingElk 2y ago
The reason linked lists are used is for large enough allocations, there is no overhead. You use the space the application isn't using. In addition, if all allocations are the same size it is O(1), you just look at the head of the list. More sophisticated strategies bucket allocations by size, this has fixed overhead. You can also use balanced trees for more memory efficiency, but this is slower. For small allocations (8 bytes) that are too small to contain pointers allocators will allocate a block and use bitsets.

sour-taste 2y ago

Some interesting things that would be interesting to add to this: - thread safety ( not too hard to add on top of your liked list) - variable sized allocations. Ideally something more akin to malloc. Could be done wastefully by rounding up to the nearest chunk size - (as mentioned in the article) variable chunk sizes - zeroing of memory before handing it back to users - double free detection or even better full asan support

8dcc 2y ago
I don't currently have much experience with thread safety, but it's something I should look into. Thank you.

kazinator 2y ago

If you write your own allocator in C, do yourself a favor and use the valgrind API inside it. Its use can be conditional so you can "compile it out". Or should I say it has to be, so you can build the code in an environment where there's no valgrind API.

gopalv 2y ago
+1 - this isn't even that hard, it is include a single header + annotate allocations/frees, with some redzones around the actual allocation to know when the user-code is writing into the pool pointer areas. https://developers.redhat.com/articles/2022/03/23/use-valgrind-memcheck-custom-memory-manager https://developers.redhat.com/articles/2022/03/23/use-valgri...
- deleted 2y ago
  [deleted]
- hooli_gan 2y ago
  https://en.wikipedia.org/wiki/Red_zone_(computing) https://en.wikipedia.org/wiki/Red_zone_(computing)
- dsp_person 2y ago
  oof love on this page how scrolling hijacks the back button
- swah 2y ago
  Thats with Claude, right?
  - gopalv 2y ago
    > with Claude The comment itself is AI generated or the code reference? Here's some of my old code https://github.com/php/pecl-caching-apc/blob/0dd2a69bab58822ba86a88445de06638a6a2456d/apc_pool.c#L221 https://github.com/php/pecl-caching-apc/blob/0dd2a69bab58822...
8dcc 2y ago

accelbred 2y ago

Note that using this will likely violate strict aliasing due to using the void pointer returned as one type, freeing it, and then getting that same chunk again and using it as another type. You'll probably want to compile with -fno-strict-aliasing to be safe. A good reference on strict aliasing: https://gist.github.com/shafik/848ae25ee209f698763cffee272a58f8 https://gist.github.com/shafik/848ae25ee209f698763cffee272a5...

leni536 2y ago
That's what allocators do. If C's object model doesn't allow users of the language to write their own allocators then that object model is broken. C++ relatively has fixes to allow allocators to work, it requires calls to std::launder.
- dwattttt 2y ago
  I understand the C standard hides such actions behind a wall of "this is the allocator", and expected the compiler authors to also be the allocator authors, allowing them to know when/how they can break such rules (in the context of their own compiler)
  - unwind 2y ago
    No, allocators are not magic (in that regard) in C. There is nothing out of the ordinary going on with an allocator, the parent comment is simply mistaken (as pointed out by another answer).
    - dwattttt 2y ago
      Ah, I see that it's because the char type never violates Strict Aliasing. I was wondering how you could define a type such as Chunk, yet hand out a pointer to it to a user who will cast it to some other type.
      - SleepyMyroslav 2y ago

8fingerlouie 2y ago

A long time ago, in a galaxy far far away, i wrote something similar for an embedded platform. I was implementing a WAP Browser at the time (yes, WAP, https://en.wikipedia.org/wiki/Wireless_Application_Protocol https://en.wikipedia.org/wiki/Wireless_Application_Protocol), and we needed dynamic memory allocation in an environment where everything was static due to realtime constraints. So i ended up with this : https://github.com/jinie/memmgr https://github.com/jinie/memmgr

openmarkand 2y ago

[flagged]

oguz-ismail 2y ago
> using GPL as the license for a library is kind of limiting That's the point of using GPL
matheusmoreira 2y ago
He should have used AGPLv3. Anyone who doesn't like it should contact him with a business proposal for a proprietary license.
andrewmcwatters 2y ago
Almost no one should be using the MIT or equivalent licenses anymore now that the industry has been overrun by commercial freeloaders. AGPL or GPLv2 and above.

guardian5x 2y ago

The Latin Modern font on this website does not look so good in Chrome, is it because of the font size, or is it just me? (Chrome)

johnisgood 2y ago
I was going to say this. Looks awful to me as well. It is the font-family.
dmonitor 2y ago
Sounds like a Windows issue based on other people in the thread. I'm on Firefox with the same issue. Removing Latin-modern from the CSS file made it much more readable for me.

9029 2y ago

Another (admittedly less portable) way to solve the resizing problem is to reserve a large virtual memory space using linux mmap with the PROT_NONE flag and then commit pages as needed using mprotect with PROT_READ|PROT_WRITE flags. I believe windows' VirtualAlloc/VirtualProtect also allows this

jeffbee 2y ago
You don't need to do anything with the flags. You can just mmap a huge virtual area and the pages will be realized whenever you first touch them.
- 9029 2y ago
  Today I learned, thanks

cb321 2y ago

One aspect people don't tend to mention (and TFA does not because it has "general purpose" as a scope) about doing your own allocation arenas is that because a "pointer" is just the name (really number) of an allocated region, this also affords flexibility in the width of those numbers aka "pointer size" that decides your "address" space. So, for example, if you are willing to limit yourself to 64 KiNodes of equal sized objects, a pool like https://github.com/c-blake/bst/blob/main/POOL.c https://github.com/c-blake/bst/blob/main/POOL.c can use an unsigned short 2-byte pointer. This small address space specialization can give a full 4x space overhead optimization over modern 64-bit pointers. You could even use 8x less with 1-byte pointers if 256 nodes is enough or use bit fields or equivalents for even more fine-grained address space size selection. Admittedly, linked structures are usually less interesting for very small address space sizes, but this is sometimes useful. People may complain about arbitrary limits that relate to this kind of optimization, but the linked part could be "small by design" without compromising overall scale { such as for structure within a B-tree node or other multi-level indexing setups }. In any event, I think it is useful to highlight pointer size arbitrariness to junior engineers. It is often learned once & immediately forgotten behind an onslaught of general purpose-ness (& pointer type systems/syntax). Relocation ideas also relate. E.g., if all the pointers are implicitly indices into a (small?) array, and all the code needs a "base address" of that array to get a VMem address, then you can relocate the whole bundle of objects pretty easily changing only the base address.

8dcc 2y ago
Yes, this is true. I didn't use that in the code because I thought it would make it less readable, though. I might mention it somewhere, thank you.
- cb321 2y ago
  In many prog.lang's, it absolutely makes things less readable. This is not an accident, but because the PL itself specifically tries to syntactically support pointer types (i.e. to literally aid readability). Most PLs do so only for general purpose VMem pointers with user-defined pointers being afterthoughts (at best). You probably need (at least!) operator overloading to get the same level of readability as "PL-native" pointers { though "readability" is a bit subjective and powerful PL features can be divisive; Scare "quotes" for interpretation hazard :-) }. Anyway, you probably knew all that & I don't mean to suggest otherwise, but it made sense to write since HN loves PL talk.

matheusmoreira 2y ago

This is really informative. I wonder if there is a better solution for the reallocation problem, one that preserves pointers.

kragen 2y ago
You can keep the raw pointers inside your manager object for a particular object type and only hand out some kind of handle that requires an indirection step, such as an array index.
- matheusmoreira 2y ago
  I've seen that design before. Base and offset easily allows relocations of data in memory. https://www.man7.org/linux/man-pages/man2/mremap.2.html https://www.man7.org/linux/man-pages/man2/mremap.2.html If the mapping is relocated, then absolute pointers into the old mapping location become invalid (offsets relative to the starting address of the mapping should be employed). I've always assumed that forcing an indirection causes a noticeable performance impact. I mean, everyone uses absolute pointers by default, right?
  - kragen 2y ago
    There are a lot of variations on it: - Unix file descriptors are small-integer array indices into, normally‚ arrays in kernel space. - Many Smalltalk implementations, especially on older machines, named objects in memory with small-integer indices into a global object table (typically shifted in some way to accommodate tagged SmallIntegers) which was implemented as an array of pointers to the real object locations. - Functions exported from DLLs on Windows can be identified by "ordinals" that index a table of all exported functions instead of by name. - PalmOS, Win16, and Pre-X MacOS identified allocations of memory from the operating system by "handles" which were, again, indices into a table of pointers, the master pointer block. To access the actual memory you would call HLock() (MacOS name) and index the table (yourself, on MacOS, or using the return value from the lock function on PalmOS or Win16) to get the physical address, which could change if the handle was unlocked. - Forth maintained an in-memory buffer cache of 1024-byte disk blocks, which it identified by ordinal number rather than, say, cylinder/head/sector tuples or inode+offset tuples. To get the memory address of block 53, you would say 53 block (Forth for "block(53)") and freely index into those 1024 bytes, which were guaranteed to remain resident until the next call to block or until you yielded the CPU with another I/O operation. If you modified the data there, you would call update to tell Forth the buffer was modified. If block 53 was not currently in memory, Forth would pause your task until it had loaded it, running other tasks meanwhile. If there was no free block buffer, Forth would free one up, by writing out a modified buffer to disk if necessary. This provided a sort of virtual memory in about 100 lines of code without requiring memory-mapping hardware. (The "BLOCK I/O" part of F83's KERNEL86.FS is 8 16-line screens long, but a fair bit of that is actually dealing with MS-DOS's file I/O functions.) - Because standard Pascal had no string type and no way to handle variable-length arrays of any kind, TeX uses indices into a string table as its string type. It inserts newly encountered strings in the string table. - Symbols in some Lisps. - Pretty much anything in any Fortran program. See http://www.the-adam.com/adam/rantrave/st02.pdf http://www.the-adam.com/adam/rantrave/st02.pdf on how to program Fortran in any language. How noticeable the performance impact is depends a lot on how often you have to traverse the extra level of indirection. (Doing a base+offset addition before each memory access could be a significant performance issue on things like a Commodore 64 or a TRS-80 but basically doesn't matter on 8086 or better hardware.)

kragen 2y ago

This is a very nice article! The diagrams in particular are very clear. (They seem to have been done in draw.io: https://github.com/8dcc/8dcc.github.io/blob/main/img/pool-allocator4.svg?short_path=a1a0364 https://github.com/8dcc/8dcc.github.io/blob/main/img/pool-al... which seems to be a pretty decent Apache-2.0 free software licensed diagram editor: https://github.com/jgraph/drawio/ https://github.com/jgraph/drawio/) I think it would be improved further if it began with the calling interface callers use to invoke the allocator, because it's easier to understand the implementation of some service such as pool allocation when you begin by knowing what service, exactly, is required. I began with the assumption that the author was describing an arena allocator under another name, rather than a fixed-size block allocator, both because the APR's influential arena allocator is called "apr_pool_t" and because one of the main headings in the table of contents (a greatly appreciated feature, like all the typography of the article) was "Closing the pool". It took me quite a while to figure out that I was mistaken. It's plausible that I only had this problem because I am an unusually stupid, ignorant, or pigheaded person (some would say all three), but, if not, many other people will have the same difficulty I had of taking several minutes to figure out what the topic of the article is. (I could have saved myself by clicking either of the first two links in the Introduction, but I didn't because I thought I already knew what it was.) The current top-voted comment on this thread is by someone who had the same reading comprehension problem I did, but never realized their erorr: https://news.ycombinator.com/item?id=42643951 https://news.ycombinator.com/item?id=42643951 and nobody had pointed out their mistaek until I did just now. So I think we can say with some confidence that many HN readers will have the same difficulty. I think that the article would also be improved by a few other small additions: - It says, "The pool allocator, however, is much faster than malloc", but doesn't provide any benchmarks or even an order of magnitude. - Probably when one benchmarks the implementation given, one will find that it is only slightly faster than jemalloc or even gnumalloc, because they both dispatch small allocations to a fixed-block allocator similar to this one, and the dispatch isn't very expensive. This can be fixed by inlining the allocation fast path and the deallocation function, which will then compile down to a few instructions each. A simple demonstration of how to do this is in my arena allocator kmregion in http://canonical.org/~kragen/sw/dev3/kmregion.h http://canonical.org/~kragen/sw/dev3/kmregion.h and http://canonical.org/~kragen/sw/dev3/kmregion.c http://canonical.org/~kragen/sw/dev3/kmregion.c (GPLv3+). The current implementation of 8dcc libpool is guaranteed to be unable to do this unless you're using link-time optimization or a so-called "unity" or "amalgamation" build process. - It's worth distinguishing between average-case performance (in which this allocator is slightly better than malloc) and worst-case performance (in which case malloc, generally speaking, isn't even in the running). - It may be worth mentioning that often such pool allocators are used in conjunction with initializing the objects in the pool to a valid state when the pool is created; that way you don't have to reinitialize objects to a valid state every time you deallocate and reallocate them, which is usually more work than malloc does to find the right free list. This does require not overwriting the user data with your freelist pointer, so it's a space/time tradeoff. - Maybe you should mention alignment, especially now that even on amd64 GCC has taken to using new instructions that require alignment. Even as it is, though, it's highly educational, visually pleasant, and very understandable (once I got over my initial misconception of having a totally wrong idea of what the article was about).

jll29 2y ago

This code is very beautifully written, thanks for sharing. However, you should consult the book "C: Interfaces and Implementations" by Dave Hanson, which has a library called "Arena" that is very similar to your "Pool"s, and it shows a few more tricks to make the code safer and easier to read (Chapters 5+6, 6 in particular). D. Hanson's book (written in the 'literary programming' style invented by Donal Knuth) also demonstrates having debugging and production implementations for the same C API to catch memory errors, and his book is from 1997: > Copyright © 1997 by David R. Hanson (He used to be a SE professor I Princeton before getting hired by Microsoft, I believe.)

8dcc 2y ago
Thank you so much! I will definitely check it out. I also planned on writing an article about arena allocators soon.
kragen 2y ago
I think you mean "literate programming". The arena allocator in Hanson's chapter 6 is an arena allocator, not a "pool allocator" in the sense that 8dcc means, which is to say, a constant-time fixed-size-block allocator. It seems that you had the same reading comprehension problem that I did. The difference is that Hanson's arena allocator can make allocations of any size (his Arena_alloc takes an nbytes argument) and cannot deallocate individual allocations, only the entire arena (his Arena_free takes only an arena pointer as a parameter). A fixed-size-block allocator like the one we are discussing here can only make allocations of a fixed size, but can recycle them individually, not only all at once. (If Hanson's name sounds familiar, it might be because you've read the lcc book.) It may be worth noting that Donald Knuth also invented the font used in 8dcc's article.
- actionfromafar 2y ago
  Honestly, "literary programming" does better explain how Knuth writes code.
  - kragen 2y ago

exDM69 2y ago

Here's another interesting O(1) memory allocator but with arbitrary sized allocations and low fragmentation. Negative side is relatively high memory overhead (a few dozen bytes per allocation). This kind of allocator is often used to suballocate GPU memory in game and graphics applications. I'm using a variant of this algorithm with added support for shrinkable and aligned allocations and flexible bin sizing. You can also extend this idea to two dimensions to create texture atlases, which is possible in O(1) for power of two sized allocations. Original: https://github.com/sebbbi/OffsetAllocator https://github.com/sebbbi/OffsetAllocator Rust port: https://crates.io/crates/offset-allocator https://crates.io/crates/offset-allocator

2rsf 2y ago

This bring old memories back, I implemented something similar on a motorola 68360 ages ago. Since the size of the buffer I used was not huge I skipped the pointers and simply enumerated each chunk, it was remarkably efficient and stable.

codr7 2y ago

I usually default to slab allocators if I have to write my own: https://github.com/codr7/libcbs#slab-allocation https://github.com/codr7/libcbs#slab-allocation

drysine 2y ago

Also "Arena allocator tips and tricks (nullprogram.com)" [0] [0] https://news.ycombinator.com/item?id=37670740 https://news.ycombinator.com/item?id=37670740

sylware 2y ago

It all depends on the load profile using the allocator. You never know, that said you cannot beat, in theory, a semantically specialized allocator for a specific load... in other words, the right way(TM). This means applications should bundle their own allocators for the various load types they have. The "generic" allocator is sort of an heresy for the lazy, short termists or those who are in hurry. Don't worry I still use such generic allocator, sometimes, but often I do mmap myself the memory and deal directly with it.

astrange 2y ago
The system allocator is the one that comes with all the system's memory debugging tools and security (or lack of it), so you'd better not mind losing those if you want to ditch it.

voctor 2y ago

There is a small series of posts on the BitSquid blog about memory allocation which is worth reading! http://bitsquid.blogspot.com/2015/08/allocation-adventures-3-buddy-allocator.html http://bitsquid.blogspot.com/2015/08/allocation-adventures-3...

8dcc 2y ago

Hello, I am the author. Thank you all for the instructive comments, I made some changes to the article since I first posted it: - Added a link to this HN post. - Renamed some variables and types in the code for readability. - Mention (in a footnote) that we could allocate the 'Pool' structure and the chunk arrays with a single call, or even return the 'Pool' on the stack. Suggested by 'liontwist' and 'unwind'. - Mention (in a footnote) that we don't always need to store the full address when building the linked list of free chunks. Suggested by 'cb321'. - Added valgrind support (also to my 'libpool' project). Suggested by 'kazinator'.

cb321 2y ago
FWIW, while it is true that a smaller pointer lets you have smaller minimum fixed size objects in your pool, as your new footnote suggests, the space concern I was mostly alluding to in [1] is all the references in your client code { such as the BST code I linked to where each binary search tree (BST) node has 2 pointers (or 3 if they have parent pointers to give BST nodes "doubly linked list-like autonomy") }. This can really add up. For example, like 20 years ago, I did a `print sizeof` in gdb for some g++ STL map node with a data payload of like 4 bytes and it was some obscene size approximately >= 1 order of magnitude bigger than necessary (like 80 bytes instead of, say 8 with 2Byte ptrs). While main memory is cheap, CPU cache memory is not and for "linky" structures, it often pays to be more cache-friendly. It's pretty easy to imagine a 10X smaller thing fitting into an L2 CPU cache where the larger thing would not even fit in L3, netting you a big latency boost (though the more root-ward levels of the tree likely always stay in caches in a hot loop). EDIT: Anyway, you don't have to believe me. Others did an x32 ABI for x86_64 mostly to have "merely 2X" smaller pointers: https://en.wikipedia.org/wiki/X32_ABI https://en.wikipedia.org/wiki/X32_ABI [1] https://news.ycombinator.com/item?id=42643410 https://news.ycombinator.com/item?id=42643410
veltas 2y ago
Also the font isn't incredibly easy to read on Windows. I'm assuming Georgia was selected? Which has been on Windows for years but renders so badly it looks like the font color isn't black, even though I think it is black? This isn't really your fault but I would have stuck to Times New Roman for Windows' sake.

jhallenworld 2y ago

A sometimes useful thing is to treat the pool as a stack and provide a call to free all recently allocated items up to a certain index. So you make a bunch of deep subroutine calls that use the pool allocator, and then on return free them all. It's like a secondary automatic storage class. Also sometimes useful to provide another call to promote an automatic item to a more permanent one so that it is excluded from being freed like this.

harrison_clarke 2y ago

you can avoid resizing and moving the pools if you allocate massive pools up front. most OSs let you overcommit memory, and most programs using memory pools only have a handful of them (on windows, you'd need to handle this with VirtualAlloc. osx and linux let you overcommit with malloc, and handle it with a copy-on-write page fault handler)

lelandbatey 2y ago

It seems like almost all of the complexity of this allocator comes from having to manage the fact that it's being implemented on top of the system allocator. I thought the whole point of using a custom allocator was to avoid the system allocator for exactly the problems they mention e.g. calling the system-provided realloc() might move your stuff around, having to track separate pool starts so you can call the system-provided free() on them, etc. Like, yeah you have to do that, but I thought the whole point of writing a custom allocator was to not use the system allocator beyond statically allocating a huge block of memory upfront and then managing that yourself, is it not?

8dcc 2y ago
> I thought the whole point of writing a custom allocator was to not use the system allocator beyond statically allocating a huge block of memory upfront and then managing that yourself, is it not? Yes, that's what the article is basically about. The other problems you mention only happen when trying to expand an existing pool, which might not be necessary for some people.

alecco 2y ago

(related) LLFree Paper: LLFree: Scalable and Optionally-Persistent Page-Frame Allocation https://www.usenix.org/system/files/atc23-wrenger.pdf https://www.usenix.org/system/files/atc23-wrenger.pdf Video presentation: https://www.youtube.com/watch?v=yvd3D5VOHc8 https://www.youtube.com/watch?v=yvd3D5VOHc8 Implementation and benchmarks are well documented at the repos: Rust repo https://github.com/luhsra/llfree-rs https://github.com/luhsra/llfree-rs C repo https://github.com/luhsra/llfree-c https://github.com/luhsra/llfree-c

pajko 2y ago

ThreadX has pool allocators: https://github.com/eclipse-threadx/threadx/blob/master/common/src/tx_byte_allocate.c https://github.com/eclipse-threadx/threadx/blob/master/commo...

kazinator 2y ago
Everyone and his dog who has programmed C for a few decades has several as well. :)
stefantalpalaru 2y ago
[dead]

teo_zero 2y ago

What I find weird is that the chunk's size is fixed, while the caller must specify how many chunks a pool contains at pool creation. I would do exactly the dual: the chunk's size should be defined at pool creation, so that you can create multiple pools, each dedicated to one specific kind of object. (You need a third field in struct Pool, though.) Instead, the number of chunks per pool should not something the user needs to care about: if they knew in advance how many objects are required, they would simply allocate an array big enough! The library implementation should define a sensible number and stick to it. Similarly, I don't like exposing pool_expand(): too much burden on the user. Expansion should be automatically triggered by pool_alloc() whenever the current pool is exhausted. This would also allow a much simpler pool_new() that just initializes its pointers to NULL, leaving it to the first invocation of pool_alloc() to actually do the first allocation. This would avoid the duplication of code between pool_new() and pool_expand(). Another benefit of fixing the number of chunks is a possible simplification of ArrayStart: this could include a proper array instead of a pointer, avoiding a malloc(). Something like this: struct ArrayStart { struct ArrayStart *next; Chunk arr[CHUNKS_PER_ARRAY]; };

8dcc 2y ago
> I would do exactly the dual: the chunk's size should be defined at pool creation, so that you can create multiple pools, each dedicated to one specific kind of object. This is supported in my 'libpool' project. I thought I mentioned it in the article, but now I am not so sure. https://github.com/8dcc/libpool/blob/main/src/libpool.h#L51 https://github.com/8dcc/libpool/blob/main/src/libpool.h#L51 > Similarly, I don't like exposing pool_expand(): too much burden on the user. Expansion should be automatically triggered by pool_alloc() whenever the current pool is exhausted. I feel like this shouldn't be too hard to do, but I actually did write a function for this in another project I am working on. https://github.com/8dcc/sl/blob/9ddd84d75ffc3b0ba1373bc13bc65b5ae5a73dee/src/expr_pool.c#L185-L191 https://github.com/8dcc/sl/blob/9ddd84d75ffc3b0ba1373bc13bc6... > This would also allow a much simpler pool_new() that just initializes its pointers to NULL, leaving it to the first invocation of pool_alloc() to actually do the first allocation. I didn't think of this, but I rather keep the two functions separate, specially for readability in the article.