5 ms·
In the grand tradition of HN i haven't read the article (but in my defense it is blocked by work's firewall). Still, if he claims that unordered_map has issues
by gpderetta 8y ago
In the grand tradition of HN i haven't read the article (but in my defense it is blocked by work's firewall). Still, if he claims that unordered_map has issues he is not alone. It is well known that the standard requirements preclude a more efficient implementation.
And the issue with vector value initializing it's elements is also well known and programmers have been asking for a solution (more user friendly than a custom allocator) for a long time.
- jcelerier 8y agoI don't understand the problems. Want a better hash map ? Use whatever makes your day here : https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.... ; they are all header-only just like the standard library's. Want a vector that does not initialize its elements ? Ask and thou shalt receive: https://github.com/aguinet/pector https://github.com/aguinet/pector The whole point of C++ is to make it easy for people to write generic libraries beyond de standard base provided by the stdlib. So why won't you use those ?
- gpderetta 8y agoOh, I'm in violent agreement. The single biggest contribution of the STL is its set of concepts more than the actual implementations. If you do not like the specific tradeoffs for a container or algo implementation, you can swap it for a different implementation often without code changes. I.e. you do not need to remove abstraction, you just swap it for a different one. Still it is fair to critique the specific tradeoff done by the standard library.
- stochastic_monk 8y agoIt’s the linear chaining effectively required by the standard. I had an application years ago which was 10x as fast after dropping in khash over unordered_map.
- gpderetta 8y agoIIRC that's because of the iterator and address invalidation requirements that effectively require an node based implementation. But if your code does not rely on these guarantees then, as you suggest, you can swap it with a different implementation with the same interface. You do not have to pay for what you do not use.
- deleted 8y ago[deleted]
- bluescarni 8y agoI wonder what the reaction would have been if he/she had written a blog post explaining how moving from list to numpy.array for storing numerical data in Python resulted in massive performance benefits. You gotta admit the situation is kinda similar. What is unfriendly about custom allocators? Note that in this specific case you don't need to write any allocation function, you just have to re-implement the construct() function with something that does not value-initialises if no construction arguments are provided.
- twtw 8y ago> You gotta admit the situation is kinda similar. I disagree. 1. Everybody knows Python is a scripting language, and trying to do heavy computation without handing it off to a library is going to be slow. 2. A vector is the de facto data structure for this in c++. In Python, numpy is effectively the de facto approach for math.
- bluescarni 8y agoSorry but I think this is still an apt analogy. 1. "Everybody" knows that unordered sets/maps in C++ must de-facto use chaining due to the requirements imposed by the standard. 2. numpy.array is not part of the Python standard library. It is an extra component you still need to install separately. As someone who deals regularly with novice Python users (often coming from Matlab & the likes), one of the very first points of pain/confusion is the fact that I need to teach/convince them not to use the facilities of the core language to represent "vectors".
- gpderetta 8y agoChanging the allocator changes the type of the vector, which has ABI/API implications, especially if the vector type is not under your control. Also, IMHO tying allocation with initialization in the allocator concept is not one of C++ brightest moments. There have been continuous talks about adding an unsafe_push_back and an unsafe resize for these and other reasons.
- stochastic_monk 8y ago
- CoolGuySteve 8y agoIf you're rapidly removing and adding, a simple fix for unordered_map is to add your own stack allocator. That way the memory you touch for it's lists is nearly always hot. The same technique vastly improves map and set too.