Exploring a new data structure for the dirstate

[Siddharth Agarwal]

Oops, I made a couple of mistakes in my post.

On 01/04/2013 08:18 PM, Siddharth Agarwal wrote:
> (FWIW internal nodes are 2 pointers -- 16 bytes on x86-64 -- and I've 
> been considering ways to reduce that to 1. But even so, point taken.)

Internal nodes are actually 40 bytes on x86-64 right now. I can probably 
reduce them to 24.

> With the same ~180k file dirstate, an in-place sort on the list of 
> keys takes 0.17s when the list is completely sorted.

Ugh -- I mistakenly took the keys from the dict, not from the critbit 
tree. Sorting an almost sorted list (a few unsorted elements appended to 
the end) is pretty fast -- takes just 0.02 seconds.