Líné GNU MP (Knihovna pro velká čísla)

BubikBelze

Líné GNU MP (Knihovna pro velká čísla)
« kdy: 26. 12. 2017, 19:25:09 »
Ahoj,

počítám různé hodnoty pomocí GNU MP a běží to asi 20x pomaleji, než by mi bylo milé.

Provedl jsem instalaci apt-get install libgmp10 a libgmp-dev

Kód: [Vybrat]
libgmp-dev/unstable,now 2:6.1.2+dfsg-1.1 amd64 [installed]
libgmp10/unstable,now 2:6.1.2+dfsg-1.1 amd64 [installed]
libgmpxx4ldbl/unstable,now 2:6.1.2+dfsg-1.1 amd64 [installed,automatic]

Překlad jedu normálně gcc s parametrem -lgmp
#include <gmp.h> 


  • Hodnoty mám uložené uvnitř: mpz_t
  • Když to jde, používám funkce _ui (dlouhé číslo * 6) místo (dlouhé číslo * dlouhé číslo)
  • Nepočítám nic, co počítat nemusím.
  • Pro výpočty používám stejné globální proměnné.
  • Zkoušel jsem nahradit mpz_init za mpz_init2(prom, délka) a další kraviny (static, atd.).
  • Vyházel jsem všechny zbytečné výpočty

A stejně to je zatraceně líné!! :-\
Vyřešil jsem problém se zasekáváním CPU na Ryzenu, ale při té příležitosti jsem udělal další testy a zjistit, jak moc líné to je. Počítám tisíce a tisíce opakujících se výpočtů, které na sebe bohužel navazují.
Padají mi z toho 256bitová celá čísla.

Pro ilustraci:
Za dobu několika málo vynásobení deseti čísel v GNU MP stihnu spočítat 22 MD5 součtů vstupních dat a ověřit, že mi to došlo v pořádku. To mě rozbilo! Protože výpočet MD5 není právě jednoduchý a já používám svojí upravenou verzi pro snazší žvýkání, která není nijak optimalizovaná a je vlastně jen tak naprasená, přesto výpočetně poměrně náročná.

Cvičně jsem zkusil číslo vynásobit ručně - rozložené registrech - a je to fofr!
Zato s GNU MP to je neuvěřitelně líné.

Budu rád za jakékoliv tipy.
Tak nevím, co dělám blbě ::)

Jestli máte s optimalizací GNU MP nějaké zkušenosti, budu moc rád, pokud mi poradíte, co zkusit.
Nezkoušel jsem překládat vlastní verzi knihovny GNU MP, oni tam píšou, že by to nemělo být až tak nutné.


Tomas2

  • ****
  • 310
    • Zobrazit profil
    • E-mail
Re:Líné GNU MP (Knihovna pro velká čísla)
« Odpověď #1 kdy: 26. 12. 2017, 20:05:01 »
bohužel, kdysi stejné zkušenosti, používáme fortan s modulem fmzm, líp neporadím.

BubikBelze

Re:Líné GNU MP (Knihovna pro velká čísla)
« Odpověď #2 kdy: 26. 12. 2017, 20:35:16 »
Já si myslím, že něco dělám blbě.  ::)  :(

Franta <xkucf03/>

Re:Líné GNU MP (Knihovna pro velká čísla)
« Odpověď #3 kdy: 26. 12. 2017, 21:10:56 »
Když ale neukážeš kód, tak ti těžko někdo poradí. Doporučuji někde zveřejnit relevantní část kódu a napsat do e-mailové konference GNU MP.

BubikBelze

Re:Líné GNU MP (Knihovna pro velká čísla)
« Odpověď #4 kdy: 26. 12. 2017, 22:00:23 »
Pro překlad je nutné dát nejprve:
Kód: [Vybrat]
apt-get install libgmp-dev  (někde i libgmp10)
Překlad:
Kód: [Vybrat]
gcc -o test test.c -lgmp
A maximálně ořezaný kód:

Kód: [Vybrat]
// Minimalni include
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>   
#include <gmp.h>

// Pro mereni casu od oka
struct timeval stop, start;

//  Gnu MP
// Definice cisel
mpz_t test,test1,test2,test3,test4,test5;

//Testovaci funkce vycucana z prstu, pouzite funkce jsou ty, co se pouzivaji v kazdem pruchodu
void ImplS()
    {
   
      gettimeofday(&start, NULL);
     
      mpz_set_ui(test5, 64);
      mpz_mod(test3,test1,test2);
      for (int x=0;x<200;x++)
      {           
      if (mpz_cmp_ui(test3,1) == 0) { printf("Chyba ImplS"); exit(1);}
      mpz_div(test3,test2,test5);
      mpz_mul (test, test1, test3);
      mpz_sub_ui (test, test2,2);
      }
     
      gettimeofday(&stop, NULL);   
      printf("Doba trvani %lu\n", stop.tv_usec - start.tv_usec);
                       
    }

     
int main ()
          {         
          mpz_init (test);
          mpz_init (test1);
          mpz_init (test2);
          mpz_init (test3);
          mpz_init (test4);
          mpz_init (test5);
           
          //Nastavim si nejake hodnoty, jen tak
          mpz_set_str(test1, "98026498413065498413061649849130659574916061649749846510016498844622159884961", 10);
          mpz_set_str(test2, " 8412168943211616954984651120065198498461313216256168884462132320656498449848", 10);
          ImplS();         
       
         return 0;
         }

Mě to dává hodnoty 22-28 a při stejném měření času za stejnou dobu provedu 20 až 25 součtů MD5, včetně přípravy dat a vyhodnocení :-(


BubikBelze

Re:Líné GNU MP (Knihovna pro velká čísla)
« Odpověď #5 kdy: 26. 12. 2017, 22:20:50 »
Doplním, že jsem napsal dosti hrubé prototypy stejných funkcí (bez řešení přetečení, znaménka atd.), nicméně funkční pro základní sady čísel a jelo to rychlostí blesku. Ale asi určitě nechci přepisovat knihovnu GNU MP :(  :-\

Neviditelný

Re:Líné GNU MP (Knihovna pro velká čísla)
« Odpověď #6 kdy: 26. 12. 2017, 23:15:07 »
Pokud si zvednu počet otáček cyklu na 20M, běží mí to na SNB i7 nějaké 2 sekundy. Obávám se, že GMP je psaná příliš univerzálně a "ruční" implementace pro konkrétní případy budou znatelně rychlejší. Ryzen k dispozici nemám, ale GMP je prošpikovaná kousky kódu v assembleru pro všechny možné architektury. Není možné, že na Ryzenu nefunguje správně autodetekce podporovaných instrukcí a používá se nějaká generická varianta, která je fakt znatelně pomalejší?

Joshua

Re:Líné GNU MP (Knihovna pro velká čísla)
« Odpověď #7 kdy: 26. 12. 2017, 23:17:35 »
256 bitove čísla sú fakt malé na gmp a gmo na neho nieje optimalizovane. Čo tak použiť boost multiprecision?

http://www.boost.org/doc/libs/1_57_0/libs/multiprecision/doc/html/boost_multiprecision/tut/ints/cpp_int.html

BubikBelze

Re:Líné GNU MP (Knihovna pro velká čísla)
« Odpověď #8 kdy: 26. 12. 2017, 23:36:20 »
256 bitove čísla sú fakt malé na gmp ... Čo tak použiť boost multiprecision?

Aha, no pro mě je 256 bitové číslo celkem velké :-D
Já se snažím držet C99 a tohle je C++ ::) nevím, jestli se mám bát.
No pokud bych si měl vybrat mezi "naučit se C++" nebo "udělat si vlastní GNU MP", no...
(Celé jádro projektu je v C99 a jak to zmixovat...přepsání nepřichází v úvahu...ach jo.  :-\ )
Rozhodně děkuji za radu! Minimálně zkusím použít těch pár funkcí a uvidím, jak vychází časově.

generická varianta, která je fakt znatelně pomalejší?

Zkusím si opravit virtualko a pustit to na něm. No kdyby byl výsledek 5-8usec, budu si hrát s optimalizací instrukcí, takhle se obávám, že z 25 asi 3 neudělám :-( Nicméně to zkusím, máš pravdu.

....ach jo lidi...

Jádro programu je násobení, dělení, sčítání a odčítání.
Přepsat tyhle funkce na AVX/FMA bych si troufl.
Jenže já tam potřebuju počítat i modulo, což je komplexní smyčka a odmocninu.

Karacubu jsem implementoval, ale udělat efektivně i dělení, poskládat z toho modulo, pak i odmocninu atd...  :-[ :'(
UF!  :-[

Jsem doufal, že mi napíšete "Jsi kokot, měl jsi zapnout přepínač -lgmp -fast" a tím by to běželo super rychle :-D
Přesněji řečeno jsem myslel, že jsem GNU MP v něčem nepochopil, něco dělám špatně a proto je to líné.
To, že je línější celé GNU MP z nějakého důvodu, to je horší varianta :-D

Neviditelný

Re:Líné GNU MP (Knihovna pro velká čísla)
« Odpověď #9 kdy: 27. 12. 2017, 00:29:03 »
Tenhle benchmark tě bude zajímat: https://bluescarni.github.io/mppp/benchmarks.html

Ten tvůj zkušební kód přepsaný s mp++ běží přeložený s -Ofast skoro 2x rychleji než ten Cčkový.

BubikBelze

Re:Líné GNU MP (Knihovna pro velká čísla)
« Odpověď #10 kdy: 27. 12. 2017, 00:44:18 »
kód přepsaný s mp++ běží skoro 2x rychleji než ten Cčkový.

Děkuju za info a čas! Nicméně já na C++11 nejsem a hlavně zlepšení 2x je málo, potřebuji tak 10x.
Asi mi nic jiného než AVX/FMA nezbude.