lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

Paul Hudson wrote:
> I didn't think I was being particularly sophisticated then, and I'm sure the
> state of the art has advanced in the 22 years since then.

But the art of CPU design has advanced since then, too.

> So I agree, I see nothing in C switch statements that makes them inherently
> slow.

Maybe you want to catch up on the topics of pipelined CPUs,
out-of-order execution and the impact of branch misprediction
penalties. Writing a good compiler for a modern CPU is not easy.
Many design decisions that may have been right two decades ago,
no longer apply.

As I said, the problem with switch-based dispatch is usually _not_
the interval check. It's the single-dispatch-site, unpredictable,
indirect branch. And the problem is real.

In many cases even a linear series of up to a dozen branches
performs better, especially when sorted by frequency. Decision
trees ordered by frequency perform even better. In some cases it's
preferable to perform redundant computations or to use predicated
instructions just to avoid a branch. Modern CPUs are strange beasts.

To get this back on topic: incidentally trace compilers (such as
LuaJIT) generate these kind of decision trees on-the-fly, based on
runtime execution statistics.