Sebességteszt: 4096 pontos FFT

 ( hg2ecz | 2017. január 4., szerda - 3:49 )

Kíváncsiságom miatt leprogramoztam a 4096 pontos FFT-t tisztán az adott nyelveken és 1000-szer futtatva a lefordított C-hez képesti futási időarányok láthatóak alább x86 és ARM Cortex A53 architektúrákra.

Intel i5-3337u, Ubuntu-16.04 (64 bit):
--> Java: 1,5-szörös idő a C-hez képest (JRE: build 1.8.0_111-8u111-b14-2ubuntu0.16.10.2-b14). Kiváló a JIT-je x86-on.
--> C# mono-val 5,6-szoros idő (Debian 4.2.1.102+dfsg2-7ubuntu4)
--> Pypy-vel Python 5,5-szörös idő (klasszikus cPython csigalassú: 86-szoros idő, cPython3: 105-szörös idő)
--> LuaJit-tel LUA 6-szoros idő (LUA interpreter 260-szoros idő)
--> JavaScript nodejs-7.3 esetén 20-szoros idő
--> PHP7 esetén 100-szoros idő

ARM Cortex A53 (Rpi3), Debian Stretch beta (32 bit):
--> Java: 110-szeres idő a C-hez képest (OpenJRE: build 1.8.0_111-8u111-b14-3-b14) - nincs benne ARM-ra JIT
--> Java: 8-szoros idő a C-hez képest (Oracle JRE: build 1.8.0_65-b17)
--> C# mono-val 8,7-szeres idő (Debian 4.6.2.7+dfsg-1)
--> Pypy-vel Python 27-szeres idő - ARM esetén a JIT még reszelhetőnek tűnik.
--> LuaJit-tel LUA 8,1-szeres idő
--> JavaScript nodejs-4.4 esetén 24-szeres idő, nodejs-7.3 esetén 36-szoros idő
--> PHP7 esetén 130-szoros idő

Elsőre meglepő, hogy a Java JIT-je x86-on nagyon szépen muzsikál, viszont ARM-on az OpenJRE egyáltalán nem, az Oracle JRE pedig az x86-nál sokkal rosszabbul. A Dalvik létrejöttének egyik oka valószínüleg ez volt.

És ha már tempókról írok, architektúrák tempói C nyelven írt FFT-vel tesztelve, Intel i5-3337u-hoz viszonyítva (1 szálon, tehát a turbó mód is játszik):
--> Intel J1900 esetén 2,35-szörös idő kellett
--> Raspberry Pi3-on 5,7-szer lassabban futott (a J1900-hoz képest 2,4-szer lassabb)

Szerk#1: köszi az Oracle JRE ötletet. Abban tényleg van JIT ARM-ra ... belefűztem a fenti listába.
Szerk#2: x86-on a Java JIT "előmelegítve" jobb eredményt produkált (javítottam), ARM-on Oracle JRE esetén sem.

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ő.

Esetleg a megírt kódokat feltehetnéd valahová.

+1 Mehetne akár a benchmarksgame-re is.

GitHUB-ra feldobtam. Aki lát benne kevésbé optimális fogást, a javításokat örömmel veszem.
Ruby-t is látom felajánlottátok. Ha valaki átírja rá, azt is befogadom.

Egyébként kimondottan jelfeldolgozásra való alkalmasság érdekelt abban az esetben, ha speciális a feladat és nincs lehetőségem kész háttérmodul importálására. Az FFT-re azért esett a választás, mert kacifántos és libfftw3 segítsésgével tudtam ellenőrizni hogy nem számoltam félre.

Hol a github link? Csak én nem látom? :)

> GitHUB-ra feldobtam.

Köszi!

> Aki lát benne kevésbé optimális fogást, a javításokat örömmel veszem.

A JIT-es nyelveknél, ha adnál egy kis időt a bemelegedésre, akkor egy kicsit közelebb kerülnénk a valós számokhoz.

pl. Java-nál a mérés elé tegyél egy bemelegítő számolási ciklust:

for (i=0; i<10000; i++) fft(LOG2FFTSIZE, xy_out_fft, xy);

// FFT
...

FFT_REPEAT=1000 esetén:
0,23457 ms/piece
-ről
0,19205 ms/piece
-re gyorsult.

Egyébként majdnem ennyi lett FFT_REPEAT=100000-nél is bemelegítés nélkül.

Szerk.: a C-fast: 0,125 ms/piece lett; 1,5-ször lassabb a Java-s.

Köszi, beleraktam. ARM-on nem hozott az Oracle JRE esetén sem javulást.
Azonban x86-on tényleg levihető 1,5-ös arányra. Javítottam a fenti összefoglalóban is.

Egyébként hogy a gyors prociddal össze tudd vetni az SBC-t: C-fast Rpi3-on 0,902 msec,
Odroid-C2 prociján 64 bitesként 0,789 msec míg 32 bites binárisként 0,73 msec

> gyors prociddal

Ez egy mobil i7-4720HQ.

Elég jó látni, hogy ezek az olcsó kis ARM procik milyen gyors ütemben fejlődnek.

sub

ARM-on az Oracle féle verziót vagy az OpenJDK-t próbáltad?

Érdemes lenne esetleg az embedded verzió(ka)t is kipróbálni.

(Törölve - vak vagyok.)

Ahhoz, hogy valós képet kapjunk a Java-s sebességekről, ott egy kicsit azért másként kell tesztelni, mint a C-s programoknál. Lásd itt.

Ezt konkrétan eddig nem ismertem, de 7-8 éve írtam C vs Java microbenchmarkokat kb ilyenek mint láncolt listában pointer chasing, bináris (AVL) fa kiegyensúlyozás és a jelenségek egy részével találkoztam. De azért a cikkben írt példákban eléggé rázza a pofonfát pl a számítás eredményének helyben eldobásával, elég common sense, hogy ilyet nem csinálunk, mert nemcsak Java tudja kioptimalizálni, még akár a gcc is. A Runnable dispatch félreoptimalizálása (benchmark futtatási sorrend) meg egyszerűen a benchmarkonkénti warmup túl kis értéke miatt van. De ez megint nemcsak java specifikus, minden JIT compileres futtatókörnyeztnél (sőt más okok miatt az interpretáltaknál is) kisebb nagyobb mértékben előjön. Lassan már inkább C lesz a kakukktojás, aminél nem.

Egyébként ha kellő ideig hagytam a jit compilert optimalizálgatni, akkor következetesen a gcc -o1 és -o2-vel fordított eredményei közé be tudott jönni a jvm, ami szerintem elég jó.
---
Régóta vágyok én, az androidok mezonkincsére már!

Igen, a hotspot compiler "bemelegedése" miatt az ilyesmit úgy kell futtatni, hogy előtte hosszú ideig járatjuk a programot, ezalatt megtalálja a JVM, hogy ez egy hotspot, és akkor kompilálja. Amíg ez nem következik be, addig optimalizálatlanul fut a kód, illetve maga az optimalizáló JIT fordítás is erőforrást visz el.

Ezek miatt (meg egyebek miatt is, pl garbage collector), a Java benchmarkolása elég összetett dolog.

Plusz az összehasonlíthatóság feltétele az is, hogy ugyanannyira legyen a forráskód optimalizált, ezért jó lenne forrást látni.

ARM-re tudtommal sokáig nem állt rendelkezésre a JIT compiler, de legalábbis az optimalizált változat biztosan nem, és ezért a gyengébb teljesítményű interpretált módban fut a program, azért sokkal lassabb. Ennek nem az az oka, hogy az ARM annyival alkalmatlanabb lenne Java-hoz, hanem az, hogy ez a JVM félkész.

pontosabban interpretal minden methodot, amig meg nem hivtad CompilerThreshold-szor, ami alapbol 10000. A forditas egy erre dedikalt szalon tortenik. A vm barmikor donthet ugy, hogy visszadobja interpretaltnak, pl ha egy devirtualizacio mar helytelen lenne. Azaz igy volt java 8-ig, amiben AFAIK mar default a tiered compilation, amivel bekerult egy rakas koztes lepes az interpretalt es a server profile koze. :)

--
NetBSD - Simplicity is prerequisite for reliability

subscribe
-------------------------------------------------------------------------------
Az életben csak egy dolog a szép, de az épp nem jut eszembe.

Slackware Linux 14.2 | 4.4.37-janos

Nem lenne kedved megnézni egy Ruby-t? Vagy adni forrás kódot?

Engem még az awk is érdekelne.


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

Akkor már a Perl-t is hozzácsaphatnánk. De tény, hogy tudtommal egyetlen AWK megvalósításban sincs semmilyen fordítás, tudtommal teljesen interpretált az egész (még JIT sincs). (Illetve mintha a Mortice Kern Systems-nek - MKS-toolkit - lett volna AWK-to-C-je ezer éve.)

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

Viszont tudtommal nem is bután olvassa a scriptet, ha kell több milliószor egy ciklusmagot, hanem valami köztes kódot csinál. Gondolom, a változónevek memóriacímekké fordulnak, meg a függvény hívások szintén.


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

OT
Egy "tesztet" csnáltam AWK-val - hát marhára nem mindegy, melyiket használja az ember.
A rövid teszt: "leprogramoztam" az Ackermann-függvényt és megmértem 3,10 paraméterekkel - elég nagy a szórás: az én gépemen mawk (~6 sec), gawk (~18 sec), nawk(~36 sec) az eredmény, és a system idő is a One-True-AWK-nál a legnagyobb. Szóval nem azzal kéne dolgozni :-)
/OT

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

Most csak a különféle awk implementációkat hasonlítottad egymáshoz. Semmit nem mond más nyelvekhez viszonyított sebességéről. Nyilván compilált nyelv nem ér, az awk mégis csak interpretált.


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

Azért ennek az összehasonlításnak legalább annyi értelme van, mint egy FPU unicode feldolgozó sebességét megmérni. ;)
Aztán a klasszikus (legyen BSD) awk kimaradt, pedig a fenti verziók egyáltalán nem kompatibilisek.
Az awk fordít, méghozzá a regexp-eket. Egy igazi művész bizonyára meg tud írni egy fft algoritmust regexp támogatással, de lássuk be: összehasonlítás helyett sokkal hasznosabb, ha valaki el tudja dönteni mi mire való.
Sok év tapasztalat és rengeteg adat alapján ki merem jelenteni, hogy a C:awk futásidő aránya 1:6.
Numerikus feldolgozásnál megint felesleges az összehasonlítás, mert az awk-ban nincs is olyan. Ennek ellenére - ha speciális esetben jól kitalált az ábrázolás - néha elég jó eredmény lehet elérni. Persze ez megint nem a nyelvek összehasonlítását, hanem a programíró awk-guruságát méri.

Mit értesz numerikus feldolgozás alatt? A GNU awk-ban vannak szögfüggvények, exponenciális, logaritmus függvény, az alapműveletek, véletlenszám generálás. Ezen felül C-szerűen írható benne program, egyáltalán nem vagy rákényszerítve, hogy mindent regexp-ben fogalmazz meg. Ciklus szervezésre, feltételes végrehajtásra is van lehetőség. Van asszociatív tömb kezelés, továbbá van mód file írására, olvasására. Így hirtelenjében azt mondom, semmi sem hiányzik ahhoz, hogy szinte bármit, teszem azt fft-t megírj awk-ban.


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

Háát...gratulálok!
awk 'BEGIN { X+=111111.5; X+=10; print substr(X,3),X }'
Ezt azért rakd át C-be, úgy C-szerűen. ;)

Tehát mégegyszer: nem azt írtam, hogy nem lehet megírni, hanem az összehasonlítás felesleges. Templomban is lehet káromkodni, csak nem való. Ugyanúgy, ahogy a C# és az abacus összevetése is jó dolognak tűnik elsőre. Vagy azt állítod, hogy az abacus alkalmatlan sin(x) számítására?!?!?!

Bár nem kizárt, hogy tájékozatlan vagyok, és egy ideje a gawk tartalmaz komplett math implemetációt, valamint turbó mákdarálót is. Enne ellenére vannak olyan dolgok, amikor soha nem fordulnak meg a fejemben. Pl. a heapsort megvalósítására 4M adat esetén ksh-t használjak. Annak ellenére, hogy meg lehet benne írni. Szóval gawk-fft előfordulási valószínűsege tart a nullához, míg az fft-altivec/sse/stb. sokkal valószínűbb a mai világban, mint a C#-fft. Tehát ezek a vizsgálatok olyat hasonlítanak össze, ami a valóságban nem szokott előfordulni. Pl. hogyan jutunk el a Holdra gyorsabban: rollerrel vagy Trabanttal?

(Igen, az altivec NEM programnyelv.)

Na várj, ha valóban sebesség a szempont, akkor a natív C-nél ne is nagyon menjünk messzebbre.

Viszont nem korrekt, hogy a shell scriptekben megszokott, „egy sorba írok valamit, mert lusta vagyok több sorba írni, úgyis rövid lesz, pontosvesszőt meg kitalálták már” mentalitással prezentálod, mennyire lesz áttekinthetetlen egy fft awk-ban.

Eleve nem muszáj awk scriptet shell scriptbe ágyazni. De, ha már igen, akkor valahogy úgy, hogy egy sok soros stringként definiáljuk az awk scriptet, amelyet mint változót adunk át helyettesítésre a shellnek, aki átadja ezt az awk-nak.

Viszont ennél sokkal szebb natív awk scriptet írni valahogy így, bár ez valóban szöveg feldolgozás egy szintén (színdefiníciós) szövegfile alapján, mellesleg a LEDE router-em bannerét színezi ki:

#!/usr/bin/awk -f

BEGIN {
    a["norm"]="\x1b[m";
    a["black"]="\x1b[30m";
    a["red"]="\x1b[31m";
    a["green"]="\x1b[32m";
    a["brown"]="\x1b[33m";
    a["blue"]="\x1b[34m";
    a["magenta"]="\x1b[35m";
    a["cyan"]="\x1b[36m";
    a["white"]="\x1b[37m";
    a["lred"]="\x1b[31;1m";
    a["lgreen"]="\x1b[32;1m"
    a["yellow"]="\x1b[33;1m";
    a["lyellow"]=a["yellow"];
    a["lblue"]="\x1b[34;1m";
    a["lmagenta"]="\x1b[35;1m";
    a["pink"]=a["lmagenta"];
    a["lcyan"]="\x1b[36;1m";
    a["lwhite"]="\x1b[37;1m";
    s="";
    while (getline colors <colorfile) {
        tn=split(colors, t);
        for (i=1; i<=tn; i++) {
            un=split(t[i], u, /\*/);
            if (u[un] ~ /^[0-9]+$/) {
                continue;
            }
            if (un==2) {
                if (u[1] ~ /^[0-9]+$/) {
                    mul=int(u[1]);
                    if (mul>99) {
                        mul=99;
                    }
                } else {
                    mul=0;
                }
                for (j=0; j<mul; j++) {
                    s=s u[2] " ";
                }
            }
            if (un==1) {
                s=s u[1] " ";
            }
        }
    }
    colornum=split(s, c);
    FS="";
    p=1;
}

{
    s="";
    last=" ";
    for (i=1; i<=NF; i++) {
        if ($i!=" " && last==" ") {
            if (p<=colornum) {
                if (c[p] in a) {
                    s=s a[c[p]];
                } else {
                    s=s a["norm"];
                }
                p++;
            } else {
                s=s a["norm"];
            }
        }
        if ($i==" " && last!=" ") {
            s=s a["norm"];
        }
        s=s $i;
        last=$i;
    }
    s=s a["norm"];
    printf("%s\n", s);
}

Mivel szeretem az awk-t, kíváncsi voltam, mennyire gyors. Nyilván fényévekre a C-től, mert interpretált, de sokkal gyorsabb például egy bash-nél. Engem továbbra is érdekel egy ilyen mérés eredménye.


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

+1
Az első sorra. Bár kifelejtetted a dsPIC+asm verziót. ;)

Amít írtam, nem tipitkus "awk oneliner" akart lenni, hanem éppen cygwin cmdline-t másoltam oda. Tehát semmi köze az awk forrás tagolásához.
Amit nem értettél a példában, hogy az awk alapvetően string, regexp és tsai feldolgozására van kihegyezve. Kicsit lehet irányítgatni a szám kezelését, amit így szoktam megtenni:

BEGIN
...
X+=0
...

Ebben az esetben az alapértelmezetten EMPTY vagy 0 értékre incializált változó inkább fog számként viselkedni. Vagyis nehezebb eltéveszteni.
A példában egy float(szerű) valamivel számoltam, majd a substr kiírta az int érték kerekített substringjét. Ezzel kívántam bizonyítani, hogy csak egy típus van, de az nem int hanem string, ha szám akkor inkább int. Ez sem jelenti azt, hogy használhatatlan, de így működik, azaz számításokra nem optimális.
Az awk nekem is a kedvencem. A szokásos feldolgozások mellett többször használtam terminálszerver vagy router programozására konfigurációs adatbázis alapján, telnet felületen keresztül. Nyugodtan állíthatom, hogy több mint 100.000 sort írtam benne.

Ja, hogy az volt a baj, hogy gyengén típusos nyelv? Sok scriptnél így van ez. Ha egy számjegyekből, néhány kiegészítő jelből álló stringet numerikus függvény kap meg, akkor bizony pontosan tudja, hogy az egy szám abban a kontextusban. Azt persze értem, hogy konvertálni kell, ami idő.


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

Bingó!
Bár ez NAGYON gyengén típusos nyelv. ;)

Idézet:
awk 'BEGIN { X+=111111.5; X+=10; print substr(X,3),X }'
Ezt azért rakd át C-be, úgy C-szerűen. ;)

Most eltekintve attól, hogy kihagytad a /dev/null paramétert, ami miatt ez a végtelenségig olvassa az STDIN-t, egy *jó* C-fordító (és egy közepes C-programozó) biztosan kioptimalizálná valami ilyesmire:

#include < stdio.h >
main() { puts( "1122 111122" ); }

Egyébként egy kezdeti AWK-ban írt FFT-implementáció van itt. Finomítani való akad még rajta. :-D

Egyébként szerintem mind a ketten félreértettétek a kiinduló megjegyzésemet:

a) először is, szerintem az nyugodtan elmondható, hogy egy C-ben írt implementációnál az összes interpretált (pl. AWK) és az összes JIT-es nyelv-beli megvalósítás (Java, C#, stb) csak lassabb lehet futásidőben, hisz az elsőnél a futási időbe nem fog beleszámítani a fordítás ideje, a másodiknál meg igen. (Feltéve, hogy mind a kettő ugyanúgy számol.)

b) csak annyit akartam jelezni, hogy lehet éppen átírni a C-beli FFT-t számoló kódot AWK-ba is akár, de ha valaki éppen mérni akar, akkor nagyon nem mindegy, hogy melyikkel mér, hisz egy az FFT-nél sokkal egyszerűbb kód esetén is jelentős futásidejű eltérés van a legelterjedtebb és legkönnyebben elérhető nyílt forráskódú AWK-implementációk között.

c) és akkor azt még figyelembe se vettem az én kis tesztecskémben, hogy mivel ezek az AWK implementációk C-ben vannak írva, ezért egy "korrekt" összehasonlításhoz az kellene, hogy pontosan ugyanazok, a pontosan ugyanolyan módon fordított C-fordítók fordítsák ugyanolyan paraméterezéssel az egyes AWK-kat (és a hozzájuk használt libc/libm megvalósításokat). Ez pl. már nálam sem biztosan teljesült, hisz FreeBSD-n a One-True-AWK az alaprendszerbeli (azaz itt konkrétan clang-gal fordított), míg a mawk és gawk csomagból telepített (azaz akár gcc-vel fordított is lehet).

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

Köszi a kiigazítást, de sajnos az awk nem úgy működik, ahogy hiszed. ;)

BEGIN {}
pattern {action}
...
pattern {action}
END {}

A fenti szerkezet közepe (legyen BODY) alapértelmezetten olvassa az stdin-t. A BEGIN a BODY és az END szakasz bármelyike elhagyható. (Ad absurdum, ha mindegyiket elhagyod, akkor program sincs, viszon van default action==print, ezért vár a stdin-re.) A BEGIN és a BODY szakaszból ki lehet lépni az exit utasítással, ekkor a végrehajtás az END szakasszal folytatódik - ha van. A példámban hiányzik a BODY ezért nincs aki olvasson az stdin-ről, azaz a program rögtön kilép. Gyávábbak és hitetlenek a BEGIN szakasz utolsó soraként irhatnak egy exit-et. ;)
Ezt nem csak azért írom, mert rengeteg awk programot ítam, hanem a közzétett sorokat előzőleg mindig kipróbálom - vagy felhívom a figyelmet az ellenkezőjére. És azért lett egysoros, hogy egérrel jobban bekeríthesd és kipróbálhasd.

Az abc pontokkal egyetértek. Az awk ereje abban rejlik, hogy a regexp-eket fordítja. Ez a tulajdonság egyáltalán nem elhanyagolható, ha a regexp vagy azok összefűzött verziója több oldalt tesz ki, és néhány millió rekordot kel feldolgozni. Ez az a pont, amikor meg lehetne írni C-ben is, de úgy fel kéne hozzá kötni a gatyát, hogy nem éri meg. ;)

Visszatérve az abc pontokra, még másról is lehet szó. Egy ilyen tesz teljesen önkényes választáson alapul. Mint minden tesztnél, soha nem a valós felhasználás sebességét, hanem a tesztprogram futását méred. Egy gyakorlott szakember nem csak ügyesen kódol, hanem az eszköz kiválasztásánál is ügyeskedik. Ráadásul egy adott feldolgozás megírásának módja általában függ az adatok mennyiségétől. Volt egyszer egy feldolgozás, ami 2 órán keresztül futkározott. Majd jött egy újabb adatmennyiség, amihez egy kicsit gyorsabb gépre raktam a feldolgozást és egy kicsit át is szerveztem. A futásidő 6 perc lett (azaz huszad része) 12x több adattal. A végeredmény 240x gyorsabb feldolgozás. Ugyan a másik gép gyorsabb volt, de azért nem ennyivel. ;) Viszont a dal és az awk ugyanaz maradt!

Köszi a javítást a nem kötelező /dev/null-ról, ez most jól meglepett. Ezt a részt viszont magyarázd meg, mert szerintem hibás:

Idézet:
(Ad absurdum, ha mindegyiket elhagyod, akkor program sincs, viszon van default action==print, ezért vár a stdin-re.)

Default action csak akkor van, ha van *explicit* minta. Jó pár awk manualban szerepel ez: a pattern { action } párosból vagy egyik, vagy másik elhagyható, de mind a kettő nem. Ami persze a szó szoros értelmében nem igaz, hiszen lehet awk-scriptet írni úgy hogy nincs "body", de BEGIN és END igen - viszont szó nincs róla, hogy ilyenkor is lenne explicit print:

$ awk 'BEGIN { a=1 } END { print a }' /etc/profile
1
$ 

Ha viszont a body-t is elhagyom, az én értelmezésem szerint a te fent idézett megfogalmazásod szerint az üres awk-script egy cat-tal egyenértékű, holott nem:

$ awk '' /etc/profile
$ awk '' 
$ 

Az első nem ír ki semmit a profile-ból, a második nem vár az STDIN-en semmit, csak kilép.

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

Majdnem igazad van, de a helyzet bonyolultabb!

Vegyünk alapul egy ősi definíciót (90-es évek eleje):
Beírok egy parancsot és enter
- Kiírja hogy kopirájt Pítör Norton == DOS
- Nem ír ki semmit == UNIX
:)

Újabb definíció (napjainkban):
Beírok egy parancsot és enter:
- Nem ír ki semmit == UNIX
- Kiír mindenféle ostobaságot == GNU
:)

A fentiek alapján a tévedésemet elismerem, de csak addig, hogy nincs pattern (se) -> nincs default action.

Tehát

awk /etc/profile

nem ír ki semmit (nem lehet semmiképp elérni, hogy bármit kiírjon sem az stdin sem a file inputból), de vár.

DE!

$ echo hello|awk /etc/profile
hello

$

SŐT!

$ echo hello|awk /etc/kuki
hello

A /etc/kuki nem létezik, viszont stdin-ről olvas.

ÁMBÁR!

$echo hello|awk
->kirongyol az usage

VALAMINT!

$awk /etc/kuki
aaa
^D
aaa

Azaz stdin-ről olvas figyelmen kívül hagyva a nem létező /etc/kuki-t.

Talán vannak még variációk, de elfáradtam.

No, ez az igazi konzisztencia és koherencia. Csak nem mondom meg mivel! :D

További pontosítások. Az összes awk /x/y tipusú hívásodat te magad félreérted - azt ott nem feldolgozandó fájlnak tekinti (ezért mindegy neki, hogy létező vagy nem létező fájl), hanem AWK programnak. (Tudod: az első nem-opció paraméter az a jellemzően aposztrófok között átadandó AWK-script. Lásd még: egrep awk-ban: awk /ERE/ ) Tekintve hogy a szintaxis egyértelmű - a "minta { akció } " párosból az akciónak kötelező eleme a kapcsos zárójel-pár, ezért az ott nem a végrehajtandó utasítás, hanem a feldolgozandó (azaz feltételnek minősülő) minta. Hogy mi a francot jelent egy "látszólag_regex_illeszkedés_vizsgálat_kiegészítve_valamivel" kinézetű szöveg, arra még nem jöttem rá. (Főleg úgy, hogy a /min/ta illeszkedik - ezért is van az STDIN olvasása és a kiírás.)

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

A helyzet ennél sokkal rosszabb. Programnak csak a -f opcióval, egyébként pattern-nek, és szintaktikai hibát is jelez. Tehát a /etc/profile az nem path hanem pattern! Ha programot írnál aposztrófok közé, akkor a pattern-t is oda kell rakni.

$echo hello|awk /hello/
hello

$echo hello|awk //
hello

$ echo hello |awk /x/

A /min/ta elég érdekes, mert a /min/ odáig jó, a "ta" meg a pattern vagy logikai kifejezés folytatása lenne. De a /min/ nem illeszkedik, így a továbbiakat nem is értelmezi. Már csak az a kérdés, hogy ha a /min/ illeszkedik, akkor miért nem vizsgálja tovább és dob esetleg szintakszot?

Számomra annyi a tanulság, hogy awk oneliner csak nagyon egyszerű vagy pontosan megfogalmazott programocska lehet. Más esetekben zavar támadhat.

Akkor tisztázzuk. Azt mondtam, hogy ha awk /x/y sort írsz, akkor a /x/y nem a végrehajtandó kódot tartalmazó fájl neve (ekkor kellene a -f opció), hanem maga a végrehajtandó kód. (Ahogy mondtad: oneliner) És mivel a végrehajtandó kód "minta { akció }" felépítésű kell legyen, aminél akció csak kapcsos zárójel között állhat, ebből következik, hogy a /x/y csak minta lehet. Formájából adódóan ez ugye regex illeszkedés-szerű. Viszont valami nagyon nem kerek ezzel, mert fenti példáid egytől egyig teljesen korrektek (még a meglehetősen furcsa második is, lásd echo hello | grep '' ), de szerintem ez a leglogikátlanabb:

$ echo hello | awk /x/y
hello
$

No és ennek is megvan a kimenete. Ezt viszont nem értem. x ugye nincs a helloban, ezt mutatja a te harmadik példád is, de miért lett kimenet abban a pillanatban, ha mögé került az y. Az a gyanúm, hogy valahogy a /x/ regexp és az "y" (amit egyelőre nem értek, hogy micsoda) és a " " - sztring összefűzó operátor (de lehet hogy valami más) kombinációja eredményezi azt, hogy a "feltétel" teljesül. (Vannak még ilyen zűrös példák:

$ echo hello | awk 0
$
$ echo hello | awk 1
hello
$

Szóval totál káosz.)

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

Az utolsó példákra legalább tudom a választ. A 0==false, 1==true - ezek mint a regexp vagy logikai feltételek eredménye - és a default action==print.

Ha a megadott minta illeszkedik, akkor print hajtódik végre, ha nem, akkor semmi.

pl.

> echo hello | awk /./
hello

> echo hello | awk /x/

> echo hello | awk /h/
hello

> echo hexo | awk /x/
hexo

vagy stdin-nel:

> awk /x/
hello
hexo
hexo
mas

Csak a hexo-t duplázta.

Azt, hogy az /x/y miért illeszkedik, azt én sem tudom.

> Azt, hogy az /x/y miért illeszkedik, azt én sem tudom.

Pedig ugye ez volt a kérdés, a többi teljesen egyértelműen az awk jól dokumentált viselkedésének köszönhető.

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

De azért kiszámolta az FFT-t. Szombat reggeli ujjgyakorlatként a LUA kódot átírtam gyorsan AWK-ra (gawk).

Megjegyzem, szkriptnyelvként a LUA kedvesebb, mert
- a (g)awk-nál az összes változó globális ... ez hibát is okozott
- igen korlátozott az AWK, például millisec-es időre sincs függvénye
- gawk-nál a LUAjit 76-szor gyorsabb ... a C-ben írt pedig 640-szer gyorsabb. Az AWK is jól elpazarolja a procit.

> igen korlátozott az AWK, például millisec-es időre sincs függvénye

Ha ilyen lassú, akkor felesleges is ;)

Mondjuk ha megnézed a gawk doksit, akkor ezt találod:

Idézet:
Bit Manipulations Functions
Gawk supplies the following bit manipulation functions. They work by
converting double-precision floating point values to uintmax_t
integers, doing the operation, and then converting the result back to
floating point.

És persze a jópárszor használt rshift és lshift ugye ilyen. Szerintem ha ezeket a megfelelő "osztunk kettővel/néggyel", "szorzunk kettővel/néggyel" műveletre cserélnéd, akkor egyrészt gyorsabb lenne, másrészt nem lenne gawk-specifikus funkció benne (azaz ki lehetne próbálni a többi awk megvalósítással). De ez csak tipp.

Amúgy létezik függvényre lokális változó, szimplán extra paraméterként kell a fv-paraméterek közé felvenni.

Hopp, van még egy gawkizm: az @include - de azért azt se túl bonyolult "javítani".

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

Persze hülye vagyok, az AWK csak egydimenziós tömböket kezel gyárilag, az összes többdimenziós tömböt a SUBSEP változó segítségével kell megadni - azaz a gawk-> awk átalakítás egy kicsit több, mint az lshift-ek és rshiftek lecserélése (meg az include eldobása. (Technikailag persze csak annyi, hogy a[i][j] helyett a[i,j] formára kell hozni - ha jól emlékszem.

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

AWK doksit vesd össze légyszíves a LUA doksival. Érdemes, én is meglepődtem a két nyelv közötti hasonlóságokon.
Ennek tükrében nem véletlen, hogy a LUA kódot dolgoztam át.
A lokális változó furcsán van megoldva, köszi a tippet.

Hány százalékont gyorsult, ha elhagytad a bitmanipulációs műveleteket?

Még semennyit, mert bitwise or és and sincs, szóval azzal is kell egy kicsit gyökölni. Ráadásul ha "gyorsan" akarnám megcsinálni, akkkor nem implementálom és hívogatom ezeket a fv-eket, hanem inline cserélem ki a kódban. Egyelőre lassan haladok a módosításokkal.

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

millisec-es időre sincs függvénye

Ez most meglepett. Egy fft-ben miért kellene bármire várakozni? Gondolom, nem egy audio stream-ről csinálsz fft-t valós időben, hanem adott mintákból, mint adathalmazból a lehető leggyorsabban, ahogy a csövön kifér, csak más-más nyelven implementálva. Szerintem valamit nagyon félreértek ezzel a ms-os idővel, csak nem tudom, hogy mit.

a (g)awk-nál az összes változó globális ... ez hibát is okozott

Ez nincs így. A függvény bemeneti paraméterei között kell megadni a lokális változókat, ám a függvényt lehet kevesebb paraméter átadásával hívni, mint amennyi a függvény definíciójában szerepel. Tehát:

function f(a, b, c,
x, y, z) {
...
}

A hívása:

val=f(param1, param2, param3);

Ekkor a függvényen belül x, y, z lokális változók.


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

Ha megnézed a kódot, akkor látod, hogy a millisec simán a méréshez kell, nem az fft-hez. Azaz induláskor lekérjük , hogy most mennyi az idő, meg amikor befejeztük, akkor is. A különbség a futási idő :-)

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

Bocsánat, nem pillantottam a kódra. ;)


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

Ha már itt tartunk: hogyan lehet AWK-ban megoldani, hogy ha kétszer megolvasom a /proc/uptime -t, akkor ne ugyanazt az eredményt adja vissza.
A délelőtti kódomban ugyanis ezért van symlink-elve más fájlnévre a második felolvasáshoz.

$ awk 'BEGIN {
uptime="/proc/uptime"
while ( 1 )
{
getline < uptime
close(uptime)
print $0
system("/usr/bin/sleep 1")
}}'
1030667.75 782904.56
1030668.89 782905.42
1030670.00 782906.34
1030671.19 782907.27
1030672.38 782908.18
1030673.56 782909.11
1030674.77 782909.94
1030675.78 782910.76
1030676.99 782911.62
1030678.10 782912.53
1030678.91 782913.12

Köszi a segítséget, javítottam.

Idézet:
Aztán a klasszikus (legyen BSD) awk kimaradt,

Ha az oawk-ra - awk77 -re gondolsz (azaz Aho-ék első megvalósítására), az SystemV-os, nem BSD-s :-) Egyszerűen nem emlékszem, és most nem érek rá utánanézni, hogy az oawk-ban volt-e saját függvény definició - ha nem, akkor azzal azért elég nehéz lenne bármi komolyabbat csinálni - ha már abban is volt, akkor annyira nem vészes, viszonylag kevés olyan funkciója van az nawk-nak, amit az ack()-nál illetve az fft()-nél ki kéne használni.

No kiszáltam.

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

Engem az érdekel egy kicsit, hogy a Java miért ennyivel rosszabb a Monohoz képest, ARM-en.
Esetleg, hogy a .NET Core hogy teljesít a Monohoz (s a Javahoz) képest.
--
blogom

ARM-re nem készült el a JIT compiler jelentős része, ezért az optimalitálások teljesen kimaradtak belőle.

Ebben biztos vagy, vagy csak gondolod?

Az OpenJDK-ban valószínűleg tényleg nincs benne, de az Oracle-féle verzióban, főleg az embedded-ekben már nem lennék ilyen biztos, főleg, hogy van pl. RaspberryPi-ra optimalizált verzió is.

Szerk.: a készítő update-olta az Oracle-féle verzióval az ARM-os méréseit és így már látszik is, hogy abban tényleg benne van, (8-szoros lemaradás a C-hez képest, a többinél meg gyorsabb).

Az embedded-ekre még azért kíváncsi lennék.

viszont akkor lassan végetér a „nincs is semmi különbség (csak nagyonnagyonkevés) az OpenJDK-s és az Oracle-s JVM implementáció között” állítás érvénye?
van erről valami up-to-date lista, hogy az egyes Oracle JVM implementációk mennyiben térnek el az OpenJDK-s implementációtól?
--
blogom

Én is úgy értettem, hogy a mért verzió volt ilyen. Régebben próbálkoztunk Java program "portolásával", hasonló értékeket mértünk, és akkor hallottam ezt az infót.

A jazelle lehetne még érdekes.

Küldtem pull resuestet: .NET Core App 1.0->1.1

Fuszenecker Róbert

Amúgy meg, jól vektorizálható feladatot CPU-val végeztetni GPU helyett, WUT???

A felvetés jó, de kicsi lett nálam a prioritása. Oka: ARM SBC-ben gondolkozom. Itt pedig még pár év kell, mire érdemes lesz erre alapozni.

Ha viszont valaki dob OpenCL vagy egyéb nyelvre átírt kódról pull requestet, szívesen beolvasztom azt a kódot is, ahogy a C#, F# és a TypeScript kód is barátom segítségével jött létre.

Van, az F#-MathNumerics könyvtárban találod.

Fuszenecker Róbert

Lazán kapcsolódik, épp most jött:

Grumpy is an experimental Python runtime for Go. It translates Python code into Go programs, and those transpiled programs run seamlessly within the Go runtime. We needed to support a large existing Python codebase, so it was important to have a high degree of compatibility with CPython (quirks and all). The goal is for Grumpy to be a drop-in replacement runtime for any pure-Python project.

https://opensource.googleblog.com/2017/01/grumpy-go-running-python.html

Ha értenék hozzá, kipróbálnám pár Lisp implementáción.

Pedig ez engem is nagyon érdekelne.
Van egy C-s implementáció, ami iteratív, de van egy olyan C megvalósítás is, ami rekurzív.
Úgy gondolnám, talán ez utóbbi közelebb áll a Lisp logikájához.

Fuszenecker Róbert

Magát az algoritmust lehet át tudnám ültetni, viszont az szerintem nem lenne túl lisp. Valami rémlik a régi tanulmányokból az FFT-ről, de nagyon halovány. Matek BX meg Rendszertechnika, régi szép idők.

Itt az ideje egy kis ujjgyakorlatnak, maximum a másik belejavít és csak tanulsz újabb trükköket.

Hááát azért... 15 perces munkával sikerült a C# kódot 57,8%-al gyorsítani. (.NET 4.6.1-en, W10-en).

1) Az mcs paraméterei közül hiányzott az optimalizáció. (VS-ből, .NET 4.6.1-el fordítva ez nálam 781 ms-ről levitte 391 ms-re, azt nem tudom, hogy az mcs mennyire jó IL kódot fordít.)
2) A System.Numerics.Complex egy struct, az xy_out-nál teljesen feleslegesen volt egy plusz konstruktorhívás, simán át lehet adni az xy_in-ből, érték szerint fog átadódni.
3) Ugyanígy lejjebb az (1,0)-ás értéket teljesen felesleges volt újra létrehozni. Egyébként van a Complex.One érték. Ezen még optimalizáltam egy picit. (Ez a második ponttal együtt újabb 15%-ot hozott)
4) Picit refaktoráltam a kódot, hogy ne legyenek már annyira Java-sok a nevek, mert baromira zavart.
5) Tök felesleges a phasevec inicializálásának megtörténtéhez egy külön változót létrehozni, azt is lehet vizsgálni, hogy az null-e.
6) Egyékbént az FFT függvényen belül teljesen felesleges inicializálni azt újra és újra.

----------------
Lvl86 Troll, "hobbifejlesztő" - Think Wishfully™

Az nekem is feltűnt, hogy x86_64-en a mono jobban jit-elt, mint a .NET Core.
Nem volt nagyságrendi különbség, de látszott a végeredményen.

Fuszenecker Róbert

Egyébként küldtem pull requestet.

----------------
Lvl86 Troll, "hobbifejlesztő" - Think Wishfully™

Be is merge-öltem magamhoz :-) Nem is tudtam, hogy ilyet is tud a GH. Mármint egy meglevő PR-t leszedni magamhoz.
Nekem is van/lesz egy PR-em, mert VS2015 jelezte, hogy a project.json-ben nincsen runtime section és net452 framework support, majd elküldöm, ha hazaérek.

Fuszenecker Róbert

Rpi-n 4%-ot gyorsult a módosítás.

Hát ez nagyon érdekes.

x86_64:
-------
C: 6.48 ms/piece
.NET Core: 9 ms/piece.

Most vagy nagyon dolgozott a MS a JIT-en, vagy Saxus kolléga optimalizációi ennyit jelentenek.

Fuszenecker Róbert

P.S. dotnet run -c Release

Hát. Írtam, hogy nálam mi mennyit jelentett.

(Ezt most a makefile-jal, azaz az mcs-sel fordítottad?)

----------------
Lvl86 Troll, "hobbifejlesztő" - Think Wishfully™

Nem, ez .NET Core 1.1

A dotnet run -c Release paranccsal.

Meglepődtem, mert ez a másfélszeres szorzó gyakorlatilag ugyanaz, mint Java esetén.
Jók már ezek a mai JIT-ek. Nihil novi sub sole :-)

Fuszenecker Róbert

Ezt egyébként min tesztelted?

Csak mert nekem ez jön ki:

Total (1000): 298
1000 piece(s) of 4096 pt FFT;  0,298 ms/piece

(i5-2320, W10, .NET 4.6.1, optimalizált fordítás)

----------------
Lvl86 Troll, "hobbifejlesztő" - Think Wishfully™

Egy döglődő laptopon. Nemsokára megjön a rPi-m, szerintem teljesítményben versenyre kelhet :-)

Fuszenecker Róbert

Nagyjából emiatt érdemes használni Githubot, Bitbucketet vagy bármi hasonlót: lehet normális felületen követni a dolgokat és nem emailezni kell, mint a kőkorszakban megrekedtek.

Meg további előnye, hogy lehet egyszerűen hozzáfűzni kommentet a PR-hez, illetve, ha ott fixálsz valamit, amit megkifogásolnak, akkor szépen lecseréli a kódot, áttekinthető módon, stb.

----------------
Lvl86 Troll, "hobbifejlesztő" - Think Wishfully™

Igen, a többi feature-t ismertem, de ez a "kilopom a PR-t a másik repóból" dolgot még sosem csináltam.
Mindig tanul az ember.

Fuszenecker Róbert

Egyébként most nézem: nem ugyanazt csinálja a C#-os kód, mint a C-s kód. A C-s kód egy paraméterül kapott tömbbe pakolja az eredményt, míg a C#-os visszaad mindig egy újat. Ez még 10%-ot hozott.

----------------
Lvl86 Troll, "hobbifejlesztő" - Think Wishfully™

Ha így haladsz, estére lenyomod a C-s mintakódot ;-)

Fuszenecker Róbert

Nem probléma, utána írhatja assembly-ben. :)


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

Parallel.ForEach() -> tada.wav ;)

----------------
Lvl86 Troll, "hobbifejlesztő" - Think Wishfully™

Hat igen, de az már nem ugyanazt csinálja, mint az eredeti C implementáció.

Egy ideig gondolkodtam egy GPU-s megvalósításon, mert a DFT egy mátrix-vektor szorzás, ugye, ahhoz meg a GPU nagyon ért, de az már alma-körte lenne ebben a kontextusban.

Fuszenecker Róbert

Látom, megjelent az unsafe is.
Külön engedélyezni kellett a .NET Core buildben.

Fuszenecker Róbert

Bocs, az nem volt szándékos, véletlen benne felejtettem a kódban. Kísérletezgettem egy picit az unsafeal is.

----------------
Lvl86 Troll, "hobbifejlesztő" - Think Wishfully™

Nem baj, szerintem maradhat.
Én egyszer néztem meg safe vs. unsafe beállításokkal, nem tapasztaltam sok performancia-különbséget, ezért meghagytam safe-ben.
Már bent van a PR.

Nem tudom, VS2015-ben lefordul-e, mintha ott az lenne beállítva targetként, hogy a project.json alapján fordítson, ezt majd lehet, hogy visszacsinálom klasszikus C# projektté. Az a baj, ha a VS észreveszi, hogy van project.json, egyből konvertálja .NET Core projektté, akkor is, ha igazából 2 build rendszert akarsz párhuzamosan használni. Ez nem igazán életszerű, kivéve most, amikor performanciát mérünk.

Fuszenecker Róbert

Nem, én is egy külön projektben szerkesztgettem a .cs fájlt. Önmagában az unsafe keyword nem csinál semmit, főleg nem ad a JIT-ternek semmi extrát. Az csupán ahhoz kell, hogy használhass pointereket is. Amivel még kísérletezgetni lehet esetleg itt-ott az az unchecked, de az sem kifejezetten performance miatt lehet érdekes, hanem, hogy ne dobjon exceptiont, ha elvárt/kívánt viselkedés az under/overflow, pl.

----------------
Lvl86 Troll, "hobbifejlesztő" - Think Wishfully™

Unchecked-ez akartam írni, csak nem sikerült :) Érdekes, mert F#-nál volt különbség, de ez adódhat abból, hogy ott a checked implementáció overloadolja a nem checked-et.

Ha megjön az rpi-m, újramérem az arányt.

Fuszenecker Róbert

Nna. Ha kicsit egészségesebb leszek, megpróbálom ráereszteni a Xilinx SDSoC-t (módosítás nélkül).

Jól sejtem, hogy hardware-ből akarod megcsinálni? :D Ha igen, az a gyanúm, a te megoldásod lesz a leggyorsabb. :)


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

Annyira azért nem, mert csak rá fogom ereszteni a szoftvert, hogy "nesze, ebből a függvényből csinálj hardvert", aztán meglátjuk, mi lesz. Sokat nem várok.

Ez érdekes, várom az eredményt. :)