Compare julia sum to a cpp implementation - julia is extremely slow?!

[Tamas_Papp]

Not for integers though.

That said, while comparisons are always interesting, summing an array is an O(1) operation that most mature compilers optimize to death, and interpreted languages have built-ins for. So it may not be the most informative benchmark for real-life use.

[tobias.knopp]

@Tamas_Papp

Not for integers though.

True, then its interesting, why Julia is slower.

[Sukera]

Have you tried starting julia with O3 as well?

[kristoffer.carlsson]

@stakaz

However, I see that julia code is becoming slower as the array increases while cpp code remains const in time.

When this happens, your instinct should be to start question the C++ code, not the Julia code… Clearly, if the time measured to sum something doesn’t change with the size of the thing you sum, something is off.

@stakaz

Ok, so this manually defined version of a sum is much faster in julia:

They don’t give the same answer though. Julia widens in sum to prevent overflow:

julia> mysum(A)
-117 # Int8

julia> sum(A)
1376139 # Int64

see the docstring for sum:

The return type is Int for signed integers of less than system word size, and UInt for unsigned integers of less than system word size.

Keeping things in the Int8-domain means that you can fit a lot more numbers in each simd lane which will dramatically speed things up.

When benchmarking:
1 ) Be careful you are actually measuring what you want to measure.
2) Make sure that the things you compare compute the same thing.

[kristoffer.carlsson]

@Tamas_Papp

summing an array is an O(1) operation that most mature compilers optimize to death

Summing an array is O(n) though?

[stakaz]

@kristoffer.carlsson

They don’t give the same answer though.

Sorry, my fault. With S = 0 as a starting point I now get the following results:

L = 10
  139.358 ns (0 allocations: 0 bytes)
  102.533 ns (0 allocations: 0 bytes)
L = 100
  7.543 μs (0 allocations: 0 bytes)
  6.099 μs (0 allocations: 0 bytes)
L = 1000
  722.445 μs (0 allocations: 0 bytes)
  635.842 μs (0 allocations: 0 bytes)
L = 10000
  75.421 ms (0 allocations: 0 bytes)
  65.100 ms (0 allocations: 0 bytes)

@kristoffer.carlsson

1 ) Be careful you are actually measuring what you want to measure.
2) Make sure that the things you compare compute the same thing.

Yeah, thanks, I’ve tried but failed at this particular points

[stakaz]

Yes, I am always with -O3 flag…

[kristoffer.carlsson]

I challenge you to find any workload that will be faster with -O3 than the default. Since the SLP optimization pass got moved from -O3 to -O2 (default) there is almost no point of -O3.

[stakaz]

@kristoffer.carlsson

I challenge you to find any workload that will be faster with -O3 than the default. Since the SLP optimization pass got moved from -O3 to -O2 (default) there is almost no point of -O3 .

Ok, nice to know.

@tobias.knopp

True, then its interesting, why Julia is slower.

Yes, this is also a question for me here.

[kristoffer.carlsson]

sum dispatches to a generic mapreduce that does some blocking in the evaluation which has a tiny bit of overhead:

julia> @btime sum($A)
  30.160 μs (0 allocations: 0 bytes)
1377411

julia> @btime mysum($A)
  29.863 μs (0 allocations: 0 bytes)
1377411

[mbauman]

@stakaz

tobias.knopp:

True, then its interesting, why Julia is slower.

Yes, this is also a question for me here.

Could you re-post/consolidate the MWE where Julia is still summing slower the C++? It’s gone through so many iterations that it’s no longer clear if or how things are still slower.

[Tamas_Papp]

@kristoffer.carlsson

Summing an array is O(n) though?

Right, thanks for the correction.

[stakaz]

@mbauman

Could you re-post/consolidate the MWE where Julia is still summing slower the C++? It’s gone through so many iterations that it’s no longer clear if or how things are still slower.

Yes, I finally got some time to test it further. I simplified to 1d array as it turns out to be the case for them as well.

The julia code is:

using BenchmarkTools

function mysum(A) 
	S = 0
	@simd for i ∈ eachindex(A) 
		@inboundsS += A[i] 
	end
	return S 
end

for L ∈ [1_000, 10_000, 100_000, 1000_000]
	@show L
	A = fill(Int8(1), L)

	@assert sum(A) == mysum(A)
	@btime sum($A)
	@btime mysum($A)
end

and the cpp code is:

#include <iostream>
#include <cstdlib>

#include <vector>
#include <chrono>

template <typename T>
int sum(std::vector<T> &A)
{
	int S = 0;
	for (auto x = 0; x < size(A); ++x)
			S += A[x];
	return S;
}


int main()
{
	for (auto L : {1000, 10000, 100000, 1000000})
	{
		std::vector<int8_t> A(L, 1);
			for (auto x = 0; x < size(A); ++x)
					A[x] = 1;

		auto N = 1000;
		auto t_total = std::chrono::duration<double>(0);
		for (auto i = 1; i <= N; ++i)
		{
			int S = 0;
			auto t_start = std::chrono::steady_clock::now();
			S = sum(A);
			auto t_end = std::chrono::steady_clock::now();
			t_total += t_end - t_start;
			std::cerr << S << std::endl;
		}

		t_total /= N;
		std::cout << "L = " << L << std::endl;
		std::cout << "  t = " << std::chrono::duration_cast<std::chrono::nanoseconds>(t_total).count()  << " ns\n" << std::endl;
	}
	return 0;
}

This gives the following times on my machine (julia version 1.3.0-rc2, gcc 9.1.0)

function	julia sum	julia mysum	cpp
L = 1E3	0.647 μs	0.632 μs	0.467 μs
L = 1E4	7.543 μs	6.099 μs	6.655 μs
L = 1E5	73.753 μs	63.695 μs	30.370 μs
L = 1E6	725.797 μs	638.634 μs	469.401 μs

It is clearly that cpp outperforms for larger L but sum and mysum are close while mysum is a bit faster as expected from @smid macro.

I hope this helps…

[mbauman]

Interesting. On my machine with both g++ (9.2.0) and clang++ (10.0.1) with flags -std=c++11 -O3, I’m seeing Julia faster across the board with your script.

function	julia sum	julia mysum	cpp (clang)	cpp (g++)
L = 1E3	0.061 μs	0.064 μs	0.136 μs	0.184 μs
L = 1E4	0.728 μs	0.599 μs	0.909 μs	1.336 μs
L = 1E5	6.637 μs	5.707 μs	8.418 μs	12.773 μs
L = 1E6	65.766 μs	58.442 μs	70.558 μs	102.826 μs

Edit: although note that @btime prints the minimum time whereas your C++ program is computing the average time. Changing it to mean(@benchmark(...)) only increases the Julia numbers by about 10%, leaving the conclusion the same.

What CPU are you on? This is on an i7-9750H.

[foobar_lv2]

@stakaz

int S = 0;

Julia Int and C int are different. Consider using either long int or Int32.

[stakaz]

@foobar_lv2

Julia Int and C int are different. Consider using either long int or Int32 .

Yeah, again I was too hasty about the comparison. Now, whne using long int and taking the mean value of the time in julia as

@mbauman

mean(@benchmark(…))

I finally have these results:

function	julia sum	julia mysum	cpp
L = 1E3	0.678 μs	0.662 μs	0.582 μs
L = 1E4	8.396 μs	6.706 μs	18.32 μs
L = 1E5	77.10 μs	67.13 μs	142.2 μs
L = 1E6	751.0 μs	670.3 μs	1435 μs

This is nice to see for a julia user but I now wonder why cpp is so much slower here? I don’t see a reason for it but maybe someone still sees some “bugs” in the cpp code…

@mbauman

What CPU are you on?

The times are measured on a Intel(R) Pentium(R) CPU N3530 @ 2.16GHz.