Reversing bits in byte in C

Question is: what is the fastest and portable way to reverse bits in byte in C?

I have read article on corner.squareup.com and choose two faster portable functions.
I made additional comparing of function performance.
Comparing environment: ideone.com. Compiler: gcc-4.7.2.
Below is code:

 
Here is results of performance testing: 
200000000 calls of ReverseBitsSimpleAndElegant takes 1.660000 seconds.
200000000 calls of ReverseBitsLookupTable takes 0.980000 seconds.
200000000 calls of ReverseBits7ops32bit takes 0.920000 seconds.

So, function ReverseBits7ops32bit is the fastest way which i has found.
Let me know if you find faster way. I will check.

What does std::make_heap do?

std::make_heap reorder elements in container to satisfy definition of binary max heap.

Building binary max heap algorithm
Here is algorithm from wiki in pseudo code.
Function Build-Max-Heap calls Max-Heapify which do the main part of job [1].

Max-Heapify (A, i):
 left ← 2i
 right ← 2i + 1
 largest ← i
 if left ≤ heap_length[A] and A[left] > A[largest] then:
 largest ← left
 if right ≤ heap_length[A] and A[right] > A[largest] then:
 largest ← right
 if largest ≠ i then:
 swap A[i] ↔ A[largest]  
 Max-Heapify(A, largest)

Build-Max-Heap (A):
 heap_length[A] ← length[A]
 for i ← floor(length[A]/2) downto 1 do
 Max-Heapify(A, i)

Implemenation of building binary max heap algorithm in C++
Below is code with implemenation of functions defined in pseudo code above.



Result of code execution is:

9 8 7 4 5 6 3 2 1 

Execution result it is result positions of elements in vector:

Representation of this array as binary heap:

Refrences
[1]. Binary heap From Wikipedia, the free encyclopedia.

What is faster: std::sort or std::make_heap + std::sort_heap?

At first lets consider time complexity of algorithms.

Time complexity of std::sort.
According to the C++ standard, sort is required to perform O(NlogN) comparsions on average but has worst-case complexity of O(N*N), where N is last - first. This latitude, however, is unnecessary. It is possible to implement sort so that the number of comparsions, both average and worst-case, is only O(NlogN) [1].

Time complexity of std::make_heap.
Linear. At most 3N comparsions, where N is last - first.

Time complexity of std::sort_heap.
At most NlogN comparsions, where N is last - first.

Time complecity of std::make_heap +std::sort_heap in the worst-case is 3N + NlogN.

Performance testing.
Code below has been run on ideone.com with gcc 4.7.2. in testing purpose.


Performance testing results.
On reverse range std::sort can be slower than std:make_heap + std::sort_heap in 2 times.

==== Comparing std::sort vs std::sort_heap performance. ===
==== Range types: sorted, reversed, random  ===
==== Range size is 10000000.    ===

==== std::sort results:
Consumed time for sorted range: 0.340000 sec.
Consumed time for reversed range: 2.520000 sec.
Consumed time for random range: 1.110000 sec.

==== std::make_heap+std::sort_heap results:
Consumed time for sorted range: 1.060000 sec.
Consumed time for reversed range: 1.260000 sec.
Consumed time for random range: 4.660000 sec

Conclusions
std::sort can be slower then std::make_heap +std::sort_heap in N/(3 + logN) times in worst-case. But, in average std::sort is faster.

References
[1]. Matthew H. Austern. Generic Programming and the STL: Using and Extending the C++ Standard Template Library. ISBN 0-201-30956-4.


 

What is faster: multidimensional array or inline function?

Suppose given simple function which depends from four parameters f(i, j, c, k) = abs(i-c) + abs(c-k), where i, j, c, k are less than 100.
The question is: what is the faster way: use inline function which compute each result every time or to build multidimensional array res[i][j][c][k] once with all possible answers?

I have checked this case with i, j, c, k is less than 45 with using gcc 4.7.2.
Here are results: 
Time for array is: 5.410000 sec. 
Time for inline function is: 5.410000 sec. 

Conclusions. Time of executions is the same, because inline function is quite simple. Benefit of inline function is more understandable way of result calculation without using extra memory. So, if function is quite simple there is no reason to create multidimensonal array with cached results.

Below is the code which I used to check performance.