Hi,

This may be a silly question.
I use System.Move() to move items in a dynamic array, like

  Move(FData[0], FData[OldEnd], FStart*SizeOf(T));

Where T is the type of the elements in the array.
This seems to work as expected.

I have some questions though:

1. Does this depend on the alignment of the array?
2. Is it OK if the elements of the array are (or contain) managed types?
3. Are there caveats if T is a specialization of a generic type definition?

No. The source and destination pointers may point to unaligned data.

2. Is it OK if the elements of the array are (or contain) managed types?

You need to manually finalize/free elements which are overwritten before calling Move. Also if you intend to use Move for duplication of elements of managed types, it is better to use for-loop to copy each element separately to allow proper increments of references.

3. Are there caveats if T is a specialization of a generic type definition?

No caveats, but see #2.

Yuriy.

PM Yuriy Sydorov wrote

> 2. Is it OK if the elements of the array are (or contain) managed types? You need to manually finalize/free elements which are overwritten before calling Move.

So, if I move Arr[3] to Arr[1], I first have to finilize/free Arr[1]. After that move the bytes in Arr[3] are exactly the same as in Arr[1] (by definition of how move works) AFAIU.
Is that a problem with refcounts, because they would be the same also but the number of copies increased?

Thanks for explaning.
OK, since this is a generic class, Systme.Move() can be safe, but it is not guaranteed (almost by definition you never know what <T> is going to be in the specialization.
So, I'll use a for loop to copy the data.

I assume that doing Arr[Index] := Default(T) will also finalize the
element if that element ismanaged?

System.Move just copies bytes in the memory. So all handling of managed types must be done manually. So if Arr[1] contains a managed value you need to finalize/free it before Move. After move Arr[1] and Arr[3] will contain the same value and if you need to keep both you need to increase the refcount manually.

If your array contains class object instances and no other references to them exist then you need to Free them before overwriting by Move.

So, I'll use a for loop to copy the data. I assume that doing Arr[Index] := Default(T) will also finalize the element if that element ismanaged?

For class object instances call Arr[Index].Free, for other managed types or records containing managed types Finalize(Arr[Index]) should work.

Yuriy.

Op 2021-01-09 om 20:12 schreef Yuriy Sydorov via fpc-pascal:

Or overwrite or finalize the old value with fillchar.

In the base class, is there a way to check wether Arr[Index] is an object instance or a managed type or a datatype containing a managed type?
Now the for loop (I abandoned the use of Move) does something like this:

  Arr[NewIndex] := Arr[OldIndex];  //do I have to finalize/free

Arr[NewIndex] also in this case?

  Arr[OldIndex] := Default(T);  //I understand this is not enough in those cases

I could of course add an (empty) method FinalizeOrFreeElement(Elem: T); to the base class and call that inside the loop, but that feels a bit sloppy.

For checking if it's a managed type you should use the IsManagedType intrinsic.
You could also use it to implement the System.Move() for non-managed types. The compiler only generates the appropriate code:

If IsManagedType(T) then
  // for loop
else
  // move

Best Regards
Nico

Bart via fpc-pascal schrieb am Sa., 9.
Jan. 2021, 22:55:

If by "base class" you mean the generic class (and not a base class in the object hierarchy sense), then you can use the IsManagedType intrinsic which is available since 3.2.0.

Now the for loop (I abandoned the use of Move) does something like this: Arr[NewIndex] := Arr[OldIndex]; //do I have to finalize/free Arr[NewIndex] also in this case?

No, the compiler will handle that correctly (it's just a normal assignment after all).

Arr[OldIndex] := Default(T); //I understand this is not enough in those cases

This is only not enough for class instances if they should be Free'd. For everything else this is indeed enough.

Regards,
Sven

If after the Move only one of the two references is reachable anymore (because e.g. some internal count variable "ends" the array before that element) then you don't need to care about increasing the reference count, cause there is only one reference after all (in that case you must *not* use an assignment to clear the value, but e.g. FillChar, cause the reference count must not be touched). Only if you'd really duplicate the element you'd need to take care of that.

Regards,
Sven

Hi,

perhaps a  safe, generic function for this copying could be added to the RTL. Like:

Procedure ManagedMove<T>(const source: T;var dest: T;count: SizeInt);

a) For non-managed types it would be the same as Move(source, dest, count*sizeof(T))

b) For reference counted types (like strings or interfaces or records of them), it would do:

1. finalize dest
2. normal Move
3. clear source, with fillchar

(for ranges where source and dest overlap, it should skip 1 and 3 for the overlapping elements. Like when you shift some elements in an arrays by two elements to the left, it only has to finalize the two overridden elements before the shifted elements, and clear the last two shifted elements. There is only one way to do that keeps the reference counts valid)

c) For user-defined managed, not reference counted types, it would just do
       for i := 0 to count - 1 do dest[i] := source[i]

Because you really want to use Move for strings, it can be vastly faster than updating the refcounts. But it might not work with user-defined types, like someone could build a managed type that cannot be moved. E.g.:

  type TA = record
   class operator Initialize(var a: TA);
   procedure dosomething;
end;
var globalPointer: ^TA;
class operator TA.Initialize(var a: TA);
begin
   globalPointer := @a;
end;
procedure TA.dosomething;
begin
   assert(globalPointer = @self)
end;

And when you use IsManagedType, it does not distinguish standard strings with such weird managed types.

And perhaps there could be a special attribute to mark which kind of moving is needed, e.g..

  type [moveable] TA = record
  type [referencecounted] TA = record
  type [nonmoveable] TA = record

Bye,
Benito

Benito van der Zander via fpc-pascal
schrieb am Mo., 11. Jan. 2021, 15:26:

In principle a good idea. However this is one of those cases where you'd definitely need to use constref instead of const.

And when you use IsManagedType, it does not distinguish standard strings

with such weird managed types.

You can additionally use GetTypeKind as well. Unlike TypeInfo it directly returns the TTypeKind (which for this case is enough) and is considered constant.

And perhaps there could be a special attribute to mark which kind of moving

No, thank you.

Regards,
Sven

OK, thanks for that.
I'll have to get my head around all the caveats.

Why did I ask in the first place?
Because I was doing some work on TDeque implementation (fixing a simple range check error in TDeque.IncreaseCapacity). Inside that procedure simple loop approach is used and I thought I could maybe improve that, because when we increase capacity by less than a factor 2, you cannot simply move data in one go and speed difference (with moving data > 256 MB) might be significant.

I then contemplated all the above issues (I don't want to break current implementation), but as far as I understand things TDeque cannot be safely used with managed types as it is now. There is more code that would need to finalize elements (PopBack, PopFront, Insert, Clear) and certainly it does not support Objects (classes). Which is fine, as long as you know it.

We could try to extend it, but now we have Generics.Collections etc: do we already have a better generic Deque (double ended queue) implementation somewhere?

Op 2021-01-11 om 15:26 schreef Benito van der Zander via fpc-pascal:

Then you want to simply use ismanagedtype and move().  Moving the move() to a separate generic procedure will only lead to many instantiations of what is basically a move() procedure.

I came up with this:

Assume that:
FData is defined as Array of T (T being generic)

  procedure MoveDataManaged(StartIndex: SizeUInt; Offset: SizeInt;
NrElems: SizeUInt);
  var
    i: SizeUInt;
  begin
    if Offset>0 then
    begin
      for i := StartIndex + NrElems-1 downto StartIndex do
      begin
        if IsManagedType(T) then //finalize before overwriting
          Finalize(FData[i+Offset]);
        FData[i+Offset] := FData[i];
        if IsManagedType(T) then
          Finalize(FData[i]);
        FillChar(FData[i], SizeOf(T), 0); //erase old data, not
necessary after finalize
      end;
    end
    else
    begin
      for i := 0 to NrElems-1 do
      begin
        if IsManagedType(T) then
          Finalize(FData[StartIndex+i+Offset]);
        FData[StartIndex+i+Offset] := FData[StartIndex+i];
        if IsManagedType(T) then
          Finalize(FData[StartIndex+i]);
        FillChar(FData[StartIndex+i], SizeOf(T), 0);
      end;
    end;
  end;

I tested this with T being Array of Char (so FData being an array of array of Char).
Leaving out any of the Finalize statements will make HeapTrace barf at me about unfreed memory blocks.

Does it make any sense?

Hi,

Or var, since the source might be cleared

But it could help a lot with optimizations. For moveable types it could omit calling an assignment function and just do a memory copy; and for refcounted tyes it could that when the number of references does not change.

Like a simple swap function:

procedure stringSwap(var a, b: string);
var t: string;
begin
   t := a;
   a := b;
   b := t;
end;

A smart compiler could detect that it is a refcounted type and the number of references stays the same, and thus optimize it into:

    mov    (%rdi),%rax
    mov    (%rsi),%rdx
    mov    %rdx,(%rdi)
    mov    %rax,(%rsi)
    retq

But FPC turns it into:

    begin
    push   %rbx
    push   %r12
    lea    -0x68(%rsp),%rsp
    mov    %rdi,%rbx
    mov    %rsi,%r12
    movq   $0x0,(%rsp)
    lea    0x8(%rsp),%rdx
    lea    0x20(%rsp),%rsi
    mov    $0x1,%edi
    callq  0x4324c0 <fpc_pushexceptaddr>
    mov    %rax,%rdi
    callq  0x41fba0 <fpc_setjmp>
    movslq %eax,%rdx
    mov    %rdx,0x60(%rsp)
    test   %eax,%eax
    jne    0x469191 <STRINGSWAP+97>
    t := a;
    mov    (%rbx),%rsi
    mov    %rsp,%rdi
    callq  0x428d00 <fpc_ansistr_assign>
    a := b;
    mov    (%r12),%rsi
    mov    %rbx,%rdi
    callq  0x428d00 <fpc_ansistr_assign>
    b := t;
    mov    (%rsp),%rsi
    mov    %r12,%rdi
    callq  0x428d00 <fpc_ansistr_assign>
    callq  0x432830 <fpc_popaddrstack>
    end;
    mov    %rsp,%rdi
    callq  0x428ca0 <fpc_ansistr_decr_ref>
    mov    0x60(%rsp),%rax
    test   %rax,%rax
    je     0x4691b8 <STRINGSWAP+136>
    callq  0x4329e0 <fpc_reraise>
    movq   $0x0,0x60(%rsp)
    jmp    0x469191 <STRINGSWAP+97>
    lea    0x68(%rsp),%rsp
    pop    %r12
    pop    %rbx
    retq

Then you want to simply use ismanagedtype and move().  Moving the move() to a separate generic procedure will only lead to many instantiations of what is basically a move() procedure.

The goal is to reduce instantiations.
If there are n generic (collection) classes, C1, C2, .., Cn, and k types used in the collections, T1, T2, .. Tk, there are n*k collection class instantiation C1<T1>, C1<T2>, .. C1<Tk>, C2<T1>, ... Cn<Tk> If each collection class does its own Finalize-Loop/Move/Fillchar there are also n*k of these move implementations. So like 3*n*k calls. When any collection can call the same ManagedMove, there should only be k ManagedMove instantiations and n*k calls to ManagedMove, which is only one call. So it is k + n*k calls,  which is around a third of 3*n*k

Bye,
Benito

Your simplified code would not be thread safe. A thread swap after the first instruction of

mov (%rdi), %rax

could potentially cause a problem. RAX (A) contains the pointer to the string descriptor, which includes the pointer to the actual string data and the reference count.

Should "A" have a reference count of 1, and it is assigned a new value on another thread, its reference count will decrease to zero and the string and its descriptor are both freed. The value of "A" will be set to nil.

RAX will not have been updated, so after

mov %rax, (%rsi)

"B" will be pointing to an invalid location. Its content is now dependent on memory reallocation.

In this situation, changing "B" after the return from stringSwap procedure might again cause the string to be freed (assuming the memory was not reallocated), causing a double free error.

Use of the internal procedures to increment the string reference count of both strings before your code and then decrementing the reference counts afterwards would probably work.

The same probably applies to other reference count objects.

Derek

On Thu, Jan 28, 2021 at 11:35 AM Benito van der Zander via fpc-pascal <

Hi,

Should "A" have a reference count of 1, and it is assigned a new value on another thread, its reference count will decrease to zero and the string and its descriptor are both freed. The value of "A" will be set to nil.

If the reference count is 1, there is no other thread involved.

If there was another thread, there would be a reference in this thread and in the other thread, so the reference count would be at least 2

It is exactly as thread safe as the unoptimized function. If the reference count was 1, the unoptimized function would not work either, since the thread swap might occur just before the first instruction, and the strings are freed before the function can do anyhting

Bye,
Benito

The reference count is only updated if the variable "A" was assigned to another variable. However, if "A" was global, it may still be changed by a second thread without changing its value.

program SwapTest;
uses
  Classes, SysUtils;
type
  { MyThread }
  MyThread = class(TThread)
  protected
    procedure Execute; override;
  end;
type
  PAnsiRec = ^TAnsiRec;
  TAnsiRec = Record
    CodePage    : TSystemCodePage;
    ElementSize : Word;
    {$ifdef CPU64}
    { align fields  }
    Dummy       : DWord;
    {$endif CPU64}
    Ref         : SizeInt;
    Len         : SizeInt;
    end;
var
  AStr: string;
  BStr: string;
  LThread: TThread;
function SRefCount(P : Pointer) : integer;
begin
  if P=Nil then
    Result:=0
  else
    Result:=PAnsiRec(P-SizeOf(TAnsiRec))^.Ref;
end;
procedure stringSwap(var a, b: string);
var
  t: string;
begin
  writeln('RefCount of A before assign to T=', SRefCount(pointer(a)));
  t := a;
  writeln('RefCount of A after assign to T=', SRefCount(pointer(a)));
  a := b;
  b := t;
  writeln('RefCount of A after at exit of stringSwap=',
SRefCount(pointer(a)));
  writeln('RefCount of B after at exit of stringSwap=',
SRefCount(pointer(B)));
end;

{ MyThread }

procedure MyThread.Execute;
begin
  AStr := '';
end;
begin
  LThread := MyThread.Create(false);
  writeln('Multi-threading=', IsMultiThread);
  AStr := IntToStr(123);
  UniqueString(AStr);
  BStr := IntToHex(123, 3);
  UniqueString(BStr);
  writeln('AStr="', AStr, '", Reference count before call=',
SRefCount(pointer(AStr)));
  writeln('BStr="', BStr, '", Reference count before call=',
SRefCount(pointer(BStr)));
  stringSwap(AStr, BStr);
  writeln('AStr="', AStr, '", Reference count after call=',
SRefCount(pointer(AStr)));
  writeln('BStr="', BStr, '", Reference count after call=',
SRefCount(pointer(BStr)));
  LThread.WaitFor;
  LThread.Free;
end.

The output is dependent on the the timing of the two threads, but in this case it occurred after the return of stringSwap, but you can still see the affect of the variable being cleared by the second thread. This global value could be assigned a new value, and that could also cause an issue as the reference in your simplified code could still reference the old value which may have been deleted.

Multi-threading=TRUE
AStr="123", Reference count before call=1
BStr="07B", Reference count before call=1
RefCount of A before assign to T=1
RefCount of A after assign to T=2
RefCount of A after on exit of stringSwap=1
RefCount of B after at exit of stringSwap=2
AStr="", Reference count after call=0
BStr="123", Reference count after call=1

Derek

On Sat, Jan 30, 2021 at 12:24 AM Benito van der Zander via fpc-pascal <