Programozási nyelvek futásteljesítménye - aritmetikai feladathoz

 ( hg2ecz | 2019. április 22., hétfő - 9:56 )

Kíváncsiságból megnéztem néhány programozási nyelvet, hogy alap aritmetikai célra milyen futásteljesítményt nyújtanak Linuxon (Ubuntu 19.04). Csak olyan nyelveket próbáltam ki, amelyek univerzálisak, nem kizárólag aritmetikai problémák megoldására alkalmasak, továbbá nem igényelnek erőteljesebb futtatókörnyezet telepítést, esetleg már alapból benne vannak a Linux telepítésekben

Az algoritmus igen egyszerű (toval parancssorból átadott érték):

for i in 0..toval {
   for j in 0..toval {
      sumval += i+(j^1);
   }
}

Alább látható néhány futásidő másodpercben i5-3337u procis laptopon, 20000-es értékkel.
A kisebb futásidő a gyorsabb. Mellette az shell for ciklusból történő átlagos indulási idő:

bash		~2800s	2.0ms
gawk 		55.4s	2.0ms
perl  		44.1s	3.0ms
php7.2		10.8s	13.3ms
nodejs 		1.41s	523ms - nagyon lassan indul
luajit 		0.90s	1.63ms
pypy3		0.85s	58.6ms - python3 esetén 17ms az indulás, ellenben nagyon lassú a futás
python3+numba	0.67s	523ms - lassú a start, de nagyon gyors utána a futás

Binárisok:
gccgo -O2   	0.36s	18.3ms - binárishoz képest lassan indul
gdc  -O2  	0.34s	4.4ms
gcc -O2    	0.34s	0.85ms
gcc -Ofast ...	0.14s	0.85ms
rust 1.34	0.14s	1.28ms

update: lokális változókkal sokkal gyorsabb a PyPy3 és a gAWK, továbbá a Perl is picit gyorsabb. Javítottam a táblázatban.

A tesztek itt elérhetőek

$ ./1_build.sh            # lefordít mindent, amire felraktad a fordítót
$ ./2_test_loop.sh 20000  # toval = 20000 és futásideje
$ ./3_test_start.sh 1000  # 1000 darab zéró iterációs start ideje

Hozzászólás megjelenítési lehetőségek

A választott hozzászólás megjelenítési mód a „Beállítás” gombbal rögzíthető.

Ebben benne van a futtatókörnyezet indulási ideje is?

igen, time paranccsal mértem.

$ time ./forloop_add_test.lua 10000
Luajit: 999900000000

real 0m0,231s
user 0m0,230s
sys 0m0,001s

$ time ./forloop_add_test.lua 20000
Luajit: 7999600000000

real 0m0,902s
user 0m0,894s
sys 0m0,008s

Egyébként jó ötletet adtál, megnéztem azt is, hogy a szkript illetve bináris elindítása mennyire erőforrásigényes. A táblázatba beírtam.

Köszi! Sejtettem, hogy a nodejs-nél ebből adódik a jelentős eltérés a luajit-tel szemben, ha kivonod a warmup time-ot a futásidőkből akkor 11ms a különbség a nodejs javára.

Mérd le a calc-ot is, kérlek! Debian, Ubuntu világában apcalc a csomag neve, ha jól emlékszem, tehát nem a LibreOffice-ról beszélek most. Nagyon szeretem ezt a komplex aritmetikát is tudó, interaktív, de scriptelhető nyelvet, eszközt.

http://www.isthe.com/chongo/tech/comp/calc/


tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

Kimaradt a bc.

+1

A j^1-et szerintem a binárisra fordítók simán ki fogják optimalizálni, nem? A Perl és PHP meg talán minden ismétlésre újra is parszolja a kifejezést. Ebből jó nagy eltérések adódnak.

Kiváncsi lennék a Java-ra is, de azt valóban nem egyszerű mérni ezek miatt:

* JVM indulás
* Interpretált futás
* Hostspot fordítás - a futás során egy ponton a JVM úgy fog dönteni, hogy lefordítja binárisra a program egy részét
* Garbage Collection - ha "szemetet" termel az ismétlődő programrész, akkor ez periodikusan fog okozni egy plusz terhelést, ami torzítja a mérést, ha az ismétlésszám kicsi a szemétgyűjtés periódusához képest

A JVM indulás és a Hotspot miatt arra lehet számítani, hogy hosszú távon az átlagos futásidő sokkal jobb, mint ami egy rövid ismétléssorozat méréséből kijön.

Szóval ez a mikrobenchmark mérés egészen összetett kérdés virtuális gépek esetén.

Erre való a JMH, ami pont megoldja ezeket a problémákat a mérés során.
https://openjdk.java.net/projects/code-tools/jmh/

+epszilon gc, s akkor szerintem a fenti pontok többsége ki is van pipálva ;)

Éppen ezért raktam be a (j^1)-et, hogy a parancssorból vett max értékkel együtt becsapjam a C és Rust fordítót. Ha kihagyom, akkor a C fordító tényleg fordításkor kiszámolja az eredményt. :)
Aki játszani akar a tesztkódokkal, ide felraktam.

python3 esetén 17ms az indulás, ellenben nagyon lassú a futás
Konkretan?

Alkalmazásfüggő. Nagyobb alkalmazásoknál általában 6-szoros tempóval szoktam tervezni Pypy esetén. Az ilyen jellegű feladatoknál viszont 60-szoros az eltérés. További teszteket látsz itt: https://speed.pypy.org/

Egy furcsaság numba jit + py3 esetében (a kód módosítása nélkül csak a @jit dekorátort rakva számítást végző function elé):

$ time ~/miniconda3/bin/python test.py 100000
999990000000000

real    0m1.486s
user    0m1.313s
sys     0m0.156s
$ gcc -Wall -O2 test.c -o test
$ time ./test 100000
C: 999990000000000

real    0m4.749s
user    0m4.719s
sys     0m0.016s

A warmup elég magas (kb 500ms) emiatt növeltem meg 100000-re a toval-t. (elvileg tud aot compile-t is, de azt nem próbáltam)

Használtam már a Numba-t intenzív számolásoknál, de jól el is feledkeztem róla. Ebben az esetben lassabb indulás mellett sokkal gyorsabb kódot produkál a Pypy3-nál. Sajnos úgy vettem észre annó, hogy bizonyos részeken nem ajánlott a @jit.

gcc viszont lassú kódot fordít nálad. Esetleg 32 bites oprendszered van? Ekkor például -march=native segíthet. Oka: a 32 bites gcc alapból i486 procin is elfutó kódot generál, ami számításoknál, jelfeldolgozó rutinoknál nagyon megérződik.

64bit, de Windows Linux subsystem. Nálad mennyi idő alatt fut le a C illetve a numba-s kód 100000-es paraméterrel?

numba 100.000: real 0m3,746s
gcc -O2 100.000: hehe, belefutottam ismét a C bugba, amit már beletoltam tavaly a gcc bugreportba. A gcc -O2 valamiért nem jobb, mint a gcc -O1, mert érzésem szerintem valamit elrontottak benne.

gcc -Ofast fordít megfelelően jól, a -O2 tényleg túl lassú.
Ellenpróba: clang esetén -O2 gyors kódot fordít.

Nekem 100.000 esetén továbbra is jelentősen gyorsabb a numba a gcc-nél:

pypy (WSH): 13s
go: 5.2s
gcc -Ofast (WSH): 4.7s
py3 + Numba (WSH): 1.5s (400ms warmup-ot is beleszámítva)

A Bash sosem lesz sebességkirály, de egy kis optimalizálással nálam 40%-al gyorsult a kód:

#!/usr/bin/env bash

SUM=0

for(( I=0; I=<$1; I++))
do
        for((J=0; J<$1; J++))
        do
                (( SUM+=I+(J^1) ))
        done
done

echo "Bash: $SUM"

Az eredeti pszeudokódban az I és J ciklusok pont ugyanolyanok, a tiedben nem.
(Én mondjuk az i=<$1 formát az életben nem láttam leírva.)

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Mea culpa, kicsit bénáztam a kód formázással és annak esett áldozatul a feltétel. Elsőre nem is értettem, hogy mire célzol mert a gépemen lévő scriptben minden jó volt, csak utána láttam hogy kicsit más van az oldalon.

Az eredeti kódban I<$1 és J<$1 van.

Köszi, ezt a += bash szintaktikát kerestem. Tényleg sokat gyorsult.

Vak vagyok, vagy tényleg nincs ott sehol az egyes nyelvek konkrét kódja? Simán lehet, hogy a megvalósításokat még ilyen egyszerű kód esetén is lehetne tuningolni. (Én anno csináltam tesztet arra, hogy pl. az i=i+1 jellegű műveletből melyik gyorsabb / lassabb a shell-ben, és már ott egetverő különbségek jöttek ki - arról nem is beszélve, hogy simán lehet eltérés bash/zsh/pdksh/ksh93/mksh/stb között is.)

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

git clone https://github.com/hg2ecz/ProgrammingLanguage-SimpleTest.git
cat ProgrammingLanguage-SimpleTest/forloop-add-test/forloop_add_test.sh
(es hasonloan a tobbi nyelvre)

--
When you tear out a man's tongue, you are not proving him a liar, you're only telling the world that you fear what he might say. -George R.R. Martin

OK, ezek között valóban nem nagyon látok javítási lehetőséget, bár mondjuk a natív python-ra valaki ránézhetne, hátha nem a for i range a leggyorsabb. Bár nyilván nem az viszi az időt :-)

De hogy konstruktív is legyek. Noha az életben nem használtam a locsemege által emlegetett (ap)calc-ot, és szerintem kissé hektikus a dokumentációja, ezt hoztam össze calc ügyben (mivel nem vagyok benne biztos, hogy mit hogyan szeret a nyelv, így betettem a sumval-nál egy - talán fölösleges - zárójelpárt):

$ cat teszt.cal
define main(toval) {
	local i, j, sumval=0;
	for (i = 0 ; i < toval ; i++ ) {
	   for ( j = 0 ; j < toval ; j++) {
	      sumval += ( i + ( j ^ 1 ) );
	   }
	}
	print "calc: ", sumval;
	}

main(eval(argv(1)));

$ calc -d -q -f teszt.cal -s -- 20000
calc:  7999600000000

És ím ugyanez bc-ben. Mivel a POSIX bc csak a kisbetűs és egykarakteres változó (és függvény-)neveket szereti, ezért így szerepel a kódban. Paraméter átadás nincs, rendes kilépés nincs (azért a quit működése eléggé abnormális - bár itt éppen jó.)

$ cat teszt.bc
s = 0
define m(t) {
        auto i, j
        for (i = 0 ; i < t ; i++ ) {
           for ( j = 0 ; j < t ; j++) {
              s += ( i + ( j ^ 1 ) )
           }
        }
print "bc: ", s
}

m(20000)
quit

$ bc teszt.bc
...

Mivel ez itt egy egészen más kategóriájú gép (és feltehetően másik OS), ezért valós time értékeket nem írok, mert teljesen értelmetlen lenne összehasonlítani az eredményeket. A calc is, a bc is lassú, mint az állat :-( , de a bc-t mg így is lelőttem akkor, amikor már több, mint kétszer annyi ideje futott, mint a calc. (Az igazsághoz hozzátartozik, hogy FreeBSD alatt a hagyományos felállás van, azaz a bc csak egy interpreter a dc-hez, és az érdemi munkát a dc végzi. A GNU-implementációban ha jól tudom a bc NEM dc-re fordít, hanem natívan számol.)

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Bár eredetileg általános programozási nyelvekben gondolkoztam, "calconly_"-ként beillesztettem ezeket a kódokat is. Köszi.

És akkor az RPN (reverse polish notation) kedvelőknek jöhet a dc is, esetleg a gforth. :)

#!/bin/sh
echo "$1s!0dds#s@[l@+l#1^+l#1+ds#l!>.]s.[0s#l.xl@1+ds@l!>,]ds,xp"|dc

Ezekről a nyitóba írsz majd futásidőket?


tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

Köszi, érdekes.
Megcsináltam R-re is, hadd lehessen összehasonlítani:

args <- commandArgs(trailingOnly=TRUE)
toval <- as.numeric(args[1])
sumval <- 0
for (i in 0:(toval-1)){
        for (j in 0:(toval-1)){
                sumval <- sumval + i + (j^1)
        }
}
print(sumval)

Így köll futtatni:

Rscript --vanilla forloop_add_test.R 20000

Eredmény:

$ time ./forloop_add_test-c-O2 20000
C: 7999600000000

real    0m0,217s
user    0m0,216s
sys     0m0,001s

$ time ./forloop_add_test-c-Ofast 20000
C: 7999600000000

real    0m0,048s
user    0m0,047s
sys     0m0,001s

$ time ./forloop_add_test.awk 20000
AWK:  7999600000000

real    0m32,556s
user    0m32,526s
sys     0m0,002s

$ time Rscript --vanilla forloop_add_test.R 20000
[1] 7.9996e+12

real    0m21,512s
user    0m21,265s
sys     0m0,068s

Csak kiegészítésképpen írtam egy ilyet is (igen, világos, hogy nem teljesen ekvivalens):

args <- commandArgs(trailingOnly=TRUE)
toval <- as.numeric(args[1])
mymtx <- matrix(1,nrow=toval,ncol=toval)
print(sum(mymtx))

Jellemző, hogy mennyivel másabb a futtatási idő:

$ time Rscript --vanilla forloop_add_test_speed.R 20000
[1] 4e+08

real    0m1,411s
user    0m0,667s
sys     0m0,733s

Azt hiszem, megvan a következő kódolási feladat az őszi R kurzusomhoz. Köszi még egyszer!

--
Csaba

Köszi, R-ben még úgysem írtam programot. Kis módosítással feldobtam ezt is, továbbá írtam gyorsan egy tesztet Octave és Julia nyelvekre is.

Én kíváncsi lennék a "gyári" go fordító hogy viszonyul a mezőnyhöz (főleg a gccgo-hoz).

A tegnap raneztem a go es a c viszonyara. Ha jol emlekszem akkor ilyen eredmenyek voltak

gcc -O2    	0.18s - 0.19s
gcc -Ofast      0.12s - 0.13s
go (gyari)      0.18s - 0.19s

Free Pascal verzió, tíz perc alatt:

{$MODE FPC}

function sumval(toval: sizeint): sizeint;
var
  i,j: sizeint;
begin
  sumval:=0;
  dec(toval);
  for i:=0 to toval do
    for j:=0 to toval do
      inc(sumval,i+(j xor 1));
end;

var
  toval: sizeint = 0;
  code: word = 0;

begin
  if paramcount>0 then
    val(paramstr(1),toval,code);

  if code<>0 then
    writeln('Nope.')
  else
    writeln(sumval(toval));
end.

macOS van kéznél, arra fordítom, FPC 3.0.4 stable, valami Mid-2015 Quad i7 laptop:

charlie @ chainmbp:~ $ fpc -Xs -XX -CX -O4 forloop_add_test.pas
Free Pascal Compiler version 3.0.4 [2018/09/30] for x86_64
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Darwin for x86_64
Compiling forloop_add_test.pas
Assembling (pipe) forloop_add_test.s
Linking forloop_add_test
26 lines compiled, 0.1 sec

charlie @ chainmbp:~ $ ls -la ./forloop_add_test
-rwxr-xr-x  1 charlie  staff  100944 Apr 26 13:25 ./forloop_add_test

charlie @ chainmbp:~ $ time ./forloop_add_test 20000
7999600000000

real	0m0.194s
user	0m0.189s
sys	0m0.002s

-=- Mire a programozó: "Na és szerintetek ki csinálta a káoszt?" -=-

Szerintem a j^1 az eredeti példákban nem xor, hanem hatványozás. Persze egymillió éve nem Pascaloztam, szóval az is lehet, hogy ilyen trükkösen híjják.

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Biztos h. xor (C szintaxisban), mivel ugyanazt az eredmenyt kapom...

-=- Mire a programozó: "Na és szerintetek ki csinálta a káoszt?" -=-

Köszi, ha nem írsz róla, akkor kimarad. Pedig valamikor a BME-n ezt is jól megtanították a Pascal-t is nekünk.

$ ./1_build.sh
$ ./2_test_loop.sh 20000

./forloop_add_test-pas (20000 * 20000) Pascal: 7999600000000

real 0m0,306s
user 0m0,306s
sys 0m0,000s

./forloop_add_test-rs (20000 * 20000) Rust: 7999600000000

real 0m0,133s
user 0m0,132s
sys 0m0,000s

Ize, most megneztem milyen tesztkodot hasznalsz, en nem veletlenul tettem am az egeszet egy fuggvenybe, mert Pascalban mashogy van a lokalis es a globalis valtozok volatilitasa(? van ilyen szo?), ergo ha nem stacken vannak a valtozok, akkor mindig ujratolti/eltarolja a globalis valtozokat (pl. a ciklusvaltozokat, meg a sum erteket magat is-t), es nem tartja regiszterben, emiatt meg joval lassabb az egesz, pluszban a globalis valtozok egy rakas rendszerben GOT tablan keresztul kerulnek eleresre, ami tobb utasitas, stb...

Szoval ja, a te verziod kb. mestersegesen van lassitva a worst case scenario szintre Pascal szempontbol. Csak mondom.

-=- Mire a programozó: "Na és szerintetek ki csinálta a káoszt?" -=-

$ time ./forloop_add_test 20000 # ez az általam egyszerűsített
Pascal: 7999600000000

real 0m0,306s
user 0m0,306s
sys 0m0,000s

$ time ./forloop_add_test-orig 20000 # ez a te eredeti verziód
7999600000000

real 0m0,307s
user 0m0,307s
sys 0m0,000s

Az idő ugyanannyi. Oka: i, j, toval, sumval proci regisztereiben allokálódik, nem kell neki se stack, se ram.

Ha az fpc -nek adsz egy -a kapcsolót, akkor tanulmányozhatod a .s assembly fájlt.
A j változó az rbx-ben implementálódik.
Az i változó pedig az rdi-ben.
A toval pedig rdx (külső ciklusé) és rcx (belső ciklusé) regiszterekben allokálódik.

Egy valamit lehet optimalizálni. Az fpc a (toval-1) értéket a for előtt a helyszínen számolja ki. Tehát a külső ciklusban mindig kiszámolja a belső (toval-1)-et nálam. De ez esetünkben tized százaléknál kisebb időeltérést okoz a tied javára. Ez a mérési bizonytalanságnál kisebb eltérés.

Nálam azért nagyobbak az idők minden nyelvnél a te laptopodhoz képest, mert lassabb az i5-3337u procim a tiednél. Azt hogy milyen procid van, talán így megnézheted: dmesg | grep CPU (de nem próbáltam).

"Ha az fpc -nek adsz egy -a kapcsolót, akkor tanulmányozhatod a .s assembly fájlt."
Legkozelebb Arpinak leirod, hogy kell medialejatszot irni? :)

--
When you tear out a man's tongue, you are not proving him a liar, you're only telling the world that you fear what he might say. -George R.R. Martin