Package: guix-patches;
Reported by: Maxime Devos <maximedevos <at> telenet.be>
Date: Tue, 7 Sep 2021 15:35:02 UTC
Severity: normal
Done: Maxime Devos <maximedevos <at> telenet.be>
Bug is archived. No further changes may be made.
Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):
From: Maxime Devos <maximedevos <at> telenet.be> To: guix-patches <at> gnu.org Subject: Optimise bytevector->nix-base32-string and bytevector->base16-string. Date: Tue, 07 Sep 2021 17:34:28 +0200
[Message part 1 (text/plain, inline)]
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.
[0001-base32-Reduce-GC-pressure-in-make-bytevector-base32-.patch (text/x-patch, inline)]
From a93bad629e2746c77446cacddb9986506ce9ba88 Mon Sep 17 00:00:00 2001
From: Maxime Devos <maximedevos <at> 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(-)
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
[0002-base16-Reduce-GC-pressure-in-bytevector-base16-strin.patch (text/x-patch, inline)]
From dfd9b7557e31823320fcbd7abed77de295b7dce1 Mon Sep 17 00:00:00 2001 From: Maxime Devos <maximedevos <at> 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(-) 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 <at> gnu.org> +;;; Copyright © 2021 Maxime Devos <maximedevos <at> 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
[perf-numbers.txt (text/plain, inline)]
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%).
[signature.asc (application/pgp-signature, inline)]
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.