Skip to content

Laziness of our iterators #791

Closed

Description

@Philippe-Cholet

Similar to #601 but for all our iterators and iterator adaptors.
Laziness reference: https://doc.rust-lang.org/std/iter/index.html#laziness

And I think each iterator struct should have the related must_use attribute:

  • Adaptors: #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
  • Non-adaptors: #[must_use = "iterators are lazy and do nothing unless consumed"]

Load some items might be unavoidable in some case(?) but surely not all. TODO:

  • Add missing must_use attributes on adaptors #794
  • Make Permutations lazy #793 permutations(n) consumes n items at definition (so not lazy when n >= 1).
  • Make Combinations lazy #795 combinations(n) consumes n items at definition (so not lazy when n >= 1).
  • Make Intersperse[With] lazy #797 intersperse[_with] both consume 1 item at definition.
  • Make Product lazy #800 a.cartesian_product(b) consumes 1 item of a at definition.
    Therefore iproduct!(i_1, i_2, i_n) consumes 1 item of the first n - 1 iterators at definition.
  • Make CoalesceBy lazy #801 coalesce, dedup[_by][_with_count] all consume 1 item at definition.
  • Test the laziness of our iterators #792
  • Create CONTRIBUTING.md #767 mention laziness for new iterator adaptors and where to test it.
  • tuple_combinations::<T> consume 1 item per nested iterator at definition ("T::len()" - 1 items so not lazy for (_, _, ...)).
  • kmerge[_by] collect all items and consume 1 item of each iterator at definition.
  • Maybe update the documentation of all "eager" adaptors to say that there are "eager":
    dropping dropping_back sorted_unstable sorted_unstable_by sorted_unstable_by_key sorted sorted_by sorted_by_key sorted_by_cached_key k_smallest k_smallest_by k_smallest_by_key k_largest k_largest_by k_largest_by_key tail (so dropping[_back] and methods returning Vec[Deque]IntoIter).
    It's already good enough, it says it's "eager", or that "it consumes the entire iterator", or that "if collected to a Vec[Deque], is converted without any extra copying or allocation cost".

Activity

  1. Philippe-Cholet commented on Nov 22, 2023

    @Philippe-Cholet
    MemberAuthor

    About TupleCombinations and KMergeBy, the only way I see to make them lazy is to delay the initialization step with a LazyInit type (for e.g. based on Into conversion which is already done for the TupleCombinations part).

    // `Option` (or a third variant) is a necessary implementation detail to take ownership of `U`.
    // `Uninit(None)` (or the 3rd variant) would be unreachable.
    pub(crate) enum LazyInit<U, I> {
        Uninit(Option<U>),
        Init(I),
    }
    impl<U, I> LazyInit<U, I> {                               // useful later for
        pub fn new(uninit: U) -> Self;                        // at definition
        pub fn get(&self) -> Result<&I, &U>;                  // size_hint
        pub fn get_mut(&mut self) -> &mut I where U: Into<I>; // next, ...
        pub fn take_init(self) -> I where U: Into<I>;         // fold
        // eventually
        pub fn take_uninit(self) -> Result<U, I>;             // count
    }
    

    The most important method is get_mut which handle initialization once and simply return the mutable reference of I otherwise.

    I worry it might result in a slower iterator.

    @jswrenn @phimuemue What do you think about such pattern/type?

  2. unpinned this issue on May 16, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions