Channels ▼
RSS

Design

Algorithm Improvement through Performance Measurement: Part 6


The two implementations of the Counting Sort differed in the way they initialized the count array. The first implementation used a for loop to set each element within the count array to zero, whereas the second implementation used the compact form of array initialization. Array initialization in C sets the unspecified array elements to zero, which is exactly what is needed in this case. It's unclear why array initialization outperforms the for loop implementation, since the count array is a local array (i.e. not a global array) and the compiler has to initialize the count array at run time.

Listing 2 shows a Counting Sort implementation for 16-bit unsigned numbers. Table 2 and Graph 2 show measurement results of these three implementations along with Insertion Sort.


// Copyright(c), Victor J. Duvanenko, 2010

// Listing 2
inline void CountSortInPlace( unsigned short* a, unsigned long a_size )
{
	if ( a_size <  2 )	return;

	const unsigned long numberOfCounts = 65536;
	// one count for each possible value of an 16-bit element (0-65535/0xffff)
	unsigned long count[ numberOfCounts ] = { 0 };		// pre-initializing to zero

	// Scan the array and count the number of times each value appears
	for( unsigned long i = 0; i < a_size; i++ )
		count[ a[ i ] ]++;

	// Fill the array with the number of 0's that were counted, followed by the number of 1's, and then 2's and so on
	unsigned long n = 0;
	for( unsigned long i = 0; i < numberOfCounts; i++ )
		for( unsigned long j = 0; j < count[ i ]; j++, n++ )
			a[ n ] = (unsigned short)i;
}

Listing 2

[Click image to view at full size]
Table 2: Counting Sort, 16-bit unsigned .

[Click image to view at full size]
Figure 2

Counting Sort of arrays of 16-bit elements significantly outperforms other algorithms tested for large array sizes (1 million elements and larger). It outperforms STL sort() from 10K element array sizes from 2-30X, outperforms Hybrid 256-Radix Stable Sort from 100K elements by 1.6-6.7X, and IPP radix sort from 1 million elements by 2.9-4X. However, it lags in performance for small and mid-size arrays by up to several orders of magnitude. Most likely this is due to the L2 cache size, since 100K element array takes 200 Kbytes of memory space and fits within the L2 cache, whereas larger arrays do not. These measurements demonstrate that a hybrid algorithm approach (combining several different sorting algorithms) should be beneficial.


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