From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Pip Cet Newsgroups: gmane.emacs.devel Subject: Re: Making 'eq' == 'eql' in bignum branch Date: Mon, 20 Aug 2018 06:35:44 +0000 Message-ID: References: <29f933ac-a6bf-8742-66a7-0a9d6d3e5a88@disroot.org> <0d3175d8-d996-651e-b221-71978bde3a65@cs.ucla.edu> <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" X-Trace: blaine.gmane.org 1534746868 9062 195.159.176.226 (20 Aug 2018 06:34:28 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 20 Aug 2018 06:34:28 +0000 (UTC) Cc: eggert@cs.ucla.edu, emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Aug 20 08:34:23 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 1frdle-0002EC-Jj for ged-emacs-devel@m.gmane.org; Mon, 20 Aug 2018 08:34:22 +0200 Original-Received: from localhost ([::1]:45259 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1frdnl-0001DW-0e for ged-emacs-devel@m.gmane.org; Mon, 20 Aug 2018 02:36:33 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:36101) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1frdne-0001Co-N2 for emacs-devel@gnu.org; Mon, 20 Aug 2018 02:36:27 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1frdne-0007pu-2W for emacs-devel@gnu.org; Mon, 20 Aug 2018 02:36:26 -0400 Original-Received: from mail-lf1-x131.google.com ([2a00:1450:4864:20::131]:40997) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1frdnd-0007pI-RQ for emacs-devel@gnu.org; Mon, 20 Aug 2018 02:36:26 -0400 Original-Received: by mail-lf1-x131.google.com with SMTP id v22-v6so10047025lfe.8 for ; Sun, 19 Aug 2018 23:36:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=LzJCPjS6Vi+a4ZH1IGHj8fnzgC64Yk99Py/gQR1ON7k=; b=stXbaybniZqPbh7/BoaodWin/TnMHUEGgorcZuPc2ZPDy6S0oAFKoaY5jS6WaE/QkU 92heHCufJOjA5n3AT/o+AoOQ8v4H1V3GQiwOOS1WcdYO+9aFgwiECCmcsc+yO3dRy1Sp f51MlnpT8cvcmIXHWCrcMxLZl+nJVjHEbE4282lP0t760SNtYcfCPgqgtovA/wQtqtrh UYahjWXon9kXn8be3fTlsAIwZ//aABZkKNUCFl/21ijcvN+dh7tvl3oiddnkbxNE1kd4 z/GUZLhsGzrLrXGMI4KZmkm/vqvJUg6NoRKPXPV2xOyq3Hq1g3Ut/XbUvdR7bGUrxx3W D8SQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=LzJCPjS6Vi+a4ZH1IGHj8fnzgC64Yk99Py/gQR1ON7k=; b=qFP13qT2QglPzXKaiF+vgIdi2Qel+/ucqRrmzn0zkCk3Ff/Z9uVa+a/WAxdrmU6i5x zeH8/Z+akv7txJOdJqDrRWn7WhLnPShsRJx4kDSzYHPjPLidJ/1ZLsD7QdzSUi6sssSH ysaFVtTHGTu2Dki6FdnmqlkQT3NEBaGvPTLm6IhgVtFBHZlnWwLfu9Rv3/TJR0T6o1Ii rXwbp1JrY0+/kGHkYGzH2YKYbbE/p5/a8wD4bFPZLacJxcJj76YR9hMA5QRZv47OJVf1 LqOeHyHo19ssPayHbw4BKgVvW0ohjCY7kF6NNb63Cj1PqhQ4s8aL36FB4Cwv1zkxAiag g72Q== X-Gm-Message-State: AOUpUlEc1WeV6ERaBt3DYQjnxaULLrzwyOWVMM1TRQVe8WNCZKYzaKrA cfUNO0bukMVi+AeJpstFyemAhg1SPMmIffGnigs= X-Google-Smtp-Source: AA+uWPzXR3RO5TYlTAPqzomKPdyT4fSbKfIbF26ueOsgIehbJiF1zxvSBQ6X9J8e4yonHLWlpZl1m77WEP6O8jHqlPk= X-Received: by 2002:a19:b585:: with SMTP id g5-v6mr375570lfk.149.1534746984322; Sun, 19 Aug 2018 23:36:24 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:4864:20::131 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:228709 Archived-At: On Mon, Aug 20, 2018 at 12:05 AM Stefan Monnier wrote: > I think its cost should not be too high in practice: the time to lookup > up a GMP number in a hash table basically should never be longer than > the time it took to construct this number in the first place, so that's > a worst-case slowdown factor of 2 which I think is perfectly acceptable. Can you explain why you think that's the case? 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 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) - don't abort() when overflowing the 16 GB limit (and/or remove that limit entirely) - hash numbers as you create them, at least for the fast single-pass operations (addition, left shift, negation). Do we need to worry about algorithmic complexity attacks? Or about integers created accidentally that collide in the hash? 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.