From: Douglas Seifert <doug@...>
Date: 2011-11-28T11:20:38+09:00
Subject: Re: Is high-speed sorting impossible with Ruby?

--e89a8f3ba2adec5f7104b2c225d6
Content-Type: text/plain; charset=ISO-8859-1

>
> So I'm reading your code and trying to figure out what cracked the
>
problem. Could you share some insights? Why to disable the GC? What idea
> should one take away from other parts of your code?
>

Here is the code again.  I will put comments inline to try to give insight
into what I was thinking:


> > GC.disable
>

This is a real cheat.  By turning off the garbage collector, you don't let
the ruby interpreter reclaim memory by deallocating objects that are no
longer used.  Normally, the Ruby interpreter periodically runs a garbage
collection loop where it runs through all allocated objects and if they are
not referenced any more, may free the memory, giving it back to the OS.
 During the loop, your code will not run.  By turning it off, your program
can consume lots of memory, especially if it creates many throw away
objects.


> > n = STDIN.gets.to_i
> > a = Array.new(1e6+1) {|n| ""}
>

The above creates an Array of 1,000,001 slots.  The block syntax lets you
provide a default object dynamically.  The first time you reference a
particular index in the array, the block is called to allocate the default
object at that position.


> > while n > 0
> >   i_str = STDIN.gets
> >   i = i_str.to_i
> >   a[i] << i_str
>

Here we append a string representation of the value read to string at the
position in the index.  We are creating garbage objects here.  Each string
produced by STDIN.gets, after it is appended (copied) to the string at
position i in the array, is no longer referenced anywhere.  Since we turned
off the garbage collector, the memory used by this string just hangs around
in the ruby process.

Another interesting thing to note: Thanks to the way we created the array
above, we start out with a new empty string for each position referenced in
the array.  If we had made the mistake of creating it like this:

a = Array.new(1e6+1, "")

we would have an array where every position gets the same empty string as
the default value.  We would thus append all values in the input to the
same string ... not what we intend.


> >   n -= 1
> > end
> >
> > n = 0
> > while n < 1_000_001
> >   STDOUT.write a[n]
> >   n += 1
> > end
>

This just goes through the array and writes out the value at the position.
 If we had used the wrong Array initializer, we would basically be
outputting the entire input set 1,000,000 times.

Hope that helps ...

-Doug

--e89a8f3ba2adec5f7104b2c225d6--