Hello,

Enumerator::Lazy is not a silver bullet; it removes the overhead for
creating an intermediate array, but brings the drawback for calling
a block. Unfortunately, the latter is much bigger than the former.
Thus, in general, Lazy does bring performance drawback.

The worth of Enumerator::Lazy is to extract first some elements from
big array, especially, infinite sequence. For example:

Prime.lazy.select {|x| x % 4 == 3 }.take(10).to_a

The code becomes much complex without Lazy:

a = []
Prime.each do |x|
next if x % 4 != 3
a << x
break if a.size == 10
end

Anyway, this is not a bug. If you have any concrete idea to "fix"
this issue, please reopen the ticket.

Thank you,

--
Yusuke Endoh [email protected]

=begin
Finally come up with a concrete idea how to "fix" (based on my first PR https://.com/ruby/ruby/pull/100).

The idea is to keep all blocks (passed with lazy methods like map or select) as (({Proc})) objects inside the enumerator and apply them one by one when value requested ((({to_a})), (({next})), etc)
This strategy avoids enumerator chaining on each lazy method call and eliminates fair amount of 'calling the block' with (({rb_block_call})) operations.
Here's benchmark results:

2.0.0| ~/projects/ruby(trunk)$ rvm ruby-head
2.0.0| ~/projects/ruby(trunk)$ ruby bench.rb
user system total real
Lazy enumerator 1.460000 0.000000 1.460000 ( 1.465739)
Simple array 0.420000 0.000000 0.420000 ( 0.421446)
0.287671 NaN NaN ( 0.287531)
2.0.0| ~/projects/ruby(trunk)$ rvm system
2.0.0| ~/projects/ruby(trunk)$ ruby bench.rb
user system total real
Lazy enumerator 0.770000 0.000000 0.770000 ( 0.764750)
Simple array 0.370000 0.000000 0.370000 ( 0.382653)
0.480519 NaN NaN ( 0.500364)

ruby-head is current trunk compiled, and system ruby - is the same trunk but with my applied.
Last row in results is ratio between 'Simple array' time and 'Lazy Enumerator' time.
So, as you can see, with this lazy enumerator becomes almost 2 times faster.

It's a 'proof of concept' (only map and select added) - let me know if it makes sense.
I believe that using this approach and with your help lazy enumerator performance can be improved significantly.

I'm attaching the diff along with the main part of the source code just in case it's hard to follow the diff.

=end

Nobu, could you review the ? And if you don't see any problem, check it in?

Matz.

Here's the new attached - problem, mentioned by Yusuke Endoh, fixed - now I'm creating a new copy of enumerator on each lazy method call.
Also I fixed an error for big arrays - forgot to gc_mark procs array.

Thomas, that's the point - current implementation is very simple and hence very inefficient.
It mimics ruby implementations but as soon as we are in the C sources already - we can come up with something more efficient.

(Yusuke Endoh) wrote:

(1..10).lazy.select {|x| false }.map {|x| p x }.to_a
should print nothing, but it actually prints 1, 2, ..., 10

Fixed, thanks.

But I guess implementing
other methods, especially, #cycle and #zip, will make some
functions (process_element and lazy_iterator_block) complex
and hard to maintain.

Agree, those methods (especially #cycle) will be hard to implement in terms of procs chaining approach.

(Nobu Nakada) wrote:

So I want to see this being merged in an extensible way.

I came up with a new hybrid .
It uses procs chaining to handle lazy #map and #select, and current enumerator chaining approach for other methods.
I believe this is an extensible way. We can move forward step by step and we can stop any time.
If those tricky #zip and #cycle methods optimization won't worth the code complexity added - we can leave it as it is: based on enumerator chaining.
See new lazy_enumerator_hybrid.diff (tests are green except test_inspect).

Please, let me know you thoughts about this.

=begin
Here's an update.
All methods except (({Lazy#cycle})), (({Lazy#zip})) and (({Lazy#flat_map})) are optimized.
Benchmark results shown below.

I was working in ((<this branch|URL:https://.com/gregolsen/ruby/tree/lazy_enumerator_optimization>)).
Cycle, zip and flat_map are really tough to convert to procs chaining, however they are working fine in this hybrid solution and can be leave as it is.

All tests pass except test_inspect.
If this implementation is acceptable then the next step will be to fix inspect and add more tests to cover different types of chaining:
like chaining of enumerator chained (cycle, zip, flat_map) methods with procs chained optimized methods.

Please, let me know your thoughts.

Thanks.

======================Lazy#map
user system total real
Trunk 1.420000 0.010000 1.430000 ( 1.461111)
Optimized 0.830000 0.000000 0.830000 ( 0.833560)
======================Lazy#select
user system total real
Trunk 1.270000 0.010000 1.280000 ( 1.274074)
Optimized 0.780000 0.000000 0.780000 ( 0.785303)
======================Lazy#grep
user system total real
Trunk 1.540000 0.010000 1.550000 ( 1.552651)
Optimized 0.780000 0.000000 0.780000 ( 0.783526)
======================Lazy#take_while
user system total real
Trunk 1.260000 0.000000 1.260000 ( 1.257465)
Optimized 0.780000 0.010000 0.790000 ( 0.784682)
======================Lazy#drop_while
user system total real
Trunk 1.030000 0.000000 1.030000 ( 1.030987)
Optimized 0.400000 0.000000 0.400000 ( 0.394112)
======================Lazy#reject
user system total real
Trunk 1.240000 0.000000 1.240000 ( 1.243565)
Optimized 0.780000 0.000000 0.780000 ( 0.781825)
======================Lazy#drop
user system total real
Trunk 4.150000 0.000000 4.150000 ( 4.159758)
Optimized 1.590000 0.000000 1.590000 ( 1.598785)
======================Lazy#take
user system total real
Trunk 0.520000 0.000000 0.520000 ( 0.517902)
Optimized 0.010000 0.000000 0.010000 ( 0.003274)
=end

Here's an update:
Finally I've fixed the last test for Enumerator::Lazy#inspect - now it supports procs chaining too.
Nobuyoshi Nakada, please, see diff attached and let me know your thoughts about this.
Thanks.

Yusuke Endoh, thanks a lot for pointing out on this issue.
Fixed, please see new diff attached.

Yusuke-san seems to be last to review this, what is your opinion?

I've merged the with latest trunk (see latest diff attached), specifically with Enumerator lazy size feature.
Also I've removed the ugly case switch: now proc entry stores pointer to a function that is executed when iterating over the elements.
So now it even resembles the current implementation a bit.

Please, let me know your thoughts about all this.
Thanks in advance.

This is big, but I hope to review it soon as I will be working on Lazy soon

Finally managed to merge. Please see latest diff attached.

Rebased towards latest trunk.

@nobu (Nobuyoshi Nakada) thanks for pointing!
Indeed hybrid flag is already obsolete since I'm checking for proc_entry presence.
If no proc entries present - than it's effectively a hybrid case.
Fixed attached.

PS
I'm using this branch - https://.com/gregolsen/ruby/tree/enumerator_lazy_optimization
Should I still attach diffs here?

Applied in changeset r56185.

enumerator.c: lazy enum improvement

• enumerator.c (lazy_init_yielder): directly call stored functions.
  [Feature ]
• enumerator.c (lazy_add_method): create lazy enumerator which
  uses lazy_init_yielder().