From: jzakiya@...
Date: 2005-03-22T16:09:52+09:00
Subject: Re: n body problem

Isaac Gouy wrote:
> > The modification consists of unrolling the loops in
> > 4 methods in the Vector3D class which do vector math.
>
> Manual loop unrolling is one optimization too many.
>
> We have a preference for plain vanilla programs - we're trying to
> compare language implementations, not programmers.

I'm a litlle tired, and will respond more fully later, but I felt
a prompt response was needed now.

There is no requirement in any language, or as a paradigm of
coding practice, that a looping structure be applied to every
potential instance where its use is possible.  To "unroll" a
"loop" is a coding "optimization" only if you start from the
reference point of the use of a loop structure. If you never
use a loop structure in the first place, and instead perform a
"direct implementation" of a function from the start, then that
is the reference point of further modification.

When engaging in the exercise of "benchmarking" inherent in
that exercise is to identify coding techniques and paradigms
within the idiom of the language being used to perform the
stated tasks as fast as possible.

Benchmarking is not about predetermining an arbitrary coding
structure paradigm and unilaterally applying that paradigm
to a every language, irrespective of the negative consequences
it has to producing the fastest program in that language.

Ruby is a native dynamic interpretive language. A user, to
acquire the highest performance possible from the language, has
to understand the consequences of this fact. One thing this mean
is that a user has to be "the compiler" at times, in order to
squeeze the highest possible performance out of the language.
Ruby is not C/C++, with highly optimized compilers, which do
a lot of the thinking for the programmer to extract performance
from source code.

Thus, as in the original nbody code, you could produce the
magnitude of a 3-dimensional vector as follows:

  def magnitude
    d = self.inject(0) {|a,v| a + v*v}
    sqrt(d)
  end

but the original code took 41 minutes to run on my system
(AMD K-7, 600Mhz, 640MB, Mandrake 10.1 Ofl, Ruby 1.8.2)

However, the inject method is not "performance optimum".

So, I first rewrote the looping structure to make it faster:

  def magnitude
    d = 0.0: (0..2).each {|i| d += self[i]**2}
    sqrt(d)
  end

and this was even a little faster

  def magnitude
    d = 0.0; 3.times {|i| d += self[i]**2}
    sqrt(d)
  end

At this point, by optimizing the most performance efficient
Ruby looping structure, I got the benchmark task down from
41 minutes to 27 minutes. Then the little lightbulb in my
head turned on.

Instead of looking at the task as an exercise in the use of
programming structures, I looked at what was the physics that
was trying to be done. After I realized what the physics
was, I just wrote code to "directly implement" the physics.

  def magnitude
    x=self[0]; y=self[1]; z=self[2]
    sqrt(x*x + y*y + z*z)
  end

Not only is this code accurate, its simple, understandable, AND
creates a MUCH faster program, which is the main point for a
benchmark. Using "direct implementation" of just 4 function methods
reduced the revised benchmark (which I posted) time to 17 minutes,
from the 'original code' time of 41 minutes.

Further testing has reduced the time to 15 minutes, using the
following code for the magnitude, tested to be the fastest so far.

  def magnitude
    sqrt(self[0]**2 + self[1]**2 + self[2]**2)
  end

Besides executing the fastest in Ruby 1.8.2, you can't
produce code any shorter and simpler than this.

So by what codified set of programmnig rules can anyone say, with
sustainable validity, that this coding paradigm is inappropriate?

In fact, in the "real world" where money, time, efficiency, and
people's lives matter, "direct implementation" of functions, in
my experience, is standard procedure, especially where speed
matters. This is especially true with languages such as Forth,
my native software language.

Now the Ruby nbody benchmark performs 1 million iterations in
15 minutes instead of 41 minutes, which is 2.5 faster than the
original code!

Ruby is a great language to get real work done with. It isn't
natively the fastest, but it needn't be naively coded to create
unnecessarily slow performance.

I've just shown one simple technique to speed up Ruby 1.8.2.
Hopefully, with Ruby 2.0 and beyond, native performance will
inherently increase. Until then, if performance matters, then
you have to think a little bit about what you are really trying
to do, and do it the "best" way to optimize Ruby performance.

Thus, I disagree that benchmarks are about applying some
arbitrary programming paradigm to a set of languages, just so
the "look" of the programs are similar. Benchmarks should
illustrate how a given language can be used to perform a
given task (the benchmark) in that language, particularly
using the best programming techniques and idioms unique to
that language.

Thus, to me, the primary essence of benchmarking is comparing
how different languages can be uniquely applied to optimally
perform the same tasks, and comparing those results.

I'll expand more on these points in the future, but I hope these
comments explain my point-of-view, and reasoning, on this issue.

Jabari Zakiya