From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: ludo@gnu.org (Ludovic =?iso-8859-1?Q?Court=E8s?=) Newsgroups: gmane.lisp.guile.devel Subject: Re: fmatch Date: Fri, 07 May 2010 22:23:29 +0200 Message-ID: <8739y3lav2.fsf@gnu.org> References: <201005062239.32992.stefan.tampe@spray.se> <87ocgrncry.fsf@gnu.org> <201005071624.03781.stefan.tampe@spray.se> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: dough.gmane.org 1273263865 18012 80.91.229.12 (7 May 2010 20:24:25 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 7 May 2010 20:24:25 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri May 07 22:24:24 2010 connect(): No such file or directory 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.69) (envelope-from ) id 1OAU5v-0005eq-EC for guile-devel@m.gmane.org; Fri, 07 May 2010 22:24:24 +0200 Original-Received: from localhost ([127.0.0.1]:35734 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OAU5t-0005bK-MZ for guile-devel@m.gmane.org; Fri, 07 May 2010 16:24:21 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1OAU5n-0005ac-Qo for guile-devel@gnu.org; Fri, 07 May 2010 16:24:16 -0400 Original-Received: from [140.186.70.92] (port=52428 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OAU5h-0005UA-33 for guile-devel@gnu.org; Fri, 07 May 2010 16:24:14 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OAU5I-0001Fh-OW for guile-devel@gnu.org; Fri, 07 May 2010 16:23:49 -0400 Original-Received: from lo.gmane.org ([80.91.229.12]:50260) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OAU5I-0001FZ-9R for guile-devel@gnu.org; Fri, 07 May 2010 16:23:44 -0400 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1OAU5F-0005P0-0A for guile-devel@gnu.org; Fri, 07 May 2010 22:23:41 +0200 Original-Received: from acces.bordeaux.inria.fr ([193.50.110.5]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 07 May 2010 22:23:40 +0200 Original-Received: from ludo by acces.bordeaux.inria.fr with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Fri, 07 May 2010 22:23:40 +0200 X-Injected-Via-Gmane: http://gmane.org/ connect(): No such file or directory Original-Lines: 86 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: acces.bordeaux.inria.fr X-URL: http://www.fdn.fr/~lcourtes/ X-Revolutionary-Date: 18 =?iso-8859-1?Q?Flor=E9al?= an 218 de la =?iso-8859-1?Q?R=E9volution?= X-PGP-Key-ID: 0xEA52ECF4 X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc X-PGP-Fingerprint: 83C4 F8E5 10A3 3B4C 5BEA D15D 77DD 95E2 EA52 ECF4 X-OS: x86_64-unknown-linux-gnu User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) Cancel-Lock: sha1:61bvLAlnqSE0CWV5qUnLMOsU4ao= X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) 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:10322 Archived-At: Hello! stefan writes: >> > large patterns yield a speedup of 15 times acording to my tests compared >> > with (ice-9 match). >> > >> > I used guile-1.9.10. Does this release have a lot of checks compiled in >> > so that the comparison is unfair? >> >> All list/pair accessors type-check their arguments (this has always been >> the case with Guile so that Scheme code cannot yield to segfaults and >> the like.) > > usually the generated match code is somehting like > (if (pair? x) > (if (equal? x data) > (let a34 (cdr x) ...) > (goto-next)) > (goto-next)) > > And the checks are already there. So for this isolated system in should > be fine to skip the check. But I don't think it explains the speed > difference. Agreed. > The core of the matcher is a loop with a set of if's arranged so that in the > mean it will do 2-3 checks and then find the instruction, so no named labels. You mean no “labels as values” (info "(gcc) Labels as Values"), right? > the core of the code look like, > #define M_CONTINUE {pat ++; continue;} > while(1) > { > //printf("match-instruction (*)> %d\n",((int) Ix) >> 2);fflush(stdout); > if(SCM_UNLIKELY(Ix == i_cons)) > { > if(SCM_CONSP(x)) > { > PUSH(SCM_CDR(x)); > x = SCM_CAR(x); > M_CONTINUE; > } > goto return_false; > } Hmmmm. My first reaction is that I’d rather avoid complex VM instructions like this and instead focus on native compilation (AOT or JIT) when we feel like improving performance. What do you think? [...] > I also have similar code for usage in prolog like matching e.g. unfication + > backtracking I would expect at least the same speedup here. Note that for > this application a pure unwinding of the logic, similar to the match macro > will yield very bloated code and going for a targeted virtual machine will > make > for lean and efficient code. > > I hope that in the end a prolog implementation using this approach would be > 3-4 > times slower that what you have with a more targeted platform like gnu prolog. This all sounds like exciting work! > So in a sense this is a test of what you want. Compare the speed difference of > using c-based or scheme based solution. Still I expect the macth construct to > be easier to hack and improve uppon and at some point a direct match version > will win because you can compile it naitively. Well, until 1.8, the focus in Guile had been to write the “hot spots” in C, for performance. However, that doesn’t scale well and leads to a hard to maintain code base (we want to write Scheme in the first place, not C). For 2.2 and beyond, I really think the focus should be on allowing hot spots to be written in Scheme, which means compiling Scheme code natively. This would be beneficial to all Scheme code, not just this specific pattern matching construct. Thanks, Ludo’.