From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: stefan Newsgroups: gmane.lisp.guile.devel Subject: Re: fmatch Date: Fri, 7 May 2010 16:24:03 +0200 Message-ID: <201005071624.03781.stefan.tampe@spray.se> References: <201005062239.32992.stefan.tampe@spray.se> <87ocgrncry.fsf@gnu.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: Text/Plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-Trace: dough.gmane.org 1273245641 12302 80.91.229.12 (7 May 2010 15:20:41 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 7 May 2010 15:20:41 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri May 07 17:20:40 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 1OAPM0-0007W3-A4 for guile-devel@m.gmane.org; Fri, 07 May 2010 17:20:40 +0200 Original-Received: from localhost ([127.0.0.1]:50700 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OAP7i-0004II-Ll for guile-devel@m.gmane.org; Fri, 07 May 2010 11:05:54 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1OAP4z-0003MB-Pe for guile-devel@gnu.org; Fri, 07 May 2010 11:03:05 -0400 Original-Received: from [140.186.70.92] (port=43757 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OAP4w-0003Le-Oe for guile-devel@gnu.org; Fri, 07 May 2010 11:03:04 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OAP4u-0004uc-Nf for guile-devel@gnu.org; Fri, 07 May 2010 11:03:02 -0400 Original-Received: from spsmtp02oc.mail2world.com ([74.202.142.198]:4454) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OAP4u-0004u4-G6 for guile-devel@gnu.org; Fri, 07 May 2010 11:03:00 -0400 Original-Received: from mail pickup service by spsmtp02oc.mail2world.com with Microsoft SMTPSVC; Fri, 7 May 2010 08:02:52 -0700 auth-sender: stefan.tampe@spray.se Original-Received: from 82.182.254.46 unverified ([82.182.254.46]) by spsmtp02oc.mail2world.com with Mail2World SMTP Server; Fri, 07 May 2010 08:02:50 -0700 User-Agent: KMail/1.12.4 (Linux/2.6.31.12-0.2-desktop; KDE/4.3.5; x86_64; ; ) In-Reply-To: <87ocgrncry.fsf@gnu.org> X-OriginalArrivalTime: 07 May 2010 15:02:52.0711 (UTC) FILETIME=[5DEE3370:01CAEDF6] X-detected-operating-system: by eggs.gnu.org: Windows 2000 SP4, XP SP1+ 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:10321 Archived-At: On Friday 07 May 2010 01:59:13 pm Ludovic Court=C3=A8s wrote: > Hi Stefan, >=20 > stefan writes: > > I've been experimenting lately with an inline match construct, very much > > like using compiled regexps. >=20 > Sounds interesting. >=20 > > That is I created a tiny VM that was targeted to do matching. to show > > it consider > > > > guile> (def f ((x y 'a 'b) (+ x y))) =20 > (Such a =E2=80=98def=E2=80=99 construct would be less convenient than =E2= =80=98match=E2=80=99 IMO.) You have the full match, match-lambda etc of cause if you need it. I just use a litle syntactic sugar. > > 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? >=20 > 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=20 difference. =09 =20 > > Anyway, I will try to tweak the code even further somthing along > > > > (object-ref 1) > > (fast-match) > > (br L1) > > (br L2) > > (br L3) > > .... > > (br Ln) > > > > Here the fast-match routine can FETCH the br commands and issue them > > directly and hence one can have one compiled pattern in stead of one for > > each row in the matcher. >=20 > I don=E2=80=99t quite understand how it differs from what happens without= a > =E2=80=98fast-match=E2=80=99 instruction. Can you show the code for =E2= =80=98fast-match=E2=80=99? The core of the matcher is a loop with a set of if's arranged so that in th= e=20 mean it will do 2-3 checks and then find the instruction, so no named label= s. the core of the code look like, #define M_CONTINUE {pat ++; continue;} while(1) { =20 //printf("match-instruction (*)> %d\n",((int) Ix) >> 2);fflush(stdout= ); if(SCM_UNLIKELY(Ix =3D=3D i_cons)) { if(SCM_CONSP(x)) { PUSH(SCM_CDR(x)); x =3D SCM_CAR(x); M_CONTINUE; } goto return_false; } =20 if(SCM_UNLIKELY(Ix =3D=3D i_eq)) { pat ++; if(*pat =3D=3D x) M_CONTINUE; goto return_false; } =20 if(SCM_UNLIKELY(Ix =3D=3D i_var)) { pat ++; LOCAL_SET((SCM_UNPACK(*pat) >> 2) , x); M_CONTINUE; } =20 if(SCM_UNLIKELY(Ix =3D=3D i_pop)) { POP(x); M_CONTINUE; } ... =09 And we see the most used instructions are int the top 4 checks. I don't kno= w=20 how efficient gcc is to compile the named label method used in the guile vm= =2E=20 But this while loop is not exotic so that one should expect good assembler= =20 from=20 gcc. Also an SCM array is used which might explain some speedup. The match= =20 construct itself generats a more wordier vm instruction list as well due to= =20 the general nature of guile vm. To see the compilation ((a b) a) translates to a.id b.id '() 8 instructions!! (if (pair? x1) (let ((a (car x1)) (x2 (cdr x1))) (if (pair? x2) (let ((b (car x2))) (if (null? x2) ... a 15-16 instructions, but some inneficiency in the match algoritm maby means a factor of 3 between them, also it is brancy which seams to cost extra cycles. but 15x difference? anyway, I'm experimenting to do a directly dispatch to the correct code with=20 if(SCM_LIKELY(Ix =3D=3D i_end)) // jmp-addr { gp_end: //printf("(sp: %d =3D=3D sp_save: %d\n",sp,sp_save);fflush(stdout); int ijump =3D (*(pat+1)) >> 2; if(SCM_UNLIKELY(ijump =3D=3D 0)) { =20 scm_t_int32 offset; //ip: compiled.id
a1 b1 c1
a2 b2 c2 ... // | row =3D 0 | row =3D 1 | ... ip +=3D 3 + row * 4;=20 FETCH_OFFSET (offset); ip +=3D offset; //Store the offset for a fast lookup of the adress!!,=20 *(pat+1) =3D SCM_PACK(((scm_t_bits) ((offset + 3 * row * 4) << 2)) + 2);=20 if (offset < 0) VM_HANDLE_INTERRUPTS; } else ip +=3D (*(pat + 1)) >> 2; NEXT; } Modeilling the function data with br and obect-ref will make it possible quickly test out this idea. A in a finished solution you need to make it le= ss hacky in it's nature. 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= =20 this application a pure unwinding of the logic, similar to the match macro= =20 will yield very bloated code and going for a targeted virtual machine will= =20 make=20 for lean and efficient code. I hope that in the end a prolog implementation using this approach would be= =20 3-4 times slower that what you have with a more targeted platform like gnu prol= og. So in a sense this is a test of what you want. Compare the speed difference= of=20 using c-based or scheme based solution. Still I expect the macth construct = to=20 be easier to hack and improve uppon and at some point a direct match versio= n=20 will win because you can compile it naitively. Hope the fogg clears a little Cheers Stefan