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#17049: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST Date: Thu, 20 Mar 2014 22:27:28 +0100 Message-ID: <8738icef27.fsf@fencepost.gnu.org> References: <1395314582-22733-1-git-send-email-dak@gnu.org> <87bnx0y4qk.fsf@pobox.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1395350953 28798 80.91.229.3 (20 Mar 2014 21:29:13 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 20 Mar 2014 21:29:13 +0000 (UTC) Cc: 17049@debbugs.gnu.org To: Andy Wingo Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Thu Mar 20 22:29:22 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 1WQkWf-0003XO-AI for guile-bugs@m.gmane.org; Thu, 20 Mar 2014 22:29:21 +0100 Original-Received: from localhost ([::1]:49559 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQkWe-0003vK-RF for guile-bugs@m.gmane.org; Thu, 20 Mar 2014 17:29:20 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:34458) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQkVP-0002rW-ES for bug-guile@gnu.org; Thu, 20 Mar 2014 17:28:04 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WQkVO-0004WF-8N for bug-guile@gnu.org; Thu, 20 Mar 2014 17:28:03 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:41535) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WQkVO-0004VR-5p for bug-guile@gnu.org; Thu, 20 Mar 2014 17:28:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1WQkVN-0005Bt-N8 for bug-guile@gnu.org; Thu, 20 Mar 2014 17:28:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: David Kastrup Original-Sender: "Debbugs-submit" Resent-CC: bug-guile@gnu.org Resent-Date: Thu, 20 Mar 2014 21:28:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 17049 X-GNU-PR-Package: guile X-GNU-PR-Keywords: patch Original-Received: via spool by 17049-submit@debbugs.gnu.org id=B17049.139535086719931 (code B ref 17049); Thu, 20 Mar 2014 21:28:01 +0000 Original-Received: (at 17049) by debbugs.gnu.org; 20 Mar 2014 21:27:47 +0000 Original-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 Original-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 Original-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 Original-Received: by lola (Postfix, from userid 1000) id 18609E0934; Thu, 20 Mar 2014 22:27:28 +0100 (CET) In-Reply-To: <87bnx0y4qk.fsf@pobox.com> (Andy Wingo's message of "Thu, 20 Mar 2014 21:50:11 +0100") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.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:7418 Archived-At: 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