Author: Walter Faxon
Date: 23:19:23 07/21/04
Go up one level in this thread
Finding the maximum value (only) in an array: improvements summary. (1) As per Bob Hyatt, test while the data is being added to the array. (2) As per Daniel Clausen, a small improvement is to start with an endpoint value from the array. (3) Run the loop index downwards towards zero, avoiding the extra comparison against the array dimension; instead you rely on the "negative" flag being raised when the index is decremented below zero. (This can also be combined with unrolling, below.) (4) Some chips prefer the use of pointers to indexes, especially depending on the data sizing. (5) Tony Werten's idea is to add a sentinel value to avoid testing the index unless a new high value is found. In random-ordered arrays this really doesn't happen that often! But sometimes there is no unique sentinel value handy, or any place to put it. (A small bug in Werten's code was fixed by Ricardo Gibert.) (6) Ricardo Gibert cleverly avoids using an explicit sentinel by searching in both directions, with the last maximum value found acting as a sentinel. The only likely slowdown here is when there are many equal values, which produces more index tests than Werten's code. (7) Some advanced chips have a so-called "conditional move" instruction that can replace the maximum value without requiring a (slow) conditional branch. In these cases you'll instead need to terminate the loop using the index value. (A higher-level language like C requires you to rely on the compiler to implement conditional moves.) (Can be combined with unrolling, below.) (8) Mathieu Page provides a bit hack which obtains the maximum of two signed integers without using a (slow) conditional branch. But it's slower than a conditional move if that's available, and less general (signed integers only). (9) "Unroll" the loop, having one loop index test control multiple data tests; you'll need a switch() or some such to deal with odd cases unless the array size is fixed or an exact multiple of the degree of unrolling. For arrays known to be very small you can unroll all the way, avoiding index tests altogether except perhaps for an initial switch() on a variable array size. (10) Alvaro Begue's suggestion of unrolling using multiple maximum values might at first appear illogical since instead comparing everything against a single value means fewer overall assignments, and you don't have to combine the results. However, using multiple values also means fewer data dependencies in the unrolled loop -- very important on current hardware. But it also requires more registers... YMMV! YUM! -- Walter
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.