5 ms·

true - but would require modifying the proposed solutions. Besides, it does not remove the branching issue of mod ... unless you use a lookup table for that too

• smlckz 6y ago
  heh, the branching is now in the implementation of the lookup table
  • Jtsummers 6y ago
    It's a common pattern in embedded systems (for better or worse) when you have something like function pointers or computed go tos available. C, of course, has function pointers and I've seen dispatch tables like this before: message_handler = {type_0, type_1, ..., type_999}; // imagine it being generated message_handler[message.type](message); In the case of computed go to in Fortran, it's similar. I had the "pleasure" of maintaining this once. It's been a while so I had to look up the syntax, IIRC it used something like a dispatch tree and dispatched off each digit in the type but I could be wrong: go to (0, 100, 200, 300, ...), message_type / 100 -- integer division 0 go to ... 100 go to ... 200 go to ... ...
• Sharlin 6y ago
  Yeah, but given that `mod` (if we’re talking native integers rather than some bigint type) is implemented as a single machine instruction, i’d count that as branchless for all reasonable intents and purposes even though the hardware has to internally do something equivalent to a loop to do division.
  • draganm 6y ago
    on the CPU level (I'm talking Intel here, but it applies to most other chips) DIV/IDIV instructions (returning division result and remainder a.k.a. modulo) are the ones using up the most CPU cycles. The reason for this is that they can't be completely parallelised because of having to check conditions.