From unknown Tue Jun 24 05:10:15 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#17049 <17049@debbugs.gnu.org> To: bug#17049 <17049@debbugs.gnu.org> Subject: Status: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST Reply-To: bug#17049 <17049@debbugs.gnu.org> Date: Tue, 24 Jun 2025 12:10:15 +0000 retitle 17049 [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST reassign 17049 guile submitter 17049 David Kastrup severity 17049 wishlist tag 17049 notabug patch thanks From debbugs-submit-bounces@debbugs.gnu.org Thu Mar 20 07:23:26 2014 Received: (at submit) by debbugs.gnu.org; 20 Mar 2014 11:23:26 +0000 Received: from localhost ([127.0.0.1]:41907 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQb4H-0000FB-N7 for submit@debbugs.gnu.org; Thu, 20 Mar 2014 07:23:26 -0400 Received: from eggs.gnu.org ([208.118.235.92]:57707) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQb4E-0000F0-Q7 for submit@debbugs.gnu.org; Thu, 20 Mar 2014 07:23:23 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WQb49-0002NN-B9 for submit@debbugs.gnu.org; Thu, 20 Mar 2014 07:23:22 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50,T_RP_MATCHES_RCVD autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:55211) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQb49-0002NH-7t for submit@debbugs.gnu.org; Thu, 20 Mar 2014 07:23:17 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:59412) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQb48-0007kz-3H for bug-guile@gnu.org; Thu, 20 Mar 2014 07:23:17 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WQb47-0002Mz-62 for bug-guile@gnu.org; Thu, 20 Mar 2014 07:23:16 -0400 Received: from fencepost.gnu.org ([208.118.235.10]:41710) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQb47-0002Mv-2U for bug-guile@gnu.org; Thu, 20 Mar 2014 07:23:15 -0400 Received: from localhost ([127.0.0.1]:47340 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQb46-00084z-J2; Thu, 20 Mar 2014 07:23:14 -0400 Received: by lola (Postfix, from userid 1000) id 34F38E08C6; Thu, 20 Mar 2014 12:23:14 +0100 (CET) From: David Kastrup To: bug-guile@gnu.org Subject: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST Date: Thu, 20 Mar 2014 12:23:02 +0100 Message-Id: <1395314582-22733-1-git-send-email-dak@gnu.org> X-Mailer: git-send-email 1.9.1 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: submit Cc: David Kastrup X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) Since reverse! is often used during list creation in C, an unvalidating version could improve efficiency. However, a validating version without the cost of validation also speeds up existing code and does not require tradeoffs. In contrast to most list operations, reverse! cannot get stuck in an infinite loop but arrives back at the start when given an eventually or fully circular list. Because of that, one can save the cost of an upfront proper list check at the price of having to do a double reversal in the error case. Signed-off-by: David Kastrup --- libguile/list.c | 45 ++++++++++++++++++++++++++++++++++++++------- 1 file changed, 38 insertions(+), 7 deletions(-) diff --git a/libguile/list.c b/libguile/list.c index 1f44ad0..8cbdfcf 100644 --- a/libguile/list.c +++ b/libguile/list.c @@ -374,18 +374,49 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0, "@code{reverse!}") #define FUNC_NAME s_scm_reverse_x { - SCM_VALIDATE_LIST (1, lst); + SCM oldlst = lst; + SCM tail = SCM_BOOL_F; + if (SCM_UNBNDP (new_tail)) new_tail = SCM_EOL; - while (!SCM_NULL_OR_NIL_P (lst)) + if (SCM_NULL_OR_NIL_P (lst)) + return new_tail; + + SCM_VALIDATE_CONS (1, lst); + + /* SCM_VALIDATE_LIST would run through the whole list to make sure it + is not eventually circular. In contrast to most list operations, + reverse! cannot get stuck in an infinite loop but arrives back at + the start when given an eventually or fully circular list. Because + of that, we can save the cost of an upfront proper list check at + the price of having to do a double reversal in the error case. + */ + + do { + SCM old_tail = SCM_CDR (lst); + SCM_SETCDR (lst, tail); + tail = lst; + lst = old_tail; + } while (scm_is_pair (lst)); + + if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst))) { - SCM old_tail = SCM_CDR (lst); - SCM_SETCDR (lst, new_tail); - new_tail = lst; - lst = old_tail; + SCM_SETCDR (oldlst, new_tail); + return tail; } - return new_tail; + + /* We did not start with a proper list. Undo the reversal. */ + + do { + SCM old_tail = SCM_CDR (tail); + SCM_SETCDR (tail, lst); + lst = tail; + tail = old_tail; + } while (scm_is_pair (tail)); + + scm_wrong_type_arg (FUNC_NAME, 1, lst); + return oldlst; } #undef FUNC_NAME -- 1.9.1 From debbugs-submit-bounces@debbugs.gnu.org Thu Mar 20 07:38:48 2014 Received: (at 17049) by debbugs.gnu.org; 20 Mar 2014 11:38:48 +0000 Received: from localhost ([127.0.0.1]:41916 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQbJ9-0001mJ-Ot for submit@debbugs.gnu.org; Thu, 20 Mar 2014 07:38:47 -0400 Received: from fencepost.gnu.org ([208.118.235.10]:40224) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQbJ7-0001mA-2Q for 17049@debbugs.gnu.org; Thu, 20 Mar 2014 07:38:45 -0400 Received: from localhost ([127.0.0.1]:47531 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQbJ6-0007To-HV for 17049@debbugs.gnu.org; Thu, 20 Mar 2014 07:38:44 -0400 Received: by lola (Postfix, from userid 1000) id 1B2CAE08C6; Thu, 20 Mar 2014 12:38:44 +0100 (CET) From: David Kastrup To: 17049@debbugs.gnu.org Subject: PostScriptum: Date: Thu, 20 Mar 2014 12:38:44 +0100 Message-ID: <87y505drqz.fsf@fencepost.gnu.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: 17049 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) The final return statement cannot actually be reached, it is basically there for silencing compilers. If it is left in place, it should probably rather "return" the equivalent `lst' in order to keep the function from retaining `oldlst' unnecessarily. Holler if you want a patch amended accordingly. -- David Kastrup From debbugs-submit-bounces@debbugs.gnu.org Thu Mar 20 10:19:18 2014 Received: (at 17049) by debbugs.gnu.org; 20 Mar 2014 14:19:18 +0000 Received: from localhost ([127.0.0.1]:42370 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQdoT-0006Ah-Ej for submit@debbugs.gnu.org; Thu, 20 Mar 2014 10:19:17 -0400 Received: from fencepost.gnu.org ([208.118.235.10]:43294) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQdoR-0006AZ-Iu for 17049@debbugs.gnu.org; Thu, 20 Mar 2014 10:19:16 -0400 Received: from localhost ([127.0.0.1]:50601 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQdoQ-0005cm-Tf; Thu, 20 Mar 2014 10:19:15 -0400 Received: by lola (Postfix, from userid 1000) id 88EBEE08C6; Thu, 20 Mar 2014 15:19:14 +0100 (CET) From: David Kastrup To: 17049@debbugs.gnu.org Subject: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST Date: Thu, 20 Mar 2014 15:19:09 +0100 Message-Id: <1395325149-23272-1-git-send-email-dak@gnu.org> X-Mailer: git-send-email 1.9.1 X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: 17049 Cc: David Kastrup X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) Since reverse! is often used during list creation in C, an unvalidating version could improve efficiency. However, a validating version without the cost of validation also speeds up existing code and does not require tradeoffs. In contrast to most list operations, reverse! cannot get stuck in an infinite loop but arrives back at the start when given an eventually or fully circular list. Because of that, one can save the cost of an upfront proper list check at the price of having to do a double reversal in the error case. Signed-off-by: David Kastrup --- As opposed to the previous patch, there is just a single error path, making for a slightly nicer flow. libguile/list.c | 43 ++++++++++++++++++++++++++++++++++++------- 1 file changed, 36 insertions(+), 7 deletions(-) diff --git a/libguile/list.c b/libguile/list.c index 1f44ad0..da99c8e 100644 --- a/libguile/list.c +++ b/libguile/list.c @@ -374,18 +374,47 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0, "@code{reverse!}") #define FUNC_NAME s_scm_reverse_x { - SCM_VALIDATE_LIST (1, lst); + SCM oldlst = lst; + SCM tail = SCM_BOOL_F; + if (SCM_UNBNDP (new_tail)) new_tail = SCM_EOL; - while (!SCM_NULL_OR_NIL_P (lst)) + if (SCM_NULL_OR_NIL_P (lst)) + return new_tail; + + /* SCM_VALIDATE_LIST would run through the whole list to make sure it + is not eventually circular. In contrast to most list operations, + reverse! cannot get stuck in an infinite loop but arrives back at + the start when given an eventually or fully circular list. Because + of that, we can save the cost of an upfront proper list check at + the price of having to do a double reversal in the error case. + */ + + while (scm_is_pair (lst)) { + SCM old_tail = SCM_CDR (lst); + SCM_SETCDR (lst, tail); + tail = lst; + lst = old_tail; + }; + + if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst))) { - SCM old_tail = SCM_CDR (lst); - SCM_SETCDR (lst, new_tail); - new_tail = lst; - lst = old_tail; + SCM_SETCDR (oldlst, new_tail); + return tail; } - return new_tail; + + /* We did not start with a proper list. Undo the reversal. */ + + while (scm_is_pair (tail)) { + SCM old_tail = SCM_CDR (tail); + SCM_SETCDR (tail, lst); + lst = tail; + tail = old_tail; + }; + + scm_wrong_type_arg (FUNC_NAME, 1, lst); + return lst; } #undef FUNC_NAME -- 1.9.1 From debbugs-submit-bounces@debbugs.gnu.org Thu Mar 20 16:50:18 2014 Received: (at 17049) by debbugs.gnu.org; 20 Mar 2014 20:50:18 +0000 Received: from localhost ([127.0.0.1]:42705 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQjus-0004A5-Gi for submit@debbugs.gnu.org; Thu, 20 Mar 2014 16:50:18 -0400 Received: from a-pb-sasl-quonix.pobox.com ([208.72.237.25]:33012 helo=sasl.smtp.pobox.com) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQjup-00049u-8t for 17049@debbugs.gnu.org; Thu, 20 Mar 2014 16:50:16 -0400 Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 91904F722; Thu, 20 Mar 2014 16:50:14 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; s=sasl; bh=7Xj0tykA5y+MQCwVHQhv/MkIYKQ=; b=ul178T R2iCUYmLf5CT3tYp0tzlsfokJXsPud5ZnHwwE/4EewSHlvNSKnLI2vmJD3JNH0YR eSh7iRJ5RwjaAdqt76Q2H1kWPQYYgGYkXs5QA8tcaCL3YjXSCdXw3nPCtZ12wo1v wkpd3tSygijUZW9T9seOj5qoFu8/TiGS50FOc= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; q=dns; s=sasl; b=p/VtWkUMtQE4+0vtlXlzFWli61yoYCxm NHhAc2W7zYhu/r/AxW3AORpaSAaZJB4tOyfvmgNj/z8kegMtFefmL2ZGMiUgpgLd 1zL0aIjz35oz31B49sRrmIqkgiT5TxQ4V/k/JLIY9rPNI/QEVNFkyso4asDezGhP WzAy2x7X9w4= Received: from a-pb-sasl-quonix.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 870C1F721; Thu, 20 Mar 2014 16:50:14 -0400 (EDT) Received: from badger (unknown [88.160.190.192]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTPSA id C5582F720; Thu, 20 Mar 2014 16:50:13 -0400 (EDT) From: Andy Wingo To: David Kastrup Subject: Re: bug#17049: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST References: <1395314582-22733-1-git-send-email-dak@gnu.org> Date: Thu, 20 Mar 2014 21:50:11 +0100 In-Reply-To: <1395314582-22733-1-git-send-email-dak@gnu.org> (David Kastrup's message of "Thu, 20 Mar 2014 12:23:02 +0100") Message-ID: <87bnx0y4qk.fsf@pobox.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Pobox-Relay-ID: 3C381C18-B071-11E3-A8D3-873F0E5B5709-02397024!a-pb-sasl-quonix.pobox.com X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 17049 Cc: 17049@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) Hi, Thanks for the patch. What is its performance impact for your use case? On Thu 20 Mar 2014 12:23, David Kastrup writes: > + /* We did not start with a proper list. Undo the reversal. */ I'm hesitant. This is visible to other threads. (Granted there has to be significant wrongness if we get here...) Andy -- http://wingolog.org/ From debbugs-submit-bounces@debbugs.gnu.org Thu Mar 20 17:27:46 2014 Received: (at 17049) by debbugs.gnu.org; 20 Mar 2014 21:27:47 +0000 Received: from localhost ([127.0.0.1]:42717 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQkV8-0005BO-En for submit@debbugs.gnu.org; Thu, 20 Mar 2014 17:27:46 -0400 Received: from fencepost.gnu.org ([208.118.235.10]:52660) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQkV5-0005BD-Ac for 17049@debbugs.gnu.org; Thu, 20 Mar 2014 17:27:44 -0400 Received: from localhost ([127.0.0.1]:59963 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQkV4-0006MI-It; Thu, 20 Mar 2014 17:27:42 -0400 Received: by lola (Postfix, from userid 1000) id 18609E0934; Thu, 20 Mar 2014 22:27:28 +0100 (CET) From: David Kastrup To: Andy Wingo Subject: Re: bug#17049: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST References: <1395314582-22733-1-git-send-email-dak@gnu.org> <87bnx0y4qk.fsf@pobox.com> Date: Thu, 20 Mar 2014 22:27:28 +0100 In-Reply-To: <87bnx0y4qk.fsf@pobox.com> (Andy Wingo's message of "Thu, 20 Mar 2014 21:50:11 +0100") Message-ID: <8738icef27.fsf@fencepost.gnu.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: 17049 Cc: 17049@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) Andy Wingo writes: > Thanks for the patch. What is its performance impact for your use > case? Use case is a bit hard to benchmark from scratch as it's basically consing a list together and then reversing it. Of course, in a fresh session the consing is dominating the run time, while in a real-life session cons cells are usually available from a free list. Of course, one can just call scm_reverse_x in a loop without any consing at all, but that's probably a bit too much of a best use case. I could do this in order to give an upper limit to what improvement may be expected. In that case, if we are talking about large lists, I'd expect a factor of about 7:4 since the reversal takes 2 read-modify-writes per 2 elements, and tortoise and hare take 1 and 2 read cycles per 2 elements. The loops should be tight enough to fit into registers and executing cache, so those memory accesses should by far dominate the timing. And with a large list, all of those data accesses need to get their cache line at a different time. > On Thu 20 Mar 2014 12:23, David Kastrup writes: > >> + /* We did not start with a proper list. Undo the reversal. */ > > I'm hesitant. This is visible to other threads. (Granted there has to > be significant wrongness if we get here...) Uh, what of it? The other threads have to deal with the reversal in the non-error case, and it does not have well-defined multithread semantics. So what you are saying is that you want to have multithread-safe semantics for the error case exclusively if I understand correctly. But the tortoise-hare algorithm used in SCM_VALIDATE_LIST is not multithread-robust either as far as I can see. At any rate, this additional reversal only happens in the error case. Tortoise-hare is read-only, so it will be quite faster than a double reversal (which dirties the cache of the chain twice, and if we are talking about a circular list, the cache of the non-circular part even four times). So if we want to have an efficient error behavior, this change is not going to be an improvement. It seems pointless to add an extra unvalidated reversal when it would be just as fast as _this_ validated reversal. -- David Kastrup From debbugs-submit-bounces@debbugs.gnu.org Fri Mar 21 00:39:27 2014 Received: (at 17049) by debbugs.gnu.org; 21 Mar 2014 04:39:27 +0000 Received: from localhost ([127.0.0.1]:42813 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQrEs-0000q5-Gb for submit@debbugs.gnu.org; Fri, 21 Mar 2014 00:39:26 -0400 Received: from world.peace.net ([96.39.62.75]:35820) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WQrEo-0000pq-AV for 17049@debbugs.gnu.org; Fri, 21 Mar 2014 00:39:23 -0400 Received: from 209-6-91-212.c3-0.smr-ubr1.sbo-smr.ma.cable.rcn.com ([209.6.91.212] helo=yeeloong.lan) by world.peace.net with esmtpsa (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.72) (envelope-from ) id 1WQrEh-0003f2-Be; Fri, 21 Mar 2014 00:39:15 -0400 From: Mark H Weaver To: Andy Wingo Subject: Re: bug#17049: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST References: <1395314582-22733-1-git-send-email-dak@gnu.org> <87bnx0y4qk.fsf@pobox.com> Date: Fri, 21 Mar 2014 00:38:46 -0400 In-Reply-To: <87bnx0y4qk.fsf@pobox.com> (Andy Wingo's message of "Thu, 20 Mar 2014 21:50:11 +0100") Message-ID: <87pplgnp2h.fsf@yeeloong.lan> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 17049 Cc: David Kastrup , 17049@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 0.0 (/) Andy Wingo writes: > On Thu 20 Mar 2014 12:23, David Kastrup writes: > >> + /* We did not start with a proper list. Undo the reversal. */ > > I'm hesitant. This is visible to other threads. (Granted there has to > be significant wrongness if we get here...) If one thread attempts to access a list that's being destructively reversed by another thread, the behavior is undefined. Incidentally, that's also the reason that your recent changes to 'for-each' are defensible, Andy. Therefore, I strongly believe this to be a non-issue. I have yet to review this patch properly (except to notice that it does not follow the GNU coding standards w.r.t. bracket placement, which needs to be fixed), but based on the high-level description, it sounds good to me, and also quite clever. Regards, Mark From debbugs-submit-bounces@debbugs.gnu.org Fri Mar 21 12:57:25 2014 Received: (at 17049) by debbugs.gnu.org; 21 Mar 2014 16:57:25 +0000 Received: from localhost ([127.0.0.1]:43813 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WR2l1-0001Ob-7J for submit@debbugs.gnu.org; Fri, 21 Mar 2014 12:57:24 -0400 Received: from fencepost.gnu.org ([208.118.235.10]:54866) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WR2ky-0001OT-Ok for 17049@debbugs.gnu.org; Fri, 21 Mar 2014 12:57:21 -0400 Received: from localhost ([127.0.0.1]:33939 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WR2ky-0002eB-1A; Fri, 21 Mar 2014 12:57:20 -0400 Received: by lola (Postfix, from userid 1000) id 32A44E09F9; Fri, 21 Mar 2014 17:57:08 +0100 (CET) From: David Kastrup To: 17049@debbugs.gnu.org Subject: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST Date: Fri, 21 Mar 2014 17:56:58 +0100 Message-Id: <1395421018-29987-1-git-send-email-dak@gnu.org> X-Mailer: git-send-email 1.9.1 In-Reply-To: <87pplgnp2h.fsf@yeeloong.lan> References: <87pplgnp2h.fsf@yeeloong.lan> X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: 17049 Cc: David Kastrup X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) Since reverse! is often used during list creation in C, an unvalidating version could improve efficiency. However, a validating version without the cost of validation also speeds up existing code and does not require tradeoffs. In contrast to most list operations, reverse! cannot get stuck in an infinite loop but arrives back at the start when given an eventually or fully circular list. Because of that, one can save the cost of an upfront proper list check at the price of having to do a double reversal in the error case. Signed-off-by: David Kastrup --- Formatting changes. Also renamed oldlst to old_lst to match the existing variable name style better. libguile/list.c | 41 ++++++++++++++++++++++++++++++++++++----- 1 file changed, 36 insertions(+), 5 deletions(-) diff --git a/libguile/list.c b/libguile/list.c index 1f44ad0..9b2a0d7 100644 --- a/libguile/list.c +++ b/libguile/list.c @@ -374,18 +374,49 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0, "@code{reverse!}") #define FUNC_NAME s_scm_reverse_x { - SCM_VALIDATE_LIST (1, lst); + SCM old_lst = lst; + SCM tail = SCM_BOOL_F; + if (SCM_UNBNDP (new_tail)) new_tail = SCM_EOL; - while (!SCM_NULL_OR_NIL_P (lst)) + if (SCM_NULL_OR_NIL_P (lst)) + return new_tail; + + /* SCM_VALIDATE_LIST would run through the whole list to make sure it + is not eventually circular. In contrast to most list operations, + reverse! cannot get stuck in an infinite loop but arrives back at + the start when given an eventually or fully circular list. Because + of that, we can save the cost of an upfront proper list check at + the price of having to do a double reversal in the error case. + */ + + while (scm_is_pair (lst)) { SCM old_tail = SCM_CDR (lst); - SCM_SETCDR (lst, new_tail); - new_tail = lst; + SCM_SETCDR (lst, tail); + tail = lst; lst = old_tail; } - return new_tail; + + if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst))) + { + SCM_SETCDR (old_lst, new_tail); + return tail; + } + + /* We did not start with a proper list. Undo the reversal. */ + + while (scm_is_pair (tail)) + { + SCM old_tail = SCM_CDR (tail); + SCM_SETCDR (tail, lst); + lst = tail; + tail = old_tail; + } + + scm_wrong_type_arg (FUNC_NAME, 1, lst); + return lst; } #undef FUNC_NAME -- 1.9.1 From debbugs-submit-bounces@debbugs.gnu.org Fri Mar 21 13:44:13 2014 Received: (at 17049) by debbugs.gnu.org; 21 Mar 2014 17:44:13 +0000 Received: from localhost ([127.0.0.1]:43842 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WR3UK-0003re-BP for submit@debbugs.gnu.org; Fri, 21 Mar 2014 13:44:12 -0400 Received: from fencepost.gnu.org ([208.118.235.10]:55787) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1WR3UH-0003rT-LA for 17049@debbugs.gnu.org; Fri, 21 Mar 2014 13:44:10 -0400 Received: from localhost ([127.0.0.1]:34860 helo=lola) by fencepost.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WR3UG-0000cA-4E; Fri, 21 Mar 2014 13:44:08 -0400 Received: by lola (Postfix, from userid 1000) id A7F2ADF667; Fri, 21 Mar 2014 18:44:07 +0100 (CET) From: David Kastrup To: Andy Wingo Subject: Re: bug#17049: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST References: <1395314582-22733-1-git-send-email-dak@gnu.org> <87bnx0y4qk.fsf@pobox.com> Date: Fri, 21 Mar 2014 18:44:07 +0100 In-Reply-To: <87bnx0y4qk.fsf@pobox.com> (Andy Wingo's message of "Thu, 20 Mar 2014 21:50:11 +0100") Message-ID: <8738ib30rc.fsf@fencepost.gnu.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux) MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: 17049 Cc: 17049@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) --=-=-= Content-Type: text/plain Andy Wingo writes: > Hi, > > Thanks for the patch. What is its performance impact for your use case? Here is an artificial use case (I make care to get my list scattered over memory, assuming that sort! keeps the cells around). --=-=-= Content-Type: application/octet-stream Content-Disposition: attachment; filename=zoppo.scm Content-Transfer-Encoding: base64 KHVzZS1tb2R1bGVzIChzcmZpIHNyZmktMTkpIChzcmZpIHNyZmktMSkpCihkZWZpbmUgeHh4IChz b3J0ISAobWFwISByYW5kb20gKG1ha2UtbGlzdCA1MDAwMCAxMDAwMDAwMCkpIDwpKQooZGVmaW5l IHN0YXJ0LXRpbWUgKGN1cnJlbnQtdGltZSkpCihmb3ItZWFjaCAobGFtYmRhIHggKHNldCEgeHh4 IChyZXZlcnNlISB4eHgpKSkgKG1ha2UtbGlzdCAyMDAwMSkpCihkaXNwbGF5ICh0aW1lLWRpZmZl cmVuY2UgKGN1cnJlbnQtdGltZSkgc3RhcnQtdGltZSkpCgogICAgICAK --=-=-= Content-Type: text/plain The output for my version first and the default version afterwards is #