[fpc-pascal] Sorted map vs hash map ?

[Sven Barth]

Am 21.07.2015 16:33 schrieb "Michael Van Canneyt" <michael at freepascal.org>:
>
>
>
> 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 :)
>

I had the same feeling as you when I looked at the code the first time, but
then I found out how it is really intended ^^

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