9 ms·

How to allocate memory

156 points by ksherlock 10y ago

obi1kenobi 10y ago
If you'd like to learn more, here's an MIT research paper on fast memory allocation that has some really clever ideas: http://supertech.csail.mit.edu/papers/Kuszmaul15.pdf http://supertech.csail.mit.edu/papers/Kuszmaul15.pdf Abstract: SuperMalloc is an implementation of malloc(3) originally designed for X86 Hardware Transactional Memory (HTM). It turns out that the same design decisions also make it fast even without HTM. For the malloc-test benchmark, which is one of the most difficult workloads for an allocator, with one thread SuperMalloc is about 2.1 times faster than the best of DLmalloc, JEmalloc, Hoard, and TBBmalloc; with 8 threads and HTM, SuperMalloc is 2.75 times faster; and on 32 threads without HTM SuperMalloc is 3.4 times faster. SuperMalloc generally compares favorably with the other allocators on speed, scalability, speed variance, memory footprint, and code size. SuperMalloc achieves these performance advantages using less than half as much code as the alternatives. SuperMalloc exploits the fact that although physical memory is always precious, virtual address space on a 64-bit machine is relatively cheap. It allocates 2 MiB chunks which contain objects all the same size. To translate chunk numbers to chunk metadata, SuperMalloc uses a simple array (most of which is uncommitted to physical memory). SuperMalloc takes care to avoid associativity conflicts in the cache: most of the size classes are a prime number of cache lines, and nonaligned huge accesses are randomly aligned within a page. Objects are allocated from the fullest non-full page in the appropriate size class. For each size class, SuperMalloc employs a 10-object per-thread cache, a per-CPU cache that holds about a level-2-cache worth of objects per size class, and a global cache that is organized to allow the movement of many objects between a per-CPU cache and the global cache using O(1) instructions. SuperMalloc prefetches everything it can before starting a critical section, which makes the critical sections run fast, and for HTM improves the odds that the transaction will commit.
- rayiner 10y ago
  The SuperMalloc paper has some really interesting ideas about how to manage metadata. When you do a free(), you need to know the size of the underlying allocation. You also probably need to get access to some metadata relating to that allocation. Ideally, you want to even be a bit robust against someone freeing something that isn't a pointer to the beginning of a heap object. Jemalloc uses a radix tree to map from addresses to the headers of the 1-2MB "chunks" it uses as the top level of allocation. SuperMalloc allocates into 2MB chunks, but such that each chunk has objects of the same size. It then uses an array with one double word per 1MB chunk in the address space, which holds the size of the objects in each chunk. That also allows you to quickly find the metadata, which is stored at the beginning of each chunk. The array can get big--512MB for an array covering a 48-bit address space with 2MB chunks, but it's space and the virtual memory system won't map that to real memory until each page is accessed.
- scott_s 10y ago
  HN discussion on the SuperMalloc paper: https://news.ycombinator.com/item?id=10770781 https://news.ycombinator.com/item?id=10770781
- eatbitseveryday 10y ago
  While it has some new material, it's also not very well-written, and some of the benchmarks could be argued as being unrealistic. For example, Brad should have also included results using applications such as Redis (which by default uses jemalloc), or MongoDB, or many others. In many other scenarios not detailed in the paper, the allocator can use much more memory compared to tcmalloc. The "Vyukov" benchmark is an invented (and I would argue, contrived) scenario that Vyukov him or herself thought of to cause memory bloat in Intel's TBB just by examining the code. Whether or not it actually occurs in a real application is debatable. If you may have noticed, nowhere in the paper is tcmalloc mentioned :) It is still a viable alternative today. There are many other papers I would recommend in addition to this reading, e.g., "Dynamic Storage Allocation A Survey and Critical Review" Wilson et al. despite it being quite old. This might get me down votes, but it is wise to remember that just because work has the MIT stamp on it, doesn't mean it's always the most top-quality.
  - scott_s 10y ago
    The only limitation of "Dynamic Storage Allocation A Survey and Critical Review" is that it does not include a discussion on multithreaded allocator design - because the paper predates when people really started caring. I'm unaware of a survey paper which covers that aspect of memory allocation. (By the way: yours is a good comment! There's no need to mention you may get downvotes. We ask people not to do that, as it can tend to have a "I dare you" effect: https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html)
    - eatbitseveryday 10y ago
      > There's no need to mention you may get downvotes. We ask people not to do that, as it can tend to have a "I dare you" effect: https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html Oops. Sorry, I will be careful next time. Thanks for pointing that out. > does not include a discussion on multithreaded allocator design This is very true. tcmalloc seems to have been the earliest design with thread-local pools. jemalloc didn't originally have this design[1], and over time many allocators just adopted it, including SuperMalloc and others. [1] https://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919/ https://www.facebook.com/notes/facebook-engineering/scalable... (search for tcmalloc)
- geocar 10y ago
  I don't know how fast SuperMalloc is for other people, but in my experience it's not as fast as some other mallocs() (like Hoard or tcmalloc) and, in the end, it's still just another malloc(). Giving up the malloc() interface allows a very simple page-long allocator to outperform every malloc() I've ever tried (including SuperMalloc), and it would truly surprise me to learn there was some exotic memory technique (HTM, caching, etc) that could beat me.
  - ciniglio 10y ago
    Can you elaborate on what you mean by "Giving up the malloc() interface"?
    - geocar 10y ago
      malloc(sizeof(foo)) is slower than alloc_foo() because the latter can simply be a pointer increment, but there is no way to tell the malloc() interface that you're going to be doing nothing but allocating foo for a while. malloc() can guess this with heuristics, but a good malloc() needs to perform well for a wide variety of use cases: Surely you can appreciate that balance has a cost that the specialised allocator simply doesn't have to pay.
    - scott_s 10y ago
      The API for malloc is very simple: void* malloc(size_t len); void free(void* ptr); Basically, ask for an amount of memory, and give back a pointer to memory. But it does not allow you communicate anything but the amount on an allocation, and you can only give a memory pointer on freeing. If, for example, malloc had an interface like: void* malloc(size_t len, duration_t dur); enum duration_t { SHORT, MEDIUM, LONG}; One can imagine you could optimize based on the given hint. Once you open up one kind of hint, you can imagine many other kinds of things users could communicate explicitly to the memory allocator about the allocation and access patterns of their data. All implementations of free also need to find the related metadata for the given pointer. We could also imagine an interface for free which required the user to maintain that, but could perhaps speed things up: void free(void* ptr, meta_t d); Or, we could also imagine communicating how important it is to free this memory: void free(void* ptr, immediacy_t im); enum immediacy_t { IMMEDIATE, DELAYABLE }; In the latter case, maybe the memory allocator could put off doing delayable requests, and do them in a batch later. (Making it a bit more like garbage collection.) I'm not sure any of these ideas would help, but the point is that because of the limited interface, we really can't explore them. We can, but then convincing the rest of the world to change such a basic building block of C code is quite hard.
- gbrown_ 10y ago
  On the subject of papers, for those who have not read them Jeff Bonwick's work on the Solaris slab allocator is well worth reading. https://www.usenix.org/legacy/publications/library/proceedings/bos94/full_papers/bonwick.a https://www.usenix.org/legacy/publications/library/proceedin... https://www.usenix.org/legacy/event/usenix01/full_papers/bonwick/bonwick_html/index.html https://www.usenix.org/legacy/event/usenix01/full_papers/bon... Pretty much every OS kernel has adopted the techniques outlined in these papers.
  - eatbitseveryday 10y ago
    These ideas are also excellent. While slab allocators can be very fast and space-efficient, they are meant to be used in scenarios where you know in advance what object sizes are, as each slab cache only allocates one kind of object. The kernel is a great use case, because you know which structs will be frequently allocated/destroyed, thus create a slab cache for just that one data structure (and others for other structs). And the kernel itself does not change frequently, nor does it allocate objects of sizes imposed by user-space (like a file system or key-value store would have to). Memcached employs (-ed ?) its own allocator that is almost analogous to a slab allocator. It creates each cache not from understanding specific object sizes (since it cannot - it is a key-value store), but from a range of sizes incremented by some runtime constant. This can lead to really severe memory bloat in some instances. Memory allocators are not easy. Even "general-purpose" allocators are not truly meant for general-purpose allocation; the DSA paper mentioned above states (page 6 top left): > It has been proven that for any possible allocation algorithm, there will always be the possibility that some application program will allocate and deallocate blocks in some fashion that defeats the allocator's strategy, and forces it into severe fragmentation
- scottlamb 10y ago
  > SuperMalloc exploits the fact that although physical memory is always precious, virtual address space on a 64-bit machine is relatively cheap. It allocates 2 MiB chunks which contain objects all the same size. Hmm, this must not interact well with huge pages: either all those (1 huge page-sized) chunks actually take up physical memory or you're stuck with 4 KiB pages. Transparent huge pages on Linux are a noticeable performance difference in practice. In one of my applications, a coworker discovered that dTLB misses were a significant source of slowness. He pointed out that we had a lot of "holes" in our memory allocation caused by the malloc implementation calling madvise on 4 KiB pages when they were empty, thus preventing them from being coalesced into a 2 MiB huge page (or causing them to be migrate back to small pages). Setting a commandline flag to prevent this decreased CPU usage by 7%.
- anarazel 10y ago
  > SuperMalloc achieves these performance advantages using less than half as much code as the alternatives. SuperMalloc exploits the fact that although physical memory is always precious, virtual address space on a 64-bit machine is relatively cheap. On the other hand that can considerably increase the size of the page table, and the cost and frequency of TLB misses. So I'm not sure this all a meaningful comparison.
mallaco 10y ago
> One major limitation of malloc (and even the best implementations like jemalloc and dlmalloc) is that they try to use a single allocator for each data structure. This is a mistake: A huge performance gain can be had by using a separate allocator for each of your data structures — or rather, for each of your data usage patterns. I stopped reading the article at this point. This statement has been disproven repeatedly over the years with Hoard and jemalloc. It is counter-intuitive but the data backs it up. Custom per-data-structure allocators can fragment the global memory arena and cause more CPU cache misses as result of the extra code involved. The latest/greatest malloc/free implementations use a myriad of optimizations to achieve speed improvements that a custom allocator implementation would rarely use. It's not an accident that jemalloc is so widely used in major applications - it works extremely well. https://github.com/jemalloc/jemalloc/wiki/History https://github.com/jemalloc/jemalloc/wiki/History https://github.com/jemalloc/jemalloc/wiki/Adoption https://github.com/jemalloc/jemalloc/wiki/Adoption
- gens 10y ago
  How about fragmentation ? AFAIK jemalloc is horrible when it comes to memory usage.
  - mallaco 10y ago
    My use of jemalloc in multithreaded servers shows the opposite to be true. Memory use is a little higher than the single mutex dlmalloc, but you'd expect this with a modern high performance thread aware malloc implementation. You think MariaDB would choose jemalloc if it wasn't efficient in memory use?
    - biocomputation 10y ago
      >> You think MariaDB would choose jemalloc if it wasn't efficient in memory use? I don't think this is a smart way of choosing an allocator.
  - pcwalton 10y ago
    What makes you say that? jemalloc's fragmentation is very low [1]. [1]: https://blog.pavlov.net/2007/12/04/vlad-and-analysis-of-dtrace-was-used/ https://blog.pavlov.net/2007/12/04/vlad-and-analysis-of-dtra...
FroshKiller 10y ago
I don't mean to be spammy about this, but I feel like I should repeat it. If you like this kind of content, consider joining the SDF. It's a free public access computing community with lots of artists, hackers, and grognards of all stripes. Your support is appreciated: https://sdf.org/ https://sdf.org/
_RPM 10y ago
sizeof returns size_t, not sure why he's using `long long`, but to be precise it isn't a function, so it doesn't "return" anything. I guess it "yields" size_t.
colanderman 10y ago
Not to be a downer, but this is poor and outdated C programming style. Don't use sbrk(2) unless you're completely reimplementing the standard library. Don't use alloca(3) unless you want weird headaches. Just use dynamically-sized arrays, which have been present in C for nearly two decades. They are block-scoped and easier to reason about. None of the magic numbers are explained. `(p->si_addr + (16LL<<22)) & ~4095`, where do those come from? I'm guessing 4095 is the page size less one, but DON'T hardcode that! Don't assign to lvalues in conditionals! (e.g. `while(j<31 && !(h=free_table[j]))`) It's hard to read and bug-prone. Don't use `&h[1]` to refer to the space after a structure. I'm pretty sure that's undefined behavior, and it often gives the wrong alignment for whatever you want to put after h. Rather, add a final element to the structure of flexible array type (say `int data[]` if you're storing ints after the structure). That is guaranteed to have the semantics you're looking for. Here's my advice: 1) Just use malloc(3). It's already fast and tuned to many allocation scenarios (including all four in this article!), and your application will continue to reap whatever performance improvements its maintainers make. Use aligned_alloc(3) if you need pages. 2) When working in the embedded world, it's often preferable to preallocate pools as large as your app will ever need for each kind of object you have collections of, and pin them to RAM (not necessarily for performance, but so you know you have the space). If you do so, you can reference the objects by index rather than pointer. It's much faster and more space-efficient, especially on 64-bit architectures. 3) Don't be afraid to realloc(3) to grow arrays. It incurs no asymptotic penalty. 4) Pay attention to data layout, to make sure that commonly-accessed stuff is not interspersed with rarely-accessed stuff. E.g. separate indexes from data where possible, if you tend to traverse the index rather than the data. (Caveat: all my comments above apply to glibc. YMWV on other systems.)
- akira2501 10y ago
  > Don't use `&h[1]` to refer to the space after a structure. I'm pretty sure that's undefined behavior Not defending the code, but it isn't undefined. Pointers to "one past the last element of an array" are a special case and have specific/defined behavior in the standard.
  - colanderman 10y ago

156 points by ksherlock 10y ago

If you'd like to learn more, here's an MIT research paper on fast memory allocation that has some really clever ideas: http://supertech.csail.mit.edu/papers/Kuszmaul15.pdf http://supertech.csail.mit.edu/papers/Kuszmaul15.pdf Abstract: SuperMalloc is an implementation of malloc(3) originally designed for X86 Hardware Transactional Memory (HTM). It turns out that the same design decisions also make it fast even without HTM. For the malloc-test benchmark, which is one of the most difficult workloads for an allocator, with one thread SuperMalloc is about 2.1 times faster than the best of DLmalloc, JEmalloc, Hoard, and TBBmalloc; with 8 threads and HTM, SuperMalloc is 2.75 times faster; and on 32 threads without HTM SuperMalloc is 3.4 times faster. SuperMalloc generally compares favorably with the other allocators on speed, scalability, speed variance, memory footprint, and code size. SuperMalloc achieves these performance advantages using less than half as much code as the alternatives. SuperMalloc exploits the fact that although physical memory is always precious, virtual address space on a 64-bit machine is relatively cheap. It allocates 2 MiB chunks which contain objects all the same size. To translate chunk numbers to chunk metadata, SuperMalloc uses a simple array (most of which is uncommitted to physical memory). SuperMalloc takes care to avoid associativity conflicts in the cache: most of the size classes are a prime number of cache lines, and nonaligned huge accesses are randomly aligned within a page. Objects are allocated from the fullest non-full page in the appropriate size class. For each size class, SuperMalloc employs a 10-object per-thread cache, a per-CPU cache that holds about a level-2-cache worth of objects per size class, and a global cache that is organized to allow the movement of many objects between a per-CPU cache and the global cache using O(1) instructions. SuperMalloc prefetches everything it can before starting a critical section, which makes the critical sections run fast, and for HTM improves the odds that the transaction will commit.

rayiner 10y ago
The SuperMalloc paper has some really interesting ideas about how to manage metadata. When you do a free(), you need to know the size of the underlying allocation. You also probably need to get access to some metadata relating to that allocation. Ideally, you want to even be a bit robust against someone freeing something that isn't a pointer to the beginning of a heap object. Jemalloc uses a radix tree to map from addresses to the headers of the 1-2MB "chunks" it uses as the top level of allocation. SuperMalloc allocates into 2MB chunks, but such that each chunk has objects of the same size. It then uses an array with one double word per 1MB chunk in the address space, which holds the size of the objects in each chunk. That also allows you to quickly find the metadata, which is stored at the beginning of each chunk. The array can get big--512MB for an array covering a 48-bit address space with 2MB chunks, but it's space and the virtual memory system won't map that to real memory until each page is accessed.
scott_s 10y ago
HN discussion on the SuperMalloc paper: https://news.ycombinator.com/item?id=10770781 https://news.ycombinator.com/item?id=10770781
eatbitseveryday 10y ago
While it has some new material, it's also not very well-written, and some of the benchmarks could be argued as being unrealistic. For example, Brad should have also included results using applications such as Redis (which by default uses jemalloc), or MongoDB, or many others. In many other scenarios not detailed in the paper, the allocator can use much more memory compared to tcmalloc. The "Vyukov" benchmark is an invented (and I would argue, contrived) scenario that Vyukov him or herself thought of to cause memory bloat in Intel's TBB just by examining the code. Whether or not it actually occurs in a real application is debatable. If you may have noticed, nowhere in the paper is tcmalloc mentioned :) It is still a viable alternative today. There are many other papers I would recommend in addition to this reading, e.g., "Dynamic Storage Allocation A Survey and Critical Review" Wilson et al. despite it being quite old. This might get me down votes, but it is wise to remember that just because work has the MIT stamp on it, doesn't mean it's always the most top-quality.
- scott_s 10y ago
  The only limitation of "Dynamic Storage Allocation A Survey and Critical Review" is that it does not include a discussion on multithreaded allocator design - because the paper predates when people really started caring. I'm unaware of a survey paper which covers that aspect of memory allocation. (By the way: yours is a good comment! There's no need to mention you may get downvotes. We ask people not to do that, as it can tend to have a "I dare you" effect: https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html)
  - eatbitseveryday 10y ago
    > There's no need to mention you may get downvotes. We ask people not to do that, as it can tend to have a "I dare you" effect: https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html Oops. Sorry, I will be careful next time. Thanks for pointing that out. > does not include a discussion on multithreaded allocator design This is very true. tcmalloc seems to have been the earliest design with thread-local pools. jemalloc didn't originally have this design[1], and over time many allocators just adopted it, including SuperMalloc and others. [1] https://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919/ https://www.facebook.com/notes/facebook-engineering/scalable... (search for tcmalloc)
geocar 10y ago
I don't know how fast SuperMalloc is for other people, but in my experience it's not as fast as some other mallocs() (like Hoard or tcmalloc) and, in the end, it's still just another malloc(). Giving up the malloc() interface allows a very simple page-long allocator to outperform every malloc() I've ever tried (including SuperMalloc), and it would truly surprise me to learn there was some exotic memory technique (HTM, caching, etc) that could beat me.
- ciniglio 10y ago
  Can you elaborate on what you mean by "Giving up the malloc() interface"?
  - geocar 10y ago
    malloc(sizeof(foo)) is slower than alloc_foo() because the latter can simply be a pointer increment, but there is no way to tell the malloc() interface that you're going to be doing nothing but allocating foo for a while. malloc() can guess this with heuristics, but a good malloc() needs to perform well for a wide variety of use cases: Surely you can appreciate that balance has a cost that the specialised allocator simply doesn't have to pay.
  - scott_s 10y ago
    The API for malloc is very simple: void* malloc(size_t len); void free(void* ptr); Basically, ask for an amount of memory, and give back a pointer to memory. But it does not allow you communicate anything but the amount on an allocation, and you can only give a memory pointer on freeing. If, for example, malloc had an interface like: void* malloc(size_t len, duration_t dur); enum duration_t { SHORT, MEDIUM, LONG}; One can imagine you could optimize based on the given hint. Once you open up one kind of hint, you can imagine many other kinds of things users could communicate explicitly to the memory allocator about the allocation and access patterns of their data. All implementations of free also need to find the related metadata for the given pointer. We could also imagine an interface for free which required the user to maintain that, but could perhaps speed things up: void free(void* ptr, meta_t d); Or, we could also imagine communicating how important it is to free this memory: void free(void* ptr, immediacy_t im); enum immediacy_t { IMMEDIATE, DELAYABLE }; In the latter case, maybe the memory allocator could put off doing delayable requests, and do them in a batch later. (Making it a bit more like garbage collection.) I'm not sure any of these ideas would help, but the point is that because of the limited interface, we really can't explore them. We can, but then convincing the rest of the world to change such a basic building block of C code is quite hard.
gbrown_ 10y ago
On the subject of papers, for those who have not read them Jeff Bonwick's work on the Solaris slab allocator is well worth reading. https://www.usenix.org/legacy/publications/library/proceedings/bos94/full_papers/bonwick.a https://www.usenix.org/legacy/publications/library/proceedin... https://www.usenix.org/legacy/event/usenix01/full_papers/bonwick/bonwick_html/index.html https://www.usenix.org/legacy/event/usenix01/full_papers/bon... Pretty much every OS kernel has adopted the techniques outlined in these papers.
- eatbitseveryday 10y ago
  These ideas are also excellent. While slab allocators can be very fast and space-efficient, they are meant to be used in scenarios where you know in advance what object sizes are, as each slab cache only allocates one kind of object. The kernel is a great use case, because you know which structs will be frequently allocated/destroyed, thus create a slab cache for just that one data structure (and others for other structs). And the kernel itself does not change frequently, nor does it allocate objects of sizes imposed by user-space (like a file system or key-value store would have to). Memcached employs (-ed ?) its own allocator that is almost analogous to a slab allocator. It creates each cache not from understanding specific object sizes (since it cannot - it is a key-value store), but from a range of sizes incremented by some runtime constant. This can lead to really severe memory bloat in some instances. Memory allocators are not easy. Even "general-purpose" allocators are not truly meant for general-purpose allocation; the DSA paper mentioned above states (page 6 top left): > It has been proven that for any possible allocation algorithm, there will always be the possibility that some application program will allocate and deallocate blocks in some fashion that defeats the allocator's strategy, and forces it into severe fragmentation
scottlamb 10y ago
> SuperMalloc exploits the fact that although physical memory is always precious, virtual address space on a 64-bit machine is relatively cheap. It allocates 2 MiB chunks which contain objects all the same size. Hmm, this must not interact well with huge pages: either all those (1 huge page-sized) chunks actually take up physical memory or you're stuck with 4 KiB pages. Transparent huge pages on Linux are a noticeable performance difference in practice. In one of my applications, a coworker discovered that dTLB misses were a significant source of slowness. He pointed out that we had a lot of "holes" in our memory allocation caused by the malloc implementation calling madvise on 4 KiB pages when they were empty, thus preventing them from being coalesced into a 2 MiB huge page (or causing them to be migrate back to small pages). Setting a commandline flag to prevent this decreased CPU usage by 7%.
anarazel 10y ago
> SuperMalloc achieves these performance advantages using less than half as much code as the alternatives. SuperMalloc exploits the fact that although physical memory is always precious, virtual address space on a 64-bit machine is relatively cheap. On the other hand that can considerably increase the size of the page table, and the cost and frequency of TLB misses. So I'm not sure this all a meaningful comparison.

mallaco 10y ago

> One major limitation of malloc (and even the best implementations like jemalloc and dlmalloc) is that they try to use a single allocator for each data structure. This is a mistake: A huge performance gain can be had by using a separate allocator for each of your data structures — or rather, for each of your data usage patterns. I stopped reading the article at this point. This statement has been disproven repeatedly over the years with Hoard and jemalloc. It is counter-intuitive but the data backs it up. Custom per-data-structure allocators can fragment the global memory arena and cause more CPU cache misses as result of the extra code involved. The latest/greatest malloc/free implementations use a myriad of optimizations to achieve speed improvements that a custom allocator implementation would rarely use. It's not an accident that jemalloc is so widely used in major applications - it works extremely well. https://github.com/jemalloc/jemalloc/wiki/History https://github.com/jemalloc/jemalloc/wiki/History https://github.com/jemalloc/jemalloc/wiki/Adoption https://github.com/jemalloc/jemalloc/wiki/Adoption

gens 10y ago
How about fragmentation ? AFAIK jemalloc is horrible when it comes to memory usage.
- mallaco 10y ago
  My use of jemalloc in multithreaded servers shows the opposite to be true. Memory use is a little higher than the single mutex dlmalloc, but you'd expect this with a modern high performance thread aware malloc implementation. You think MariaDB would choose jemalloc if it wasn't efficient in memory use?
  - biocomputation 10y ago
    >> You think MariaDB would choose jemalloc if it wasn't efficient in memory use? I don't think this is a smart way of choosing an allocator.
- pcwalton 10y ago
  What makes you say that? jemalloc's fragmentation is very low [1]. [1]: https://blog.pavlov.net/2007/12/04/vlad-and-analysis-of-dtrace-was-used/ https://blog.pavlov.net/2007/12/04/vlad-and-analysis-of-dtra...

FroshKiller 10y ago

I don't mean to be spammy about this, but I feel like I should repeat it. If you like this kind of content, consider joining the SDF. It's a free public access computing community with lots of artists, hackers, and grognards of all stripes. Your support is appreciated: https://sdf.org/ https://sdf.org/

_RPM 10y ago

sizeof returns size_t, not sure why he's using `long long`, but to be precise it isn't a function, so it doesn't "return" anything. I guess it "yields" size_t.

colanderman 10y ago

Not to be a downer, but this is poor and outdated C programming style. Don't use sbrk(2) unless you're completely reimplementing the standard library. Don't use alloca(3) unless you want weird headaches. Just use dynamically-sized arrays, which have been present in C for nearly two decades. They are block-scoped and easier to reason about. None of the magic numbers are explained. `(p->si_addr + (16LL<<22)) & ~4095`, where do those come from? I'm guessing 4095 is the page size less one, but DON'T hardcode that! Don't assign to lvalues in conditionals! (e.g. `while(j<31 && !(h=free_table[j]))`) It's hard to read and bug-prone. Don't use `&h[1]` to refer to the space after a structure. I'm pretty sure that's undefined behavior, and it often gives the wrong alignment for whatever you want to put after h. Rather, add a final element to the structure of flexible array type (say `int data[]` if you're storing ints after the structure). That is guaranteed to have the semantics you're looking for. Here's my advice: 1) Just use malloc(3). It's already fast and tuned to many allocation scenarios (including all four in this article!), and your application will continue to reap whatever performance improvements its maintainers make. Use aligned_alloc(3) if you need pages. 2) When working in the embedded world, it's often preferable to preallocate pools as large as your app will ever need for each kind of object you have collections of, and pin them to RAM (not necessarily for performance, but so you know you have the space). If you do so, you can reference the objects by index rather than pointer. It's much faster and more space-efficient, especially on 64-bit architectures. 3) Don't be afraid to realloc(3) to grow arrays. It incurs no asymptotic penalty. 4) Pay attention to data layout, to make sure that commonly-accessed stuff is not interspersed with rarely-accessed stuff. E.g. separate indexes from data where possible, if you tend to traverse the index rather than the data. (Caveat: all my comments above apply to glibc. YMWV on other systems.)

akira2501 10y ago
> Don't use `&h[1]` to refer to the space after a structure. I'm pretty sure that's undefined behavior Not defending the code, but it isn't undefined. Pointers to "one past the last element of an array" are a special case and have specific/defined behavior in the standard.
- colanderman 10y ago