Trädvy Permalänk
Medlem
Registrerad
Apr 2002

C++ vs JavaScript prestanda

Hej

Jag sitter och leker lite med C++ vs JavaScript / NodeJS. Gjorde ett litet test där jag tänkte försöka jämföra prestanda.
Skrev ett program i C++ för att räkna fram "perfekta tal" "brute force" https://sv.wikipedia.org/wiki/Perfekt_tal. Skrev sedan motsvarande i JavaScript med samma algoritm. Testar med ex 40 000 tal, tiden det tar för C++ att räkna sig igenom detta är 5600ms. Med JavaScript gör jag samma beräkning på ca 2100ms.
Har kört "build release" på C++ i både Xcode och QT creator, men med i stort sett samma resultat. Borde det inte vara tvärtom resultatmässigt?

Någon som kan ge en vettig förklaring till detta? Antar att JavaScript optimerar på något sätt som ger denna skillnad. Har det någon med hanteringen av long int i C++ att göra? Hur skulle jag kunna få C++ att slå JavaScript för samma problem? Bifogar båda kodbaserna här under:

C++ ////////////////////////////////

#include <iostream> #include <ctime> using namespace std; long divisorSum(long n); bool isPerfect(long n); void findPerfects(int stop); int main() { findPerfects(40000); return 0; } long divisorSum(long n) { long total = 0; for (long divisor = 1; divisor < n; divisor++) { if (n % divisor == 0) { total += divisor; } } return total; } bool isPerfect(long n) { return (n != 0) && (n == divisorSum(n)); } void findPerfects(int stop) { clock_t start, end; start = clock(); for (long num = 1; num < stop; num++) { if (isPerfect(num)) { cout << "Found perfect number: " << num << endl; } } end = clock(); printf("Time Cost: %lums\n", (end - start) * 1000 / CLOCKS_PER_SEC); }

JS ///// ///// ///// /////

const { PerformanceObserver, performance } = require("perf_hooks"); function divisorSum(n) { let total = 0; for (let divisor = 1; divisor < n; divisor++) { if (n % divisor == 0) { total += divisor; } } return total; } function isPerfect(n) { return n !== 0 && n == divisorSum(n); } function findPerfects(stop) { var t0 = performance.now(); for (let num = 1; num < stop; num++) { if (isPerfect(num)) { console.log(`Found perfect Number: ${num}`); } } var t1 = performance.now(); console.log("Call to doSomething took " + (t1 - t0) + " ms."); } findPerfects(40000);

Trädvy Permalänk
Medlem
Registrerad
Apr 2002
Skrivet av magnusv:

Hej

Jag sitter och leker lite med C++ vs JavaScript / NodeJS. Gjorde ett litet test där jag tänkte försöka jämföra prestanda.
Skrev ett program i C++ för att räkna fram "perfekta tal" "brute force" https://sv.wikipedia.org/wiki/Perfekt_tal. Skrev sedan motsvarande i JavaScript med samma algoritm. Testar med ex 40 000 tal, tiden det tar för C++ att räkna sig igenom detta är 5600ms. Med JavaScript gör jag samma beräkning på ca 2100ms.
Har kört "build release" på C++ i både Xcode och QT creator, men med i stort sett samma resultat. Borde det inte vara tvärtom resultatmässigt?

Någon som kan ge en vettig förklaring till detta? Antar att JavaScript optimerar på något sätt som ger denna skillnad. Har det någon med hanteringen av long int i C++ att göra? Hur skulle jag kunna få C++ att slå JavaScript för samma problem? Bifogar båda kodbaserna här under:

C++ ////////////////////////////////

#include <iostream>
#include <ctime>
using namespace std;

long divisorSum(long n);
bool isPerfect(long n);
void findPerfects(int stop);

int main() {
findPerfects(40000);
return 0;
}

long divisorSum(long n)
{
long total = 0;

for (long divisor = 1; divisor < n; divisor++) {
if (n % divisor == 0) {
total += divisor;
}
}
return total;
}

bool isPerfect(long n)
{
return (n != 0) && (n == divisorSum(n));
}

void findPerfects(int stop)
{
clock_t start, end;
start = clock();
for (long num = 1; num < stop; num++) {
if (isPerfect(num)) {
cout << "Found perfect number: " << num << endl;
}
}
end = clock();
printf("Time Cost: %lums\n", (end - start) * 1000 / CLOCKS_PER_SEC);
}

JS ///// ///// ///// /////

const { PerformanceObserver, performance } = require("perf_hooks");

function divisorSum(n) {
let total = 0;

for (let divisor = 1; divisor < n; divisor++) {
if (n % divisor == 0) {
total += divisor;
}
}
return total;
}

function isPerfect(n) {
return n !== 0 && n == divisorSum(n);
}

function findPerfects(stop) {
var t0 = performance.now();

for (let num = 1; num < stop; num++) {
if (isPerfect(num)) {
console.log(`Found perfect Number: ${num}`);
}
}
var t1 = performance.now();
console.log("Call to doSomething took " + (t1 - t0) + " ms.");
}

findPerfects(40000);

Ja, det känns väl rent principiellt lite bakvänt att du får ett bättre resultat med Javascript än C++...
Men jag skulle ju misstänka att det mest handlar om hur koden är skriven, och att Javascripttolken bakom kulisserna "genomskådar" vad själva målet är på ett bättre sätt än C++-kompilatorn gjort (eller kanske kan göra, utifrån de regler som måste följas) och lyckas generera bättre optimerad maskinkod.

Det krävs väl dock att man tar sig tid för djupare analys av själva koden, reflekterar över hur saker är definierade i de båda språken och vad för maskinkod som faktiskt genererats.

AMD Ryzen7 3800X || Gigabyte X570 Ultra || Evga GTX 1080Ti || Crucial Ballistix Sport 3200 64GB || Samsung 950 Pro 512GB || Samsung 960 Pro 1024GB || XB270HU 1440p IPS G-Sync

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Aug 2005

Javascript klarar inte superstora int, kan vara att det blir "fusk"?

Intel 6700K | 2x Asus 980 Ti Strix SLI | Asus Maximus Hero VIII | Phanteks Enthoo Primo | Corsair HX 1000w | Eyefinity 3x Dell u2312hm
Samsung Evo 850 500GB | 2x Intel 320 240GB SSD | 3 x Mekanisk HDD

Trädvy Permalänk
Medlem
Registrerad
Okt 2016

C++ i x86 debug Visual Studio
Time Cost: 1763ms

På tok för liten arbetsmängd, samt man ska aldrig ha utskrifter inom tidsmätningen då det tar enorm tid (dock knappast relevant med 3 utskrifter).

Återkom med föreslagna förbättringar samt vad har du för CPU?

Stax 353xbk | Stax L300Le + L700 Arc + Custom Pads
SMSL AD18 | Kef Q300

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Jun 2007

Med GCC 9.3 (kompilerat med -O2) och Node.js 13.13 så är både C++ och Javascript lika snabba för mig på ungefär 2700ms med en 3900X. Och det är väl inte så underligt, det är ju väldigt enkelt kod som Node.js troligtvis JIT:ar till liknande maskinkod som C++.

En enkel optimering är att ändra villkoret i for-loopen till divisor <= (n / 2), vilket halverar tiden det tar. Det finns ju ingen mening med att kontrollera tal större än n / 2, eftersom de omöjligt kan vara jämnt delbara med n. Men det gäller ju även för Javascript förstås.

Trädvy Permalänk
Medlem
Registrerad
Apr 2002
Skrivet av Ernesto:

Javascript klarar inte superstora int, kan vara att det blir "fusk"?

Javascript har väl inte int öht, enbart "number" som i praktiken är double.
Att ändra C++-koden till double lär ju dock knappast göra saken bättre (int skulle väl däremot kunna hjälpa så länge man håller sig till de här små talen).

AMD Ryzen7 3800X || Gigabyte X570 Ultra || Evga GTX 1080Ti || Crucial Ballistix Sport 3200 64GB || Samsung 950 Pro 512GB || Samsung 960 Pro 1024GB || XB270HU 1440p IPS G-Sync

Trädvy Permalänk
Medlem
Registrerad
Apr 2002
Skrivet av perost:

Med GCC 9.3 (kompilerat med -O2) och Node.js 13.13 så är både C++ och Javascript lika snabba för mig på ungefär 2700ms med en 3900X. Och det är väl inte så underligt, det är ju väldigt enkelt kod som Node.js troligtvis JIT:ar till liknande maskinkod som C++.

En enkel optimering är att ändra villkoret i for-loopen till divisor <= (n / 2), vilket halverar tiden det tar. Det finns ju ingen mening med att kontrollera tal större än n / 2, eftersom de omöjligt kan vara jämnt delbara med n. Men det gäller ju även för Javascript förstås.

Provkörde på en gammal burk med en i7-5557U och fick följande (som väl är typ i linje med vad TS observerade):

g++ 10.1.1 (-O2):
Time Cost: 6361ms

clang++ 10.0.0 (-O2):
Time Cost: 5836ms

Node v12.16.3:
Call to doSomething took 3409.502158999443 ms.

AMD Ryzen7 3800X || Gigabyte X570 Ultra || Evga GTX 1080Ti || Crucial Ballistix Sport 3200 64GB || Samsung 950 Pro 512GB || Samsung 960 Pro 1024GB || XB270HU 1440p IPS G-Sync

Trädvy Permalänk
Medlem
Plats
Karlskrona
Registrerad
Aug 2009

Bootstrap tar större procentuell del av tiden om teststorleken är liten.
Istället för 40.000 tal, kör 1.000.000 tal tex.

Sedan vet jag inte vad du kör för system. Om du använder ett Linux-system som uppfyller POSIX så returnerar clock() antalet ticks som konsumerats av programmet och skalas med CLOCKS_PER_SEC, vilket är 1.000.000 (http://www.cplusplus.com/reference/ctime/clock/).

Det betyder att du får mikrosekunder i C och millisekunder för JavaScript (https://developer.mozilla.org/en-US/docs/Web/API/Performance/...).

Så för C++, om jag inte tänker fel, bör du ta

#include <time.h> clock_t start, end; double cpu_time_used; start = clock(); /* WORK */ end = clock(); cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

Om du sedan vill ms istället för sec så gångar du cpu_time_used med 1000.

Gigabyte Aorus Master | 32gb DDR4 3466MHZ CL14 | Ryzen 3950X | 1080Ti
Asus Z97 Pro Gamer | 32gb ram DDR3 2400MHz | i7 4790k | 2 x R9 390 - Barnen fått ta över
Asrock P67 Extreme4 rev3 | 16gb DDR3 2400MHz | i7 2600K | R9 290 - Barnen fått ta över
En massa bärbara, servrar, RPi's och andra boxar

Trädvy Permalänk
Medlem
Registrerad
Apr 2002
Skrivet av evil penguin:

Javascript har väl inte int öht, enbart "number" som i praktiken är double.
Att ändra C++-koden till double lär ju dock knappast göra saken bättre (int skulle väl däremot kunna hjälpa så länge man håller sig till de här små talen).

Skrivet av evil penguin:

Provkörde på en gammal burk med en i7-5557U och fick följande (som väl är typ i linje med vad TS observerade):

g++ 10.1.1 (-O2):
Time Cost: 6361ms

clang++ 10.0.0 (-O2):
Time Cost: 5836ms

Node v12.16.3:
Call to doSomething took 3409.502158999443 ms.

Tydligen så håller moderna javascript-tolkar (som v8) koll på om värdet som finns i ett "number" är en int som en ren prestandaoptimering, även om själva språket bara definierar att ett number ska fungera som double. Se t.ex. https://www.html5rocks.com/en/tutorials/speed/v8/#toc-topic-n...

Så följande är förmodligen relevant:

g++ 10.1.1 (-O2) med kodändring "int istället för long":
Found perfect number: 6
Found perfect number: 28
Found perfect number: 496
Found perfect number: 8128
Time Cost: 1892ms

clang++ 10.0.0 (-O2) med kodändring "int istället för long":
Found perfect number: 6
Found perfect number: 28
Found perfect number: 496
Found perfect number: 8128
Time Cost: 2722ms

AMD Ryzen7 3800X || Gigabyte X570 Ultra || Evga GTX 1080Ti || Crucial Ballistix Sport 3200 64GB || Samsung 950 Pro 512GB || Samsung 960 Pro 1024GB || XB270HU 1440p IPS G-Sync

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Jun 2007

@evil penguin: Testade du även med long? Jag får precis samma resultat med både int och long (i Linux, så int = 32 bit, long = 64 bit).

Trädvy Permalänk
Medlem
Registrerad
Apr 2002
Skrivet av perost:

@evil penguin: Testade du även med long? Jag får precis samma resultat med både int och long (i Linux, så int = 32 bit, long = 64 bit).

Ja, se det citerade inlägget (eller bara tidigare i tråden).

AMD Ryzen7 3800X || Gigabyte X570 Ultra || Evga GTX 1080Ti || Crucial Ballistix Sport 3200 64GB || Samsung 950 Pro 512GB || Samsung 960 Pro 1024GB || XB270HU 1440p IPS G-Sync

Trädvy Permalänk
Entusiast
Testpilot
Plats
Göteborg
Registrerad
Aug 2011

@magnusv: Använd [code] när du klistrar in kod, så blir den läsbar. Exempel:

[code]
#include <iostream>
[/code]

Skrivet med hjälp av Better SweClockers

Trädvy Permalänk
Medlem
Registrerad
Apr 2002

Utifrån mina egna observationer tidigare i tråden så känns det som att det passar ihop och förmodligen kan förklara resultatet.

Dvs:

Node håller koll på att det i praktiken är relativt små heltal du räknar med och genererar maskinkod som räknar med 32-bit heltal. (Bör gå att validera)
Din C++-kod använder explicit 64-bit heltal.

(dvs, det är isf inte samma beräkningar som utförs när de två programmen körs)

Sedan ger det då även intryck av att det beroende på hårdvaran antingen spelar roll prestandamässigt eller ej (se perosts resultat) om man räknar med 32-bit heltal eller 64-bit heltal.

Om detta är grejen så bör det innebära att du om du börjar räkna med större tal kommer att få en brytpunkt där Node behöver byta strategi och generera annan kod (gissar att det då faktiskt blir double den börjar använda?) och rimligen då blir långsammare.

AMD Ryzen7 3800X || Gigabyte X570 Ultra || Evga GTX 1080Ti || Crucial Ballistix Sport 3200 64GB || Samsung 950 Pro 512GB || Samsung 960 Pro 1024GB || XB270HU 1440p IPS G-Sync

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

Finns lite småsaker man kan fixa, som t.ex. att köra med unsigned int i C++ versionen, division för det är lite snabbare.

Om man vill kan man väldigt enkelt använda alla CPU-trådar i C++

#include <chrono> #include <cstdio> #include <string> using namespace std; typedef unsigned long num_t; num_t divisorSum(num_t n); bool isPerfect(num_t n); void findPerfects(int stop); int main(int argc, char *argv[]) { num_t limit = 40000; if (argc > 1) { limit = stoi(argv[1]); } findPerfects(limit); } num_t divisorSum(num_t n) { num_t total = 0; for (num_t divisor = n / 2 ; divisor > 0; divisor--) { if (n % divisor == 0) { total += divisor; } } return total; } bool isPerfect(num_t n) { return n == divisorSum(n); } void findPerfects(int stop) { auto start = chrono::system_clock::now(); #pragma omp parallel for schedule(dynamic) for (num_t num = 1; num < stop; num++) { if (isPerfect(num)) { #pragma omp serial printf("Found perfect number: %ld\n", num); } } chrono::duration<double> elapsed = chrono::system_clock::now() - start; printf("Time Cost: %.2fms\n", elapsed.count()); }

För att köra på en CPU-tråd, skicka in "vanliga" argument till g++/clang (i det läget betyder #pragma omp ingenting)

För att köra med alla trådar, skicka med argumentet -fopenmp.

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Jun 2018

Andra "trick" man kan köra är att "inline"-deklarera funktioner i C/C++ och att "register"-deklarera variabler.

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

Kunde inte låta bli att testa en oneAPI variant (Intels kommande API för SIMD/GPU/FPGA programmering). Detta såg ut att passa GPUer som hand i handsken. Mycket riktigt, en Iris Graphics 655 (en Bean Canyon NUC med i7-8559U) betar av de första 400,000 (så tio gånger fler än vad som testas ovan) på 2,4 s!!!

Grejen med oneAPI är att man skriver "vanlig" C++20!

#include <iostream> #include <string> #include "CL/sycl.hpp" namespace sycl = cl::sycl; typedef unsigned num_t; int main(int argc, char * argv[]) { size_t limit = 40000; if (argc > 1) { limit = std::stoi(argv[1]); } sycl::buffer<bool, 1> pnBuf(limit); try { // Change to sycl::cpu_selector{} to run on SSE/AVX sycl::queue q(sycl::gpu_selector{}); // Submit work to GPU/GPU q.submit([&](sycl::handler& h) { auto pn = pnBuf.get_access<sycl::access::mode::discard_write>(h); // Run on number or GPU/SIMD-lane h.parallel_for<class perfect_number>( sycl::range<1>{limit}, [=] (sycl::id<1> idx) { num_t n = idx.get(0) + 1; num_t divSum = 0; for (num_t divisor = n / 2 ; divisor > 0; divisor--) { if (n % divisor == 0) { divSum += divisor; } } pn[idx] = n == divSum; } ); }); } catch (sycl::exception & e) { std::cout << e.what() << std::endl; return 1; } // Get the result from GPU/SIMD auto r = pnBuf.get_range(); auto pn = pnBuf.get_access<sycl::access::mode::read>(); for (auto n = 0; n < r.get(0); n++) { if (pn[n]) { std::cout << "Found perfect number " << n + 1 << '\n'; } } }

Om ni har Skylake eller Ice Lake med iGPU går ovan att köra. Beta-version av SDK finns att ladda ner, jag kör den från Dockerhub.

Sättet man måste tänka på GPU är: lös uppgiften för ett fall, sedan sprider man ut alla tänkbara fall över GPU-kärnorna och de jobbar med ett fall var

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

Lite pre-lunch kodande. Ursäkta för att jag inte skriver JS, men dynamiskt typade språk och jag är inkompatibla
Som tur är finns Typescript.

Går ju att använda alla kärnor även med NodeJS via cluster modulen.

import { performance } from 'perf_hooks'; import * as process from 'process'; import * as cluster from 'cluster'; import * as os from 'os'; function divisorSum(n: number): number { let total = 0; for (let divisor = n / 2; divisor > 0; divisor--) { if (n % divisor == 0) { total += divisor; } } return total; } function isPerfect(n: number): boolean { return n == divisorSum(n); } function findPerfects(from: number, to: number) { for (let num = from; num <= to; num++) { if (isPerfect(num)) { console.log(`Found perfect Number: ${num}`); } } } let limit = Number(process.argv[process.argv.length - 1]); if (!limit) { limit = 40000; } const nWorkers = os.cpus().length; if (cluster.isMaster) { const t0 = performance.now(); let activeWorkers = 0; for (let cpu = 0; cpu < nWorkers; cpu++) { cluster.fork(); activeWorkers++; } cluster.on('exit', () => { if (--activeWorkers == 0) { const t1 = performance.now(); console.log(`Took ${t1 - t0} ms.`); process.exit(0); } }); } else { // Worker const sliceLen = limit / nWorkers; const from = (cluster.worker.id - 1) * sliceLen + 1; const to = (cluster.worker.id == nWorkers) ? limit : cluster.worker.id * sliceLen; findPerfects(from ,to); process.exit(0); }

Har kört alla tester med en gräns på 100 000 tal, blir lite allt för kort tid för att mäta annars när man använder alla kärnor.

Interessant observation att även på min dator är NodeJS marginellt snabbare om man använder en enda tråd: 15,2 s. C++ versionen tar 16,4 s (g++ 9.3 med -O2) om man använder long. Kör man ned unsigned long blir det exakt samma för C++ versionen som för NodeJS: 15,2 s.

Att använda flera CPU-trådar har sina begränsningar i JS/TS... Där drar C++ ifrån en hel del. C++ med OpenMP (det jag postade ovan) klarar av det hela på 2,26 s på min 4C/8T bärbara medan NodeJS klarar av det på 4,83 s.
Båda blir totalt massakerade av oneAPI versionen körandes på Iris Graphics 655, den klarar av samma sak på 0,95s.

GPU-versionen har ändå en hel del overhead på små problem. Min 3900X kör C++ versionen på 0,90s. Ökar man till gränsen till 200 000 tar den då 3,10s på Iris Graphics 655 och 3,59 på 3900X.

Vad detta visar är ju det som redan diskuteras i tråden: enkelt exempel där Googles V8 JS motor visar just hur snabbt JS blir med rätt optimeringar, finns inget en C++ kompilator kan göra bättre i detta läget. Vad främst oneAPI varianten visar är att om man beskriver problemet på ett lite annorlunda sätt, men ändå inom C++ språkets gränser, går det att få en helt annan prestanda. Tänk vad prestandan skulle vara på ett 2080Ti, jag kör ju med en Intel iGPU!

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Medlem
Plats
NördCentrum
Registrerad
Jun 2011

Bidrar med en datapunkt även jag. Översatte programmet till Futhark och jämförde med Yoshmans OpenMP variant (med -fopenmp flaggan).

lib.fut:

let divisor_sum n = reduce_comm (+) 0i32 <| map (\divisor -> if n % divisor == 0 then divisor else 0) (1...n/2) let is_perfect n = n > 1 && n == divisor_sum n let find_perfects stop = filter is_perfect (1..<stop) let main (limit: i32): []i32 = find_perfects limit

Makefile:

Klicka för mer information

NOWARN_CFLAGS=-std=c11 -O2 CFLAGS=$(NOWARN_CFLAGS) -Wall -Wextra -Wconversion -pedantic INCLUDE=-I"${OCL_ROOT}\include" LDFLAGS=-L"${OCL_ROOT}\lib\x86_64" -lOpenCL .PHONY: all all: lib.o lib.h gcc main.c lib.o -o main.exe $(CFLAGS) $(INCLUDE) $(LDFLAGS) lib.o: lib.c lib.h gcc -o lib.o -c lib.c $(NOWARN_CFLAGS) lib.h: lib.c lib.c: lib.fut futhark opencl --library lib.fut

Visa mer

main.c:

Klicka för mer information

#include <inttypes.h> #include <stdio.h> #include <time.h> #include "lib.h" int main() { clock_t start = clock(); // Initialize Futhark and OpenCL struct futhark_context_config* cfg = futhark_context_config_new(); struct futhark_context *ctx = futhark_context_new(cfg); // Run the program const int32_t limit = 40000; struct futhark_i32_1d* out; futhark_entry_main(ctx, &out, limit); // Extract output size_t length = (size_t)*futhark_shape_i32_1d(ctx, out); int32_t* perfects = (int32_t*)malloc(length * sizeof(int32_t)); futhark_values_i32_1d(ctx, out, perfects); for (size_t i = 0; i < length; i++) { printf("%d\n", perfects[i]); } clock_t end = clock(); printf("Time Cost: %lums\n", (end - start) * 1000 / CLOCKS_PER_SEC); return 0; }

Visa mer

Utvärderingsmiljö: OS: Windows 10, CPU: AMD Ryzen 5 3600, GPU: AMD RX 580.

Med limit = 40000 (fyrtiotusen) presterade Futhark inte särskilt imponerande.

Futhark: 419ms
OpenMP C++: 252ms

Jag gissade dock på att mycket av tiden för Futharkprogrammer gick åt på one-time kostnaden att ladda upp programmet på GPUn och kompilera den genererade OpenCL koden. Jag prövade därför igen, fast med en högre limit.

Med limit = 400000 (fyrahundratusen) drog Futhark iväg!

Futhark: 1340ms
OpenMP C++: 25997ms (26s)

Nu spelar setup-kostnaden inte lika stor roll, och Futhark får chansen att visa vad det går för. Futhark-kompilatorn är väldigt smart när det kommer till automatisk parallellisering, och använder smarta tekniker som bl.a. incremental flattening för att "platta ut" nästlad parallellism till en form som passar GPUer.

Gibb: Win10 - Ryzen 5 3600 - RX 580 - 16G 3000MHz DDR4
Server: Arch - 2 * Xeon X5570 - R9 280X - 32G DDR3 ECC

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011
Skrivet av Bryal:

Bidrar med en datapunkt även jag. Översatte programmet till Futhark och jämförde med Yoshmans OpenMP variant (med -fopenmp flaggan).

lib.fut:

let divisor_sum n = reduce_comm (+) 0i32 <| map (\divisor -> if n % divisor == 0 then divisor else 0) (1...n/2) let is_perfect n = n > 1 && n == divisor_sum n let find_perfects stop = filter is_perfect (1..<stop) let main (limit: i32): []i32 = find_perfects limit

Makefile:

Klicka för mer information

NOWARN_CFLAGS=-std=c11 -O2 CFLAGS=$(NOWARN_CFLAGS) -Wall -Wextra -Wconversion -pedantic INCLUDE=-I"${OCL_ROOT}\include" LDFLAGS=-L"${OCL_ROOT}\lib\x86_64" -lOpenCL .PHONY: all all: lib.o lib.h gcc main.c lib.o -o main.exe $(CFLAGS) $(INCLUDE) $(LDFLAGS) lib.o: lib.c lib.h gcc -o lib.o -c lib.c $(NOWARN_CFLAGS) lib.h: lib.c lib.c: lib.fut futhark opencl --library lib.fut

Visa mer

main.c:

Klicka för mer information

#include <inttypes.h> #include <stdio.h> #include <time.h> #include "lib.h" int main() { clock_t start = clock(); // Initialize Futhark and OpenCL struct futhark_context_config* cfg = futhark_context_config_new(); struct futhark_context *ctx = futhark_context_new(cfg); // Run the program const int32_t limit = 40000; struct futhark_i32_1d* out; futhark_entry_main(ctx, &out, limit); // Extract output size_t length = (size_t)*futhark_shape_i32_1d(ctx, out); int32_t* perfects = (int32_t*)malloc(length * sizeof(int32_t)); futhark_values_i32_1d(ctx, out, perfects); for (size_t i = 0; i < length; i++) { printf("%d\n", perfects[i]); } clock_t end = clock(); printf("Time Cost: %lums\n", (end - start) * 1000 / CLOCKS_PER_SEC); return 0; }

Visa mer

Utvärderingsmiljö: OS: Windows 10, CPU: AMD Ryzen 5 3600, GPU: AMD RX 580.

Med limit = 40000 (fyrtiotusen) presterade Futhark inte särskilt imponerande.

Futhark: 419ms
OpenMP C++: 252ms

Jag gissade dock på att mycket av tiden för Futharkprogrammer gick åt på one-time kostnaden att ladda upp programmet på GPUn och kompilera den genererade OpenCL koden. Jag prövade därför igen, fast med en högre limit.

Med limit = 400000 (fyrahundratusen) drog Futhark iväg!

Futhark: 1340ms
OpenMP C++: 25997ms (26s)

Nu spelar setup-kostnaden inte lika stor roll, och Futhark får chansen att visa vad det går för. Futhark-kompilatorn är väldigt smart när det kommer till automatisk parallellisering, och använder smarta tekniker som bl.a. incremental flattening för att "platta ut" nästlad parallellism till en form som passar GPUer.

Ser coolt ut! Det börjar komma ut allt mer verktyg för GPUer, hade inte hört talas om Futhark innan.

Slog mig att jag gjorde ett misstag i oneAPI versionen: som den är skriven nu är det som att skapa en CPU-tråd för varje enskilt tal... Regerade inte på prestanda då den trots allt var rätt snabb givet att det handlar om en iGPU, men tyckte det var lite större glapp mot RX 580 än jag skulle ha gissat. Intels GPUer slår rejält över sin viktklass när det gäller GPGPU!

Skrev om logiken lite så att man nu delar upp problemet till att aldrig innehålla fler trådar än HW kan göra något vettigt med, det handlar ändå om tiotusentals trådar. Går att fråga GPUn om antal beräkningsenheter och maximalt antal trådar per enhet som kan köra samtidigt.

Sagt och gjort, nu går fallet med 400 000 på 2,59s. Det är nästan lite bättre än vad gissade en Iris Graphics 655 skulle mäkta med. Overhead finns, men en fördel med iGPUer är att den är långt mindre än för dGPU. Kör man 40 000 fallet tar det 0,24s på GPU.

Klicka för mer information

#include <algorithm> #include <iostream> #include <string> #include <vector> #include <optional> #include "CL/sycl.hpp" namespace sycl = cl::sycl; typedef unsigned num_t; typedef struct { size_t from; size_t to; } slice_t; typedef std::vector<slice_t> slices_t; static slices_t make_slices(size_t limit, sycl::device dev) { size_t MAX_CNT = dev.get_info<sycl::info::device::max_compute_units>() * dev.get_info<sycl::info::device::max_work_group_size>(); slices_t s; for (size_t from = 1; from < limit; from += MAX_CNT) { size_t to = from + MAX_CNT; if (to > limit) { to = limit; } s.push_back(slice_t{from, to}); } return s; } std::optional<slice_t> next_slice(slices_t &s) { if (s.empty()) { return std::nullopt; } auto slice = s.back(); s.pop_back(); return std::optional<slice_t>(slice); } std::vector<num_t> findPerfects(size_t limit) { sycl::queue q(sycl::gpu_selector{}); slices_t slices = make_slices(limit, q.get_device()); std::vector<num_t> perfect_numbers; while (auto slice = next_slice(slices)) { size_t from = slice->from; size_t cnt = slice->to - from; sycl::buffer<bool, 1> pnBuf(cnt); // Submit work to GPU/CPU q.submit([&](sycl::handler& h) { auto pn = pnBuf.get_access<sycl::access::mode::discard_write>(h); // Run on number or GPU/SIMD-lane h.parallel_for<class perfect_number>( sycl::range<1>{cnt}, [=] (sycl::id<1> idx) { num_t n = idx.get(0) + from; num_t divSum = 0; for (num_t divisor = n / 2 ; divisor > 0; divisor--) { if (n % divisor == 0) { divSum += divisor; } } pn[idx] = n == divSum; } ); }); auto r = pnBuf.get_range(); auto pn = pnBuf.get_access<sycl::access::mode::read>(); for (auto n = 0; n < r.get(0); n++) { if (pn[n]) { perfect_numbers.push_back(n + from); } } } std::sort(perfect_numbers.begin(), perfect_numbers.end()); return perfect_numbers; } int main(int argc, char * argv[]) { size_t limit = 40000; if (argc > 1) { limit = std::stoi(argv[1]); } for (auto n: findPerfects(limit)) { std::cout << "Found perfect number " << n << '\n'; } }

Visa mer

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

I tråden diskuteras att NodeJS och C++ är lika snabbt för de gör exakt samma sak. Det är också så att man kan köra detta långt snabbare på GPUer då de egentligen får en lite annan beskrivning av problemet.

Slog mig då: hur kommer Rust hantera detta fall? Grejen med Rust är att semantiken i språket gör att kompilatorn oftare kan utnyttja SIMD (SSE/AVX) jämfört med i princip alla andra språk, inklusive C++.

Sagt och gjort, en Rust version. Av någon anledning är denna dubbelt så snabb (enkeltrådfallet) jämfört med C++/NodeJS på min NUC med i7-8559U men den är lika snabb som C++/NodeJS på min 3900X. Är inte riktigt med på varför...

Klicka för mer information

use std::env; use rayon::prelude::*; type Number = u32; fn divisor_sum(n: Number) -> Number { (1..=n/2) .filter(|divisor| n % divisor == 0) .sum() } fn is_perfect(n: Number) -> bool { n == divisor_sum(n) } fn find_perfects(limit: Number) -> Vec<Number> { (1..=limit) .into_par_iter() .filter(|&n| is_perfect(n)) .collect() } fn main() { let limit = env::args() .nth(1) .unwrap_or("40000".to_owned()) .parse() .unwrap(); find_perfects(limit) .iter() .for_each(|n| println!("Found perfect number: {}", n)) }

Visa mer

Ovan är en version som automatiskt använder alla CPU-trådar. Enda man måste göra för att få den enkeltrådade är att kommentera bort denna rad

fn find_perfects(limit: Number) -> Vec<Number> { (1..=limit) // .into_par_iter() Kommentera bara bort detta så är det enkeltrådat! .filter(|&n| is_perfect(n)) .collect() }

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Medlem
Plats
Uppsala
Registrerad
Okt 2013

Mycket imponerande av js! oneAPI ska jag kolla mer på!

Några små ändringar bara så är det i C, utan++. Körtiden reduceras en gnutta, även binärstorleken, 16904 vs 17624 byte.

$ gcc -O3 csvjs.c -o c ; ./c Found perfect number: 6 Found perfect number: 28 Found perfect number: 496 Found perfect number: 8128 Time Cost: 6070ms $ g++ -O3 csvjs.cpp -o cpp ; ./cpp Found perfect number: 6 Found perfect number: 28 Found perfect number: 496 Found perfect number: 8128 Time Cost: 6261ms

#define _XOPEN_SOURCE 700 #include <stdio.h> #include <time.h> #include <stdbool.h> long divisorSum(long n); bool isPerfect(long n); void findPerfects(int stop); int main() { findPerfects(40000); return 0; } long divisorSum(long n) { long total = 0; for (long divisor = 1; divisor < n; divisor++) { if (n % divisor == 0) { total += divisor; } } return total; } bool isPerfect(long n) { return (n != 0) && (n == divisorSum(n)); } void findPerfects(int stop) { struct timespec tstart, tend; clock_gettime(CLOCK_REALTIME, &tstart); for (long num = 1; num < stop; num++) { if (isPerfect(num)) { printf("Found perfect number: %lu\n", num); } } clock_gettime(CLOCK_REALTIME, &tend); double elapsed = (tend.tv_sec - tstart.tv_sec); elapsed += (tend.tv_nsec - tstart.tv_nsec) / 1000000000.0; printf("Time Cost: %.0fms\n", elapsed*1000); }