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: [PATCH] Avoid `SCM_VALIDATE_LIST ()' Date: Mon, 01 Sep 2008 23:47:34 +0200 Message-ID: <87bpz7h72h.fsf@gnu.org> References: <87hc90u9lb.fsf@gnu.org> <49dd78620809011409w8902d24q5734da921d6dfbff@mail.gmail.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1220305763 23044 80.91.229.12 (1 Sep 2008 21:49:23 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 1 Sep 2008 21:49:23 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Sep 01 23:50:18 2008 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 1KaHHt-0005zS-Ho for guile-devel@m.gmane.org; Mon, 01 Sep 2008 23:50:17 +0200 Original-Received: from localhost ([127.0.0.1]:56620 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KaHGu-0005Tl-IO for guile-devel@m.gmane.org; Mon, 01 Sep 2008 17:49:16 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1KaHFT-0004NQ-Fu for guile-devel@gnu.org; Mon, 01 Sep 2008 17:47:47 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1KaHFR-0004Lq-PQ for guile-devel@gnu.org; Mon, 01 Sep 2008 17:47:47 -0400 Original-Received: from [199.232.76.173] (port=38887 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KaHFR-0004Lk-KY for guile-devel@gnu.org; Mon, 01 Sep 2008 17:47:45 -0400 Original-Received: from main.gmane.org ([80.91.229.2]:39686 helo=ciao.gmane.org) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1KaHFR-000257-2j for guile-devel@gnu.org; Mon, 01 Sep 2008 17:47:45 -0400 Original-Received: from list by ciao.gmane.org with local (Exim 4.43) id 1KaHFP-0004Ii-SX for guile-devel@gnu.org; Mon, 01 Sep 2008 21:47:43 +0000 Original-Received: from reverse-83.fdn.fr ([80.67.176.83]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 01 Sep 2008 21:47:43 +0000 Original-Received: from ludo by reverse-83.fdn.fr with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 01 Sep 2008 21:47:43 +0000 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 114 Original-X-Complaints-To: usenet@ger.gmane.org X-Gmane-NNTP-Posting-Host: reverse-83.fdn.fr X-URL: http://www.fdn.fr/~lcourtes/ X-Revolutionary-Date: 16 Fructidor an 216 de la =?iso-8859-1?Q?R=E9volutio?= =?iso-8859-1?Q?n?= X-PGP-Key-ID: 0xEA52ECF4 X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc X-PGP-Fingerprint: 821D 815D 902A 7EAB 5CEE D120 7FBA 3D4F EB1F 5364 X-OS: i686-pc-linux-gnu User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.2 (gnu/linux) Cancel-Lock: sha1:mq0lsl3o13Hxa8TX575crAeqYYI= X-detected-kernel: by monty-python.gnu.org: 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:7571 Archived-At: Hi Neil, "Neil Jerram" writes: >> so that they >> don't validate their input with `SCM_VALIDATE_LIST ()' since it's O(n). > > I'm afraid I don't get your rationale, because all these functions are > O(n) anyway. You're right, but it's always better to traverse the list once rather than twice. :-) It doesn't feel right to impose that overhead "just" for the sake of type-checking. Type-checking using `list?' in these cases was actually overzealous since neither RnRS nor SRFI-1 require it. Note: We could change these functions to still diagnose what `list?' diagnoses while avoiding `SCM_VALIDATE_LIST ()' such that only one list traversal is done. It boils down to implementing the tortoise and the hare in each function, as shown in the `list-copy' patch. > Did you find the use of SCM_VALIDATE_LIST () causing a problem in real > practical code? What does that mean? Real practical code using `memq' behaves just as if it called `memq' twice, that's it. Whether that is a "problem" depends on how often that happens, how long the list is, and how long you're willing to wait. :-) >> A side-effect (besides performance improvements) is that all these >> functions will now happily traverse circular lists, and will silently >> deal with dotted lists. This is acceptable behavior IMO. > > Are you sure about traversing circular lists? From my reading of your > patch, I would expect: > > (memq 'not-in-the-list some-circular-list) > => > (don't know, still waiting...) Yes, that's what I meant by "happily traverse circular lists". :-) > What do reverse* do on a circular list? What do concatenate* do? They keep reversing or concatenating---and it takes long! :-) > There are a few more specific comments below, but on balance, at the > moment, I'm seeing more disadvantages here than benefit... Again, if the disadvantage is that circular lists are not diagnosed, we can add tortoise-and-hare protection to each function while still avoiding double traversal. I'm not sure it's worth it, though. >> +** Remove argument type checking with `list?' in some list-related functions > > It's easy to read that as just "Remove argument type checking". Could > we say "Improve scalability of some list-related functions" instead, > and leave the type checking detail to the following para? Right. >> @@ -367,15 +367,19 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0, >> "@code{reverse!}") >> #define FUNC_NAME s_scm_reverse_x >> { >> - SCM_VALIDATE_LIST (1, lst); >> if (SCM_UNBNDP (new_tail)) >> new_tail = SCM_EOL; >> else >> - SCM_VALIDATE_LIST (2, new_tail); >> + SCM_ASSERT (scm_is_pair (new_tail) || SCM_NULL_OR_NIL_P (new_tail), >> + new_tail, 2, FUNC_NAME); > > Why does new_tail need to satisfy this condition? Please either add a > comment to explain, or just remove. It's a mechanical change: the code used to check for a proper list, I just changed it to check for a list (i.e., '() or a pair). > Note that if SCM_VALIDATE_CONS fails half way through the "list", the > input list will have been destructively modified such that it is > neither the same as when it started, nor a complete reversed list. Is > that a concern? (I think that was `reverse!'.) Portable RnRS code and code written without looking at `list.c' must use `list?' before calling `reverse!' to protect from such situations. So, to me, that's not a concern. Now, one could argue that there's code out there that relies on Guile's undocumented over-restriction on input arguments. That's always possible, but hopefully sufficiently rare. >> @@ -546,7 +550,8 @@ SCM_DEFINE (scm_list_copy, "list-copy", 1, 0, 0, >> SCM * fill_here; >> SCM from_here; >> >> - SCM_VALIDATE_LIST (1, lst); >> + SCM_ASSERT (scm_is_pair (lst) || SCM_NULL_OR_NIL_P (lst), >> + lst, 1, FUNC_NAME); > > Why impose this condition specifically on the head of the provided > list? So that "(list-copy 1)" raises an exception, rather than being silently ignored (as is the case with `list-copy' from `srfi-1.c'). Again, a mechanical change. Thanks, Ludo'.