Is hedge union always as fast as divide and conquer?

Question

Adams describes a divide-and-conquer algorithm for finding the union of two sets (represented as weight-balanced binary search trees). He then describes a then-new "hedge union" algorithm which he claims improves on the divide-and-conquer one. However, he does not offer a proof, or even a real explanation, of why it should be $O(m + n)$, let alone why it should be faster than divide-and-conquer.

Blelloch, Ferizovic, and Sun show that Adams's divide-and-conquer algorithm actually attains the theoretically optimal $\Theta (m \log (n/m + 1))$ where $m \le n$. They do not, however, address the hedge union algorithm.

Is hedge union, in fact, as efficient as divide-and-conquer? The least obvious part is the inner trim. It appears, at least superficially, to duplicate work between the left and right subtrees that the full split shares between them. Perhaps this is okay for some reason, but I don't know why.

A further inquiry: Haskell's Data.Set and Data.Map use hedge variants of intersection and difference, as well as union. I have not found any published discussion of those algorithms at all. Similar questions apply to these as well.

Answer 1

While I have yet to see, or produce, a theoretical analysis of the hedge algorithms, I do have some empirical evidence that they are worse than the divide-and-conquer algorithms for binary trees.

Starting with the code in the Haskell containers package, I optimized the hedge union algorithm by manually applying call-pattern specialization to reduce intermediate allocation. This improved its performance by about 10%, giving it a fair shot.

Starting with the divide-and-conquer code in Adams, I optimized the union algorithm by adding special cases when either of the inputs is a singleton (the hedge union code optimizes one side thus, and it's not clear if the other side can be optimized similarly).

I tested each implementation using a collection of set operation benchmarks packaged with containers. Divide-and-conquer was usually faster than hedge, sometimes twice as fast. When it was slower, it was only slightly so.

Similar benchmarks of other set operations gave similar results.

---

Speculation:

Hedge algorithms may be helpful when using trees with a large branching factors, which may be more expensive to split recursively. They may also be helpful for small subtrees, where they may save enough allocation to be worth the extra work.