And therefore just a little bit evil.
Before I got the gig at Mojang Studios I interviewed with some folks at Amazon and in the whiteboard code I used an std::map. If I remember how it went down, the interviewer asked me why not an unordered_map. "It's just better, right?"
The answer that immediately jumped to my tongue--but I did not say--was: well, faster, sure.
But it's hard to argue against it. Apart from speed, the map and unordered_map seem just about equivalent--unless you really need the map to be in order, why not default to the faster unordered_map?
They did not offer me that job. (Thank goodness. Much rather be at Mojang.)
Anyways, pure functional programming might provide a counterargument: suppose you have a function that creates and iterates over an unordered_map. Is that a pure function? Is it deterministic? Can we rely on it to produce the same set of outputs given the same set of inputs?
It will execute the same every time you run it, yeah? So sounds like...yes?
Fast forward a bit to me joining Mojang. The first bug I looked at was a bug that only happened on the Nintendo Switch. It seemed there was a corner case where, if joined to a network game, and using a particular avatar skinning mode, Steve's sword would appear in a rather...unfortunate...place. It was my first work item on Minecraft and so I was learning the code base and learning the Switch, so it took me almost two weeks of going back and forth between the Windows version and the Switch version, stepping through the code, trying to figure out where these things diverged and the sword was being given the wrong matrix.
Given the topic of this article you already know what the culprit was: an unordered_map. We were iterating through one, passing the results to another function, certain other sketchy things were happening where we were deciding which matrix to keep, and it turned out we were unintentionally relying on the map to iterate in a certain order. And on the Switch, with its different version of a different compiler, the order was different.
Which brings us back to whether iterating over an ordered_map is deterministic. It fools you into thinking it is, because it is deterministic on a given platform and compiler. But if you're developing for multiple platforms, it's not true. Also - the compiler writers might one day rev the unordered_map code, and that function would now return a different result.
Of course, the unordered_map was not technically to blame for that bug. It's obvious you shouldn't rely on the order of an unordered map! We fixed the function that consumed its output to stop making that assumption, and fired the coder who did it. (Just kidding - we would never do that at Mojang. #growth_mindset!)
Still, it's not the only unordered_map bug we've had on the Mojang team. And it made me think that it's one of those things where maybe we should be blaming the system rather than the individual. It's very easy to say "You forgot to initialize your variable" or "You forgot to deallocate your object" or "You forgot to invalidate the cache" etc etc - but the good languages and systems are the ones where it's harder to make dumb mistakes.
And now I'm including the good old ordered map as one of those better systems. It's deterministic and therefore reliable, unlike its modern reckless speed-demon cousin.
We often use maps and sets as convenient dictionaries to easily look up data, even if we're only dealing with a handful of items in places in the code that are called less than once per frame, just because it takes fewer lines of code than to find the thing in a vector. When doing that, I'd recommend sticking with old reliable rather than risking an encounter with Hyrum's Law. It's easy to accidentally rely on the order of an unordered map. It will happen sometimes. And sometimes it will later break.
Hey, if it shows up as a perf hotspot, then you can add those 10 extra characters to make it fast.
Besides, when I was a young man we didn't even have unordered_map!
Get off my lawn!
Comments