Re: [PATCH] Trivial speedup in Array#zip

On Wed, Apr 20, 2005 at 07:02:24AM +0900, [e-mail] wrote:
> > --- array.c.orig        2005-04-18 00:11:33.000000000 +0200
> > +++ array.c     2005-04-18 00:22:18.000000000 +0200
> > @@ -2074,12 +2074,12 @@
> >         argv[i] = to_ary(argv[i]);
> >      }
> >      if (rb_block_given_p()) {
> > +        VALUE tmp = rb_ary_new2(argc+1);
> > +        RARRAY(tmp)->len = argc + 1;
> >         for (i=0; i<RARRAY(ary)->len; i++) {
> > -           VALUE tmp = rb_ary_new2(argc+1);
> > -
> > -           rb_ary_push(tmp, rb_ary_elt(ary, i));
> > +            RARRAY(tmp)->ptr[0] = RARRAY(ary)->ptr[i];
> >             for (j=0; j<argc; j++) {
> > -               rb_ary_push(tmp, rb_ary_elt(argv[j], i));
> > +                RARRAY(tmp)->ptr[1+j] = rb_ary_elt(argv[j], i);
> >             }
> >             rb_yield(tmp);
> >         }
> 
> `tmp' can be modified or stored anywhere while yielding, so it
> should not be reused.  You can't assume that the size is
> constant, at least.

I see. What about this?


diff -ru ruby.orig/array.c ruby/array.c
--- ruby.orig/array.c	2005-04-20 02:09:10.000000000 +0200
+++ ruby/array.c	2005-04-20 02:22:22.000000000 +0200
@@ -2074,16 +2074,31 @@
 	argv[i] = to_ary(argv[i]);
     }
     if (rb_block_given_p()) {
-	for (i=0; i<RARRAY(ary)->len; i++) {
+	if (rb_multiple_asgn_in_block_p()) {
 	    VALUE tmp = rb_ary_new2(argc+1);
 
-	    rb_ary_push(tmp, rb_ary_elt(ary, i));
-	    for (j=0; j<argc; j++) {
-		rb_ary_push(tmp, rb_ary_elt(argv[j], i));
+	    RARRAY(tmp)->len = argc + 1;
+	    for (i=0; i<RARRAY(ary)->len; i++) {
+		RARRAY(tmp)->ptr[0] = RARRAY(ary)->ptr[i]; 
+		for (j=0; j<argc; j++) {
+		    RARRAY(tmp)->ptr[1+j] = rb_ary_elt(argv[j], i);
+		}
+		rb_yield(tmp);
 	    }
-	    rb_yield(tmp);
+	    return Qnil;
+	} 
+	else {
+	    for (i=0; i<RARRAY(ary)->len; i++) {
+		VALUE tmp = rb_ary_new2(argc+1);
+
+		rb_ary_push(tmp, rb_ary_elt(ary, i));
+		for (j=0; j<argc; j++) {
+		    rb_ary_push(tmp, rb_ary_elt(argv[j], i));
+		}
+		rb_yield(tmp);
+	    }
+	    return Qnil;
 	}
-	return Qnil;
     }
     len = RARRAY(ary)->len;
     result = rb_ary_new2(len);
diff -ru ruby.orig/eval.c ruby/eval.c
--- ruby.orig/eval.c	2005-04-20 02:09:09.000000000 +0200
+++ ruby/eval.c	2005-04-20 02:07:07.000000000 +0200
@@ -4569,6 +4569,30 @@
     return rb_block_given_p();
 }
 
+int
+rb_multiple_asgn_in_block_p()
+{
+    unsigned long arg_len;
+    NODE *list;
+
+    if (!rb_block_given_p())
+	return Qfalse;
+ 
+    if (nd_type(ruby_block->var) != NODE_MASGN)
+	return Qfalse;
+   
+    arg_len = 0;
+    list = ruby_block->var->nd_head;
+    while (list) {
+	arg_len++;
+	list = list->nd_next;
+    }
+
+    if (arg_len > 1)
+	return Qtrue;
+    return Qfalse;
+}
+
 /*
  *  call-seq:
  *     block_given?   => true or false
diff -ru ruby.orig/intern.h ruby/intern.h
--- ruby.orig/intern.h	2005-04-20 02:09:10.000000000 +0200
+++ ruby/intern.h	2005-04-20 01:59:14.000000000 +0200
@@ -174,6 +174,7 @@
 void rb_load _((VALUE, int));
 void rb_load_protect _((VALUE, int, int*));
 NORETURN(void rb_jump_tag _((int)));
+int rb_multiple_asgn_in_block_p _((void));
 int rb_provided _((const char*));
 void rb_provide _((const char*));
 VALUE rb_f_require _((VALUE, VALUE));



The point is allowing efficient parallel iteration in pure Ruby, that
is without things like Joel VanderWerf's enum or callcc-based external
iterators.


batsman@tux-chan:/tmp/ruby$ cat /tmp/bench.rb

(2..6).each do |i|
    a = [10] * 10**i
    b = [20] * 10**i
    t = Time.new
    a.zip(b){|x,y|}
    puts "%9d: %8.5f" % [10**i, Time.new - t]
end

a = [100] * 5
b = [1000] * 5
a.zip(b){|x| p x; x.replace([])}
batsman@tux-chan:/tmp/ruby$ ruby ../bench.rb
      100:  0.00010
     1000:  0.00083
    10000:  0.02530
   100000:  0.15629
  1000000:  4.81401
[100, 1000]
[100, 1000]
[100, 1000]
[100, 1000]
[100, 1000]
batsman@tux-chan:/tmp/ruby$ ./ruby ../bench.rb
      100:  0.00006
     1000:  0.00042
    10000:  0.00711
   100000:  0.05811
  1000000:  0.46238
[100, 1000]
[100, 1000]
[100, 1000]
[100, 1000]
[100, 1000]


-- 
Mauricio Fern疣dez