From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp1 ([2001:41d0:2:bcc0::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id cCr4JnQaOmGQeAAAgWs5BA (envelope-from ) for ; Thu, 09 Sep 2021 16:30:12 +0200 Received: from aspmx1.migadu.com ([2001:41d0:2:bcc0::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp1 with LMTPS id 6DSOInQaOmFXHwAAbx9fmQ (envelope-from ) for ; Thu, 09 Sep 2021 14:30:12 +0000 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id EC19D11158 for ; Thu, 9 Sep 2021 16:30:11 +0200 (CEST) Received: from localhost ([::1]:38238 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mOL46-00007b-A9 for larch@yhetil.org; Thu, 09 Sep 2021 10:30:10 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:58960) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mOL3y-00007D-F1 for guix-patches@gnu.org; Thu, 09 Sep 2021 10:30:02 -0400 Received: from debbugs.gnu.org ([209.51.188.43]:52578) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mOL3y-0007yU-6b for guix-patches@gnu.org; Thu, 09 Sep 2021 10:30:02 -0400 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1mOL3y-00065P-2I for guix-patches@gnu.org; Thu, 09 Sep 2021 10:30:02 -0400 X-Loop: help-debbugs@gnu.org Subject: [bug#50456] Optimise bytevector->nix-base32-string and bytevector->base16-string. Resent-From: Ludovic =?UTF-8?Q?Court=C3=A8s?= Original-Sender: "Debbugs-submit" Resent-CC: guix-patches@gnu.org Resent-Date: Thu, 09 Sep 2021 14:30:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 50456 X-GNU-PR-Package: guix-patches X-GNU-PR-Keywords: To: Maxime Devos Cc: 50456@debbugs.gnu.org Received: via spool by 50456-submit@debbugs.gnu.org id=B50456.163119777823336 (code B ref 50456); Thu, 09 Sep 2021 14:30:01 +0000 Received: (at 50456) by debbugs.gnu.org; 9 Sep 2021 14:29:38 +0000 Received: from localhost ([127.0.0.1]:35891 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mOL3a-00064K-DC for submit@debbugs.gnu.org; Thu, 09 Sep 2021 10:29:38 -0400 Received: from eggs.gnu.org ([209.51.188.92]:42768) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mOL3Y-000647-JX for 50456@debbugs.gnu.org; Thu, 09 Sep 2021 10:29:37 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:33322) by eggs.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mOL3S-0007Wy-MP; Thu, 09 Sep 2021 10:29:30 -0400 Received: from [2001:660:6102:320:e120:2c8f:8909:cdfe] (port=47214 helo=ribbon) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mOL3Q-0007OQ-Ta; Thu, 09 Sep 2021 10:29:30 -0400 From: Ludovic =?UTF-8?Q?Court=C3=A8s?= References: <7831fcdd8b8aab99cc95ba904076014b4c3cb6d2.camel@telenet.be> Date: Thu, 09 Sep 2021 16:29:26 +0200 In-Reply-To: <7831fcdd8b8aab99cc95ba904076014b4c3cb6d2.camel@telenet.be> (Maxime Devos's message of "Tue, 07 Sep 2021 17:34:28 +0200") Message-ID: <87o891esah.fsf@gnu.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.2 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: guix-patches@gnu.org List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-patches-bounces+larch=yhetil.org@gnu.org Sender: "Guix-patches" X-Migadu-Flow: FLOW_IN ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1631197812; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding:resent-cc: resent-from:resent-sender:resent-message-id:in-reply-to:in-reply-to: references:references:list-id:list-help:list-unsubscribe: list-subscribe:list-post; bh=X4xstfTy/TOhAs6qWK0RYDtmyOW9ZQWiqGiW877suts=; b=fnZ9A642Yf2N5B9RqManbducc6V/WZqLL6OguzsMB5WwEnpBXnpUvSg+/YmiJYIRitDcwz jkpr61WE4g3qU3mQfntGIdcsjmBiqusUnfL0o49ovQtZejiXB0HPMi4mjJt3U1k9xZz2GY JbFSgSOP32NisCpaDN4TSXDNO81ItJ50Oir8VdcowFDkRIZ/6npzMp3ohWYrCphFkjw0Qa WacrlQd6gKOGZmM11rXx3dtK3+uXUeT9YE/fq7cfG5fFfx+5YdWHOXIwJM6A8CTrpVXv3a 6+91SuWIp3ojULTbYo5p3dEtgLeuCtC0Ap9aWx+54rKHKR8Jk4s16vUuaZcdNg== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1631197812; a=rsa-sha256; cv=none; b=B7RS1Xd1TDCD6QSJVCJBq6/QCd8DLfbhyUX31JbSnzUaiDY3yHvKH2i1+JaUynZ+FQjhxT uXRhy9ciAZ0nCrwN6d0rfvyJTDOmj336vUDHeAlli8p9y/8G4cAK30nwPdtlP9xKZNXkPU T5m7QYEpmNVKKHC0LIE1XUnExv9RldoU2lMH4sJhwJqeZtj+/I7QUrnv9oTejwFX/+XMLl ujWQ2itFOtu2ASCwIc1zqIk7t60GQ1hAJqwG08+U6LBj9AEYjGv0ybhafR7s7nskwWgF7g /fS9vBf8wd2L15Z4ov+NPAJD0pOZpwAMKq3gbUCVp+YhAWVv+OH+xj8ZbbNykQ== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=none; dmarc=pass (policy=none) header.from=gnu.org; spf=pass (aspmx1.migadu.com: domain of guix-patches-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=guix-patches-bounces@gnu.org X-Migadu-Spam-Score: -2.91 Authentication-Results: aspmx1.migadu.com; dkim=none; dmarc=pass (policy=none) header.from=gnu.org; spf=pass (aspmx1.migadu.com: domain of guix-patches-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=guix-patches-bounces@gnu.org X-Migadu-Queue-Id: EC19D11158 X-Spam-Score: -2.91 X-Migadu-Scanner: scn1.migadu.com X-TUID: qEHoC010TCtz Hello, Maxime Devos skribis: > The two atached patches optimise bytevector->nix-base32-string and > bytevector->base16-string, making them about 20% and two times > faster respectively, by reducing allocations. They are called > from 'output-path', 'fixed-output-path' and 'store-path' > in (guix store). Thanks a lot for looking into this! > Unfortunately, this does not decrease timings to a noticable degree, > but it does decrease the allocated memory by 2.3% (*), and it does not > seem to increase timings. (See perf-numbers.txt.) Yeah, base32 code is usually pretty low in profiles of calls to =E2=80=98package-derivation=E2=80=99. > From a93bad629e2746c77446cacddb9986506ce9ba88 Mon Sep 17 00:00:00 2001 > From: Maxime Devos > Date: Sun, 5 Sep 2021 16:28:33 +0200 > Subject: [PATCH 1/2] base32: Reduce GC pressure in > make-bytevector->base32-string. > > The following code has been used to compare performance: > > ;; first 20 bytes of sha256 of #vu8(#xde #xad #xbe #xef) > (define bv #vu8(95 120 195 50 116 228 63 169 222 86 89 38 92 29 145 126 3= 7 192 55 34)) > ,profile > (let loop ((n 0)) > (when (< n #e1e6) > ((@ (guix base32) bytevector->nix-base32-string) bv) > (loop (+ n 1)))) > > Before this change, the output was: > > [...] > Sample count: 1140 > Total time: 27.465560018 seconds (10.659331433 seconds in GC) > > After this change, the output was: > > [...] > Sample count: 957 > Total time: 20.478847143 seconds (6.139721189 seconds in GC) Note that ,profile (statprof) is intrusive; additional, the REPL uses the =E2=80=9Cdebug=E2=80=9D VM engine, which is slightly slower than the = =E2=80=9Cregular=E2=80=9D one (info "(guile) Command-line Options"). To measure =E2=80=9Cactual=E2=80=9D performance, it=E2=80=99s best to write= the code down in a file and then run: time guile -l that-file.scm or, alternatively, use (ice-9 time) and wrap the body of the relevant code in (time =E2=80=A6), which is a bit more accurate than using the shell= =E2=80=99s =E2=80=98time=E2=80=99 command since it allows you to dismiss Guile startup= time. (You also need to make sure that the loop counter remains below =E2=80=98most-positive-fixnum=E2=80=99, otherwise you=E2=80=99ll end up mea= suring GC activity due to the use of bignums, but 10=E2=81=B6 is definitely OK.) > * guix/base32.scm > (make-bytevector->base32-string): Eliminate 'reverse', use mutation ins= tead. [...] > + (let* ((start (cons #f #f)) > + (end (quintet-fold (lambda (q r) > + (define pair > + (cons (vector-ref base32-chars q) #f)) > + (set-cdr! r pair) > + pair) > + start > + bv))) > + (set-cdr! end '()) > + (list->string (cdr start))))) Does replacing (reverse chars) with (reverse! chars) has the same effect? I=E2=80=99m reluctant to resorting to micro-optimizations like the one above since they make code harder to reason about. > From dfd9b7557e31823320fcbd7abed77de295b7dce1 Mon Sep 17 00:00:00 2001 > From: Maxime Devos > Date: Mon, 6 Sep 2021 00:46:17 +0200 > Subject: [PATCH 2/2] base16: Reduce GC pressure in bytevector->base16-str= ing. > > This makes bytevector->base16-string two times faster. > > * guix/base16.scm (bytevector->base16-string): Use utf8->string > and iteration instead of string-concatenate and named let. LGTM. How did you measure performance for this one? Thanks, Ludo=E2=80=99.