7 ms·
Benchmarks of Cache-Friendly Data Structures in C++
- kccqzy 8y agoHow does DenseMap compare to, say hashbrown (in Rust) or SwissTable (in C++) by Google?
- s3cur3 8y agoI don't have the know-how to write a Rust comparison (I'd happily accept a pull request from someone who does!), but I can take a to-do to add SwissTable benchmarks. :)
- saagarjha 8y ago> And unlike with vectors, I don’t know that I’ve ever come across code that retained map iterators… I've done this once. The thing I was trying to do was have multiple threads write to a std::unordered_map in such a way that each thread would write to its allocated "bucket" and nothing else (roughly, each thread would "own" map[thread_id] as a somewhat convoluted "thread local storage" which would then be collected and operated on at some point in the future from the "master" thread). It turns out that to the only way to actually do this in a standards-compliant way is to grab an iterator pointing to map.find(thread_id) prior to starting and use for subsequent modifications of the value, since using the subscript operator is apparently not guaranteed to be thread safe for associative containers.
- gpderetta 8y agoThe subscript operator can modify the map if the key if the is not present, so it is not constitute and thus formally not thread safe even if you are sure the key is always present. At and find are always constitute so you can use those instead; no need to cache iterators.
- saagarjha 8y ago> The subscript operator can modify the map if the key if the is not present, so it is not constitute and thus formally not thread safe even if you are sure the key is always present. Yeah, I know why it is unsafe in general, but I don't see why the C++ standard can't specify that operations that don't invalidate iterators are legal to perform in a concurrent manner provided they touch disjoint memory locations (for associative containers, subscripting is defined to be one such operator, as long as rehashing does not occur like in this case). > At and find are always constitute so you can use those instead; no need to cache iterators. Now that you mention it, I could have just called find every time. I guess I'm too used to it being O(n) for other collections and avoided it somewhat irrationally ;)
- gpderetta 8y agoThe wording could be changed. I guess it is just an issue of the committee only having ago items time; as there are alternatives here getting the correct wording right is not a priority so the fallback to const/non-cons thread safety guarantees is sufficient.
- quietbritishjim 8y agoIf you didn't like caching the map iterator, you could have cached the pointer to the value object instead i.e. Foo* cached_value = &mymap[this_thread_id]. Although caching the map iterator sounds perfectly fine to me.
- HappySweeney 8y agoIsn't the whole point of iterators to prevent the above strategy from crashing your program when the map is moved to another region of memory?
- quietbritishjim 8y agoI'm not exactly sure what you mean by "the map is moved to another region of memory", but a pointer to the value object in a map entry is safe (or unsafe) in exactly the same situations as an iterator into the map. Under the hood, the iterator is likely to be a pointer to a tree node struct that contains the key and value objects (along with pointers to other relevant nodes).
- rwbt 8y agoThe std::deque is also another useful 'hybrid' container that performs close to std::vector or better in some cases when you need to 'grow' the container without reallocating memory so many times. But the only good cache friendly implementation seems to be in clang libc++ (memory is allocated in 4KiB blocks). MSVC's deque implementation is horrible (8 byte blocks) and GCC's is also not that great (512 byte blocks).
- svantana 8y ago8 bytes??? Are you sure you don't mean 8 * sizeof(class)? That's just ridiculous. Regardless it would be nice if one could specify the block size as an argument. I suppose I could write my own allocator, but it's just too much hassle for such a simple thing as storage.
- rwbt 8y agoIf I remember correctly, in MSVC implementation if sizeof(T) is greater than 8 bytes then each 'block' is just one element (also blocks aren't contiguous). So effectively, MSVC implementation is useless. Boost does have a a deque container where you can specify the block size using type traits, but from my experience boost's deque wasn't such a good implementation performance wise. But Clang's libc++ implementation is very good performance wise and even beat std::vector in some cases.
- s3cur3 8y agoWorse, this is not on the table to be fixed any time soon in MSVC, because the change would break ABI compatibility. Every time someone says "just use a custom allocator," I sigh inside... it's so much overhead that almost no one does it, and even fewer do it correctly. :(
- jstimpfle 8y ago> llvm::SmallVector [...] this class preallocates some amount of data (the actual size of which is configurable via a template parameter) locally on the stack, and only performs a (slow!) heap allocation if the container grows beyond that size. Because malloc is slow, and traversing a pointer to get to your data is slow, the SSO heap storage is a double-win. But you need to "traverse" a pointer for a stack-allocated array just as well! So it's mainly that in some cases this class helps forgo a malloc, which I am not sure is that much of win, especially given that this implementation is another class that requires more (and more complicated!) object code... What I think might be better in many situations is preallocating the dynamic array so that it doesn't need to be preallocated each time the function is called. The preallocated array can be a function parameter (or object member, for OOP weenies :>), or simply a global variable.
- forrestthewoods 8y ago> But you need to "traverse" a pointer for a stack-allocated array just as well! No. Iterating a small stack array is much faster than iterating a heap array. Instead of "traverse" the author means you have to follow the pointer out to main memory to read the data. Another term they might have used is "fetch".
- jstimpfle 8y ago> Instead of "traverse" the author means you have to follow the pointer out to main memory to read the data. Another term they might have used is "fetch". No, I got that. But stack memory is main memory as well, and it is accessed through a pointer (in this case the stack pointer) just like heap memory. That is, unless the stack memory is not really stack memory, but optimized by the compiler to be register-only. Which is mostly not possible for stack-allocated arrays (when they are indexed with runtime indices, or when they are simply too large). It's true that stack memory is (almost) always in the cache, which is why stack memory is considered fast. But couldn't that be mostly true for temporary heap storage as well?
- forrestthewoods 8y ago
- wmu 8y agoI'd love to see also comparison with B-trees (https://code.google.com/archive/p/cpp-btree/ https://code.google.com/archive/p/cpp-btree/). In my tests done a few years ago this implementation was faster than std::map. And my guess is the reason of it is better use of cache.
- s3cur3 8y agoHm, I'll look into it... :)
- jstimpfle 8y agostd::map is usually implemented as a Red-black tree. Which is basically a B-tree with branching factor 2. This is less cache friendly than higher branching factors, so it's entirely expected to be slower than B-trees. On the upside, it offers stable pointers which higher branching factors cannot offer.
- pjc50 8y agoPeople like to talk about C++ giving complete control over memory layout, but there's one very important cache-relevant technique that I've not seen done transparently: "column based storage". That is, if you have class foo { int x, y, z; }, and make an array or vector of them, then they will normally be laid out in that order. For locality, you might want to have all X be together - ie, three separate arrays of X, Y and Z.
- zozbot123 8y agoTo be fair, the same is true of Rust. The issue is that with column-based storage you can't have pointers/references to individual structs within the vector. You need to use indexes.
- jgtrosh 8y agoThis is just the old array of structs vs struct of arrays trade-off, right? This is true of pretty much any programming language's low level data structures.
- mamcx 8y agoTell me to me. I try for several months to build a way around this on rust (ie: Have a generic interface to both columnar and row-oriented layout and "just" switch to optimized operations later). I think is impossible. The closest thing is use a NDArray and pick a winner/default layout... that is row-oriented, despite my intention to be columnar first, and later develop an alternate, complete rewrite, for support columnar.
- AstralStorm 8y agoThe thing is, in modern C++ you can fake a wrapper to access it like a pointer or reference. Of course it will not be high performance, but it can be done. (E .g. Eigen library.)
- smitherfield 8y agoWhy wouldn't an implementation along these lines be performant? template<typename... Ts> class SoA : public tuple<vector<Ts>...> { // ... template<size_t... Is> tuple<Ts&...> subscript(size_t i, index_sequence<Is...>) { return {get<Is>(*this)[i]...}; } public: // ... auto operator[](size_t i) { return subscript(i, index_sequence_for<Ts...>{}); } };
- LHxB 8y agoMaybe in a logarithmic plot this would look differently, but it seems to me that std::vector performs quite well in particular for few elements. So why would I bother with smallVector if simple std::vector is on par in their (supposed) prime discipline?
- orbifold 8y agoBecause you are developing LLVM or a similar performance critical project with lots of small vectors.
- s3cur3 8y agoI'm in games, and we really do have lots of vectors of maybe 8 or so elements. The small wins add up across the entire codebase.
- shereadsthenews 8y agoVector can be slow if you create and destroy them a lot, since they allocate. You can work around to some extent by providing a custom allocator, but using something like SmallVector or absl::InlinedVector can be much faster when the N is known.
- AstralStorm 8y agoOr if it's fully static size, just use std::array. You'd be surprised how often people use known static size or static max size vectors instead.
- shereadsthenews 8y agoSure. Horses for courses. Array is great when you have exactly N. InlinedVector is handy when you have <N 99% of the time.
- smitherfield 8y agoYeah, that's one of my biggest pet peeves when looking at other people's code (along with unnecessary dynamic allocations in general). One of the reasons I perhaps irrationally still prefer C++ to Rust is the pervasive use of dynamic arrays of known static size in the latter's documentation, and how it makes fixed-size arrays much less ergonomic to use than dynamic arrays.
- usefulcat 8y ago> Lookup in the ArrayMap is shockingly slow at large data sizes—again, I don’t have a good explanation for why this is. Probably because it's doing a binary search over a large array? I wouldn't expect that to be particularly fast with large arrays, since large array + binary search == lots of cache misses. There is a way (the name escapes me unfortunately) to order the items of the array such that for N items, the item that would be at index N/2 in a sorted array is at index 0, then the items that would be at N/4 and 3N/4 are at indexes 1 and 2, and so on which of course is much more cache-friendly when doing a binary search.
- BeeOnRope 8y agoThe name is Eytzinger layout.
- usefulcat 8y agoExcellent, thanks!
- deleted 8y ago[deleted]
- s3cur3 8y agoRight... this result is one of those examples of why you don't guess, you benchmark, because my intuition is that binary search should be "really fast." Clearly though the cache misses hurt a lot more than my intuitions capture.
- lostmsu 8y agoAny idea why is it not using B-trees?
- s3cur3 8y agoOh, the sorted array-backed "map" isn't using B-trees because I wanted it as a comparison point (to see how the LLVM containers fare against the old "just use a vector" advice). So the ArrayMap isn't production-ready or anything... it's intended to give a baseline against which to compare what would happen if you wrote your own dead-simple map replacement with the hope of improving perf.
- deleted 8y ago[deleted]