Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Writing a Memory Allocator for Fast Serialization

idryman.org

Post reply on HN
Print view View original

11–20 of 23 posts

Re: Writing a Memory Allocator for Fast Serialization

#11

Post by dryman »

bananaboy wrote: post #10
dryman wrote: post #8

Earlier quoted context omitted.

The problem is C++ brings in many extra pointers. For example, the vtable pointer used in virtual functions. All the pointers not converted to offset can be invalid in next process that deserializes the object.

You don't have to use virtual functions though. You can just use plain old data structures.

If I use a strict subset of C++, probably will do. However, figuring out the subset of different C++ standards and implementation that doesn't include extra pointers is hard. I might need to re-implement some useful utilities like unique pointer and share pointers as well. Some fundamental data structure in C++ includes pointers as well, like short string optimization introduce extra pointers. With my poor C++ knowledge, I don't even know what are the other pointers are missing..

Re: Writing a Memory Allocator for Fast Serialization

#12

Post by cjhanks »

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.

Re: Writing a Memory Allocator for Fast Serialization

#13

Post by sriram_malhar »

Nice bit of work.

Jiri Soukup's 2001 book on "Serialization and Persistent Objects: Turning Data Structures into Efficient Databases" consists of many techniques, including the serialisation of mmap'd pages.

https://books.google.co.in/books?id=DHDABAAAQBAJ&pg=PA74&dq=...

Re: Writing a Memory Allocator for Fast Serialization

#14

Post by Erwin »

I had a similar idea but my target was a Python application, that was parsing text to create a complex in-memory object tree with tens of thousands of objects.

The idea was that the individual elements were not always fully accessed when the application ran, so if I created them on demand from such a dense memory-mappable dump I could persist that instead of parsing every time.

The overhead of creating Python object was too high for that. But if you are using Python and are deserializing read-only dictionaries, http://discodb.readthedocs.io/en/latest/ does a subset of that -- if your app e.g. reads in 100,000 translations from a JSON file, Disco's serialization will let you just mmap them.

Re: Writing a Memory Allocator for Fast Serialization

#16

Post by barrkel »

cjhanks wrote: post #12

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…

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.

Re: Writing a Memory Allocator for Fast Serialization

#17

Post by gpderetta »

The survey of the state of the art is missing boost.interprocess, which provides shared memory allocators plus drop-in replacements for c++ standard library containers that can handle these allocators [1].

The biggest problem with interprocess is that out of the box it is not capable of handling application failures gracefully and transparently.

[1] Basically the container must not assume that the allocator::pointer type is an actual raw pointer as interprocess uses a custom offest pointer.

Re: Writing a Memory Allocator for Fast Serialization

#18

Post by hyc_symas »

dryman wrote: post #9
bertr4nd wrote: post #6

What happens if the program unexpectedly terminates during an update to these persistent data structures? Is the mmap'ed file corrupted, or still in a usable state?

I don't have a good answer to this question yet. For now I only create the heap in swap, write it to disk, and then use it as read only mmap. To ensure the written file is valid, one can write it to a temporal file first, once confirmed the file is written, then mv the file to desired file name and location. This works for immutable data, but is a big blocker for me to make OPIC work on mutable back store. This probl…

You should have looked more closely at LMDB, which already solves this problem. Also you could look at LMDB's API for using fixed-address mmap, which lets you store pointer-based structures without any deserialization step at all.

Re: Writing a Memory Allocator for Fast Serialization

#19

Post by dryman »

cjhanks wrote: post #12

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…

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/kuszmaul/SuperMalloc

Re: Writing a Memory Allocator for Fast Serialization

#20

Post by dryman »

gpderetta wrote: post #17

The survey of the state of the art is missing boost.interprocess, which provides shared memory allocators plus drop-in replacements for c++ standard library containers that can handle these allocators [1]. The biggest problem with interprocess is that out of the box it is not capable of handling application failures gracefully and transparently. [1] Basically the container must not assume that the allocator::pointer…

Awesome. This will be a super useful reference once I want to migrate the library to C++.
Post reply on HN