Welcome! Please see the About page for a little more info on how this works.

0 votes
in Collections by

Currently comparing two non identical seqs requires iterating through both seqs comparing value by value, ignoring the possibility of seq a and b having the same (pointer-equal) rest.

The proposed patch adds a pointer equality check on the seq tails that can make the equality short-circuit if the test returns true, which is helpful when comparing large (or possibly infinite) seqs that share a common subseq.

After this patch, comparisons like
(let [x (range)] (= x (cons 0 (rest x))))
which currently don't terminate, return true in constant time.

Patch: CLJ-1679-v3.patch

8 Answers

0 votes
by

Comment made by: michaelblume

When this test fails (it fails on my master, but I've got a bunch of other development patches, I'm still figuring out where the conflict is), it fails by hanging forever. Maybe it'd be better to check equality in a future and time out the future?

0 votes
by

Comment made by: michaelblume

like so =)

0 votes
by

Comment made by: bronsa

Makes sense, thanks for the updated patch

0 votes
by

Comment made by: michaelblume

Hm, previous patch had a problem where the reporting logic still tries to force the sequence and OOMs, this patch prevents that.

0 votes
by

Comment made by: michaelblume

ok, looks like CLJ-1515, CLJ-1603, and this patch, all combine to fail together, though any two of them work fine.

0 votes
by

Comment made by: michaelblume

(And really there's nothing wrong with the source of this patch, it still works nicely to short-circuit = where there's structural sharing, it's just that the other two patches break structural sharing for ranges, so the test fails)

0 votes
by

Comment made by: bronsa

I see, I guess we'll have to change the test if the patches for those tickets get applied.

0 votes
by
Reference: https://clojure.atlassian.net/browse/CLJ-1679 (reported by bronsa)
...