Re: time impact of the delta signature

On 22/02/2019 20:55, Denis Corbin wrote:
> At a moment I intended to reserve low values like 2 and 3 as square
> root and cube root of the filesystem but as file size are stored as
> infinint (libdar internal type) I would have to implement those
> mathematical function for this class... and on the other hand
> computing these mathematical function for each file would cost CPU
> more than necessary.
> 
> Any idea is welcome, though :)

I have been following this discussion but have not done any analysis of
the blocksize optimisation. However, if we assume that square root, cube
root, etc are useful, I guess that this application is unlikely to need
them to be accurate. It would probably be good enough to find the index
of the top bit that is set in the file size (i.e. integer value of
logarithm to base 2), halve that (or other fractions for other roots),
and set the bit with that index in the result. In other words estimate
the square root by the value of:

exp2( floor( floor( log2 (filesize) ) /2 ) )

[Note: if it is better for the estimate to be high, rather than low,
then the floor functions can easily become ceil]

I have not looked at the implementation of the infinint type but an
approximate square root based on this would probably not be hard to
calculate, even if the logarithm and exponentiation can't be done just
by bit-shifting and requires repeated division by 2 followed by repeated
multiplication by 2.

You could, maybe, add fairly cheap integer log2 and exp2 functions to
the infinint library for this (based either on bit shifting or on
division/multiplication by 2).