I seem to have said:
> > I think the major problem is that I'm creating tons of 
> > objects, and most of
> > the time is spent on garbage collection. Actually the real 
> > data does not got
> > lost at any point, there's just probably too many inobjects 
> > before final form.

I meant to say temporary objects.

Dave comments:
> I changed your code slightly, and you're correct-the performance is
> linear in terms of the number of objects present in the system.

Yep, it seems so.

> If you disable garbage collection, then the times become linear.

But I can't do that, as my more complex real program creates masses of
objects which means that after 30 secs and 300MB of memory we'll have only a
core file :).

> These numbers are object right-each time around the loop you create 34
> objects (15 key/value pairs and a hash for 'entry', and an array and
> two strings for 'key').

Actually there's quite much more object being created and lost. Your numbers
were (I guess) always representing the the final, or mostly clean (lately
GCed), situation.

> So, it looks like it is the overhead of marking and sweeping 
> all those thousands of objects that is causing the problem.

Yep, it seems to be the reason. 

I actually put print to rb_gc and got notified when GC happened. And it
happened often (some 1600 GCs for 8000 final objects). After it ran out of
memory, it GCed before allocating more (quite wise, I think). And each time
there were more objects to be checked, so the GC takes longer and longer on
each mark and sweep.

The behaviour is same on 1.5 series, altough probably much faster (as Guy
pointed out in Array#hash conversation). 

I don't know any real solution to this right now. GC is slow, so let's not
do it, OTOH without GCing now and then we run out of memory *fast*.

My quick hack is to allocate even more when we allocate, so the forced GC,
when temporarily out of memory and have to allocate more, will occur less
often.

There is this block At gc.c

  #define HEAPS_INCREMENT 10
  static RVALUE **heaps;
  static int heaps_length = 0;
  static int heaps_used   = 0;

  #define HEAP_SLOTS 40000
  #define FREE_MIN  4096

The FREE_MIN has changed from 512 at ruby 1.4.5 to 4096. It changes the
behaviour somewhat. But my quick checks at morning revealed that it's the
HEAP_SLOTS which makes the difference, in this case at least. So doubling
the value will double performance (almost halved execution time).

Actually I didn't manage to figure out why HEAPS_INCREMENT is not affecting
speed at all, as I originally thought it would be mostly about the
combination of HEAPS_INCREMENTED and HEAP_SLOTS.

Anyway, I'm a bit in hurry now, so can't explore more.

For the interested parties, here's essentially the same program from our
Refences and still counting -world; Perl. (Reminded me how ugly, errorprone
and tricky it is to use Perl :).

It generates 24000 items in 15 secs (compare to Ruby's original 420 secs).
So there's quite big difference in speed here. Maybe it's worth of
examination.

    - Aleksi


my $store = {};
my @key_fields = ("kkkkkk", "rrrr");
my $mod = 0;
my $t = undef;

print(time, "\n");

for my $i (0..24000){
    $str = ("ddddddddddd=0.00&oooooooooooo=0&aaaaaaa=0.00&llll=0.00&".
	    "yyyyyy=0.00&pppp=0.00&rrrr=abcd1234$mod&vvvvvv=0&".
	    "eeee=5.90&bbb=0.00&sss=0.00&ttttt=NIL&mmmmmmm=0&".
	    "kkkkkk=ABCDE&nnnnnnnnnn=0.00&qqqqqq=12170305");

    $mod++;

    $entry = {};
    map {
 	my($name, $value) = split(/=/, $_);
	$entry->{$name} = $value;
    } split(/&/, $str);

#   doesn't work, or I'm dumb. I think Perl doesn't eat arrays as keys.
#    $key = [];
#    map { push( @{$key}, $entry->{$_} ); } @key_fields;

    $key = "";
    map { $key .= $entry->{$_}; } @key_fields;
    
    $store->{$key} = $entry;

    if( $i % 1000 == 0){
	printf("%5d\n", $i);
    }
}

print(time, "\n");