I coded two small projects in C++ and D(lang) respectively to calculate a given number of prime numbers. The code is very similar in both projects. However, my D code runs MUCH faster than my C++ code, even though C++ is said to be faster. I use dmd and dub for compiling D code and clang (LLVM 11.0) with Visual C++ for compiling my C++ code. I use Visual Studio Code for actually developing and compiled my C++ program from the command line, though with -O3. I am sorry if some variable names don't match up, I quickly translated my code from German. Below is my code:
main.cpp:
#include <iostream>
#include <chrono>
#include <vector>
#include "isqrt.hpp"
bool prime(int number)
{
for(unsigned i = 2; i < isqrt(number)+1; i++)
{
if (!(number % i))
{
return false;
}
}
return true;
}
int main(int argc, char *argv[])
{
std::cout << "Prime numbers\n-------------------------\n" << std::endl;
while (true)
{
std::cout << "Please enter the amount of prime numbers you want to get calculated: ";
unsigned amount;
std::cin >> amount;
std::vector<unsigned> prime_numbers = {2,3,5};
unsigned start = 6;
bool p;
std::chrono::system_clock::time_point before = std::chrono::system_clock::now();
while(prime_numbers.size() < amount)
{
p = prime(start);
if(p)
{
prime_numbers.push_back(start);
}
start++;
}
std::chrono::system_clock::time_point after = std::chrono::system_clock::now();
//std::cout << prime_numbers << std::endl;
std::chrono::system_clock::duration diff = after - before;
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(diff).count() << std::endl;
}
std::cout << "Why has thou forsaken me?" << std::endl;
return 0;
}
isqrt.hpp:
#ifndef ISQRT_HPP
#define ISQRT_HPP
unsigned isqrt(unsigned number);
#endif
isqrt.cpp:
#include "isqrt.hpp"
unsigned isqrt(unsigned number) {
if (!number) return 0;
unsigned left = 1;
unsigned right = (number >> 1) + 1;
unsigned res;
unsigned mid;
while (left <= right) {
mid = left + ((right-left) >> 1);
if (mid*mid < number){
left = mid+1;
res=mid;
}
else {
right=mid-1;
}
}
return res;
}
main.d:
import std.stdio;
import std.datetime.stopwatch;
import isqrt;
/** Whether the number is a prime */
bool prime(int number)
{
foreach(i; 2 .. iSqrt(number)+1)
{
if (!(number % i))
{
return false;
}
}
return true;
}
void main()
{
writeln("Prime numbers\n-------------------------\n");
auto sw = StopWatch(AutoStart.no);
int amount;
while (true)
{
sw.reset();
write("Please enter the amount of prime numbers that are to be calculated: ");
readf("%d\n",amount);
int[] prime_numbers = [2,3];
int start = 5;
bool p;
sw.start();
while(prime_numbers.length < amount)
{
p = prime(start);
if(p)
{
primzahlen ~= start;
}
start++;
}
sw.stop();
//writefln("%(%s%|, %)\n",prime_numbers);
writeln(sw.peek.total!"msecs");
}
}
isqrt.d:
module isqrt;
/** Int squareroot */
public uint iSqrt(uint number) {
if (!number) return 0;
uint left = 1;
uint right = number >> 1 + 1;
uint res;
uint mid;
while (left <= right) {
mid = left + ((right-left) >> 1);
if (mid<=number/mid){
left = mid+1;
res=mid;
}
else {
right=mid-1;
}
}
return res;
}
If you slightly change your main.cpp
diff main.old.cpp main.cpp
9c9,10
< for(unsigned i = 2; i < isqrt(number)+1; i++)
---
> int max = isqrt(number) + 1;
> for(unsigned i = 2; i < max; i++)
And rebuild your C++ code again
g++ -O3 -o cppisqrt isqrt.cpp main.cpp
You will see that C++ version is only slightly slower then D version compiled with
gdc -O3 -o disqrt isqrt.d main.d
I wanted to be fair and used the same compiler backend (G++ and GDC both use GCC backend). On my home workstation C++ variant takes ~1140ms (average of 10 samples) for 200000 numbers, while D variant takes ~1090ms (also 10 samples mean).
Both G++ and GDC produce similar code:
GCC 10.2 x86-64 on https://godbolt.org produces
isqrt(unsigned int):
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-20], edi
cmp DWORD PTR [rbp-20], 0
jne .L2
mov eax, 0
jmp .L3
.L2:
mov DWORD PTR [rbp-4], 1
mov eax, DWORD PTR [rbp-20]
shr eax
add eax, 1
mov DWORD PTR [rbp-8], eax
.L7:
mov eax, DWORD PTR [rbp-4]
cmp eax, DWORD PTR [rbp-8]
ja .L4
mov eax, DWORD PTR [rbp-8]
sub eax, DWORD PTR [rbp-4]
shr eax
mov edx, eax
mov eax, DWORD PTR [rbp-4]
add eax, edx
mov DWORD PTR [rbp-16], eax
mov eax, DWORD PTR [rbp-16]
imul eax, eax
cmp DWORD PTR [rbp-20], eax
jbe .L5
mov eax, DWORD PTR [rbp-16]
add eax, 1
mov DWORD PTR [rbp-4], eax
mov eax, DWORD PTR [rbp-16]
mov DWORD PTR [rbp-12], eax
jmp .L7
.L5:
mov eax, DWORD PTR [rbp-16]
sub eax, 1
mov DWORD PTR [rbp-8], eax
jmp .L7
.L4:
mov eax, DWORD PTR [rbp-12]
.L3:
pop rbp
ret
GDC 10.2 x86-64 on https://godbolt.org produces
uint example.iSqrt(uint):
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-20], edi
cmp DWORD PTR [rbp-20], 0
jne .L2
mov eax, 0
jmp .L3
.L2:
mov DWORD PTR [rbp-4], 1
mov eax, DWORD PTR [rbp-20]
shr eax, 2
mov DWORD PTR [rbp-8], eax
mov DWORD PTR [rbp-12], 0
mov DWORD PTR [rbp-16], 0
.L7:
mov eax, DWORD PTR [rbp-4]
cmp eax, DWORD PTR [rbp-8]
ja .L4
mov eax, DWORD PTR [rbp-8]
sub eax, DWORD PTR [rbp-4]
shr eax
mov edx, eax
mov eax, DWORD PTR [rbp-4]
add eax, edx
mov DWORD PTR [rbp-16], eax
mov eax, DWORD PTR [rbp-20]
mov edx, 0
div DWORD PTR [rbp-16]
cmp DWORD PTR [rbp-16], eax
ja .L5
mov eax, DWORD PTR [rbp-16]
add eax, 1
mov DWORD PTR [rbp-4], eax
mov eax, DWORD PTR [rbp-16]
mov DWORD PTR [rbp-12], eax
jmp .L7
.L5:
mov eax, DWORD PTR [rbp-16]
sub eax, 1
mov DWORD PTR [rbp-8], eax
jmp .L7
.L4:
mov eax, DWORD PTR [rbp-12]
.L3:
pop rbp
ret
PS. D version does not need that public specifier in this case.