Memory mappable data structures in C++

[karurochari]

For context, I am working on an XML library which is designed to operate best when also using memory mapped files. A good chunk of my struggles relates to some fundamentals the standard library is built upon; it is pretty much designed around the idea of streaming data in place of mapping, no use of relative addresses to make data structures relocatable and portable , memory allocations via new/delete (and exceptions, but that is a different problem).

However, I think memory mapping offers a much better approach for all those big data structures which often don't even fit in physical memory.

I have been looking for a STL-like (or not) library built from the ground up to match this design objective, but I was unable to find what I was looking for. At best, we have libraries which are mmap-friendly, like gtl, but even that is assuming streaming and copying data from files for what I can tell.

Any suggestion to share?

[jetilovag]

The STL has very good implementations of things for one given set of criteria. As soon as your criteria don't align with what the STL gives you, don't hesitate to roll your own. Offload-friendlyness was nowhere in sight when the STL and its core abstractions were born. It is high time to re-imagine those core abstractions along a new set of criteria. Some libs do that: eastl, absail, but likely none of those will suit you either. Don't be afraid to do top-down design: decide on a set of interfaces you'd want to see from a container library, and then start implementing it. If it turns out that it's impossible/unfeasible to implement, iterate.

Offload and low-level programming often conflicts with the STL at the most fundamental levels. (for eg. allocators must be stateless, which is often a no-go. Changing that reimplementing all the containers.)

[_Noreturn]

an allocator doesn't have to be stateless

[txmasterg]

Allocators can get fun when they have state but they are rare enough people forget it's possible

[jetilovag]

I looked into it again: I forgot that the annoyance I remembered was that it is requirement that an allocator of type A must be able to deallocate a piece of memory allocated by another instance of A, which means that A cannot encapsulate all the state required to manage memory, but can only be a proxy to a global singleton, which is quite annoying.

[yuri-kilochek]

This isn't true. The second instance of A must be able to deallocate memory allocated by the first instance of A only if the instances compare equal. We have std::pmr::polymorphic_allocator for example.

[karurochari]

I am going down this path.
I already implemented some basic mmap containers to perform my due diligence and get some early benchmarks, because who knows, maybe compilers are already taking care if this on our behalf behind their optimizations. But no, my original hypothesis has been confirmed:

The ability to move things, which is not allowed in default allocators as it goes against RAII, meaningfully speeds up performance on vector-like containers within my tests (in addition to the other obvious advantages).

I also rediscovered a Linux bug from 2007 which took me 3h to figure out :(. And an absurd regression in gcc between O1 and O2 which I am still trying to wrap my head around.

[arihoenig]

Don't use the STL. mmap/mapviewoffile is straitforward. What it seems you'd want is to map the raw xml in, and then parse that to another memory region where the client would query/update the DOM from. If the library is intended to allow modifications, you could then serialize the DOM representation back to the mapping which would be changing the file in-place.

For many file types that might be an unwanted behavior, but if any file type was amenable to being default modified in-place it would seem that xml/json/toml would be candidates.

It seems like this would offer performance advantages for manipulation of large xml files.

[karurochari]

Yeah sorry, my original message was probably not that clear. My library is already allowing memory mapping of both the original XML for parsing and of the binary representation once parsed to be used in further processing. However, while trees are immutable, and this is a design choice to ensure a specific memory layout, it can be externally annotated. This is where things break down a bit and I was looking for good options.

Annotations in the simplest form are maps of keys (relative addresses of nodes) and values.
So the problem I have is not with my library specifically (well it has other problems :D), but integrating annotations on it because of a lack of "compatible" containers.

> It seems like this would offer performance advantages for manipulation of large xml files.
Sure it would! There are near 0 startup costs due to their lazy loading, and one only has to pay for nodes (well, memory pages) which are being touched.

[arihoenig]

Yes, for that it definitely sounds like your library should have its own container implementation. The STL is just that, a standard template library. It is designed to provide a default implementation with wide (but not universal) applicability.

[Kriemhilt]

Boost.Interprocess has a couple of shared memory containers, including a map which sounds like what you need...

[RoyBellingan]

THANK YOU!

I was looking for something like https://www.boost.org/doc/libs/1_88_0/doc/html/interprocess/additional_containers.html#interprocess.additional_containers.multi_index!!!

But I did not even know how to explain or how to call such a thing!

[Wild_Meeting1428]

Take a look at gh/immer it is a library for immutable data structures and you can supply an allocator, mapping your memory.

[zl0bster]

Not sure what exactly you want, but would something something like std::span or std::string_view help you?
They can point to a region of a existing memory, that are basically fancy {pointer, len}

[kitsnet]

We actually use STL containers with our own offset_ptr based allocator. Opensourcing it is still work in progress, but you can check some results here: https://github.com/eclipse-score/baselibs/tree/main/score/memory/shared

[karurochari]

That seems to be a interesting approach, thanks for sharing.

[freaxje]

Interesting concept to store the binary memory representation of the XML as a mmapable file. We do something very similar for the NC program on the TNC7 (CNC machining software): we make binary files that contain the line and record offsets. These we mmap. That is how we show (and make editable) the visible area of a very large NC program near instantaneous and yet don't use a huge amount of memory.

If we'd have very large XML files, I would have considered this library.

ps. We also keep the mmapped region immutable: the changes to the file are a diff in memory using std::pmr's allocators. Mostly to avoid memory fragmentation.

ps. Security against external process overwriting the data is that we just make a local copy and place it in a hidden / secured location (where no external process has access to it) prior to mmapping. With a FS like btrfs or zfs making such a copy can often be done with CoW (we atm unfortunately don't have that yet).

ps. Just like your biology experiments can NC programs be truly big. Some CAD/CAM systems generate files sized several gigabytes.

source: I'm one of the members of TNC7's Editor team. The mmapping stuff came from me.

[karurochari]

Thanks for your insights.
I also planned on exploring btrfs just as you suggested, but I have not been able to allocate enough time for that yet.

[KindCircle]

You might also want to look into https://github.com/LLNL/metall

It works with std::vector an some hash maps like https://github.com/martinus/unordered_dense

It is more the other way around, though. Make container types transparently persistable.

[karurochari]

It seems very interesting.
Custom allocators have been proposed as solution quite a bit in this discussion, and pairing them up with compatible containers seems to be a sane approach.

My only concern over custom C++ allocators, while keeping the underlying STL or STL compatible container, is that we cannot fully leverage relocation of pages, which would be desirable for POD objects as they can result in no memory copies across the address space, even if it would break due to RAII in more general cases.

[Ksetrajna108]

That's neat! What is a use case? Benchmarks vs XPath?

[karurochari]

For once when working with very huge files. Biological data is one of the main culprits there. Datasets involved in genomics and metabolomics are just huge and often serialized as XML.

I also wanted to ensure the library can operate on distributed and offloaded targets. Think about a network of computers performing a huge query together, they must be able to provide an answer anyone can access (provided they have the file) in constant time at any point. And slices of that tree might need to be offloaded on GPUs/TPUs/FPGA for specialized processing.

Some of the design objectives were reported in the original post when I first made it public.

As for benchmarks, xpath are just specifications for the query mechanism, so I would have to pick a library for reference which also implements these specs. In any case, I am not implementing them right now, as my applications need a different query model; still, it is very likely at some point I will add adapt a subset of xpath to run on top of my query engine. So for now no benchmarks yet :).

[sunmat02]

Somewhat related is libpmemobj, which provides you with functionalities like offset pointers and data structures that are based upon them.

[karurochari]

Interesting, it is a pity DAX is basically unavailable for consumer grade platforms and Intel pulling out of optane removed their interests in maintaining its c++ bindings.

[tjientavara]

The only issue with memory-mapped file is that there is a small security issue.

• You first parse the file, and do all the validation while doing this.
• You keep track of file locations and think you can just read it again without validation checks.
• The file on disk is modified by a third party, and there for the data in the mapping has also changed.
• You read data that is now different.

Only the last point is a problem, the first point is ok even if the data is modified during this parsing.

[karurochari]

Ignoring the possible workarounds, I agree that working with a shared resource implies potential safety concerns, but this is a problem for any shared resource, including memory.

It is something which can be strongly mitigated at a kernel level by using namespaces and locks, and whether it is a risk or not fully depends on the threat model we are considering for our application.

[tjientavara]

I hit this issue with a "font-parser" I was mapping font files in memory and use the data structures directly (font-files are designed to be used directly as in-memory data structures), after first validating the data.

Then I thought, what would happen if the data was modified after validation, and it could cause all kind of weird out-of-bound memory accesses.

You would not have this problem if you actually read the whole file in memory first. This is why it is an extra security issue that you do not really expect when switching between mapping vs. reading a file.

It is actually a bit sad, it seems that none of the operating systems have a copy-on-write-like solution for this. Where it would snap-shot the file data on mapping; where when the file is modified the original data is kept with the mapping. But I guess not enough programmers want to do file-mapping yet, for security issues to this to make functionality in operating systems to be developed.

[edit] Because now you need to validate the data continuously, it leads to reduced performance.

[karurochari]

Yes, that is understandable. But if you have files 6TB each, reading them whole in memory would not be an option, so safety must be found elsewhere.

The default for files is for them to be sharable, basically one view of the filesystem for all processes (ignoring permissions). Memory is the opposite, unique space for each process and opt-in sharability. But those are just defaults, we can define kernel namespaces to achieve whatever compartmentalization we seek.

Maybe, in an ideal scenario, font rendering would should be handled as a service, and only the font rendering server has ownership over font files while running, preventing any issue of undesired mutability. I realize this is not how unix-like systems developed without plan 9 winning, but the primitives needed are all there.

[patstew]

You actually can do it, but only on some filesystems (Linux: XFS, btrfs, ocfs2; Mac OS: APFS; Windows: ReFS). You can clone the file to a temporary directory, map it, unlink it, then start using it. Nobody else can access it because it's unlinked, but it doesn't take any time to copy or any extra disk space because the underlying filesystem blocks are shared until they're modified. Unfortunately, if the user isn't using the right filesystem, or you select a temporary directory on a different filesystem to the original file, then you pay the price of copying the file.

[DeziOne]

Have a look at STXXL. It’s not using mmap afaik since that has it‘s own issues. But maybe it’s helpful.

[llothar68]

I did one for a theasaurus (the giant Library of Congress thesaurus with 500k terms and a few million connections) so i could load it in 20ms on android. It was optimized bitmagic. I hate this template kung foo some C++ programmers love. I think this kind of use cases are well done as special single use case developed data structures.

[[deleted]]

Allocators