Skip to content
Snippets Groups Projects
  • Mitchell Kember's avatar
    e9ced84aeef4
    rust-ancestors: use BitSet for seen revisions · e9ced84aeef4
    Mitchell Kember authored
    This makes AncestorsIterator store its set of seen revisions in a BitSet-based
    DescendingRevisionSet instead of a HashSet. This provides faster lookups and
    insertions, and uses only A - B bits of memory when iteration goes from revision
    A down to revision B. In the worst case iterating from tip to -1 in the
    mercurial-devel changelog, for example, it would use about 7 KiB.
    
    Running rhg annotate on 200 random files in mercurial-devel gave on average a
    10% improvement. Here is the distribution:
    
     new/old  freq    histogram
    -------- |----- | ---------
        0.81 |   17 | **
        0.84 |   32 | ****
        0.87 |   23 | ***
        0.90 |   24 | ***
        0.92 |   20 | ***
        0.95 |   34 | *****
        0.98 |   18 | **
        1.01 |   24 | ***
        1.04 |    3 |
        1.07 |    5 |
    -------- |----- | ---------
    Avg=0.90 |N=200 |
    e9ced84aeef4
    History
    rust-ancestors: use BitSet for seen revisions
    Mitchell Kember authored
    This makes AncestorsIterator store its set of seen revisions in a BitSet-based
    DescendingRevisionSet instead of a HashSet. This provides faster lookups and
    insertions, and uses only A - B bits of memory when iteration goes from revision
    A down to revision B. In the worst case iterating from tip to -1 in the
    mercurial-devel changelog, for example, it would use about 7 KiB.
    
    Running rhg annotate on 200 random files in mercurial-devel gave on average a
    10% improvement. Here is the distribution:
    
     new/old  freq    histogram
    -------- |----- | ---------
        0.81 |   17 | **
        0.84 |   32 | ****
        0.87 |   23 | ***
        0.90 |   24 | ***
        0.92 |   20 | ***
        0.95 |   34 | *****
        0.98 |   18 | **
        1.01 |   24 | ***
        1.04 |    3 |
        1.07 |    5 |
    -------- |----- | ---------
    Avg=0.90 |N=200 |