Poor performance of unlimited integer size

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

Hello,

I am developing a front end for Dar which is intended not just to
provide a graphical way of creating archive, but also provide basic
backup management.  The application will be written using the Qt
toolkit and using libdar directly.

I note that the version of dar compiled for Fedora uses the unlimited
integer size.  The performance of dar on archives with large numbers
of files is not satisfactory, and would unfortunately also mean that
the graphical application would stall and delay.

The following command on an archive containing about 1 million files
takes 10 minutes.

$ time /usr/bin/dar -l root > /dev/null

/usr/bin/dar -l root > /dev/null  615.30s user 1.81s system 107% cpu
9:31.64 total

Memory usage peaks at 2124MB.


This delay is seen when listing, when scanning a reference archive
when creating a differential backup or when adding the archive to a
dar_manager database.  It also causes a delay when extracting a file,
which kind of defeats the purpose of having random access to files.
It would probably take as long to extract a file from a compressed
tarball.

It also means that dar cannot complete a backup of my root directory
on my laptop with 2G of RAM.

I compiled dar 2.5.16 with the --enable-mode=64 option, and the
performance greatly increased.

For the exact same archive, using 64 bit integers.

$ time /usr/bin/dar -l root > /dev/null

dar -l root > /dev/null  28.89s user 0.48s system 97% cpu 30.253 total

A 20x speed increase.

Memory usage peaked at 879MB, still high, but far better.  dar_manager
operations were faster, but still slow.

For smaller archives, the difference is less noticable.  It seems that
dar operations increase exponentially in CPU time as the number of
files increase.  For smaller archives, the difference was less
noticeable, but still there.

The dar website seems to suggest that the cost of infinint is modest,
but my testing indicates that for what would be a regular backup
scenario, the cost is high.

Looking at the page listing the limitations, the limitations of 64 bit
integers seems to far, far exceed what is required, and what
technology today can support anyway, and likely what technology for
many years to come can support.

I suggest that inifint as an integer type should not be the default.
It add in some cases unacceptable costs for no practical gain.  While
some distributors compile with 64 bit integers (MacOSX brew), other
use the default (Fedora) which leads to a dar binary which people may
consider broken or buggy.

My other question is that the API uses infinint for values internally.
 How does a libdar compiled with 64 bit integers impact what is
returned from methods returning an infinint?  I plan to possible use a
linked-in libdar compiled with 64 bit integers to ensure good
performance.  Does infinint convert internall from a native 64 bit to
an infinint type?

Thanks,
Dennis
-----BEGIN PGP SIGNATURE-----

iHUEAREIAB0WIQS9XnmVf3NcHCqygFfXi6TdSq3zSAUCW2wnSAAKCRDXi6TdSq3z
SC2DAQDaySQTiVL/8UPGjazwEhUn3N8SrC7yjuRFNXgb6sMW+gEAoO9SUPoXQk2g
u4ldwdE8HdjDf/AGfskWWBIpnjM2oNY=
=G8bn
-----END PGP SIGNATURE-----

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot