# Delegating efficiently iteration from one object to another

**URL:** <https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098>\
**Category:** Performance\
**Created:** [December 2, 2020, 10:02am UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098 "2020-12-02T10:02:29Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [December 2, 2020, 4:49pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/21 "2020-12-02T16:49:05Z")

</div>

Yes, the situation is vexing. I would really like some developers to chime in. It seems to me there should be built in Julia a way to delegate efficiently iteration!

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [December 2, 2020, 4:57pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/22 "2020-12-02T16:57:01Z")

</div>

Hopefully someone will chime in with a solution 🙂

Otherwise you can file an issue, maybe also linking to Mike Innes’ blog post. By the way I’m not sure a new iteration protocol would have to wait for Julia 2.0… For example it could dispatch with `iterate(::Iterator{T})` instead of `iterate(::T)` in a backward-compatible manner I think?

---

<div class="post-metadata">

**Author:** ![FedericoStra](https://avatars.discourse-cdn.com/v4/letter/f/76d3ee/32.png) [@FedericoStra](https://discourse.julialang.org/u/FedericoStra)\
**Post date:** [December 2, 2020, 5:58pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/23 "2020-12-02T17:58:24Z")

</div>

For me this works quite well:

```julia
mutable struct Group{N}
    s::NTuple{N,String}
    I::Iterators.ProductIterator{NTuple{N,String}}
    Group(s::NTuple{N,String}) where N = new{N}(s)
end

Base.length(G::Group) = prod(length.(G.s))
Base.eltype(::Type{Group}) = String

@inline function Base.iterate(G::Group)
    G.I = Iterators.product(G.s...) # memoize the iterator
    next = iterate(G.I)
    if next !== nothing
        s, state = next
        prod(s), state
    end
end

@inline function Base.iterate(G::Group, state)
    next = iterate(G.I, state)
    if next !== nothing
        s, state = next
        prod(s), state
    end
end

using BenchmarkTools

G = Group(("one", "happy", "man", "on", "the", "mountain"))
I = Iterators.product(G.s...)
P = (prod(s) for s in I)

for g in G end # warmup
for p in P end # warmup

@btime count(_ -> true, $G)
@btime count(_ -> true, $P)

```

Returns

```julia
julia> @btime count(_ -> true, $G)
  63.608 μs (2160 allocations: 67.50 KiB)
2160

julia> @btime count(_ -> true, $P)
  63.039 μs (2160 allocations: 67.50 KiB)
2160

```

Of course with `collect` there is a slight penalty because one needs a specialization that preallocates

```julia
julia> @btime collect(P);
  72.024 μs (2163 allocations: 84.58 KiB)

julia> @btime collect(G);
  75.176 μs (2162 allocations: 84.45 KiB)

```

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [December 2, 2020, 6:08pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/24 "2020-12-02T18:08:27Z")

</div>

- It has been discussed before why it is not the correct implementation to make I a field of G.
- indeed `count` is faster than `collect` and shows also the problem with the delegated iterator:

```julia
julia> @btime count(_->true,$G)
  3.823 μs (188 allocations: 10.22 KiB)
45

julia> I=(prod(x) for x in Iterators.product(G.s...));

julia> @btime count(_->true,$I)
  1.093 μs (45 allocations: 1.41 KiB)
45

```

---

<div class="post-metadata">

**Author:** ![FedericoStra](https://avatars.discourse-cdn.com/v4/letter/f/76d3ee/32.png) [@FedericoStra](https://discourse.julialang.org/u/FedericoStra)\
**Post date:** [December 2, 2020, 6:15pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/25 "2020-12-02T18:15:29Z")

</div>

> [@Jean\_Michel](#):
>
> `It has been discussed before why it is not the correct implementation to make I a field of G.`

You said

> The iterator is not part of `Group` construction since constructing the list of transversals is expensive  
> so is only done on demand when iterating is demanded.

In my implementation `I` is not part of the construction. It is initialized only when the iteration is first started, and the iterator is then memoized inside `G`. You can replace the field `I` with whatever alternative iterator you come up. The memoization technique is still applicable. You don’t pay the price of constructing the iterator if you never iterate over `G`.

* * *

> [@Jean\_Michel](#):
>
> `indeed `count`is faster than`collect` and shows also the problem with the delegated iterator:` […]

Your timings are off. Have you run them in a clean session?

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [December 2, 2020, 6:20pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/26 "2020-12-02T18:20:19Z")

</div>

- You made the struct mutable which is not desirable

- As mentioned before this implementation prevents two concurrent iterations.

---

<div class="post-metadata">

**Author:** ![FedericoStra](https://avatars.discourse-cdn.com/v4/letter/f/76d3ee/32.png) [@FedericoStra](https://discourse.julialang.org/u/FedericoStra)\
**Post date:** [December 2, 2020, 6:20pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/27 "2020-12-02T18:20:53Z")

</div>

If you don’t like the memoization, you can do

```julia
struct Group{N}
    s::NTuple{N,String}
end

Base.length(G::Group) = prod(length.(G.s))
Base.eltype(::Type{Group}) = String

@inline function Base.iterate(G::Group)
    I = Iterators.product(G.s...)
    next = iterate(I)
    if next !== nothing
        s, state = next
        prod(s), (I, state)
    end
end

@inline function Base.iterate(G::Group, (I, state))
    next = iterate(I, state)
    if next !== nothing
        s, state = next
        prod(s), (I, state)
    end
end

using BenchmarkTools

G = Group(("one", "happy", "man", "on", "the", "mountain"))
I = Iterators.product(G.s...)
P = (prod(s) for s in I)

for g in G end # warmup
for p in P end # warmup

@btime count(_ -> true, $G)
@btime count(_ -> true, $P)

```

and still get the same performance

```julia
julia> @btime count(_ -> true, $G)
  63.409 μs (2160 allocations: 67.50 KiB)
2160

julia> @btime count(_ -> true, $P)
  63.603 μs (2160 allocations: 67.50 KiB)
2160

```

The key takeaways are the typing of `Group` and the `@inline`. With these you get the same performance. Now `Group` is immutable and there is no memoization. Where is the problem?

---

<div class="post-metadata">

**Author:** ![FedericoStra](https://avatars.discourse-cdn.com/v4/letter/f/76d3ee/32.png) [@FedericoStra](https://discourse.julialang.org/u/FedericoStra)\
**Post date:** [December 2, 2020, 6:22pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/28 "2020-12-02T18:22:41Z")

</div>

> [@Jean\_Michel](#):
>
> `As mentioned before this implementation prevents two concurrent iterations.`

False. The iterator `G.I` does not change during iteration so it is possible to iterate over it concurrently. The progression of the iteration is stored in `state`, not by mutating `G.I`.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [December 2, 2020, 6:28pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/29 "2020-12-02T18:28:05Z")

</div>

- Your last implementation is the same as mine, apart from the `@inline` which does not change timings.
- I see you changed the example which explains the different timings.
- I do not know if you are right about concurrency. Not my domain of expertise. I repeated the point of Sudete.

---

<div class="post-metadata">

**Author:** ![FedericoStra](https://avatars.discourse-cdn.com/v4/letter/f/76d3ee/32.png) [@FedericoStra](https://discourse.julialang.org/u/FedericoStra)\
**Post date:** [December 2, 2020, 6:31pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/30 "2020-12-02T18:31:02Z")

</div>

> [@Jean\_Michel](#):
>
> Your last implementation is the same as mine

Well, if you disregard the typing of `Group` and the `@inline`, which make the performance equal to that of `Iterators.product`…

What is still missing from my last example? `Group` is immutable, there is no memoization, the performance is the optimal one. If there is something I overlooked please tell me. But it seems to me that this implementations satisfies your request. Right?

* * *

> [@Jean\_Michel](#):
>
> I do not know if you are right about concurrency. Not my domain of expertise. I repeated the point of Sukera.

Even with the memoized version you could iterate over `G` twice simultaneously. But I agree that the non-memoizing version is cleaner, leaving the `struct` immutable.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [December 2, 2020, 6:32pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/31 "2020-12-02T18:32:34Z")

</div>

Your typing of `Group` is “cheating”. The number of transversals is not known at group construction time as has been explained: in the real-life case of permutation groups the computation of transversals is expensive and is not done at group creation time, only when iteration is demanded.

---

<div class="post-metadata">

**Author:** ![FedericoStra](https://avatars.discourse-cdn.com/v4/letter/f/76d3ee/32.png) [@FedericoStra](https://discourse.julialang.org/u/FedericoStra)\
**Post date:** [December 2, 2020, 6:33pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/32 "2020-12-02T18:33:49Z")

</div>

What do you mean? You pass a vector of `Strings`. You know how many they are. Then just convert it to a tuple to make the length known to the compiler.

When you use `Iterators.product` you are fixing the number of strings anyway.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [December 2, 2020, 6:37pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/33 "2020-12-02T18:37:16Z")

</div>

Perhaps my MWE is not correct: I should hide from `Iterators.product` the number of strings.

---

<div class="post-metadata">

**Author:** ![FedericoStra](https://avatars.discourse-cdn.com/v4/letter/f/76d3ee/32.png) [@FedericoStra](https://discourse.julialang.org/u/FedericoStra)\
**Post date:** [December 2, 2020, 6:38pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/34 "2020-12-02T18:38:54Z")

</div>

> [@Jean\_Michel](#):
>
> I should hide from `Iterators.product` the number of strings.

But you can’t. When you call `Iterators.product` you “freeze” the number of subiterators.

So you cannot compare the performance of a dynamic version (your `Group` with `Vector`) with a static version (`Iterators.product`). The latter will always be faster. The only workaround is to make `Group` static as well.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [December 2, 2020, 6:41pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/35 "2020-12-02T18:41:13Z")

</div>

You confuse me. In both cases the `Vector` is made into a tuple by the call `Iterators.product(G.s...)`

---

<div class="post-metadata">

**Author:** ![FedericoStra](https://avatars.discourse-cdn.com/v4/letter/f/76d3ee/32.png) [@FedericoStra](https://discourse.julialang.org/u/FedericoStra)\
**Post date:** [December 2, 2020, 6:47pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/36 "2020-12-02T18:47:45Z")

</div>

In your first version `Base.iterate` is not able to infer the return type of `I` (it infers `Any`), because it gets produced from a `Vector`.

In my last version, `Base.iterate` correctly infers the type to be `Base.Iterators.ProductIterator{NTuple{6,String}}`.

To see this check `@code_typed iterate(G)` for both versions.

This makes a _huge_ difference.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [December 2, 2020, 6:50pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/37 "2020-12-02T18:50:22Z")

</div>

- It is a problem that the type of `I` is not inferable. Maybe it is _the_ problem.
- From what you say `Vector` is definitely correct since 6 is not known at compile time in the real life example.

---

<div class="post-metadata">

**Author:** ![FedericoStra](https://avatars.discourse-cdn.com/v4/letter/f/76d3ee/32.png) [@FedericoStra](https://discourse.julialang.org/u/FedericoStra)\
**Post date:** [December 2, 2020, 8:04pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/38 "2020-12-02T20:04:19Z")

</div>

> [@Jean\_Michel](#):
>
> It is a problem that the type of `I` is not inferable. Maybe it is _the_ problem.

Yes, it is _the_ problem. But the type of `I` cannot be inferable if you construct it from a `Vector`:

```julia
julia> foo(v::Vector) = Iterators.product(v...)
julia> @code_warntype foo(["asd", "qwe"])

```

* * *

> [@Jean\_Michel](#):
>
> From what you say `Vector` is definitely correct since 6 is not known at compile time in the real life example.

It doen’t need to be known at compile time, but rather at _construction time_ of `G = Group(...)`. In your example, `G` is fixed once created, you don’t require the flexibility to append to `G.s`. Hence, to take advantage of this fact, you must type it so that the compiler can infer the type of `Iterators.product(G.s...)`. If `G.s` is a `Vector`, it can’t do that because the length is not in the type. If you use a `Tuple` it can and you get faster code.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [December 2, 2020, 8:21pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/39 "2020-12-02T20:21:35Z")

</div>

It is not known at construction time of the group. Just at construction time of the iterator.

---

<div class="post-metadata">

**Author:** ![FedericoStra](https://avatars.discourse-cdn.com/v4/letter/f/76d3ee/32.png) [@FedericoStra](https://discourse.julialang.org/u/FedericoStra)\
**Post date:** [December 2, 2020, 8:24pm UTC](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098/40 "2020-12-02T20:24:27Z")

</div>

How can it be? Is the group mutable? Can you give a more precise example? Because in the one you gave it was known at construction time.

[Previous page](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098.md?page=1)

[Next page](https://discourse.julialang.org/t/delegating-efficiently-iteration-from-one-object-to-another/51098.md?page=3)