My Enumerable::Lazy patch was accepted into ruby trunk few days ago. So, in ruby 2.0, we can go like this:<\/p>\n\n\n\n
a = [1,2,3,4,2,5].lazy.map { |x| x * 10 }.select { |x| x > 30 } #=> no evaluation\na.to_a #=> [40, 50], evaluation performed - no intermediate arrays generated.\n<\/pre>\n\n\n\n\n\n\n\nWhy?<\/h2>\n\n\n\n
Ruby is awesome language, and while being an imperative one, still allows us to write an elegant, functional programming style code. For example:<\/p>\n\n\n\n
data.map(&:split).map(&:reverse)\n<\/pre>\n\n\n\nlooks way more readable than this:<\/p>\n\n\n\n
data.map { |l| l.split.reverse }\n<\/pre>\n\n\n\nBut there’s a serious performance drawback here in the first case: while maping data<\/code> array twice, unnecessary intermediate array generated. Not a big deal while manipulating tiny arrays, but let’s say you want to parse a huge text file:<\/p>\n\n\n\nFile.open(\"text\") do |f|\n f.each.flat_map(&:split).grep(\/ruby\/)\nend\n<\/pre>\n\n\n\nIn this case you’d like to avoid unnecessary memory consumption, and that is when laziness come in handy. Having lazy flat_map<\/code> and grep<\/code> makes possible to perform evaluation of the whole chain only when we want to get an actual result. Moreover, iterating only once over the original data. That’s the purpose of Lazy enumerator. It overrides several Enumerable<\/code> methods (map<\/code>, select<\/code>, etc) with their lazy analogues.<\/p>\n\n\n\nUPDATE:<\/h4>\n\n\n\n
Now, after Enumerator::Lazy is almost finished I’ve decided to measure it’s performance. After running some trivial benchmarks I was very upset – it’s almost 4 times (!) slower than the normal arrays are. The point is in blocks that extensively created while chaining enumerator together. See this bug report and comments for more info<\/a>. In this case the real benefit of Enumerator::Lazy is not as big a it may seem at the very beginning. But take look at this piece of code:<\/p>\n\n\n\nPrime.lazy.select {|x| x % 4 == 3 }.take(10).to_a\n<\/pre>\n\n\n\ninstead of this one:<\/p>\n\n\n\n
a = []\nPrime.each do |x|\n next if x % 4 != 3\n a << x\n break if a.size == 10\nend\n<\/pre>\n\n\n\nNow it totally makes sense – when evaluation of the whole chain is too expensive or even impossible (infinite sequences) then laziness is a must if we want to keep our code simple and elegant.<\/p>\n\n\n\n
When?<\/h2>\n\n\n\n
It’s really hard to say who was the first to come up with an idea of lazy enumerations for ruby. Probably this post<\/a> back in 2008 is among the ground-breakers. The idea is quite simple and based on fact that Enumerators can be chained. Comments were added to enumerator.c file explaining how laziness can be achieved and since that many<\/a> many<\/a> many<\/a> great articles were published. ruby-lang<\/a> discussion was started more than 3 (!) years ago, and finally Matz vote<\/a> for implementation by Yataka Hara<\/a>.<\/p>\n\n\n\nEnumerable::lazy<\/code> method were proposed. It returns instance of Enumerable::Lazy<\/code> on the top of the enumerable object, that can be lazy-chained further. C patch was requested<\/a> and I found myself challenged to make a pull request<\/a> (I’m in to functional programming recently and interested in ruby internals too). The patch was slightly refactored and accepted a few days ago. It’s landed trunk and will be available since ruby 2.0 (see roadmap).<\/p>\n\n\n\nHow?<\/h2>\n\n\n\nEnumerator (skip if familiar with)<\/h3>\n\n\n\n
Just to give an insight of what Enumerator can do:<\/p>\n\n\n\n
# enumerable as enumerator\nenum = [1, 2].each\nputs enum.next #=> 1\nputs enum.next #=> 2\nputs enum.next #=> StopIteration exception raised\n\n# custom enumerable\nenum = Enumerator.new do |yielder|\n yielder << 1\n yielder << 2 end puts enum.next #=> 1\nputs enum.next #=> 2\nputs enum.next #=> StopIteration exception raised\n\nenum = \"xy\".enum_for(:each_byte)\nenum.each { |b| puts b }\n# => 120\n# => 121\n\no = Object.new\ndef o.each\n yield\n yield 'hello'\n yield [1, 2]\nend\nenum = o.to_enum\np enum.next #=> nil\np enum.next #=> 'hello'\np enum.next #=> [1, 2]\n\n# chaining enumerators\nenum = %w{foo bar baz}.map\nputs enum.with_index { |w, i| \"#{i}:#{w}\" } # => [\"0:foo\", \"1:bar\", \"2:baz\"]\n\n# protect an array from being modified by some_method\na = [1, 2, 3]\nsome_method(a.enum_for)\n\n# how about this one\n[1,2,3].cycle.take(10) #=> [1, 2, 3, 1, 2, 3, 1, 2, 3, 1]\n<\/pre>\n\n\n\nAs you might already noticed #to_enum<\/code> and #enum_for<\/code> are Kernel<\/code> module methods, thus available for any object. Examples are taken from enumerator.c directly, you can find more if you want, also check test\/ruby\/test_enumerator.rb. Well, Enumerator internals probably deserve a separate blog post, but worth to know it’s ruby fibers that makes all this ‘next’ magic possible.<\/p>\n\n\n\nLazy enumerator<\/h3>\n\n\n\n
To understand how Enumerable::Lazy works just check this out:<\/p>\n\n\n\n
module Enumerable\n class Lazy < Enumerator\n\n def initialize(obj)\n super() do |yielder|\n obj.each do |val|\n if block_given?\n yield(yielder, val)\n else\n yielder << val\n end\n end\n end\n end\n\n def map\n Lazy.new(self) do |yielder, val|\n yielder << yield(val) end end end end a = Enumerable::Lazy.new([1,2,3]) a = a.map { |x| x * 10 }.map { |x| x - 1 } puts a.next #=> 9\nputs a.next #=> 19\n<\/pre>\n\n\n\nThere’s nothing new here – it’s a typical lazy enumerator ruby implementation that can be googled in a second. Same as provided by Yutaka<\/a>. But did you notice – I’m not using &block<\/code> as a parameter (to call it as a proc inside each block) here but yielding directly instead. I love this hidden ruby power – you can yield<\/code> inside another block! block_given?<\/code> works as expected too. Moreover, you can call self<\/code> inside another block or make a return from the function. Awesome – we are lucky guys here :-). See Yehuda Katz post<\/a> (another one<\/a>) to have a better feeling.<\/p>\n\n\n\nThe code is self-explanatory, but let’s make it crystal-clear:
the basic idea is to chain enumerators – rather than perform evaluation directly, map returns another Enumerable::Lazy<\/code>, having previous one as an argument. And only when we need to get an actual result (by calling to_a<\/code>, next<\/code>, each<\/code> with block, take<\/code>, etc) evaluation performed. To get next value ruby climbs back over this enumerators chain finally getting next value from the actual enumerable (Fig.1). Then this value pops-up back to you, while modified with blocks along the way (in the same order they were applied).<\/p>\n\n\n\nC patch<\/h3>\n\n\n\n
The C patch<\/a> – mimics ruby code example. Except the fact that rather than calling super<\/code> inside lazy_initialize<\/code>,
I’m allocating generator with a block and then calling enumerator_init<\/code> passing this new generator as an argument.<\/p>\n\n\n\nIn final patch nobu<\/a> refactored code a little bit – instead of having if-else condition inside a block, he extracted two methods (lazy_init_block_i<\/code> and lazy_init_block<\/code>) and moved if-else into lazy_initialize<\/code> directly. Also, I was passing a ruby array as a block parameter, but it’s better to construct and pass a simple C array. Thus, no need to use rb_ary_entry<\/code> to get yielder and value inside a block, like this:<\/p>\n\n\n\nstatic VALUE lazy_map_func(VALUE val, VALUE m, int argc, VALUE *argv)\n{\n VALUE result = rb_yield_values2(argc - 1, &argv[1]);\n\n return rb_funcall(argv[0], id_yield, 1, result);\n}\n<\/pre>\n\n\n\ninstead of this:<\/p>\n\n\n\n
static VALUE lazy_map_func(VALUE val, VALUE m, int argc, VALUE *argv)\n{\n VALUE result = rb_funcall(rb_block_proc(), id_call, 1,\n rb_ary_entry(val, 1));\n\n return rb_funcall(rb_ary_entry(val, 0), id_yield, 1, result);\n}\n<\/pre>\n\n\n\nAnother lesson for me to learn from ruby core guy. Frankly speaking, I was a total newbie in ruby patching. So it took me two weekends to come up with the (fairly trivial) pull request. First weekend I came up with another crazy pull request<\/a> – I was storing all blocks as procs inside enumerator itself. And when next value (using Enumerable#next<\/code>) is requested – all blocks are applied one by one. Lazy map and select were working great, but when trying to adjust Enumerator#each I realized that it’s a road to nowhere (is it?).<\/p>\n\n\n\nWell, you are a tough guy if you made this far, so If you are planning to start patching there are plenty<\/a> of great articles<\/a> for you. Also, bonus article<\/a> showcasing why we should be lazy.<\/p>\n\n\n\nConclusion<\/h2>\n\n\n\n
We have 5 lazy methods so far – select<\/code>, map<\/code>, reject<\/code>, grep<\/code> (added by first patch) and flat_map<\/code> (added<\/a> later on by shugo<\/a>). Additionally – rather than doing Enumerable::Lazy.new([1,2,3,4])<\/code> you can use handy shortcut [1,2,3,4,5].lazy<\/code>. If you want to get your hands on – just compile ruby trunk and feel free to play.<\/p>\n\n\n\nUPDATE:<\/h3>\n\n\n\n
A lot of commits was made into Lazy enumerator during this week. In particular:<\/p>\n\n\n\n
- Nesting changed: Enumerable::Lazy is now Enumerator::Lazy<\/li>
- Additional lazy methods added, here’s full list so far:
map<\/code>, flat_map<\/code>, select<\/code>, reject<\/code>, grep<\/code>, zip<\/code>, take<\/code>, take_while<\/code>, drop<\/code>, drop_while<\/code>, cycle<\/code><\/li>- Enumerator::Lazy#lazy method added – just returns self<\/li>
- Enumerator::Lazy#force as alias to
to_a<\/code><\/li><\/ul>\n\n\n\nStay tuned!<\/p>\n","protected":false},"excerpt":{"rendered":"
My Enumerable::Lazy patch was accepted into ruby trunk few days ago. So, in ruby 2.0, we can go like this:<\/p>\n","protected":false},"author":34,"featured_media":9464,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[3],"tags":[],"coauthors":["Innokenty Mihailov"],"class_list":["post-1327","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-development"],"acf":[],"aioseo_notices":[],"categories_data":[{"name":"Engineering","link":"https:\/\/railsware.com\/blog?category=development"}],"post_thumbnails":"https:\/\/railsware.com\/blog\/wp-content\/themes\/railsware\/vendors\/images\/article-thumbnail-default.jpg","amp_enabled":true,"_links":{"self":[{"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/posts\/1327","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/users\/34"}],"replies":[{"embeddable":true,"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/comments?post=1327"}],"version-history":[{"count":53,"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/posts\/1327\/revisions"}],"predecessor-version":[{"id":13996,"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/posts\/1327\/revisions\/13996"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/media\/9464"}],"wp:attachment":[{"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/media?parent=1327"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/categories?post=1327"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/tags?post=1327"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/railsware.com\/blog\/wp-json\/wp\/v2\/coauthors?post=1327"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}