From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.lisp.guile.bugs Subject: bug#17147: [PATCH] Add versions of and/or avoiding O(n^2) argument matching Date: Thu, 05 Jun 2014 06:06:53 +0200 Message-ID: <87vbsg57aa.fsf@fencepost.gnu.org> References: <87k3ban107.fsf@fencepost.gnu.org> <1401891509-29257-1-git-send-email-dak@gnu.org> <87lhtctb5o.fsf@yeeloong.lan> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1401941294 31051 80.91.229.3 (5 Jun 2014 04:08:14 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 5 Jun 2014 04:08:14 +0000 (UTC) Cc: 17147-done@debbugs.gnu.org To: Mark H Weaver Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Thu Jun 05 06:08:08 2014 Return-path: Envelope-to: guile-bugs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WsOyF-00081p-Q5 for guile-bugs@m.gmane.org; Thu, 05 Jun 2014 06:08:07 +0200 Original-Received: from localhost ([::1]:38217 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WsOyE-00045E-Sf for guile-bugs@m.gmane.org; Thu, 05 Jun 2014 00:08:06 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:40618) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WsOyB-000454-DX for bug-guile@gnu.org; Thu, 05 Jun 2014 00:08:04 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WsOyA-0002Ah-EB for bug-guile@gnu.org; Thu, 05 Jun 2014 00:08:03 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:45723) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WsOyA-0002Ad-Bs for bug-guile@gnu.org; Thu, 05 Jun 2014 00:08:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WsOy9-00018H-SH for bug-guile@gnu.org; Thu, 05 Jun 2014 00:08:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Thu, 05 Jun 2014 04:08:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17147 X-GNU-PR-Package: guile X-GNU-PR-Keywords: Original-Received: via spool by 17147-done@debbugs.gnu.org id=D17147.14019412354272 (code D ref 17147); Thu, 05 Jun 2014 04:08:01 +0000 Original-Received: (at 17147-done) by debbugs.gnu.org; 5 Jun 2014 04:07:15 +0000 Original-Received: from localhost ([127.0.0.1]:44600 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WsOxP-00016p-11 for submit@debbugs.gnu.org; Thu, 05 Jun 2014 00:07:15 -0400 Original-Received: from fencepost.gnu.org ([208.118.235.10]:42338 ident=Debian-exim) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WsOxL-00016e-Nu for 17147-done@debbugs.gnu.org; Thu, 05 Jun 2014 00:07:12 -0400 Original-Received: from localhost ([127.0.0.1]:49645 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WsOxK-0001Mv-V9; Thu, 05 Jun 2014 00:07:11 -0400 Original-Received: by lola (Postfix, from userid 1000) id 39E60E0D19; Thu, 5 Jun 2014 06:06:53 +0200 (CEST) In-Reply-To: <87lhtctb5o.fsf@yeeloong.lan> (Mark H. Weaver's message of "Wed, 04 Jun 2014 21:09:23 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (gnu/linux) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-guile@gnu.org List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.bugs:7498 Archived-At: Mark H Weaver writes: > David Kastrup writes: > >> Fixes >> >> * module/ice-9/boot-9.scm (and, or): Add syntax rules that only do one >> pattern matching operation per and/or rather than per argument. > > Thanks, but I ended up simply changing the macros to dotted tail > patterns. It's commit 1ea8954814d124b995f2296bc6aec92adb566bc1. Still one matching operation per argument (though an O(1) rather than an O(n) one) rather than a single match. Incidentally, most other syntax rules don't degrade on ... like that because they do not do recursive matching on already matched patterns either, case in point being the cond rule. So indeed and/or have been about the worst culprits for this case. -- David Kastrup