Implémentation CompareText plus rapide pour D2009

Question

J'utilise intensivement des structures de données de hachage dans mon programme. J'utilise une implémentation de la carte de hachage de Barry Kelly publiée sur les forums de Codegear. Cette implémentation utilise en interne la fonction CompareText de RTL. Le profilage m'a fait réaliser que beaucoup de temps est passé dans la fonction CompareText de SysUtils.

J'ai eu un coup d'œil à la

Fastcode site

et trouvé quelques implémentations plus rapides de CompareText. Malheureusement, ils ne semblent pas fonctionner pour D2009 et ses chaînes Unicode.

Maintenant pour la question: existe-t-il une version plus rapide similaire qui prend en charge les chaînes D2009? Les fonctions CompareText semblent être beaucoup appelées lors de l'utilisation de maps de hachage (au moins dans l'implémentation que j'utilise actuellement), donc peu d'améliorations de performances peuvent vraiment faire la différence. Ou les implémentations présentées ici devraient-elles aussi fonctionner pour les chaînes Unicode?

Answer 1

La plupart des fonctions FastCode seront probablement compilées et sembleront fonctionner correctement dans Delphi 2009, mais elles ne seront pas adaptées à toutes les entrées. Ceux qui sont implémentés dans l'assembleur échoueront car ils supposent que les caractères ne sont qu'un octet chacun. Ceux implémentés dans Delphi s'en tireront un peu mieux, mais ils renverront quand même des résultats incorrects parfois parce que la vieille notion de "case-insensitive" de CompareText est basée sur ASCII alors que la nouvelle devrait être basée sur Unicode. Les règles pour lesquelles les caractères sont considérés comme identiques sont beaucoup différent pour Unicode de la façon dont ils sont pour ASCII.

Andreas indique dans un commentaire ci-dessous que Unicode CompareText utilise toujours les règles de comparaison de cas ASCII, de sorte qu'un certain nombre de fonctions FastCode devraient fonctionner correctement. Il suffit de les regarder avant de les utiliser pour s'assurer qu'ils ne font aucune hypothèse de taille de caractère. Je semble rappeler que certaines fonctions FastCode ont déjà été incorporées dans le Delphi RTL. Je n'ai aucune idée si CompareText était l'un d'entre eux.

Si vous appelez CompareText beaucoup dans une table de hachage, alors cela suggère que votre table de hachage ne fait pas un très bon travail. CompareText ne doit être appelé que lorsque le hachage de la chose que vous recherchez désigne un compartiment non vide dans la table de hachage. À partir de là, une table de hachage utilise souvent une recherche linéaire pour trouver le bon élément dans le compartiment et appelle CompareText pour chaque élément au cours de cette recherche. Je ne sais pas si c'est comme ça que ça fonctionne.

Vous pouvez résoudre ce problème en utilisant une fonction de hachage différente qui distribue ses résultats de manière plus homogène sur les compartiments disponibles. Si vos compartiments sont déjà remplis uniformément, alors vous aurez peut-être besoin de plus de compartiments (et ensuite assurez-vous que la fonction de hachage distribue également uniformément sur ce numéro également).

Si la classe de hachage que vous utilisez est basée sur TBucketList, il est possible d'améliorer le stockage de baquets. Cette classe ne calcule pas de hachage sur l'ensemble de l'entrée. Il utilise l'entrée uniquement pour déterminer le compartiment à utiliser. Si la classe gardait également trace du hachage complet calculé pour une chaîne, les comparaisons pendant la recherche linéaire pourraient aller beaucoup plus vite. Comparez simplement les hachages et ne comparez les cordes que lorsque les hachages correspondent parfaitement. (Pour une liste de baies de 256 baquets, la plus grande taille prise en charge, un seul octet de l'entrée détermine le compartiment et le reste des octets est ignoré.) I've written about TBucketList here before.