Parallel arrays revisited

Listen all a'yall,

You may remember we had a discussion a while ago, in the depths of a
thread called "Class Constants - pros and cons":

http://groups.google.com/group/comp.lang.java.programmer/browse_thread/thread/8a7f6b2357c59a68

About storing large amounts of data as parallel arrays rather than arrays
of objects. The example was an astronomical model, where, roughly
speaking:

public class Universe {
  private Star[] stars;
  public class Star {
  private double x;
  private double y;
  private double z;
  public double getX() {return x;}
  public double getY() {return y;}
  public double getZ() {return z;}
  }
  public Star getStar(int i) {
  return stars[i];
  }
}

Became:

public class Universe {
  private double[] x;
  private double[] y;
  private double[] z;
  public class Star {
  private int i;
  public double getX() {return x[i];}
  public double getY() {return y[i];}
  public double getZ() {return z[i];}
  }
  public Star getStar(int i) {
  return new Star(i);
  }
}

It was proposed that this would have better performance; this idea was
debated, and also suggested to be less important than programmer-time
concerns.

This is an interesting presentation (sadly in page-embedded PDF format or
something, although downloadable) from Michael Busch, and engineer at
Twitter, about how they optimised Lucene to handle Twitter's search needs:

http://www.box.net/shared/hivdg1hge9

The bottom line (and, indeed, the top line, given that it's the title) is
that they handle a billion searches a day, they do this with an
open-source java stack, and they had to rewrite some of the innards of
Lucene using parallel arrays to do it.

Well, and a lot of other enjoyably evil low-level tweaks.

To put a number on it, for memory-tight environments (which search engines
are, because you want to use all your memory for data, not JVM headroom),
using parallel arrays rather than small objects brought performance
improvements of "up to 400%". Where there was plenty of headroom, the
improvement was small - 4.3% in the example given.

Clearly, Twitter's search is a case where it was worth expending
programmer time to save execution time. But parallel arrays are definitely
a technique which can save execution time.

tom

--
Caps lock is like cruise control for cool.