From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Making 'eq' == 'eql' in bignum branch Date: Mon, 20 Aug 2018 10:02:34 -0400 Message-ID: References: <29f933ac-a6bf-8742-66a7-0a9d6d3e5a88@disroot.org> <87tvpdnzgy.fsf@tromey.com> <4c2a814f-c254-29e5-39cf-11b5f2e5c9c8@cs.ucla.edu> <49d8ba62-c9a5-9203-d882-8e900b441ff3@cs.ucla.edu> <8e0320d9-e0d0-2b57-57cc-2df4399f133c@cs.ucla.edu> <87lgaio7xd.fsf@tromey.com> <877em1cb0i.fsf@tromey.com> <765767b2-d2e5-a9a6-f724-d58ecf4847bb@cs.ucla.edu> <76081b5d-8c10-0a37-2c97-d4864c0faa80@cs.ucla.edu> <09153aed-361d-4f82-d9ac-b502314769ae@cs.ucla.edu> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: blaine.gmane.org 1534773689 18410 195.159.176.226 (20 Aug 2018 14:01:29 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 20 Aug 2018 14:01:29 +0000 (UTC) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) Cc: eggert@cs.ucla.edu, emacs-devel@gnu.org To: Pip Cet Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Aug 20 16:01:25 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 1frkkE-0004dH-FH for ged-emacs-devel@m.gmane.org; Mon, 20 Aug 2018 16:01:22 +0200 Original-Received: from localhost ([::1]:47255 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1frkmL-0000Oz-3v for ged-emacs-devel@m.gmane.org; Mon, 20 Aug 2018 10:03:33 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:39659) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1frkli-0000Of-2p for emacs-devel@gnu.org; Mon, 20 Aug 2018 10:02:54 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1frkld-0002CR-Cd for emacs-devel@gnu.org; Mon, 20 Aug 2018 10:02:53 -0400 Original-Received: from pruche.dit.umontreal.ca ([132.204.246.22]:39840) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1frkld-0002C3-8C for emacs-devel@gnu.org; Mon, 20 Aug 2018 10:02:49 -0400 Original-Received: from fmsmemgm.homelinux.net (lechon.iro.umontreal.ca [132.204.27.242]) by pruche.dit.umontreal.ca (8.14.7/8.14.1) with ESMTP id w7KE2Ye5000959; Mon, 20 Aug 2018 10:02:36 -0400 Original-Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848) id 65C80AE243; Mon, 20 Aug 2018 10:02:34 -0400 (EDT) In-Reply-To: (Pip Cet's message of "Mon, 20 Aug 2018 06:35:44 +0000") X-NAI-Spam-Flag: NO X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0 X-NAI-Spam-Rules: 2 Rules triggered EDT_SA_DN_PASS=0, RV6355=0 X-NAI-Spam-Version: 2.3.0.9418 : core <6355> : inlines <6821> : streams <1796046> : uri <2692409> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 132.204.246.22 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:228721 Archived-At: > I think it's currently true, but only because make_number always > creates a copy of its argument (at which point we might as well hash > it), and it sounded like Paul was going to fix that soon. Two options: 1- the operation does not create a new number. Since Elisp's side only sees immutable bignum numbers if the number is not new we indeed shouldn't create a new number and can reuse the existing bignum without any need for hash-consing either: so hash-consing doesn't make this case any slower. 2- the operation does create a new number. In that case the creation of the number almost inevitably will have to touch every "limb" of the number (it has a complexity of O(N) in the best case), so computing the hash shouldn't take noticeably more time. > It sounds to me like a good implementation of this would require GMP > support, keeping a hash of each mpz_t in the memory allocated for it. We can keep the hash in the hash-table. > Do we need to worry about algorithmic complexity attacks? Or about > integers created accidentally that collide in the hash? Emacs already offers so many other attack vectors that I don't think it's worth worrying about this one at this point. > I think 64-bit integers, at least, ought to be fast and small. Indeed, it's for those small bignums that hash-consing will be most expensive, but I'm not sure it'll be a significant problem. Stefan