Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / fpc-pascal / 2015-07

Sorted map vs hash map ?

5 messages · 3 people · –

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

Serguei TARASSOV

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.

Regards,
Serguei

Reply by email

Michael Van Canneyt
to Serguei TARASSOV
Serguei TARASSOV wrote 10 lines
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.

Michael.

Reply by email

Sven Barth
to Michael Van Canneyt
"Michael Van Canneyt" wrote 8 lines
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.

Show quoted text 7 lines
> > 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

Reply by email

Michael Van Canneyt
to Sven Barth
Sven Barth wrote 34 lines
Am 21.07.2015 12:13 schrieb "Michael Van Canneyt" : > > > > 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.

Reply by email

Sven Barth
to Michael Van Canneyt
"Michael Van Canneyt" wrote 35 lines
On Tue, 21 Jul 2015, Sven Barth wrote: > Am 21.07.2015 12:13 schrieb "Michael Van Canneyt" < : >> >> >> >> >> 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'

Show quoted text 10 lines
> > 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

Show quoted text 11 lines
> 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

Reply by email