From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Paul Eggert Newsgroups: gmane.emacs.diffs,gmane.emacs.devel Subject: Re: master fe042e9: Speed up (+ 2 2) by a factor of 10 Date: Tue, 4 Sep 2018 10:28:18 -0700 Organization: UCLA Computer Science Department Message-ID: <536be78f-4e8d-586c-0a2b-454c889ebc46@cs.ucla.edu> References: <20180904015038.20117.2150@vcs0.savannah.gnu.org> <20180904015039.B9EAD20496@vcs0.savannah.gnu.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------90E881BDA45A47A598009DB3" X-Trace: blaine.gmane.org 1536081991 1919 195.159.176.226 (4 Sep 2018 17:26:31 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 4 Sep 2018 17:26:31 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 Cc: emacs-diffs@gnu.org To: Pip Cet , emacs-devel@gnu.org Original-X-From: emacs-diffs-bounces+gnu-emacs-diffs=m.gmane.org@gnu.org Tue Sep 04 19:26:27 2018 Return-path: Envelope-to: gnu-emacs-diffs@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 1fxF5q-0000Fm-MI for gnu-emacs-diffs@m.gmane.org; Tue, 04 Sep 2018 19:26:22 +0200 Original-Received: from localhost ([::1]:51988 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fxF7x-0000Ky-3Y for gnu-emacs-diffs@m.gmane.org; Tue, 04 Sep 2018 13:28:33 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:59380) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fxF7r-0000EA-9J for emacs-diffs@gnu.org; Tue, 04 Sep 2018 13:28:28 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fxF7q-0000fG-9z for emacs-diffs@gnu.org; Tue, 04 Sep 2018 13:28:27 -0400 Original-Received: from zimbra.cs.ucla.edu ([131.179.128.68]:47040) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fxF7l-0000dg-Pp; Tue, 04 Sep 2018 13:28:22 -0400 Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 9E7EA16161D; Tue, 4 Sep 2018 10:28:20 -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 MUKgyovtJl6p; Tue, 4 Sep 2018 10:28:18 -0700 (PDT) Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id DE62A1615A6; Tue, 4 Sep 2018 10:28:18 -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 WJxVipk2yHZw; Tue, 4 Sep 2018 10:28:18 -0700 (PDT) Original-Received: from [192.168.1.9] (cpe-23-242-74-103.socal.res.rr.com [23.242.74.103]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id B3DDE1610F1; Tue, 4 Sep 2018 10:28:18 -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-diffs@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: Mailing list for Emacs changes List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-diffs-bounces+gnu-emacs-diffs=m.gmane.org@gnu.org Original-Sender: "Emacs-diffs" Xref: news.gmane.org gmane.emacs.diffs:146865 gmane.emacs.devel:229250 Archived-At: This is a multi-part message in MIME format. --------------90E881BDA45A47A598009DB3 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Pip Cet wrote: >> - num += mpz_mod_ui (z, XBIGNUM (n)->value, cycle_length); >> + num += mpz_mod_ui (mpz[0], XBIGNUM (n)->value, cycle_length); > > I think it would be best to use mpz_div_ui here (despite its name, it > returns the remainder of the division specified by its arguments). I assume you meant mpz_tdiv_ui. Yes, thanks, that should be a bit faster. Likewise for mpz_tdiv_r instead of mpz_mod, for --with-wide-int platforms. I installed the attached. > Are you sure it wouldn't be possible to get the performance gains your > patch gives us without introducing global temporaries, such as by > using mpz_swap efficiently? Is this worth investigating, maybe, or do > you prefer global temporaries for another reason? I'm no fan of these temps, but the GMP mpz API does push hard in the direction of preinitialized temps if we want efficiency, as the overhead for small operands is the first thing listed in . And in the context of Emacs, doesn't mpz_swap rely on having preinitialized temps? How would we use mpz_swap efficiently without having preinitialized temps? Unfortunately in C I don't see how to have preinitialized temps without making them "global" in some sense; we could easily make them Emacs-thread-local if necessary, but they'd still be "global" to the thread. I mainly introduced global temporaries to fix memory leaks when a bignum calculation overflows past integer-width or when memory is exhausted. It would also be possible to avoid these leaks by putting a record_unwind_protect of some sort around every bignum calculation, but that would slow things down significantly. As a side effect, somewhat to my surprise, I found that global temps made the code simpler and easier to understand. I still don't like the "global" part of them, though, and perhaps with further hacking we can find some way to make them local while keeping the code simple and efficient. --------------90E881BDA45A47A598009DB3 Content-Type: text/x-patch; name="0001-Tweak-nthcdr-for-bignum-efficiency.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0001-Tweak-nthcdr-for-bignum-efficiency.patch" >From 628f6a2c7a9fe476b7e71efed3a8f8784a00cc54 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Tue, 4 Sep 2018 10:24:51 -0700 Subject: [PATCH] Tweak nthcdr for bignum efficiency * src/fns.c (Fnthcdr): Use mpz_tdiv_ui and mpz_tdiv_r instead of mpz_mod_ui and mpz_mod, as they are more efficient. Suggested by Pip Cet in: https://lists.gnu.org/r/emacs-devel/2018-09/msg00073.html --- src/fns.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/fns.c b/src/fns.c index 8b25492eae..5a98f14881 100644 --- a/src/fns.c +++ b/src/fns.c @@ -1470,11 +1470,11 @@ DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0, CYCLE_LENGTH. */ /* Add N mod CYCLE_LENGTH to NUM. */ if (cycle_length <= ULONG_MAX) - num += mpz_mod_ui (mpz[0], XBIGNUM (n)->value, cycle_length); + num += mpz_tdiv_ui (XBIGNUM (n)->value, cycle_length); else { mpz_set_intmax (mpz[0], cycle_length); - mpz_mod (mpz[0], XBIGNUM (n)->value, mpz[0]); + mpz_tdiv_r (mpz[0], XBIGNUM (n)->value, mpz[0]); intptr_t iz; mpz_export (&iz, NULL, -1, sizeof iz, 0, 0, mpz[0]); num += iz; -- 2.17.1 --------------90E881BDA45A47A598009DB3 Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline