Efficient abstraction of item types in generics collection iterations

I am not good at English. Sorry if there are any funny expressions.

I created a trait for some generics collection structure.
The trait manages operations that do not depend on generics type parameters.
(The code is at the end of this post)

In that trait, the method that returns iterator is formed as follows.

fn items(&self) -> Box<dyn Iterator<Item = &dyn Display> + '_>

My question is about heap allocation and abstraction costs with Box.
Of course, the impact is very very very small.
However, I was expecting "zero cost abstraction" in the beginning.

I wonder in C/C++ memory allocation may not be required here.
Probably, it can be done with some pointer operations and aggressive cast.

On the other hand, to do the same thing in Rust, it might be possible
if some iterator type of Vec or other collections provided raw pointers to items,
but there is no such API, and even if there were, it would likely be unsafe.

Am I missing something or am I just nervous?
Please let me know your advice.


Here is the code that reproduces my situation.

use std::fmt::Display;

fn main() {
    let mut collections = Vec::<Box<dyn MyCollection>>::new();
    collections.push(Box::new(MyCollectionOf(vec![1, 2, 3])));
    collections.push(Box::new(MyCollectionOf(vec!["a", "b", "c"])));

    let items = collections.iter().map(|x| x.items()).flatten();
    for item in items {
        println!("{}", item);
    }
}

/// Abstract item collection.
trait MyCollection {
    fn items(&self) -> Box<dyn Iterator<Item = &dyn Display> + '_>;
}

/// Concrete item collection.
struct MyCollectionOf<T>(Vec<T>);
impl<T: Display> MyCollection for MyCollectionOf<T> {
    fn items(&self) -> Box<dyn Iterator<Item = &dyn Display> + '_> {
        Box::new(self.0.iter().map(|x| x.as_disp()))
    }
}

/// For Upcast to [`Display`].
///
/// # Notes
///
/// This trait is not required, if "trait_upcasting" feature is released.
trait AsDisp: Display {
    fn as_disp(&self) -> &dyn Display;
}

impl<T: Display> AsDisp for T {
    fn as_disp(&self) -> &dyn Display {
        self
    }
}

I don’t really see how it’s required… as a simple as cast seems to work fine (playground).

Regarding your question for heap allocation and dynamic abstraction… you can of course just use the new feature of support for impl Trait return types in traits; at least assuming you don’t have a need for MyCollection itself to be object safe. If you do want to use some &dyn MyCollection or Box<dyn MyCollection>, then it’s not really possible to avoid all overhead of making the Iterator somewhat dynamically abstracted (and involving a heap allocation), either.

Ah… and now I’m noticing you do use Box<dyn MyCollection> in your main function. So yeah then there’s not really any better way to avoid overhead for the items Iterator either.

1 Like

First of all, I was very surprised by x as _.
I thought I had to be patient until "trait_upcasting" was released.
But there was already such a good way to do this. Thank you so much.

Then, about item type abstraction.
Okay, so the overhead is unavoidable. I am bit sad.
However, when I learn from the experts, I am ready to give up.
Thank you very much again.

Of course, depending on the concrete way you use it, there might still be ways to reduce the level of dynamic overhead (even though even with that, it’s presumably very small, especially if you do something comparatively “slow” such as printing for each item, anyways).

For example if you know the concrete use-case for your collection, you can bake the use-case into the trait, so that you only need one dynamic function call per full collection, and no allocations. E.g.

use std::fmt::Display;

/// Abstract item collection. Not object safe though.
trait MyCollection {
    fn items(&self) -> impl Iterator<Item = impl Display>;
}

/// Concrete item collection.
struct MyCollectionOf<T>(Vec<T>);
impl<T: Display> MyCollection for MyCollectionOf<T> {
    fn items(&self) -> impl Iterator<Item = impl Display> {
        self.0.iter()
    }
}

fn main() {
    trait PrintAllItems {
        fn print_all_items(&self);
    }
    // Instead of something general like `dyn MyCollection` was before,
    //  we use a specific trait `dyn PrintAllItems` for this use-case
    let mut collections = Vec::<Box<dyn PrintAllItems>>::new();
    collections.push(Box::new(MyCollectionOf(vec![1, 2, 3])));
    collections.push(Box::new(MyCollectionOf(vec!["a", "b", "c"])));

    impl<T: MyCollection> PrintAllItems for T {
        fn print_all_items(&self) {
            for item in self.items() {
                println!("{}", item);
            }
        }
    }

    for collection in &collections {
        // only `print_all_items` is dynamic function call,
        // inside, the each whole loop for `print`-ing all items for one collection
        // can run without further overhead
        collection.print_all_items();
    }
}
1 Like

Wow! an internal iterator here.
Uh... I may have held on to the way that worked for me in other languages.
Your code gives me so many insights. I really thanks for that!
(And I didn't even know that I could use impl for the associated type...).

1 Like