Ruby Forum Ruby-core > Enumerable#zip Needs Love

The community has been building a Ruby 1.9 compatibility tip list on
my blog.  While most of the changes are good, a pattern is emerging:
Enumerable#zip was damaged in the translation.  The short story is:

* Making Enumerable#zip() return and Enumerable::Enumerator when
called without a block hid a very useful return value that was already
in place.  Now we typically need `enum.zip(…).to_a` to get the
expected results.
* Beyond being less attractive, Enumerable::Enumerator is quite a bit
slower.  It looks like `enum.zip(…).to_a` in 1.9 is about 12 times
slower than a straight `enum.zip(…)` in Ruby 1.8.
* Making Enumerable#zip() stop at the length of the shortest
Enumerable among the receiver and arguments really hurt its
usefulness.  It now discards data and it's hard for us to prevent
that, since we need to lengthen all short Enumerable objects we plan
to use before the call.  The Ruby 1.8 system of limiting the result
set to the size of the receiver was much more powerful, in my
opinion.  We could find the longest or shortest Enumerable to get the
length we wanted, filter out the `nil` containing groups it inserted,
or trim the size of the Enumerable objects involved (easier than
expanding them).

So, I'm making a plea for restoring Enumerable#zip() to the cool
iterator we all know and love:

* Can we restore the Array return value?  We can still use
`enum_for(:zip, …)` when needed.  This fits in with the other
iterators that have a useful return value like all?(), any?(),
count(), drop(), inject()/reduce(), none?(), one?(), sort(), and take().
* Can we revert to the 1.8 behavior of setting the result set length
to the length of the receiver and adding `nil` objects for shorter
Enumerable arguments?  That seems to give us a lot more control over
the end result.

Thanks for listening.

James Edward Gray II

Hello James,

I think the two changes have to be looked at separately.

At 07:05 08/01/04, James Gray wrote:
>The community has been building a Ruby 1.9 compatibility tip list on  
>my blog.  While most of the changes are good, a pattern is emerging:   
>Enumerable#zip was damaged in the translation.  The short story is:
>
>* Making Enumerable#zip() return and Enumerable::Enumerator when  
>called without a block hid a very useful return value that was already  
>in place.  Now we typically need `enum.zip(...).to_a` to get the  
>expected results.

My recollection may be faulty, and I may not be the typical case,
but I usually have been using zip immediately followed by some
additional operation, which should still work in 1.9, rather
than to produce an explicit array.

>* Beyond being less attractive, Enumerable::Enumerator is quite a bit  
>slower.  It looks like `enum.zip(...).to_a` in 1.9 is about 12 times  
>slower than a straight `enum.zip(...)` in Ruby 1.8.

That looks bad. But have you looked at how much slower or
faster things get when zip is used not just to create an array?
I could also immagine that the zip.to_a combination, and some
similar combinations, could be optimized in the future.

>* Making Enumerable#zip() stop at the length of the shortest  
>Enumerable among the receiver and arguments really hurt its  
>usefulness.  It now discards data and it's hard for us to prevent  
>that, since we need to lengthen all short Enumerable objects we plan  
>to use before the call.  The Ruby 1.8 system of limiting the result  
>set to the size of the receiver was much more powerful, in my  
>opinion.  We could find the longest or shortest Enumerable to get the  
>length we wanted, filter out the `nil` containing groups it inserted,  
>or trim the size of the Enumerable objects involved (easier than  
>expanding them).

I think these arguments make a lot of sense, so I think this
should be moved back to the old behavior, unless there is some
serious implementation problem.

>So, I'm making a plea for restoring Enumerable#zip() to the cool  
>iterator we all know and love:
>
>* Can we restore the Array return value?  We can still use  
>`enum_for(:zip, ...)` when needed.  This fits in with the other  
>iterators that have a useful return value like all?(), any?(),  
>count(), drop(), inject()/reduce(), none?(), one?(), sort(), and take().

Many of these return a single value, where an Enumerable would really
be strange. The only ones that return an array are are drop(), take(),
and sort().

Regards,    Martin.

>* Can we revert to the 1.8 behavior of setting the result set length  
>to the length of the receiver and adding `nil` objects for shorter  
>Enumerable arguments?  That seems to give us a lot more control over  
>the end result.
>
>Thanks for listening.
>
>James Edward Gray II
>
>


#-#-#  Martin J. Du"rst, Assoc. Professor, Aoyama Gakuin University
#-#-#  http://www.sw.it.aoyama.ac.jp       mailto:duerst@it.aoyama.ac.jp

On Jan 4, 2008, at 12:11 AM, Martin Duerst wrote:

> I think the two changes have to be looked at separately.

Sounds good to me.  I posted them here with the hope of inspiring
discussion around them.  Perhaps if enough of us reach agreement, Matz
will take pity on us zip() fans.  :)

>
> My recollection may be faulty, and I may not be the typical case,
> but I usually have been using zip immediately followed by some
> additional operation, which should still work in 1.9, rather
> than to produce an explicit array.

Well, Array is a superset of Enumerable, right?  So the operations you
can follow up with are increased by an Array return value and you
don't lose access to any of the iterators.

>> * Beyond being less attractive, Enumerable::Enumerator is quite a bit
>> slower.  It looks like `enum.zip(...).to_a` in 1.9 is about 12 times
>> slower than a straight `enum.zip(...)` in Ruby 1.8.
>
> That looks bad. But have you looked at how much slower or
> faster things get when zip is used not just to create an array?

I hadn't before, no.  Let's check though:

$ ruby -v speed_test.rb
ruby 1.8.6 (2007-09-24 patchlevel 111) [i686-darwin9.1.0]
Rehearsal -------------------------------------------------
zip().to_a():   8.040000   0.020000   8.060000 (  8.066183)
zip() { }:      8.770000   0.020000   8.790000 (  8.789457)
--------------------------------------- total: 16.850000sec

                     user     system      total        real
zip().to_a():   8.100000   0.010000   8.110000 (  8.112016)
zip() { }:      8.820000   0.010000   8.830000 (  8.852391)
$ ruby_dev -v speed_test.rb
ruby 1.9.0 (2007-12-25 revision 14709) [i686-darwin9.1.0]
Rehearsal -------------------------------------------------
zip().to_a(): 100.870000   9.620000 110.490000 (110.607631)
zip() { }:     82.510000   9.410000  91.920000 ( 92.208807)
-------------------------------------- total: 202.410000sec

                     user     system      total        real
zip().to_a():  99.890000   9.940000 109.830000 (109.915261)
zip() { }:     81.550000   9.470000  91.020000 ( 90.950279)
$ cat speed_test.rb
#!/usr/bin/env ruby -wKU

require "benchmark"

DATA = Array.new(25) { rand }

TESTS = 1_000_000
Benchmark.bmbm do |results|
   results.report("zip().to_a():") { TESTS.times
{ DATA.zip(DATA).to_a } }
   results.report("zip() { }:")    { TESTS.times { DATA.zip(DATA)
{ } } }
end

__END__

Good call.  It seems that zip() performance on the whole has tanked.

James Edward Gray II

By the way the RDOC for Enumerable#zip for 1.9 seems to need some work:

k$ ri1.9 Enumerable#zip
--------------------------------------------------------- Enumerable#zip
     enum.zip(arg, ...)                   => enumerator
     enum.zip(arg, ...) {|arr| block }    => nil
------------------------------------------------------------------------
     Takes one element from _enum_ and merges corresponding elements
     from each _args_. This generates a sequence of _n_-element arrays,
     where _n_ is one more that the count of arguments. The length of
     the sequence is truncated to the size of the shortest argument (or
     _enum_). If a block given, it is invoked for each output array,
     otherwise an array of arrays is returned.

        a = [ 4, 5, 6 ]
        b = [ 7, 8, 9 ]

        [1,2,3].zip(a, b)      #=> [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
        [1,2].zip(a,b)         #=> [[1, 4, 7], [2, 5, 8]]
        a.zip([1,2],[8])       #=> [[4,1,8]]

Note that although the signature says that calling it without a block
will return an enumerator, the examples show it returning an array.



--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

On Jan 4, 2008, at 12:11 AM, Martin Duerst wrote:

>> length we wanted, filter out the `nil` containing groups it inserted,
>> or trim the size of the Enumerable objects involved (easier than
>> expanding them).
>
> I think these arguments make a lot of sense, so I think this
> should be moved back to the old behavior, unless there is some
> serious implementation problem.

Matz, at least this much of my proposal seems uncontested.  Can you
tell us the reason for the new behavior?

James Edward Gray II

Hi,

In message "Re: Enumerable#zip Needs Love"
    on Tue, 8 Jan 2008 07:15:56 +0900, James Gray 
<james@grayproductions.net> writes:

|Matz, at least this much of my proposal seems uncontested.  Can you  
|tell us the reason for the new behavior?

The rationales behind the changes were:

  (a) stopping at the shortest

      adopting the behavior from python where I took the idea of zip
      method.  I saw some use cases that the shortest stop may
      helpful.  Besides that it's much simpler to implement.  But
      there's still room for you to persuade me.

  (b) return value

      My estimation was that zip was mostly used for iteration, and
      there's little need to get an array from zip, so that it is more
      convenient to keep consistency with other enumerator returning
      methods in Enumerable.

But use-case is more important than theoretical rationale.  There are
several options we can take:

  (1) easiest way - keeping 1.9 as it is.

      no additional work required, but you have to stand the change
      from 1.8; this might not be a good idea.

  (2) 2nd easiest way - zip without block returns an array

      this one is rather easy too.  instead of returning Enumerator,
      we can return a zipped array.  The performance issue can also be
      solved for this use-case.

  (3) hardest way - (2) + honoring length of the receiver

      I am not sure how to implement it yet.  but if it is REALLY
      needed this one is the way to go?

Any opinion?

              matz.

On Jan 7, 2008, at 8:07 PM, Yukihiro Matsumoto wrote:

>
>  (a) stopping at the shortest
>
>      adopting the behavior from python where I took the idea of zip
>      method.  I saw some use cases that the shortest stop may
>      helpful.  Besides that it's much simpler to implement.  But
>      there's still room for you to persuade me.

Well, I don't want to sound like a broken record here, but the way I
see it is:

* With the 1.8 system, we easily can have it both ways.  We can find
the bigger group and lead with that to save all data, or find the
shorter group and lead with it to trim data.
* Under 1.9 we lose data by default and it's challenging to save it
since all groups must be expanded to the same length.

>   (b) return value
>
>      My estimation was that zip was mostly used for iteration, and
>      there's little need to get an array from zip, so that it is more
>      convenient to keep consistency with other enumerator returning
>      methods in Enumerable.

I can see your point here and Martin seemed to agree with you, but:

* An Array is a super set of Enumerable, so we gain more options
without losing anything.
* It seems to break a fair bit of 1.8 code.  I can name three
libraries affected by the change off the top of my head.
* Performance seems like another good reason to do this, since you
said it would speed things up.

I promise I'm done pleading my case now.  ;)

> But use-case is more important than theoretical rationale.  There are
> several options we can take:
>
>  (3) hardest way - (2) + honoring length of the receiver
>
>      I am not sure how to implement it yet.

I don't understand.  We had this in 1.8.  Can we not go back to that
code?

James Edward Gray II

Hi,

In message "Re: Enumerable#zip Needs Love"
    on Tue, 8 Jan 2008 13:50:09 +0900, James Gray 
<james@grayproductions.net> writes:

|>  (a) stopping at the shortest

|* With the 1.8 system, we easily can have it both ways.  We can find  
|the bigger group and lead with that to save all data, or find the  
|shorter group and lead with it to trim data.
|* Under 1.9 we lose data by default and it's challenging to save it  
|since all groups must be expanded to the same length.

Points taken.

|>   (b) return value

|* An Array is a super set of Enumerable, so we gain more options  
|without losing anything.

Although an array is a Enumerable, and implements every methods in
Enumerable, I still hesitate to call it "super set", just because it
introduces several restriction of Enumerable, for example non infinity
length.  This is typical super set/sub set issue.

But using zip to create zipped array is certainly important use-case,
and consistency is not the primary goal of Ruby's design.

|* It seems to break a fair bit of 1.8 code.  I can name three  
|libraries affected by the change off the top of my head.
|* Performance seems like another good reason to do this, since you  
|said it would speed things up.

Points taken.

|> But use-case is more important than theoretical rationale.  There are
|> several options we can take:
|>
|>  (3) hardest way - (2) + honoring length of the receiver
|>
|>      I am not sure how to implement it yet.
|
|I don't understand.  We had this in 1.8.  Can we not go back to that  
|code?

The internal was totally re-written in 1.9 using fiber, but that's OK.
It's our matter.  In fact, I figured out how to do it while waiting
for your reply.  And actually implemented it already.  See attached
patch.

              matz.

diff --git a/enum.c b/enum.c
index 04fade3..bf18e27 100644
--- a/enum.c
+++ b/enum.c
@@ -1347,6 +1347,36 @@ enum_each_with_index(int argc, VALUE *argv, VALUE 
obj)


 static VALUE
+zip_a(VALUE val, NODE *memo, int argc, VALUE *argv)
+{
+    volatile VALUE result = memo->u1.value;
+    volatile VALUE args = memo->u2.value;
+    volatile VALUE tmp;
+    long idx = memo->u3.cnt++;
+    int i;
+
+    tmp = rb_ary_new2(RARRAY_LEN(args) + 1);
+    rb_ary_store(tmp, 0, val);
+    for (i=0; i<RARRAY_LEN(args); i++) {
+  rb_ary_push(tmp, rb_ary_entry(RARRAY_PTR(args)[i], idx));
+    }
+    rb_ary_push(result, tmp);
+    return Qnil;
+}
+
+static VALUE
+call_next(VALUE *v)
+{
+    return v[0] = rb_funcall(v[1], id_next, 0, 0);
+}
+
+static VALUE
+call_stop(VALUE *v)
+{
+    return v[0] = Qundef;
+}
+
+static VALUE
 zip_i(VALUE val, NODE *memo, int argc, VALUE *argv)
 {
     volatile VALUE result = memo->u1.value;
@@ -1357,8 +1387,20 @@ zip_i(VALUE val, NODE *memo, int argc, VALUE 
*argv)
     tmp = rb_ary_new2(RARRAY_LEN(args) + 1);
     rb_ary_store(tmp, 0, enum_values_pack(argc, argv));
     for (i=0; i<RARRAY_LEN(args); i++) {
-  VALUE v = rb_funcall(RARRAY_PTR(args)[i], id_next, 0, 0);
-  rb_ary_push(tmp, v);
+  if (NIL_P(RARRAY_PTR(args)[i])) {
+      rb_ary_push(tmp, Qnil);
+  }
+  else {
+      VALUE v[2];
+
+      v[1] = RARRAY_PTR(args)[i];
+      rb_rescue2(call_next, (VALUE)v, call_stop, (VALUE)v, 
rb_eStopIteration, 0);
+      if (v[0] == Qundef) {
+    RARRAY_PTR(args)[i] = Qnil;
+    v[0] = Qnil;
+      }
+      rb_ary_push(tmp, v[0]);
+  }
     }
     if (NIL_P(result)) {
   rb_yield(tmp);
@@ -1369,12 +1411,6 @@ zip_i(VALUE val, NODE *memo, int argc, VALUE 
*argv)
     return Qnil;
 }

-static VALUE
-zip_b(NODE *memo)
-{
-    return rb_block_call(memo->u3.value, id_each, 0, 0, zip_i, 
(VALUE)memo);
-}
-
 /*
  *  call-seq:
  *     enum.zip(arg, ...)                   => enumerator
@@ -1400,19 +1436,30 @@ zip_b(NODE *memo)
 static VALUE
 enum_zip(int argc, VALUE *argv, VALUE obj)
 {
-    int i;
-    VALUE result;
+    int i, block;
+    ID conv;
     NODE *memo;

-    for (i=0; i<argc; i++) {
-  argv[i] = rb_funcall(argv[i], rb_intern("to_enum"), 1, 
ID2SYM(id_each));
+
+    if (!rb_block_given_p()) {
+  conv = rb_intern("to_a");
+  for (i=0; i<argc; i++) {
+      argv[i] = rb_funcall(argv[i], conv, 0, 0);
+  }
+  memo = rb_node_newnode(NODE_MEMO, rb_ary_new(), rb_ary_new4(argc, 
argv), 0);
+  rb_block_call(obj, id_each, 0, 0, zip_a, (VALUE)memo);
+
+  return memo->u1.value;
     }
-    RETURN_ENUMERATOR(obj, argc, argv);
-    result = rb_block_given_p() ? Qnil : rb_ary_new();
-    memo = rb_node_newnode(NODE_MEMO, result, rb_ary_new4(argc, argv), 
obj);
-    rb_rescue2(zip_b, (VALUE)memo, 0, 0, rb_eStopIteration, (VALUE)0);
+    else {
+  conv = rb_intern("to_enum");
+  for (i=0; i<argc; i++) {
+      argv[i] = rb_funcall(argv[i], conv, 1, ID2SYM(id_each));
+  }
+  memo = rb_node_newnode(NODE_MEMO, Qnil, rb_ary_new4(argc, argv), 0);

-    return result;
+  return rb_block_call(obj, id_each, 0, 0, zip_i, (VALUE)memo);
+    }
 }

 static VALUE
diff --git a/enumerator.c b/enumerator.c
index 0474469..d9179db 100644
--- a/enumerator.c
+++ b/enumerator.c
@@ -365,9 +365,9 @@ enumerator_with_index(VALUE obj)
 }

 static VALUE
-next_ii(VALUE i, VALUE obj)
+next_ii(VALUE i, VALUE obj, int argc, VALUE *argv)
 {
-    rb_fiber_yield(1, &i);
+    rb_fiber_yield(argc, argv);
     return Qnil;
 }

On Jan 7, 2008, at 11:06 PM, Yukihiro Matsumoto wrote:

> Although an array is a Enumerable, and implements every methods in
> Enumerable, I still hesitate to call it "super set", just because it
> introduces several restriction of Enumerable, for example non infinity
> length.

Ah, I never considered infinite length iterators.  Good example.

Well, that's two points against using an Array, so maybe we are better
of sticking with Enumerable.  I do think we should still consider
going back to back to having the result size be the length of the
receiver though since I really feel like zip() was easier to make use
of, in that form.

> The internal was totally re-written in 1.9 using fiber, but that's OK.
> It's our matter.  In fact, I figured out how to do it while waiting
> for your reply.  And actually implemented it already.  See attached
> patch.

Great.  I'm glad you figured it out.

James Edward Gray II

Hi,

In message "Re: Enumerable#zip Needs Love"
    on Tue, 8 Jan 2008 23:23:16 +0900, James Gray 
<james@grayproductions.net> writes:

|Well, that's two points against using an Array, so maybe we are better  
|of sticking with Enumerable.  I do think we should still consider  
|going back to back to having the result size be the length of the  
|receiver though since I really feel like zip() was easier to make use  
|of, in that form.
|
|> The internal was totally re-written in 1.9 using fiber, but that's OK.
|> It's our matter.  In fact, I figured out how to do it while waiting
|> for your reply.  And actually implemented it already.  See attached
|> patch.
|
|Great.  I'm glad you figured it out.

I've checked in.  I think it works fine on both finite and infinite
enumerable objects, with sane performance (perhaps slower than 1.8
though).

              matz.

On Jan 8, 2008, at 8:34 AM, Yukihiro Matsumoto wrote:

> |receiver though since I really feel like zip() was easier to make use
> I've checked in.  I think it works fine on both finite and infinite
> enumerable objects, with sane performance (perhaps slower than 1.8
> though).

Thanks for all your work on this Matz.

Do we need to update the documentation to reflect the change?  I've
tried to do so in the patch below, but please double-check that I
described the new behavior correctly.

James Edward Gray II

Index: enum.c
===================================================================
--- enum.c  (revision 14958)
+++ enum.c  (working copy)
@@ -1400,18 +1400,19 @@
   *
   *  Takes one element from <i>enum</i> and merges corresponding
   *  elements from each <i>args</i>.  This generates a sequence of
- *  <em>n</em>-element arrays, where <em>n</em> is one more that the
- *  count of arguments.  The length of the sequence is truncated to
- *  the size of the shortest argument (or <i>enum</i>).  If a block
- *  given, it is invoked for each output array, otherwise an array of
- *  arrays is returned.
+ *  <em>n</em>-element arrays, where <em>n</em> is one more than the
+ *  count of arguments.  The length of the resulting sequence will be
+ *  <code>enum#size</code.  If the size of any argument is less than
+ *  <code>enum#size</code>, <code>nil</code> values are supplied. If
+ *  a block is given, it is invoked for each output array, otherwise
+ *  an array of arrays is returned.
   *
   *     a = [ 4, 5, 6 ]
   *     b = [ 7, 8, 9 ]
   *
   *     [1,2,3].zip(a, b)      #=> [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
   *     [1,2].zip(a,b)         #=> [[1, 4, 7], [2, 5, 8]]
- *     a.zip([1,2],[8])       #=> [[4,1,8]]
+ *     a.zip([1,2],[8])       #=> [[4, 1, 8], [5, 2, nil], [6, nil,
nil]]
   *
   */

Hi,

In message "Re: Enumerable#zip Needs Love"
    on Wed, 9 Jan 2008 04:58:11 +0900, James Gray 
<james@grayproductions.net> writes:

|Do we need to update the documentation to reflect the change?  I've  
|tried to do so in the patch below, but please double-check that I  
|described the new behavior correctly.

I guess the description is correct.  Could you check in?

              matz.

On Jan 8, 2008, at 5:19 PM, Yukihiro Matsumoto wrote:

> I guess the description is correct.  Could you check in?
Done.

Thanks Matz.

James Edward Gray II

On Jan 9, 2008 12:19 AM, Yukihiro Matsumoto <matz@ruby-lang.org> wrote:
>
>                                                         matz.
Sorry for asking a stupid question: Are we not getting an Enumerator
anymore for a call of #zip without any block?
If so, would that not be the only method in Enumerable not doing so?
Cheers
Robert
>
>



--
http://ruby-smalltalk.blogspot.com/

---
Whereof one cannot speak, thereof one must be silent.
Ludwig Wittgenstein

On Jan 10, 2008, at 1:03 PM, Robert Dober wrote:

> Sorry for asking a stupid question: Are we not getting an Enumerator
> anymore for a call of #zip without any block?

Correct.

> If so, would that not be the only method in Enumerable not doing so.

No.  Here's my list from earlier in this thread:

   all?(), any?(), count(), drop(), inject()/reduce(),
   none?(), one?(), sort(), and take()

James Edward Gray II

On Jan 10, 2008 8:16 PM, James Gray <james@grayproductions.net> wrote:
> On Jan 10, 2008, at 1:03 PM, Robert Dober wrote:
>
> > Sorry for asking a stupid question: Are we not getting an Enumerator
> > anymore for a call of #zip without any block?
>
> Correct.
>
> > If so, would that not be the only method in Enumerable not doing so.
>
> No.  Here's my list from earlier in this thread:
Ok I meant those returning arrays or Enumerables ;)
>
>    all?(), any?(),
I fail to see the meaning of these
> count(),
not in revision 14709, did this change too?
> drop(), inject()/reduce(),
>    none?(), one?(), sort(), and take()
normal enough, AAMOF sort is a good example for what kind of semantics
I was worried about.

Thx.
Robert
>
> James Edward Gray II
>
>



--
http://ruby-smalltalk.blogspot.com/

---
Whereof one cannot speak, thereof one must be silent.
Ludwig Wittgenstein

On Jan 10, 2008, at 3:10 PM, Robert Dober wrote:

> On Jan 10, 2008 8:16 PM, James Gray <james@grayproductions.net> wrote:
>> count(),
> not in revision 14709, did this change too?

Ah, it doesn't return an Enumerable if passed an argument.

James Edward Gray II