C code - memory access / preemption

Question

I wrote a code snippet in which the data:

unsigned char buf[4096]; // data in chunks of size 4k unsigned counter[256]; 

I add i / p data for every 3 contiguous bytes and save ans. ex: temp [4096]; temp [0] = buf [0] + buf [1] + buf [2]; ... up to 4096

Then, a histogram is generated from the temp results using code:

 for(i = 0; i < 4096; i++) counter[temp[i]]++; 

The histogram is sorted (bubble sort), and then the 8 most repeated values ​​are executed. The code runs in the linux kernel (2.6.35)

The problem I am facing is that if I remove the sort part, the time taken to execute the code is very fast (6 microseconds on my laptop, measured using gettimeofday function). But after the introduction of sorting, the process slows down to a large extent (44 microseconds). The sorting function itself takes 20 microseconds, I can’t understand why this time is increasing. I did a memory analysis using cachegrind, the results are normal, and I even tried disabling preemption ubut, but it shows no difference. If anyone can help me here. Thank you

Answer 1

The Bubble variety is slow, it compares and swaps your values ​​up to 4096 * 4096 = 16,777,216 times. If you only need the 8 best values, choosing 1 sweep will be faster with confidence. By itself so.

  const uint_t n = 8; uint_t best[n] = {0}; uint_t index[n] = {0}; uint_t j; for(uint_t i=0; i<4096; i++) { if(counter[i] > best[n-1]) { for(j=n-2; j && counter[i] > best[j]; j--); /* Find the insertion position, as our value might be bigger than the value at position n-1. */ memmove(&best [j+1], &best[j] , (n-1 -j) * sizeof best[0]); /* Shift the values beyond j up 1 */ memmove(&index[j+1], &index[j], (n-1 -j) * sizeof index[0]); best[j] = counter[i]; /* Put the current best value at the top */ index[j] = i; /* Store the index in the second array to know where the best } 

value was. * /}}

In this case, you compare your values ​​only once, and the cost of memmove negligible, because your array of choice is small. There is no need to sort the array, this algorithm is O (n), the best type is O (n.log2 n)

EDIT : I added an array for the index. EDIT2 : the second one was introduced to fix the main error that I had in the first case. EDIT3 : Comment: memmove with size 0 is allowed and is basically nop.

Answer 2

Bubble sort is slow ... O (N ^ 2) complexity ... if you want to improve performance, use a data structure like a heap, or run a quick sort algorithm on your array, both of which will give you O ( N log N) for the sorting process. In addition, both methods will work well on fixed-length arrays.