Large non-recursive make not scaling. Patch.

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Large non-recursive make not scaling. Patch.

coreybrenner
Hello,

I have been involved in a project where I set up a very large tree using
GNU make nonrecursively.  The goals I set out for the tree were to emulate
union builds, and to emulate the simplicity of recursive makefiles using
non-recursive make.

I achieved both, but ran into a problem of the main variable hash not
scaling well when setting up variable "namespaces" (in reality, a large
variable name, including relative path,) when the build went past a couple
of thousand directories.

I have implemented a PATRICIA trie for GNU Make, to take care of the
problem caused by linear probing in the global hash.  I have attached
patches against the 3.81 release, and tonight's CVS.

I would like some feedback for this patch, to see if it helps others.
What steps do I need to take to assign copyright of this code to FSF, so
that it may become a mainline part of GNU make, should it prove helpful?

Thank you,

Corey Brenner


     
_______________________________________________
Help-make mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-make

ptrie.diff-3.81 (110K) Download Attachment
ptrie.diff-cvs (103K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Large non-recursive make not scaling. Patch.

Greg Chicares-2
On 2010-03-23 07:41Z, Corey Brenner wrote:
>
> What steps do I need to take to assign copyright of this code to FSF, so
> that it may become a mainline part of GNU make, should it prove helpful?

http://www.gnu.org/prep/maintain/html_node/Copyright-Papers.html


_______________________________________________
Help-make mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-make
Reply | Threaded
Open this post in threaded view
|

Re: Large non-recursive make not scaling. Patch.

coreybrenner
Hi, and thanks for the pointer.

I don't see anything like an "assign.future.program" which, I gather from
context, is what I would be looking for on the savannah site suggested by
the link you sent.

Can the GNU Make maintainer send me a request?  Is that still Paul Smith?

Thanks,

--Corey

--- On Tue, 3/23/10, Greg Chicares <[hidden email]> wrote:

> From: Greg Chicares <[hidden email]>
> Subject: Re: Large non-recursive make not scaling.  Patch.
> To: "Corey Brenner" <[hidden email]>
> Cc: [hidden email]
> Date: Tuesday, March 23, 2010, 7:43 AM
> On 2010-03-23 07:41Z, Corey Brenner
> wrote:
> >
> > What steps do I need to take to assign copyright of
> this code to FSF, so
> > that it may become a mainline part of GNU make, should
> it prove helpful?
>
> http://www.gnu.org/prep/maintain/html_node/Copyright-Papers.html
>


     


_______________________________________________
Help-make mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-make
Reply | Threaded
Open this post in threaded view
|

Re: Large non-recursive make not scaling. Patch.

Paul Smith-20
In reply to this post by coreybrenner
On Tue, 2010-03-23 at 00:41 -0700, Corey Brenner wrote:
> I achieved both, but ran into a problem of the main variable hash not
> scaling well when setting up variable "namespaces" (in reality, a
> large variable name, including relative path,) when the build went
> past a couple of thousand directories.
>
> I have implemented a PATRICIA trie for GNU Make, to take care of the
> problem caused by linear probing in the global hash.  I have attached
> patches against the 3.81 release, and tonight's CVS.

Hi Corey; thanks for this work.  Can I just be clear: the problem you're
trying to solve is that if variable names themselves are very large then
computation of the hash alone can add considerable time to the lookup,
is that right?  That's what I assume from the fact that you're using a
PATRICIA trie.

I would love to see some kind of comparison of time/space tradeoffs
(some people have LOTS AND LOTS of variables, and I wonder what the
storage efficiency is for the trie vs. the simple open hash).  Doesn't
have to be anything formal but if you had some runs, maybe using
valgrind or even just GNU libc's heap statistics functions, that showed
memory usage differences for larger projects, and/or performance
differences, that would be very nice!



_______________________________________________
Help-make mailing list
[hidden email]
http://lists.gnu.org/mailman/listinfo/help-make