2 ms·

So you need to do a binary search but you don't want to use division instructions. The funny thing is that DEC's assembler for the PDP-10 did a very similar th

So you need to do a binary search but you don't want to use division instructions. The funny thing is that DEC's assembler for the PDP-10 did a very similar thing to set up the binary search of its symbol table, which was its critical path. The JFFO instruction (Jump on Find First One) was added to the PDP-10 instruction set for this purpose.

fanf2 2y ago
Binary search is easy because division by two is just a shift. It doesn’t need any division or even multiplication instructions. I can guess why they might have used JFFO but it seems needlessly complicated. I wonder why libcxx doesn’t use multiplication for modular reduction. https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-...
- FrankWilhoit 2y ago
  The trick is quickly finding the largest power of two that is less than the size of the table. It was done with two instructions: the second was the JFFO, the first was an FADD with a purposely denormalized operand. The symbol table was kept sorted on every insert.
  - fanf2 2y ago
    That was my guess :-) But binary search doesn’t need explicit powers of two. I wonder if maybe the PDP10 is much faster at loops with explicit counters instead of comparing the search upper and lower bounds.
    - FrankWilhoit 2y ago
      No, the loop would have been slower. That is why they found the starting point with that bizarre two-instruction sequence. For any table size between (2^^n)+1 and 2^^(n+1), inclusive, it returned 2^^n as the starting point. Then of course it had to loop after that.