bug#6524: du now uses less than half as much memory, sometimes

[Jim Meyering]

Jim Meyering wrote:
> Jim Meyering wrote:
>> This is just a preliminary heads-up.  At least one detail must be
>> addressed before I push: I haven't written justification for the
>> change to hash.c (I confess that I don't remember -- parts of this
>> change date back to Dec 2008 ;-)
>
> I've pushed the four change-sets I wrote.
> Here's Paul's improvement, including the touch-up changes I mentioned.
>
> Paul, one question I have is whether to include an initial_inode_set_size
> parameter in your di_set_alloc function.  That would make it more
> efficient in the event that an application happens to know in advance the
> number of inodes it will process (say if it's processing a single device
> and all of its inodes).  However, there's no rush to address that --
> you're welcome to push this as-is.
>
> Subject: [PATCH] du: improve device-inode tracking code
>
> The preceding implementation would not save space when most inode
> numbers have one of the top few bits set.  Remove that limitation
> by using a separate inode-managing set for each distinct device.

BTW, if someone can test this patch on a 32-bit system
on a tree with lots of hard-linked files that have inode numbers
of 2^32 or larger, it would be instructive to see how it compares
to the version of du before any of these changes.  I think it will
still save memory, but how does performance change in that case?