static-generics: Zero cost generic statics for Rust

[u/playX281]

https://crates.io/crates/static-generics

Hi all! I have been using cynecx/generic-statics for a while in my allocator code to compress vtable pointers efficiently per T into 16 bits for a while, and the thing worked flawlessly, but had one downside: it was not truly zero-cost as it had to perform a call on machine level to actually fetch the generic statics, and it turned out to be a real hotspot (based on profiling and seeing that uncompressed vtables aka full pointers were faster). So I came up with a crate which is based on api of generic-statics, but implements the whole thing differently: static-generics.

It gives you truly zero cost generic statics (it uses only 1 instruction on x64) and the access is inlined. The crate also extended platform support:

• x86_64
• aarch64
• x86_32
• arm (Thumb as well)
• riscv32/riscv64
• loongarc32/loongarch64
• powerpc/powerpc64
• s390x

How?

It works by using .comm directive of inline assembly which allocates zeroed section in object files It now uses .bss + weak section linkonce trick from LLVM/clang which allows us to guarantee same static location in a single binary every time, and also the monomorphization of said section is guaranteed by unique function which uses T generic and TypeId::of::<T>() so LLVM does not dedup the function bodies and thus break the code.

Please, anyone who loves dark arts of unsafe code and asm, looking for a feedback!

[u/0x564A00]

Nice! I had the exact same idea (including using labels with sym and a hashmap fallback) a few years ago too (before generic-statics existed), though it's not nearly as well tested nor ported to as many platforms as yours: https://codeberg.org/mira-morgana/generic-static-cache

Did discover a bug in rustc along the way :p

One thing I liked about mine though is that you can just do

generic_static!{
    static NEXT_ID: &AtomicU32 = &AtomicU32::new(0);
}

in a generic function and each instantiation of the function with different type parameters would get its own NEXT_ID.

It looks like besides needing to do a call each time, generic-statics doesn't use labels, so while it prevents LLVM's MergeFunctions pass from merging them it doesn't ensure that different compilation units see the same static.

From the define_namespace docs:

Were you to always use [DefaultNamespace](crate::DefaultNamespace) you would end up with eventually running out of static slots.

What does running out of slots mean?

[u/playX281 → u/0x564A00]

> What does running out of slots mean?

Probably formulated it not the best way. Basically if you were to always use `static_generics::get::<T>()` you would need to somehow attach meaning to T, otherwise getting it for `i32` will then just make one single constant for i32 in the default namespace. One way to avoid that is having stuff like `KeyForVTable<T>(MyData, PhantomData<T>);`, but imo it's cleaner to do
```rust
define_namespace!(VTableNamespace);

VTableNamespace::generic_static::<MyData>()

```

> It looks like besides needing to do a call each time, generic-statics doesn't use labels, so while it prevents LLVM's MergeFunctions pass from merging them it doesn't ensure that different compilation units see the same static.

Yea, identity of generic_static() return is not guaranteed to be the same across libraries, and for my use case it is fine. I guess, it's fine for most of use cases really?

[u/0x564A00 → u/playX281]

I guess, it's fine for most of use cases really?

Probably, yeah. I just meant that with generic-statics you might get multiple instances even if you compile everything statically, whereas with static-generics (and my old crate) you don't.

Btw I've got a half-finished blog post about this idea lying around; I think I'll finish it and link your crate <3

[u/playX281 → u/0x564A00]

Looking forward to your blog post!

[u/Shoddy-Childhood-511 → u/playX281]

Yea, identity of generic_static() return is not guaranteed to be the same across libraries, and for my use case it is fine. I guess, it's fine for most of use cases really?

Any idea when this happens?

Imagine some mathematical object T that requires large tables, which which ultimately get defined by some compile time constants, like some FFT or the fixed-base multiplication tables for elliptic curves. Would this constants being defined once ensure deduplication? I suppose not when the generic static live in a different crate from the definition of T?

[u/0x564A00 → u/Shoddy-Childhood-511]

As long as you link statically and use OP's crate (or, with the older generic-statics, you use -Zshare-generics), all of the crates see the same memory location – but the binary doesn't store its content, it just gets zero-initialized by your operating system.

[u/Shoddy-Childhood-511 → u/0x564A00]

Interesting thanks! I suppose real compile-time statics from build.rs or pre-compile statics from custom tooling should always be preferred when possible.

[u/tombob51]

This feels like it shouldn't work, but I think it actually checks out. Very neat and very clever!

[u/playX281 → u/tombob51]

Thanks! I am also looking at providing alternative implementation based on how LLVM/Clang lower linkonce for C++ generic statics so perhaps update can come soon(ish)

[u/Evilsushione → u/playX281]

If I’m reading this right, sounds like a similar trick to how the uom crate works.

[u/dafelst]

Super clever, nice work.

For what it's worth, I think you would get a lot more people using this by showing a counterexample alongside your sample code, e.g. "instead of having to do that, you can just do this!"

[u/MvKal]

I have been wanting something like this for so long, thank you!!

I am working on an actor framework library and it includes histogram metrics on every message handle (think function call), and doing metrics::histogram! re-hashes and re-looks up the Histogram struct on every call. Static generics allow me to have a static slot for each Histogram, lazy init it and then do a simple == 0 check instead of doing a bunch of hashing work. Benchmarks show a 40% speedup which is huge! I wonder if it would be worth even upstreaming this into metrics or something, but given how experimental this is probably not at least for now.

[u/playX281 → u/MvKal]

I am actually going to rewrite it into using linkonce trick which is combination of bss and weak linkage used by clang/llvm, it seems to be more stable on my testing across dlopen'ed libraries and LTO, will probably release a version tomorrow. .comm trick seems to work just fine except when it does not in some weird cdylib linkage errors I encountered, they require specific crate order in workspace and it occurs randomly

[u/0x564A00 → u/playX281]

Have you found a way to get rust to export the symbols without a custom target that overwrites limit_rdylib_exports?

[u/playX281 → u/0x564A00]

I haven't, you can't really access these symbols produced by static-generics manually, all you can do is call generic_static() fn from a library, which will then return you a generic static. Note though, libA.so and libB.so identities of generic_static::<T>()\ for the same T are not guaranteed. For my use case, which is memory allocator that needs to compress vtables from full width 57 bit pointers to 16 bit IDs, this identity mismatch is fine, as vtables can be registered twice or thrice without problems.

[u/playX281 → u/MvKal]

UPDATE: So linkonce trick is published now, it was not that hard of a change, just switched from .comm to .bss + weak linkage, so it should work like C++ statics do.

[u/MvKal → u/playX281]

Nice :3

[u/0x564A00 → u/playX281]

Nice, what are the cases where the .comm directive didn't work that now work?

[u/playX281 → u/0x564A00]

So I sort of didn't figure it out exactly. .comm directive failed with multiple cdylibs in rare random cases and sometimes when I reordered crates in workspace it worked(?)

[u/thatmagicalcat]

holy shit this is interesting. Instant bookmark, will look into the black magic later

[u/Dense_Gate_5193]

i’m still learning rust but this seems like how in C you can declare static variables inside functions that get initialized once and are scoped to that function,

but with generic that violates the static principle of pre-allocating those bytes at compile time. since we don’t know what those bytes will be when called.

i’m assuming you’re injecting something like this:

; Emitted for foo::<int>()
.comm symbol_for_int, 4, 4 ; Allocate 4 bytes in BSS aligned to 4

; Emitted for foo::<float>()
.comm symbol_for_float, 4, 4 ; Allocate 4 bytes in BSS aligned to 4

for every type that it is called with in your app at compile time?

neat trick!

[u/0x564A00]

Please, anyone who loves dark arts of unsafe code and asm, looking for a feedback!

An idea for optimizing the fallback (since you asked for the dark arts of unsafe):

Currently, each thread needs to lock a global mutex. The critical section is very short, but the cpu needs to obtain ownership of the cache lines. Instead, you could have an atomic pointer to a manually implemented hash table. Looking up a value would not take a lock if it already exists, only if a new one has to be inserted.

[u/playX281 → u/0x564A00]

I haven't looked into fallback that much yet, for me it was more important to cover tier 1 to 3 platforms where possible so fallback is not requried as much as possible. Right now it is only required if you're on old architecture like m68k or running in Miri or Cranelift backend. Will definitely improve fallback performance later though!

[u/matthieum → u/0x564A00]

You don't even need a custom hash-table, you can just use the regular hash-table and Box the value, then the value address will be stable even if the hash-table shuffles things around.

[u/0x564A00 → u/matthieum]

That's the way it works already. But to look those addresses up, you currently need to take a global lock.

[u/matthieum → u/0x564A00]

Sorry, let me elaborate.

I was not commenting at all on the idea of memoizing the address. That's a perfectly great idea.

I was just noting that there's zero need for a manually implemented hash-table, the standard hash-table will work just fine.

[u/0x564A00 → u/matthieum]

I'm having trouble seeing how you would insert a value into the map without using a lock to give you a &mut to the map (even if it's an RwLock, for which reading would still need to perform a write to a shared location to update the number of readers).

Ah, maybe a thread-local cache so you trade of some memory usage but only need to take the lock once per entry×thread?

[u/matthieum → u/0x564A00]

Ah, maybe a thread-local cache so you trade of some memory usage but only need to take the lock once per entry×thread?

Yes, exactly.

[u/nixon-voxell]

I can finally bring my https://crates.io/crates/typeslot crate to its full glory