Is there a good way to use C++ STL data structures contained within an mmap'ed region of memory?

Question

Anonymous · Accepted Answer

http://www.boost.org/doc/libs/1_42_0/doc/html/interprocess.html, especially http://www.boost.org/doc/libs/1_42_0/doc/html/interprocess/allocators_containers.html#interprocess.allocators_containers.containers_explained

Be careful if you use a file though. If you mmap a file and the machine dies, there are no consistency guarantees -- the kernel can output different sections of the file at different times. You should take a snapshot of the file if you want to be safe in the case of power failures.

Another thing to be careful of is memory fragmentation. If you go this route Boost will be doing its own memory allocation. There are a number of allocators they offer, and I'm not sure how well tuned they are. If you are using a lot of memory, you should have monitoring for fragmentation. If possible, you should avoid allocating short-lived, per request data in the shared space.

Dustin Dettmer · Answer

Every STL object takes an "alloc" template parameter.  The default functionality is to use 'new'.  You can pass in a custom allocation object that you create.  This document appears to discuss exactly your subject, STL types going through threads.
http://www.drdobbs.com/184406243

Another interesting approach is to override the new operator.  This is dangerous though so maybe make a custom new operator (this can also be overridden!).  Ah the joys of C++, where everything is customizable...

Dennis DeCoste · Answer

you might want to check out STXXL ...

Hussein Kanji · Answer

Even if you go down the custom allocator route, i.e. create a memory mapped file and then create a STL map structure with a custom allocator, the problem is pointers.

You have to make sure the memory mapped file always loads from the same exact memory address. You can do this on some operating systems, i.e. on Windows, you can choose the address with MapViewOfFileEx.

You could replace pointers by a template pointer class that keeps the load address of mmap() as a static member, and the offset relative to the mmap area as a member.

ChatGPT · Answer

Using C++ STL data structures with memory-mapped files (mmap) requires careful consideration because STL containers expect to manage their own memory. However, you can leverage mmap to work with STL containers in a way that allows for efficient memory usage while ensuring data integrity. Here’s a general approach to using STL containers with mmap:
Steps to Use C++ STL with mmap
1. Memory Mapping: First, create a memory-mapped file using [code]mmap[/code]. This allows you to map a file or device into memory, enabling you to access the file as if it were a part of the process's memory.
2. Placement New: Use placement new to construct STL objects in the mmap'ed region. This allows you to create objects at a specific memory location.
3. Custom Allocator: Consider implementing a custom allocator that uses the mmap'ed memory for allocation. This allocator can be passed to STL containers to ensure they allocate memory from the mapped region.
4. Object Lifetime Management: Be cautious about the lifetime of the objects. You need to ensure that objects are properly destroyed when they are no longer needed, especially if you're using placement new.
5. Synchronization: If the mmap'ed memory is shared between multiple processes, you'll need to implement synchronization mechanisms (like mutexes) to prevent data races.
Example
Here’s a basic example demonstrating the concept:
[code]#include %3Ciostream%3E
#include %3Csys/mman.h%3E
#include %3Cfcntl.h%3E
#include %3Cunistd.h%3E
#include %3Cnew%3E
#include %3Cvector%3E

class MmapAllocator {
public:
    using value_type = char;

MmapAllocator() = default;

template %3Ctypename U%3E
    MmapAllocator(const MmapAllocator%3CU%3E&) {}

char* allocate(std::size_t n) {
        return static_cast%3Cchar*%3E(::operator new(n));
    }

void deallocate(char* p, std::size_t) {
        ::operator delete(p);
    }
};

template %3Ctypename T, typename U%3E
bool operator==(const MmapAllocator%3CT%3E&, const MmapAllocator%3CU%3E&) { return true; }
template %3Ctypename T, typename U%3E
bool operator!=(const MmapAllocator%3CT%3E&, const MmapAllocator%3CU%3E&) { return false; }

int main() {
    const char* filename = "mmap_example.dat";
    const size_t size = 1024;

// Create and open the file
    int fd = open(filename, O_RDWR | O_CREAT, 0666);
    ftruncate(fd, size);

// Memory-map the file
    void* ptr = mmap(nullptr, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    if (ptr == MAP_FAILED) {
        perror("mmap");
        return 1;
    }

// Use placement new to create a vector in the mmap'ed region
    auto* vec = new(ptr) std::vector%3Cint, MmapAllocator%3Cint%3E%3E();

// Use the vector
    vec-%3Epush_back(1);
    vec-%3Epush_back(2);
    vec-%3Epush_back(3);

std::cout %3C%3C "Vector contents: ";
    for (const auto& val : *vec) {
        std::cout %3C%3C val %3C%3C " ";
    }
    std::cout %3C%3C std::endl;

// Clean up
    vec-%3E~vector(); // Destroy the vector
    munmap(ptr, size);
    close(fd);
    return 0;
}[/code]
Key Points
 * Custom Allocator: The [code]MmapAllocator[/code] class provides a custom allocator that you can use with STL containers.
 * Placement New: The [code]new(ptr)[/code] syntax constructs the vector in the mmap'ed region.
 * Lifetime Management: Remember to manually call the destructor of the vector before unmapping the memory.
Considerations
 * Performance: Using mmap can be slower for small allocations due to the overhead of managing memory pages.
 * Portability: The approach may have platform-specific behavior, especially regarding file handling and mmap.
 * Error Handling: Always check for errors, especially when dealing with system calls like [code]mmap[/code] and [code]open[/code].
This approach provides a solid foundation for using STL containers with mmap'ed memory, but be sure to tailor it to fit your specific application needs and constraints.

Michael Bauers · Answer

I can only speak for myself.

Firstly, I can’t fathom writing C++ code without STL.

I did work on a project where it was strongly discouraged. The stud programmers who had won the respect of managers were telling people STL was not fast enough. Some people argued with them, telling them that premature optimization made no sense…first it should have been proved STL was too slow and for which blocks of the code. It felt so 1990s.

Presuming someone is not standing next to you, insisting you program C++ like you would program C, you should be using all the STL you can. It’s debugged. It’s almost certainly written by very smart people, who realized millions of lines of code might be relying on it, in mission critical applications…so you can rely on it being pretty damn efficient for what it does.

I constantly use vectors and maps, and don't worry about them being inefficient until proven otherwise. Sets also have their uses for me. I haven’t found much use for other stuff ( it’s obviously useful though)

And STL stuff is designed to work with algorithms. Algorithms can make for more compact, more reliable code ( again, they have been thoroughly debugged and made efficient - no need to waste time on that.) And they support range based for loops.

What’s inefficient, IMO, is trying to roll your own half baked, not documented, not fully tested alternatives.

Adam Helps · Answer

Yes, absolutely. Much more so than in, say, student code, because “industry” programmers are far more likely to know how to use the STL*. The STL is awesome.

The STL is generally the best implementation available for the data structures it provides. You should never be writing your own vector**. You should not be writing your own sort, or reverse, or set_intersection, or make_heap. Use the STL version.

There are reasons to write your own classes. For example, Mike Acton’s points about the poor cache behavior of maps (and various other issues) are valid:

https://www.youtube.com/watch?v=rX0ItVEVjHc
However, the whole point of SG14*** is to address these kinds of things, and over time I expect to see more STL in high-performance situations, not less. And most code is not trying to squeeze out a reliable 60 frames-per-second, it’s trying to produce a solution that works with minimal bugs and acceptable performance while consuming a minimum of programmer time.

For that reason, yes, we industry programmers use a lot of STL.

*I know that it’s technically the C++ standard library. But I’m writing this answer from my hotel at CPPCon, and just got out of a presentation attended by actual C++ committee members, in which they were still calling it the STL. Old names die hard.

**I have written my own vector, I had a perfectly good reason for doing so, and I still hold a deep and furious loathing in my heart for the circumstances that forced it. So I stand by my “never” even though I have personally run into exceptions. I hope to have the last of the technical mess that led to it cleaned up in the next year so that I can throw the whole thing in the damnatio memoriae bin.

***SG14 is Study Group 14, the subsection of the C++ committee that works on improving the performance of the language (especially issues around latency). It is attended by people who work on video games, high frequency trading, and embedded devices.

A G · Answer

The STL is coded pretty well as you could imagine. For most scenarios, they are fast enough and easy to use. I’d only consider writing my own if there is need for dirty optimizations in the name of maximum efficiency. As a simple example, a linked list is faster if the pointer to the next piece of datum is stored within the datum. That’s a hacky way to do it though — way clunkier, more prone to error, and less elegant. But with C++, it isn’t uncommon to go all out in the name of optimization as the language comes out to play when performance matters. I’d also naturally write my own or find a prewritten library for a data structure unrepresented in the STL. There are some rare data structures that have advantages a programmer might need for certain situations.

There’s actually a FAQ question about this on Bjarne Stroustrup’s website, the guy who made C++, and in it, he addresses a question about the list implementation and this optimization. As you might expect, he defends the STL’s implementation as being plenty fast for most scenarios. I couldn’t find it on his website anymore, but old C++ pros telling him about this apparently warranted answering the critique.

Jack Brennen · Answer

You can’t avoid the use of raw pointers in C++.

You can hide the use of raw pointers behind smart pointer abstractions.

Most smart pointer library implementations are built on top of raw pointers.

The issue is that C++ runs on top of a CPU ISA (instruction set architecture). Virtually every ISA that I’ve ever seen has instruction-level support for raw pointers, but they generally have very limited support for smart pointers, if any.

So if you want to actually access memory, there’s a raw pointer access down at the bottom of the C++ abstraction layers.

You could implement a memory pool by doing a “placement new” of std::array%3Cchar, 0x1000000%3E and constructing the object on a memory range obtained from the OS using mmap.

But if you want to return smart pointers which use that array as the backing store, then at some point, you’re going through raw pointers — even if you never dereference them.

Rob Menke · Answer

Sparingly and only as a last resort.

The C++ Standard Library offers a good collection of data structures and algorithms that fulfill 99% of normal use cases. Occasionally you may need to augment what the Standard Library offers with extra data, but that can be done easily with custom classes or even [code ]std::tuple[/code] in a pinch. It is very rare to implement a data structure from scratch: the more esoteric data structures are rarely needed as their performance benefits are far outweighed by implementation complexity (the ‘[math]c[/math]’ in [math]|f(n)|\le|cg(n)|[/math]).

If you plan to produce code for others to use, then become familiar with the bridge between the containers and the algorithms: the iterators. Learn how they work, how they are categorized by functionality, and how to implement them. Once you master that, writing new algorithms or new containers will be easy, and you will leverage the power of the existing Standard Library without having to reimplement everything. But more importantly, you’ll be familiar with the Standard Library to realize when — if ever — it is necessary.

Lokesh Kadiyala · Answer

Data Structures are the way by which data is stored and retrieved. Data Structures are used everywhere. By everywhere I mean where ever the technology exists. Manoeuvred use of data structures and are what make the application run effectively & efficiently.

Have you ever thought of programming without using functions? That's what we would be doing if Stack never ever existed.

Now coming to your question.

Think what motivated you the most in technology. Be specific. For me. Gaming it is Try to think of how & which data structures can be used for simple games like snakes and ladders, UNO, ludo etc. Arrive at a solution and ask experts if they have arrived at right solution. If not learn. Be curious. Lot of the times intelligence boils down to curiosity.

%3E If you have learned a new language and can visualize how an application works internally. Then you have succeeded at learning.
You can also improve your knowledge by practicing questions on Data Structures from Hackerank, Codechef and many other websites.

Please up vote. Thankyou.

David Brower · Answer

It’s used for two things.

1. Access to the contents of a file as region of memory which can be more effective than using explicit i/o operations (read/write etc.).
2. Creating shared memory between processes, with a filename as the “key” and using something like /tmp or some other tmpfs as the backing file system.
Very ambitious people will use mmap as backing store and shared memory across processes at the same time, but can be very challenging to syncronize. It’ll become more popular when Optane-like persistent memory is widely available and can be used with load/store into the mmapped region.

John Patek · Answer

There is a universal answer to this universal question:

Q: Can I do (something from C) in C++?

A: Yes, but you probably shouldn’t.

C++ is a superset of C, meaning it supports everything from C, but it has its own unique features not provided by C. One of those features is data structures. C only provides structs and unions, which are not useful for handling a collection of data. The C++ standard library has a variety of “containers” available, such as lists and vectors. In addition, it also has an extensive set of algorithms that can be customized and applied to data that is held in different container classes.

If it’s for a school or personal learning project and you want to create C data structures to use in C++ code, it can work. But if this is a serious project, you are creating unnecessary work for yourself.

Ken Gregg · Answer

If you want to be a professional software developer, you will need to learn how data structures (and the algorithms that operate on them) are actually implemented, without the assistance of canned libraries of data structure containers and algorithms.

Then, you’ll have an understanding of what’s actually going on, how to choose and use the most appropriate containers and algorithms, etc. when you use canned libraries. You’ll have a more accurate mental model, and you’ll be more adept at using available libraries.

I recommend working through Mastering Algorithms with C, implementing as many data structures and algorithms as possible from scratch, debugging them, experimenting with them, etc. This is the way to learn how they really work, by implementing them without the help of canned libraries.

Ray Gardener · Answer

The STL (or now the C++ standard library) is meant to provide best-in-class algorithms for common tasks, or at least those with reasonably good performance for most use cases. Basically, if a better algorithm existed, it would find its way into the library. So for developers, it's impractical to spend time writing code to do what is already available; the odds that they can outperform the stdlib are too small. In fact, I would argue that the standard library should be much larger; devs are still writing too much code at the application level.

The other significant advantage is having a common v

The other significant advantage is having a common vocabulary. If you're on a team and someone says "we'll use a vector here and a map there", it's convenient that everyone knows what that means.

Anonymous · Answer

From the operating system, and the operating system decides how to oblige.

When a computer boots, the first program that gets to execute has absolute access to all the memory. It can do whatever it wants, with whatever region of the memory it wants.

Fortunately, the first program is the operating system (unless you have a rootkit virus), and as soon as the OS boots, it marks all memory as protected. Protected memory is set in hardware, i.e., the page table sets which pages can be read, which ones can be written and which ones cannot. So initially OS locks all pages, and since it is the first program, itself has no problem accessing anything.

Whenever you run a program via the OS, the system first unlocks a few pages, loads the program there, and starts executing it. If this program now tries to access any memory outside these initial pages, it will cause a page fault error, caused by the CPU and handled by the OS. The OS usually closes this program for bad behavior (you see a segmentation fault error on screen).

Well behaved programs on the other hand, if need access to other memory, be it for their own usage, or to inspect memory of other programs, nicely ask the OS. The OS decides exactly what to do. For example, to access memory of other programs, the OS asks the user to give this program administrative privileges (the dimmed out verification dialog in Windows), and once granted, lets it read other memory.

mmap is the system call programs need to call when they want to grab extra pages of memory to use as their own. The OS either grants them these pages (often) or rejects the request (rarely, e.g., memory is full). Before granting however, the OS marks those particular pages as read/writable, so that the program can access them.

Now comes the tricky part. The OS rapidly switches between programs and runs each for a short while (1-10 miliseconds), to make it appear that they are running in parallel. Every time the OS switches between programs, it marks all pages as inaccessible and then marks pages of that particular program as accessible. That’s how OS protects program memories from each other, and that’s one of the reasons switching between programs is expensive.

Pablo Fuente Salas · Answer

You simply cannot do that.

Why? because once you requested an array that array has fixed size.

if you later add another array, you cannot use the first array and just ask for more on the same

and you need to be changing from one and the other which means, is no longer just one array

also if you try to use the second you have no info of the first unless, you actually copy all of it

which needs a LOT of time to copy all the old array into the new and when freeing the old one, it fragments memory. (because the first array needs to be active at the same time as the second).

the best way to do that is to know how much you will use and request it just once.

if not array are not the best idea.

Kurt Guntheroth · Answer

The STL portion of the C++ standard library is broadly used in industry. The STL provides flexible and fully-debugged algorithms and data structures that cover a wide variety of needs.

Certain industries cannot adopt the STL, either because of performance limitations, or because STL data structures allocate dynamic variables, which is forbidden by the most restrictive coding standards in the automotive and aerospace industries.

Chris Reid · Answer

STL containers are distributed as header-only templates. So, Yes, it is quite possible, because you have the source for the templates available. The STL containers are compiled as source code every time from the source code generated from the template, but with all the types filled in.

That being said, it is highly unlikely to be easy to successfully alter any of the STL containers significantly from the inside, because they are very compact and have very little leeway for change in their basic function.

A much more successful strategy would be to create composite classes that adds the functionality you desire while containing the STL class itself, unmodified. If there is something the container does not already do, such as split itself in to two parts, provide some kind of self-modification or compaction, etc., then it is better to create a class around it the implements those functions.

Joseph Newcomer · Answer

Writing C++ programs.

Or Java programs, C# programs, Python programs, FORTRAN programs, or any other language. Data structures are the same thing in all languages. Only the syntax varies.