Post: Experimenting with type-erased datastructures

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.

1 Like

This is better posted on users.rust-lang.org, internals is about developing the Rust language, not general posts about Rust

Ok, mods feel free to delete this - my reasoning was that rust-users mostly seemed to be help questions, while I found some posts here with discussion along similar lines - libraries and wrappers over core stdlib functionality.

This sounds like something polymorphization would help with?

1 Like

It looks similar, but I think somewhat different. From what I can tell polymorphism is trying to prevent monomorphizing functions where the type parameter isn't used. However, I want to accomplish something similar where the type parameter is used!

Having compiler support would make this much easier, but that would imply implicit autoboxing which I don't think belongs in Rust.

Polymorphism might help here if the compiler could detect that a datastructure implementation only ever uses the types for typechecking and virtualized everything else, but I would be wary of hoping compiler magic could prevent monomorhpization here.

1 Like