Algorithm Improvement through Performance Measurement: Part 5

NIST Tests

The National Institute of Standards and Technology has created several publications on random number generators under the category of computer security, along with a statistical test suite for assessing the quality of random and pseudo-random number generators [6] and [7]. This test suite is a command-line application that prompts the user with various testing options, and was simple to port to Windows 7 and Windows XP.

This test suite was used to analyze the five RNG algorithms presented above. Each algorithm was used to generate an ASCII file with 100 million bits, 32-bits per line. Each 32-bit value was generated either 1-bit at a time, or 16-bits at a time. Each algorithm was assessed at 10K, 100K and 1M bits, and run over 100 bit streams for each. The results of these tests are presented in Table 7.

Table 7: Number of NIST tests failed. "*" indicates a fatal error during test run producing no results

The measurements in Table 7 show that using the Windows C rand() function to generate 1-bit per function call performs very poorly, failing most of the tests. Contrasting, at 15-bits per call it passes all of the NIST tests at large array size of 1 million bits -- one of the best results. These measurements correlate well with the earlier measurements, confirming that the Windows C rand() function can perform poorly or can perform well, depending on how it is used.

The other four RNGs from [4] perform very well, only marginally failing a few tests, and showing little difference between generating 1-bit or 16-bits per function call. Mersenne twister [5] is the best performer at 100K bits, and passes all of the tests at 1 million bits.

Affect on Algorithm Performance

Performance of algorithms can vary significantly with variance of input data sets. Tables 8 through 13 show measured performance of various sorting algorithms discussed in [1], [2], [3] and [8] as input data sets are varied in size and the quality of randomness. STL sort() and stable_sort() are examined because sort() uses Heap Sort and stable_sort() uses Merge Sort.

Table 8: STL sort()

Table 9: STL stable_sort()

Table 10: Binary-Radix Sort [2]

Table 11: Stable Hybrid N-bit-Radix Sort [3]

Table 12: Insertion Sort [8]

Table 13: Selection Sort [8]

Performance measurements shown in Tables 7 through 13 exhibit that STL sort() varies the most by as much as 2.3X, followed by Binary-Radix Sort at 1.7X, STL stable_sort() and Stable Hybrid N-bit-Radix Sort at 1.4X. Insertion Sort and Selection Sort do not seem to vary in performance with variation in the input data statistics.

Binary-Radix Sort is faster than STL sort() with good random number distribution, but is slower with a poor distribution. STL stable_sort() is significantly slower than STL sort() with poor random number distribution. Stable Hybrid N-bit-Radix Sort is several times faster than STL sort() under all input data sets tested.