[PATCH 2 of 4] log: do not walk the entire revision window when it's bigger than required

Nicolas Dumazet nicdumz at gmail.com
Wed Apr 28 00:08:25 CDT 2010


2010/4/28 Matt Mackall <mpm at selenic.com>:
> On Mon, 2010-04-26 at 14:53 +0200, Benoit Boissinot wrote:
>> On Mon, Apr 26, 2010 at 12:06:10PM +0900, Nicolas Dumazet wrote:
>> > # HG changeset patch
>> > # User Nicolas Dumazet <nicdumz.commits at gmail.com>
>> > # Date 1272014685 -32400
>> > # Node ID d16d31df0b0dfba503fc1f68b8eb32df59ed396d
>> > # Parent  093655bea24814baf545b76ff154accfdc49d1c4
>> > log: do not walk the entire revision window when it's bigger than required
>> >
>> > When a [minrev, maxrev] revision interval is required, we first walk forward
>> > the filelog in a windowed manner, accumulating revisions, and then yield those
>> > revisions in reversed order.
>> > We used to forward-walk the full filelog, not using the revision range
>> > information; and then filter revisions matching the range during the second
>> > step.
>> >
>> > We can, however, use the "maxrange" hint during the first step, to stop our
>> > forward-walk early. Depending on the size of the current window, it saves us
>> > 8 to 512 filelog node reads.
>>
>> Does it work with "crossed" linkrevs? (linkrev are not guaranteed to be
>> monotonic)
>
> Yeah, I think that's a problem. Nic?

I talked a bit about it with Benoit on IRC.

I admit that I still have difficulties to wrap my mind around
non-monotic linkrevs. I see the output of test-strip-cross and it
helps to see that it indeed happens. But the way the revisions are
created is a bit too cryptic to allow me to think about it.

I do think however, that this serie does not change a thing with this
regard. The current code indeed seems broken, now that I'm told about
"crossed" linkrevs.
But my code does not change much, it only moves a comparison earlier:

before:

def iterator1():
    stack = []
    for i in baseiterator():
        stack.append(i)
    for i in reverse(stack):
        yield i
def iterator2():
    for i in iterator1():
        if rev(i) <= maxrev:
            yield i

after:

def iterator1():
    stack = []
    for i in baseiterator():
        if rev(i) > maxrev:
            break
        stack.append(i)
    for i in reverse(stack):
        yield i
def iterator2():
    for i in iterator1():
        yield i

The resulting output is the same, isnt it? Only the generation is
stopped earlier in the second case. Or am I missing some point? :)



But if the idea is to rewrite walkchangerevs, we can as well drop this
patch and #3, and I'll just resend a rebased #4?

Cheers!

>
>> Or was it already "broken"?
>
> Probably always broken.
>
> The real problem here is that the whole walkchangerevs thing sucks.
> First, filtering should be done in two passes - all the easy index-only
> stuff followed by walking over the expensive revs. Second, it's way too
> log-specific.
>
> --
> http://selenic.com : development and support for Mercurial and Linux
>
>
>
>



-- 
Nicolas Dumazet — NicDumZ


More information about the Mercurial-devel mailing list