ClojureScript

Faster set equivalence

Details

  • Type: Enhancement Enhancement
  • Status: Closed Closed
  • Priority: Minor Minor
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
  • Patch:
    Code

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:

=== 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

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
    Resolved: