4 ms·

> but I would have expected a dict function lookup would have been faster than the binary tree of if/else decisions. This would just be an O(n) worst-case oper

> but I would have expected a dict function lookup would have been faster than the binary tree of if/else decisions. This would just be an O(n) worst-case operation, the same as a non-optimized switch statement. In C/C++, Rust, etc it makes sense to use an array of function pointers as it degrades into a jump table, but not in Python. Same goes for an exhaustive and non-fallthrough switch statement. Using a binary search tree (what this essentially is a flattened version of) halves the worst case. For 8-bit CPUs, the more common paradigm is to use a giant switch statement and just order the OPs by frequency. You get the same Worst-Case, but a much better Average-Case.

junon 3y ago
What about python arrays? Been a while since I poked around python internals but surely lookups in a list isn't worst case O(n), no?
flohofwoe 3y ago
In C and C++ a continuous switch-case will be turned into a simple jump table though, which turns the "opcode decoding" into a single indirect branch instruction (or something similar on esoteric ISAs like WASM). The jump table transform happens at least on gcc, msvc and llvm based compilers. Also, at least llvm is also clever enough to build a mix of binary search and jump tables for "sparse" switch case statements.
- deaddodo 3y ago
  Which is what I said, no? > In C/C++, Rust, etc it makes sense to use an array of function pointers as it degrades into a jump table [...]. Same goes for an exhaustive and non-fallthrough switch statement. I have no doubt that non-exhaustive (sparse) switch statements can also be optimized in compilers today; the more important portion is the non-fallthrough aspect.
tasty_freeze 3y ago
Python uses some kind of hash, so worst case O(n) would be very unlikely. And rereading what I wrote, I don't know why I said dict -- an array would be just fine. For most languages, a dense case statement is implemented via a jump table, a fast, constant time operation.
- deaddodo 3y ago
  I said that, no? > In C/C++, Rust, etc it makes sense to use an array of function pointers as it degrades into a jump table [...]. Same goes for an exhaustive and non-fallthrough switch statement.

junon 3y ago

What about python arrays? Been a while since I poked around python internals but surely lookups in a list isn't worst case O(n), no?

flohofwoe 3y ago

In C and C++ a continuous switch-case will be turned into a simple jump table though, which turns the "opcode decoding" into a single indirect branch instruction (or something similar on esoteric ISAs like WASM). The jump table transform happens at least on gcc, msvc and llvm based compilers. Also, at least llvm is also clever enough to build a mix of binary search and jump tables for "sparse" switch case statements.

deaddodo 3y ago
Which is what I said, no? > In C/C++, Rust, etc it makes sense to use an array of function pointers as it degrades into a jump table [...]. Same goes for an exhaustive and non-fallthrough switch statement. I have no doubt that non-exhaustive (sparse) switch statements can also be optimized in compilers today; the more important portion is the non-fallthrough aspect.

tasty_freeze 3y ago

Python uses some kind of hash, so worst case O(n) would be very unlikely. And rereading what I wrote, I don't know why I said dict -- an array would be just fine. For most languages, a dense case statement is implemented via a jump table, a fast, constant time operation.

deaddodo 3y ago
I said that, no? > In C/C++, Rust, etc it makes sense to use an array of function pointers as it degrades into a jump table [...]. Same goes for an exhaustive and non-fallthrough switch statement.