Best data structure for fast unions of large sets of integers

[gdalle]

See this new topic for a discussion of the recursive set idea, if the performance nerds are not tired yet!

Can I speed up this recursive set implementation?

Hey there! I come to you with another performance nerdsnipe, whose solution could have a big impact on the autodiff ecosystem (via SparseConnectivityTracer.jl and DifferentiationInterface.jl). You may remember my first question on pseudo-set data structures for fast unions: One interesting proposal from that discussion (thanks @Tarny_GG_Channie) is a lazy set union, containing only pointers to the two sets it unites. I want to see how fast we can make this approach. The code below benchmar…