Hey everyone, I did a small experiment seeing how type erased a BTree, as opposed to a generic BTree, could improve compile times. My end goal is to justify the effort of writing partially or fully type erased wrappers around the standard library datastructures. I assume that most code isn't performance sensitive and would benefit fro faster to compile datastructures.
The short story is that type erased datastructures massive outperform generic datastructures in the compile-time test (no surprise here). in release mode, the standard library version takes 6 minutes to compile while the type erased test takes 25 seconds.
What I didn't expect was the difficulty of writing such a library. At various stages, I ran into problems such as:
- std::any::Any requires a 'static trait bound
- The compiler has a lot of trouble reasoning about Box lifetimes, even after my annotation attempts
- It's sort of hairy trying to move values into and out of Box objects
I ended up writing a simplified sort of Box object to carry around my data and vtable. It's a bit hacky, but it 'works,' at least for my experiment. It makes me worry that it's much easier to write unsound interfaces to the library.
Another issue is that type erasure interacts very poorly with traits such as Hash. Hash requires that the hash member function is generic across Hasher: fn hash<H: Hasher>(&self, &mut H), making total type erasure impossible. I think passing the type erased function itself an erased closure to a fully typed function can solve this, but this still means generating more generic code. I expect iterators will have similar issues as well, but I haven't gotten so far.
Has anybody here ever tried to write such a library, and encountered safer ways of writing such code? I would like for users to have drop-in type erased datastructures to help with compile times, but at the same time without invoking too much gnarly unsafe and introducing soundness problems.