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: Making 'eq' == 'eql' in bignum branch Date: Mon, 20 Aug 2018 00:05:56 -0700 Organization: UCLA Computer Science Department 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; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: blaine.gmane.org 1534749096 14011 195.159.176.226 (20 Aug 2018 07:11:36 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 20 Aug 2018 07:11:36 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 Cc: emacs-devel@gnu.org To: Pip Cet , Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Aug 20 09:11:32 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 1freLc-0003Y2-10 for ged-emacs-devel@m.gmane.org; Mon, 20 Aug 2018 09:11:32 +0200 Original-Received: from localhost ([::1]:45317 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1freNi-0002FU-EA for ged-emacs-devel@m.gmane.org; Mon, 20 Aug 2018 03:13:42 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:41142) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1freNX-00022K-9r for emacs-devel@gnu.org; Mon, 20 Aug 2018 03:13:34 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1freGI-000613-3J for emacs-devel@gnu.org; Mon, 20 Aug 2018 03:06:05 -0400 Original-Received: from zimbra.cs.ucla.edu ([131.179.128.68]:36386) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1freGH-00060Q-RL for emacs-devel@gnu.org; Mon, 20 Aug 2018 03:06:02 -0400 Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id F0FF316087B; Mon, 20 Aug 2018 00:05:58 -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 EfqEVrYCl7UO; Mon, 20 Aug 2018 00:05:58 -0700 (PDT) Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 2A549160885; Mon, 20 Aug 2018 00:05:58 -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 HYIKuWWaobqj; Mon, 20 Aug 2018 00:05:58 -0700 (PDT) Original-Received: from [192.168.1.9] (unknown [47.154.30.119]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id CEC5016087B; Mon, 20 Aug 2018 00:05:57 -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:228710 Archived-At: Pip Cet wrote: > 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. It's on my list of things to look at, though I can't guarantee I'll fix it (much less "soon"). > 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. > Perhaps we should make a wishlist of GMP features, which would > currently include three items: > > - make long-running integer operations interruptible (so C-g works) We can approximate this by checking for C-g in the GMP-specific memory allocator hooks. Perhaps all we need is some sort of guarantee that unbounded computation won't occur without some memory allocation action. > - don't abort() when overflowing the 16 GB limit (and/or remove that > limit entirely) Yes, that reeally needs to be fixed. I think I have a handle on avoiding that glitch in the meantime (still polishing it). > - hash numbers as you create them, at least for the fast single-pass > operations (addition, left shift, negation). Could well be a win, yes. Not sure how much of a win it would be for typical use, though. Usually bignums are pretty small. > Do we need to worry about algorithmic complexity attacks? Or about > integers created accidentally that collide in the hash? Both, I'd think. > I think 64-bit integers, at least, ought to be fast and small. Maybe > we could use our free tag value for that special case. Hold on, let's not spend that valuable tag so casually! Perhaps bignums or floats are a better use for a tag than 64-bit ints. One other thing: we can pry another tag free. Now that we have bignums we no longer need to give fixnums two tags.