time impact of the delta signature

Hello Denis,

  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.

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?
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).


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.

Thank you,

Andy

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