[HN Gopher] How fast is rolling Karp-Rabin hashing?
       ___________________________________________________________________
        
       How fast is rolling Karp-Rabin hashing?
        
       Author : mfiguiere
       Score  : 5 points
       Date   : 2024-02-04 20:37 UTC (2 hours ago)
        
 (HTM) web link (lemire.me)
 (TXT) w3m dump (lemire.me)
        
       | ashvardanian wrote:
       | This is extremely timely! I was working on SIMD variants for
       | collision-resistant rolling-hash variants in the last few weeks
       | for the v3 release of the StringZilla library [1].
       | 
       | I have tried several 4-way and 8-way parallel variants using
       | AVX-512 DQ instructions for 64-bit integer multiplications [2] as
       | well as using integer FMA instructions on Arm NEON with 32-bit
       | multiplications [3]. The latter needs a better mixing approach to
       | be collision-resistant.
       | 
       | So far I couldn't exceed 1 GB/s/core [4], so more research is
       | needed. If you have any ideas - I am all ears!
       | 
       | [1]:
       | https://github.com/ashvardanian/StringZilla/blob/bc1869a8529...
       | 
       | [2]:
       | https://github.com/ashvardanian/StringZilla/blob/bc1869a8529...
       | 
       | [3]:
       | https://github.com/ashvardanian/StringZilla/blob/bc1869a8529...
       | 
       | [4]: https://github.com/ashvardanian/StringZilla/tree/main-
       | dev?ta...
        
       ___________________________________________________________________
       (page generated 2024-02-04 23:01 UTC)