D2009のCompareText実装の高速化

Question

プログラムでハッシュマップデータ構造を広範囲に使用しています。 Codegearフォーラムに投稿された、Barry Kellyによるハッシュマップの実装を使用しています。その実装は、内部でRTLのCompareText関数を使用します。プロファイリングにより、SysUtils CompareText関数に多くの時間が費やされていることがわかりました。

私は見ていた

ファストコードサイト

そしてCompareTextのより高速な実装を見つけました。残念ながら、D2009とそのUnicode文字列では機能しないようです。

次の質問：D2009文字列をサポートする同様の高速バージョンはありますか？ CompareText関数は、ハッシュマップを使用するときに（少なくとも現在使用している実装では）頻繁に呼び出されるようであるため、パフォーマンスの向上はほとんどありません。または、そこに提示された実装はユニコード文字列でも動作するはずですか？

Answer 1

Delphi 2009では、多くのFastCode関数がコンパイルされて正常に動作しているように見えますが、すべての入力に適しているわけではありません。アセンブラーに実装されているものは、文字がそれぞれ1バイトだけであると想定しているため失敗します。 Delphiで実装されたものは少し良くなりますが、古い CompareText の「大文字と小文字を区別しない」という概念が原因で、間違った結果を返すことがあります。 ASCIIに基づいていますが、新しいものはUnicodeに基づいている必要があります。文字が大文字と小文字を区別して同じであると見なされるルールは、Unicodeの場合とASCIIの場合とではかなり異なります。

Andreasは、以下のコメントでUnicode CompareText がASCII大文字と小文字の比較規則を使用しているため、多くのFastCode関数が正常に機能するはずだと述べています。それらを使用する前に目を通して、文字サイズを仮定していないことを確認してください。 FastCodeの一部の機能がDelphi RTLに既に組み込まれていることを思い出すようです。 CompareText がそれらの1つであったかどうかはわかりません。

ハッシュテーブルで CompareText を頻繁に呼び出している場合は、ハッシュテーブルがうまく機能していないことを示しています。 CompareText は、検索対象のハッシュがハッシュテーブル内の空でないバケットを指定した場合にのみ呼び出されます。そこから、ハッシュテーブルはしばしば線形検索を使用してバケット内の適切なアイテムを見つけ、その検索中にすべてのアイテムに対して CompareText を呼び出します。それがあなたが使用しているものがどのように機能するのかわかりません。

使用可能なバケットに結果をより均等に分散する別のハッシュ関数を使用して、これを解決することができます。バケットがすでに均等に満たされている場合は、さらにバケットが必要になる可能性があります（そして、ハッシュ関数がその番号にも均等に分散することを確認します）。

使用しているハッシュマップクラスが TBucketList に基づいている場合、バケットストレージに改善の余地があります。そのクラスは、入力全体でハッシュを計算しません。入力 only を使用して、使用するバケットを決定します。クラスが文字列に対して計算された完全なハッシュも追跡する場合、線形検索中の比較ははるかに高速になります。ハッシュを比較し、ハッシュが完全に一致した場合にのみ文字列を比較します。 （サポートされる最大サイズの256バケットバケットリストの場合、入力の1バイトのみがバケットを決定し、残りのバイトは無視されます。）以前に TBucketList について書いたことがあります。