NVIDIA / NVIDIA/cccl

[BUG]: Low performance of sorting with OMP backend

Open
#1,244 2 comments 1 reaction 0 assignees View on GitHub
Dominant language
C++
Stars
2.5k
Forks
486
Avg merge
2d 6h
Merged PRs (30d)
295

Description

### Is this a duplicate?

- [X] I confirmed there appear to be no [duplicate issues](https://github.com/NVIDIA/cccl/issues) for this bug and that I agree to the [Code of Conduct](CODE_OF_CONDUCT.md)

### Type of Bug

Performance

### Component

Thrust

### Describe the bug

Performance of `thrust::sort` with OpenMP backend seems to be far worse than even standard `std::sort`. The code provided in "How to reproduce" section compares timings of sorting with `std` and `thrust`. I tested it on two machines, one with AMD Ryzen 5950X and 32GB DDR4 memory, and the other with Intel i7-1365U and 32GB DDR5 memory, both on Fedora 38 operating system. In the first case, `std::sort` manages to sort `100 000 000` floats in 32s and thrust performs the same task in ~87s. In the second case, the timings are ~31s and ~117s respectively. Looking at htop it seems that thrust indeed uses some parallelization as all cores being used.

### How to Reproduce

1. Save the following file as `sorting_comparison.cpp`:
```C++
#include
#include
#include
#include
#include

#include
#include

using namespace std;
using namespace std::chrono;

const int VEC_SIZE = 100'000'000;

vector random_vector(int size) {
vector data(size);
random_device rnd_device;
mt19937 mersenne_engine{rnd_device()};
uniform_real_distribution dist{-10.0f, 10.0f};

generate(begin(data), end(data),
[&dist, &mersenne_engine]() { return dist(mersenne_engine); });

return data;
}

int main() {
vector data = random_vector(VEC_SIZE);
thrust::device_vector data_for_thrust(data);

auto start = high_resolution_clock::now();
sort(begin(data), end(data));
auto stop = high_resolution_clock::now();
cout << "std took: " << duration_cast(stop-start).count() << "s" << endl;

start = high_resolution_clock::now();
thrust::sort(begin(data_for_thrust), end(data_for_thrust));
stop = high_resolution_clock::now();
cout << "thrust took: " << duration_cast(stop-start).count() << "s" << endl;

return 0;
}
```
2. Make sure thrust is available in include path and compile the file with:
```bash
g++ -fopenmp -lgomp -DTHRUST_DEVICE_SYSTEM=THRUST_DEVICE_SYSTEM_OMP sorting_comparison.cpp -o sorting-comparison
```
3. Run `./sorting-comparison`, it should print timings for `std::sort` and `thrust::sort` to stdout.

### Expected behavior

I would expect `thrust::sort` to be at least as fast as `std::sort`.

### Reproduction link

_No response_

### Operating System

Fedora 38

### nvidia-smi output

N/A

### NVCC version

N/A

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.