[fpc-pascal] Sorted map vs hash map ?

Michael Van Canneyt michael at freepascal.org
Tue Jul 21 12:13:33 CEST 2015

On Mon, 20 Jul 2015, Serguei TARASSOV wrote:

> Hi all,
> I did a small test to compare performance of TFPGMap and TFPHashList in 
> sequential and random accessing values by keys.
> http://arbinada.com/main/en/node/1511
> The results are not the same than expected.
> In theory, the hash map should give O(1) and O(log2 N) for the sorted map.
> Any explanations and suggestions are welcome.

In my opinion there is a simple explanation:

As a general solution, using generics will always be slower than 'native' classes.
The reason is that any generic implementation which does not place restrictions on the types used,
will be forced to use CompareMem() and Move() for its implementation (as do the classes in fgl). 
Even when the generic class is otherwise optimally programmed, calling these routines will 
always be slower than a direct comparision in 2 CPU registers in case of integers/pointers.


More information about the fpc-pascal mailing list