Swap strings without reference counting

user_3212191 0
Viewed 207

In QuickSort, a lot of time is spent on the swap temp:=var[i]; var[i]:=var[j]; var[j]:=temp. When the vars are integer I time 140 msec for a large random array. When the vars are string, the time is 750 msec. It appears to me that much of the difference is caused by the need to update the reference counts in all three assignments. But is this necessary? After all, the reference counts for var[i] and var[j] will be the same before and after these three assignments. Would the following code corrupt things? (not that it solves a speed problem, but out of interest):

    // P : Pstring;
    move(values[i],P,sizeOf(Pstring));
    move(values[j],values[i],sizeOf(Pstring));
    move(P,values[i],sizeOf(Pstring));

There is no temp variable. Only the two pointers to the strings are interchanged. And if this is oké, is there a Delphi function to swap 2 pointers?

quicksort delphi string
1 Answers

What you are proposing is a well known and valid optimisation. Rather than calling the Move function it is better to perform direct assignments using casts to avoid reference counting code being generated.

var
  temp: Pointer;
.... 
temp := Pointer(var[i]);
Pointer(var[i]) := Pointer(var[j]);
Pointer(var[j]) := temp;

In order for this to work you need to be confident that no exceptions will be raised during the swap process. Simple assignments of valid memory will not lead to exceptions, so this concern can be readily dismissed.

user_5050880
Related