Re: time impact of the delta signature

Hello,

> 
>     Il 14 febbraio 2019 alle 21.08 Denis Corbin <[email protected]> ha scritto:
> 
>     -----BEGIN PGP SIGNED MESSAGE-----
>     Hash: SHA256
> 
>     On 14/02/2019 12:24, andycapo--- via Dar-support wrote:
> 
>         > > 
> >         Surely the BLOCK_LEN could be dynamically adjusted to the file
> >         size. But for now this value simply works well.
> > 
> >     > 
>     If I correctly understand [1], using block size equal to the file size
>     reduce CPU but remove the ability to do delta patch ("[...] file copy
>     if changed"). It is suggested to rather use "sqrt(filesize)"
> 

I may have expressed in an ambiguous way: surely if the block lenght is equal exactly to the filesize, we get no benefit from the delta-diff (being the granularity equal to the file size). I was only referring to have a block lenght that is adjusted according to the file size, instead of a fixed length (in the first post about this topic I spoke of a blocksize that is about 1% the filesize).

> 
>     And another drawback is memory consumption which is increasedproportionally to this block size. This may be a problem when
>     computing delta signature for huge files.
> 

Interesting discussion the [1] you cited. I see that memory compsumption is defined as

“[...] Memory = blocksize + 16x(filesize/blocksize) [...]”

I assume the units of the coefficient "16" is Bytes. So the memory usage increases also on the number of checksum blocks (that are defined as filesize/blocksize: but each block occupies only 16 bytes? doesn't the block checksum size increase with block size?).

Anyway, if the equation is correct, the equation tells us that there exist, for each file size, a blocklenght that guarentees the minimal memory compsumption, i.e. if the block is too small or too large we encounter a memory overhead.

The "memory-optimal blocksize" BLOCK_LEN is:

BLOCK_LEN_MEMOPT = 4 x sqrt(filesize)

(I get this result by imposing that the first derivative of memory with respect to blocksize is zero and then solving for the blocksize).

In order to be more efficient in speed, it may be useful to consider a larger blocksize, let's say a factor 10 with respect to the value computed of BLOCK_LEN_MEMOPT.

> 
>     So I will avoid linking theblock size to the file size but increase the default value to 4 MB as
>     you suggest and probably add an option to let the user define this
>     value if needed.
> 
>         > > 
> >         Regards Andy
> > 
> >     > 
>     Thanks for your feedback,
> 
>     Best Regards,
>     Denis
> 
>     [1] https://sourceforge.net/p/librsync/mailman/message/480886/
> 

I agree, an option to specify the blocksize, or the multiplier FACTOR of the "memory-optimal blocksize" (i.e. BLOCK_LEN = FACTOR x BLOCK_LEN_MEMOPT), is surely the best solution.

Moreover, it should be verified if the librsync algorithms benefit from block-sizes that are power of 2 (as is rather usual in these kind of algorithms), so the BLOCK_LEN may be better rounded to the nearest power of 2.

Regards

Andy

_______________________________________________
Dar-support mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/dar-support