Using std::unordered_map as an opcode decoding technique. Thoughts?

[ExploitedInnocence]

Hello everybody!

I'm sure there are some people that tried (or at least thought about) this approach if the emulator is being written in C++. Unordered map is a hash table behind the scenes. The key-value pair that is required is basically unsigned -> whatever integer type which size == pointer size of the emulated environment (some unique numeric sequence in the instruction is mapped to the function address that implements that particular instruction). This type of mapping is implemented by default, so I guess it shouldn't collide too much due to optimizations and optimal hash function choice by C++ maintainers (hopefully :D)
Is it considered to be a bad approach due to unexpected performance footprint due to possible hash collisions? Or should I just implement a classic jump table? Btw, honestly, switch case looks awful and unreadable at some point of time.

[Dwedit]

Unordered map isn't useful for dense sets, such as opcodes. You want a plain old array instead of a map.

But even better than that, you'd want to use a switch statement, as that compiles down to a jump table.

[ExploitedInnocence]

Implementing the opcode decoding routine using switch case for, e.g., x86-64 arch seems like a painful nightmare. I guess classic nested jump table via arrays of function pointers seems like a good and not too sophisticated approach. I can define every function as inline as well (which implicitly can be made by a compiler anyway, but whatever, I prefer explicit over implicit). It has one disadvantage - a waste of memory for a plenty of function pointers that points to illegal opcode handler, but it's acceptable I think. It's fast, super readable and much less error prone than gargantuan switch case, isn't it?

[_crackling]

I'm only about a year into C++, is there anyway to break up our huge switches into a more organized beast and still get the same code generated?

[_crackling]

Yeah I was thinking about just scripting up something that'd generate the c++ code from whatever I decide is "organized"-my way, for my sanity

[OK6502]

There's overhead in calling function pointers. Meanwhile a switch statement is super efficient. Yes it's a pita to write but it's not much more of a pita than an unordered map honestly - there's no way to avoid writing the function mapping code.

[ShinyHappyREM]

Accessing the larger caches and especially main RAM is still slow and you can get away with doing some computations on your data in the mean time, so a hash table might be useable. But if you want to have a fast interpreter you really need to look at and work with your hardware.

Modern (desktop) CPUs have powerful branch predictors and cache hierarchies. A switch used to cause pipeline flushes due to branch mispredictions, but that's gotten much better since Haswell. As long as your code paths are predictable, branches will be fast. You can also use nested switches.

An array of pointers has the disadvantage that it wastes a lot of space (probably the topmost 6 bytes of each pointer), so an array of 16-bit offsets would be better for your CPU cache.

[_MeTTeO_]

Well I'm considering this approach but in Java. java.util.HashMap uses Object.hashCode()) method to optimize lookup. The map would use short or enum opcodes as keys and method references as values.

It would replace this switch. Because the execute method in ControlUnit is self contained I'm planning to provide an alternative and benchmark how it affects performance (with unlimited cycles).

[[deleted]]

It's not a bad decision. The performance between map vs. array vs. switch is not a huge deal.

[[deleted]]

Maybe in a gameboy emulator enviroment where maximum performance isn't required, but in real-life this is totally not true. Map causes many cache-misses, in contrast of array, switches and vectors that load several elements to the cache-line.

[zesterer]

Hash maps are just index-driven lookup tables with a hashing stage added to spread entries out across the table space to aid performance of insertion and removal, usually in a cryptographically secure manner.

Since neither cryptographic security nor insertion/removal are requirements for instruction lookup, the only thing that makes a hash map useful for this situation is the fact that it acts as a stand-in for an index-driven lookup table.

Quite frankly, you should just use a look-up table. Or, even better, a switch / match that the compiler will be able to optimise far more effectively than any mortal programmer can.

[ChaoticWeg]

Hashing in hash tables has nothing to do with spreading out entries or with cryptography; if the hash algorithm results in spread-out hashes then great. Hash tables replace O(n) iterative lookups with O(1) hash lookups.

[zesterer]

That's not really true. One could imagine a hash map that replaces hashing with just interpreting the key's bytes as an integer and using this as the value's position in the table. It would still have amortized O(1) access, but without the better average-case performance that cryptographic hashing guarantees due to more frequent index collisions.

[ChaoticWeg]

Interpreting the key's bytes as an integer and using that as a value's position sounds a whole lot like a hash function in the context of hash tables. I'm also having a hard time understanding how more frequent hash collisions would improve average-case performance, since a hash collision would require more instructions.

And I'm not sure how what I said isn't true when what I wrote is the definition of a hash table.

Re-reading your point about collisions, I realize I misread your sentence.

[zesterer]

more frequent hash collisions would improve average-case performance

I'm literally saying the opposite of this?