How to specify the concrete type of a function, needed for a generic argument

I've been trying to wrtite a structure that finds TopN elemements in a collection:

pub struct TopN<const N: usize, Item, Key, KeyFn>
where
    Key: Ord,
    KeyFn: FnMut(&Item) -> Key,
{
    // Keeps top-n items, sorted descending
    array: SmallVec<[Item; N]>,
    key: KeyFn,
}

The general case is easy - it takes a function from outside, so the compiler can figure out the Key and KeyFn types:

impl<const N: usize, Item, Key, KeyFn> TopN<N, Item, Key, KeyFn>
where
    Key: Ord,
    KeyFn: FnMut(&Item) -> Key,
{
    pub fn by_key(f: KeyFn) -> TopN<N, Item, Key, KeyFn> {
        TopN {
            array: SmallVec::new(),
            key: f,
        }
    }
...

But then I'd like to also make it work for a special case, where the function is just identity, so I'd like to have a special constructor new() that doesn't take a function:

type IdentityFn<T> = fn(&T) -> T;
pub fn identity<T: Copy>(item: &T) -> T {
    *item
}


impl<const N: usize, Item> TopN<N, Item, Item, IdentityFn<Item>>
where
    Item: Ord + Copy,
{
    pub fn new() -> TopN<N, Item, Item, IdentityFn<Item>> {
        TopN {
            array: SmallVec::new(),
            key: identity::<Item>,
        }
    }
}

This compiles and works, but runs into a performance problem, because now it takes a pointer to a function. But I'd like to specialize it for my concrete identity function. How do I do that?

I guess I need sth like:

type IdentityFn<T> = concrete_type_of(identity::<T>);

Is it possible?

If you want to specialize something then it's pretty obvious that said process would be called a specialization.

Indeed, Rust have such thing (on nightly). Alas, it's not even on Rust 2024 roadmap.

Is this what benchmarks have shown? How do you run them? This sounds more like big in optimizer than the need for specialization.

If you want to specialize something then it's pretty obvious that said process would be called a specialization.

But that's something much more sophisticated and more general than I need. I thought in specialization, I could write different custom code depending on the types - and this is not what I need here.

Here I just need to generate a single concrete implementation for a single concrete function type - this is what generics do, but I haven't figured out how to specify the input type.

Is this what benchmarks have shown? How do you run them? This sounds more like big in optimizer than the need for specialization.

Yes. 4x difference, benchmarked with criterion. Not sure if it really is a bug in the optimizer - a call through a function pointer is way more expensive than an inline call. Figuring out there is only one possible function call target is likely a complex optimization in the general case, so I wouldn't blame it on the compiler.

Is an unnameable type an acceptable solution here ?
You could probably return something like:

fn new() -> S<impl Fn(&T) -> T> { ... }

I'm on my phone so I can't test it, but it should work

They are exactly what you need. What you want is, instead, much more elaborate and complicated thingie.

I think you are mixing C++ templates and Rust generics.

C++ templates are, basically, just elaborate macro system in a disguise. Each type is handled entirely separately and code for each type is processed completely independently from code for other types.

Ada, Java, Rust generics are different: code for all types are processed uniformly. Today they are monomorphised, but who said it would be true tomorrow? Swift have polymorphic generics, Rust may receive them, one day, too.

From that POV what you want is not “small, insignificant thingie on the side” but “radical change which may change the whole language future”. Specialization is small potatoes in comparison.

No, that's called generics. If you don't need to support different types with a common interface, then you don't need generics.

No, that's a concrete function/implementation, it's exactly what generics don't do. I'm guessing you are confusing "specialization" with "instantiation" (of a generic type constuctor to a concrete type)?

However, one concrete implementation isn't, in fact, what you seem to want.

What you seem to want are two generic functions over two different instantiations of a given type variable in the same generic type constructor.

Note that you are specifically asking for a function pointer by writing fn(…) -> …, even though this is entirely unwarranted, since fn items have their own, indirection-free, zero-sized, Fn()-trait-implementing, type.

You can do all of what you (seem to) want without specialization, and without dynamic dispatch/indirect calls, simply by introducing your own IdentityFn type, and implementing a common trait for it and all other key functions.

Accordingly, this compiles and should not contain any dynamic dispatch.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.