4 ms·

Random allocation sounds like it could potentially hurt cache for some workloads, but still, this is easily the coolest idea I've seen so far this year. It's b

by _wmd 8y ago

Random allocation sounds like it could potentially hurt cache for some workloads, but still, this is easily the coolest idea I've seen so far this year. It's beyond amazing we can still innovate on something like a memory allocator using hardware tricks that have been available for nearly 40 years. Leave no stone unturned!

xiphias2 8y ago
Couldn't the same algorithm with different parameters be used to increase cache utilization?
nteon 8y ago
Hi! I'm one of the authors -- thanks so much! We thought similarly about cache performance, but weren't able to find specific examples (most of the slow benchmarks we dug into were due to unoptimized allocator performance rather than poorer caching). Informally I think one of the reasons for this is that in long running problems, allocations returned from malloc end up being pretty random rather than contiguous -- as allocations are freed they are put in freelists, and freelists are designed more for temporal locality rather than spatial.
- liuliu 8y ago
  On free, other allocators are likely to return the last freed address but with mesh it will return a random location (i.e. hurt temporal locality). But I guess in modern CPUs it doesn't matter that much because that whole page probably cached anyway, selecting any offsets from that page would be similarly good. BTW, this is really cool project. Do you envision any difficulties of merging this into jemalloc?
  - _wmd 8y ago
    jemalloc is written in C :) That aside, I don't think merging with an existing allocator, if it weren't obscenely unlikely due to the general conservatism in such projects, would necessarily accomplish anything. In terms of contrasts it'd be like trying to merge Ruby with Python.. this project's approach stands independently. It may be better to ask what features it can gain from merging with something like jemalloc
    - liuliu 8y ago
      Yeah, it is interesting to see whether Jason Evans is interested enough to port some of the ideas over to jemalloc. My original wording is poor and shouldn't be read as suggesting merging the codebase literally. Just from reading the paper, the idea itself is simple enough to get ported to any modern allocators (with the only sticky point, as discussed in this thread earlier, about the random allocation algorithm). The overhead in finding / merging pages would be interesting topic to see whether it is reasonable for these modern allocators as well. Wondering whether there are other difficulties the authors saw about porting the idea to other allocators.

by _wmd 8y ago

xiphias2 8y ago

Couldn't the same algorithm with different parameters be used to increase cache utilization?

nteon 8y ago

Hi! I'm one of the authors -- thanks so much! We thought similarly about cache performance, but weren't able to find specific examples (most of the slow benchmarks we dug into were due to unoptimized allocator performance rather than poorer caching). Informally I think one of the reasons for this is that in long running problems, allocations returned from malloc end up being pretty random rather than contiguous -- as allocations are freed they are put in freelists, and freelists are designed more for temporal locality rather than spatial.

liuliu 8y ago
On free, other allocators are likely to return the last freed address but with mesh it will return a random location (i.e. hurt temporal locality). But I guess in modern CPUs it doesn't matter that much because that whole page probably cached anyway, selecting any offsets from that page would be similarly good. BTW, this is really cool project. Do you envision any difficulties of merging this into jemalloc?
- _wmd 8y ago
  jemalloc is written in C :) That aside, I don't think merging with an existing allocator, if it weren't obscenely unlikely due to the general conservatism in such projects, would necessarily accomplish anything. In terms of contrasts it'd be like trying to merge Ruby with Python.. this project's approach stands independently. It may be better to ask what features it can gain from merging with something like jemalloc
  - liuliu 8y ago
    Yeah, it is interesting to see whether Jason Evans is interested enough to port some of the ideas over to jemalloc. My original wording is poor and shouldn't be read as suggesting merging the codebase literally. Just from reading the paper, the idea itself is simple enough to get ported to any modern allocators (with the only sticky point, as discussed in this thread earlier, about the random allocation algorithm). The overhead in finding / merging pages would be interesting topic to see whether it is reasonable for these modern allocators as well. Wondering whether there are other difficulties the authors saw about porting the idea to other allocators.