如果可以估计TList,TObjectList和plain数组之间的性能差异有多明显？

Question

*摘要:

请查看德尔福专家的知识渊博的评论.特别是对我来说,我会尝试使用旧的TList/TObjectList作为David建议,并使用hard-cast和TObjectList.List属性作为A.Bouchez建议.我将在未来重构时尝试使用TDynArray.

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

假设我有一个TAtom如下面代码中定义的类.目前,在运行时hundreds最多thousands有TAtom实例stored in a dynamic array.在运行时,我需要对TAtom.X/Y/Z所有现有的TAtom实例进行简单的浮点运算,30每秒多次.

现在,我需要补充的能力adding,inserting,deletingTAtom的实例在运行时.似乎我的选择是(1)请求一个大阵列; (2)坚持动态数组并手动设置SetLength; (3)切换到常规TList; (4)切换到常规TObjectList.

我想避免(1)除非有必要,因为我必须改变很多功能签名.(2)看起来也不好,因为TList/TObjectList似乎为这项任务而生.但是,因为需要使用常规TList/TObjectList进行类型转换,是否可以对可能的性能命中进行一些评论？我的意思是,如果在重写代码之前可以估算性能负担,那将是最好的.如果性能会明显下降,我还可以使用其他技术吗？

此外,我想知道使用TList和TObjectList之间是否存在性能差异？

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

  TAAtom = array of TAtom;

Answer 1

我可以在你的清单中添加另一个选择吗？

如果您没有对数据使用任何继承功能,则TAtom可以使用a record而不是a class.每个类实例都需要在内存中分配,填充为零并单独初始化.Getmem/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

适用于Delphi 6至XE.

随着更新版本的Delphi支持泛型,您应该更好地朝着这个方向前进.

Answer 2

如果您使用Generics.Collections.TObjectList<TAtom>并且不需要铸造.

对于您描述的用法,性能应该没问题.插入比添加到最后要求更高,因为您需要在插入点之后将项目移动到列表中.

只要你避免SetLength(A, Length(A)+1)并选择更合理的分配策略,动态数组就等同于所有TList类似的类.

在尝试将大型列表维护为连续的内存块时,我偶尔会遇到性能和内存碎片问题.然后我采用了子分配方案.但由于您的列表包含基本上是指针的对象引用,因此您已经有隐式子分配.

这些都是有点投机的,你真的需要衡量 - 否则我们只能猜测.