[fpc-pascal] Sorted map vs hash map ?

Michael Van Canneyt michael at freepascal.org
Tue Jul 21 16:32:39 CEST 2015

On Tue, 21 Jul 2015, Sven Barth wrote:

> Am 21.07.2015 12:13 schrieb "Michael Van Canneyt" <michael at freepascal.org>:
>> 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.
> You are wrong with your assumptions regarding TFPGList: it does not use
> Move(). The base implementation in TFPSList does, but the generic class
> overrides that with an assignment. Otherwise for example Strings wouldn't
> work with TFPGList.

I am glad it is not as bad as I thought :)


More information about the fpc-pascal mailing list