Simon,
> That part of the code was specifically written to take advantage of
> processing pipelines in the hardware, not because the actual theoretical
> algorithm for that approach was itself faster.
Yup, good point.
> Nobody's said what compiler/hardware they have been using, so since both
> Alon and Tom say their character finding logic is faster, it is likely
> to be down to that? Name your platforms gentlemen, please.
In this case, we've been using gcc (3.2.3 RHEL3 Linux, 3.4.3 Solaris 10) on Opteron and Intel Xeon and Pentium 4.
Alon'sperformance comparisons for the parse only were done on a HT enabled P4 3.0GHz on RHEL3 with gcc 3.2.3, probably
withoptimization -O2, but possibly -O3.
Note that the level of microparallelism on upcoming CPUs is increasing with increasing pipeline depth. Though there
willbe a step back on the Intel line with the introduction of the Centrino-based Xeon cores in 2006/7, other CPUs
continuethe trend, and I expect the next generation of multi-core CPUs to possibly introduce threaded
micro-architectureswhich can also be scheduled as pipelines. The gcc 4 compiler introduces auto vectorization, which
mayenhance the optimality of some loops.
I think the key thing is to make as much parallelism apparent to the compiler as possible, which will generally mean
loops. This means faster code on all modern CPUs and it won't hurt older CPU speeds.
> My feeling is that we may learn something here that applies more widely
> across many parts of the code.
Yes, I think one thing we've learned is that there are important parts of the code, those that are in the data path
(COPY,sort, spill to disk, etc) that are in dire need of optimization. For instance, the fgetc() pattern should be
bannedeverywhere in the data path.
BTW - we are tracking down (in our spare time :-() the extremely slow sort performance. We're seeing sort times of
1.7MB/son our fastest machines, even when the work_mem is equal to the square root of the sort set. This is a
*serious*problem for us and we aren't getting to it - ideas are welcome.
Optimization here means both the use of good fundamental algorithms and micro-optimization (minimize memory copies,
exposelong runs of operations to the compiler, maximize computational intensity by working in cache-resident blocks,
etc).
- Luke