Add fast path in seq comparison for structurally sharing seqs

Question

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

Answer 1

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?

Answer 2

Comment made by: michaelblume

like so =)

Answer 3

Comment made by: bronsa

Makes sense, thanks for the updated patch

Answer 4

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.

Answer 5

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.

Answer 6

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)

Answer 7

Comment made by: bronsa

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

Answer 8

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