Re: time impact of the delta signature

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 13/02/2019 14:38, andycapo--- via Dar-support wrote:
> Hello Denis,

Hello Andy,

> 
> I performed the dar archive of a file size 2.0 GB and a file 6.8
> GB (both part of a virtual machine image). I compressed the files
> separately, i.e. each archive only contain the file (respectively,
> case 1 and 2). I also tested, on the same files, the impact in
> terms of execution time, of performing the archives with the 
> "--delta sig" option (cases 3 and 4). The machine was kept mostly
> idle during tests.
> 
> Here below the results in terms of time
> 
> CASE | SIZE [GB] | SIGNATURE | TIME [s] | REL.TIME | SIGNATURE TIME
> [s] 1  |    2.0    |     NO    |     68   |   1.0    | - 2  |
> 6.8    |     NO    |    225   |   3.3    | - 
> ----------------------------------------------------------------------
- --
>
> 
3  |    2.0    |    YES    |    187   |   2.8    |  187- 68 =  119
> 4  |    6.8    |    YES    |   2169   |  31.9    | 2169-225 = 1944 
> ----------------------------------------------------------------------
- --
>
>  I'm really surprised of the time impact of the delta signature.
> 
> Here my conclusions: The two files differ by a size factor 6.8 GB /
> 2.0 GB = 3.4. The increase in execution time between run 1 and 2,
> is practically equal to the size increase. So we could conclude
> that, as expected, the compression algorithm timing is linear in
> the size of the archived file.
> 
> Instead, if we consider the cases 3 and 4 in which the "--delta
> sig" is active, the situation changes. In particular we can say
> that the the execution time increase is only due to the signature
> process. For instance the time for the signature for case 3 is
> about 187 s - 68 s = 119 s.
> 
> The signature time increase is 1944/119=16.3, so the signature
> algorithm time complexity is about O(2.28), i.e. from the size
> increase 3.4^2.28 = 16.3.

Very interesting test!

> 
> Could we do anything to keep the time complexity of the signing 
> algorithm linear in time? I'm not an expert, but for instance, if
> the length of the checksum blocks increase as the file size
> increases, may we get some advantage?

the delta signature algorithm is implemented in librsync library that
libdar relies on throught its API. Thus there is little thing I can do
about it from libdar... and splitting the files per block on which to
calculate the delta signatures will make the thing very complicated in
dar archive format as you will have to detect block boundary (adding
marks in the data flow for example), protect them against corruption,
remove these marks from the data, stick block of file data toghether
in order to restore a given file...

> Form a practical point of view, if the checksum block size is (at
> least) 1 percent of the file size I think that we could get a good
> compromise between the granularity of the delta diff and signing
> time (assuming that the complexity is due to the number of block,
> like for the par2 algorithm).
> 
> At least, I think that a switch "--delta-sig-max-size" is needed: 
> otherwise the execution time for files larger than, say, 10 GB can
> be prohibitive (I have virtual machines on unsplitted virtual
> disks, with files that are well above 50 GB).

adding a --delta-sig-max-size is pretty possible and easy, I take note
of your suggestion and add it to the todo list :-)

> 
> 
> The dar commands used are:
> 
> CASES 1 & 2:
> 
> time sudo dar -c "..." -R "..." -g "file" -va
> 
> CASES 3 & 4:
> 
> time sudo dar -c "..." -R "..." -g "file" --delta sig -va
> 
> 
> I can give you more details if needed.


In addition to avoiding compression, you could also have disabled
sparse file detection (--sparse-file-min-size 0) and tape marking
(--alter=tape-marks) to remove these two sources of computation and
get even closer to the impact of delta signature.

> 
> Thank you,
> 
> Andy
> 
> 

Regards,
Denis
-----BEGIN PGP SIGNATURE-----

iQIzBAEBCAAdFiEEOzEprx3d76WjfYGPCDGwvQPYsYIFAlxkcOEACgkQCDGwvQPY
sYLiVRAAmmyDxTxYS2EGHPobtHmhLIvpK8Q8pY1u1suqqtFVkkPdzdc6fBz258E5
gbrS6kUd2B2M4bQDgkYlBEGhhkSvFaZesGiRCV4bg6p1XVc+WBBT+r+u82bmS8YP
LcH0gu+3YIQE/PbbyCV3tvj71G14nEVZ/uAMVwytfu6mkOQPS5UZ34thp+dRo6e7
B/c+flD2/g6qAwvXnwoXLEP8lXuKBIIwvhvsjdRE8nzUyJQBqRAJRzmQpp5BYOkd
Fznzgf3bT3eJf5w5SUeDIejbK+xjfNbnudR5EF5CaRTlAHtx1R+fmVaGhLB/80lS
Zc5XNnLhh+Sshbhr+Y3NK2mqvRDJFnbxl7N4IfJ1T0I4x5TFTzAHnw5/j910SBvo
UsJBOry3WbCPKPJrRlU1R6pf+eUmRWfwr7TScYIVi0Td6RGWuhwVkFLzlk66kapu
NhpNKJa7OzGVW2vPgmoD4NlVwtTM7z1OhXb0rZJkDqwlXKtKCz+qzMGBmgm1J1/0
CYOgDVzyeTzc6ye0Vfa2Djkb5eCtq7lCR9OrZqZRkJDeZMEP3sNcTW+MtI1gGTPs
e0lbys2gmmuSA73MdCA29L4u7Z5bo2S6eqxm8xWkt0siEetK0WrDi7halhLTbkUU
K2mA8mrnEJYRHMDHFdKRWujRAUduR3bF+FX5IKkSZBNhjq/mivs=
=uj7l
-----END PGP SIGNATURE-----