Add documentation on the reasoning

Explains the thought process behind adding the union algorithm and
discusses the alternative and heuristic behind.

1 files changed, 14 insertions, 4 deletions

diff --git a/src/librustc_data_structures/bit_set.rs b/src/librustc_data_structures/bit_set.rs
index 08b7185dbe2..e626f4333d9 100644
--- a/src/librustc_data_structures/bit_set.rs
+++ b/src/librustc_data_structures/bit_set.rs
@@ -557,10 +557,20 @@ impl<T: Idx> HybridBitSet<T> {
                         changed
                     }
                     HybridBitSet::Dense(other_dense) => {
-                        // `self` is sparse and `other` is dense. Clone the
-                        // other set and do the bitwise union with sparse
-                        // `self`. This avoids traversing the dense
-                        // representation twice.
+                        // `self` is sparse and `other` is dense. To
+                        // merge them, we have two available strategies:
+                        // * Densify `self` then merge other
+                        // * Clone other then integrate bits from `self`
+                        // The second strategy requires dedicated method
+                        // since the usual `union` returns the wrong
+                        // result. In the dedicated case the computation
+                        // is slightly faster if the bits of the sparse
+                        // bitset map to only few words of the dense
+                        // representation, i.e. indices are near each
+                        // other.
+                        //
+                        // Benchmarking seems to suggest that the second
+                        // option is worth it.
                         let mut new_dense = other_dense.clone();
                         let changed = new_dense.reverse_union_sparse(self_sparse);
                         *self = HybridBitSet::Dense(new_dense);