Re: crush: straw is dead, long live straw2

[Thorsten Behrens <tbehrens@suse.com>]

[-- Attachment #1: Type: text/plain, Size: 976 bytes --]

Sage Weil wrote:
> Calculating the ln() function is a bit annoying because it is a floating 
> point function and CRUSH is all fixed-point arithmetic (integer-based).  
> The current draft implementation uses a 128 KB lookup table (2 bytes per 
> entry for 16 bits of input precision).  It seems to be about 25% slower 
> than the original straw code in my simple microbenchmark, but I'm not sure 
> that's a number we should trust since it loops through a zillion inputs 
> and will pull most of the lookup table into the processor caches.
> 
> We could probably try a few others things:
> 
[snip]

My Hacker's Delight copy has a number of further variants (on
pp. 215), unfortunately only covering log_2 (which is trivially the
number of leading zeros in the binary representation) and log_10. But
since the logarithms are simply related by a multiplicative constant,
something clever might be doable here with a bit of thinking.

Cheers,

-- Thorsten

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 966 bytes --]