1. 6

    We explored a number of these schemes for wasm. LEB128 turned out to be the best one because almost all the integers encode in a single byte, and so the branch predictor is very happy.

    With a different distribution of values, another scheme may be faster.

    1. 1

      Yes very interesting, the issue has some data sets showing that 90-94% of values are encoded in a single byte.


      Although the summary seems to be not that “LEB128 is the best one”, but that “LEB128 is more familiar and it’s not obvious that the cleverer encodings are better on real world data”, which is fair.

      And the comment linked in the issue is interesting and shows the other side, saying PrefixVarint is “massively faster”, which you would expect for other distributions: https://news.ycombinator.com/item?id=11263378

    1. 6

      He’s building Pikchr into Fossil, so you will be able to use diagrams in commit messages, tickets, and wiki pages, etc. It’s very new, I don’t think a Pikchr-enabled Fossil has been released yet.

      1. 5

        An interesting alternative to phi nodes is basic block parameters (which happen to be provably equivalent, but somewhat easier to work with).

        See here.

        1. 1

          I was really happy with how block parameters turned out for Cranelift IR. If you’re designing a new IR, I would recommend looking into it. It’s equivalent to SSA, so you can use all the same optimization techniques.

          In the register allocator, passing arguments to a block is very similar to passing arguments to a function call. This makes it a nice notation for an SSA-based register allocator.