I got sucked into a LinkedIn post on “Why Dictionaries are 7 x slower than arrays”, and shuddered as the BigO crowd leapt all over it, completely missing the point entirely. It wasn’t supposed to be about O(n)Log(banana)^Transformer. It was about memory. And computer architecture. <\/p>\n\n\n\n
So please, indulge me, here is the real reason why a C# Dictionary is 7x slower than an array.<\/p>\n\n\n\n
If you have a standard array<\/strong> (e.g., You’ve got the size, you’ve got the location, it’s already in the cache\u2014you\u2019re golden! <\/p>\n\n\n\n Oh boy. First, we need a hash<\/strong>. Not great, but whatever, we can do a But even if we do have to probe further, it’s not that bad<\/strong> because the dictionary stores its entries in a contiguous array of structs ( Already, this is getting a bit beefy. And we still haven\u2019t even touched our actual data yet.<\/strong> <\/p>\n\n\n\n At this point, we’ve found our With a contiguous array<\/strong>, the next bit of data is guaranteed<\/strong> to be right after the last bit. Your But Memory is slow.<\/strong> CPUs stall<\/strong> if they don\u2019t get the data they need. That\u2019s it.<\/p>\n\n\n\n That said, computers are plenty fast<\/strong>, and dictionaries are super useful<\/strong>. I use them all over the place. And when I don\u2019t, I use Why?<\/strong> Because convenience outweighs speed… until it doesn\u2019t.<\/strong> Randall Hyde has a fantastic series of books on Amazon called Write Great Code. if you haven’t, go read them. When you better understand the machine you will write better code.<\/p>\n\n\n\n Or at least, when you write sloppy code, you will know why its sloppy and you’ll be able to justify it \ud83d\ude42 <\/p>\n","protected":false},"excerpt":{"rendered":" I got sucked into a LinkedIn post on “Why Dictionaries are 7 x slower than arrays”, and shuddered as the BigO crowd leapt all over it, completely missing the point entirely. It wasn’t supposed to be about O(n)Log(banana)^Transformer. It was about memory. And computer architecture. So please, indulge me, here is the real reason why…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-92","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.mastertoncodes.com\/index.php?rest_route=\/wp\/v2\/posts\/92","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mastertoncodes.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mastertoncodes.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.mastertoncodes.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mastertoncodes.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=92"}],"version-history":[{"count":2,"href":"https:\/\/www.mastertoncodes.com\/index.php?rest_route=\/wp\/v2\/posts\/92\/revisions"}],"predecessor-version":[{"id":95,"href":"https:\/\/www.mastertoncodes.com\/index.php?rest_route=\/wp\/v2\/posts\/92\/revisions\/95"}],"wp:attachment":[{"href":"https:\/\/www.mastertoncodes.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=92"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mastertoncodes.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=92"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mastertoncodes.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=92"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}MyClass[]<\/code>, not<\/em> a List<><\/code>!), it’s contiguous in memory<\/strong>, which means:<\/p>\n\n\n\n\n
Now, enter
Dictionary<int, MyClass><\/code>.<\/h3>\n\n\n\n%<\/code> without overheating, no big deal. Now we\u2019ve got a bucket<\/strong>. If we\u2019re lucky, the first entry is what we\u2019re looking for\u2014no need to walk the chain looking for our hash. Phew! <\/p>\n\n\n\nEntry<TKey, TValue><\/code>)<\/strong>, which means:<\/p>\n\n\n\n\n
The real problem? Heap allocation.<\/strong><\/h3>\n\n\n\n
TValue<\/code> in the Entry[]<\/code> array. But now, all bets are off<\/strong>.<\/p>\n\n\n\n
With a dictionary? Nope.<\/strong><\/p>\n\n\n\ndict[0]<\/code>, dict[1]<\/code>, and dict[2]<\/code> could live literally anywhere<\/strong> in memory.
Each lookup could cause cache misses, cache evictions, and CPU stalls<\/strong> all over the place. <\/p>\n\n\n\ndict[0]<\/code>, dict[1]<\/code>, and dict[2]<\/code> looks so convincing. That delicious syntactic sugar. But remember when you allocated the memory for those entries? It was off the heap. Was it immediately after each other? Maybe. Does that it make it contiguous? Hell no!<\/p>\n\n\n\nAnd that’s the real reason dictionaries are slower than arrays.<\/strong><\/h3>\n\n\n\n
The big caveat<\/strong><\/h3>\n\n\n\n
List<><\/code>.<\/p>\n\n\n\n
And when it doesn\u2019t?
You better know how to diagnose, debug, and fix it.<\/strong><\/p>\n\n\n\n