пятница, 25 сентября 2015 г.

#1167. Про контейнеры, ARC и производительность

У меня есть контейнеры.

Ссылки:

http://18delphi.blogspot.ru/2013/07/blog-post_3683.html
http://18delphi.blogspot.ru/2013/07/blog-post_8789.html
http://18delphi.blogspot.ru/2013/07/blog-post_20.html
http://18delphi.blogspot.ru/2013/07/2_18.html
http://18delphi.blogspot.ru/2013/07/blog-post_5374.html
http://18delphi.blogspot.ru/2013/07/2.html

Типа TList<T>.

Но свои.

Обычно итерация по контейнеру выглядит так:

for i := 0 to Container.Count - 1 do
 Container.Items[i].SomeMethod;

Где Items выглядит так:

function _l3TypedList_.pm_GetItems(anIndex: Integer): _ItemType_;
//#UC START# *47A1B1C102E9_47B084190028get_var*
//#UC END# *47A1B1C102E9_47B084190028get_var*
begin
//#UC START# *47A1B1C102E9_47B084190028get_impl*
 Result := GetItem(anIndex);
//#UC END# *47A1B1C102E9_47B084190028get_impl*
end;//_l3TypedList_.pm_GetItems

function _l3TypedListPrim_.GetItem(Index: Integer): _ItemType_;
//#UC START# *47B1CCC901BE_47A74A5F0123_var*
//#UC END# *47B1CCC901BE_47A74A5F0123_var*
begin
//#UC START# *47B1CCC901BE_47A74A5F0123_impl*
 CheckIndex(Index);
 Result := ItemSlot(Index)^;
//#UC END# *47B1CCC901BE_47A74A5F0123_impl*
end;//_l3TypedListPrim_.GetItem

Исходники:
https://bitbucket.org/lulinalex/mindstream/src/7b84d023d4aefe22476b8a4ce398c42088e7f164/Examples/1167/?at=B284

И вообще говоря - всё неплохо.

Контейнеры типа TList<T> устроены "примерно так же".

НО!

"Неплохо до тех пор" пока _ItemType_ это тип БЕЗ ARC. Т.е. атомарный или объект.

А не запись с интерфейсами или интерфейс.

Как только появляется ARC и/или "большая" запись, то возникает проблема производительности.

В чём?

А в том, что Items[i] возвращают элементы контейнера ПО ЗНАЧЕНИЮ.

Т.е. - КОПИРУЮТ значения во временые переменные.

Но есть метод GetItemSlot:

function GetItemSlot(anIndex: Integer;
  aList: _l3Items_): PItemType;
//#UC START# *47BEDF2A02EA_47A74A5F0123_var*
//#UC END# *47BEDF2A02EA_47A74A5F0123_var*
begin
//#UC START# *47BEDF2A02EA_47A74A5F0123_impl*
 Result := Pointer(aList.f_Data.AsPointer + anIndex * cItemSize);
 assert(Result <> nil);
//#UC END# *47BEDF2A02EA_47A74A5F0123_impl*
end;//GetItemSlot

- он возвращает УКАЗАТЕЛЬ на элемент контейнера.

Тогда итерацию по контейнеру можно переписать:

for i := 0 to Container.Count - 1 do
 Container.ItemSlot(i).SomeMethod;

Синтаксически - похоже на то что выше. Даже "разыменовывать" указатель не надо. Это делает компилятор.

А вот семантически это несколько другое.

Возвращается указатель на элемент, а не копия значения.

Соответственно нет никаких накладных расходов ни на ARC ни на копирование "большой записи".

ПОНЯТНО, что мы тут неким образом выставляем наружу "кишки контейнера".

Потому что в Delphi нет аналога C++ const & (константная ссылка).

И по этому указателю можно записать значение. Но тут уж - ССЗБ (Сам Себе Злобный Буратина).

Зато с производительностью имеем выигрыш.

Даже если мы сделаем так:

procedure SomeProc(const anItem: ItemType);
...

for i := 0 to Container.Count - 1 do
 SomeProc(Container.ItemSlot(i)^);

То ВСЁ РАВНО ни ARC, ни копирования - НЕ БУДЕТ.

Потому, что там - const написано в SomeProc перед anItem.

И возвращаясь к TList<T> - скажу следующее:

Конструкция:

for Element in Container do
 Element.SomeMethod;

Имеет все те же проблемы, что и самый первый пример.

Ибо:

  TEnumerator<T> = class abstract
  protected
    function DoGetCurrent: T; virtual; abstract;
    function DoMoveNext: Boolean; virtual; abstract;
  public
    property Current: T read DoGetCurrent;
    function MoveNext: Boolean;
  end;

  TEnumerable<T> = class abstract
  private
  {$HINTS OFF}
    function ToArrayImpl(Count: Integer): TArray<T>; // used by descendants
  {$HINTS ON}
  protected
    function DoGetEnumerator: TEnumerator<T>; virtual; abstract;
  public
    destructor Destroy; override;
    function GetEnumerator: TEnumerator<T>;
    function ToArray: TArray<T>; virtual;
  end;

Current: T - возвращается ЗНАЧЕНИЕ, а не указатель или ссылка.

А значит ARC и/или КОПИРОВАНИЕ.

Более того в мобильной версии ARC работает ещё и ДЛЯ ОБЪЕКТОВ (если есть присваивание).

И в контейнерах типа TList<T> по-другому - не сделаешь.

А в "моих" - сделаешь.

Через ItemSlot.

Спасибо за внимание.

P.S. Ну и аналогично в https://bitbucket.org/lulinalex/mindstream/src/99ff3eee284bcab17905f1c9cbe02d4769c3e585/Examples/1167/tfwValueStack.pas?at=B284&fileviewer=file-view-default

Не зря pLast используется, а не Last,

Вот например:

...
function TtfwValueStack.PopBool: Boolean;
//#UC START# *4DB013AF01C9_4DB009CF0103_var*
//#UC END# *4DB013AF01C9_4DB009CF0103_var*
begin
//#UC START# *4DB013AF01C9_4DB009CF0103_impl*
 EtfwCheck.IsTrue(Count > 0, 'Стек пустой');
 Result := pLast.AsBoolean;
 Delete(Count - 1);
//#UC END# *4DB013AF01C9_4DB009CF0103_impl*
end;//TtfwValueStack.PopBool

function TtfwValueStack.IsTopBool: Boolean;
//#UC START# *4DB04213007C_4DB009CF0103_var*
//#UC END# *4DB04213007C_4DB009CF0103_var*
begin
//#UC START# *4DB04213007C_4DB009CF0103_impl*
 if Empty then
  Result := false
 else
  Result := (pLast.rType = tfw_vtBool); 
//#UC END# *4DB04213007C_4DB009CF0103_impl*
end;//TtfwValueStack.IsTopBool
...
function TtfwValueStack.IsTopString: Boolean;
//#UC START# *4DB0488A0157_4DB009CF0103_var*
//#UC END# *4DB0488A0157_4DB009CF0103_var*
begin
//#UC START# *4DB0488A0157_4DB009CF0103_impl*
 if Empty then
  Result := false
 else
  Result := (pLast.rType = tfw_vtStr); 
//#UC END# *4DB0488A0157_4DB009CF0103_impl*
end;//TtfwValueStack.IsTopString

function TtfwValueStack.PopDelphiString: AnsiString;
//#UC START# *4DB0489C0129_4DB009CF0103_var*
//#UC END# *4DB0489C0129_4DB009CF0103_var*
begin
//#UC START# *4DB0489C0129_4DB009CF0103_impl*
 EtfwCheck.IsTrue(Count > 0, 'Стек пустой');
 Result := pLast.AsDelphiString;
 Delete(Count - 1);
//#UC END# *4DB0489C0129_4DB009CF0103_impl*
end;//TtfwValueStack.PopDelphiString
...
etc

P.P.S. Да про многопоточность - я тоже знаю.

В многопоточности НЕЛЬЗЯ указатель отдавать. ТОЛЬКО значение.

Если с контейнером реально из РАЗНЫХ потоков нужно работать.

P.P.P.S. Опять же все проблемы с ARC и копированием вылезают на больших объёмах данных.

2 комментария:

  1. for in - для ленивых. Сам таким становлюсь потихоньку.
    А вот сделать, чтобы Enumerator возвращал указатель на значение - это интересная мысль...

    ОтветитьУдалить
    Ответы
    1. А между тем в C++ и STL for удобен и не влияет на производительность, потому, что там const & есть.

      Удалить