Sovraccarico dell'uso dei bignum

Question

Ho riscontrato questo problema sull'opportunità di utilizzare i bignum nella mia lingua come tipo di dati predefinito quando sono coinvolti numeri. L'ho valutato io stesso e l'ho ridotto a una domanda di comfort e prestazioni. La risposta a questa domanda dipende da quanto è grande il risultato in termini di prestazioni nei programmi che non vengono ottimizzati.

Quanto è piccolo il sovraccarico dell'uso dei bignum nei punti in cui un numero fisso o intero sarebbe stato sufficiente? Quanto piccolo può essere nelle migliori implementazioni? Che tipo di implementazioni raggiungono il più piccolo overhead e che tipo di ulteriori compromessi si traducono in

Che tipo di hit posso aspettarmi dai risultati nelle prestazioni linguistiche generali se imposterò la mia lingua sui bignum?

Answer 1

Ad essere onesti, la risposta migliore è " provalo e vedi " ;.

Chiaramente i bignum non possono essere efficienti come i tipi nativi, che in genere si adattano a un singolo registro della CPU, ma ogni applicazione è diversa - se la tua non fa un intero carico di aritmetica intera allora l'overhead potrebbe essere trascurabile.

Answer 2

Forse puoi vedere come lo fa Lisp. Farà quasi sempre la cosa esattamente giusta e convertirà implicitamente i tipi quando sarà necessario. Ha numeri fissi ("interi" normali), bignum, rapporti (frazioni proprie ridotte rappresentate come un insieme di due numeri interi) e galleggianti (in diverse dimensioni). Solo i float hanno un errore di precisione e sono contagiosi, cioè una volta che un calcolo comporta un float, anche il risultato è un float. " Lisp pratico pratico " ha una buona descrizione di questo comportamento.

Answer 3

Vieni a pensarci bene ... Non credo che avrà molti successi nelle prestazioni.

Poiché i bignum per natura, avranno una base molto grande, diciamo una base di 65536 o più grande per la quale di solito è un valore massimo possibile per fixnum e interi tradizionali.

Non so quanto saresti grande la base del bignum, ma se la imposti sufficientemente grande in modo che quando viene usata al posto di numeri fissi e / o numeri interi, non supererebbe mai la sua prima cifra bignum quindi l'operazione sarà quasi identica ai normali fixnums / int.

Questo apre un'opportunità per le ottimizzazioni in cui per un bignum che non cresce mai sopra la sua prima cifra di bignum, potresti sostituirle con un'operazione a una cifra di bignum super veloce.

E poi passa agli algoritmi a n cifre quando è necessaria la seconda cifra bignum.

Questo potrebbe essere implementato con un flag di bit e un'operazione di convalida su tutte le operazioni aritmetiche, pensando approssimativamente, potresti usare il bit di ordine più alto per indicare il bignum, se un blocco di dati ha il suo bit di ordine più alto impostato su 0, quindi elaborali come se fossero normali fixnum / ints ma se è impostato su 1, quindi analizza il blocco come una struttura bignum e usa gli algoritmi bignum da lì.

Questo dovrebbe evitare hit di performance da semplici variabili iteratore di loop che penso sia la prima possibile fonte di hit di performance.

È solo il mio pensiero approssimativo, un suggerimento poiché dovresti sapere meglio di me :-)

P.S. scusate, ho dimenticato quali erano i termini tecnici di bignum-digit e bignum-base

Answer 4

la tua riduzione è corretta, ma la scelta dipende dalle caratteristiche prestazionali della tua lingua, che non possiamo conoscere !

una volta implementata la lingua, è possibile misurare la differenza di prestazioni e forse offrire al programmatore una direttiva per scegliere l'impostazione predefinita

Answer 5

Non conoscerai mai l'effettivo rendimento fino a quando non creerai il tuo benchmark in quanto i risultati varieranno per lingua, per revisione della lingua e per CPU e. Non esiste un modo indipendente dalla lingua per misurarlo, tranne per il fatto ovvio che un numero intero a 32 bit utilizza il doppio della memoria di un numero intero a 16 bit.

Answer 6

  

Quanto è piccolo il sovraccarico dell'uso dei bignum nei punti in cui un numero fisso o intero sarebbe stato sufficiente? Mostra piccolo può essere nelle migliori implementazioni?

La cattiva notizia è che anche nella migliore implementazione software possibile, BigNum sarà più lento dell'aritmetica incorporata per ordini di grandezza (cioè tutto dal fattore 10 al fattore 1000).

Non ho numeri esatti ma non credo che i numeri esatti possano essere di grande aiuto in una situazione del genere: se hai bisogno di numeri grandi, usali. Altrimenti no. Se la tua lingua li utilizza per impostazione predefinita (quale lingua fa? Alcune lingue dinamiche fanno ...), pensa se lo svantaggio di passare a un'altra lingua è compensato dal miglioramento delle prestazioni (che dovrebbe raramente essere).

(Che potrebbe essere approssimativamente tradotto in: c'è un'enorme differenza ma non dovrebbe importare. Se (e solo se) è importante, usa un'altra lingua perché anche con la migliore implementazione possibile, questo la lingua evidentemente non è adatta per il compito.)

Answer 7

Dubito totalmente che ne varrebbe la pena, a meno che non sia molto specifico del dominio.

La prima cosa che viene in mente sono tutti i piccoli punti per i cicli nei programmi , le piccole variabili iteratrici saranno tutte bignum? È spaventoso!

Ma se la tua lingua è piuttosto funzionale ... forse no.