Measuring Internal Algorithms

I did two series of test programs. The first sorted unsigned integers, and the second null-terminated strings.

Input Data

For input I used random unsigned integers, random length strings from 1 to 128 characters, consisting of random printable characters, and 1000 character long records with the first 997 characters equal and the last three consisting of random characters.

The comparison times for these element sets differ of course. For strings, the randomness ensures that the comparison function usually only needs to compare the first character of each string.

The suitability of the data can be discussed, but I think that it represents a reasonable input selection.

Timing

The timings where made by measuring the total real time for the sort with the built-in Symmetry $\mu$s-clock (accurate to $1\; \mu$s). The real time was used because the thread implementation makes the operating systems concept of user time meaningless. Also, the $\mu$s-clock is more accurate than the system clock.

However, measuring the real time has a number of pitfalls. Interrupts, other processes switching in, and system overhead all combine to increase the time. In order to get reasonable accuracy, I timed each combinations of elements for one and four processors ten times (using the same input data), and took the shortest time. Also, I ensured that the system had no other users, and that the system load was less than 5% during the measurements. All considered, I think this gives a reasonable approximation of the algorithm performance.