5 ms·
I think the most important lesson of this article is in this sentence: Why this code was written this way instead of just checking against the ID by linearly i
by userbinator 5y ago
I think the most important lesson of this article is in this sentence:
Why this code was written this way instead of just checking against the ID by linearly iterating over the Components, I have no idea.
There's another comment here that shows their JPEG decoder only supports 1 or 3 components. Using a hash table for at most 3 entries is astronomical overkill! The field for the number of components in a JPEG file is only a byte - so even if you were to support more than 3 components, it would be 255 at most, and sane JPEG files are unlikely to have more than 4 in practice. So fixed-size arrays are the perfect solution. I have a very good idea why it was written like that, however: the mere availability and ease of use of abstract data structures naturally leads to their overuse by what seems to be an overwhelming majority of developers, and the eagerness to "futureproof" and add unnecessary complexity is also very common.
Overcomplexity creates bugs, and (leaky) abstractions hide them. Even if the complexity (and bug) isn't visible in your code, it's still there. If the initial code had been reviewed by me, it most certainly would not pass.
I am saying this as someone who has actually written a JPEG decoder --- it is not as difficult as it may sound, and I highly recommend giving it a try --- and also witnessed (and fixed) the messes that people get in with overcomplicating things. Perhaps that slight "architecture astronaut" mentality comes from starting with a higher-level language; I started with Asm and my preferred language is usually C, and I haven't seen the tendency to overcomplicate much in others who did the same.
The reason the Components were in a hash table was that they would then be checked against the component ordering in a “Start of Scan” section to make sure all the components in the SOS section are in the expected order.
For comparison, this is the corresponding code in my JPEG decoder. I didn't even bother using a loop:
if(read_byte()!= cids[0])
data_error("SOS scan first component must match");
hts[0] = read_byte(); /* high nybble: DC table index; low nybble: AC table index */
if(read_byte() != cids[1])
data_error("SOS scan second component must match");
hts[1] = read_byte();
if(read_byte() != cids[2])
data_error("SOS scan third component must match");
hts[2] = read_byte();
- deleted 5y ago[deleted]
- logicchains 5y ago>I have a very good idea why it was written like that, however: the mere availability and ease of use of abstract data structures naturally leads to their overuse by what seems to be an overwhelming majority of developers, and the eagerness to "futureproof" and add unnecessary complexity is also very common. To give some context, iterating over an array of three small items takes worst case roughly 100ns(cache miss), best case 1ns(l1 cache hit). Most common hashmap implementations (like std::unordered_map) dynamically allocate items so they're stored randomly in memory, giving roughly 300ns worst case(3 cache misses), 3ns best case(3 l1 cache hits) for iterating over them. So using a hash map is going to be 3x slower without even accounting for the time spent hashing, and 3x more likely to hit the worse case due to requiring three cachelines still in the l1 cache for best performance as opposed to just one. If regularly adding/deleting items, using a std::unordered_map would literally be orders of magnitude slower due to using malloc/free for each item added/removed.
- Bancakes 5y agoHow did you get exactly a 3x slowdown? I thought unordered_map is a vector of vectors aka separate chaining?
- MauranKilom 5y agoNo. unordered_map buckets are linked lists of nodes (key + value pairs). So you have one indexing into the bucket array to retrieve the list pointer, and then you may or may not have to chase an arbitrarily long linked list. But the nodes are necessarily allocated separately, so (assuming the bucket array is in cache [previous post should say 4 cachelines, not 3] and you don't have to chase beyond the first list element) you still have that indirection somewhere into memory. This all comes from the specification requiring even load factors arbitrarily close to 1 and to still have amortized constant time insertion, lookup and deletion.
- Bancakes 5y agoThat's horrid. I have some old code where adjacency matrices are unordered maps of unordered maps. Yikes.
- hyperman1 5y agoIn this case, there is an alternative view to 'architecture astronaut': Conservative programming. If you don't have experience with the spec, it might not be clear that n<=4 is the reasonable maximum if the spec permits n=255. Who knows what horrible JPGs exist in the wild? Even if you only find examples to test n<=4, are you willing to take the risk ignoring what's left? Your code needs to be out in the real world for a while before you can truly say. Better a slow but working implementation.
- _0ffh 5y agoGP explicitly covered this: Just expand your fixed-size array to the required size, it's still not a big array. It solves the exact problem, the map is overkill and overly complicated. The problem is, the map is only more complicated in the resulting binary, not in the library users' source code.
- eru 5y agoNot sure the binary comes into it. The map in this language has a more complicated API than the array (because iteration is a bit more complicated).
- samus 5y agoAllocating 255 elements is not the end of the world. Unless the decoder is supposed to run on a memory-constrained platform, this is barely noticeable.
- kristofferc 5y ago> Using a hash table for at most 3 entries is astronomical overkill! Here is the given reason for using a HashMap: https://github.com/SerenityOS/serenity/commit/f107c7065230c6ffa179caca28773e04d4f3107d https://github.com/SerenityOS/serenity/commit/f107c7065230c6...
- unwind 5y agoThat is interesting. The code switches out a static array of size 3 for a hash table, in order to handle that incoming IDs (used as indexes in the array, then keys in the hash) can go up to 255 instead of just 2. I would think that upping the array to size 256 would still be cheaper (or at least not a lot more expensive) in terms of memory used than adding a full hash table, but I have not inspected Serenity's hash implementation to validate that claim. It would almost certainly be cheaper in terms of performance, especially from less memory allocations.
- iforgotpassword 5y agoAgree. Even if the hash map somehow wouldn't use more than an array[256], it would still be faster as the compiler can optimize more due to simpler memory layout, and even the cpu can cache more efficiently and better speculate since less/simpler code is involved. Always start with an array if the problem allows for it, even if you need to reallocate sometimes, or have to scan linearly. Measure performance before using a map or linked list.
- mhandley 5y agoOr even use an array of size 3, but include the IDs in each element and linearly scan for the right ID. As the whole array will likely fit on a cache line and you want to access all three elements in a short time anyway, this is likely no slower than a hash table.
- munchbunny 5y agoThat's what I was thinking after reading the rationale, there are plenty of options that don't involve a hash map. That said, linearly scanning is not much different from a hash map with linear probing that has no empty slots left, so it's not necessarily obvious that the hash map actually takes that much more space.
- eru 5y ago> Using a hash table for at most 3 entries is astronomical overkill! The field for the number of components in a JPEG file is only a byte - so even if you were to support more than 3 components, it would be 255 at most, and sane JPEG files are unlikely to have more than 4 in practice. So fixed-size arrays are the perfect solution. I have a very good idea why it was written like that, however: the mere availability and ease of use of abstract data structures naturally leads to their overuse by what seems to be an overwhelming majority of developers, and the eagerness to "futureproof" and add unnecessary complexity is also very common. > Overcomplexity creates bugs, and (leaky) abstractions hide them. Even if the complexity (and bug) isn't visible in your code, it's still there. If the initial code had been reviewed by me, it most certainly would not pass. I suspect in this case the problem is trying to use this style of coding in a language like C++. If you implement this in eg Python, using the hash table would have been perfectly natural and the simplest way to do it. (And a modern enough Python would guarantee your ordering.) In Java, Haskell or Rust etc something else might have been simplest.
- amelius 5y ago> I have a very good idea why it was written like that, however: the mere availability and ease of use of abstract data structures naturally leads to their overuse by what seems to be an overwhelming majority of developers, and the eagerness to "futureproof" and add unnecessary complexity is also very common. Or perhaps the code is shared with some other project which does require the added complexity.
- londons_explore 5y ago> Using a hash table for at most 3 entries is astronomical overkill! I disagree. Simplicity of the code is most vital to avoid bugs, and if a hash table is what the language typically uses to represent key value mappings, that is what should be used, for 3 or 3 million items. Keep the code idiomatic, and only optimize where necessary. A good implementation of a hash table has a special fast path for tiny runtime sizes. A good compiler could bound the size of the hash table, and switch out the implementation if its size can be bounded at compile time. Sure, in this case, it didn't work so well. But the principle of idiomatic code still stands.
- userbinator 5y agoFrom experience, I can say that the amount of times I've heard those arguments also corresponds closely with the sort of code this article is about. If you're using a language where all you have are hash tables (PHP comes to mind), then there's no way around it; but it's insanity to overlook simplicity.