Deleting large hashmaps with millions of strings on one thread affects performance on another thread

Question

So I have this C++ program that basically parses giant dataset files and load contents into hashmap in memory (this part is being throttled in the main thread, so it never goes out of its way to take up giant chunk of time). And when that is done I flipped pointer to the new memory location, and call delete on the old one. Other than that the program is doing incoming request matching by looking up content in those in memory map (on main thread). Suppose those giant maps are wrapped in Evaluator class:

Evaluator* oldEvaluator = mEvaluator;
Evaluator* newEvaluator = parseDataSet();
mEvaluator = newEvaluator;
delete oldEvaluator;

//And then on request processing:
mEvaluator.lookup(request)

The map can contain millions of string objects as keys. They're regular strings that could be request attributes like ip, UserAgent, etc but each is a string object inserted into the STL unordered_map.

The dataset is periodically updated but most of the time the program is just doing request attribute matching against the dataset in memory, and it's fine and efficient and no errors, except when bulk consumption of the new dataset happen. The alternative way of consuming this large dataset is to use streaming, but that's a relatively longer term solutions.

It used to be a single threaded program using event driven model but every time a complete new set is placed and destruction is called, it took too long to delete the whole thing and hence blocking the request processing.

So I put the deletion of such map onto a separate thread. Problem is while now the deletion and request processing appears to happen simultaneously I can see very visible, drastic slowdown on request processing thread.

Of course there are other processes running on the host and I do expect the 2 threads to compete for CPU cycles. But I didn't expect to see a drastic slow down on request matching thread. On average, a request should be processed 500us level but while the deletion thread was running it got as slow as 5ms. With sometimes cpu interrupts the matching thread (because it took way too long) it can go as long as 50ms, or 120ms, etc. In extreme cases a request could be taken the entire 1000ms to be processed, which is about the time the whole data structure deletion takes on another thread.

What is the best way to know the root cause of such slow down? Is it more of a CPU or memory bandwidth bottleneck? I was imagining as long as I put it on a separate thread I wouldn't care how slow it goes cos it has to delete string objects one by one after all, so I didn't expect it to affect the other thread...

EDIT: Thanks to couple comments/answers already seem to point out several possible causes:

1. Memory fragmentation. Because less frequently visited string is stored in more expensive memory locations (so cache miss), or because it's stored in unordered_map with many pointers, or because system is doing memory compacting while deleting holes all over the place? But why exactly is this affecting slowness in another thread?
2. One comment mentioned it's heap contention due to thread-safe locking? So the entire heap for this program locks down because one thread is busy deleting holes that prevents another's access of heap memory? Just to clarify, the program deliberately never allocates stuff and frees others at the same time, and it only has 2 threads, one dedicated for just deletion.

So what should I do then? I tried Jemalloc though not sure I use it entirely correctly --- it seems including -ljemalloc in linker line just magically replaces libc's malloc? I tried, with no performance difference but I could be using it wrong. My program doesn't do any explicit malloc, everything is new with unknown size in advance, and hooked up together with pointers and STL maps.

And also all strings stored in Key are specifically used for quick lookup so they can't be stored in vector with index even though that would make contiguous memory space, it will be horrible to locate them. So,

1. How can I find for sure the above 2 memory issues are the cause (any tools/metrics?)
2. What can I do to fix it without changing my consumption model to streaming? Assuming the root causes were the above 2, seems like I should do either/both 2 things: 1) allocate all my STL maps along with the objects all from one pool? How do I do that? 2) reduce heap contention (I don't know if Jemalloc solves either of this in my case)

Answer 1

It might be worthwhile to store just a single std::string for all your data combined, and use std::string_view in the map. This eliminates mutex contention as there's only one memory allocation needed. string_view has a trivial destructor so you don't need a thread for that.

I've successfully used this technique before to speed up a program by 2500%, but that was also because this technique reduced the total memory usage.

Answer 2

You can try using a std::vector for storing the memory. std::vector elements are stored contiguously, so it will reduce cache miss (see What is a "cache-friendly" code?)

So you will have a map<???,size_t> instead of map<???,std::string> you will have one more indirection to get your string (wich means an extra run time cost) but it allow you to iterate on all strings with way less cache-miss.

Answer 3

It would be great if you recreate the problem you are encountering with a MVCE and show it: you know, many times the problem you are thinking is your problem... is not the problem.

How can I find for sure the above 2 memory issues are the cause (any tools/metrics?)

Given the information here I would suggest to use a profiler - gprof (compile with -g -pg) being the basic one. If you have the Intel compiler available you can use vtune.

There is a free version of vtune but I have personally used the commercial version only.

Besides from this you can insert timings in your code: from the textual description, it's not clear whether the time to populate the map is comparable to the time needed to erase it, or it grows consistently when run concurrently. I would start with if. Note that the current version of malloc() is greatly optimized for concurrency too (is this Linux? - add a tag to the question please).

For sure when you erase the map there are millions of free()'s called by std::~string() - but you need to be sure that this is the problem or not: you can use a better approach (many mentioned in the answers/comments) or a custom allocator backed by a huge memory block that you create/destroy as a single unit.

If you provide a MVCE as a starting point, I or others will be able to provie a consistent answer (this is not an answer, yet - but too long to be a comment)

Just to clarify, the program deliberately never allocates stuff and frees others at the same time, and it only has 2 threads, one dedicated for just deletion.

Keep in mind that each string in the map needs one (ore more) new and one delete (based on malloc() and free() respectively), being the strings either in the keys or in the values.

What do you have in the "values" of the map?

Since you have a map<string,<set<int>> you have many allocations: Every time you perform a map[string].insert(val) of a new key, your code implicitly call malloc() for both the string and the set. Even if the key is in the map already, a new int in the set require a new node in the set to be allocated.

So you have really many allocations while building the structure: your memory is very fragmented on one side, and your code seems really "malloc intensive", that could in principle lead to the memory calls to starve.

Multithreaded memory allocations/deallocations

One peculiarity of modern memory subsystems, is that thay are optimized for multi-core systems: when one thread allocates memory on one core, there is not a global lock, but a thread-local or core-local lock for a thread-local pool.

This means that when one thread needs to free the memory allocated by another one, there is a non-local (slower) lock involved.

This means that the best approach is that each thread allocates/deallocates its own memory. Said that in principle you can optimize a lot your code with data structures that require less malloc/free interactions, your code will be more local, with respect to memory allocations, if you let each thread:

• get one block of data
• build the map<string,<set<int>>
• free it

And you have two threads that, repeatedly perform this task.

NOTE: you need enoguht RAM to handle concurrent evaluators, but now already you are using 2 of them concurrently loaded with a double buffering scheme (one filling, one cleaning). Are you sure your system is not swapping because of RAM exahustion?

Furthermore, this approach is scalable: you can use as many threads as you want. In your approach you were limited to 2 threads - one building the structure, one destorying it.

Optimizing

Without a MVCE it's a hard task to give directions. Just ideas that you only know whether can be applied at now:

• replace the set with sorted vector, reserved at creation time
• replace the map keys with a flat vector of equally spaced, sorted strings
• store the string keys sequentially in a flat vector, add hashes to keep track of the keys of the map. Add an hash-map to keep track of the ordering of the strings in the vector.

Answer 4

So thanks to all the answers and comments given, I wasn't able to pick out a best due to partly the problem itself being vague and no one single answer really covered everything. But I did learn a lot from these answers and hence upvoted most of them. Here's what I found after various experiments, that the major issues are:

1. The reason slow operation on deletion thread affects another. Given it doesn't do malloc/dealloc concurrently on both threads, there should not be any heap contentions, nor is general CPU or available memory at bottleneck, the only plausible explanation left is memory bandwidth exhaustion. I found this answer to another post says: it's generally possible for a single core to saturate the memory bus if memory access is all it does. All my deletion thread does is traverse a giant map and delete each element in it, so it's conceivable it saturates memory bus so the other thread, which is doing both memory access and other computation, drastically slows down. From here on I'll focus on various reasons this deletion can be slow

2. The map is giant, with millions of elements and hundreds of megabytes in size. Deleting every one of them requires accessing them first and clearly very few can even fit in L1/L2/L3 cache. So there's a ton of cache miss and fetch from RAM.

3. As couple answers/comments mentioned here, I store std::string objects in map. Each allocated with its own space and has to be fetched and deleted one by one. The advise from MSalters improves performance much better by storing string_view in map, while storing actual byte content of each string, in a contiguous memory block pre-allocated. Now the deletion of a million objects in the map becomes almost trivial destructions of string_view objects which are merely pointers, and the destruction of all string contents are destruction of that pre-allocated block.

4. I didn't mention in some other parts of the program I also store other C++ objects in other maps. And they're likewise problematic. Similar "flattening" of such C++ objects are necessary, albeit harder to do without ready-made classes like string_view. The idea is if we can store as much as primitive types and pointers as we can, and put all content (most of them can be boiled down to strings) in contiguous bytebuffers. Making everything trivial to destroy is the goal.

5. Lastly, it turns out the map container itself can be pretty costly to destroy particularly when it's big. For Node-based std containers traversing and deleting each node handle takes time. What I found is alternative implementations of truly flat hashmap, will make the deletion a lot faster. Examples of such map include Abseil flat_hash_map and this blogger's flat_hash_map. Note that they're both true hash_maps even though they're flat. Boost's flat_map also can be deleted very fast but it's not a real hashMap, it's backed by strictly ordered vector which makes insertion (when my input is not ordered) extremely slow.

Answer 5

this will be a lengthy answer because your question is very complicated.

Read procedure

When you read something you start to allocate memory into you app. Now this is ok in a normal case when you do not need performance there is where the problems begin.

STL maps are red-black trees so they have a lot of pointers, which means each element is /was allocated individually, this creates a situation that your memory space is very fragmented and it is difficult for the system to deallocate the elements efficiently. Reason: the system has to follow the pointers.

The appropriate container

STL map explained: Why is std::map implemented as a red-black tree?

Here is a basic discussion about the behavior of the map memory management. https://bytes.com/topic/c/answers/763319-stl-map-memory-management

Acording to your description you read a massive file that you then sequentially stream to someone. My question here is can dis data be stored as a STL Pair into continuous memory, since you say you have to stream it?

Do you have to search for elements in there ? If yes then you should find out how often or in which frequency, this answer will tell you if the STL map is a good container since it is efficient in searching activities.

Now in this link there a re some benchmarks about pointer referenced containers and continuous containers. https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

The idea is that you use the appropriate container so you have the right behavior of the memory management.

Is there any advantage of using map over unordered_map in case of trivial keys? Here is an alternative to your map that could be a cheap fast hack until you develop a more precise solution.

Memory management

My question in your problem is can you clear and reuse your container? Since freeing containers is expensive business.

You could you use a ring buffer of STL maps where: one is read -> one ready -> one written That would be very efficient and could give you the edge since you would not have to free any buffers, just clear after usage.

Edit: Here is an answer about memory fragmentation that happens during frequent deletes in a container. What is memory fragmentation?

You problem is that you use strings, they can extend the memory but underneath they are mallocs of char. Now I would not delete stuff but flag it unused or something else.

One tiny thing that might help if you use string reserve function when you create your strings. Then you can say 128, which means 128 bytes and will eat a bit of memory but will make fragmentation handling easier, and reallocation behavior of the string less difficult.

Now this might also be totally useless. You need to profile your app to see what is going on best way perf and Flamgraphs if you are on Linux.