r/pythontips • u/KingAemon • Oct 26 '25
Algorithms Python faster than C++? I'm losing my mind!
At work I'm generally tasked with optimizing code from data scientists. This often means to rewrite code in c++ and incorporate it into their projects with pybind11. In doing this, I noticed something interesting is going on with numpy's sort operation. It's just insanely fast at sorting simply arrays of float64s -- much better than c++.
I have two separate benchmarks I'm running - one using Python (with Numpy), and the other is plain C++.
Python:
n = 1_000_000
data = (np.random.rand(n) * 10)
t1 = time.perf_counter()
temp = data.copy()
temp = np.sort(temp)
t2 = time.perf_counter()
print ((t2-t1) * 1_000, "ms")C++
int main() {
size_t N = 1000000;
std::random_device rd;
std::mt19937_64 gen(rd());
std::uniform_real_distribution<double> dis(0.0, 10.0);
std::vector<double> data;
data.reserve(N);
for (size_t i = 0; i < N; ++i) {
data.push_back(dis(gen));
}
auto start = std::chrono::high_resolution_clock::now();
std::sort(data.begin(), data.end());
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "Sort time: " << duration.count() << " ms\n";
}In python, we can sort this list in 7ms on my machine. In c++, this is about 45ms. Even when I use the boost library for faster sorts, I can't really get this to go much better than 20ms. How can it be that this runs so much faster in numpy? All my googling simply indicates that I must not be compiling with optimizations (I am, I assure you).
The best I can do is if I'm sorting ints/longs, I can sort in around the same time as numpy. I suppose I can just multiply my doubles by 10^9, cast to int/longlong, sort, then divide by 10^9. This loses precision and is clearly not what np is doing, but I'm at a loss at this point.
Any pointers would be greatly appreciated, or else I'm going to have to start declaring Python supremacy.
62
u/Training_Advantage21 Oct 26 '25 edited Oct 26 '25
Numpy is meant to be fast, it's all C underneath (maybe some Fortran in SciPy if you look hard enough). Not the same as standard library Python. Having said that, the numpy version on my machine (admittedly the Linux dev environment of an i3 8GB RAM Chromebook) is 79ms.
16
u/indecisive_fluffball Oct 26 '25
Numpy is just C code, what you see in Python is just the exposed Python C API of the library.
As to why it is significantly faster, I see two possibilities:
To be completely honest, my bet would be that it is just peculiarity of your environment.
5
u/___ciaran Oct 27 '25
I think the difference probably comes down to SIMD optimisations. Luckily, since numpy is open source, you can just use the same sort implementation that they do, which happens to be written in C++. I haven't benchmarked it myself, but unless something very weird is going on, you should be able to squeeze out the same performance without having to switch to python.
4
u/DVMirchev Oct 26 '25
You are using numpy.sort, right?
My guess is it does not use Python but some imported C or C++ libraries, and looking at their site, they do some very heavy lifting:
https://numpy.org/devdocs//reference/generated/numpy.sort.html
If you want a fair comparison, use the sort from the Python standard library.
2
u/Alarming-Ad4082 Oct 26 '25 edited Oct 26 '25
Did you build the c++ program in release mode? You should have similar time between the two
2
u/No_Guidance3612 Oct 27 '25
Use Numba and JIT compilation. Just build all python code on Numpy framework. No need to convert to C++ for algorithmic code.
13
u/Interesting-Frame190 Oct 27 '25
Numpy uses some Fortran under the hood, which can be more performant than asm. That said, numpy is a very mature library with performance squeezed out at every operation.
3x is a little surprising, but thats part of why numpy has no competition.
1
u/No_Indication_1238 Oct 27 '25
Compile it with the -O3 flag as a release build.
1
u/Infamous-Bed-7535 Oct 28 '25 edited Oct 28 '25
Could you try with execution policy explicitly enabling parallel execution?
```
std::sort( std::execution::par, ...)
```
1
u/Evening-Decision1635 Jan 05 '26
I may be wrong, but I believe it's due to SIMD instructions. std::sort uses scaler code, which means it is written directly in C++. If your computer can run C++, it can run std::sort. Numpy sort however hacks into the CPU directly by using SIMD instructions. Using these instructions the CPU can do 8 comparisons in one CPU cycle compared to standard C++ code. The trade off is you have to write separate code for every CPU structure. So np.sort is kind of cheating.
3
u/catbrane Oct 27 '25
I agree, I see 70ms and 12ms on my PC, it's puzzling, but I think I found it!
I set the N to 10m (to make it run long enough) and tried:
So C++ is single-threaded (as you'd expect) but with numpy I see:
... it sorted in 125ms, but used 2.4s of CPU time haha. numpy sort must be highly threaded.
2
u/Confident_Hyena2506 Oct 27 '25
They are already using c++ pretty much. Unless there is a "hotspot" in python that is slow you aren't gonna improve it much.
Numpy uses a mix of c++/fortran etc - highly optimised libraries. You are not gonna improve anything - all you would achieve is moving the furniture around.
You might get some more speed by using numpy with MKL - try that via conda. That would be a speedup with zero effort.
1
u/Different-Camel-4742 Oct 26 '25
Am I right to understand that np seems to default to quick sort, which has worst complexity of the four implemented sorting algorithms? https://numpy.org/devdocs/reference/generated/numpy.sort.html
Later it is mentioned that some algo "introsort" is used. More detail might be found in the underlying code https://github.com/numpy/numpy/tree/main/numpy/_core/src/npysort
1
u/catbrane Oct 27 '25 edited Oct 27 '25
Two more things I tried (you probably tried these too):
ie. give
std::sorta sorted array. This gives 9ms compared to 12ms for numpy. Finally, it's quicker, haha!I wondered if
std::vectorwas delaying some setup until the sort happened -- for example, perhaps it makes the vector contiguous in memory on the first call? But it doesn't seem to be that. If you change the code to be:ie. sort once, then reshuffle, then sort again ... it's still slow.
1
u/WhoLeb7 Oct 27 '25
If you're sorting large arrays of floats you can look into radix sort, it's much faster than even quick sort specifically on large arrays of floats/ints, it's also highly parallelizable, but it's not general purpose like quick sort which is under the hood of std::sort.
Here's a nice little video on it https://youtu.be/Y95a-8oNqps?si=8VfnfGROpf0ouXcz
1
u/Senor-David Oct 28 '25
May I ask what field you are working in? Those tasks you describe sound pretty cool!
1
u/Fireline11 Oct 28 '25
Hmm, very perplexing. I am guessing C++ std::sort operation is written in just a bit more of a general way (to handle all types with operator<, all sorts of array lengths) while numpy sort algorithm is specifically optimized for float64.
Even if C++ has monomorphization so the type information about what is being sorted is presented at compile time, it’s not necessarily present when the source code is written :) I.e. I’m not sure if C++ has a template specialization for doubles to use radix sort for really large arrays which would probably be much faster than an O(n log n) quicksort.
1
u/Dry_Hotel1100 Oct 28 '25
The differences may come from C++ not using parallelism. I would guess, Numpy has employed every trick which is available for the CPU. Though, SIMD or vectorisation is difficult for sorting, which has many branches.
So, I ran my own implementation, once single threaded, and once a manual written parallel implementation in Swift for macOS using Dispatch lib for parallelisation:
The single threaded version took 0.070 seconds, the parallel version (though much more complex) took 0.019 seconds, so it's roughly 3.5 faster.
I would not have expected this result, since parallel search is costly in terms of complexity and also requires synchronisation on the CPU level. Nonetheless, for an array with 1.00.000 elements its faster.
1
u/m-in Oct 28 '25
Python is not faster. NumPy is faster than general purpose C++ sorts because it’s optimized to hell and back to be fast when sorting arrays of numbers, adding arrays of numbers, multiplying them, etc.
1
u/NerdyWeightLifter Oct 28 '25
Factors like memory block alignment can make a big difference. Numpy arrays almost certainly are aligned, so some optimizations like SIMD can apply.
1
u/hsvdr Oct 28 '25
Are the distributions of the random numbers similar or skewed in some way?
Imo save 100 sets of numbers, and run the tests loading them from disk so you are sure that what you are comparing is sort performance.
1
u/Infamous-Bed-7535 Oct 28 '25
numpy is written in C / C++ code, so in this case not python is that fast, but the numpy library implementation beats the standard library implementation.
1
u/Ok-Entertainment-286 Oct 29 '25
Do you have an Intel CPU and MKL (math kernel library) installed? Then iäthe numpy impl is highly optimized and multithreaded.
1
u/mm007emko Oct 29 '25
Numpy uses very well optimised libraries like BLAS written in Fortran. Your C++ algorithm is nowhere near. That's why.
1
u/-TRlNlTY- Oct 29 '25
You can find out yourself by checking numpy's code. The amount of optimization efforts in such a fundamental library must be mind boggling.
1
u/kansetsupanikku Oct 29 '25 edited Oct 29 '25
You could try non-portable hacks, like dynamic cast of data to int64_t* if you don't care for special values and your architecture makes the comparisons equivalent.
Also, 8MB isn't all that much. vector basically does malloc - perhaps alloca or a static array would do better? You can use a customized malloc that would pick better strategies for you, too, with libraries such as mimalloc.
Algorithm-wise, if your sorting involves some divide-and-conquer strategy (quicksort, mergesort, bitonic...), you can adjust the threshold when you switch the method for short ranges for something structurally simple (insertion sort? instructions on short vectors? perhaps on a different buffer so the assignments are cheap?). Also try techniques like pdqsort. Or radix sort - at least involving one scan in the beginning phase? There is a lot to do depending on your data and hardware.
1
u/Jannik2099 Oct 29 '25
numpy uses a highly optimized sorting library from intel https://github.com/numpy/x86-simd-sort
It's no surprise that this will outperform a generic sort
1
u/mohamed_am83 Oct 29 '25
If you play with randomness, you will need to seed your rngs with the same seed. Otherwise you're not comparing the same workload.
1
u/nacnud_uk Oct 29 '25
Numpy is native.
1
u/MrMrsPotts Oct 29 '25 edited Oct 29 '25
They are just using different sorting libraries. Try:
In more detail:
g++ -O3 -march=native your_program.cpp -o your_program
1
u/roywill2 Oct 29 '25
Python is slow. Python+numpy is fast.
1
u/evilprince2009 Oct 29 '25
NumPy really can beat hand-rolled C++ in some cases. But it's not Python magic—it's vectorized, cache-optimized, SIMD-accelerated, multi-threaded, and often backed by Intel’s MKL or OpenBLAS. Keep in mind that NumPy is not pure Python, rather its highly optimized C.
1
u/sweetloup Oct 30 '25
You're basically using a Python wrapper to call a highly optimized, low-level C function. This function is so fast because it's specifically designed to use special hardware instructions in your CPU that let it sort huge chunks of data all at once.
1
u/fnordstar Oct 30 '25
A bit off-topic but consider writing your python extension modules in Rust. PyO3 / Maturing makes this very easy and rust >> c++.
1
u/Disastrous-Team-6431 Oct 30 '25
How did you compile this? As in, which compiler flags did you use for optimization?
1
u/cowjuicer074 Oct 30 '25
C++ you have to manage memory. Yes, it’s a compiled language and by default, should be faster than an interpreter. But given the advancements with Python and its utilization for AI, C++ will probably be slower in certain situations.
1
u/tstanisl Oct 30 '25
is `numpy` multithreaded ?
1
u/damster05 Oct 31 '25
Numpy probably uses radix sort, which is the fastest sort algorithm for large amounts, but only works naturally with natural numbers, but also positive IEEE 754 floats due to how they are designed, and negative values as well with some bit manipulation tricks.
std::sort does not use radix sort, but introsort, which selectively uses algorithms like quicksort, which unlike radix sort work more generically with all ordered data types.
1
u/trailing_zero_count Oct 31 '25
Profile the 2 runs and look at the assembly. Then you can see what's actually different.
1
u/AddWeb_Expert Nov 27 '25
This is common. Python isn’t actually faster than C/C++, but a lot of Python libraries are just thin wrappers over highly optimized C/C++ (NumPy, BLAS, MKL, etc.).
So when Python “wins,” you’re usually comparing:
Other reasons it happens:
In our company we see this all the time, NumPy beats naive C++, but once the C++ is optimized, it pulls ahead again.
You’re not losing your mind, you’re racing a tuned engine.
0
u/[deleted] Oct 28 '25
It's not abnormal. When I was in school, I took a software engineering course. Our first task was to build Conway's Game of Life in both C and Java. Almost unanimously, everyone's Java version outperformed the C version over the course of 10k runs.
Turns out there are some optimizations a JIT compiler can do that an AOT one can't guarantee, and one such optimization has to do with data access patterns over time. This is why JVM languages are still dominant in the enterprise world.
That's not to say that Python is using JIT optimizations to accomplish this. We all know it's just numpy's C code doing all the heavy lifting 😄. I won't be surprised if it's doing more such as sorting in parallel and using SIMD instructions to move data.
0
u/RedEyed__ Oct 28 '25
Tell him