Re: time impact of the delta signature

Denis Corbin <[email protected]> Sat, 23 Feb 2019 10:24:16 +0100
Newsgroups	gmane.comp.sysutils.backup.dar.support
Message-ID	<[email protected]>

On 22/02/2019 23:23, Graham Cobb wrote:
> 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).
> 
> 

Of course an approximate value of root mathematical functions is
sufficient to answer the need. And as infinint type is just an integer
type that has no limit (except the available memory resources) and that
the shift left and right operations are already implemented, thus little
remains to do to add the approximate square, cube, ... root functions! :)

Thank you for this interesting approach!

Best Regards,
Denis

_______________________________________________
Dar-support mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/dar-support
signature.asc (application/pgp-signature, 833 B)