(address . guix-patches@gnu.org)
7831fcdd8b8aab99cc95ba904076014b4c3cb6d2.camel@telenet.be
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 <maximedevos@telenet.be>
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(-)
Toggle diff (31 lines)
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 <maximedevos@telenet.be>
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(-)
Toggle diff (63 lines)
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 <ludo@gnu.org>
+;;; Copyright © 2021 Maxime Devos <maximedevos@telenet.be>
;;;
;;; 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%).
-----BEGIN PGP SIGNATURE-----
iI0EABYKADUWIQTB8z7iDFKP233XAR9J4+4iGRcl7gUCYTeGhBccbWF4aW1lZGV2
b3NAdGVsZW5ldC5iZQAKCRBJ4+4iGRcl7jqOAQCFvc3OjfQejFi5OvpJoFjHjH4N
ScQNeScR3iQ/XsH59wD7B8DvTWWad46Djmwup/0X6LBEiCylqdqu4cIrBXrDuAE=
=KwMr
-----END PGP SIGNATURE-----