Fast lookup tables - TArray.BinarySearch vs Dictionary vs binary search

[PolywickStudio 2]

On 3/17/2021 at 7:16 AM, Stefan Glienke said:

As always you again seem to only read half of what I wrote.

 

Base line (code as you posted) - running on an i5-3570K @ 3.4GHz

Get Name from ID (Search by integer):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       46         397       60         23         48         59
   50       72         474       67         28         52         59
  100      105         504       62         32         51         59

Get ID from Name (Search by string):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       21         373      106         11         25        107
   50      105         443      109         18         26        110
  100      204         487      104         23         29        103

Use equalitycomparer from Tiny.Generics.pas for TDict and Spring - running on the i5-3570K @ 3.4GHz

Get Name from ID (Search by integer):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       45         407       44         24         49         44
   50       71         468       42         27         48         42
  100       96         499       43         32         53         43

Get ID from Name (Search by string):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       21         379       26         11         27         25
   50      106         445       25         18         27         25
  100      207         483       26         22         29         27

Simply put "procedure Main;" after the CreateRandomData procedure and "end;begin Main;" before the end. - running on the i5-3570K @ 3.4GHz

Get Name from ID (Search by integer):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       28         387       27         25         32         26
   50       51         455       25         28         32         24
  100       76         487       27         32         34         27

Get ID from Name (Search by string):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       22         380       27         12         25         27
   50      105         446       24         18         28         24
  100      207         489       25         24         30         26
  
Same code as before but running on an i7-8700 @ 3.2Ghz

Get Name from ID (Search by integer):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       23         306       21         20         27         20
   50       42         355       22         24         28         20
  100       63         377       22         26         29         21

Get ID from Name (Search by string):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       17         299       16          7         18         17
   50       72         359       16         13         19         17
  100      139         383       17         21         22         18
  
Same code compiled with XE8 and also running on the i7-8700 @ 3.2GHz

Get Name from ID (Search by integer):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       26         292       22         20         24         21
   50       65         342       22         23         26         21
  100      112         355       21         25         26         23

Get ID from Name (Search by string):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       24         281       17          8         18         18
   50      116         331       18         13         20         18
  100      215         347       17         16         22         17

Edit - for bonus points - I fixed the TArray.BinarySearch case by using an IComparer that I prepared and stored as field because that a) solves the return stack buffer glitch caused my TDelegatedComparer and b) avoids producing an anonymous method every time that method is being called. Also got rid of the CompareValue call in BinarySearchByID, can use < and >.

Can I ask.

 

Do you have the source-code for your changes you made?

 

The source-code in this thread has only for the Sequenced, TArray.BinS, TDict and TSynDict,  not Spring.

 

For CustomBinS, the hash routine often access violation 'out of range' and not suitable for larger arrays...

 

On 3/17/2021 at 7:16 AM, Stefan Glienke said:

Running on the i5-3570k @ 3.4Ghz

Get Name from ID (Search by integer):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       26          64       25         21         31         27
   50       52          73       26         23         32         30
  100       77          84       25         23         34         25

Get ID from Name (Search by string):
records Sequenced  TArray.BinS  TDict  CustomBinS  TSynDict     Spring
   10       22          63       25         11         27         27
   50      105          81       24         18         27         26
  100      205          94       24         22         29         27