Насколько заметна разница в производительности между TList, TObjectList и простым массивом, если ее можно оценить?

Если вы используете Generics.Collections.TObjectList<TAtom> и нет необходимости в кастинге.

Производительность должна быть удовлетворительной для описываемого вами использования. Вставка сложнее, чем добавление в конец, потому что вам нужно сдвинуть элементы после точки вставки вверх по списку.

Пока вы избегаете SetLength(A, Length(A)+1) и выбираете более разумную стратегию распределения, динамические массивы эквивалентны всем TList-подобным классам.

Иногда у меня возникали проблемы с производительностью и фрагментацией памяти при попытке сохранить большие списки как непрерывные блоки памяти. Затем я прибег к схеме суб-распределения. Но поскольку ваши списки содержат ссылки на объекты, которые по сути являются указателями, у вас уже есть неявное суб-распределение.

Все это несколько умозрительно, и вам действительно нужно измерить - иначе мы можем только догадываться.

Могу я добавить еще один вариант в ваш список?

Если вы не используете какую-либо функцию наследования для данных в TAtom, вы можете использовать record вместо class. Каждый экземпляр класса должен быть выделен в памяти, заполнен нулями и инициализирован индивидуально. Getmem/Freemem всегда стоит, а фрагментация памяти будет увеличиваться.

Предварительно выделенный динамический array of record будет быстрее, чем отдельные экземпляры класса для добавления. И данные лучше подойдут для кэша 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, поддерживающей дженерики, вам лучше пойти в этом направлении.

Однако, поскольку требуется приведение типов с использованием обычного TList / TObjectList, может ли кто-нибудь прокомментировать возможное снижение производительности?

Если вы наберете cast, используя форму

List[I] as TAtom

так как будут добавлены небольшие накладные расходы, которые действительно могут сложиться в вашей ситуации. Однако, если вы жестко преобразуете

TAtom(List[I])

насколько мне известно, накладных расходов на самом деле не возникает, поскольку приведение типов выполняется без проверок, и я также считаю, что это выполняется во время компиляции.

Что касается другого аспекта вашего вопроса, я думаю, что они все уже были должным образом освещены ...

Поскольку TObjectList является прямым потомком TList, производительность будет очень близка.

Первый вопрос: мы говорим о Classes.TList и Contnrs.TObjectList или о Generics.Collections.TList соответственно Generics.Collections.TObjectList?

Если мы говорим о дженериках, и TList, и TObjectList реализованы с использованием динамических массивов. Если есть какая-либо разница в производительности между прямым использованием динамического массива или использованием более удобного интерфейса универсального контейнера, она будет незначительной.

Если мы говорим о более старых TList и TObjectList, то нам нужно сравнивать только TList с эквивалентом динамического массива, поскольку TObjectList является потомком TList, поэтому он наследует все его характеристики производительности. TList использует блок памяти, выделенный с помощью ReallocMem. Внутренне динамический массив делает то же самое, поэтому существенной разницы быть не должно!

Вывод

Если между ними есть какая-то разница в производительности, вероятно, потому, что наивное использование динамического массива использует ужасный SetLength(A, Length(A)+1), в то время как лучшая реализация во всех предоставленных Delphi контейнерах предварительно выделяет память в более крупных частях. При правильном коде между этими альтернативами не должно быть значительной разницы!

Создайте тестовый проект и измерьте время добавления, вставки и удаления тысяч экземпляров TAtom, используя четыре метода. Затем решите, какой из них использовать.

TList и TObjectList, вероятно, быстрее, чем динамический массив при добавлении, вставке и удалении, потому что динамический массив постоянно должен перераспределяться. Реализация TList и TObjectList этого не делает.

TList и т. Д. Делают именно то, что должен делать код, работающий с фрагментами памяти или динамическими массивами, но их реализация уже оптимизирована для общего случая и включает соображения о том, как ведет себя диспетчер памяти.

Одним из критериев может быть соотношение чтений / обновлений к последовательности. Если после создания последовательность обновляется нечасто, то должна быть заметна лучшая скорость с динамическими массивами, потому что для доступа к элементам с TList и т.п. требуется один вызов метода плюс проверка границ плюс проверка типа, если вы используете оператор as.

В конце концов, стоимость арифметических операций, выполняемых на TAtom, должна преобладать во времени выполнения, поэтому выбор dynarray или TListXXX не имеет значения.

Динамические массивы записей будут иметь наименьшее влияние при доступе к элементам, если ваши атомы являются объектами, тогда все списки будут в некоторой степени эквивалентными с точки зрения скорости доступа.

Однако, если вы выполните многие из них, вашей ключевой проблемой будут вставки и удаления, для которых все списки и массивы будут работать плохо, но это то, что вам скажет профилирование. В этом случае вы можете подумать о следующем:

• связанный список, если вам не нужен доступ к атомам по индексу
• дерево, если вы использовали его для пространственного раздела ваших атомов, вы могли бы также использовать этот раздел для хранения ваших атомов, а не массива
• разрешение элементов undefined / nil в вашем массиве / списке и поддержание стека элементов undefined / nil и индекса, если вам нужен отсортированный список (потенциально самое высокопроизводительное решение, но также, вероятно, наиболее сложное с точки зрения эффективности )