From mboxrd@z Thu Jan 1 00:00:00 1970 To: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net> In-reply-to: Your message of "Mon, 17 Jan 2011 21:59:58 +0200." References: <20110117165024.CC7C75B04@mail.bitblocks.com> <20110117183601.567225B04@mail.bitblocks.com> From: Bakul Shah Date: Mon, 17 Jan 2011 12:30:31 -0800 Message-Id: <20110117203032.9C8455B04@mail.bitblocks.com> Subject: Re: [9fans] `mk` (from Plan9 ports) efficiency related issue Topicbox-Message-UUID: 9dd3c058-ead6-11e9-9d60-3106f5b1d025 On Mon, 17 Jan 2011 21:59:58 +0200 Ciprian Dorin Craciun 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.