Re: Poor performance of unlimited integer size

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

On 08/10/2018 06:29 AM, Denis Corbin wrote:
> 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! :)
> 

I am still in two minds about it.  It is intended to be
backup-focused, for those who like manual, simple backups, but with
more emphasis on making restoration and viewing and managing the state
of the backups easy and visible.  I'm not sure whether this should be
the separate project I've started, or a contribution to KDar which
includes dar_database style management functionality.

I should give my thanks to you for creating dar, as I was looking for
a replacement for dump/restore and it met all my needs.  Simple, easy
differential backup, able to do ad-hoc backups, backups in manageable
file archives, encryption and can reliably save ALL the files
attributes easily.  It is a software package where you can tell the
author has given a lot of thought to how it might be used and what
people might want to do, and accommodated for that and documented it wel
l.


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

Thank you for the clarification.  I didn't do the math over archives
of different sizes, and went by my initial impression.
> 
>> 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.
> 

In the FAQ about a 'slight' penalty.

http://dar.linux.free.fr/doc/FAQ.html

Under "What slice size can I use with dar?" it says "thanks to its
internal own integer type named "infinint" dar is able to handle
arbitrarily large integers. This has a slightly memory and CPU penalty
in regard to using native computer 32 or 64 bits integers, but has the
advantage to provide a long term implementation in dar."



> 
>> 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 first impression was a bug, and I was looking to migrate away from
using dar until I did some web searching and thought that maybe the
integer type was more significant than it might appear.  I was a
little concerned it might turn people off using dar if they find the
program seems to hang for 10 minutes or so while restoring a single file
.

I'm not sure under what circumstances anyone would reach the stated
limits though, unless I'm reading the website wrong and the file size
limits are not 18EB but smaller.

>> 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
> 
> 
> ----------------------------------------------------------------------
- --------
>
> 
Check out the vibrant tech community on one of the world's most
> engaging tech sites, Slashdot.org! http://sdm.link/slashdot 
> _______________________________________________ Dar-libdar_api
> mailing list [email protected] 
> https://lists.sourceforge.net/lists/listinfo/dar-libdar_api
> 

-----BEGIN PGP SIGNATURE-----

iHUEAREIAB0WIQS9XnmVf3NcHCqygFfXi6TdSq3zSAUCW21iOgAKCRDXi6TdSq3z
SF2DAQDjrCoErr8lfl5k7HX3MWz5en5zO0MsSoqenw/jgyer7AD/ctIaQaJoXgeA
5gacgUNo1V7ebG5i1Xr8yLHZh5xvFcc=
=ToBl
-----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