welcome to the world of…

Looks like a small bulb used to indicate something unusual, like a malfunction.

Reserve virtual memory

Filed under: Uncategorized — Tags: , , , , — admin @ 2018-06-16 13:42

I needed to load a huge amount of data into memory. It had to be a continuous chunk of memory and I could not tell the size from a beginning. C++ std::vector is a good candidate however its downside is that it reallocates and copies all data when it runs out of its current capacity. Virtual memory mapping to the rescue!

My thinking steps looked like:

  • I know a potential maximum of required memory for all possible cases.
  • If I allocate it all at once then I’ll have a continuous memory chunk however it is going to be a huge waste of space in many cases since the dataset size is varying a lot.
  • And it does not scale well if I run it on a much larger data set on a computer with much larger memory than I have.
  • How to ensure a continuous memory address space without preallocating the whole block?
  • In modern OSes processes are running in a virtual memory which is mapped to a real memory.
  • Virtual address space is huuuuuuuuge (well, actually only huuuge, see note at the end).
  • Virtual address does not need to point to a real address if you don’t use it.
  • How about preallocate just a virtual memory block and then map it to a real memory on demand?
  • mmap() and friends can do it!

mmap() is not only for sharing memory and mapping file content to memory. This call will allocate 128 GB of virtual space:

void* ptr = mmap(nullptr, 128ul * 1024 * 1024 * 1024, PROT_NONE,
                 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0));

PROT_NONE tells the kernel that there should be no mapping to a real memory.

Now lets say you need a space for 5 megs of memory:

mprotect(ptr, 5 * 1024 * 1024, PROT_READ | PROT_WRITE);

This will give you 5 megs of accessible memory. If you need more later then call it again with a larger number.

And that’s it. Wrap it in some fancy vector-like class and serve it.

Note: even if you operate on a 64 bit machine with 64 bit addresses you can’t use all 64 bits of the space. E.g. x86 virtual address space has “only” 48 bits. So if you are working with very large data sets (e.g. hundreds of gigabytes) or at least some of them can be then you can easily hit the limit and you will wonder how come you can mmap only few dozens of such large blocks.

Solution can be to add mremap() into the equation. Don’t allocate too large virtual space and even if you hit the allocated limit then call mremap() with MREMAP_MAYMOVE. Watch for a little trap – the whole old space must have the same protection flags. That means you can’t have few megs with PROT_READ and the rest PROT_NONE or you’ll get EFAULT. This approach has also one disadvantage – you can’t use move/copy semantics on contained items like std::vector does. The item type must be trivially copyable.

Final note: mmap(), mprotect() and mremap() are slooooow compared to e.g. malloc() so design your boundaries well and benchmark!

No Comments

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.