8

*Summarization:

Please check the knowledgeable comments from the Delphi experts. Specifically for me, I would try to use old TList/TObjectList as David suggested, and use hard-cast and TObjectList.List property as A.Bouchez suggested. I will try TDynArray when refactoring in future.

=====================================================================

Say that I have a TAtom class as defined in the following code. There are about hundreds up to thousands of TAtom instances at run time, stored in a dynamic array for now. At run time, I need to do simple float math on TAtom.X/Y/Z of all the existing TAtom instances more than 30 times per second.

Now, I need to add the ability of adding, inserting, deleting of TAtom instances at run time. It seems that my choices are (1) request a big array; (2) stick to dynamic array and manually SetLength; (3) switch to regular TList; (4) switch to regular TObjectList.

I want to avoid (1) unless it is necessary, because I then have to change quite a lot function signatures. (2) looks not good either, because TList/TObjectList seems born for this task. However, because type-casting is needed using the regular TList/TObjectList, could some one comment on the possible performance hit? I mean, it would be best if the performance burden could be estimated before I rewrites the code. If the performance will drop noticeably, is there other technics that I could use?

Furthermore, I am wondering if there is performance difference between using TList and TObjectList? 

  TAtom = class
  public
    ElementZ: Integer;
    X, Y, Z: Extended;  
    other variables: other types;
  end;

  TAAtom = array of TAtom;
4

8 に答える 8

8

あなたのリストに別の選択肢を追加してもいいですか？

のデータに継承機能を使用しない場合は、の代わりにをTAtom使用できます。各クラスインスタンスは、メモリに割り当てられ、ゼロで埋められ、個別に初期化される必要があります。常にコストがかかり、メモリの断片化が増加します。recordclassGetmem/Freemem

事前に割り当てられたダイナミックarray of recordは、追加する個々のクラスインスタンスよりも高速になります。また、データはCPU L1/L2キャッシュにより適しています。

挿入および削除の場合、削除/挿入するデータが増えるため（どちらもポインターのリストのみを保持するため） 、そのようなレコードの配列はTList、アイテムが大量にある場合よりも遅くなります。TList/TObjectList挿入/削除をさらに高速化するには、リンクリストを使用することをお勧めします。

TList/TObjectList内部通知のため、メカニズムにはいくらかのオーバーヘッドがあります。メカニズムそして、GetItem()プロパティは、動的配列を直接使用するよりも（範囲チェックのために）少し遅くなる可能性があります。

しかし、TDynArrayラッパーを使用すると、動的配列に固執しても、優れたパフォーマンス、事前割り当て機能、および同様のTListメソッドを使用できます。SaveToStream, Slice, Reverseまた、外部インデックスを使用した並べ替えなど、さらに多くの方法を利用できます。

type
  TAtom = record // could be 'packed record' to save memory (but loose perf)
    ElementZ: Integer;
    X, Y, Z: Extended;  
    other variables: other types;
    // TDynArray also handle complex (e.g. string) types here
  end;
  TAtoms = array of TAtom;

var Atom: TAtom;
    AtomArray: TAtoms;
    AtomCount: integer;
    Atoms: TDynArray;
begin
  Atoms.Init(TypeInfo(TAtoms),AtomArray,@AtomCount);
  Atoms.Capacity := 10000; // pre-allocate array = same as SetLength(AtomArray,10000)
  for i := 1 to 10000 do begin
    A.ElementZ := Random(1000);
    A.X := Random;
    A.Y := Ramdom;
    A.Z := Random;
    // set other fields
    Atoms.Add(A); // fast adding of A properties
  end;
  // you have TList-like methods for your dynamic array
  Atoms.Delete(500); // delete 500th item
  A.ElementZ := 5000;
  Atoms.Insert(500,A); // insert A values at 500th index
  assert(Atoms.Count=10000);
  assert(AtomCount=10000); // same as Atoms.Count
  Atoms.Compare := SortDynArrayInteger;
  Atoms.Sort; // will sort by 1st Integer value = ElementZ
  for i := 1 to Atoms.Count-1 do // or AtomCount-1
    // you have still direct access to AtomArray[]
    // -> this is even the fastest access to the data
    assert(AtomArray[i].ElementZ >=AtomArray[i-1].ElementZ )
  Atoms.SaveToStream(aStream); // will also save any string content
  Atoms.Reverse; // reverse all items order
  Atoms.Clear;
  // faster adding will be done with direct access to the dynamic array
  Atom.Count := 10000; // allocate memory for 10000 items
  for i := 0 to 10000-1 do
  with AtomArray[i] do
  begin
    ElementZ := Random(2000);
    X := Random;
    Y := Random;
    Z := Random;
  end;
  Atoms.Sort; // TDynArray knows about the data just created
end; // no need to have any try...finally ..Free block

XEまでのDelphi6で動作します。

ジェネリックスをサポートするDelphiの新しいバージョンでは、この方向に進んでください。

于 2011-03-18T13:01:46.483 に答える
7

使用Generics.Collections.TObjectList<TAtom>し、キャストの必要がない場合。

説明する使用法では、パフォーマンスは良好である必要があります。挿入ポイントの後にアイテムをリストの上方に移動する必要があるため、挿入は最後に追加するよりも要求が厳しくなります。

より賢明な割り当て戦略を避けて選択する限り、動的配列は同様のクラスSetLength(A, Length(A)+1)すべてと同等です。TList

大きなリストをメモリの連続ブロックとして維持しようとすると、パフォーマンスとメモリの断片化に問題が発生することがありました。それから私はサブアロケーションスキームに頼りました。ただし、リストには本質的にポインタであるオブジェクト参照が含まれているため、すでに暗黙的なサブ割り当てがあります。

それはすべていくぶん推測的であり、あなたは本当に測定する必要があります–そうでなければ、私たちは推測することしかできません。

于 2011-03-18T12:49:35.090 に答える
3

ただし、通常の TList/TObjectList を使用した型キャストが必要なため、パフォーマンス ヒットの可能性についてコメントしていただけますか?

フォームを使用してキャストを入力した場合

List[I] as TAtom

小さなオーバーヘッドが追加されるため、状況によっては実際に追加される可能性があります。ただし、ハード型キャストの場合

TAtom(List[I])

私の知る限り、型キャストはチェックなしで実行されるため、実際にはオーバーヘッドは発生しません。また、コンパイル時に行われると考えています。

あなたの質問の他の側面については、それらはすべて適切にカバーされていると思います...

于 2011-03-18T14:22:34.457 に答える
1

最初の質問：私たちはそれぞれについて話しているのですかClasses.TList、それとも話しているのですか？Contnrs.TObjectListGenerics.Collections.TListGenerics.Collections.TObjectList

ジェネリックスについて話している場合、TListとTObjectListの両方が動的配列を使用して実装されます。動的配列を直接使用する場合と、汎用コンテナーのより優れたインターフェースを使用する場合の間にパフォーマンスの違いがある場合、それは無視できる程度になります。

「古い」TListとについて話している場合、はの子孫であり、パフォーマンス特性をすべて継承しているため、同等の動的配列とTObjectListのみ比較する必要があります。を使用して割り当てられたメモリのブロックを使用します。動的配列は内部で同じことを行うので、大きな違いはないはずです！TListTObjectListTListTListReallocMem

結論

2つの間にパフォーマンスの違いがある場合、それはおそらく動的配列の素朴な使用が恐ろしいものを使用しているSetLength(A, Length(A)+1)のに対し、Delphiが提供するすべてのコンテナでのより良い実装はメモリをより大きなチャンクに事前に割り当てているためです。適切なコードがあれば、これらの選択肢の間に大きな違いはありません！

于 2011-03-18T12:48:16.353 に答える
1

TListなどは、メモリまたはdynarrayのチャンクで動作するコードが実行する必要があることを正確に実行しますが、それらの実装はすでに一般的なケースに合わせて最適化されており、メモリマネージャの動作に関する考慮事項が含まれています。

1つの基準は、シーケンスに対する読み取り/更新の比率である可能性があります。シーケンスが作成後に更新される頻度が低い場合は、dynarrayを使用すると、速度が大幅に向上するはずです。これは、などの要素にアクセスするには、1つのメソッド呼び出しと境界チェックに加えて、演算子TListを使用する場合はタイプチェックが必要になるためです。as

結局、実行される演算のコストがTAtom実行時間を支配し、dynarrayまたはTListXXX無関係の選択を行う必要があります。

于 2011-03-18T13:02:01.023 に答える
1

レコードの動的配列は、アイテムにアクセスするときの影響が最も少なくなります。アトムがオブジェクトである場合、すべてのリストはアクセス速度の点で多少同等になります。

ただし、それらの多くを実行すると、主な問題は挿入と削除になり、すべてのリストと配列のパフォーマンスが低下しますが、それはプロファイリングによってわかります。その場合は、次のことを検討してください。

  • インデックスでアトムにアクセスする必要がない場合は、リンクされたリスト
  • ツリー、アトムの空間パーティションに使用する必要がある場合は、そのパーティションを使用して、配列ではなくアトムを保持することもできます
  • 配列/リストで未定義/nil要素を許可し、未定義/nil要素のスタックを維持し、ソートされたリストが必要な場合はインデックスを維持します(潜在的に最高のパフォーマンスのソリューションですが、効率の観点から正しくするのが最も複雑になる可能性があります) )
于 2011-03-18T13:29:23.310 に答える
1

テスト プロジェクトを作成し、4 つの方法を使用して数千の TAtom インスタンスを追加、挿入、および削除する時間を測定します。次に、どちらを使用するかを決定します。

動的配列は常に再割り当てする必要があるため、TList と TObjectList は、追加、挿入、および削除時におそらく動的配列よりも高速です。TList と TObjectList の実装はそれを行いません。

于 2011-03-18T12:42:46.163 に答える
1

TObjectList は TList の直接の子孫であるため、パフォーマンスは非常に近いものになります。

于 2011-03-18T12:42:51.040 に答える