From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Neil Jerram" Newsgroups: gmane.lisp.guile.devel Subject: Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()' Date: Mon, 1 Sep 2008 23:09:01 +0200 Message-ID: <49dd78620809011409w8902d24q5734da921d6dfbff@mail.gmail.com> References: <87hc90u9lb.fsf@gnu.org> 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: ger.gmane.org 1220303363 15826 80.91.229.12 (1 Sep 2008 21:09:23 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 1 Sep 2008 21:09:23 +0000 (UTC) Cc: guile-devel@gnu.org To: "=?ISO-8859-1?Q?Ludovic_Court=E8s?=" Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Sep 01 23:10:16 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 1KaGf8-0002dr-4B for guile-devel@m.gmane.org; Mon, 01 Sep 2008 23:10:14 +0200 Original-Received: from localhost ([127.0.0.1]:47787 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KaGe8-0007KM-Sf for guile-devel@m.gmane.org; Mon, 01 Sep 2008 17:09:12 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1KaGe2-0007J5-Cw for guile-devel@gnu.org; Mon, 01 Sep 2008 17:09:06 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1KaGe0-0007IV-DA for guile-devel@gnu.org; Mon, 01 Sep 2008 17:09:06 -0400 Original-Received: from [199.232.76.173] (port=42390 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KaGe0-0007IS-5t for guile-devel@gnu.org; Mon, 01 Sep 2008 17:09:04 -0400 Original-Received: from rv-out-0708.google.com ([209.85.198.241]:21755) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1KaGdz-0004gI-L3 for guile-devel@gnu.org; Mon, 01 Sep 2008 17:09:04 -0400 Original-Received: by rv-out-0708.google.com with SMTP id k29so2060549rvb.6 for ; Mon, 01 Sep 2008 14:09:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to :subject:cc:in-reply-to:mime-version:content-type :content-transfer-encoding:content-disposition:references; bh=jl8pf7+gDj2WpTWOVm8+7wCm2j04Fm69/Y+n4RQPecU=; b=qe0Z6QYWHQyN1PVE8nloBOaQYLMd8A9Tv5WA9H4bE5t8IZfS1vy9bQSeeR1ZL+DHif jDJPrw2LTt+ZRLwgMqe8qymI9+0l9PMjPip2IlnC8z9BN8Mp4A05FkeSzDt1ubus/zdb 9Eb0qAZOot0zUycFhqP8VkYQVWZegWG7Jj7AU= DomainKey-Signature: a=rsa-sha1; c=nofws; d=googlemail.com; s=gamma; h=message-id:date:from:to:subject:cc:in-reply-to:mime-version :content-type:content-transfer-encoding:content-disposition :references; b=Nxwfpm3wEb71EYMS2zRcpD1d0hmlbKKQqdoAYogjtpiPZeVc8GIEtmPbsI/LKsFbA8 guf3utLoycEnIyTZho4AhwezAMQWb7zXIS4PuKj/8M2KfymVdzzNU7sILoDOjrCduQmD fF5U4e5+gXg11WvHCI0RDtVuE3gMMriiTRf44= Original-Received: by 10.140.201.1 with SMTP id y1mr3683253rvf.200.1220303341812; Mon, 01 Sep 2008 14:09:01 -0700 (PDT) Original-Received: by 10.141.177.4 with HTTP; Mon, 1 Sep 2008 14:09:01 -0700 (PDT) In-Reply-To: <87hc90u9lb.fsf@gnu.org> Content-Disposition: inline X-detected-kernel: by monty-python.gnu.org: Linux 2.6 (newer, 2) 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:7570 Archived-At: 2008/9/1 Ludovic Court=E8s : > Hello, > > This is a followup to this discussion: > > http://thread.gmane.org/gmane.lisp.guile.devel/7194 > > The attached patch changes several list-related functions reverse!, memq, memv, member, filter, filter! SRFI-1: concatenate, concatenate!, member, remove, remove! > 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. (For reverse*, filter* and concatenate* I believe this is obvious. For mem* and remove*, they should always be O(n) in practice because it would be stupid to design a list structure where the element being looked for or removed was not equally likely to be anywhere along the list.) I know you gave an example in the above-referenced thread, but IMO that was a pathological one. Did you find the use of SCM_VALIDATE_LIST () causing a problem in real practical code? > 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) =3D> (don't know, still waiting...) :-) What do reverse* do on a circular list? What do concatenate* do? There are a few more specific comments below, but on balance, at the moment, I'm seeing more disadvantages here than benefit... Regards, Neil > diff --git a/NEWS b/NEWS > index c2bed17..cfcd43b 100644 > --- a/NEWS > +++ b/NEWS > @@ -56,6 +56,13 @@ When you use GDS to evaluate Scheme code from Emacs, y= ou can now use > This makes these internal functions technically not callable from > application code. > > +** Remove argument type checking with `list?' in some list-related funct= ions 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? > + > +Several list-related functions (e.g., `memq', `list-copy', etc.) used > +R5RS `list?' to validate their arguments. However, `list?' has linear > +complexity, so these functions have been changed to not resort to > +`list?'. > + > ** `guile-config link' now prints `-L$libdir' before `-lguile' > ** Fix memory corruption involving GOOPS' `class-redefinition' > ** Fix build issue on Tru64 and ia64-hp-hpux11.23 (`SCM_UNPACK' macro) > diff --git a/libguile/list.c b/libguile/list.c > index a1a79a4..8b0a2e4 100644 > --- a/libguile/list.c > +++ b/libguile/list.c > @@ -1,4 +1,4 @@ > -/* Copyright (C) 1995,1996,1997,2000,2001,2003,2004 > +/* Copyright (C) 1995,1996,1997,2000,2001,2003,2004,2008 > * Free Software Foundation, Inc. > * > * This library is free software; you can redistribute it and/or > @@ -367,15 +367,19 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0, > =09 "@code{reverse!}") > #define FUNC_NAME s_scm_reverse_x > { > - SCM_VALIDATE_LIST (1, lst); > if (SCM_UNBNDP (new_tail)) > new_tail =3D SCM_EOL; > else > - SCM_VALIDATE_LIST (2, new_tail); > + SCM_ASSERT (scm_is_pair (new_tail) || SCM_NULL_OR_NIL_P (new_tail), > +=09=09new_tail, 2, FUNC_NAME); Why does new_tail need to satisfy this condition? Please either add a comment to explain, or just remove. > while (!SCM_NULL_OR_NIL_P (lst)) > { > - SCM old_tail =3D SCM_CDR (lst); > + SCM old_tail; > + > + SCM_VALIDATE_CONS (1, lst); > + > + old_tail =3D SCM_CDR (lst); > SCM_SETCDR (lst, new_tail); > new_tail =3D lst; > lst =3D old_tail; 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? > @@ -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), > +=09 lst, 1, FUNC_NAME); Why impose this condition specifically on the head of the provided list? Please either explain or remove. > > newlst =3D SCM_EOL; > fill_here =3D &newlst; > @@ -613,8 +618,13 @@ SCM_DEFINE (scm_memq, "memq", 2, 0, 0, > =09 "returned.") > #define FUNC_NAME s_scm_memq > { > - SCM_VALIDATE_LIST (2, lst); > - return scm_c_memq (x, lst); > + for (; !SCM_NULL_OR_NIL_P (lst); lst =3D SCM_CDR (lst)) > + { > + SCM_VALIDATE_CONS (2, lst); > + if (scm_is_eq (SCM_CAR (lst), x)) > +=09return lst; > + } > + return SCM_BOOL_F; > } > #undef FUNC_NAME > > @@ -629,9 +639,9 @@ SCM_DEFINE (scm_memv, "memv", 2, 0, 0, > =09 "returned.") > #define FUNC_NAME s_scm_memv > { > - SCM_VALIDATE_LIST (2, lst); > for (; !SCM_NULL_OR_NIL_P (lst); lst =3D SCM_CDR (lst)) > { > + SCM_VALIDATE_CONS (2, lst); > if (! scm_is_false (scm_eqv_p (SCM_CAR (lst), x))) > =09return lst; > } > @@ -650,9 +660,9 @@ SCM_DEFINE (scm_member, "member", 2, 0, 0, > =09 "empty list) is returned.") > #define FUNC_NAME s_scm_member > { > - SCM_VALIDATE_LIST (2, lst); > for (; !SCM_NULL_OR_NIL_P (lst); lst =3D SCM_CDR (lst)) > { > + SCM_VALIDATE_CONS (2, lst); > if (! scm_is_false (scm_equal_p (SCM_CAR (lst), x))) > =09return lst; > } > @@ -884,9 +894,11 @@ SCM_DEFINE (scm_filter, "filter", 2, 0, 0, > SCM walk; > SCM *prev; > SCM res =3D SCM_EOL; > + > SCM_ASSERT (call, pred, 1, FUNC_NAME); > - SCM_VALIDATE_LIST (2, list); > - > + SCM_ASSERT (scm_is_pair (list) || SCM_NULL_OR_NIL_P (list), > +=09 list, 2, FUNC_NAME); Same comment as above. > + > for (prev =3D &res, walk =3D list; > scm_is_pair (walk); > walk =3D SCM_CDR (walk)) > @@ -910,9 +922,11 @@ SCM_DEFINE (scm_filter_x, "filter!", 2, 0, 0, > scm_t_trampoline_1 call =3D scm_trampoline_1 (pred); > SCM walk; > SCM *prev; > + > SCM_ASSERT (call, pred, 1, FUNC_NAME); > - SCM_VALIDATE_LIST (2, list); > - > + SCM_ASSERT (scm_is_pair (list) || SCM_NULL_OR_NIL_P (list), > +=09 list, 2, FUNC_NAME); Same comment as above. > + > for (prev =3D &list, walk =3D list; > scm_is_pair (walk); > walk =3D SCM_CDR (walk))