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

Re: Robin Hood Hashing for the perl core

Thread Previous | Thread Next
From:
Ed Avis
Date:
August 3, 2021 18:32
Subject:
Re: Robin Hood Hashing for the perl core
Message ID:
DM4PR11MB5247A5EA160DE3ECADCB3B969DF09@DM4PR11MB5247.namprd11.prod.outlook.com
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