Eliminate global lock in allocation path

[bblum]

Currently, I believe @ and ~ are represented by allocating on the same literal heap at runtime. Creating a new private heap for each task for @-allocations would let tasks avoid hitting a global lock for every allocation.

Global locking is an important consideration for massively-parallel computation, and providing a way to avoid it while still allowing dynamic memory allocation would be seriously attractive to the multicore programming world. (It would also provide more motivation to use @-vectors!)

[brson]

It might additionally be nice to have pluggable allocation strategies (in some sense - at least for comparing options). So far we've mostly been assuming that simply plugging in jemalloc or tcmalloc will be sufficient for most uses, since they do very smart things with multithreading, but there's a lot of opportunity for experimenting here.

[bblum]

I have heard tell that concurrent allocators also exist which can avoid locking in fast-paths. Definitely worth a look.

[graydon]

My intention is to make the local heap (and probably the stack) use a general
pool of pages from the operating system (via mmap/VirtualAlloc) plus a
secondary set of "large allocations" from malloc. A thread-caching allocator
may also make sense for the exchange heap, but whatever does the exchange heap
it has to understand MT operation. The local heap does not.

The page pool should suffice for most values and will permit mostly-copying
style mixed conservative / precise operation, copying and compacting between
pages that are only precisely references. I also intend to segregate pages into
dense (per-type) bibop-style allocation sets tracked with bitmaps. Both factors
should keep fragmentation low, and there should be no sharing of pages between
tasks.

[brson]

Removing 0.7 milestone. I don't think this will happen before 1.0

[bblum]

nominating production ready

[graydon]

accepted for production-ready milestone

[nikomatsakis]

Updated title to reflect the fact that the global lock is bad, but there are many possible solutions beyond making distinct per-task heaps: just using jemalloc probably gets us most of the same perf wins, for example.

[brson]

I also believe that it will be hard to beat just using jemalloc everywhere.

[thestinger]

I think jemalloc is mostly free of locks because once your allocations are larger than the thread-local arenas you start hitting mmap/munmap, and the Linux kernel doesn't use a global lock for that anymore.

[thestinger]

jemalloc is re-enabled, so I think we can consider this a non-issue

the only potential issue is with large allocations on non-Linux platforms, but we would need hard numbers to verify if that's the case and the garbage collector will provide a local heap anyway (eventually)