Implementazione più rapida di CompareText per D2009

Question

Uso ampiamente le strutture di dati della mappa hash nel mio programma. Sto usando un'implementazione della mappa hash di Barry Kelly pubblicata nei forum di Codegear. Tale implementazione utilizza internamente la funzione CompareText di RTL. La profilazione mi ha fatto capire che un sacco di tempo è trascorso nella funzione CompareText di SysUtils.

Ho dato un'occhiata a

Sito Fastcode

e ho trovato alcune implementazioni più veloci di CompareText. Sfortunatamente sembrano non funzionare con D2009 e le sue stringhe unicode.

Ora per la domanda: esiste una versione simile più veloce che supporta le stringhe D2009? Le funzioni CompareText sembrano essere chiamate molto quando si usano le mappe hash (almeno nell'implementazione che sto attualmente usando), quindi piccoli miglioramenti delle prestazioni potrebbero davvero fare la differenza. O le implementazioni qui presentate dovrebbero funzionare anche per le stringhe unicode?

Answer 1

Molte delle funzioni di FastCode probabilmente si compileranno e sembreranno funzionare bene in Delphi 2009, ma non saranno adatte a tutti gli input. Quelli che sono implementati in assembler falliranno perché presumono che i caratteri siano solo un byte ciascuno. Quelli implementati in Delphi andranno un po 'meglio, ma a volte restituiranno risultati errati a volte perché la vecchia nozione di CompareText di "quot-insensitive" si basa su ASCII mentre il nuovo dovrebbe essere basato su Unicode. Le regole per le quali i personaggi sono considerati lo stesso salvataggio per case sono molto diverse per Unicode da come sono per ASCII.

Andreas afferma in un commento di seguito che Unicode CompareText utilizza ancora le regole di confronto tra maiuscole e minuscole ASCII, quindi un certo numero di funzioni FastCode dovrebbe funzionare correttamente. Basta guardarli prima di usarli per assicurarsi che non stiano facendo ipotesi sulla dimensione del personaggio. Mi sembra di ricordare che alcune funzioni FastCode erano già incorporate in Delphi RTL. Non ho idea se CompareText fosse uno di questi.

Se stai chiamando molto CompareText in una tabella hash, ciò suggerisce che la tua tabella hash non sta facendo un ottimo lavoro. CompareText dovrebbe essere chiamato solo quando l'hash della cosa che stai cercando ha designato un bucket non vuoto nella tabella hash. Da lì, una tabella hash utilizzerà spesso una ricerca lineare per trovare l'elemento giusto nel bucket e chiamerà CompareText per ogni elemento durante quella ricerca. Non so se funziona così.

Potresti risolverlo usando una diversa funzione hash che distribuisce i suoi risultati in modo più uniforme sui bucket disponibili. Se i tuoi bucket sono già riempiti in modo uniforme, potresti aver bisogno di più bucket (e quindi assicurati che la funzione hash si distribuisca uniformemente anche su quel ).

Se la classe di hash-map che stai usando si basa su TBucketList , allora c'è spazio per migliorare l'archiviazione bucket. Quella classe non calcola un hash sull'intero input. Utilizza l'input solo per determinare il bucket da utilizzare. Se la classe tiene anche traccia dell'hash completo calcolato per una stringa, i confronti durante la ricerca lineare potrebbero andare molto più velocemente. Basta confrontare gli hash e confrontare le stringhe solo quando gli hash corrispondono completamente. (Per un bucket-list da 256 bucket, la dimensione supportata più grande, solo un byte dell'input determina il bucket e il resto dei byte viene ignorato.) Ho già scritto su TBucketList qui prima.