5 ms·

Rpmalloc – A lock-free memory allocator

95 points by gbrown_ 10y ago

faragon 10y ago
Anyone has measured what takes to free a big amount of small reserved blocks at once, e.g. free 10^8 blocks of 16 bytes?
- CyberDildonics 10y ago
  Are you doing something where you are doing one hundred million small allocations that all get freed at once? If so, I'm going to make a bold claim that there are better ways to manage that memory than a general purpose allocator.
  - faragon 10y ago
    It was just curiosity for that corner case. Obviously, for handling many small memory elements, it is better to avoid calling allocators as much as possible, e.g. using one linear allocation for all the elements, and using realloc() with geometric resize heuristic (i.e. instead of realloc(new_size), doing realloc(new_size * 1.50)).
    - CyberDildonics 10y ago
      That many allocations probably shouldn't even be allocations in the first place. Realloc is not going to make things better, it copies the memory in anything but very tiny allocations.
      - faragon 10y ago
        Realloc, if well implemented, does not copy (using virtual memory stuff).
        hawski 10y ago
        In this case would it work similarly to having single big mmap and counting on kernel allocating pages on first write? So for most cases you would only have a single mmap call and multiple page faults (as it would always be the case). I assume that most allocators do mmap for big allocations so it does not need to be called directly. I lately tried very naive synthetic test to check when realloc will return different address (meaning that it had to copy). My system started swapping, but it did not return different address. I did not know that realloc works like that, but why wouldn't it.
        hoytech 10y ago
        > check when realloc will return different address (meaning that it had to copy) What faragon is referring to is that this assumption is incorrect. The virtual address changing does not imply the memory was copied. On linux for example it could have been remapped with mremap(2).
_wmd 10y ago
Pretty graphs but insufficient analysis, not even a mention of fragmentation in the readme.
- maniccoder 10y ago
  What specifically would you like to know? I would be happy to elaborate more in the readme if you can explain in more detail what you mean with "insufficient analysis". The reason I posted about it on twitter in the first place was that I wanted feedback and comments on what to improve. (Btw, I'm the author of the library)
  - _wmd 10y ago
    Sorry for the terse (and let's face it, slightly unintentionally mean) comment, I just meant that the most interesting aspect of an allocator is not simply its performance, but how it copes with adverse conditions. Yours is already lockless, so that sounds positive already w.r.t. multithreaded performance, but how about when faced with classical allocation patterns likely to cause fragmentation (alloc 2kb, alloc 2kb, free 2kb, alloc 3kb, rinse repeat), and suchlike. I've never had a desire to deviate from my underlying library's libc allocator, but the principle reason for that (aside from potential for mismatched malloc/free calls due to integration errors), is that I know this stuff is a dark art to nail correctly, and I'm opening myself up to all kinds of potential unknowns by discarding the finely tweaked (although potentially not the most efficient) libc allocator that's been getting patched on to handle adversity for the past 20-30 years. I'd expect documentation of this sort to appear in the readme, even if just to make mention of another allocator this one is patterned on, where I could maybe go digging for further information around failure cases This is just a conservative engineer talking, I've never actually written my own general purpose heap allocator, although I understand the design of a few, but perhaps not sufficiently to understand the motivation behind the design (e.g. the kinds of failure cases the design is hoping to avoid). Just more interested in how it's likely to break my app :)
    - maniccoder 10y ago
      Thank you for the clarifications, I will definitely improve the documentation w.r.t trouble cases, fragmentation and similar allocators. The goal is of course not to replace the standard allocator, but rather to offer an alternative for those cases where the standard allocator performs poorly.
CyberDildonics 10y ago
Looks like they are missing jemalloc in the benchmarks, which would be good to see. I think the simplicity of a 1300 line allocator is very alluring. At that level it should avoid bloating small programs and is hopefully easy enough to understand if digging in to it. Also it looks like it is split up into 3 files. consolidating it to a single header file C library would be very nice. One oddity is the 16 bytes alignment. 64 bytes is the false sharing boundary in x64 so I'm surprised to see this in a concurrent allocator, but maybe I've misunderstood exactly what that means here.
- TwoBit 10y ago
  jemalloc doesn't support non-Unix platforms (eg Windows). You may or may not be able to find a Windows port of any particular jemalloc version, but the developers ignore Windows because they don't use it in their server software. We gave up using jemalloc on Windows because it was such a crap shoot.
  - kbenson 10y ago
    That sounds like a good basis for a "portable" version project. Other very targeted software (such as OpenSSH[1]) does this. I'm not sure what it takes to make jemalloc windows compatible, but even if the jemalloc developers don't want to support windows, it's possibly they might be more amenable to working with a project dedicated to portability in general. Also, my understanding is that Rust uses jemalloc, and Rust runs on windows, so what does Rust do? Just use a known good ported jemalloc version? 1: https://www.openssh.com/portable.html https://www.openssh.com/portable.html
    - steveklabnik 10y ago
      We don't use jemalloc on Windows, we use the system allocator, aka HeapAlloc.
    - CyberDildonics 10y ago
      There are already versions out there on github that have windows support built in, I've used it on windows. I also had problems with it however.
tqh 10y ago
They don't mention anything about memory fragmentation..
hacknat 10y ago
Remember kids, "lock-free", does not always mean faster, it just means lock free. Example: Lock-free linked lists are great spiky write consistent read situations, but in high-write situations they probably aren't any better than locked linked lists.
karavelov 10y ago
Does is support allocating memory from HugePages? I couldn't find anything but it should be easy to add for *nix systems as it is already using mmap to request memory from the kernel.
- maniccoder 10y ago
  It does not, at the moment. Feel free to create an issue about it on the github repo, or even submit a PR if you're feeling creative.
areakkana 10y ago
Watch Beauty and the Beast Online free https://gardenhood.com.au/forum/online-watch-beauty-and-beast-movie-online-putlocker-free-2 https://gardenhood.com.au/forum/online-watch-beauty-and-beas...
Asooka 10y ago
I don't see it mentioned, so does anyone know: Can I use this in parallel with malloc? Meaning, can one part of my program use this for allocating memory, while another uses the standard library malloc/free?
- frutiger 10y ago
  If you implement the pmr interface and use pmr container types[0] then yes. 1. http://en.cppreference.com/w/cpp/memory/memory_resource http://en.cppreference.com/w/cpp/memory/memory_resource
- maniccoder 10y ago
  Yes, you can (unless you also include the provided malloc.c glue code which provides the malloc family of entry points - only use the rpmalloc.c implementation). However, read the caveat section in the readme if you're on a mmap based system.
ckok 10y ago
Seems interesting; but what happens when 1 thread allocates memory, passes it to another thread and ends? There does not seem to be a way to change ownership of a memory block?
- maniccoder 10y ago
  Memory blocks are owned by the span (the page-aligned larger bucket of blocks) they belong to. While a span is in use (at least on block is allocated) it is indeed owned by the heap that allocates the block. When the span is completely freed, ownership is released. In your case, the block will be marked as free for allocation. If it is the last used block in that span, the span will eventually be returned to the global cache and reused by other heaps/threads when the owner thread ends. If the span is still used, it will remain in the heap until the heap is picked up by another thread. Heaps are reused as threads are joined and created (i.e number of allocated heaps are the maximum number of concurrent threads since process started). The worst case is that one thread allocates blocks, hands them off to other threads then ends, and that the process never creates additional threads. In this case, the spans will remain mapped and unused. I have planned to allow other threads to pick up and collect spans from unused heaps at some point to solve this.
  - ckok 10y ago
    that's pretty cool. Is there a way to track progress on reuse (like an issue I can follow)?
    - maniccoder 10y ago
      https://github.com/rampantpixels/rpmalloc/issues/6 https://github.com/rampantpixels/rpmalloc/issues/6

95 points by gbrown_ 10y ago

Anyone has measured what takes to free a big amount of small reserved blocks at once, e.g. free 10^8 blocks of 16 bytes?

CyberDildonics 10y ago
Are you doing something where you are doing one hundred million small allocations that all get freed at once? If so, I'm going to make a bold claim that there are better ways to manage that memory than a general purpose allocator.
- faragon 10y ago
  It was just curiosity for that corner case. Obviously, for handling many small memory elements, it is better to avoid calling allocators as much as possible, e.g. using one linear allocation for all the elements, and using realloc() with geometric resize heuristic (i.e. instead of realloc(new_size), doing realloc(new_size * 1.50)).
  - CyberDildonics 10y ago
    That many allocations probably shouldn't even be allocations in the first place. Realloc is not going to make things better, it copies the memory in anything but very tiny allocations.
    - faragon 10y ago
      Realloc, if well implemented, does not copy (using virtual memory stuff).
      - hawski 10y ago
        In this case would it work similarly to having single big mmap and counting on kernel allocating pages on first write? So for most cases you would only have a single mmap call and multiple page faults (as it would always be the case). I assume that most allocators do mmap for big allocations so it does not need to be called directly. I lately tried very naive synthetic test to check when realloc will return different address (meaning that it had to copy). My system started swapping, but it did not return different address. I did not know that realloc works like that, but why wouldn't it.
        hoytech 10y ago
        > check when realloc will return different address (meaning that it had to copy) What faragon is referring to is that this assumption is incorrect. The virtual address changing does not imply the memory was copied. On linux for example it could have been remapped with mremap(2).

_wmd 10y ago

Pretty graphs but insufficient analysis, not even a mention of fragmentation in the readme.

maniccoder 10y ago
What specifically would you like to know? I would be happy to elaborate more in the readme if you can explain in more detail what you mean with "insufficient analysis". The reason I posted about it on twitter in the first place was that I wanted feedback and comments on what to improve. (Btw, I'm the author of the library)
- _wmd 10y ago
  Sorry for the terse (and let's face it, slightly unintentionally mean) comment, I just meant that the most interesting aspect of an allocator is not simply its performance, but how it copes with adverse conditions. Yours is already lockless, so that sounds positive already w.r.t. multithreaded performance, but how about when faced with classical allocation patterns likely to cause fragmentation (alloc 2kb, alloc 2kb, free 2kb, alloc 3kb, rinse repeat), and suchlike. I've never had a desire to deviate from my underlying library's libc allocator, but the principle reason for that (aside from potential for mismatched malloc/free calls due to integration errors), is that I know this stuff is a dark art to nail correctly, and I'm opening myself up to all kinds of potential unknowns by discarding the finely tweaked (although potentially not the most efficient) libc allocator that's been getting patched on to handle adversity for the past 20-30 years. I'd expect documentation of this sort to appear in the readme, even if just to make mention of another allocator this one is patterned on, where I could maybe go digging for further information around failure cases This is just a conservative engineer talking, I've never actually written my own general purpose heap allocator, although I understand the design of a few, but perhaps not sufficiently to understand the motivation behind the design (e.g. the kinds of failure cases the design is hoping to avoid). Just more interested in how it's likely to break my app :)
  - maniccoder 10y ago
    Thank you for the clarifications, I will definitely improve the documentation w.r.t trouble cases, fragmentation and similar allocators. The goal is of course not to replace the standard allocator, but rather to offer an alternative for those cases where the standard allocator performs poorly.

CyberDildonics 10y ago

Looks like they are missing jemalloc in the benchmarks, which would be good to see. I think the simplicity of a 1300 line allocator is very alluring. At that level it should avoid bloating small programs and is hopefully easy enough to understand if digging in to it. Also it looks like it is split up into 3 files. consolidating it to a single header file C library would be very nice. One oddity is the 16 bytes alignment. 64 bytes is the false sharing boundary in x64 so I'm surprised to see this in a concurrent allocator, but maybe I've misunderstood exactly what that means here.

TwoBit 10y ago
jemalloc doesn't support non-Unix platforms (eg Windows). You may or may not be able to find a Windows port of any particular jemalloc version, but the developers ignore Windows because they don't use it in their server software. We gave up using jemalloc on Windows because it was such a crap shoot.
- kbenson 10y ago
  That sounds like a good basis for a "portable" version project. Other very targeted software (such as OpenSSH[1]) does this. I'm not sure what it takes to make jemalloc windows compatible, but even if the jemalloc developers don't want to support windows, it's possibly they might be more amenable to working with a project dedicated to portability in general. Also, my understanding is that Rust uses jemalloc, and Rust runs on windows, so what does Rust do? Just use a known good ported jemalloc version? 1: https://www.openssh.com/portable.html https://www.openssh.com/portable.html
  - steveklabnik 10y ago
    We don't use jemalloc on Windows, we use the system allocator, aka HeapAlloc.
  - CyberDildonics 10y ago
    There are already versions out there on github that have windows support built in, I've used it on windows. I also had problems with it however.

tqh 10y ago

They don't mention anything about memory fragmentation..

hacknat 10y ago

Remember kids, "lock-free", does not always mean faster, it just means lock free. Example: Lock-free linked lists are great spiky write consistent read situations, but in high-write situations they probably aren't any better than locked linked lists.

karavelov 10y ago

Does is support allocating memory from HugePages? I couldn't find anything but it should be easy to add for *nix systems as it is already using mmap to request memory from the kernel.

maniccoder 10y ago
It does not, at the moment. Feel free to create an issue about it on the github repo, or even submit a PR if you're feeling creative.

areakkana 10y ago

Watch Beauty and the Beast Online free https://gardenhood.com.au/forum/online-watch-beauty-and-beast-movie-online-putlocker-free-2 https://gardenhood.com.au/forum/online-watch-beauty-and-beas...

Asooka 10y ago

I don't see it mentioned, so does anyone know: Can I use this in parallel with malloc? Meaning, can one part of my program use this for allocating memory, while another uses the standard library malloc/free?

frutiger 10y ago
If you implement the pmr interface and use pmr container types[0] then yes. 1. http://en.cppreference.com/w/cpp/memory/memory_resource http://en.cppreference.com/w/cpp/memory/memory_resource
maniccoder 10y ago
Yes, you can (unless you also include the provided malloc.c glue code which provides the malloc family of entry points - only use the rpmalloc.c implementation). However, read the caveat section in the readme if you're on a mmap based system.

ckok 10y ago

Seems interesting; but what happens when 1 thread allocates memory, passes it to another thread and ends? There does not seem to be a way to change ownership of a memory block?

maniccoder 10y ago
Memory blocks are owned by the span (the page-aligned larger bucket of blocks) they belong to. While a span is in use (at least on block is allocated) it is indeed owned by the heap that allocates the block. When the span is completely freed, ownership is released. In your case, the block will be marked as free for allocation. If it is the last used block in that span, the span will eventually be returned to the global cache and reused by other heaps/threads when the owner thread ends. If the span is still used, it will remain in the heap until the heap is picked up by another thread. Heaps are reused as threads are joined and created (i.e number of allocated heaps are the maximum number of concurrent threads since process started). The worst case is that one thread allocates blocks, hands them off to other threads then ends, and that the process never creates additional threads. In this case, the spans will remain mapped and unused. I have planned to allow other threads to pick up and collect spans from unused heaps at some point to solve this.
- ckok 10y ago
  that's pretty cool. Is there a way to track progress on reuse (like an issue I can follow)?
  - maniccoder 10y ago
    https://github.com/rampantpixels/rpmalloc/issues/6 https://github.com/rampantpixels/rpmalloc/issues/6