Wednesday, April 13, 2011

Simple Heapsort / Sun Studio ->C/C++ Profiler /Good bye Ubuntu


  • This is the simplest implementation of the heap sort algorithm:


[sourcecode language="cpp"]

#include <cstdlib>
#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
#include <cmath>
using namespace std;
/*  We use this function each time we remove the root node, to restructure the
heap evenly.
*/
template <class T>
void createData(vector<T> &list, int size,int lowerBound, int upperBound) {
T num;
int range = upperBound - lowerBound + 1;
for (int i = 0; i < size; i++) {
num = lowerBound + int(rand() / (RAND_MAX / range + 1.0));
list.push_back(num);
}
}

template <class T>
void fixHeap(vector<T> &list, int root, int key, int bound) {
//list  the list/heap being sorted
//root  the index of the root of the heap
//key   the key value that needs to be reinserted in the heap (the one that was
// taken from the tree's bottom )
//bound the upper limit (index) on the heap (or list size)
int vacant = root;
int largerChild;
while (2 * vacant <= bound) {
largerChild = 2 * vacant;
if (largerChild < bound && list[largerChild + 1] > list[largerChild])
largerChild++;
//does the key belong above this child?
if (key > list[largerChild])break;
else // no, move the larger child up
{
list[vacant] = list[largerChild];
vacant = largerChild;
}
}
list[vacant] = key;
}

void execSimpleHeapSort(int size,bool printResult) {
int max;
vector<int> list;
createData(list,size,0,10000);
const int N = list.size() - 1;
//to create the heap structure
for (int i = N / 2; i >= 1; i--) {
fixHeap(list, i, list[i], N - 1);
}
//here we remove the root element (the maximum value) N times
//and of course we need to fix the heap each time we do that
for (int i = N - 1; i > 1; i--) {
max = list[1];
fixHeap(list, 1, list[i], i - 1);
list[i] = max;
}

if(printResult){
cout << " The sorted list : " << endl;
for (int i = 1; i < N; i++) {
cout << list[i] << " ";
}
cout << endl;
}
}

void simpleSTLsort(int size){
vector<int> list;
createData(list,size, 0, 10000);
sort(list.begin(),list.end());
}


int main(int argc, char** argv) {
srand((unsigned) time(0));
execSimpleHeapSort(10000000,false);
//simpleSTLsort(10000000);
return 0;
}

[/sourcecode]

Based on the pseudocode presented in "Analysis of Algorithms, An Active Learning Approach" by Jeffrey J. McConnel.

I coded it in order to test the profiling tools available in the Sun Studio suite  v.12.2 for C/C++, which was impossible to install correctly in ubuntu without disrupting some critical configurations (I was interested in using the compilers also, not just the profiling tools). For the aforementioned reason and others I decided  to switch to CentOS once and for all, I grew very tired of all the cool stuff being only well tested on Suse and RedHat. Yes, my CentOS is a  second class Red Hat citizen but who cares.

  • This is the output generated by sorting a vector with 10 million integers using the simple heap-sort:

    [caption id="attachment_220" align="aligncenter" width="300" caption="Performance of simple heap-sort on 10 million keys"][/caption]

    It took about 32 seconds to complete the task and his memory footprint was around 39 MB. This report can give you information about memory leaks (i.e: when you reserve memory and never release it), hot spots regarding CPU utilization and Thread synchronization issues, awesome!!!!!

  • And if you weren't impressed with that, take a look:

    [caption id="attachment_221" align="aligncenter" width="300" caption="Which functions used how many cpu cycles"][/caption]

    Yeahh, it can even give you a report on what functions were the most expensive to process.

  • How does the sort function included in the C++ STL compared with the simple heap-sort algorithm?

    [caption id="attachment_222" align="aligncenter" width="300" caption="The STL sorting algorithm rocks!"][/caption]

    8 secods !,  just a quarter of the time that it took to do the same task with the simple heap-sort algorithm, with basically the same memory footprint.

  • Conclusion: To code your own sorting functions is not worth it, period....unless you parallelize them, because as you can see the stl implementation ,although highly optimized is not parallel, the report depicts only one thread. I think the merge sort approach could allow such parallelism, but I'm not sure....

  •  

1 comment:

  1. Explain HeapSort With Example and screenshots with simple explanation check the link
    http://geeksprogrammings.blogspot.com/2013/08/explain-heapsort-with-example.html

    ReplyDelete