From: Michael Hohn <mhhohn@...>
Date: 2003-01-14T06:32:30+09:00
Subject: Re: Ruby:  politics & performance [long]

Louis Krupp <lkrupp@pssw.NOSPAMPLEASE.com.invalid> writes:

> Phil Tomson wrote:
> 
> > In article <200301111701.12221.transami@transami.net>,
> > Tom Sawyer  <transami@transami.net> wrote:
> <snip>
> >> one option might be to use hashes in place of arrays. you can index
> >> them yourself. instead of [a, b, c] use {0=>a, 1=>b, 2=>c}. hashes,
> >> i was suprised to discover, are around 12x faster than arrays.
> > except that he's talking about list_append as used in the
> > parser... I don't think using hashes will help at all.  It seems
> > that the issue has to do with node lists which are constructed by
> > the parser.
> 
> Correct -- I think it's this bit of parse.y:
> 
> ---
> args 		: arg
> 		    {
> 			value_expr($1);
> 			$$ = NEW_LIST($1);
> 		    }
> 		| args ',' arg
> 		    {
> 			value_expr($3);
> 			$$ = list_append($1, $3);
> 		    }
> 		;
> ---
> 
> For the first item in the list, list_append has to check one
> node, for the second it looks at two, and
> 1 + 2 + 3 + ... + n = (n**2 + n)/2 traversals for n items.
> 
> list_concat does basically the same thing.
> 

In that case, a simple fix would be one extra indirection, assuming 
list_reverse and list_prepend are available:

args1           : args { $$ = list_reverse($1); }

args 		: arg
		    {
			value_expr($1);
			$$ = NEW_LIST($1);
		    }
		| args ',' arg
		    {
			value_expr($3);
			$$ = list_prepend($1, $3); /* was list_append */
		    }
 		;

For any given argument list, this would reduce effort to O(n)...