1. 21

  2. 6

    Thorough work. Going back to the premise, I want to offer an alternative viewpoint by asking whether, in the case of binary trees implemented by arrays, “integer division by 2” of the array index is necessarily the best interpretation of what you are trying to do here?

    Instead, you can also see the array index as a bit string, where every bit tells you which path to go down, left or right. In that case, “shifting right by one bit” moves you up to the parent. “Shifting left” moves you down to the left child. Flipping one bit flips you over to the other child. Bit wise operations indeed seem more natural with that interpretation.

    A lot of “power of 2” multiplication/division has similar interpretations. For example, when walking page tables, you could see walking down the levels as “dividing by the size of the granule”, or simply as “shifting right to select the index on that level”.

    No contest on anything where the power of 2 is coincidence, i.e. for non “computery” things where there is no such underlying structure.

    1. 1

      Sometimes you want code to run reasonably fast in debug mode.

      Also, unless the instruction interpreter is converting the div by an immediate into a shift, which would surprise me, you’re almost certainly better off using a shift. Micro benchmarks can be very misleading on modern microarchitecture.

      1. 1

        I love this kind of work. Well done!

        I guess it’s a remnant, like many others, of old practices which made sense with older hardware but that now it’s less useful.

        Even today I try to turn divisions into multiplications, even if that probably has a very tiny effect on most modern machines.