Channels ▼
RSS

Tools

Algorithm Improvement through Performance Measurement: Part 5


Setup

The setup for performance comparison setup was as follows: single-threaded 32-bit command prompt application, compiled Visual Studio 2008, optimization project setting is set to optimize for speed and inline any suitable function. The application ran on Intel Core i7 860 at 2.8-GHz Quad-Core CPU with hyper-threading (1 Mbyte L2 cache, and 8 MBytes of shared L3 cache) -- 8 GBytes of system memory (dual-channel 1333 MHz DDR3 attached directly to the CPU), running 64-bit Windows 7 operating system.

Conclusion

A few aspects of five random number generators (RNGs) were explored, exposing issues in the Windows C rand() function. When extracting 1-bit per function call, this RNG generated only 4K unique values within an array of 100 Million 32-bit numbers (0.004% unique). However, when extracting 15-bit per function call, it was as good as the other four RNG algorithms explored.

Four other RNG functions from [4] and [5] were shown not to exhibit such an wide range of quality, over the same usage pattern. A subtle possibility for misuse of good RNGs was demonstrated, which led to never generating some values. This flaw was corrected and improved statistics were exhibited.

These results (bad and good) were visualized by producing several images, which clearly showed issues with the Windows C rand() RNG with visible patterns and low density of values. Image produced with other RNGs appeared of uniform density and without immediately visible patterns.

NIST test suite for RNGs [6] was introduced and used on all RNGs. This test suite correlated well with other findings, showing that Windows C rand() function can perform very poorly (1-bit per call failing most of the tests) and can perform very well (15-bits per call passing all of the tests). The other four RNGs performed very well on these tests and did not show usage sensitivities. Mersenne twister passed all of the tests for the large data set, while other RNGs nearly passed as well. Other RNG test suites are available at [9].

The affect of RNG quality on performance of sorting algorithms was explored. STL sort() showed the largest performance variation due to quality of the input data set, with 2.3X variation, followed by the Binary-Radix Sort at 1.7X, STL stable_sort() and Stable Hybrid N-bit Radix Sort at 1.4X. Insertion Sort and Selection Sort did not vary in performance. Stable Hybrid N-bit-Radix Sort was several times faster than STL sort() under all input data sets used.

References

[1] Algorithm Improvement through Performance Measurement: Part 3, In-place Hybrid N-bit-Radix Sort Victor J. Duvanenko

[2] Algorithm Improvement through Performance Measurement: Part 2, In-place Hybrid Binary-Radix Sort. Victor J. Duvanenko

[3] Algorithm Improvement through Performance Measurement: Part 4, Stable Hybrid N-bit-Radix Sort. Victor J. Duvanenko

[4] Numerical Recipes in C: The Art of Scientific Computing, Second Edition, H. Press, S.A. Teukolsky, W.T. Vetterling, B. P. Flannery, pp. 274-283.

[5] Arthur Jackson, implementation of the Mersenne twister.

[6] National Institute of Standards and Technology, Random Number Generation.

[7] NIST SP800-22, "A Statistical Test Suite for Random and Pseudorandom Number generators for Cryptographic Applications".

[8] Algorithm Improvement through Performance Measurement: Part 1, Optimizing sort Algorithms for Today's CPUs. Victor J. Duvanenko

[9] Other Random-Number Generator Tests


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video