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: Sat, 28 Jul 2018 20:34:32 -0700 Organization: UCLA Computer Science Department Message-ID: <09153aed-361d-4f82-d9ac-b502314769ae@cs.ucla.edu> References: <29f933ac-a6bf-8742-66a7-0a9d6d3e5a88@disroot.org> <83bmecy6fx.fsf@gnu.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> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: quoted-printable X-Trace: blaine.gmane.org 1532835165 28697 195.159.176.226 (29 Jul 2018 03:32:45 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 29 Jul 2018 03:32:45 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 To: Stefan Monnier , emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Jul 29 05:32:41 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 1fjcRk-0007LK-Vp for ged-emacs-devel@m.gmane.org; Sun, 29 Jul 2018 05:32:41 +0200 Original-Received: from localhost ([::1]:47049 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fjcTr-0004XV-8U for ged-emacs-devel@m.gmane.org; Sat, 28 Jul 2018 23:34:51 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:58369) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fjcTh-0004XP-Uc for emacs-devel@gnu.org; Sat, 28 Jul 2018 23:34:43 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fjcTc-0007vI-QW for emacs-devel@gnu.org; Sat, 28 Jul 2018 23:34:41 -0400 Original-Received: from zimbra.cs.ucla.edu ([131.179.128.68]:49684) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fjcTc-0007ug-HE for emacs-devel@gnu.org; Sat, 28 Jul 2018 23:34:36 -0400 Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 37F39160661; Sat, 28 Jul 2018 20:34:34 -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 ceM3PSyNJb_b; Sat, 28 Jul 2018 20:34:33 -0700 (PDT) Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 3C88016066F; Sat, 28 Jul 2018 20:34:33 -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 g56hQuArua5m; Sat, 28 Jul 2018 20:34:33 -0700 (PDT) Original-Received: from [192.168.1.9] (unknown [47.154.30.119]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id DB771160661; Sat, 28 Jul 2018 20:34:32 -0700 (PDT) Openpgp: preference=signencrypt Autocrypt: addr=eggert@cs.ucla.edu; prefer-encrypt=mutual; keydata= xsFNBEyAcmQBEADAAyH2xoTu7ppG5D3a8FMZEon74dCvc4+q1XA2J2tBy2pwaTqfhpxxdGA9 Jj50UJ3PD4bSUEgN8tLZ0san47l5XTAFLi2456ciSl5m8sKaHlGdt9XmAAtmXqeZVIYX/UFS 96fDzf4xhEmm/y7LbYEPQdUdxu47xA5KhTYp5bltF3WYDz1Ygd7gx07Auwp7iw7eNvnoDTAl KAl8KYDZzbDNCQGEbpY3efZIvPdeI+FWQN4W+kghy+P6au6PrIIhYraeua7XDdb2LS1en3Ss mE3QjqfRqI/A2ue8JMwsvXe/WK38Ezs6x74iTaqI3AFH6ilAhDqpMnd/msSESNFt76DiO1ZK QMr9amVPknjfPmJISqdhgB1DlEdw34sROf6V8mZw0xfqT6PKE46LcFefzs0kbg4GORf8vjG2 Sf1tk5eU8MBiyN/bZ03bKNjNYMpODDQQwuP84kYLkX2wBxxMAhBxwbDVZudzxDZJ1C2VXujC OJVxq2kljBM9ETYuUGqd75AW2LXrLw6+MuIsHFAYAgRr7+KcwDgBAfwhPBYX34nSSiHlmLC+ KaHLeCLF5ZI2vKm3HEeCTtlOg7xZEONgwzL+fdKo+D6SoC8RRxJKs8a3sVfI4t6CnrQzvJbB n6gxdgCu5i29J1QCYrCYvql2UyFPAK+do99/1jOXT4m2836j1wARAQABzSBQYXVsIEVnZ2Vy dCA8ZWdnZXJ0QGNzLnVjbGEuZWR1PsLBfgQTAQIAKAUCTIByZAIbAwUJEswDAAYLCQgHAwIG FQgCCQoLBBYCAwECH In-Reply-To: Content-Language: en-US X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] 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:227937 Archived-At: Stefan Monnier wrote: > I'm afraid you might be comparing apples and pears, since the relative > cost may vary substantially depending on the CPU's architecture. > Have you tried to measure the slowdown of my patch on your machine? It's definitely apples-to-pears, as your patch hashes incorrectly and tha= t might=20 be a performance advantage. For what it's worth I tried to do the measurement again, and this time go= t=20 different numbers. Again, this is Fedora 28 x86-64, AMD Phenom II X4 910e= ,=20 user+system time, average of 3 runs for "cd lisp; time make compile-alway= s",=20 otherwise-idle system. However, this time I started with master commit=20 db80851a1f10d73f0b2c12299c3d77716bb8425a, and I did 4 runs and ignored th= e first=20 one to avoid any startup overheads involved. This time I got: master 460.= 587 s,=20 my patch 465.373 s (1% slower than master), your patch 469.619 s (2% slow= er than=20 master). >> have you thought about hashing floating-point objects instead, so >> that comparing pointers suffices for eql, and eq becomes equivalent to= eql >> in a different way? >=20 > No I have not considered this trade-off carefully. It's true that > floats aren't used very often, but it would make floats enormously more > expensive both in CPU and memory resources. Currently, they cost > 8 bytes of allocated heap, and currently our hash-tables cost about > 6 words per entry (i.e. 48 bytes per entry on 64bit systems). > Clearly we could cut that down for hash-consing uses (where key=3D=3Dva= lue), > but it's still pretty bad. How about if we do to floats what fixnum+bignum would do to integers? That is, on a 64-bit host, if the low-order 4 bits of the significand are= all=20 zero, we encode the floating-point number directly in the Lisp_Object (wi= th a=20 tag) so that the Lisp_Object need not be dereferenced and uses zero bytes= of=20 floating-point heap. Otherwise, we put the floating-point value into a sp= ecial=20 hash-consed table that should use about 16 bytes per entry (one for the d= ouble,=20 one for the pointer to it). I just checked 'make compile-always' and unde= r this=20 proposal a full run would create 95694 Lisp floats of which 80048 (84%) w= ould=20 use zero bytes and 15646 (16%) would use 16 bytes of floating-point heap.= This=20 would mean a total floating-point heap usage of 15646*16 =3D 250 kB, as o= pposed to=20 current master which uses 95694*8 =3D=3D 766 kB, i.e., we'd shrink floati= ng-point=20 heap usage by about a factor of 3. The tradeoff would be different on a 32-bit platform, since in the above=20 discussion we would replace '4 bits' with '36 bits', '15620 (16%)' with '= 16083=20 (17%)', and '16 bytes per entry' with '12 bytes per entry'. But it'd be a= n=20 even-bigger space win, as the total heap usage of 16083*12 =3D 193 kB of = heap=20 would be even smaller than the 64-bit total, i.e., we'd shrink floating-p= oint=20 heap usage by about a factor of 4. We could of course use even less storage simply by lowering the precision= of=20 Emacs Lisp floating-point, although that'd be a user-visible change, woul= d be a=20 fairly drastic thing to do on 32-bit platforms, and wouldn't really addre= ss the=20 bignum eql issue. (Though it might be interesting to try anyway....)