What does the actual TArray.Sort comparator do by default and when do you use it?

Question

In Delphi XE2 help for System.Generics.Collections.TArray.Sort , it says:

 Note: If the Comparer parameter is provided, it is used to compare elements; otherwise the default comparator for the array elements is used. 

I dug up a bit and found that the default comparator for TArray.Sort is _LookupVtableInfo from _LookupVtableInfo . Code for this

 function _LookupVtableInfo(intf: TDefaultGenericInterface; info: PTypeInfo; size: Integer): Pointer; var pinfo: PVtableInfo; begin if info <> nil then begin pinfo := @VtableInfo[intf, info^.Kind]; Result := pinfo^.Data; if ifSelector in pinfo^.Flags then Result := TTypeInfoSelector(Result)(info, size); if ifVariableSize in pinfo^.Flags then Result := MakeInstance(Result, size); end else begin case intf of giComparer: Result := Comparer_Selector_Binary(info, size); giEqualityComparer: Result := EqualityComparer_Selector_Binary(info, size); else System.Error(reRangeError); Result := nil; end; end; end; 

It is called

 IComparer<T>(_LookupVtableInfo(giComparer, TypeInfo(T), SizeOf(T))) 

I looked at it quite a bit, and I'm not quite sure that I know what he is doing. Does it just compare a bit in memory with each other or what exactly?

The second part of the question is the more general one of the situations in which you probably want to use the default comparator, or is it unlikely that you will ever want to use it?

Answer 1

The default comparison provides an implementation for many common types. In particular, it supports the following:

• Integral types: Byte , Word , Integer , etc.
• Enumerated types.
• Floating point types.
• Strings.
• Kits.
• class instances.
• Procedural Variables.
• Methods
• Options.
• Static arrays.
• Dynamic arrays.
• Interfaces
• Pointers.
• Records.

For many of these types, the default implementation is exactly what you expect. For example, for integers, enumerated types, floating-point types, the implementation uses the operators < , > and = . For string , the default implementation calls CompareStr .

For other types, the default implementation is probably less useful. For example, for records, a comparison is a binary comparison. It is very likely that you will want to provide your own comparison implementation for the record. One thing to keep track of entries is that the default resolver will compare any additions to your entry and you will never want to do this. Therefore, it is never useful for aligned recordings with additions. And I also asked the utility for records containing reference types.

For dynamic arrays, the default implementation first compares the length, and then, if the length is equal, compares the binary content of the array. Thus, this may be reasonable for arrays of simple value types. But for multidimensional dynamic arrays or arrays of reference types there are not many.

For class instances, methods, and procedural variables, interfaces by default compare operands as a pointer (two pointers in the case of methods) and perform address comparisons.

When do you want to use the default mapper? Well, you will use it when it meets your requirements for comparison. Therefore, this certainly makes sense for simple value types. In addition, you will need to make individual decisions.

Answer 2

The function you posted there is actually not a comparison function, but rather a function that returns a comparison function based on TypeInfo and SizeOf T.

After that, we see more in Generics.Defaults many functions of the form:

function Compare_ type name (Inst: Pointer; const Left, Right: Type ): Integer;

all of which have the same body (but note that the left and right are of different types)

 begin if Left < Right then Result := -1 else if Left > Right then Result := 1 else Result := 0; end; 

and finally for all remaining

 function BinaryCompare(const Left, Right: Pointer; Size: Integer): Integer; var pl, pr: PByte; len: Integer; begin pl := Left; pr := Right; len := Size; while len > 0 do begin Result := pl^ - pr^; if Result <> 0 then Exit; Dec(len); Inc(pl); Inc(pr); end; Result := 0; end; 

Answer 3

David did a great job writing a textual description of how the default mappings work, but for some of you it may be easier to follow when you see how the base code is structured (and decide if the defaults are applied).

I will only talk about Compare_ 's style of comparison. The Equals_ style works the same way.

What happens is that _LookupVtableInfo selects the IComparer interface to compare Compare_ styles (and IEqualityComparer style for Equals_ ).

Under these interfaces are not ordinary interfaces, but interface shells around the global functions of this form for the Compare_ style:

 function Compare_t<T>(Inst: Pointer; const Left, Right: T): Integer; 

and global procedures of this form for the Equals_ style:

 function Equals_t<T>(Inst: Pointer; const Left, Right: T): Integer; function GetHashCode_t<T>(Inst: Pointer; const Left, Right: T): Integer; 

The result of Compare_ style Compare_ is simple, but slightly different from -1, 0, +1, which some people might expect:

 < 0 for Left < Right = 0 for Left = Right > 0 for Left > Right 

In most cases, the implementation is very simple:

I grouped the Compare_ style functions Compare_ how they do it.

• Common types (including enumerations and Int64).
• Floating point types (Real) (including Comp and Currency).
• Short lines (from Turbo Pascal / Delphi 1 day).
• Wide lines (OLE styles).
• Methods
• Pointers (including classes, interfaces, references to classes and procedures).

(Regular types outside the range of 1, 2, 4, 8 bytes and real types outside the range of 4, 8, 10 bytes cause an error because they are illegal).

The first group simply subtracts Left from Right: integers with signature / unsigned 1 or 2 bytes long

 function Compare_I1(Inst: Pointer; const Left, Right: Shortint): Integer; function Compare_I2(Inst: Pointer; const Left, Right: Smallint): Integer; function Compare_U1(Inst: Pointer; const Left, Right: Byte): Integer; function Compare_U2(Inst: Pointer; const Left, Right: Word): Integer; Result := Left - Right; 

The second group makes a comparison:

 function Compare_I4(Inst: Pointer; const Left, Right: Integer): Integer; function Compare_I8(Inst: Pointer; const Left, Right: Int64): Integer; function Compare_U4(Inst: Pointer; const Left, Right: LongWord): Integer; function Compare_U8(Inst: Pointer; const Left, Right: UInt64): Integer; function Compare_R4(Inst: Pointer; const Left, Right: Single): Integer; function Compare_R8(Inst: Pointer; const Left, Right: Double): Integer; function Compare_R10(Inst: Pointer; const Left, Right: Extended): Integer; function Compare_RI8(Inst: Pointer; const Left, Right: Comp): Integer; function Compare_RC8(Inst: Pointer; const Left, Right: Currency): Integer; function Compare_WString(Inst: PSimpleInstance; const Left, Right: WideString): Integer; function Compare_Pointer(Inst: PSimpleInstance; Left, Right: NativeUInt): Integer; type {$IFNDEF NEXTGEN} TPS1 = string[1]; TPS2 = string[2]; TPS3 = string[3]; {$ELSE NEXTGEN} OpenString = type string; TPS1 = string; TPS2 = string; TPS3 = string; {$ENDIF !NEXTGEN} function Compare_PS1(Inst: PSimpleInstance; const Left, Right: TPS1): Integer; function Compare_PS2(Inst: PSimpleInstance; const Left, Right: TPS2): Integer; function Compare_PS3(Inst: PSimpleInstance; const Left, Right: TPS3): Integer; // OpenString allows for any String[n], see http://my.safaribooksonline.com/book/programming/borland-delphi/1565926595/5dot-language-reference/ch05-openstring function Compare_PSn(Inst: PSimpleInstance; const Left, Right: OpenString): Integer; if Left < Right then Result := -1 else if Left > Right then Result := 1 else Result := 0; function Compare_Method(Inst: PSimpleInstance; const Left, Right: TMethodPointer): Integer; var LMethod, RMethod: TMethod; begin LMethod := TMethod(Left); RMethod := TMethod(Right); if LMethod < RMethod then Result := -1 else if LMethod > RMethod then Result := 1 else Result := 0; end; 

Now we get to the interesting bits: not so direct results.

Strings use CompareStr . If you want something else, you can use TOrdinalIStringComparer

 function Compare_LString(Inst: PSimpleInstance; const Left, Right: AnsiString): Integer; function Compare_UString(Inst: PSimpleInstance; const Left, Right: UnicodeString): Integer; Result := CompareStr(Left, Right); 

BinaryCompare used for:

• binary data, including unknowns, Char / WChar, Set, Array, Record. An exception is if binary data is 1, 2 or 4 bytes in x86 and x64 and 8 bytes in x64 in size, they will be compared as integers.
• dynamic frames (be careful when they are multidimensional!).
• as a last resort (see below)

For records that can be compared, it makes sense to overload the operator and use them for comparison.

Binary data of 1, 2, 4 or 8 bytes is an exception, which will give strange results on machines with a small limb (Intel x86 and x64 and a bi-directional lever in little-endian mode):

 function Comparer_Selector_Binary(info: PTypeInfo; size: Integer): Pointer; begin case size of // NOTE: Little-endianness may cause counterintuitive results, // but the results will at least be consistent. 1: Result := @Comparer_Instance_U1; 2: Result := @Comparer_Instance_U2; 4: Result := @Comparer_Instance_U4; {$IFDEF CPUX64} // 64-bit will pass const args in registers 8: Result := @Comparer_Instance_U8; {$ENDIF} else Result := MakeInstance(@Comparer_Vtable_Binary, size); end; end; 

The rest is pure binary:

 function Compare_Binary(Inst: PSimpleInstance; const Left, Right): Integer; begin Result := BinaryCompare(@Left, @Right, Inst^.Size); end; function Compare_DynArray(Inst: PSimpleInstance; Left, Right: Pointer): NativeInt; var len, lenDiff: NativeInt; begin len := DynLen(Left); lenDiff := len - DynLen(Right); if lenDiff < 0 then Inc(len, lenDiff); Result := BinaryCompare(Left, Right, Inst^.Size * len); if Result = 0 then Result := lenDiff; end; 

As usual, the Variants are in a separate league. First attempt at VarCompareValue . If this fails, then a Compare_UString check is Compare_UString . If this fails, BinaryCompare checked. If it fails: hard luck.

 function Compare_Variant(Inst: PSimpleInstance; Left, Right: Pointer): Integer; var l, r: Variant; lAsString, rAsString: string; begin Result := 0; // Avoid warning. l := PVariant(Left)^; r := PVariant(Right)^; try case VarCompareValue(l, r) of vrEqual: Exit(0); vrLessThan: Exit(-1); vrGreaterThan: Exit(1); vrNotEqual: begin if VarIsEmpty(L) or VarIsNull(L) then Exit(1) else Exit(-1); end; end; except // if comparison failed with exception, compare as string. try lAsString := PVariant(Left)^; rAsString := PVariant(Right)^; Result := Compare_UString(nil, lAsString, rAsString); except // if comparison fails again, compare bytes. Result := BinaryCompare(Left, Right, SizeOf(Variant)); end; end; end;