Hacker News Reader

>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.

How did you get exactly a 3x slowdown? I thought unordered_map is a vector of vectors aka separate chaining?

No. 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.

That's horrid. I have some old code where adjacency matrices are unordered maps of unordered maps. Yikes.

Yes. Pointer chasing datastructures really want to live in a language that has a compacting and relocating garbage collector.

If all your objects are doomed to die where there were born, you better put them in the right place. (So an array is good for C-like languages.)

Or even better yet, use a language with a sensible SSA implementation that can identify local only variables and allocate them on the stack (like golang).

That technique is useful _and_ independent of what I suggested. Ie you can do it whether you have garbage collection or not.

Though it's less important on languages with compacting garbage collectors, because there allocation can be just a pointer bump, which is pretty similar to what you do for stack allocation.

See also this Scheme implementation which allocates everything on the C stack:

> Previous Schemes for implementing full tail-recursion when compiling into C have required some form of "trampoline" to pop the stack. We propose solving the tail-recursion problem in the same manner as Standard ML of New Jersey, by allocating all frames in the (garbage-collected) heap. The Scheme program is translated into continuation-passing style, so the target C functions never return. The C stack pointer then becomes the allocation pointer for a Cheney-style copying garbage collection scheme. Our Scheme can use C function calls, C arguments, C variable-arity functions, and separate compilation without requiring complex block-compilation of entire programs. Introduction IEEE Scheme [IEEE90] requires that all functions be properly tail-recursive, in order that tail-recursive programs not require an unbounded amount of stack space. Several Scheme compilers have targeted the C language [Bartlett89], because C is an efficient systems programming language which is available on nearly ev...

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7...

Do keep in mind that some languages like Scheme (because of call/cc) and Haskell (because of laziness) in general don't have a single stack. See eg https://en.wikipedia.org/wiki/Parent_pointer_tree for what Scheme needs to do.

Of course, allocation of variables with hierarchically nested lifetimes (ie stack allocation) is still an important and common special case that your compiler/interpreter should probably recognize and handle well.

Escape analysis is a well studied field after all. https://en.wikipedia.org/wiki/Escape_analysis

In 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.

GP 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.

Not 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).

Allocating 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.

> 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/f107c7065230c6...

That 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.

Agree. 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.

Or 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.

That'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.

I wouldn't expect a hash map that uses linear probing to wait until it's full (or even nearly full) before increasing the size of the table. Doing a linear scan on a hash table which is both nearly full and very large would be quite bad.

Normally I wouldn't expect it either, but if you know it caps out at single-digit numbers of elements, then it's not the worst idea.

I'd still just use a plain array, but my point was that hash maps aren't necessarily big and unwieldy.

Might be higher performance, wouldn't necessarily be less complex or less likely to result in a bug, as the original point in this thread suggested. It turns out it's not exactly an "overcomplexity" problem. And looks less like it was caused by “the mere availability and ease of use of abstract data structures naturally leads to their overuse.”

Even if not optimal, it definitely looks less unreasonable as a choice now that the original motivation found.

And if it had been “fixed” in the simple way without finding the original motivation, it very well may have introduced a different edge-case bug.

So one important lesson here, is always try to do some “due dilligence” to track down why code was written how it was before changing it, even if (or especially if) you assume it was just shoddy coding. (What’s the metaphor/aphorism used about this? I remember there is one, but can't recall/find it now).

(And also reminds us of the importance of good granular commits with good commit messages, to leave that history! Much easier to find original motivation than in a pre-version-controlled world).

Skimming the JPEG spec I think the commit author was waaaay off base. The actual spec is very clear that 4 components is the max and are expected to be sequential in nature (4.11 Summary of coding processes) unless I'm reading it wrong. Ultimately the original implementation was wrong fro not including a fourth channel per spec... but not wrong in assuming sequential.

Even if there are more than 4 components, they are still required to be sequentially ordered. Their decoder also errors out if there are more than 3 components (https://news.ycombinator.com/item?id=27375596), so all you need to do is keep the IDs in an array of 3 entries and check that they match later. That's what the fragment of code I posted from my decoder does.

That's what I'd assumed when I started skimming the spec, but the section I referenced seems to indicate a max of four regardless. I've never heard of a JPEG that's not RGB(A) or CMYK. So it would be highly unusual, not saying it couldn't happen but given how unusual it would probably be replaced with a custom format for that specific application.

> 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.

> 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.

From 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.

> 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.