develooper Front page | perl.perl5.porters | Postings from August 2021

Re: Robin Hood Hashing for the perl core

Thread Previous | Thread Next
From:
Philip R Brenan
Date:
August 3, 2021 20:59
Subject:
Re: Robin Hood Hashing for the perl core
Message ID:
CALhwFRk0RqAFSAjWbmwOXj57=wdog=n9aH5=qT828-Ja=U5D6A@mail.gmail.com
If the proposed new hash function is "better" than the existing function
then the existing hash function is not "the best" which raises the
possibility that there might be other "better" hash functions to choose
from.  One such possibility might use multi way trees:
https://metacpan.org/dist/Tree-Multi to replace the collision chain with a
more efficient implementation  encoded using "Single Instruction, Multiple
Data": https://metacpan.org/pod/Nasm::X86#Avx512-instructions which would
be impervious to hashing attacks regardless of the seed chosen as in the
worst case the hash would degenerate to a single constant height  tree of
broad degree.

May I therefore propose that if hash functions are in fact in play: there
should be a competition to find the best hash functions currently available
today and that the best of the best should be made available to all Perl
programmers via a "use' clause that gives each Perl programmer the
opportunity to choose the best function for their specific needs?  This
would provide a powerful argument for using Perl - the only language that
puts the needs of its application programmers first and unambiguously ahead
of the needs of the programmers supporting the language.


On Tue, Aug 3, 2021 at 7:32 PM Ed Avis <ed.avis@qmaw.com> wrote:

> Thank you for posting this detailed introduction to the new hashing
> implementation.  I just wanted to remark on one thing.  Randomization of
> the iteration order isn't a goal in itself, but it serves two purposes: to
> stop attackers being able to guess the hash seed by observing the iteration
> order, and to 'teach people a lesson' and make sure they don't
> inadvertently rely on a hash key ordering that's subject to change.
>
> If the hash implementation fixed an iteration order that didn't give away
> anything about the hash seed or how to engineer collisions, then it
> wouldn't need to be randomized.  Some hash implementations allow you to
> return the keys in the order they were originally inserted, without extra
> cost.  I think that would be a very desirable feature in any replacement
> hash implementation.  If the insertion order could be preserved with only a
> small constant penalty, that would speed up and simplify code where you
> currently use the much slower Tie::IxHash, and would also speed up code
> which currently needs 'sort keys', not because alphabetical ordering is
> particularly important, but just to get deterministic output.
>
> If your new hash implementation doesn't provide an obvious way to preserve
> the insertion order of keys, and so randomization will continue to be
> necessary, then I apologize for letting out one of the bees I have in my
> bonnet.
>
> --
> Ed Avis <ed.avis@qmaw.com>
> Please ignore confidentiality stuff below this point.
>
>
> This email and any files transmitted with it are CONFIDENTIAL and are
> intended solely for the use of the individual(s) or entity to whom they are
> addressed. Any unauthorised copying, disclosure or distribution of the
> material within this email is strictly forbidden. Any views or opinions
> presented within this email are solely those of the author and do not
> necessarily represent those of PGIM Limited, QMA Wadhwani LLP or their
> affiliates unless otherwise specifically stated. An electronic message is
> not binding on its sender. Any message referring to a binding agreement
> must be confirmed in writing and duly signed. If you have received this
> email in error, please notify the sender immediately and delete the
> original. Telephone, electronic and other communications and conversations
> with PGIM Limited, QMA Wadhwani LLP and/or their associated persons may be
> recorded and retained. PGIM Limited and QMA Wadhwani LLP are authorised and
> regulated by the Financial Conduct Authority. PGIM Limited (registered in
> England No. 3809039) has its registered office at Grand Buildings, 1-3
> Strand, Trafalgar Square, London WC2N 5HR and QMA Wadhwani LLP (registered
> in England No. OC303168) has its registered office at 9th Floor, Orion
> House, 5 Upper St. Martin's Lane, London, England, WC2H 9EA.
>
> Please note that your personal information may be stored and processed in
> any country where we have facilities or in which we engage service
> providers. If you provide personal information to us by email or otherwise,
> you consent to the transfer of that information to countries outside of
> your country of residence and these countries may have different data
> protection rules than your country.
>
> To learn about our privacy policies, please use this link
> <https://www.pgim.com/disclaimer/privacy-center> to read the Privacy
> Notices.
>

Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About