[fpc-pascal] Sorted map vs hash map ?

[Sven Barth]

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.

Regards,
Sven
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-pascal/attachments/20150721/37c3f371/attachment.html>