Radix Sort function

Question

I am working with this assignment of optimizing a radix sort code in C++ and I need to reduce the execution time. My code is working and it looks like this:

void RadixSort::RadixSortNaive(std::vector<long> &Arr) {

long Max_Value = findMax(Arr);

    int Max_Radix = 1;
while (1) {
  if (Max_Radix >= Max_Value) break;
  Max_Radix = Max_Radix*radix_;
}

for (int i = 1; i < Max_Radix; i = i*radix_) {
  for (int j = 0; j < key_length_; j++) {
    int K;
    if (Arr[j] < i) K = 0;
    else K = (Arr[j] / i) % radix_;
    Q[K].push(Arr[j]);
  }

  int idx = 0;
  for (int j = 0; j < radix_; j++) {
    while (Q[j].empty() == 0) {
      Arr[idx] = Q[j].front();
      Q[j].pop();
      idx++;
    }
  }
}
class RadixSort{
public :

  void setConfig(int key_length, int radix) {
    key_length_ = key_length;
    radix_ = radix;
    for (int i = 0; i < radix_; i++) {
      Q.push_back(std::queue<long>());
    }
  }

  long findMax(std::vector<long> Arr) const {
    long Max = 0;
    for (int i = 0; i < key_length_; i++) {
      if (Max < Arr[i])
        Max = Arr[i];
    }
    return Max;
  }

  void RadixSortNaive(std::vector<long> &Arr);
  void RadixSortStudent(std::vector<long> &Arr);

private:
  int key_length_;
  int radix_;
  std::vector<std::queue<long>> Q;
};

}

However, I am sure that there is still room for improvement. I have been trying to implement parallelization with OMP library but nothings seemed to work. Is there any way where I can improve the previous code? Maybe improving the loops or any other code optimization technique.

Answer 1

Firstly, please put the headers:

#include <vector>
#include <algorithm>
#include <queue>

I wonder if you could may be do this set up in a constructor or something. Because otherwise you are just telling the user to do a two-phase initialization. If the user of this class misses this, the function won't work.

void setConfig(int key_length,int radix) {
            key_length =key_length;
            radix_ = radix;
            for (int i = 0; i < radix_; i++) {
                Q.push_back(std::queue<long>());
            }
        }

Thirdly, find max does not consider negative numbers for some reason. It is also public. Ideally, one can replace it with a call to a library function:

long findMax(std::vector<long> Arr) const {
        return *max_element(Arr.begin(), Arr.end());
       
    }

Fourthly, you are basically calculating the maxRadix from maxValue and using for the iteration:

while (1) {
            countNumber++;
            if (Max_Radix >= Max_Value) break;
            Max_Radix = Max_Radix * radix_;
        }

When in reality you can use MaxValue as the limit to your final iteration. I hope you get the idea, I have not tested this, but I guess this should work fine.

for (int i = 1; i < Max_Value; i = i * radix_)
 

       
       

Answer 2

Most books/algorithm focus on optimizing without taking into account caching (data locality) and branch prediction. Those aspects are very important to performance on a (large) CPU. So the next things you need to do is understand how your input data is organized (which helps you optimize branch prediction and dat locality)and to start measuring your code performance using a profiler.

Just to give you an idea on how weird sorting data can be watch this : CppCon 2019: Andrei Alexandrescu “Speed Is Found In The Minds of People" https://www.youtube.com/watch?v=FJJTYQYB1JQ.