Re^4: Better Hash Tables?

I do believe that for real world applications it will be better to allocate more memory for the table than to complicate the code.

You are missing the point. In a hash table that is filled to a certain degree, there is some effort required to add a new element (or search for an existing one). Seems there was consensus over some decades that a specific algorithm was optimal (but which had not been proved), that was disproved in the paper.

A non-optimal algorithm - even on an enlarged table - is slower than the optimal one. Just because there is a measure that can easily express a 99.999% filled table does not mean you should use it. The "asymptotic behavior" is asymptotic with the table's size for any given "fillness".

Would you state there is no point in making an engine more efficient just because you can enlarge the fuel tank?

Greetings,
🐻

$gryYup$d0ylprbpriprrYpkJl2xyl~rzg??P~5lp2hyl0p$

Comment on Re^4: Better Hash Tables?

Replies are listed 'Best First'.
Re^5: Better Hash Tables? by Jenda (Abbot) on Feb 26, 2025 at 00:21 UTC
If you make the engine 1 % more efficient while at the same time it weights ten times as much and costs twenty times as much, I say, please make the tank 1 % bigger. Thank you. The algorithm suggested by the paper adds complexity and slows all adds and the advantage is better asymptotic behavior in case of hugely overfilled tables. Using this algorithm would be optimizing for situation that doesn't happen. Any even just remotely sane implementation of hashes increases the size of the table long long before this algorithm might provide any improvement. It may make sense in some special cases when the memory is the scarce resource and a slowing down all adds/searches by a constant factor is not the important thing. Possibly when the hash table is a physical processor cache or something, but that's not what Perl is for and it's not where Perl is used. Jenda 1984 was supposed to be a warning, not a manual!	[reply]

Replies are listed 'Best First'.

Re^5: Better Hash Tables?
by Jenda (Abbot) on Feb 26, 2025 at 00:21 UTC

If you make the engine 1 % more efficient while at the same time it weights ten times as much and costs twenty times as much, I say, please make the tank 1 % bigger. Thank you.

The algorithm suggested by the paper adds complexity and slows all adds and the advantage is better asymptotic behavior in case of hugely overfilled tables. Using this algorithm would be optimizing for situation that doesn't happen. Any even just remotely sane implementation of hashes increases the size of the table long long before this algorithm might provide any improvement.

It may make sense in some special cases when the memory is the scarce resource and a slowing down all adds/searches by a constant factor is not the important thing. Possibly when the hash table is a physical processor cache or something, but that's not what Perl is for and it's not where Perl is used.

Jenda
1984 was supposed to be a warning,
not a manual!

[reply]