Experimenting with type-erased datastructures

1

Moved into rust-users at the suggestion of rust-internals users.

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.

https://vgatherps.github.io/2020-04-14-erasure/

2

The design of Rust is such that type erasure goes "against the grain of the language" as well as its intent (i.e. safety), so to speak. As such I expect that not many people will attempt to create or use type-erased generic types. Essentially, in terms of safety it's going back to the days of Java 1.4.

As for the question, yes a safer alternative to type-erased generic types exists but it's exactly what you're trying to get away from: generic types.

3

There's not necessarily a reason that the interface must lose type safety or be non-generic. The goal is to erase types from the internals of the implementation, leaving type-safe interface and marshalling code.

My worries lie in that here, one totally must trust the interface to enforce all the constraints. The implementation will wipe that away removing a sanity check by the compiler.

4

I understand your wish for faster compile times, I share that same wish.
But personally I do not consider sacrificing safety for compile time a good tradeoff, even if it is "only" for implementation internals (which is the bulk of the code pretty much always).

5

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.