Re: [9fans] `mk` (from Plan9 ports) efficiency related issue

[Bakul Shah <bakul+plan9@bitblocks.com>]

On Mon, 17 Jan 2011 21:59:58 +0200 Ciprian Dorin Craciun <ciprian.craciun@gmail.com>  wrote:
>     Actually I'm using the `mk` from
> `http://swtch.com/plan9port/unix/mk-with-libs.tgz` which I'm assuming
> is an extract of the `plan9port` sources. As such in order to build it
> I had to resort to updating the Makefile, but I didit.

Look at the top 4 items:

  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 28.11      2.24     2.24        1     2.24     2.24  clrmade
 22.96      4.07     1.83        1     1.83     1.83  attribute
 22.33      5.85     1.78        1     1.78     1.78  ambiguous.clone.2
 20.45      7.48     1.63        1     1.63     1.63  cyclechk

Next look at the call graphs to see that these functions are
called 59+ million times! Significantly more times than
anything else.  These are all in src/cmd/mk/graph.c -- mk is
using simple algorithm with much worse time complexity than
is theoretically possible.

I haven't studied make algorithms much to know if one can
just compute transitive closure of the dependency matrix
upfront as that would definitely be much faster than walking
so many linked lists so many times. cycle check is then just
walking down the diagonal of TC(dependency-matrix) to find
self-dependencies. A dependency matrix is usually very sparse
so one can do better than Warshall's Algorithm with its
O(N^3) time complexity.

Not sure how any of this helps you though.... You are better
off using gnumake for maximum portability, however detestable
it might be. You have to learn just enough of it to get by.