Effortless Performance Improvements in C++: std:unordered_map | Hacker News Reader

Effortless Performance Improvements in C++: std:unordered_map

julien.jorge.st

120 pointsjandeboevrie139 comments

If you look at part 1 [0], it is pretty clear that std::map is not THE major bottle neck. The whole program is pretty slow.

The issues I see are: a lot of string copying instead of string views, splitting strings into vectors rather than splitting on demand, replacing on the same string repeatedly and collecting into a string before adding it to another string. It seems like their benchmark data has a lot of small lines with set and value commands, which would not be majorly hurt by those issues.

The performance of ~20MB/s is REALLY SLOW for string processing in cpp. A fast but not super optimized c++ program should be getting in the ballpark of 500MB/s.

[0]: https://julien.jorge.st/posts/en/effortless-performance-impr...

Clearly a veteran of C++ in particular or the “zero-cost abstraction” cluster of languages in general is not going to miss a bunch of needless allocations etc. in a setting where performance matters a lot and I basically agree about the high notes of where you’d start to tune this up.

But the author is clearly a highly-motivated intermediate C++ user who is taking time to share some key lessons and anyone who keeps that up for long won’t be intermediate for long!

So it’s still a cool blog IMHO :)

Well I'm always surprised how the actual implementation of the stl primitives looks like "C++ cool tricks 101" turned to eleven and I wouldn't be surprised if the ability of compilers to optimize that was not great

Eh, the folks writing the standard library definitely work adjacent to the folks doing the compiler in C++ for sure and I think Rust and stuff too. Both gcc and clang for example ship with co-designed standard libraries.

It’s backwards compatibility that kills them on performance which is why the 900-IQ C++ shops like Google etc. just go their own way on the hash table because it’s worth it to them to do the extra work.

It's not just backwards compat, it's all the crazy guarantees that the stdlib has to make. Most code doesn't have strong exception guarantees... the stdlib generally speaking does. It also has to deal with all sorts of silly things without breaking like people overloading operator,() and still expecting things to work without issue. They really are a case study in getting decent performance in most cases out of exceptionally defensively written code.

Their speedup from the initial code to the end of the map blogpost is ~5%. In their repo, they have a much better version that presumably there will eventually be blogposts leading up to. That version is approximately twice as fast as their initial version.

I worked on optimizing that version for a little while. The result is a version which takes 30% of the time of the original and a little worse than twice as fast as the best in the repo. That's still disappointingly slow to me, but I'm not great at c++ so I don't really want to take the time to try to improve it further.

You have a lot of good points that will indeed be addressed in the next posts :)

The operations on the strings are subtly expensive and I was expecting to see them above the accesses to the maps in the perf report. Now they were not and I address the problems in the order of this report, so we will have to wait a bit to discuss them. The intent is also to unroll a scenario of optimization for the reader: measure to get insight, try something, measure again, decide.

If you have the time and the motivation I would love to see a fast but not super optimized version of this program. I tried to keep using the standard library and not going into cryptic code (i.e. trying to keep the code clear for an average programmer), and I stopped when the performance gain became very small, but I am pretty sure we can get better performance if we push further.

Going step by step, slowly tackling the issues while also showing the reason behind why it is optimized, is a great way to teach. Congrats on mentorship skills!

In spite of some technically incorrect statements this is a generally very useful observation and not just in C++: it’s easy to pay for traversal properties you don’t need in an associative data structure. Hash tables and red black trees shine in different applications :)

Still pretty low-effort but slightly higher cost and benefit is to switch to more modern data structures that have to break a little backwards compatibility to get big wins. Things like Folly’s F14 and Abseil’s collections (Abseil has both faster hash tables and faster tree-style maps).

I think languages like Rust with a little less backwards compatibility burden are shipping with cache-aware and SIMD-exploiting data structures “out of the box” these days, but but my knowledge of e.g. Rust stops short of “read the standard library a bunch of times” so check with someone who has :)

Rust promises its language and standard library have full backward compatibility however that promise only refers to the actual documented API behaviour and this is intentionally narrow in places where it matters for performance.

Thus for example, the HashMap in Rust 1.0 is different from the HashMap shipped in any recent Rust, but they both implement the API described in the documentation, the new one is just much faster because it's actually HashBrown, a re-implementation in Rust of Google's Swiss Tables C++ hash map.

Hyrum's Law means that to some extent even though the defined API is narrow, people will write Rust code, by mistake or on purpose which depends on internals that were never guaranteed. For example, sort_unstable_by() is, as its name says, an unstable sort, you should not assume that it leaves ['a', 'A', 'B', 'b'] in the same order when you provide a case-insensitive comparison operator - you should have used sort_by() if you could not accept instability in your sort results.

Rust gets to measure the impact of Hyrum's Law and re-consider potential changes which have large real impact because it does Crater Runs, which compile and test large volumes of Rust software from the crates.io package site and GitHub, with to-be-released Rust versions. If you made a change that you thought was basically a typographical fix, and it's technically not a breaking change by Rust's rules but it blew up 15000 widely used crates, you need to think harder about whether that's OK and most likely revert your change.

C++ has no analogue of the Crater Run as of yet, and it offers a lot of needlessly broad APIs which lock it into choices that are terrible because it promised something that in hindsight nobody cares about, but now you daren't change that.

The ABI promises in real world C++ implementations make this even worse. Rust's Mutex<Option<CompactString>> [[CompactString is a 3rd party library type]] is significantly smaller than a std::mutex on most popular C++ platforms, and yet std::mutex is literally just a mutex, whereas Mutex<Option<CompactString>> is a mutex protecting an optional Small String Optimized string containing up to 24 bytes of UTF-8 encoded string all in line in your smaller data type.

> C++ has no analogue of the Crater Run as of yet...

It does in the form of large organizations with large codebases that try out candidate releases and file bug reports.

It's not managed by a central "C++ team" as such if that's what you mean, but there are N independent C++ implementations. At some point we're comparing organizational structure and not technology outcomes.

It's like Continuous Integration versus previous practices of "Jim has a working checkout, and I think he built the release version last time, ask Jim to make you a fresh release CD, remind him to switch off the debug symbols though. Oh also I think we're over 650MB now, so he might need to change settings in the CD burner app".

It's not that the previous practices didn't work, more or less, it's that they were manual and so you couldn't really rely on them. CI is categorically better, despite being in some sense just an automation of what should be existing practice.

Except in this case we're literally talking about established CI processes. They're just not triggered by the "C++ contributor" because those don't exist as such. We have GCC contributors, Clang contributors, etc. Periodically a batch of those contributions get marked for testing and they get pushed through various CI processes and bug reports or even PRs get generated.

The C++ compiler vendors I am aware of also have access to nontrivial C++ codebases that give them access to these sorts of "see what broke" speculative build jobs: Red Hat has RHEL and CentOS repositories, Microsoft has the presumably massive Microsoft codebases, everyone has access to vcpkg, and so on.

I'll also note that this is just normal for sufficiently popular systems languages. If Rust as successful as it seems like it will be, there will some day be far more code outside of public crates than inside them.

Anyway, there are some differences for sure, but it's not night and day they way you describe it.

> The ABI promises in real world C++ implementations make this even worse.

There are legitimate use cases that require good performance and some ABI stability guarantees. Like various kinds of closed-source client libraries.

Rust doesn't have to serve those use cases, of course. But "stable ABI is bad" is a very broad statement.

The real problem here is the lack of packaging solutions for systems programming, which are frequently multi-language in some way. And in the case of closed-source use cases, that would look like binary packages. If we had quality dependency management, we would have different options for different use cases and standard libraries could focus on 90% use cases instead of 99.99% ones. Being all things to all users isn't a winning strategy.

Can you expand on the technically incorrect statements part? If I can fix the post I would love to do it :)

I find it so strange and unintuitive that a table lookup in STL can actually amend the table to include the key. I don't know of another library that works like that.

    std::map<std::string, std::string> m;
    (void) m["nonexistent"];
    m.size(); // => 1

Is there a historic reason for this strange specification? Or is it just a concession make the "operator=" sugar work better?

If you try to implement your own map you’ll naturally end up with this quirk.

operator[] returns a reference to a slot in the map which can be read from or assigned to. Since the reference must be valid, you better have allocated a slot in the map that can be written to if the value didn’t exist.

I don't think it's _that_ unnatural to just return a reference to a dummy value (i.e. have a member T map<T>::dummy and always return that if the key does not exist). Users writing to it/reading from it are on their own; you could even reinitialize it on every such operator[] call.

operator[] is not only used for lookups though, it’s also used for insertions:

    m["nonexistent"] = 1;

This would not work if you return a dummy value.

That's true; thanks! It's 3am and time for bed :-)

This is why I gave up on [] and just use .at now.

Which is perfectly reasonable if you're willing to deal with the performance consequences of exceptions (or crashes).

.find() is the safe way to do map lookup without side effects.

It is a quirk of C++ that element lookup and assignment are forcibly unified like this. Ruby for instance has an operator[]= which could solve the problem.

You could do it in C++ via proxy objects, but are kind of tricky to get right.

They are impossible to get right unless you are OK with things breaking when they get passed to templates. This is why std::vector<bool> is considered a mistake.

C++ really needs an 'operator auto' to properly support proxies :(

"quirk" looks more like "major overlooked detail" to me

I mean, left side expressions and right side expressions are different

Indeed, Rust's HashMap implements Index<&T> but not IndexMut<&T> meaning you can write this:

let salary = salaries["Jim Bob"]; // Note this panics if "Jim Bob" isn't a key in salaries, by analogy to arrays which panic if you do an out-of-bounds array access

However you can't write this, it won't compile:

salaries["Jim Bob"] += 10_000; // No raise for Jim Bob, this does not compile because that's not a mutable reference.

To be fair, you could achieve the same in C++ by only implementing `operator[]() const`.

Huh. Does that do the same thing? I can't figure it out in my head whether this causes all the correct things to fail and everything else to work.

If you only implement operator[]() it should do the same thing as only implementing Index in Rust, thanks to implicit cast conversion. Whether it causes "the correct things to fail and everything else to work" is up to interpretation, as this will give you const references to the array values, which is much less idiomatic in C++ than in rust.

Yeah, I think this probably does what I think ought to happen here, but in the process it probably makes a bunch of reasonable looking C++ not work, and thus would make programmers unhappy which is not a good goal :/

C++ allows you to override the constness of everything internally by defining a member variable as `mutable`.

Unfortunately while C++ does distinguish between things which can appear on the left hand side and right hand side of assignment, the things that can go on the lhs are much broader than in most programming languages. For example, a pretty normal thing to write in C++ is `foo(map) = 1;`, where foo something like `int& foo(std::map<std::string, int>& map) { return map["key"]; }`.

The ability to compute and pass around lvalue references (where "lvalues" are approximately "things that can appear on the lhs of assignment") is a very powerful feature, but also one which causes complexity in all sorts of other places, which is a bit of a theme for C++. One of those complexities is that non-const `operator[]` essentially has to be `operator[]=` even if at this specific call site there's no assignment happening.

C++ could have had const `std::map:::operator[]` throw an exception if the key isn't present, but having const and non-const versions of a function do different things is extremely error-prone and instead you have to use at() if that's what you want.

They're not forcibly unified if you don't use operator overloading. There is a find() and an insert().

I tend to use find() when doing a read only lookup, and operator overloading for writing.

There are two issues with that:

- what is the dummy value? does the value type even have one?

- I don't think index-assignment (or attribute-assignment) is overloadable in C++, so you need `a[b]` to return something which can be assigned to, and proxy values tend to be really wonky (see: `vector<bool>`), so assigning to the result of the indexing would replace the dummy value

This was written at a time when std::option didn't exist. Thus it needed to return T& instead of option<T&>. When std::option was added, they couldn't change the existing interface because of back compat and the lack of a migrator tool (e.g. Swift has major backwards incompatible source changes but they have a tool that will migrate your code fore you). C++ has warts like this all over the place.

optional<T &> is not valid in C++ [1]

[1]: https://en.cppreference.com/w/cpp/utility/optional

Because C++ doesn't have the Guaranteed Niche Optimization C++ optional<T&> would be pretty miserable whereas Rust's Option<&T> is exactly what you want.

In practice C++ APIs where you'd naturally write Option<&T> use pointers and are consequently easier to use wrong, this is an example of Rust actually providing improved safety technology (whereas many commonly identified safety differences like bounds checking in Rust are cultural differences)

C++ could specify that std::optional<T&> is valid and implementations could implement the Guaranteed Niche Optimizations. This is not a theoretical possibility: boost.optional (which std::optional is based on) does exactly that.

The reason std::optional doesn't allow references is because someone in the commitee objected that some users might be confused by the assignment semantics (will assignment rebind or assign through the reference?) and the proposal authors dropped it instead of spending too long discussing pro and cons. It can still be easily re-added if the commitee wants to.

No need to drag the rust in the discussion.

I'm pretty sure you can't express the actual guarantee in C++ because of inadequacy in the design of the C++ type system, which has caused problems elsewhere recently too.

You could easily hack std::optional<T&> specifically - and several people have, not just Boost - however C++ has a long history of "clever" hacked specializations that turn out to be disastrous so that isn't attractive. It's called generic programming for a reason.

The fact that it looks like you might be able to rebind or assign through the reference is a design goof. To the extent that std::optional is just the Boost type with a sticker on, that's a goof by the people behind the Boost type. However, they were hemmed in by inadequate language functionality, WG21 has the option to go fix the language, and they didn't do that, so the blame for that goes to them and not Boost. Having now standardised std::optional with the design goof, there is no attractive route forward.

The correct answer to "someone's" question by the way should be neither and that's the goof in std::optional, assignment to a Maybe type is assignment to the Maybe type you can't assign a Foo to a Maybe<Foo>, imagine if C++ also thought this ought to work for std::vector<int> ...

> I'm pretty sure you can't express the actual guarantee in C++ because of inadequacy in the design of the C++ type system, which has caused problems elsewhere recently too.

Far from being inadequate, it is pretty trivial to do so: https://gcc.godbolt.org/z/n4vK4jeaG .

You still need to special-case references because they are not actual C++ objects and need special handling.

It's not about whether you can implement this hack - obviously numerous people have done that - it's about the type system itself.

Here's a question for you, what is the type of a do expression which just returns from the function you're in ? I mean, it's just an expression, we don't have to actually evaluate it we can ask what the type is... can't we ?

As far as I can see, C++ does not have a suitable type, which is why e.g. some C++ functions end up with a special attribute to signify that they won't actually return. I can see why this type would be unsettling, it's like when the ancient Greeks didn't like zero and so they initially refused to treat it as an integer. The type you want here is the additive identity.

Because the type system doesn't really understand additive identity, it's a struggle to write such a guarantee - not as a hack but in the type system.

I'm sorry, but I have no interest in playing a game of True Scotsman Chases The Goalpost.

Even if I did, I have no idea what you are trying to say.

edit: sorry that was a bit harsh. Can you try to explain what property is C++ missing exactly to implement the Niche optimization? I suspect you are trying to say that C++ lacks proper sum types (which is true), but that's really orthogonal to the optimization.

I don't think it is orthogonal, because it means we have to resort to this hack everywhere and we already know that specialization hacks end badly. Let me briefly explain why I've thought about this pretty hard.

Over in Rust I really want to make BalancedI8, BalancedI16 and so on, types which are exactly the same as the ordinary signed integers of each size, except, their smallest possible value (e.g. i8::MIN ie -128) is gone (so BalancedI8::MIN is -127), leaving them nicely balanced between negative and positive, their abs() method doesn't have a hidden surprise - and of course this offers the smallest possible niche so Option<BalancedI8> fits in a single byte.

I obviously can in some sense do that today and I did -- the types are published, but today I can't use them from stable Rust, these types require a (deliberately permanently unstable) Rust-internal attribute telling the compiler about the niche, and they also can't be safely constructed (obviously I provide a safe function to make one, but you can't just conjure one into existence without calling the function, yes it gets inlined but that's not very ergonomic)

This is not a desirable state of affairs. As usual in Rust, the reason for the perma-unstable feature flag is that there's a germ of an idea of the Right Thing™ and so the eventual removal of the feature flag is predicated on obsoleting the feature by having the Right Thing™ in the language itself, not stabilization of the existing flag. Rust types which provide a niche will some day remove the feature flag and instead be defined using the language in the now-natural way, yet to end users nothing seems to have changed. The backwards incompatible change lives only inside private internals of the standard library so it's fine.

In this case that Right Thing turns out to be Pattern Types. What if we actually just tell the type system what's going on here about which values a type can actually have versus which ones are niches by providing a Pattern for the type. So it knows everywhere in the language that -128 may be a valid i8 but it's not a valid BalancedI8 because the pattern doesn't match.

However, Pattern Types might take quite a while to produce even a basic MVP implementation that can be stabilized, and so for a while I was pushing to get some way to just have what I want stabilized, sooner - without all of Pattern Types, and then replace it later using Pattern Types. But I was persuaded that actually this is poison, if you introduce my hack as a stable feature then it cannot ever actually be translated into a Pattern Type in user's code, so it becomes this weird orphan feature, "tialaramex's stupid niche type hack" forever even though all new types would use Pattern Types to achieve a much superior outcome, there's no known way to fix any of my hacked types.

So in effect you're making the arguments I was making like a month ago, that I now see are hopeless, which is why I'm asserting so vigorously that this is just a hack and what you should aim for instead is to explain to the type system what's going on even though that's harder.

The question about decltype ( do { return; } ) is pertinent because that type is to a type system like zero is to the integers in Z. I hope I spelled that correctly - I can't Godbolt it because do expressions are a speculative design, but hopefully you get the idea. This problem is easier to express with a do expression than with other C++ where the same problem arises but is harder to exhibit.

Thanks for elaborating on this, now I understand your thoughts. I wanted to write a longer answer, but life got in the middle. So I'll just say:

If rust devs do not want to add a specialization or traits for this feature and wait for the Right Thing it is fine. It is such a niche (get it?) requirement that it is not worth polluting the standard library.

But if you really need it as an user, I don't think the trait solution is an hack at all. I don't see specialization as an hack in general and in fact is important for writing efficient code.

Ideally you would be able to encode every possible property of your program elegantly and generically in the type system while keeping the language lean, fast and easy to understand. In practice at any point in time only a language will only have a finite subset of features and an user can't wait forever for the language to reach perfection. Any 50+ year language will necessarily accumulate cruft. Embrace it. Worse is better.

> It can still be easily re-added if the commitee wants to.

Yes but the earliest that could happen is, like, 2026 or perhaps 2027. Because you have to wait for both a new std revision to become available.

Isn't that pretty common? The [] operator acts like find or insert default value, so you can do nice things like ++map[key]. The map.find(key) works if you don't want to insert, it will return map.end() if the key couldn't be found.

My only gripe with find() is that you can't do `if (auto it = map.find(key))`. Otherwise yes, that's the way.

At least you can do `if (auto it = map.find(key); it != map.end())` since C++17.

I didn't know that was possible, thanks. It's worse than in other languages imo but better than the existing C++ alternatives, I will use it.

> Isn't that pretty common?

AFAIK basically just 3 wide-spread languages which do this, and they're all known for their idiosyncratic behaviour: C++, Perl, and PHP.

A few languages provide this as opt-in via a subtype (Python's defaultdict) or init (Ruby's Hash.new with a block parameter).

Some more will do it via an opt-in callsite API e.g. Python's `setdefault`, Java's `computeIfAbsent`, Rust's `entry` API.

perl only does this in some cases; unlike with std::map, this is safe:

   my $x = $h{$v};

this is not safe because it autovivifies $h{$v} as an ARRAY ref:

   my $x = $h{$v}[$i];

with respect to idiosyncratic behavior, if a language doesn't have idiosyncratic behavior, it has no reason to exist; it's just gratuitously incompatible syntax for already-available semantics

Python's defaultdict also behaves like this, inserting the nonexistent entry into the dict:

    from collections import defaultdict
    m = defaultdict(int)
    m["nonexistent"]
    len(m) # => 1

There are examples of the opposite too, though. Ruby's Hash does not insert the entry:

    m = Hash.new(0)
    m["nonexistent"]
    m.length # => 0

Python's defaultdict is aptly named to indicate this behavior (the bare `dict` won't do this). `std::map` isn't.

> There are examples of the opposite too, though. Ruby's Hash does not insert the entry:

It does if you initialise the hash with a block to do so:

    m = Hash.new {|h, k| h[k] = 0}
    m["nonexistent"]
    m.length # => 1

That is, essentially, what defaultdict does. Just through subclassing (because `dict` does not provide such a fallback, but it has a magic method you can override to customise the mapping's behaviour in that case).

this famously introduced bugs into norvig's published code (i forget if it was the sudoku solver or the spell checker) that nobody noticed for years

if norvig isn't smart enough to use defaultdict without introducing bugs then i'm not either

iirc it was the spellchecker. My memory is fuzzy and unreliable but what it's claiming is that the first version on his webpage had that bug, he fixed it, and later I pointed out another bug of the same type. Or something like that!

(I am sure I never reported anything about the sudoku solver, since I never studied it.)

thanks!

Lookup is map.at() (throws on invalid element), you can use map.contains() since c++20 or map.find()!=map.end() to see if the element exists beforehand.

operator[] does more than lookup, but there are other functions for the other stuff. It should be pretty clear...?

Things can be clear while still being unintuitive :)

Comparing to other languages I know, I couldn't think of another where collection[key] denotes insertion.

operator[] is indeed not great, the semantics are too surprising for such a short-hand notation.

  auto [it, newly_created] = m.try_emplace(key);

Does the same, and gives back more information. For something like `m[key] = value`, you can do `m.insert_or_assign(key, value)`, and save the default construction + assignment when the key was not there.

For ordinary lookup you don't want to randomly mutate the map anyway. If your reference to the map is const, you can't use operator[] anyway, fortunately. However `m.at(key)` is not great either when the key not being present is really not exceptional, and the dance with `m.find(key)` is often not too ergonomic. I still suggest to just use `find` here.

I (and many other C++ programmers), on the other hand, I'm always annoyed and surprised that dictionaries on other languages do not have default insert on lookup.

It is just very convenient (hence the existence of defaultdict in python).

Insert on lookup is convenient but encourages either double-lookup patterns (contains + get) or unintentional inserts. I very much like Python's setdefault -- except for its 10-chars name.

Well, STL encourages an iterator centric approach, so:

  if(auto i = x.find(y); i!=x.end()){ 
      // use i->{first,second}
  }

Also ideally you should be able to do this:

  for(auto [key, value]: x.equal_range(y)) { 
     
  }

But infuriatingly, x.equal_range returns a pair instead of some range view so you need some additional infrastructure (either convert the result of equal range into a range or add some begin/end overloads for pair).

My C++ is a bit rusty (no puns intended), I didn't know your first syntax was possible now (another comment states it comes from C++17), that's much nicer than the alternative that pollutes the scope indeed. Having to repeat both x and i is unfortunate, but that's par for the course with C++ iterators.

The equal_range solution looks nice from a genericity perspective (look ma I do multimaps!) but is really unintuitive with regular maps imo. Unless I'm mistaken it also does not allow an else branch for when the value is not there, which is often needed.

A for-else a-la Python would actually be generally useful!

Hopefully one day we will get proper patter matching and destructing in if statements (Herb Sutter has made significant progress on this).

For-else could be useful, but I don't think Python's semantics would actually help here? Python's for-else runs when the for loop did not break (even if nonempty), but what would be needed here would be to run when the for loop was empty, which is a different condition.

cpp2 is both interesting and ambitious, I really hope it gets somewhere.

Indeed, I misremembered the semantics of for-else! I don't think I have actually used it in python :)

Yeah for-else as implemented in Python is... not actually that useful. It's the right tool to inline std::find_if and that's basically it. I think the behavior you had in mind would actually be more intuitive and more useful.

OTOH, try...else I find myself missing at times.

You need both access patterns (otherwise you do a double-lookup to insert a default value) and C++ already provides both.

Whatever is implemented by operator[] in a given language is going to be implicitly encouraged by the language, and that's what most novices will use.

Yes.

Especially annoying when looking up something in a const& map.

The alternative approach could have been to make operator[]= and operator[] different.

You couldn't quite do that, because C++ has compound operators, and they can of course be overloaded, so:

foo[bar] += baz;

... needs to provide operator+= with a mutable reference to foo[bar], and a maybe immutable reference to baz.

So does C#, and it simply desugars the above into (foo[bar] = foo[bar] + baz), except that "foo" and "bar" are only evaluated once.

In what version of C# do you believe C# gained overloading for the compound assignment operators ? The latest Microsoft documentation I could find claims these operators cannot be overloaded.

It was always present. The reason for the claim in the docs is because they cannot be overloaded by themselves, only indirectly via overloading the binary operators that they're syntactic sugar for.

https://learn.microsoft.com/en-us/dotnet/csharp/language-ref...

Which is actually better than C++ in more than one way. As a library author, you overload a+b, and you get a+=b for free. As a user, you know that a+=b always means the same thing as a=a+b (except for side effects) regardless of the library.

Similarly, you can't overload && and || in C# directly like you can in C++, but instead you overload "operator true" and "operator false", and you get the boolean ops consistently derived from that (which means that they can short-circuit properly when overloaded, unlike in C++).

I agree that the consistency is nice, but it does mean we would end up paying twice for a hash lookup in this context, the sub-expressions are only evaluated once but the actual lookup must be performed both by the getter and the setter.

  salaries["Jim Bob"] += 10_000;

Calls the getter on salary to look up "Jim Bob", it finds maybe he's currently on 80_000, returns 80_000, we add 10_000 to that, getting 90_000 and then we call the setter on salary asking it to write 90_000 to "Jim Bob". Two lookup operations.

It's also deeply unfortunate here that C# thinks "null" is both a plausible value for common types and a good way to distinguish lookup failure. So it's possible either that Jim Bob's salary literally is null for some insane reason or that Jim Bob wasn't on the payroll, and the effects here are identical.

The extra lookup would not be acceptable in C++ or Rust, though that feels much more reasonable in a language like C# or Go -- paying a little performance to buy nicer ergonomics. The needlessly dangerous API shape on the other hand is very C++ and ought not to exist in C#.

C# does not attach any special meaning to null in the context of lookup, nor does it allow it by default even for reference types (assuming that you're compiling with nullability checks on, which has been the default for years), so I'm not quite sure what you're referring to. The standard way to indicate a failed lookup in C# is to throw an exception.

But, yes, it is true that you end up needing double lookup when combining compound assignment with indexing.

> C# does not attach any special meaning to null in the context of lookup

Lots of C# APIs do, in fact return null from Index (ie the [] operator) for "Not found", you're clearly writing much newer .NET code and so you're using a modern generic container which can't do this (because its return type can't be null)

> nor does it allow it by default even for reference types (assuming that you're compiling with nullability checks on, which has been the default for years)

My emphasis. I believe the default you're talking about starts in .NET 6 in late 2021. I don't think "since late 2021" qualifies as "for years".

C# Code I write from scratch does have nullability checks because I'd prefer to be in a language where "Null reference" isn't a thing, and this is as close as C# gets - but I maintain tonnes of code that was written three, five, even ten years ago.

I've been writing C# code since 2002, when .NET 1.0 first came out. "Modern generic collections" have been around since .NET 2.0 - that's 2005, so almost 18 years now. Their use was already pervasive by 2010, in my experience. Just about the only place where I can think of finding old-style patterns like returning nulls is WinForms and WebForms APIs from that same era that implemented the non-generic interfaces like IDictionary, and which can't be changed for backwards compatibility reasons.

I stand corrected on the timeline for nullable reference types being the default - for some reason I remembered it as being on by default for new projects since VS 2019.

The historic reason is that in C, [] on arrays is defined as returning an lvalue on which assignment then operates - that is, they have always been separate things, and there was no operator []= or anything like that to define semantics of array assignment in a single operation.

C++ simply generalized this model to all collections, in line with the overall "better C" design. But then for maps it means that [] has to proactively create an entry if you want []= to work like it does everywhere else.

Similarly, C++ iterators are generalized C pointers, which is also not an ideal abstraction in practice (and why few other languages do it that way).

To preempt the inevitable comment: in some cases (make sure to check!) you can use a third-party hash table such as the one Abseil provides, which may be faster for your usecase if you can use it. Of course, profile first before switching and make sure that std::unordered_map is your bottleneck, understand why it is slow, then determine whether it would be possible to switch.

Are there any cases where the abseil maps are slower?

And: how often does this even matter? I'd guess very rarely.

The Abseil maps assume you are using a good quality hash for your hash map. If you are using one that's particularly bad, e.g. your standard library typically provides hashes which are a complete joke, Google's Swiss Tables have catastrophically bad performance.

In contrast your typical std::unordered_map has indifferent performance with a good hash versus a terrible hash, anything vaguely resembling a working hash will perform similarly (not very well).

Remember "all the defaults are wrong" in C++. That's not literally true, but more often than not, if there's a clownishly obvious mistake possible, C++ made it and you will need to explicitly work around it in your C++ program. In this case, there's no avalanche behaviour in most out-of-box hashes for C++. So the hash for 1, 2, 3 and 4 are extremely similar, and indeed in many cases they turn out to be 1, 2, 3 and 4 respectively. Not a good hash.

I was genuinely surprised when I stumbled upon this Stack Overflow question [1] where someone asked why std::hash is the identity function for int, and some commenters argue that it is a perfectly sensible choice for a hash function.

[1] https://stackoverflow.com/questions/38304877/why-stdhashint-...

   $ python
  >>> [hash(x) for x in range(4)]
  [0, 1, 2, 3]

Why do you think it isn't?

Well, using the identity function as a hash does not provide any avalanche effect at all. And as parent comments point out, certain hash map implementations require a strong hash function. I'm guessing that the identity function probably isn't a "good" hash function as required by abseil's swiss tables and similar hash maps, but to be honest I haven't looked into this any further. Put another way, I'd have expected std::hash to be at least a very basic hash function (like FNV-1 for example).

Hmm, I know that at least some hash map implementations look for hash functions with an is_avalanching trait and otherwise add an explicit combination step; I'd assume that std::unordered_map implementations do the explicit combination all the time as std::hash was pretty much introduced just to work with such containers

As you presumably know std::unordered_map is essentially obliged to be a particular flavour of hash map which I'd say values simplicity of implementation over any performance metrics but which also provides certain iterator invalidation semantics which C++ programs could in principle come to rely on (and hence it cannot be swapped for a new structure).

Turns out for this structure hash quality just doesn't matter very much. The identity function is all you need for mediocre results, and a really great hash produces only slightly improved results with this data structure, yet running the hash costs performance so why bother ?

But a modern hash map structure actually relies on that quality for reasonable performance.

https://martin.ankerl.com/2022/08/27/hashmap-bench-01/#bench...

Ask that table about std::unordered_map - notice the fancier hashes make it worse (bigger numbers are worse, relative to 100 is the best) but not that much worse. It's always poor, it just varies as to whether it's very poor.

Now, ask it about absl::flat_hash_map - for Abseil's own hashes the results range from very good to mediocre, and likewise other modern high quality hashes, but for std::hash it's so awful most benchmarks don't finish, shown as - instead of a number.

You can try to detect this, but this is a fundamentally a QoI problem. Why even provide this rubbish hash function in the standard library? This is a lesson the C++ standard library refuses to learn, if you can't do it well then don't become an attractive nuisance by doing it badly.

People are actually less unhappy with Microsoft's stdlib which gives you a poor FNV hash instead of the identity function. Like, OK, this isn't a great hash, but it does basically work (under non-adversarial conditions, FNV has big problems for tailored input) something like Swiss Tables will be substantially slower than it ought to be, but not crazy benchmark failed due to timeout slower. Nobody is cheering, but it doesn't cause open weeping.

> Turns out for this structure hash quality just doesn't matter very much. The identity function is all you need for mediocre results, and a really great hash produces only slightly improved results with this data structure, yet running the hash costs performance so why bother ?

Then it's the good choice - I'm pretty confident the only reason std::hash is explicitly in the standard library is because it's the only way they could find to enable people to specialize hash functions for their own custom types - checking when it was introduced (C++ TR1: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n18...), std::hash is in a subsection of the "unordered containers" section and is really shown as an implementation detail of those (that has to be user-customizable).

If you use another hash table implementation, likely you're also going to choose a hash function that works well with it - I use Ankerl's in my own code for instance which 1/ comes with a modern hash implementation, wyhash, and 2/ obviously I specialize for the really specific cases I need performance for with the known statistical properties of my inputs. But I wouldn't want to pay for this cost for std::unordered_map

Luckily absl also provides absl::Hash, which doesn't have this problem.

If you don't need all the guarantees provided by std::unordered_map (pointer stability is usually the big one), you can go a /lot/ faster with a map that uses open addressing.

Some of my favorite alternative hash map implementations are ska::flat_hash_map and ska::bytell_hash_map from https://github.com/skarupke/flat_hash_map. They're fast, and the single header implementation makes them easy to add to a project. For my use cases they generally offer similar performance to abseil and folly F14.

Don't be fooled by the fact that they haven't been updated in ~5 years. I've been using them for nearly that long and have yet to find any bugs.

https://github.com/martinus/unordered_dense

Check this one out, it's a successor to this idea. Boost also introduced a very performant flat_hash_map in 1.81

std::unordered_map is forced to be slow and make lots of allocations due to iterator invalidation requirements. It's usually a good choice to avoid it (and use a different hash table implementation) if you care about performance.

The thing is, it’s not actually effortless in many situations to switch from one map to the other. In C++, if you switch to an unordered map, you now have to contend with the annoying boilerplate of implementing a hash function for many key types. Using an ordered map may sometimes give you a slight hit in performance, but it offers significant benefits in developer convenience, and for small maps, the binary tree could actually be faster anyway.

In fairness the tree still needs operator<() which sometimes less but not always easier to figure out than std::hash<>. I’d make a polite observation that in practice the GNU std::map is a red-black tree and that terminology mixup (which the author makes) might confuse folks.

It’s not unusual for the operator to be automatically available while the hashing function is not, however.

Yeah that’s fair and not a bad point.

Also, for some reason the C++ standard library does not provide a simple hash_combine or similar that would allow composing hashes of sub-objects of your custom type in a straightforward manner.

Can many hashes be combined quickly in a uniform way? This is another benefit of `<`, it composes.

> Can many hashes be combined quickly in a uniform way?

The XOR operator?

If you do that 10 times for all members of your struct, do you get good uniformly distributed keys?

This post doesn't think so: https://stackoverflow.com/questions/5889238/why-is-xor-the-d...

XOR is a bad way to do it, but there are ones that work much better that are described in answers to that post, and it's what other languages use in similar situations (e.g. tuples in Python and C#):

https://github.com/python/cpython/blob/71db5dbcd714b2e1297c4...

Yes, and eventually you start computing another hash of the buffer of the concatenated members. I'm not saying it can't be done, I'm just comparing it with recursive memberwise comparison.

All pairs of {x,y} with x==y or hash(x)==hash(y) would hash to the same value (0). That's seems suboptimal.

Just wait until you accidentaly hash your key struct invisible padding between data members (that are not there on you arch, because different alignment), and get irreproducible heisenbugs.

For anyone in a situation where an unordered_set or unordered_map is in a hot part of the code, I'd also highly recommend Robin Hood: https://github.com/martinus/robin-hood-hashing

It made a huge difference in one of the programs I was running.

EDIT: I could have sworn they used to also support the ordered versions, but maybe not.

Thanks!

Under what situation (if any) does the ordered map win over the unordered? I find it difficult to believe it is always an improvement, what's the niche uses?

Any time you actually need to use the ordering property. For instance, if you have an ordered map with string keys, you can very efficiently find all the keys with a given prefix. With an unordered_map, you'd have to iterate through the entire data structure.

Thanks for explaining the obvious, my self taught programming skills are unordered and my biggest obstacle is generally my not seeing what is right in front of me.

All of <algorithm> uses ordering operators as well. If you have a "regular" type with proper comparison and assignment operators, it works for everything, container keys, sorting, etc, etc.

Doing a string prefix search in an ordered map is actually not maximally efficient since you end up comparing the shared prefix over and over again during the binary search. You'd definitely don't want to be doing this with long prefixes.

If you want to store an object that implements operator< but doesn't have a hash function. While working on a leetcode problem I stored vector<int> in a set<vector<int>> instead of unordered_set<vector<int>> in order to eliminate duplicates.

Do you know about std::unique? Generally sets are a poor tool for removing duplicates.

Doesn't std::unique only generally work on consecutive items, and effectively requires the items to already be in a container (or at the very least have access to iterators to the items)?

If so, that sounds fairly limiting to me (i.e. potential extra storage - of duplicates, sorting required, etc).

This person is already putting sets inside vectors, so I don't think they are worried about storage.

But yes, you either need to stop occasionally and remove the duplicates or use a set, if the storage is prohibitive.

Otherwise in terms of performance, sorting and unique is much faster than inserting one element at a time in a set.

Some stuff I can think of:

- Hashing can be slower than comparison (or vice-versa), depending on the input. (e.g., imagine if your keys are multi-gigabyte files - hashing them would require reading all of their contents, whereas comparing might only need to read the first few bytes.)

- Ordered maps guarantee good worst-case performance. Unordered maps only guarantee average case. Usually you don't need to care, but with adversarial input you might.

- Ordered maps can guarantee low latency (well, to the extent your allocator can). Unordered maps can't - they suddenly block your program until the whole table is rehashed. Again, usually you don't need to care, but in some situations you might.

- Ordered maps have stable iterators; unordered maps "only" have stable pointers.

- Ordered maps have a guaranteed iteration order that depends solely on their contents; unordered maps don't.

- Any time the ordering itself is useful (see sibling comment)

That was very helpful, my initial mistake was I forgot about the data and only looked at what was being done too it, but I also neglected how we access that data. My background in analog electronics has made this one of the more difficult things in programming for me, I am used to my data as a stream not as something stored.

There may be contrived situations where std::map<T> is actually faster due to the operator < work being possibly cheaper than doing the full hash of the key, but that will only work if the key type is very well distributed early on in the key (i.e. for very long strings, with the first few characters in long strings all being different among items in the std::map, providing the ability to short-circuit quickly) and the number of items in the map is less than what's needed to meet the short-circuit threshold that makes it technically more efficient.

But that's very unlikely, and in such a contrived scenario it's likely doing a linear std::find() over an array of keys would be as fast or faster anyway, due to better caching/pre-fetching/branch-prediction.

If you're really looking to optimize hash map performance, you should try Abseil's flat_hash_map. It's able to do some things that the standard library's maps cannot because it doesn't have to stick to the standard library's guarantees of pointer stability.

Both std::map and std::unordered_map are slow, ,actually. See this discussion on StackOverflow:

https://stackoverflow.com/q/42588264/1593077

I always listened that unordered_map is more cache friendlier than map. My intuition tells me unordered_map is better to iterate, and map is better to random access.

Unordered map is a hash map. Map is a binary search tree.

There’s no random access for hash map, in the sense of “give me the fifth element”. If you mean a lookup, like map[key], hash map has an O(1) amortized look up, where as a binary tree has an O(log n) look up, so hash map will generally be faster in this regard.

By "iterate" I expect they mean to just look at all the key/value pairs in the map. Since it says "Unordered" right in the name they don't care what order they see the elements, just that they see them all.

This is easy to do in all sane hash map designs, and is very fast in a linear design like Abseil's Swiss Tables.

Also sadly C++ std::unordered_map is guaranteed to be not just a hash table but an open hash table, using buckets to keep all the stuff which collided together. This is probably not what you wanted, but too bad that's what was standardized.

This is quite unfortunate. The way to get a really good hash table is by enforcing a bunch of simplifying assumptions (power of 2 sizes, sentinel values, etc). But the C++ committee has to make the "one true table" for everyone.

std::map actually seems to fit this role better. It works reasonable well for many workloads and types without tuning a bunch of parameters.

> is very fast in a linear design like Abseil's Swiss Tables.

It's not that fast, because branching is completely unpredictable when iterating the sparse array (though a very high load factor helps). That's why a few modern hash tables trade an additional indirection on lookup by storing entries in a dense array and making the sparse array an array of indices into that.

It makes iterating the map as efficient as iterating an array (or zipping two depending on data layout), it also saves some memory (especially if the indices array is adaptive), and has the neat side-effect of making the map conserve insertion order (though deletion is a bit of a concern, tradeoffs may have to be made with the other advantages).

Good point about the branch cost.

For a general purpose hash map, I think promising to preserve order despite deletion (like Python's current dict) is a mistake in performance terms†. Python could afford a penalty here because their previous dict was so ludicrously bad that you won't notice. We can't know if the user of a general purpose hash map does 0% deletes or 50% deletes nor whether the ordering is valuable to them at all anyway.

† If we don't promise to preserve order then delete just swaps the removed item from the dense array with the last item, then removes the last item, very efficient, if we insist on preserving order we're either using tombstones which mean branches or we're shuffling half the bloody array for each deletion.

> so hash map will generally be faster in this regard.

Complexity is not a measure of runtime. The performance drawbacks for std::map have to do with cache, not O(log) vs O(1). log(billion) is 30. And that's exactly how many comparisons you have to do, not a constant multiple of that.

With an open addressing hash table, who knows how many steps you will need to find an element. It's even more questionable if it does linked list chaining.

> binary search tree.

It's usually a red black tree and maybe could be a b-tree? "Search tree" is accurate.

> maybe could be a b-tree?

IIRC the complexity requirements of std::map preclude a b-tree (or require a binary tree). Though I don't remember the exact reasoning.

abseil's website makes the same claim, though also without justification:

> B-trees have a different implementation from STL std::map containers, which require binary trees commonly implemented as red-black trees.

> It's usually a red black tree and maybe could be a b-tree? "Search tree" is accurate.

I mean, I haven’t write red black trees for a while, but it is a type of binary search tree, as far as I remember, isn’t it?

You are correct. Sorry if I am being pedantic. I was also trying to suggest it could be a b-tree but others have pointed out that it doesn't quite fit the spec.

> My intuition tells me unordered_map is better to iterate, and map is better to random access.

map is definitely not better for random access, with the possible exception of adversarial input: IIRC std::map pretty much requires an rbtree so you get an O(log2(n)) access, while unordered_map is a hashmap so has an O(1) best case but O(n) worst case.

unordered_map might have a better cache friendliness (though that's debatable as IIRC the standard requires closed-hashing), however iterating it is a long series of unpredictable branches (each bucket can be empty or full and the better your hash function the more random it is), std::map requires a lot of pointer-chasing instead but it's all completely predictable.

Map is unfriendly in several ways because of the nodes being allocated with new by default. You can significantly improve its behavior by constructing the map with an arena allocator. Then you will enjoy better cache locality and cheaper mutations.

Why not just use iterator that will avoid multiple lookups.

This is a solution presented in the post :)

I rarely need to use maps, but everytime I had to, std::unordered_map was measurably slower than std::map. In particular in debug mode, it was really slow, and if you choose an unfortunate hashing function (I think older MSVC versions had a really bad one), it can easily become a bottleneck. In particular with small data or data that has trivial comparison functions, std::map might often be better and should be the go-to choice.

Reply on news.ycombinator.com