[Bug 4352] New: Recursion between lazy sets during set subtraction

[mercurial-bugs at selenic.com]

http://bz.selenic.com/show_bug.cgi?id=4352

          Priority: normal
            Bug ID: 4352
                CC: mercurial-devel at selenic.com
          Assignee: bugzilla at selenic.com
           Summary: Recursion between lazy sets during set subtraction
          Severity: bug
    Classification: Unclassified
                OS: All
          Reporter: gregory.szorc at gmail.com
          Hardware: All
            Status: UNCONFIRMED
           Version: 3.1
         Component: Mercurial
           Product: Mercurial

If you have two orderedlazyset (possibly lazyset) and invoke __sub__ on them,
it's possible to get into a recursion loop and hit some O(n^2) or O(n log n)
badness.

This occurs when spanset.__sub__ isn't passed a baseset, for example.

One solution is to cache the results of self._contains in lazyset.__iter__,
just like it's done in lazyset.__contains__. See
http://selenic.com/repo/hg/file/5c153c69fdb2/mercurial/revset.py#l2338.
However, I tried this and it adds overhead and slows down the revset benchmarks
by ~10% nearly across the board IIRC.

I think the proper solution is to implement a _diffset class, much like _addset
already exists to optimize the case of adding 2 lazy sets.

I use the |(not public()) - obsolete()| revset to test this. But that obviously
requires a repo with obsolescence markers and lots of non-public changesets to
get the recursion to a point where it becomes problematic for performance.

-- 
You are receiving this mail because:
You are on the CC list for the bug.