A possible way to fully eliminate boundary checks in union find

[QuarticCat]

Union-find operations are frequent in egg. By checking the generated ASM by cargo-show-asm, we can find that there are boundary checks everywhere. By my tests, eliminating them can get 1%-2% running time reduction. However, simply removing them can cause soundness problems. Here's a safe way to fully eliminate boundary checks.

I notice that in union-find, the internal vector can never shrink. Therefore, if we can prove that an Id comes from a union-find set, indexing it in that set must be safe. To prove this property, we can utilize the so-call "branded types" stated in this paper https://plv.mpi-sws.org/rustbelt/ghostcell/.

In egg's use case, the introduction of branded types won't hurt the usability of union-find too much. However, it needs to break the API. I don't expect you to use this technique. I'm just excited that we can do this. :)

[mwillsey]

Yes, this is definitely a neat idea. Another (easier) idea would be to assume that the "parent pointer" already in the unionfind are valid, and only check them on insertion. This way you only pay one bounds check per access.