[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 :)

Michael.



More information about the fpc-pascal mailing list