Hacker News Reader

Comment by kristofferc | Hacker News Reader

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

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.

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.

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.

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

Reply on news.ycombinator.com