Re: Accelerating crush with SIMD

[Loic Dachary <loic@dachary.org>]

Hi Greg,

On 29/08/2016 06:28, Gregory Farnum wrote:
> On Sun, Aug 28, 2016 at 10:59 AM, Loic Dachary <loic@dachary.org> wrote:
>> Hi,
>>
>> Could we significantly accelerate crush with SIMD instructions ? I don't remember the idea being discussed but maybe I missed it.
> 
> I think it was attempted, but using a lookup table method turned out
> to be much faster. Sage did some prototyping and then some folks from
> Intel did a lot of heavy optimization; I'd be surprised if anybody
> managed to speed up the CRUSH calculations much at this point (at
> least, without changing the fundamental math involved).
> 
> Sorry I can't be more detailed; the actual CRUSH implementation is
> something I've largely left alone. I imagine the optimization points
> become pretty clear running git blame or something though. ;)

I was not thinking of accelerating the crush hash function or the straw2 function, but to have them run simultaneously on 4/8/16 items at a time using _mm, _mm256 or _mm512 instructions[1], when possible. I'll put together a proof of concept later today to clarify what I have in mind.

Cheers

[1] https://software.intel.com/sites/landingpage/IntrinsicsGuide/
-- 
Loïc Dachary, Artisan Logiciel Libre