Const Generics & Struct Members (why is it different to features?)

I am currently writing code which is intended to become a highly-optimized library later on.
One of these intended optimizations are Const Generics, in order to compile away branches and avoid potential mispredictions during runtime and unnecessary calls/instructions.

To give some more context, the struct I am about to post is intended to be used in either a cached or non-cached mode (the latter always reading from the file, which is higher IO).
Both variants must be instantiable, because I need that for the planned CLI tool.

My old implementation was this:

pub struct MPQ {
    file: Option<File>,
    cache: Option<Vec<u8>>,
// other members and functions
}

This of course requires checking cache at runtime if it is Some and also unwrap().

I already know that I can rewrite it as this, which allows me to optimize away the if statement at least, by using CACHED as expression:

pub struct MPQ<const CACHED: bool> {
    file: Option<File>,
    cache: Option<Vec<u8>>,
// other members and functions
}

What I would like to also get rid of is Option, so I do not have to unwrap().

// when CACHED is false, the struct only has file
pub struct MPQ<const CACHED: bool> {
    file: File,
// other members and functions
}
// when CACHED is true, the struct only has cache
pub struct MPQ<const CACHED: bool> {
    cache: Vec<u8>,
// other members and functions
}

I know it is also possible to use a generic type instead, to handle a member dynamically as File or Vec, but I would prefer the bool approach.
It is more ergonomic for me, but it is also more generic (hehe), since this could be used without a type required (turning behavior off and on).

Interestingly enough Rust already provides the cfg attribute, which allows dynamic members by defining custom features.

pub struct MPQ<const CACHED: bool> {
    #[cfg(feature = "cached")]
    cache: Vec<u8>,
// other members and functions
}

But I can not use that, since I need both variants at the same time in my code.
I don't understand why this is possible with features, but not const generics, as both are evaluated at compile time, no?
From what I understood, for the compiler MPQ<true> and MPQ<false> would be entirely different types, and thus can have a different set of members etc.
At least right now I do not see a reason why it is possible with one, but not the other.

Maybe you could try an enum which contains both File and Cache variants and given the match statement only takes one branch the branch predictor should have minimal misses if any. I'm not sure if it's possible to save on the total struct size like you are trying to do, since the struct size must be constant at compile time and since it could either contain File or Cache it must at least be large enough to contain the largest of the variants.

Example: Rust Playground

The const generic system isn't that rich. The type system as a whole isn't that rich; a given type constructor always has the same set of fields (which may differ by type, but not by name).

You can code this concept into the type system, though it may not be ergonomic to use.

pub trait MpqStorage {
    type Ty;
}

impl MpqStorage for Mpq<true> {
    type Ty = Vec<u8>;
}

impl MpqStorage for Mpq<false> {
    type Ty = File;
}

pub struct Mpq<const CACHE: bool> where Self: MpqStorage {
    storage: <Self as MpqStorage>::Ty,
}

But I would sooner just go with type generics.

pub struct Mpq<Storage> {
    storage: Storage,
}
4 Likes

You could something like:

struct Foo<const BAR: u8> {
    bar: [Bar; BAR]
}

This will make the bar field zero-sized for Foo<0>. The only problem is, you can't do that with a bool, and so nonsensical values above 1 are possible.

But the size would be constant for MPQ<true> and MPQ<false> respectively, which is fine, since they are distinct types, or am I getting this wrong?

Got it - that's unfortunate.
I will keep your proposed solution in mind and will test it when I come back home later tonight.

Do you happen to know what the best/proper way is to contact the Rust dev team?
Yesterday I found some other places which were looking for the same or very similar things as me after posting this thread here, by rephrasing my search - seems I am not the only one.
It would be neat to have written statement by development why this is currently not possible, or if it will never be possible because of $REASON.
This hopefully would be found by others searching that topic, and preventing them to ask the exact same question again ^^

I don't understand why this is possible with features, but not const generics, as both are evaluated at compile time, no?

Features and const generics are extremely different things. The former has nothing to do with the type system and is essentially a purely syntax-level preprocessing step. Parsing vs semantic analysis, two stages in your standard issue compiler architecture that are typically intentionally separated into as discrete steps as possible. "Compile time" is not a single thing.

3 Likes

Thanks, I will keep this in mind, since it might potentially come in handy in other scenarios.
For this one I am trying to prevent the member from being part of the struct completely, since this would also prune it away from IDE autocompletion (users will be less confused, if they do not get offered zero sized members for usage).

Yes, I know that features and const generics are two distinct things.
What I was trying to say is, that both of them are evaluated during the compilation, which in theory could give them the same capabilities (if implemented).
This thread is more or less asking why it is not possible with const generics at all, or if I am simply too dumb to properly do it and there actually is a way.

Zulip or to some extent IRLO or perhaps via Github, depending on the situation.

That said, documented guarantees have to pass a vote ("FCP"), significant changes have to go through RFC, and there's not always a good place to document non-guaranteed but generally agreed upon things or "vibes". And a guarantee that some language development will never be possible seems unlikely.[1] So I don't know how achievable your goal of getting this particular issue written up is... or how productive trying to hit up the devs directly would be.

This forum was a good place to ask. The reference may be a good place to ask for more documentation. Some const generic limitations are already documented.

Pretty much everything is done on a volunteer basis, so things may move quite slow without a champion.

My trait approach wouldn't be so bad with implied bounds. Those have downsides of their own, but at least there's enough interest that it was RFC'd. Or with some sort of exhaustive const generic type checking I guess (so you could drop the where Self: MpqStorage bound entirely as it's always satisfied).

Anyway I think it's enough to show that something close is possible today, but not ergonomic. Improving ergonomics may be possible in the future. I doubt we'll get actual optional fields based on generics, as they'd be pretty limited. Consider the analogous situation in terms of function items.[2] Without some significant new language development, type-dependent optional fields would not be usable in generic context.


  1. It's hard in general to document everything that isn't possible... ↩︎

  2. n.b. Rust tries to avoid post-monomorphization errors, preferring instead to prove that generic functions will work with any parameters that meet the bounds. ↩︎

They would just ask a different question. The whole topic was discussed, back and forth, for years.

That's the core thing: how distinct are they? Rust's generics and C++ templates give different answers.

Sure, when you look on MPQ<true> and MPQ<false> in isolation and promise to never, absolutely never to try to use them in the same code… you can just use MPQ_true and MPQ_false and call it “done”. Or use features, which also guarantee that code for different cases if never used at athe same time.

But, well… that's not how one wants to use generics or templates.

For MPQ<true> and MPQ<false> to have some advantage over MPQ_true and MPQ_false there have to be some code that accepts MPQ<x> where x is not true or false, but some unspecified constant.

And that's where C++/Zig go to the right and Rust goes to the left[1]: C++/Zig say, essentially “template function is just a template, we would just instantiate it for a given type and check if it works” while Rust says “hey, you plan to use MPQ<x> somewhere… but how? I want to ensure that if someone looks on the signature s/he would immediately know if it would work or not”.

Rust's approach is great… when it works. When it doesn't… you can emulate C++ approach, actually, but because of issue #77125 it's extremely unergonomic and tedious. I can write some more if you are interested, but ingridients are, essentially, type_id (manually implemented if you want for the code to work on stable, or via const_type_id on nightly), static_assert (spelled as const { assert!(…); } in Rust and working like it would in C++ or Zig), if const (looking similar to what you have in C++ with if constexpr, but working very differently), transmute_copy (extremely scary function with very few safety guarantees, but used only in most trivial fashion and [ab]using the fundamental property of Rust's types that, literally, says: “every type must be ready for it to be blindly memcopied to somewhere else in memory”) and, finally, ManuallyDrop.

Yes, it works, you can imitate C++ approach almost perfectly… but that's extemely tedious (although, perhaps, someone may create nice wrapper? I don't want to try to do that till issue #77125 because without it ergonomic would be awful, anyway). Till then you may use some kind of tricks. For you use-case you can just use alias:

pub enum Marker<const CACHED: bool>{}

pub trait MyTypes {
    type MPQ;
}

mod marker_true {
    pub struct MPQ {
        cache: Vec<u8>,
    }
}

mod marker_false {
    pub struct MPQ {
        file: File,
    }
    use std::fs::File;
}

impl MyTypes for Marker<true> {
    type MPQ = marker_true::MPQ;
}

impl MyTypes for Marker<false> {
    type MPQ = marker_false::MPQ;
}

pub type MPQ<const CACHED: bool> =
    <Marker<CACHED> as MyTypes>::MPQ;

It's a bit more boilerplatey than @quinedot's approach, but nicely separates implementation for true and false – and also provides place to put all the implemntations that work with one type and with the other type.


  1. Or is it the other way around?… they go in different directions, at least. ↩︎

1 Like

It seems like the right thing here is probably to lean on branch prediction, but if you really need the cache not to be there, you can do something like:

trait Cache {
    fn get(&self, key: usize) -> Option<u8>;
    fn fill(&mut self, key: usize, value: u8);
}

struct MemoryCache {
    cache: Vec<u8>,
}
impl Cache for MemoryCache { ... }

struct NoCache;
impl Cache for NoCache {
    fn get(&self, key: usize) -> Option<u8> { None }
    fn fill(&mut self, key: usize, value: u8) {}
}

and then make your code generic on a Cache type.

Thanks to everyone who chipped in with their suggestions and solutions.
I have got it running, and it already paid off by reducing runtime a few percent (even though everything runs on NVMe already).

Now I try to write a more convenient wrapper which is reusable and could help others facing the same issue as well: will do this in a separate new thread though and link here.
It would shift the burden of implementation/handling to the wrapper definition, away from the specific project implementations.

I now also have a better understanding of why some things are possible via features, but not const generics.
For anyone wondering: the thing I tried to achieve here is having a compile-time optimized handling for reading from a file.
Systems with low memory can simply use File and read/write from a file on disk directly, while systems with vast memory (running in a separate optimized codepath) can load the entire thing into memory, reducing IO/latency, most of all when it is on old spinny HDDs.

This is what I got now in my current project, in case anyone stumbles in here:

trait DataSource {
    type Type: Debug;
    #[inline]
    fn read(&self, offset: usize, length: usize) -> Vec<u8>;
}

#[derive(Debug)]
#[repr(C)]
pub struct MPQ<const CACHED: bool>
where
    Self: DataSource,
{
    source: <Self as DataSource>::Type,
    header0: Option<Header0>,
    header1: Option<Header1>,
    hash_tbl: Option<Vec<HashRow>>,
    block_tbl: Option<Vec<BlockRow>>,
}

impl DataSource for MPQ<false> {
    type Type = File;

    #[inline]
    fn read(&self, offset: usize, length: usize) -> Vec<u8> {
        let mut buffer = unsafe { vec_no_init::<u8>(length) };
        self.source
            .seek_read(&mut buffer, offset as u64)
            .unwrap_or_else(|error| {
                panic!(
                    "reading 0x{:X} Bytes at 0x{:08X} from file: {}",
                    length, offset, error
                );
            });
        buffer
    }
}

impl DataSource for MPQ<true> {
    type Type = Vec<u8>;

    #[inline]
    fn read(&self, offset: usize, length: usize) -> Vec<u8> {
        let mut buffer = unsafe { vec_no_init::<u8>(length) };
        buffer.copy_from_slice(&self.source[offset..offset + length]);
        buffer
    }
}

#[inline(always)]
pub unsafe fn vec_no_init<T>(size: usize) -> Vec<T> {
    let mut vec = Vec::with_capacity(size);
    vec.set_len(size);
    vec
}

If your fn vec_no_init is something like

fn vec_no_init(len: usize) -> Vec<u8> {
    let mut v = Vec::with_capacity(len);
    v.set_len(len);
    v
}

it is unsound, and your code has UB[1]; u8 is not allowed to be uninitialized. The Vec case wants Vec::extend_from_slice, and the IO case needs to rely on std using the unstable read_buf API to avoid redundant initialization without optimization.


  1. At least at the library level. At the language level, this relies on undecided details (whether dropping a type without drop glue asserts it to be byte valid). ↩︎

1 Like

right now I have rewritten vec_no_init as this:

#[inline(always)]
pub unsafe fn vec_no_init<T>(size: usize) -> Vec<T> {
    let mut vec = Vec::with_capacity(size);
    vec.set_len(size);
    vec
}

I made the function as a whole unsafe, instead of having an unsafe block inside it.
It is intended to only be used, if I as the programmer, can trivially assure that every element is initialized in the following code.
The compiler can optimize away the initialization in certain cases, if it is able to determine so at compile-time.
This is just a little optimization to force the drop of initialization.

In your example the set_line() call does not work, because the function is missing the unsafe keyword, and also that line is not wrapped in it.
I have rewritten my exampe above and added the definition of vec_no_init as well, that slipped my sight last time :stuck_out_tongue:

This function is also unsound (except in certain special cases about T that are not usually relevant). Read the documentation of set_len():

Safety

  • new_len must be less than or equal to capacity().
  • The elements at old_len..new_len must be initialized.

This means that the elements must be initialized before you call set_len(), not after.

2 Likes

you are of course correct - in my case i need it for pure data u8 buffers (dunno why I wrote it as generic).
thanks for pointing out the details, I will once again rewrite it in my code.

Except u8 is also not one of those special cases. Uninitialized bytes does not mean arbitrary bytes.

3 Likes