From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Kevin Ryde Newsgroups: gmane.lisp.guile.devel Subject: Re: Evolution & optimization of the module system Date: Thu, 22 Feb 2007 09:21:46 +1100 Message-ID: <87wt2bxibp.fsf@zip.com.au> References: <87sld4g6io.fsf@chbouib.org> <877iufhwj6.fsf@zip.com.au> <87irdyxzy3.fsf@laas.fr> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: sea.gmane.org 1172096537 899 80.91.229.12 (21 Feb 2007 22:22:17 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Wed, 21 Feb 2007 22:22:17 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Wed Feb 21 23:22:11 2007 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1HJzqk-0000MK-Vk for guile-devel@m.gmane.org; Wed, 21 Feb 2007 23:22:11 +0100 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1HJzqk-0002Og-Ck for guile-devel@m.gmane.org; Wed, 21 Feb 2007 17:22:10 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1HJzqf-0002K1-B4 for guile-devel@gnu.org; Wed, 21 Feb 2007 17:22:05 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1HJzqd-0002Gg-7w for guile-devel@gnu.org; Wed, 21 Feb 2007 17:22:04 -0500 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1HJzqd-0002GY-1y for guile-devel@gnu.org; Wed, 21 Feb 2007 17:22:03 -0500 Original-Received: from mailout2-8.pacific.net.au ([61.8.2.231] helo=mailout2.pacific.net.au) by monty-python.gnu.org with esmtp (Exim 4.52) id 1HJzqc-0006nv-45 for guile-devel@gnu.org; Wed, 21 Feb 2007 17:22:02 -0500 Original-Received: from mailproxy2.pacific.net.au (mailproxy2.pacific.net.au [61.8.2.163]) by mailout2.pacific.net.au (Postfix) with ESMTP id 4121610A36D for ; Thu, 22 Feb 2007 09:21:50 +1100 (EST) Original-Received: from localhost (ppp21E8.dyn.pacific.net.au [61.8.33.232]) by mailproxy2.pacific.net.au (Postfix) with ESMTP id DEBA32742D for ; Thu, 22 Feb 2007 09:21:52 +1100 (EST) Original-Received: from gg by localhost with local (Exim 4.63) (envelope-from ) id 1HJzqN-0001lC-4E for guile-devel@gnu.org; Thu, 22 Feb 2007 09:21:47 +1100 Mail-Copies-To: never In-Reply-To: <87irdyxzy3.fsf@laas.fr> (Ludovic =?iso-8859-1?Q?Court=E8s's?= message of "Mon, 19 Feb 2007 10:24:20 +0100") User-Agent: Gnus/5.110006 (No Gnus v0.6) Emacs/21.4 (gnu/linux) X-detected-kernel: Linux 2.6, seldom 2.4 (older, 4) X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:6542 Archived-At: ludovic.courtes@laas.fr (Ludovic Court=E8s) writes: > > Actually, `process-duplicates' is O(N*USES) _for each module used_. So > the overall duplicate processing is really O(N*USES^2). With the > patched version, the whole process is O(N*USES). That can make quite a > difference when USES > 1. It should be ok, it's only hash table lookups, which are fast. And N is normally pretty modest too. > Right, it increases the size of individual module objects. I haven't > made any measurements but I'm not sure whether it should be a concern, > given that the number of modules is not supposed to be too high (i.e., > at most a few hundreds). Any idea of an estimate of the memory occupied > by a (balanced) hash table given its number of elements? Copying the table of 2000 core bindings into every module doesn't sound good, not if it's only for once-off duplicates checking. If you want you can check the existing innermost loops are good. In process-duplicates var1 and var2 are almost always different (one of them #f usually), so getting that down to C with some sort of "hashq-intersection" or "hashq-for-each-intersection" would help a lot. I'd predict throwing a little C at bottlenecks like that will be enough. Another possibility would be to defer duplicates checking until the end of a define-module or use-modules form (or even until the end of the file), if mutual cross-checks can be done faster en-block, if you know what I mean. It could use a temporary combined hash if that helped (perhaps sharing bucket cells to save gc work). The particular "module-define!" you struck should obviously be only about USES many hash lookups (ie. about a dozen typically), most of the time, if that's not already the case. > Depends on what you mean here. Modules distributed with core Guile are > not special-cased (and shouldn't be, IMO). They're special in that we know there's no clashes between them. process-duplicates should ignore any ice-9 vs ice-9, if that doesn't happen already. _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://lists.gnu.org/mailman/listinfo/guile-devel