Re: Poor performance of unlimited integer size

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

On 09/08/2018 13:37, Dennis Katsonis wrote:
> Hello,

Hello Dennis,

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

nice! :)

Be aware that next to come major release 2.6.0 brings some API
re-design to simplify the use (less libdar specify auxiliary types)
and added new features. though there will be the same API in the
specific 'libdar5' namespace and I will be available to help you
migrating to the API v6 upon request.

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

this is know limitation of the 'infinint' dar/libdar flavor
http://dar.linux.free.fr/doc/Limitations.html


> 
> 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 memory requirement is not exponential but proportional to the
number of file saved. The CPU requirement is rawly proportional to the
volume of data to treat (CRC computation, compression, encryption,
...). This is true for both 64 bits and infinint flavors, though the
infinint flavor does not rely on CPU integer operation where from its
slowness.


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

Where have you read that? This should be an error to be fixed.

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

... that's to be considered, though there is warning at compilation
time when you compile using infinint... thus, if the one that compile
does not even read that warning, he will neither read documentation,
limitations and will blindly complain for any problem he will meet,
such people drain a lot of time and are always unsatisfied at the
end... so that's usually a good thing for me they do not use dar, it
saves me time to do more interesting things than trying to justify and
explain ...

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

Well, that's correct...

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

infinint and 64 bits flavors only differ by the way the "infinint"
class is implemented. infinint is an alias (typedef if you prefer) to
either "class real_infinint" or "class limitint" (32 or 64 bits
integer underneath). Both classes have the same interface with the
reste of libdar, only their implementation differ.

There is still infinint class up to the API... in APIv6 I've pushed
away a lot of internal types (including infinint) using pimpl idiom
for some classes, but that was too complicated or it would have
impacted performances to do it for all API related classes... thus the
API remains indirectly dependent on either real_infinint/limitint
class used in libdar. I other words, if you program has been
dynamically linked with libdar64 it won't be possible to have it
dynamically linked with libdar (relying on infinint), at least today.
I have not done the test with APIv6 but I pretty sure it wont work.

> 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?
Not exactly. both classes (limitint and real_infinint) do the same
thing in particular they store/read integers the same way into a dar
archive. So the resulting archive is the same. If an integer is too
large to be handled by class limitint, the class will detect overflow
during arithmetic operation or while reading integer from an archive
and libdar will abort with an Elimitint exception.

Historically libdar relied on real_infinint (class was named infinint
at that time) but due to poor performances the limitint class has been
created to be substitued to class infinint (now renamed as
real_infinint). Internally dar does not directly manipulate 64 bits
intergers, for dates, for sizes, for offset, for anything, unless when
dealing with system calls and library calls, where the "infinint"
class has the ability to convert from and to those classical integer
types like size_t and the like.

So if your plan is to statically link your program with libdar64 there
is no issue, it will work flawlessly.

> 
> Thanks, Dennis
> 
> 

Cheers,
Denis

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIVAwUBW2ykFwgxsL0D2LGCAQiaXw/+NuIGHOGUEFR56UXzsGYm39Nv+iM4Pyx7
5KA5Xqd/vsAf0pE4mLNFlwnNVqUUXUaK6899+UYymr/Y5+myvNlfRfFp0PLilMJI
pT8XNiMhI1P6lQL17lHQuvKCbl6K2B4cG9FwzmC35Eg3nVuxsKt+N5QCSEl8WzBd
j3alkO0hK/AnyHNC4LkJJ8sdNjOyQLiLoCrMVlw2baO5XwzAzKtV39lDiRpqF9su
4Wu28UkD8ITzE0cFTrlKuBAVqGWLYT9As1pQHhKuRMj61e3j5wRZ/B/wVqByJ4ic
rClXaMRDgT3rDRWkfrOo+smTeKnlPzkmn+EexztSF9V5T8rXiGxDqXp/Ik8RgfKl
DJvvtznmqGrzKqjsnDjzAvssZwEOcYJZST/BFyraNRLqdNmhQ4inMTZ2IOVf809f
EdbVhmW8wS2l+hJjlPVr3xjWkgX4vXVag6xJwKB9FIV4SqfwcdZUwIowJGbVIKax
xX9cTQYCqr7C5x+1JUsl14rvBBXGdBtApXD/K4QACUJYjVBr2+ne4wQiy0Dq/NUG
QeqFqgqcg1vypWjYuOVi9x/On/X0haSorp4GL51NDWS/7M8KBoDi1oo6EpwvBJVd
FLC43eDWP7yK6YN2Bn221LY+MnqohGcf7stNgPgWcoCLVjwNChxxyQkKGa0g3lV3
6DYX6KGzusQ=
=7hCG
-----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