5 ms·
It's not a "simple" allocator. It's an overly simplistic and largely unoptimized one. E.g. try and make it work well with 2 threads. Now try and make it work w
by huhtenberg 9y ago
It's not a "simple" allocator. It's an overly simplistic and largely unoptimized one.
E.g. try and make it work well with 2 threads. Now try and make it work well with 2 threads, one - allocating, another - freeing, etc.
Writing a memory allocator is a _fantastic_ exercise in data structures and optimization. It's also an easy one, so making a reasonably fast allocator from scratch is not that hard, but in the end it's much more fun to write one than to look at someone else's results. This is also what makes these toy allocators to be a dime a dozen.
- senatorobama 9y agoIs there an allocator that uses lockless programming?
- bonzini 9y agoYou can do mostly lockless. The fast path is what matters the most, the difficult part is not wasting too much memory for the sake of not hitting the slow path.
- masklinn 9y agoIIRC jemalloc has per-thread pools & caches which I assume can be accessed locklessly. I don't think the entire thing is lossless, and neither is tcmalloc. And as far as I know these are the only significantly thread-aware allocators (or at least production-ready ones).
- bonzini 9y agoglibc has also grown a good thread-aware allocator, though that is more recent than tcmalloc or jemalloc.
- qznc 9y agoYou may find this interesting: https://concurrencyfreaks.blogspot.de/2017/08/why-is-memory-reclamation-so-important.html https://concurrencyfreaks.blogspot.de/2017/08/why-is-memory-...
- valarauca1 9y agoLow contention lock-less structures are slower then low contention locks. You end up doing more work and get less in return. JEmalloc does locking on multiple pools, failing one it tries another. So there is a high probability it won't preform many atomic CAS ops.
- fao_ 9y agoUnlike the one in 7th edition unix? https://news.ycombinator.com/item?id=15269040 https://news.ycombinator.com/item?id=15269040
- huhtenberg 9y agoAre you implying that this ^ 40-year old piece of code is somehow suitable for modern use? A "pointer-per-block" alone will cost you 8 bytes of overhead on 64-bit machines. Both this and the 'while' loop in 'alloc' can be optimized away with rudimentary slab allocation. There's no threading support, etc.
- fao_ 9y agoYou stated that the example was "overly simplistic and largely optimized". I made no claim as to what system this code is optimized for, I was simply stating that it is possible to have an allocater the same size that is (or was) suitable for production use.
- saurik 9y agoI have had an absolute hell of a time finding a memory allocator that will work in a fundamentally single-threaded environment (where I need compliant C only with no library functions or processor features that offer anything for threads); do you have a suggestion? Everyone seems to care a lot about how to "make it work well with 2 threads", at which point the very premise tends to make the allocator unusable for me :(.
- pm215 9y agoIf you have no threads at all, I would naively think it should be fairly simple to just stub out the locking and similar calls. Have you looked at dlmalloc, which lets you build with USE_LOCKS=0 to turn off the threadsafety?
- saurik 9y agoThank you so much! I had stared at a few malloc implementations (both standalone and from a few libcs), and I had finally gotten to the point (after seeing how thouroughly integrated the threading often is, with not just atomic variables and locks but sometimes thread local storage) that I had largely given up on any implementation that even mentioned multithreading as a feature, but I clearly should have kept going: I just managed to get dlmalloc compiled using nothing but mmap, munmap, abort, memcpy, memset, sysconf (which should be fine), and time (which also should be fine). That just did not seem to be plausible with TCMalloc or jemalloc. Again: thanks so much!!
- justincormack 9y agoNetBSD and Musl libc are good sources for simpler implementations. From memory the NetBSD jemalloc is an early simple single file version that is pretty easy to adapt.
- apenwarr 9y agoLook up "buddy system allocator." The algorithm is super fast and easy to understand and implement. It was also the one used in the very first Linux kernels (probably for those reasons).
- jacquesm 9y agoI agree with all of your comment except for the bit where you write that it is also an easy one. Writing a memory allocator without obvious (and not so obvious) bugs is really hard.
- huhtenberg 9y agoSure. I meant that writing a reasonably fast non-reentrant allocator is easy. Getting it to work well in a threaded environment is where all the worms are.
- fish_fan 9y ago> Writing a memory allocator without obvious (and not so obvious) bugs is really hard. Actually, I disagree. Putting aside the implication you had that writing bugless software is possible, I think that memory allocation is straightforward. The interface is simple and the gotchas haven't changed since memory protection standardized. Writing a correct allocator amounts to a checklist of allocation and free behavior, plus some extra stuff like "how hard/probable is it to detect use after free" &c. Correctness, property calculation itself, and proving (theoretical) performance of your algorithm is not so hard. Now writing a general purpose one that doesn't trigger catastrophic performance against one app of many is really hard.
- jacquesm 9y agoI'm going to have to disagree with you. Your average programmer isn't going to be able to write a linked list implementation that is correct, let alone a whole allocator and free mechanism. I've seen enough code by now to be strongly convinced of this and it will take something fairly momentous to get me convinced of the opposite.
- fish_fan 9y agoWell, that seems to be more of a problem with C familiarity than memory allocation. If you can write correct data structures in C, you have rudimentary knowledge of linkers and mprotect (or whatever is analagous on Windows), you'll be fine.