среда, 14 октября 2015 г.

#854. Containers, ARC and efficiency

Original in Russian: http://programmingmindstream.blogspot.ru/2015/09/1167-arc.html

I have containers.

Links:

Abstract containers.
Deriving of specific atomic containers from abstract ones.
Comments about containers  (in Russian)
Special containers. Part 2
http://18delphi.blogspot.ru/2013/07/blog-post_5374.html
Abstract containers. Part 2

Similar to TList<T> but own ones.

Usually, the iteration by container is as follows:

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

Items is as follows:

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

The source code:
https://bitbucket.org/lulinalex/mindstream/src/7b84d023d4aefe22476b8a4ce398c42088e7f164/Examples/1167/?at=B284

Actually, it is quite good.

Containers of TList<T> sort are organized “in almost the same way”.

BUT!

It is “quite good” as long as _ItemType_ is the type WITHOUT ARC, i.e. it is atomic or is an object but neither a record with interfaces nor an interface.

As soon as we deal with ARC and/or a “large” record, we face efficiency issues.

What issues?

Items[i] return container’s elements ON VALUE, i.e. the values are COPIED to temporary variables.

But there is GetItemSlot method:

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

It returns the POINTER to the container’s element.

Thus we may rewrite the iteration by container:

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

The syntax is the same. We did not even have to dereference the pointer – the compiler did.

However, the semantics is different.

Instead of value copy the pointer to the element is returned.

Therefore, there are no overhead costs for either ARC or copying the “large record”.

IT IS CLEAR that we show the “container’s intestine”.

The reason is Delphi has no analogue to C++ const & (const reference).

We can write the value on this pointer but be ready to face the music.

Anyway, we win on the efficiency.

Even if we do as follows:

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

we still have NEITHER ARC nor copying.

The reason is const is written in SomeProc before anItem.

Referring back to TList<T> I’d like to say that the structure:

for Element in Container do
 Element.SomeMethod;

has the same problems as in the very first example.

The reason is:

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

Current: T returns the VALUE instead of a pointer or a reference.

Thus ARC and/or COPYING.

Moreover, in mobile version ARC also works FOR OBJECTS (if there is assignment).

No way to do it differently in containers of TList<T> sort.

But it is possible to do it in “my” containers – using ItemSlot.

Thank you for attention.

P.S. Same is in https://bitbucket.org/lulinalex/mindstream/src/99ff3eee284bcab17905f1c9cbe02d4769c3e585/Examples/1167/tfwValueStack.pas?at=B284&fileviewer=file-view-default

pLast is used instead of Last with a good reason.

See the example:

...
function TtfwValueStack.PopBool: Boolean;
//#UC START# *4DB013AF01C9_4DB009CF0103_var*
//#UC END# *4DB013AF01C9_4DB009CF0103_var*
begin
//#UC START# *4DB013AF01C9_4DB009CF0103_impl*
 EtfwCheck.IsTrue(Count > 0, 'Empty stack');
 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, 'Empty stack');
 Result := pLast.AsDelphiString;
 Delete(Count - 1);
//#UC END# *4DB0489C0129_4DB009CF0103_impl*
end;//TtfwValueStack.PopDelphiString
...
etc

P.P.S. I do know about multithreading.

It does NOT ALLOW to return the pointer, JUST the value.

This is when you have to work with container using DIFFERENT threads.

P.P.P.S. Still, same issues with ARC and copying come up for large amounts of data.

Комментариев нет:

Отправить комментарий