4 ms·

The idea in general is well understood, the popular HDF5 library has an IO driver which essentially memory maps structures in this way. Numpy also allows for m

The idea in general is well understood, the popular HDF5 library has an IO driver which essentially memory maps structures in this way. Numpy also allows for memory mapping numpy complex structures. In the past I have used this strategy for mapping point data (on the order of billions of points) which would never possibly fit into memory. Tuning the allocator is not as straight forward as you may believe. If you have variable sized allocations the problem is fairly difficult... you essentially are forced to rewrite a worse version of ptmalloc, jemalloc, or tcmalloc. If your allocations are fixed, you're in a slightly rosier situation. However, you have to consider - how will you support deletions? Will you journal and garbage collect? Are you going to force variable latency? Are you going to implement atomic barriers on lockless structures? Now that I think of it... what is the cost of an atomic operation on a shared memory map? You will also need to concern yourself with cache hits/misses. In my experience it is somewhat difficult to predict what memory in your map is going to be in cache and what won't. If your data scatters... your performance is going to be fairly slow.

barrkel 9y ago
I've implemented this scheme in the past, for fast serialization in a C# app - a byte array was used for session storage, and requests updated values directly inside the byte array rather than serializing and deserializing an object graph for every request. It needs to be combined with a GC to work well for precisely the reasons you mention: variable sized allocations, and reallocations, will bloat the blob of memory otherwise. Also, if using a GC, allocation is a much simpler problem, because fragmentation isn't an issue. In some cases, where data is built up once, then reused read-only, you don't need to pay the reallocation cost. For example, the Borland C++ compiler used this approach for precompiled headers. The symbol table information was allocated in a single contiguous blob of memory, with pointer locations noted just like you'd note fixups when writing an object file. Then, when the precompiled header was loaded, the fixups would be iterated over and the difference in old load address and new load address would be added to every pointer location: and all the pointers work again! The idea is in this conjunction of linkers, loaders and garbage collectors; all three are strongly related functionalities. A smart linker is a copying GC; a moving GC is almost isomorphic to an OS loader, except the source is memory rather than disk (or mmap); a loader is a runtime linker; etc.
dryman 9y ago
All these concerns are critical, and this is why I spent 6 months to build OPIC malloc prototype. I surveyed a lot on state of the art malloc implementations, as well as some POC papers. The model I implemented is similar to scalloc and supermalloc. I did a simple benchmark, the performance is identical to jemalloc. That's seems good enough for me for now. OPIC has potential to use even faster concurrency model dropping atomic implementation and move to urcu (user space rcu). However, this is not very necessary for a serialization focused malloc. The detail of how I implemented this malloc will be discussed in later post. Reference. https://github.com/cksystemsgroup/scalloc https://github.com/cksystemsgroup/scalloc https://github.com/kuszmaul/SuperMalloc https://github.com/kuszmaul/SuperMalloc

barrkel 9y ago

I've implemented this scheme in the past, for fast serialization in a C# app - a byte array was used for session storage, and requests updated values directly inside the byte array rather than serializing and deserializing an object graph for every request. It needs to be combined with a GC to work well for precisely the reasons you mention: variable sized allocations, and reallocations, will bloat the blob of memory otherwise. Also, if using a GC, allocation is a much simpler problem, because fragmentation isn't an issue. In some cases, where data is built up once, then reused read-only, you don't need to pay the reallocation cost. For example, the Borland C++ compiler used this approach for precompiled headers. The symbol table information was allocated in a single contiguous blob of memory, with pointer locations noted just like you'd note fixups when writing an object file. Then, when the precompiled header was loaded, the fixups would be iterated over and the difference in old load address and new load address would be added to every pointer location: and all the pointers work again! The idea is in this conjunction of linkers, loaders and garbage collectors; all three are strongly related functionalities. A smart linker is a copying GC; a moving GC is almost isomorphic to an OS loader, except the source is memory rather than disk (or mmap); a loader is a runtime linker; etc.

dryman 9y ago

All these concerns are critical, and this is why I spent 6 months to build OPIC malloc prototype. I surveyed a lot on state of the art malloc implementations, as well as some POC papers. The model I implemented is similar to scalloc and supermalloc. I did a simple benchmark, the performance is identical to jemalloc. That's seems good enough for me for now. OPIC has potential to use even faster concurrency model dropping atomic implementation and move to urcu (user space rcu). However, this is not very necessary for a serialization focused malloc. The detail of how I implemented this malloc will be discussed in later post. Reference. https://github.com/cksystemsgroup/scalloc https://github.com/cksystemsgroup/scalloc https://github.com/kuszmaul/SuperMalloc https://github.com/kuszmaul/SuperMalloc