| # I happened to be looking at some of Cranelift's code, and I noticed that their constant-time dominates() | |
| # check was using a somewhat more ad-hoc version of a hidden gem from the data structures literature called the | |
| # parenthesis representation for trees. As far as I know, this was invented by Jacobson in his 1989 paper | |
| # Space-Efficient Static Trees and Graphs. I first learned about it from the slightly later paper by Munro and Raman | |
| # called Succinct Representations of Balanced Parentheses and Static Trees. I figured I'd give it an extremely | |
| # quick intro and then show how it leads to a (slightly better) version of Cranelift's algorithm. | |
| # | |
| # This parenthesis representation of trees is surprisingly versatile, but its most striking feature is that | |
| # it lets us query the ancestor relationship between two nodes in a tree in constant time, with a few instructions. | |
| # And the idea is extremely simple and intuitive if you just draw the right kind of picture. |
To make things easier, we can tell git to use the PuTTY tools rather than the built in ssh client. The PuTTY tools include an identity manager and an SSH replacement.
Follow these four steps:
Download and install PuTTY using the MSI installer package from the PuTTY download page. Alternately, you can just get the "PLink" and "Pageant" executables from the same page and save them somewhere in your path.
Add a new user or system environment variable:
sysdm.cpl