Re: catalogue/directory: sorted set instead of vector

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hello Thomas,

Thomas Jacob a =E9crit :
> Hey Dennis,
> =

> I have come across a performance issue in DAR 2.3.9 =

> that occurs if you archive directories with a huge number of
> files in them (and possibly do on-the-fly-isolate,
> haven't yet tested wether this is required for the
> problem to occur).

I know this problem, yes,

> =

> Specifically, after gprofing the issue, the problem
> seems to happen in the directory class defined in
> catalogue.hpp/cpp which uses the STL vector template
> to store an unsorted list of nommes, and this
> list is often linearily searched to find out if
> a given name is already present in the list,
> with the obvious consequences if the list becomes
> large.
> =

> I've replaced that with the sorted STL set template + std::string
> < operator, which has much nicer performance characteristics
> in this case, but internally sorts the elements and thus
> when reading out the members of a directory
> the order of elements will no longe be the same as when
> they were added to this data structure.
> =

> Could this cause problems with some of DAR's features?

Yes, this conflict with hard links and it may also lead the user to have
to change of slice unnecessarily.

> More specifically, is the order of the elements in the directory class
> relevant for at least one part of DAR?

the order is important first for restoration to avoid having the user
been asked slice N , then N+1, then N again, then N+1 and so on.

The order is also important for hard links, as in the 2.3.x code, the
first entry corresponding to an hard linked inode holds all the
necessary information of the inode. Subsequent entries related to this
hard linked inode just contain a reference to the first one. If when dar
reads the catalogue from the archive (thus before restoring any file)
such subsequent entry is met before the main entry, dar will not be able
to properly build the catalogue in memory. It is thus important to write
the archive catalogue --- in particular a given directory contents ---
in a well defined order, that's it the order the inode have been read
from filesystem.

> If not, would you be interested
> in a patch? Any specific requirements for a patch (at the moment
> I am simply replacing the implementation without any extra autoconf
> or runtime options to control this feature)

Now if you look at dar source code in the CVS trunk (the current
development version), you will see that the hard link support has been
mostly rewritten and does not have such main and subsequent entries to
take care of hard linked inodes. And second, the directory class holds
first a STL list in place of the STL vector you mentioned, and second it
contains a STL map for fast lookup which points to the entry of the STL
list.

For the test I had done, the performance was really improved (I remember
a factor of 40 on some large directories, but I was several month ago,
my memory may be inaccurate and some new features implemented since that
time may have change that deal). For now I am still adding features
testing them after each implementation in as much as possible aspect
they impact but I will focus on global behavior and feature interactions
 when the pre-release phase will start. I have expected a major release
(2.4.0) for the end of the year, but I'm afraid I will probably be
late... so maybe we will only have the pre-release phase before the end
of the year and the release some months after that.

> =

> In any case, the performance impact is fairly major if you archive
> a single directory with a million empty files with the following config

Yes, I can imagine... There has been some feedback on that point some
time ago (that triggered the new implementation by the way).

> (standard dar-2.3.9 --enable-debug --enable-profiling --enable-mode=3D64):
> =

> --create /tmp/dar_test
> --on-fly-isolate /tmp/dar_test_iso
> --fs-root DAR_Test/ # 1 million empty files (named 0 .. 999999)
> --slice 500M
> =

> It takes about 6 minutes to run this with my patched version,
> the unpatched version is still running (since about 2 days
> now), I am letting it finish to see what the difference in memory
> usage is.
> =

> Sure, having a million files in a directory, particularily in a Linux
> ext3 directory, is not such a clever idea, but customers are well
> customers ;)

Yes! I fully Agree! By the way, old filesystems (like first versions of
ext2) had also this behavior of heavy penalty on large directories, for
that reason many software like split their cache directory in a several
directory level tree.

> =

>     Thomas
> =

> =


Thank you for your feedback Thomas. I do change the 2.3.x releases only
for bugs to keep it stable (OK, we could open a long discussion on the
fact that this problem is or not a bug. For me it is not, the software
does what it is expected to do, slowly, yes). Instead next to come 2.4.0
is still under heavy development, thus any change can be brought there
with much more ease.

Kind Regards,
Denis.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFKpAaPpC5CI8gYGlIRAlkiAJ0f5lRLjNEFJwHZJzXkxO8SKmfCAwCgr7gO
VJ4QixJmCgX8Lz2XlgGRbtI=3D
=3Do0BG
-----END PGP SIGNATURE-----

---------------------------------------------------------------------------=
---
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day =

trial. Simplify your report design, integration and deployment - and focus =
on =

what you do best, core application coding. Discover what's new with =

Crystal Reports now.  http://p.sf.net/sfu/bobj-july