We're updating the issue view to help you get more done. 

Faster set equivalence

Description

Equivalence calls on the core sets, PersistentHashSet and PersistentTreeSet, can be made faster by switching from every? to reduce-kv as they are both backed by maps which support IKVReduce.

A benchmark under V8:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 === PHS === Patch: [a (into #{} (range 1)) b (into #{} (range 1))], (= a b), 1000000 runs, 345 msecs [a (into #{} (range 2)) b (into #{} (range 2))], (= a b), 1000000 runs, 530 msecs [a (into #{} (range 4)) b (into #{} (range 4))], (= a b), 1000000 runs, 801 msecs [a (into #{} (range 8)) b (into #{} (range 8))], (= a b), 1000000 runs, 1497 msecs [a (into #{} (range 32)) b (into #{} (range 32))], (= a b), 10000 runs, 140 msecs [a (into #{} (range 100)) b (into #{} (range 100))], (= a b), 10000 runs, 318 msecs [a (into #{} (range 1000)) b (into #{} (range 1000))], (= a b), 1000 runs, 404 msecs [a (into #{} (range 100000)) b (into #{} (range 100000))], (= a b), 100 runs, 3411 msecs Master: [a (into #{} (range 1)) b (into #{} (range 1))], (= a b), 1000000 runs, 986 msecs [a (into #{} (range 2)) b (into #{} (range 2))], (= a b), 1000000 runs, 1488 msecs [a (into #{} (range 4)) b (into #{} (range 4))], (= a b), 1000000 runs, 2255 msecs [a (into #{} (range 8)) b (into #{} (range 8))], (= a b), 1000000 runs, 3716 msecs [a (into #{} (range 32)) b (into #{} (range 32))], (= a b), 10000 runs, 328 msecs [a (into #{} (range 100)) b (into #{} (range 100))], (= a b), 10000 runs, 928 msecs [a (into #{} (range 1000)) b (into #{} (range 1000))], (= a b), 1000 runs, 1284 msecs [a (into #{} (range 100000)) b (into #{} (range 100000))], (= a b), 100 runs, 13921 msecs === PTS === Patch: [a (into (sorted-set) (range 1)) b (into (sorted-set) (range 1))], (= a b), 1000000 runs, 504 msecs [a (into (sorted-set) (range 2)) b (into (sorted-set) (range 2))], (= a b), 1000000 runs, 690 msecs [a (into (sorted-set) (range 4)) b (into (sorted-set) (range 4))], (= a b), 1000000 runs, 1106 msecs [a (into (sorted-set) (range 8)) b (into (sorted-set) (range 8))], (= a b), 1000000 runs, 2065 msecs [a (into (sorted-set) (range 32)) b (into (sorted-set) (range 32))], (= a b), 10000 runs, 85 msecs [a (into (sorted-set) (range 100)) b (into (sorted-set) (range 100))], (= a b), 10000 runs, 315 msecs [a (into (sorted-set) (range 1000)) b (into (sorted-set) (range 1000))], (= a b), 1000 runs, 381 msecs [a (into (sorted-set) (range 100000)) b (into (sorted-set) (range 100000))], (= a b), 100 runs, 4877 msecs Master: [a (into (sorted-set) (range 1)) b (into (sorted-set) (range 1))], (= a b), 1000000 runs, 1204 msecs [a (into (sorted-set) (range 2)) b (into (sorted-set) (range 2))], (= a b), 1000000 runs, 2034 msecs [a (into (sorted-set) (range 4)) b (into (sorted-set) (range 4))], (= a b), 1000000 runs, 3471 msecs [a (into (sorted-set) (range 8)) b (into (sorted-set) (range 8))], (= a b), 1000000 runs, 7128 msecs [a (into (sorted-set) (range 32)) b (into (sorted-set) (range 32))], (= a b), 10000 runs, 260 msecs [a (into (sorted-set) (range 100)) b (into (sorted-set) (range 100))], (= a b), 10000 runs, 643 msecs [a (into (sorted-set) (range 1000)) b (into (sorted-set) (range 1000))], (= a b), 1000 runs, 718 msecs [a (into (sorted-set) (range 100000)) b (into (sorted-set) (range 100000))], (= a b), 100 runs, 8302 msecs

Environment

None

Status

Assignee

David Nolen

Reporter

Thomas Mulvaney

Labels

Approval

None

Patch

Code

Priority

Minor