Re: string table for pathnames

[Greg McGary]

Jim Meyering <address@hidden> writes:

> Greg McGary <address@hidden> wrote:
> 
> > Hi Paul & all,
> >
> > I have a very large build system that has 20,847 *.o files, and
> > therefore the same number of *.d files containing header file
> > dependencies.  gmake stores entire contents of *.d files, leading to
> > tremendous bloat.  The aggregate size of the *.d files is approx 60 MB
> > (approx 2.25 million entries), yet there is only approx 260 KB (approx
> > 7500 entries) of unique content.
> >
> > I dearly wish for a string table to eliminate the redundancy.
> > I think a Patricia trie would work well for this application.

FYI, a colleague whipped-up a Patricia trie implementation and we
compared its performance with the hash-tables already in gmake.  There
was no significant difference in performance, so there's no
justification for adding another algorithm to gmake when the existing
one does the trick.  For the dataset in question (the 60 MB of strings
mentioned above), CPU time to index was on the order of 2 seconds on a
800 Mhz Athlon--not at all significant for a process whose file I/O
can take a small number of minutes to a networked filer.

> Hi Greg!

Hi Jim!

> I learned about `judy arrays' just recently
> 
>   http://judy.sourceforge.net/
> 
> It looks like they might be useful for lots of things.

Thanks, I'll have a look!

Greg