From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Paul Eggert Newsgroups: gmane.emacs.devel Subject: Re: Some vars now limited to fixnum size. (Was: Merging bignum to master) Date: Mon, 20 Aug 2018 16:15:29 -0700 Organization: UCLA Computer Science Department Message-ID: <71e06938-2b8c-74f8-ae55-756931613e84@cs.ucla.edu> References: <877ekwu1mn.fsf@tromey.com> <611579fd-52f2-0104-ef82-a7a4a3929700@cs.ucla.edu> <878t51t32a.fsf_-_@red-bean.com> <28fcabff-d102-d67f-442f-f59eab5040c9@cs.ucla.edu> <31ba6457-6428-efc7-8423-1d6134c8e747@cs.ucla.edu> <8336v8ex5f.fsf@gnu.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------C19F8DF6B589969071EED87F" X-Trace: blaine.gmane.org 1534807499 19140 195.159.176.226 (20 Aug 2018 23:24:59 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 20 Aug 2018 23:24:59 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 Cc: kfogel@red-bean.com, tom@tromey.com, emacs-devel@gnu.org To: Pip Cet , eliz@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Aug 21 01:24:54 2018 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1frtXa-0004td-3M for ged-emacs-devel@m.gmane.org; Tue, 21 Aug 2018 01:24:54 +0200 Original-Received: from localhost ([::1]:49820 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1frtZg-0004Se-Ib for ged-emacs-devel@m.gmane.org; Mon, 20 Aug 2018 19:27:04 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:43389) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1frtYX-0004HN-Cv for emacs-devel@gnu.org; Mon, 20 Aug 2018 19:25:58 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1frtOd-0000RC-9c for emacs-devel@gnu.org; Mon, 20 Aug 2018 19:15:40 -0400 Original-Received: from zimbra.cs.ucla.edu ([131.179.128.68]:56924) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1frtOZ-0000OG-Hx; Mon, 20 Aug 2018 19:15:35 -0400 Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id BE32F16160F; Mon, 20 Aug 2018 16:15:33 -0700 (PDT) Original-Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id 9afXCNTI8XAM; Mon, 20 Aug 2018 16:15:32 -0700 (PDT) Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 8083916161C; Mon, 20 Aug 2018 16:15:32 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Original-Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id e0265jEBYMOl; Mon, 20 Aug 2018 16:15:32 -0700 (PDT) Original-Received: from [192.168.1.9] (unknown [47.154.30.119]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id 108AA16160F; Mon, 20 Aug 2018 16:15:32 -0700 (PDT) In-Reply-To: Content-Language: en-US X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 131.179.128.68 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:228769 Archived-At: This is a multi-part message in MIME format. --------------C19F8DF6B589969071EED87F Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Pip Cet wrote: >> So we now silently replace the argument with another, smaller value, >> and then go ahead as if business as usual? Is that a good, >> user-friendly behavior? > It's certainly incorrect for circular lists. Yes, sorry, I forgot the circular case. Fixed by installing the attached patch. This patch improves circular-list nthcdr performance for fixnums too. For example, on my Fedora 28 x86-64 platform (AMD Phenom II X4 910e, circa 2010) the third line of the following benchmark runs about 8 million times faster: (setq bench-circular (list 1 2 3 4 5 6)) (setcdr (nthcdr 5 bench-circular) bench-circular) (nthcdr 536870911 bench-circular) Normally I wouldn't bother with this sort of performance improvement (I mean, how often to people write code that deliberately goes around in circles? :-), but nthcdr is used so often that it seemed worth doing. Plus it was fun to fix this mostly by using machine arithmetic rather than GMP. --------------C19F8DF6B589969071EED87F Content-Type: text/x-patch; name="0001-Speed-up-nthcdr-N-L-when-L-is-circular.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0001-Speed-up-nthcdr-N-L-when-L-is-circular.patch" >From eb83344fc7c08ec08b51e7700f1ac2632afa462c Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 20 Aug 2018 15:52:29 -0700 Subject: [PATCH] Speed up (nthcdr N L) when L is circular Also, fix bug when N is a positive bignum, a problem reported by Eli Zaretskii and Pip Cet in: https://lists.gnu.org/r/emacs-devel/2018-08/msg00690.html * src/fns.c (Fnthcdr): If a cycle is found, reduce the count modulo the cycle length before continuing. This reduces the worst-case cost of (nthcdr N L) from N to min(N, C) where C is the number of distinct cdrs of L. Reducing modulo the cycle length also allows us to do arithmetic with machine words instead of with GMP. * test/src/fns-tests.el (test-nthcdr-circular): New test. --- src/fns.c | 58 ++++++++++++++++++++++++++++++++++++++----- test/src/fns-tests.el | 16 ++++++++++++ 2 files changed, 68 insertions(+), 6 deletions(-) diff --git a/src/fns.c b/src/fns.c index aeb9308d22..8cff6b1b6c 100644 --- a/src/fns.c +++ b/src/fns.c @@ -1403,7 +1403,12 @@ DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0, (Lisp_Object n, Lisp_Object list) { CHECK_INTEGER (n); - Lisp_Object tail = list; + + /* A huge but in-range EMACS_INT that can be substituted for a + positive bignum while counting down. It does not introduce + miscounts because a list or cycle cannot possibly be this long, + and any counting error is fixed up later. */ + EMACS_INT large_num = EMACS_INT_MAX; EMACS_INT num; if (FIXNUMP (n)) @@ -1412,16 +1417,57 @@ DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0, { num = mpz_sgn (XBIGNUM (n)->value); if (0 < num) - num = EMACS_INT_MAX; /* LIST cannot possibly be this long. */ + num = large_num; } - for (; 0 < num; num--) + EMACS_INT tortoise_num = num; + Lisp_Object tail = list, saved_tail = tail; + FOR_EACH_TAIL_SAFE (tail) { - if (! CONSP (tail)) + if (num <= 0) + return tail; + if (tail == li.tortoise) + tortoise_num = num; + saved_tail = XCDR (tail); + num--; + rarely_quit (num); + } + + tail = saved_tail; + if (! CONSP (tail)) + { + CHECK_LIST_END (tail, list); + return Qnil; + } + + /* TAIL is part of a cycle. Reduce NUM modulo the cycle length to + avoid going around this cycle repeatedly. */ + intptr_t cycle_length = tortoise_num - num; + if (! FIXNUMP (n)) + { + /* Undo any error introduced when LARGE_NUM was substituted for + N, by adding N - LARGE_NUM to NUM, using arithmetic modulo + CYCLE_LENGTH. */ + mpz_t z; /* N mod CYCLE_LENGTH. */ + mpz_init (z); + if (cycle_length <= ULONG_MAX) + num += mpz_mod_ui (z, XBIGNUM (n)->value, cycle_length); + else { - CHECK_LIST_END (tail, list); - return Qnil; + mpz_set_intmax (z, cycle_length); + mpz_mod (z, XBIGNUM (n)->value, z); + intptr_t iz; + mpz_export (&iz, NULL, -1, sizeof iz, 0, 0, z); + num += iz; } + mpz_clear (z); + num += cycle_length - large_num % cycle_length; + } + num %= cycle_length; + + /* One last time through the cycle. */ + for (; 0 < num; num--) + { tail = XCDR (tail); rarely_quit (num); } diff --git a/test/src/fns-tests.el b/test/src/fns-tests.el index f722ed6333..92dc18fa03 100644 --- a/test/src/fns-tests.el +++ b/test/src/fns-tests.el @@ -624,4 +624,20 @@ dot2 (should (eq (gethash b2 hash) (funcall test b1 b2))))))) +(ert-deftest test-nthcdr-circular () + (dolist (len '(1 2 5 37 120 997 1024)) + (let ((cycle (make-list len nil))) + (setcdr (last cycle) cycle) + (dolist (n (list (1- most-negative-fixnum) most-negative-fixnum + -1 0 1 + (1- len) len (1+ len) + most-positive-fixnum (1+ most-positive-fixnum) + (* 2 most-positive-fixnum) + (* most-positive-fixnum most-positive-fixnum) + (ash 1 12345))) + (let ((a (nthcdr n cycle)) + (b (if (<= n 0) cycle (nthcdr (mod n len) cycle)))) + (should (equal (list (eq a b) n len) + (list t n len)))))))) + (provide 'fns-tests) -- 2.17.1 --------------C19F8DF6B589969071EED87F--