From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Po Lu Newsgroups: gmane.emacs.devel Subject: Re: [PATCH] Re: Bignum performance Date: Mon, 14 Aug 2023 15:50:36 +0800 Message-ID: <87r0o6m59v.fsf@yahoo.com> References: <20230809094655.793FC18A4654@snark.thyrsus.com> <83fs4rjq9j.fsf@gnu.org> <87jzu2tvfc.fsf@dataswamp.org> <87y1ih3mc1.fsf@localhost> <87h6p5kcek.fsf@dataswamp.org> <87msyxoj2t.fsf@localhost> <875y5lkb4b.fsf@dataswamp.org> <87bkfdsmde.fsf@localhost> <87v8dlihc5.fsf@dataswamp.org> <87il9l1i59.fsf@localhost> <87edk9icis.fsf@dataswamp.org> <871qg84qij.fsf@localhost> <871qg8l03q.fsf@dataswamp.org> <877cpzl357.fsf@localhost> <87sf8ni85u.fsf@dataswamp.org> <87ttt3fdjt.fsf@localhost> <877cpyicv1.fsf@dataswamp.org> <87v8dimjiv.fsf@yahoo.com> <878raert6t.fsf@localhost> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="20418"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: emacs-devel@gnu.org To: Ihor Radchenko Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Aug 14 09:51:44 2023 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1qVSMZ-00058j-1T for ged-emacs-devel@m.gmane-mx.org; Mon, 14 Aug 2023 09:51:43 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qVSLx-0002uB-L6; Mon, 14 Aug 2023 03:51:08 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qVSLr-0002oU-9n for emacs-devel@gnu.org; Mon, 14 Aug 2023 03:50:59 -0400 Original-Received: from sonic305-20.consmr.mail.ne1.yahoo.com ([66.163.185.146]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1qVSLn-0008Fo-4t for emacs-devel@gnu.org; Mon, 14 Aug 2023 03:50:59 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1691999446; bh=9iF2sO0ONvoN64+PGlRIowiDKzs6Kgq3zXM2bPBcv/w=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From:Subject:Reply-To; b=SwL51DBtHQjw99bzjfj4kZxf4T1o8BEYYRefc9BdbT4EigNAd9Wn5DQwfZmjTJXKOS2VZKB5i6PcVGRlpvMcM8Yo5nVrfjgHhOcLVpsKaXTRyBnnmqwGsOwyUvjX85vEDd3oiEAKVRyAgUSAmHD7u7hcWvzLcsSEPTGefXt05RB0zm4J0YQUD1Cu/qmXzlVjKPzUIf44bI+p1wolioIojMv1+qWvDq8H+B133oN0J4FfypdDoR6+hE644gpf4JDk231r3MBbEKDDVu/w6PdIRUr6u5a7DBo/9UBoTMDO97QrMt+W0zGBqPoXvbnJWFn5GUiIXf/XCpW2R3ym6YpQRQ== X-SONIC-DKIM-SIGN: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1691999446; bh=37hNVLX/Oc5c1E5h8dXfsZeT+29F85psk0/frIfjQm7=; h=X-Sonic-MF:From:To:Subject:Date:From:Subject; b=Gw1+33wGErChGP+J4HxpmBnKrWgPPHKf9K4M9tCuctlMmfpDLiMfnQhAQ/BOKG+QvGusiMVmZen870IAchS2VR5OFCFCVh1ErYSOqHjR+3ilR0cUjAGGjfLqPZHa8VdBJcwTDrwYxIDOXSCJsHs86aV6Lz3dG8z4oq1WDsX0GJH1/9PbDmUIqBhl785yfAfwbxtQaFtIGlispAPeQ499heNetZLnTeLHqAXkEB4xng/fLcMPOtKwfNSa5P26EdwroLqONW/QYI7BnAKhDDIMYE0AkW83Rylp87Og0JSprxz3xlfOa/ELJPOTshAPLLGu6zGuwFitX52zMurMZVYD5w== X-YMail-OSG: fY2C7qsVM1mmNDtubd49O59LYDq4xeTxRFQdHGBm6HKnjSpE5CK.r_76jP5cneQ gY9BVdCMLXRFyhQfwZS2FKRqtC99pVgM4VXtbB.RklLx4Gyge4L_a56vF9ocQuvavv6cNZ27URQX 3wawkiuVfGvSK076XKVZJvPPDp0vskvvmtkvG3XY2hTuoiVszbaja0pHU19aOQGYtND7ovQHSVvs Uy2ntgiOgBZLNKiUOllkRvaXbhnVoAmSEvpKt5NXh6YvXDZekwNfQpUzv_OztcC9G9RT6lLpD2Af cNSUpW.VQJT_zMgjGi0T.I.OmhqmyJIwxrcsU6myclZp_orqxp3gR8Zt8e_2zfXdIg0AYtQ7yl0m BGSuZVcucN25egNf15edNS_r8.NHPZ_97LNhI0VRNaD4OZRJI4iiUrVc8R5hvJlqRfdDC376NRd2 rlrVj1mNbGk4BCJCwGwK6XP6GoaE3_pSqkUu0qzmrNpzmUr_SK9uZjtptnmbgyLwASW7CsGm_n3J hgbuy3Rb.inVzlvbwOZ6vyt4lTUGQs062FWsSByUj5Km_m0d.Mdp4PHaHLmd4WQmEjXWpaCA71lR WvlisAR00eBQyDZBMzBSLRdURDV04aM02qPtDGwx0ho10XTLhsP3HKkQF3F.UAOrkohDAYtav2I0 Xsr2ngqsooKNrqJukI5cUWircY5gaDzBLGfE0MFMEPDY0ayWg_RqKyrRklg1rvgOIA1HC1MWXkci wRWqo_Qh7VXQAOj0pvyZ5BekvOPZa4mSRmfc9KoKDyH4PqqI7A8nGoDKdFGINxVo9C1QZhtX5S0z ElKdiJwVWwiPgsWg0CnTdyz.JZXfOVA4tTUehXXBpy X-Sonic-MF: X-Sonic-ID: 344b7b70-58f4-4736-867e-94b6954846ad Original-Received: from sonic.gate.mail.ne1.yahoo.com by sonic305.consmr.mail.ne1.yahoo.com with HTTP; Mon, 14 Aug 2023 07:50:46 +0000 Original-Received: by hermes--production-sg3-69654d8bd-hj7c9 (Yahoo Inc. Hermes SMTP Server) with ESMTPA ID a25bb2e86253c293ca84422f91afaaa3; Mon, 14 Aug 2023 07:50:41 +0000 (UTC) In-Reply-To: <878raert6t.fsf@localhost> (Ihor Radchenko's message of "Mon, 14 Aug 2023 07:15:06 +0000") X-Mailer: WebService/1.1.21695 mail.backend.jedi.jws.acl:role.jedi.acl.token.atz.jws.hermes.yahoo Received-SPF: pass client-ip=66.163.185.146; envelope-from=luangruo@yahoo.com; helo=sonic305-20.consmr.mail.ne1.yahoo.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 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-mx.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:308709 Archived-At: Ihor Radchenko writes: > Po Lu writes: > >>>> And we have huge overheads converting things back-and-forth >>>> between GMP and Elisp formats. It is by choice. And my patch >>>> did not do anything about this difference. >> >> AFAIU, no conversion takes place between ``Elisp formats'' and GMP >> formats. Our bignums rely on GMP for all data storage and memory >> allocation. > > Thanks for the clarification! > So, GMP is not as fast as SBCL's implementation after all. > SBCL uses https://github.com/sbcl/sbcl/blob/master/src/code/bignum.lisp > - a custom bignum implementation, which is clearly faster compared to > GMP (in the provided benchmark): GMP is significantly faster than all other known bignum libraries. Bignums are not considered essential for Emacs's performance, so the GMP library is utilized in an inefficient fashion. > perf record ~/Git/emacs/src/emacs -Q -batch -l /tmp/fib.eln > 0.739 s > (0.007 s for SBCL) > > 17.11% emacs libgmp.so.10.5.0 [.] __gmpz_sizeinbase > > 7.35% emacs libgmp.so.10.5.0 [.] __gmpz_add > > ^^ already >0.1 sec. The subroutine actually performing arithmetic is in fact mpn_add_n_coreisbr. mpz_add and mpz_sizeinbase are ``mpz'' functions that perform memory allocation, and our bignum functions frequently utilize mpz_sizeinbase to ascertain whether a result can be represented as a fixnum. As such, they don't constitute a fair comparison between the speed of the GMP library itself and SBCL. GMP provides low-level functions that place responsibility for memory management and input verification in the hands of the programmer. These are usually implemented in CPU-specific assembler, and are very fast. That being said, they're not available within mini-gmp, and the primary bottleneck is in fact mpz_sizeinbase.