C++ fordító Win64-re int128 támogatással
2008-09-10T15:14:07+02:00
2008-09-16T01:07:08+02:00
2022-07-25T21:12:32+02:00
  • Most, hogy újra 64 bites oprendszer közelében vagyok, ki tudtam próbálni az említett dolgokat.

    Először is polyJoe javaslatára megírtam magamnak a 128 bites aritmetikát az MSVC kedvéért. Nem igazán törődtem az optimalizálással, így is került bele pár bug amit kb. egy óra debugolással találtam meg. A lényeg, hogy 1-2% teljesítményromlást okozott csak ez a csel a GCC-hez képest (lásd lentebb), ami szerintem elfogadható. (Ha van int128 típus, akkor persze azt használja a kód, nem a sajátomat.)

    Letöltöttem az ICC trial változatát is. Nagy sajnálatomra a 64 bites fordítója nem ismerte fel az __int128 kulcsszót (_int128 és int128 formában sem), szóval ugyanazt a kódot kellett használnom, amit az MSVC kedvéért írtam. Annyival volt jobb az MSVC-nél, hogy legalább inline assemblyt hagyott volna használni, de már nem volt lelkierőm emiatt egy harmadik változatot írni. A végeredmény az MSVC kódjánál gyorsabb, de a GCC kódjánál egy hajszálnyit még mindig lassabb kód lett. Persze akármilyen jól is optimalizál, az idő 80%-ában az én kézzel írt ASM kódom fut, amihez nem nyúlhat.

    Gregoriusnak igaza volt: az OpenSSL tényleg konstans idő alatt futó algoritmusokat használ alapesetben. A tisztességes összehasonlítás végett átírtam egy kicsit a kódját, hogy a gyorsabb, nem konstans idejű algoritmusokat használja. Ez gyorsított valamennyit, de nem annyit, hogy teljesen utolérje vele az én kódomat. (4096 bitnél a gyorsulás kb. 5%, 114.85 ms-ről 108.6 ms-re 32 biten).

    Az időeredmények az én gépemen (AMD Sempron 2800+, órajel: 1600 MHz):
    64 bit
    saját kódom (MSVC): 0.4234 ms kódolás, 33.28 ms dekódolás
    saját kódom (ICC): 0.4203 ms kódolás, 32.97 ms dekódolás
    saját kódom (GCC): 0.4141 ms kódolás, 32.70 ms dekódolás
    OpenSSL (MSVC): 0.649 ms kódolás, 42.43 ms dekódolás

    32 bit
    saját kódom (MSVC): 1.3360 ms kódolás, 100.84 ms dekódolás
    OpenSSL (MSVC): 1.64 ms kódolás, 109.37 ms dekódolás

    Mindegyik érték 4096 bites kulcshosszra vonatkozik, és három mérés átlaga. Időmérés közben csak egy Total Commander és egy Jegyzettömb futott a program mellett, az egeret nem mozgattam. A 64 bites OpenSSL értékek gyengébbek a lehetségesnél, mert a Win64-es változat még nem teljesen stabil, és nem tartalmaz ASM kódot.

    Köszönöm mindenkinek a segítséget. Úgy látszik, bele kell törődnöm, hogy a 128 bites számok támogatása nem általános dolog AMD64 platformon, legalábbis Windows alatt nem. Még jó, hogy átkerült a topik a Társalgóba, mert most gondban lennék, ki kapja a pontot
    Mutasd a teljes hozzászólást!
  • Ilyen topikok olvasásakor érzi úgy az ember, hogy nem tud semmit


    Írj egy diplomamunkát a hosszú számokon végzett aritmetikáról, rögtön vágni fogod a témát
    Mutasd a teljes hozzászólást!
  • Az implementációm kb. 10-15 százalékkal gyorsabb az OpenSSL-nél a saját gépemen. Persze annyira nincs nagy arcom, hogy azt gondoljam, hogy leköröztem az OpenSSL-t író embereket, inkább csak arról lehet szó, hogy egy: az én kódom kevésbé általános, és alig van benne hibaellenőrzés, kettő: az én kódomat csak két AMD gépen teszteltem, lehet, hogy az x86 architektúrákon átlagosan nézve az OpenSSL a gyorsabb.

    A kutyuli ott van elvermelve, hogy a jobb minőségű RSA algoritmusoknak azon túl, hogy gyorsaknak kell lenniük, még arra is ügyelniük kell, hogy bármilyen bemenetre ugyanannyi idő alatt adjanak választ (ugyanannyit számoljanak, ugyanannyi teljesítményt vegyenek fel, stb). Vagyis egy meghatározó kompromisszum van a sebesség és a biztonság között. Ott van például a gyorshatványozás: az algoritmus (szorzás az alappal vagy négyzetre emelés az exponens megfelelő bitjének függvényében) futási sebességéből következtethetsz az exponens tartalmára. Kellően furfangos esetben bitenként lépésről lépésre megfejthető a kulcs.
    Mutasd a teljes hozzászólást!
  • Gratulálok, szerintem büszke lehetsz rá, ez nagyon szép eredmény, főleg egy diplomamunkától!

    Köszi szépen. Azt mondjuk nem tudom elképzelni, hogy valami olyat csináltam volna, amire az OpenSSL-es fiúk nem gondoltak, szóval valami csel lesz a dologban. Majd lehet, hogy összemérem a GMP-vel is, de gondolom a bolygó leggyorsabbját úgyse verem meg

    Beleolvastam a doksijába: a szorzáshoz négyfajta algoritmus közül, a számok mérete alapján dönti el, hogy melyiket használja: (Basecase, Karatsuba, Toom-3, FFT) Elég durvának tűnik!

    A Karatsubát én is próbáltam implementálni, de sehogy se sikerült vele megverni a Basecase algoritmust 4096 biten és alatta. Erősen architektúra-függő, hogy milyen hossztól éri meg a Karatsuba (a szorzás és összeadás közti sebességkülönbség dönti el), valószínűleg ezen a procin csak hosszabb számra érné meg. A másik kettőről előre tudtam, hogy az én hossztartományomban nem fognak kifizetődni.
    Mutasd a teljes hozzászólást!

  • Ilyen topikok olvasásakor érzi úgy az ember, hogy nem tud semmit
    Mutasd a teljes hozzászólást!
  • Az implementációm kb. 10-15 százalékkal gyorsabb az OpenSSL-nél a saját gépemen.


    Gratulálok, szerintem büszke lehetsz rá, ez nagyon szép eredmény, főleg egy diplomamunkától!

    Én azt olvastam valahol, hogy a GMP durvábban van optimalizálva, mint az OpenSSL.
    A GMP honlapján az olvasható, hogy a bolygó leggyorsabb nagyszám könyvtára. Beleolvastam a doksijába: a szorzáshoz négyfajta algoritmus közül, a számok mérete alapján dönti el, hogy melyiket használja: (Basecase, Karatsuba, Toom-3, FFT) Elég durvának tűnik!
    Mutasd a teljes hozzászólást!
  • El van nézve

    Ezen a gépen nincs 64 bites Windows, szóval majd vasárnap délután tudom érdemben megnézni az ICC-t meg a longnum könyvtárak 64 bitre fordítását. Majd ide is megírom, mire jutotam.
    Mutasd a teljes hozzászólást!
  • Tevedes: En nem ertettem mit csinalsz, es nem lattam, hogy pontosan mitol gyorsulna fel barmi is, hogy 64bit-re valt... ebben az esetben valoban van legjogosultsaga. Hangnemhez annyit fuzok hozza, hogy szkeptikus vagyok a prog.hu-n kommentelokkel kapcsolatban, nagyon ritka az aki valoban valami ertelmeset csinal es nem a Q3 forrasat probalja leforditani mingw-vel kezdeti C-tanulasi projekt gyanant. Valoban kioktato voltam, elnezesed kerem.
    Mutasd a teljes hozzászólást!
  • cad:
    Nezd adtunk tampontokat, innentol neked kell pontosan utananezned. Forditokat is kaptal, amelyek tudnak kezelni 128bites primitiveket, tobbet nem tehetunk.


    A támpontokat köszönöm, a kioktatást nem. Volt egy egyszerű kérdésem, szépen elmagyaráztam mi van, kértem segítséget. Te úgy gondoltad, hogy nem értem, mit csinálok, ezért elmagyaráztam. Innentől szerintem már csak arra megy ki a játék, hogy te bizonygatod, hogy én nem értek hozzá. Pl. rámutatsz, hogy vannak integer SSE2 műveletek, az pedig nem tűnik fel, hogy én is említettem egy ilyet (PMULUDQ). Ha azt akarod hinni, hogy én nem értek hozzá, hát hidd nyugodtan, de szerintem nem érdemeltem ki a kioktató hangnemet. Részemről ennyi.

    nadamhu:
    Köszi, ezek szerint mégsem (teljesen) bennem van a hiba, valaki azért meg tudta érteni, hogy miről beszélek. A bignum műveleteim már megvannak, 64 bites változatban is, csak nem vagyok megelégedve vele, hogy alfa verziójú fordítóval tudom csak normálisan lefordítani. Az implementációm kb. 10-15 százalékkal gyorsabb az OpenSSL-nél a saját gépemen. Persze annyira nincs nagy arcom, hogy azt gondoljam, hogy leköröztem az OpenSSL-t író embereket, inkább csak arról lehet szó, hogy egy: az én kódom kevésbé általános, és alig van benne hibaellenőrzés, kettő: az én kódomat csak két AMD gépen teszteltem, lehet, hogy az x86 architektúrákon átlagosan nézve az OpenSSL a gyorsabb. Azért én elégedett vagyok, hogy mégis megközelítettem egy profi lib sebességét.

    _psc_reloaded:
    Aha, de! Ha jól értettem a problémádat, az a gondod, hogy 64 bites inteket ha összeszorzol az eredmény 128 bites int lesz, és azt nem tudod tárolni, mert nincs normális fordító/támogatás int128 -ra.

    Jól érted a problémát
    A linkelt bignum libek forrásában nézném meg, hogy hogy oldják meg ott a srácok. Mi ez, ha nem tanulási folymat?

    Ez tényleg jó ötlet, megnézem. Remélem nem az sül ki, hogy a 64 bites működéshez int128 típust használnak azok is, mert akkor visszajutok a startmezőre.
    Ha jól értettem, a adiplomamunka témája az RSA kódolás, nem pedig a bignum-ok kezelése. Tehát -szigorúan szvsz- simán beleférhet, hogy a bignum kezelésre egy kész bignum libet használsz, s a többi algoritmust, a lényeget, az RSA-t magad implementálod.

    Ezzel igazából az a gond, hogy az RSA kódolás nagyon egyszerű, ha már van alatta egy bignum könyvtár. Amikor még csak próbálgattam a szárnyaimat, az NTL nevű bignum könyvtárat használtam a saját funkcióim ellenőrzésére. NTL-lel kb. 3 sor egy RSA kódolás, és ugyanennyi a dekódolás: mindkettő moduláris hatványozás. Ha nem magamnak írom a bignum részt, akkor gyakorlatilag nem írok semmit. Na meg aztán a témám a hosszúszám aritmetika, nem a kriptográfia, bár ezt előbb kellett volna tisztáznom, elnézést kérek.
    Mutasd a teljes hozzászólást!
  • En azt ertettem, de mivel itt azert irja at, hogy gyorsabb legyen akkor az nem tul elonyos, ha a platform nem bir ilyen dolgokkal szamolni nemde? ;) De azota ezen mar tuljutottunk, mert nem arra volt szuksege amire en gondoltam.
    Mutasd a teljes hozzászólást!
  • Nem tudom:) De itt egyértelműen a fordítóra vonatkozott a dolog.
    Mutasd a teljes hozzászólást!
  • Ertem, es akkor hogy nevezned azt az utasitas szintu szetvalasztast, amikor pl 64bites szamokkal dolgozunk egy XMM regiszterbe vagy 32bitessekkel.
    Mutasd a teljes hozzászólást!
  • tud 128 bites szamokat primitiv tipuskent kezelni", mert ilyet egyik IA-32, Intel 64 vagy IA-64es architektura sem tud.

    primitív típust kezelni csak nyelvek, illetve fordítók tudhatnak, az architektúráknak IA-32, Intel 64, IA-64, semmi de semmi köze a primitív típusokhoz.
    Mutasd a teljes hozzászólást!
  • gyébként ha nem használsz bignum stuffot (akár egy készen levőt, akár sajátot, mindegy)


    Bár semmi közöm hozzá, de beleokoskodok én is:

    - Számomra teljesen nyilvánvaló az eddigiekből, hogy Csaboka természetesen ír saját bignum libraryt. Erről szól az egész.
    - Szerintem pont a bignum library írás a diplomamunkájának lényege. Szerintem nagyon jó kis téma, sokat lehet belőle tanulni alacsonyszintű optimalizálásról. Majd ráér egész életében mindenre csak third party libeket használni, (és végül teljesen elfelszínesedni, mint a legtöbb programozó) Amíg tanul az ember, legalább addig csináljon már meg dolgokat maga is, ezzel lehet tanulni a legtöbbet! Ki tudja, lehet, hogy Csaboka bignum library-je már most gyorsabb, mint némelyik azok közül, amelyek open source az interneten vannak. (néha az open source minősége, hmm...)
    - Hirtelen én sem nem látom át, hogy hogy hogyan lehet jól párhuzamosítani a bignum műveleteket, (SSE stb...) ha már ezt ajánlottátok, akkor erről írhatnátok, mert eddig hasznos tanácsot nem sokat adtatok, bocs, de annál többet kötekedtetek, főleg cad...
    Mutasd a teljes hozzászólást!
  • Nezd adtunk tampontokat, innentol neked kell pontosan utananezned. Forditokat is kaptal, amelyek tudnak kezelni 128bites primitiveket, tobbet nem tehetunk.

    Mire megyek én lebegőpontos számokkal? Nekem nem szabad, hogy csonkoljon vagy kerekítsen bármit is. Nekem 64 bit mantissza és 0 bit karakterisztika kell.


    Ne csinald mar kerlek. Nezz mar utana, SSE2-tol integer muveletek is vannak. Reszemrol nem tudok mar ehez tobbet hozzafuzni.

    Mondtunk forditot, letoltod, kiprobalod aztan kiderul, hogy megfelelo-e vagy sem. Aztan ha megvan az eredmeny, orommel varjuk, hogy bevalt-e vagy sem, hogy ha esetleg mas is ilyen helyzetbe kerul mar legyenek eredmenyek.
    Mutasd a teljes hozzászólást!
  • Ha ezt csinálnám, utána mit írnék a diplomamunkámba? "Célom a hosszúszám aritmetika megismerése volt az RSA algoritmus implementációjával. Célomat úgy értem el, hogy meghívtam ezt a 3 darab függvényt ebből a hosszúszám könyvtárból. Ezalatt a következőket tanultam: semmit. Köszönöm."


    Aha, de! Ha jól értettem a problémádat, az a gondod, hogy 64 bites inteket ha összeszorzol az eredmény 128 bites int lesz, és azt nem tudod tárolni, mert nincs normális fordító/támogatás int128 -ra.
    A linkelt bignum libek forrásában nézném meg, hogy hogy oldják meg ott a srácok. Mi ez, ha nem tanulási folymat?
    Továbbmegyek: ezt az egészet nem fogod megúszni anélkül, hogy ne írj egy saját bignum libet. Ehhez is jó kiindulási pont megsasolni, hogy hogyan csinálják a "profik". Ez nem plagizálás, nem kódlopás, hanem _taulás_. Megnézed, hogy kell csinálni, és megcsinálod magad - ha már ennyire nem akarsz egy kész bignum libet használni.
    Ha jól értettem, a adiplomamunka témája az RSA kódolás, nem pedig a bignum-ok kezelése. Tehát -szigorúan szvsz- simán beleférhet, hogy a bignum kezelésre egy kész bignum libet használsz, s a többi algoritmust, a lényeget, az RSA-t magad implementálod.
    Egyébként ha nem használsz bignum stuffot (akár egy készen levőt, akár sajátot, mindegy), akkor hogyan fogod kezelni a nagy prímszámokat? Hogyan fogod tárolni őket? Minden képp kel egy ilyen lib. Ha meg van, akkor nem értem a problémát, hisz ezek implementálják az aritmetikai műveleteket is, így akár 2048 bites számokat is össze tudsz velük szorozni, az eredmény megy egy 4096 bites szám lesz, amit szintén egy bignum típus tárol...
    Mutasd a teljes hozzászólást!
  • Hajjaj, kezdem egyre hülyébben érezni magam. Remélem, csak rosszul magyaráztam, és nem tényleg hülyeséget csinálok...

    Nem megoldható, hogy megírd az int128 típus műveleteit? Mármint asm-rutinokkal. Azt már tudod C-ből használni.

    Éppen megoldható lenne, csak mivel a 64 bites Visual C++ az inline assembly-t se támogatja, kénytelen lennék külön eljárásként megírni őket. Minden alkalommal, amikor műveletet végeznék, plusz idő lenne az eljáráshívás és a visszatérés. Bár most hogy mondod, ez talán nem lenne olyan nagy gond, mert a C++ -os kódok úgyis csak az idő elenyésző részében futnak (az idő kb. 80%-át 3 assembly rutin futása teszi ki). Ezt ki fogom próbálni.

    Szamomra nem derult ki, hogy pontosan mit szeretnel kezdeni a 128bites adatszerkzettel, kivaltkepp a "tud 128 bites szamokat primitiv tipuskent kezelni", mert ilyet egyik IA-32, Intel 64 vagy IA-64es architektura sem tud.

    Nem azt mondtam, hogy az architektúra tudja kezelni a 128 bites számokat. Azt mondtam, hogy a fordító tudja kezelni a 128 bites számokat primitív (=nem összetett) típusként. És egyszerűen arra kell, hogy ha mondjuk összead két int64-et a kódom, akkor tudja valamiben tárolni, amiben a carry sem veszik el. Ha pedig osztásról van szó, akkor az algoritmusnak tudnia kell int128-at osztani int64-gyel (azaz az AMD64-es DIV utasítás megfelelőjét).

    itt pedig eleg jol kihasznaljatok ezeket a dolgokat, SSE, SSE2 stb. eleg jo tamogatast nyujt ilyen jellegu dolgokhoz.

    Igazából én nem látom, hogy lehetne jól párhuzamosítani ezeket a műveleteket SSE-vel vagy SSE2-vel. Mindig fellép valamilyen carry, amit fel kell használnod a következő lépésben. Talán a hagyományos szorzásnál lehetne két "sort" párhuzamosan szorozni PMULUDQ-val 32 biten, de valószínűleg több macera lenne azzal, hogy az adatokat a megfelelő formára hozd a regiszterekben, mint ami még megéri. Más szavakkal: vagy elvégzel egy szorzást 3 órajel alatt, vagy elvégzel kettőt ugyanennyi idő alatt, aztán még 3-4 órajelet töltesz azzal, hogy szétválogasd, mi hova megy tovább. Ez sajnos nem multimédia, itt a részeredmények függenek egymástól.

    PS: IA-32-es rendszerek is kepesek 64bites szamokkal dolgozni, lasd SSE muveletek, amikor is pl ket 64bites lebegopontos szamon vegzik el parhuzamosan ugyan azt a muveletet. Ha ugy vesszuk akkor 128biten vegeznek muveletet, egyszerre.

    Mire megyek én lebegőpontos számokkal? Nekem nem szabad, hogy csonkoljon vagy kerekítsen bármit is. Nekem 64 bit mantissza és 0 bit karakterisztika kell.

    Miért nem nézed meg, hogy csiálja a pl. bignum library a nagy számok kezelését?
    Ha minden igaz, abban van MMX/SSE támogatás is.
    sourceforge -on találsz kismillió nagyszám-kezelő library -t, minek írni egy n+1-ediket? Vagy a diplomamunkában nem szabad külső libet használni?

    Ha ezt csinálnám, utána mit írnék a diplomamunkámba? "Célom a hosszúszám aritmetika megismerése volt az RSA algoritmus implementációjával. Célomat úgy értem el, hogy meghívtam ezt a 3 darab függvényt ebből a hosszúszám könyvtárból. Ezalatt a következőket tanultam: semmit. Köszönöm." Most ne haragudj, de az egyetemen sokszor kell implementálnod olyasmit, amit előtted már millióan implementáltak, csak azért, hogy te is megértsd. Ha majd a való világban kell RSA, akkor fogok egy kész kriptográfiai libet és meg van oldva.

    Így nem hiszem, hogy a GCC windowos portja (a MinGW) kaki lenne. Próbáld a legfrissebb verziót!

    Hidd el, azt próbáltam. Ha nem hiszed, járj utána: itt a mingw-64 SourceForge oldala. A legfrissebb 32 bites és 64 bites MinGW-s változat nekem összeomlik az #include <iostream> láttán. A legfrissebb Cygwin-es valamivel régebbi, jelenleg azt használom, de az is internal compiler error-t dob, ha -g kapcsolóval próbálok fordítani. A Cygwin projekten belül pedig nem tudok róla, hogy 64 bites keresztfordítót is kiadnának. Elhiszem, hogy Linuxon nem kaki a GCC, de sajnos Windowson nem olyan rózsás a helyzet.
    Mutasd a teljes hozzászólást!
  • Igen, tipikusan a befektetett ido es az erte jarok sebessegnovekedes alapjan

    Itt a lényeg, a mai 8-core, 3 Ghz, 32Gb RAM világban én sem írnék már egy szem ASM kódot sem, ha azért elég gyorsra sikerül megírni a kódot egy magasabb szintű nyelvben. Már nem vadászunk egy-egy órajel-ciklusokra, egy-egy megspórolt byte-ra...
    Mutasd a teljes hozzászólást!
  • Igen, tipikusan a befektetett ido es az erte jarok sebessegnovekedes alapjan, nincs ertelme asm-ben kodolni. Persze nem taagadom, vannak hotspotok amik megfelelo tudassal kezzel jobban optimalizalhatoak, persze ehez valoban kiterjedt tudas szukseges.
    Mutasd a teljes hozzászólást!
  • icc11-et nem nagyon ismerem, lehet, hogy az már jó/jobb e téren, nem tagadom.
    icc9-cel valóban jobb eredményeket lehetett elérni, mint gcc-vel, bcc-vel (ez vicc:) ), msvc-vel, de még mindig jobb kódot tudott írni az ember kézzel MMX/SSE utasításokra.
    Persze ez valahol normális, hisz azért sokszor kell inteligencia is ahhoz, hogy az ember "meglássa", egy-egy algoritmust hogyan kellene átalakítani ahhoz, hogy párhuzamosan végezhessünk műveleteket számokkal.
    Mutasd a teljes hozzászólást!
  • Visual Studio -hoz ezt találtam:
    Handling Large Number in a Simple Way
    .NET Reference Guide

    Ez meg egy jó Arbitrary Precision Integer Arithmetic lib:
    http://spinning-yarns.org/michael/mpi/

    Ezt is érdemes:
    The GNU MP Bignum Library
    Mutasd a teljes hozzászólást!
  • Hat en most az icc11-et betateszteltem par honapig es az igen szep eredmenyeket mutatott vektorizacio teren, bar en leginkabb SSE / SSE2-ig hasznaltam ki ezeket a dolgokat, efelett nem nagyon voltak tesztesetek, ezek meg mar icc9-el is igen jo eredmenyeket ertek el, bar neha alakitani kellett a loop strukturan, hogy kepes legyen vektorizalni.
    Mutasd a teljes hozzászólást!
  • Miért nem nézed meg, hogy csiálja a pl. bignum library a nagy számok kezelését?
    Ha minden igaz, abban van MMX/SSE támogatás is.
    sourceforge -on találsz kismillió nagyszám-kezelő library -t, minek írni egy n+1-ediket? Vagy a diplomamunkában nem szabad külső libet használni?

    Ha MMX/SSE is érdekel, akkor gyúrj rá rendesen, mert én még olyan C fordítót nem láttam, ami rendesen kioptimalizálja/párhuzamosítja az aritmetikai műveleteket MMX/SSE részére. Ergo az MMX/SSE kódot általában asm-ben szokták megírni, nem bízzák a fordítóra.

    MinGW: nem tudom, hogy milyen verziók vannak mostanság forgalomban, de elvileg ez a GCC portja, és a legfrissebb GCC-t is szokták portolni. GCC-vel meg már több éve is fordítottam 64 bites FreeBSD-t, Gentoo -t. Így nem hiszem, hogy a GCC windowos portja (a MinGW) kaki lenne. Próbáld a legfrissebb verziót!
    Ha esetleg mégis kaki a MinGW, akkor próbáld a Cygwin -t, ez egy réteg a linuxos gcc és a windows között, kb. olyasmi, mint a wine, csak fordítva, és közel sem olyan bonyolult, bár némi lassulást biztos, hogy okoz. Viszont a programodat könnyebb platformfüggetlenre csinálni, mert megcsinálód úgy, ahogy Linuxon kéne, aztán windowson a cygwin felett fut.
    Mutasd a teljes hozzászólást!
  • Szamomra nem derult ki, hogy pontosan mit szeretnel kezdeni a 128bites adatszerkzettel, kivaltkepp a "tud 128 bites szamokat primitiv tipuskent kezelni", mert ilyet egyik IA-32, Intel 64 vagy IA-64es architektura sem tud.

    Ha ekkora adatokkal dolgoztok, akkor mindenkeppen elonyos a 64bit, ez vitathatatlan.

    Valaszt viszont megkaptad, ICC szemelyeben. Ha a sebesseg szamit, akkor azzal kell dolgoznod. Sajat tapasztalatom szerint jelentosen gyorsabb kodot general mint a gcc hasonlo optimalizacios feltetelek mellett, egyszeruen azert mert sokkal jobban vektorizal, itt pedig eleg jol kihasznaljatok ezeket a dolgokat, SSE, SSE2 stb. eleg jo tamogatast nyujt ilyen jellegu dolgokhoz.

    cl-el ha tamogatja, ha nem, nincs ertelme foglalkozni.

    PS: IA-32-es rendszerek is kepesek 64bites szamokkal dolgozni, lasd SSE muveletek, amikor is pl ket 64bites lebegopontos szamon vegzik el parhuzamosan ugyan azt a muveletet. Ha ugy vesszuk akkor 128biten vegeznek muveletet, egyszerre.

    PS2: harminc nap utan teljesen szabadon es jogosan lehet uj kulcsot igenyelni. Nem tudom mi a gond ezzel az opcioval, sott nem tartom elkepzelhetetlennek, hogy akademia celokra van ingyens lincensz.
    Mutasd a teljes hozzászólást!
  • Nem megoldható, hogy megírd az int128 típus műveleteit? Mármint asm-rutinokkal. Azt már tudod C-ből használni.
    Mutasd a teljes hozzászólást!
  • Namost itt ugy erzem sulyos felreertesek vannak. Eloszor is majd magyarazd el legszives, hogy pontosan miert varsz gyorsulast es pontosan mitol. Konkretan, peldakkal.


    Ezer örömmel. Konkrétan az RSA titkosítást és a hozzá való kulcsok generálását implementáltam, a véletlenszám-generáláson kívül teljesen saját kóddal. Ehhez ugye kell jó sok szorzás, négyzetre emelés és úgynevezett Montgomery-redukció művelet, mind hosszú (legalább 512 bites) számokon. Ezen műveletek implementációjához a CPU szorzó műveletét használjuk fel, vagyis egy lépésben akkora darabot tudunk szorozni a számból, amekkora a gépi szó hossza. A szorzások száma a használt számok gépi szóban mért hosszának négyzetével arányos.

    Itt jön be egy 64 bites processzor, mint pl. az én Sempronom. Két 32 bites szám szorzása 3 órajel, két 64 bites szám szorzása 5 órajel. Ha 64 bites darabokat szorzunk, és nem 32 biteseket, akkor feleződik a bemenet gépi szóban mért hossza, vagyis az algoritmushoz negyedannyi szorzás kell. Ezek a szorzások egyenként 5/3 annyi időbe kerülnek, mint a kisebbek, tehát a várható futásidő (5/3)*(1/4)=5/12-e lesz a 32 bitesének, kicsivel jobb, mint kétszeres gyorsulás.

    No és itt kezdődik a probléma is. A használt algoritmusok használnak olyan átmeneti eredményeket, amelyek két gépi szó hosszúak. Pl. a szorzásnál két 32 bites szám szorzata 64 bites lesz, amiből az alsó 32-t letároljuk, a felső 32 a carry. Teljesen analóg módon két 64 bites szám szorzata 128 bites, de ezt már nem tudom egy változóban eltárolni, ha a C++ fordítóm nem támogat 128 bites egészeket. A sebességigényes kód mind assemblyben van, úgyhogy ott nem gond, de nem akarnám a többi, C++ -ban írt kódot is átírni assemblyre csak azért, mert nem elég kompetens a fordító.

    Egyébként nem csak várom a gyorsulást, hanem már látom is, mivel már megvan az implementáció, ahogy mondtam az elején. A gyakorlatban a 64 bites kód durván háromszor gyorsabban végzi ugyanazt, mint a 32 bites kód.

    Addig is. A gepbe ugyan vannak (mar MMX ota) 64bites, es SSE kompatibilis procik ota 128bites regiszterek. De ezek tobbnyire azert vannak, hogy pl 4 32bites / 2 64bites stb adatszerkezeteket taroljanak (pl 2 double / 4 float stb.), ez nem jelenti, hogy hardveresen kepesek barmilyen 128bit szeles operaciot elvegezni


    Nem mondtam, hogy egy lépésben akarok 128 bittel számolni. A 32 bites procik se tudnak 64 bittel műveletet végezni egy lépésben, mégis tudnak a fordítók int64-et kezelni. Az összeadást/kivonást nagyon egyszerű két lépésre osztani (ADD/ADC vagy SUB/SBB), a szorzás is könnyű (két szorzásra és egy összeadásra bomlik), egyedül az osztás okoz nehézséget, de egy kis könyvtári rutinnal azt is meg lehet oldani. Igazán nem értem, a Microsoftnál miért nem vették a fáradságot...

    Ha mindenkeppen akarsz egy 128bites integer tipust, akkor keszits egyet. Ha ket 64bites vagy 4 32bites strukturakent osszerakod, akkor siman elkepzelheto, hogy a fordito (nem, nem cl.exe, ot felejtsd el ilyen szempontbol, ha aritmetikai sebessegrol beszelunk akkor icc) kepes lesz SSE2+/SSE3 kodot generalni beloluk.

    SSE-vel sem lehet egyszerre 128 biten műveletet végezni, de ahogy mondtam, ez nem is szükséges.
    Mutasd a teljes hozzászólást!
  • Namost itt ugy erzem sulyos felreertesek vannak. Eloszor is majd magyarazd el legszives, hogy pontosan miert varsz gyorsulast es pontosan mitol. Konkretan, peldakkal.

    Addig is. A gepbe ugyan vannak (mar MMX ota) 64bites, es SSE kompatibilis procik ota 128bites regiszterek. De ezek tobbnyire azert vannak, hogy pl 4 32bites / 2 64bites stb adatszerkezeteket taroljanak (pl 2 double / 4 float stb.), ez nem jelenti, hogy hardveresen kepesek barmilyen 128bit szeles operaciot elvegezni (illetve persze hogy kepesek, mert pl 2 64bites adatnak tekintik a regiszterbe levo bitsorozatot).

    Peldaul icc is tamogat 128bites integer tipust (__m128i), amely tartalmazhat 2 64bites, 4 32bites 8 16bites vagy 16 8bites adatot.

    Ha mindenkeppen akarsz egy 128bites integer tipust, akkor keszits egyet. Ha ket 64bites vagy 4 32bites strukturakent osszerakod, akkor siman elkepzelheto, hogy a fordito (nem, nem cl.exe, ot felejtsd el ilyen szempontbol, ha aritmetikai sebessegrol beszelunk akkor icc) kepes lesz SSE2+/SSE3 kodot generalni beloluk. Viszont ha mar itt tartunk, lehet eleg hamar elersz az expression templatekig is :).

    Szerintem kicsit eloreszaladtal, eloszor olvass el 1-2 HPC-s konyvet, tajekozodj MMX/SSE2+/SSSE3 teruleteken, mert szerintem olyan iranyba probalsz optmilaizalni amihez (meg) nem nagyon ertesz.
    Mutasd a teljes hozzászólást!
  • A leírások szerint ez fordít x86-64 platformra, bár azt nem tudom, hogy az int128-at tudja-e. Minden esetre az a 399 dollár kissé húzós egy diplomamunka kedvéért, azt meg nem akarom a dolgozatba írni, hogy a forrás szabad, és bárki lefordíthatja, de csak 30 napig jó a fordító...

    Azért köszi a szándékot
    Mutasd a teljes hozzászólást!
  • Azt nézted, hogy az intel C++ compiler tudja-e? (Egy időben ez a compiler fordította a leggyorsabb kódot x86, ra, ma már nem követem az eseményeket.)

    link

    (Bár nem ingyenes, de van trial verziója)
    Mutasd a teljes hozzászólást!
  • Akkor valószinűleg félreértettem...
    Mutasd a teljes hozzászólást!
abcd