Subject: Optimise bytevector->nix-base32-string and bytevector->base16-string.

From: Maxime Devos <[email-masked]>
Date: Tue, 07 Sep 2021 17:34:28 +0200

Hi guix,

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).

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.)

(*) GUIX_PROFILING=gc guix build -d pigx --no-grafts

Greetings,
Maxime.
From a93bad629e2746c77446cacddb9986506ce9ba88 Mon Sep 17 00:00:00 2001
From: Maxime Devos <[email-masked]>
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 37 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)

* guix/base32.scm
  (make-bytevector->base32-string): Eliminate 'reverse', use mutation instead.
---
 guix/base32.scm | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)

diff --git a/guix/base32.scm b/guix/base32.scm
index 49f191ba26..e76bf35ecc 100644
--- a/guix/base32.scm
+++ b/guix/base32.scm
@@ -141,12 +141,18 @@ the previous application or INIT."
 (define (make-bytevector->base32-string quintet-fold base32-chars)
   (lambda (bv)
     "Return a base32 encoding of BV using BASE32-CHARS as the alphabet."
-    (let ((chars (quintet-fold (lambda (q r)
-                                 (cons (vector-ref base32-chars q)
-                                       r))
-                               '()
-                               bv)))
-      (list->string (reverse chars)))))
+    ;; Mutation can be avoided with 'reverse'.  However, that would
+    ;; make this procedure about 30% slower due to the extra GC pressure.
+    (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)))))
 
 (define %nix-base32-chars
   ;; See `libutil/hash.cc'.
-- 
2.33.0

From dfd9b7557e31823320fcbd7abed77de295b7dce1 Mon Sep 17 00:00:00 2001
From: Maxime Devos <[email-masked]>
Date: Mon, 6 Sep 2021 00:46:17 +0200
Subject: [PATCH 2/2] base16: Reduce GC pressure in bytevector->base16-string.

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.
---
 guix/base16.scm | 44 +++++++++++++++++++++++---------------------
 1 file changed, 23 insertions(+), 21 deletions(-)

diff --git a/guix/base16.scm b/guix/base16.scm
index 6c15a9f588..9ac964dff0 100644
--- a/guix/base16.scm
+++ b/guix/base16.scm
@@ -1,5 +1,6 @@
 ;;; GNU Guix --- Functional package management for GNU
 ;;; Copyright © 2012, 2014, 2017 Ludovic Courtès <[email-masked]>
+;;; Copyright © 2021 Maxime Devos <[email-masked]>
 ;;;
 ;;; This file is part of GNU Guix.
 ;;;
@@ -32,27 +33,28 @@
 
 (define (bytevector->base16-string bv)
   "Return the hexadecimal representation of BV's contents."
-  (define len
-    (bytevector-length bv))
-
-  (let-syntax ((base16-chars (lambda (s)
-                               (syntax-case s ()
-                                 (_
-                                  (let ((v (list->vector
-                                            (unfold (cut > <> 255)
-                                                    (lambda (n)
-                                                      (format #f "~2,'0x" n))
-                                                    1+
-                                                    0))))
-                                    v))))))
-    (define chars base16-chars)
-    (let loop ((i len)
-               (r '()))
-      (if (zero? i)
-          (string-concatenate r)
-          (let ((i (- i 1)))
-            (loop i
-                  (cons (vector-ref chars (bytevector-u8-ref bv i)) r)))))))
+  (define len (bytevector-length bv))
+  (define utf8 (make-bytevector (* len 2)))
+  (let-syntax ((base16-octet-pairs
+                (lambda (s)
+                  (syntax-case s ()
+                    (_
+                     (string->utf8
+                      (string-concatenate
+                       (unfold (cut > <> 255)
+                               (lambda (n)
+                                 (format #f "~2,'0x" n))
+                               1+
+                               0))))))))
+    (define octet-pairs base16-octet-pairs)
+    (let loop ((i 0))
+      (when (< i len)
+        (bytevector-u16-native-set!
+         utf8 (* 2 i)
+         (bytevector-u16-native-ref octet-pairs
+                                    (* 2 (bytevector-u8-ref bv i))))
+        (loop (+ i 1))))
+    (utf8->string utf8)))
 
 (define base16-string->bytevector
   (let ((chars->value (fold (lambda (i r)
-- 
2.33.0

while true; do time GUIX_PROFILING=gc ./the-unoptimised-baseN-guix/bin/guix build -d pigx --no-grafts; done

# First run removed
/gnu/store/fq6x8d2vcm6sbjkimg7g8kcgb4c5xv1b-pigx-0.0.3.drv
Garbage collection statistics:
  heap size:        93.85 MiB
  allocated:        325.20 MiB
  GC times:         18
  time spent in GC: 3.69 seconds (24% of user time)

real	0m15,066s
user	0m15,149s
sys	0m0,709s
/gnu/store/fq6x8d2vcm6sbjkimg7g8kcgb4c5xv1b-pigx-0.0.3.drv
Garbage collection statistics:
  heap size:        93.85 MiB
  allocated:        325.19 MiB
  GC times:         18
  time spent in GC: 3.70 seconds (24% of user time)

real	0m15,924s
user	0m15,695s
sys	0m0,836s
/gnu/store/fq6x8d2vcm6sbjkimg7g8kcgb4c5xv1b-pigx-0.0.3.drv
Garbage collection statistics:
  heap size:        93.85 MiB
  allocated:        325.20 MiB
  GC times:         18
  time spent in GC: 3.66 seconds (24% of user time)

real	0m15,369s
user	0m15,339s
sys	0m0,704s
/gnu/store/fq6x8d2vcm6sbjkimg7g8kcgb4c5xv1b-pigx-0.0.3.drv
Garbage collection statistics:
  heap size:        93.85 MiB
  allocated:        325.20 MiB
  GC times:         18
  time spent in GC: 3.69 seconds (25% of user time)

real	0m14,889s
user	0m15,066s
sys	0m0,679s

Summary.

(define (avg . r) (/ (apply + r) (length r)))
(define (stddev . r) (* (/ (length r) (- (length r) 1)) (sqrt (apply avg (map (lambda (x) (expt (- x (apply avg r)) 2)) r)))))

(define  %time/gc '(3.69 3.70 3.66 3.69))
(values (apply avg %time/gc) (apply stddev %time/gc))
$7 = 3.685
$8 = 0.01999999999999997

(define  %real '(15.066 15.924 15.369 14.889))
(define  %user '(15.149 15.695 15.339 15.066))
(define  %sys  '(0.709 0.836 0.704 0.679))

(values (apply avg %real) (apply stddev %real))
$1 = 15.312000000000001
$2 = 0.5237633053202561

(values (apply avg %user) (apply stddev %user))
$3 = 15.31225
$4 = 0.32283655995634153

(values (apply avg %sys) (apply stddev %sys))
$5 = 0.732
$6 = 0.08148074073737369

while true; do time GUIX_PROFILING=gc ./the-optimised-baseN-guix/bin/guix build -d pigx --no-grafts; done

/gnu/store/jfjfg7dnis7v6947a0rncxdn3y1nz0ad-pigx-0.0.3.drv
Garbage collection statistics:
  heap size:        93.85 MiB
  allocated:        317.83 MiB
  GC times:         18
  time spent in GC: 3.71 seconds (22% of user time)

real	0m17,646s
user	0m16,539s
sys	0m0,705s
/gnu/store/jfjfg7dnis7v6947a0rncxdn3y1nz0ad-pigx-0.0.3.drv
Garbage collection statistics:
  heap size:        93.85 MiB
  allocated:        317.83 MiB
  GC times:         18
  time spent in GC: 3.63 seconds (22% of user time)

real	0m18,733s
user	0m16,698s
sys	0m0,691s
/gnu/store/jfjfg7dnis7v6947a0rncxdn3y1nz0ad-pigx-0.0.3.drv
Garbage collection statistics:
  heap size:        93.85 MiB
  allocated:        317.82 MiB
  GC times:         18
  time spent in GC: 3.72 seconds (24% of user time)

real	0m15,429s
user	0m15,448s
sys	0m0,696s
/gnu/store/jfjfg7dnis7v6947a0rncxdn3y1nz0ad-pigx-0.0.3.drv
Garbage collection statistics:
  heap size:        93.85 MiB
  allocated:        317.82 MiB
  GC times:         18
  time spent in GC: 3.70 seconds (24% of user time)

real	0m15,292s
user	0m15,315s
sys	0m0,635s

(define %time/gc '(3.71 3.63 3.72 3.70))
(define %time/real '(17.646 18.733 15.429 15.292))
(define %time/user '(16.539 16.698 15.448 15.315))
(define %time/sys '(0.705 0.691 0.696 0.635))

(values (apply avg %time/gc) (apply stddev %time/gc))
$17 = 3.6900000000000004
$18 = 0.04714045207910329
(values (apply avg %time/real) (apply stddev %time/real))
$19 = 16.775000000000002
$20 = 1.9554380015172506
(values (apply avg %time/user) (apply stddev %time/user))
$21 = 16.0
$22 = 0.8304360300468671
(values (apply avg %time/sys) (apply stddev %time/sys))
$23 = 0.6817499999999999
$24 = 0.03660449274186007

Tests show neither a decrease nor an increase in timings.
Now looking at the allocation count:

The heap size before:
  heap size:        93.85 MiB
  allocated:        325.20 MiB

The heap size after:
  heap size:        93.85 MiB
  allocated:        317.82 MiB

A small improvement (-2.3%).