Mi è stato detto che quando ho una tabella hash di dimensioni m e m=2^k , posso usare l'operatore & come num & (size-1) invece di num % size , per adattare l'hashCode alla mia tabella taglia.
Mi è stato anche detto che il comando Num & sizeMinusOne è più del doppio più veloce di num & (size-1) .
La mia domanda è, perché?
E l'operazione di creazione di una variabile chiamata SizeMinusOne non richiede troppo tempo?
Per quanto riguarda % 2**k vs. & 2**k-1 : questa è una micro ottimizzazione, ma fattibile. Il compilatore non può dimostrare che size sia sempre una potenza di due (essendo variabile e possibilmente modificata dal codice in diverse unità di traduzione), quindi non può eseguire l'ottimizzazione stessa. La divisione in interi ha un throughput e una latenza significativamente peggiori rispetto alle operazioni bit a bit su praticamente ogni architettura. In una certa misura, ciò può essere giustificato anche con la teoria della complessità: le operazioni bitwise richiedono una dimensione lineare di tempo / circuito, mentre le operazioni di divisione / modulo più note richiedono dimensioni di tempo / circuito superlineari. Questo effetto è misurabile anche sulle macchine contemporanee (lo so perché non ci credevo e l'ho provato).
Riguarda size-1 contro sizeMinusOne : L'idea è di memorizzare sizeMinusOne (ho visto il nome mask per questo) invece di size , per ridurre la ridondanza. In un modello di macchina molto locale, miope, num & sizeMinusOne è (pseudo-RISC)
and r3, r1, r2
mentre num & (size - 1) è
sub r3, r2, #1
and r3, r1, r3
con impostazione diversa identica e codice circostante. Poiché le operazioni bitwise e aritmetiche sono in genere ugualmente veloci (ciclo ALU singolo, latenza ottimale), si potrebbe effettivamente sostenere che il primo impiega metà delle risorse del secondo.
Ma questo ignora il fatto che il codice circostante richiederà molto più tempo, un centinaio di cicli nel complesso è una stima molto ottimistica. In quel contesto, un singolo ciclo non è solo arachidi, è un errore di misura, semplicemente rumore. Non perdere il sonno su di esso. Inoltre, a seconda del codice circostante potrebbe non essere nemmeno un singolo ciclo: una CPU fuori ordine (come la maggior parte dei core x86 contemporanei) potrebbe molto bene spremere la sottrazione da qualche parte nella pianificazione mentre una ALU è inattiva e da fare con esso prima ancora di aver finito di calcolare num .
Esistono tuttavia altri motivi per memorizzare mask anziché size . Di solito il primo è usato più spesso del secondo, quindi preferendo mask puoi semplificare il codice.
Leggi altre domande sui tag bitwise-operators math hashing