Performance of set operations

Comparing set operations
Operations on un-balanced sets

Is it possible to improve upon the performance of Clojure's built-in set operations?

Yes, for particular scenarios. droitfintech's fset library and new utilities introduced in this library offer measurable performance improvements across a wide range of conditions.

Clojure's set namespace prioritizes straightforward, idiomatic implementations with variadic arguments.

We'll use the Criterium benchmarking facility to objectively measure the evaluation times of a range of scenarios. Our test sets will contain one to one-million elements. While spanning that range, we'll investigate the effects of overlap (i.e., the sizes of the unions and intersections) between the two input sets.

• All means that both sets contain the exact same elements; the union and intersection are identical.
• Half means that half of each set is shared with the other; the intersection is one-third of the union.
• None indicates that neither set has an element in common with the other; the intersection is empty.

Finally, we'll explore the performance implications of the two sets being substantially different sizes.

Overall, fset and this library's third variant, designated alt 3 demonstrate 10-40% speedup over Clojure's implementations. For the latter, the cost is more complex implementation and missing variadics.

This upper trio of results involve operating on two sets containing the same number of elements, from one to one-million. The first chart shows full overlap, the middle shows half overlap, and the lower shows no overlap between the elements of the two sets. Each data point represents computing the union, the intersection, the left-difference, and the right-difference.

fset (gold circles) and alt 3 (purple squares) demonstrate a modest, but consistent, 20-40% speedup over the core implementation (red triangles).

(fn [n] ((tactic) (get-in test-sets [n :left]) (get-in test-sets [n :right-all])))

Show details

(fn [n] ((tactic) (get-in test-sets [n :left]) (get-in test-sets [n :right-half])))

Show details

(fn [n] ((tactic) (get-in test-sets [n :left]) (get-in test-sets [n :right-none])))

Show details

In contrast to the upper trio of charts where both sets were the same size, these lower two charts explore what happens when the two sets are substantially different sizes.

The first of the two lower charts shows timings when the left-hand set size is fixed at one-million elements while the right-hand set ranges from one to one-million elements. Again, the two alternative implementations (gold circles and purple squares) provide modest speedups compared to the core implementation (red triangles).

The second of the two lower charts shows timings when the left-hand set size is always one-thousand times larger than the right-hand set. Again, the alternative implementations show modest 15-25% speedups.

(fn [n] ((tactic) (get-in test-sets [1000000 :left]) (get-in test-sets [n :right-half])))

Show details

(fn [n] ((tactic) (get-in test-sets [n :left]) (get-in test-sets [(/ n 1000) :right-half])))

Show details