Welcome to the CHICKEN Scheme pasting service

base64-benchmark: chicken-5 twice as fast as chicken-6 pasted by klm` 1 days ago

;;; testing base64 encoding algorithm (the non-padding part, anyway)
;;; chicken5.4.0 is at around 200MB/s and c6 is at around 100MB/s. a C implementation is
;;; included for reference, which , on my machine, does at around 2000MB/s for both C5 and C6.
;;;
;;; csc6git -v -m main -O5 bench64.scm
;;; pv -Ss 8G /dev/zero | ./bench64 >/dev/null
;;;  0:00:42 [93.3MiB/s] ...
;;;
;;; csc5 -m main -O5 bench64.scm -o bench64-c5
;;; pv -Ss 64G /dev/zero | ./bench64-c5 >/dev/null
;;;  0:00:14 [ 215MiB/s] ...
;;; csc6git -v -m main -O5 bench64.scm -o bench64-c
;;; [csi6g] klm@rex ~/p/chicken-base64 > pv -Ss 8G /dev/zero | ./bench64-c >/dev/null
;;;   0:00:04 [1.96GiB/s] ...
;;;
;;; 2 questions:
;;; (1) why does C6 perform worse than C5? I tried to dodge all UTF8/encoding mechanisms.
;;; (2) I might have expected this to do bettar than 10% of its C counterpart. Is there anything
;;;     that could be done to allow the Chicken compiler to improve on this?
;;;
;;; Note that I don't need to consider trailing or padding, I'm just interested in encoding
;;; large base64 chunks fast-ish. The corner-cases (padding, non-multiples of 3 byte input etc)
;;; doesn't warrant optimization. I'd love to see if the Scheme version of this alrogithm could
;;; compete with C, but I don't know if that's realistic.
;;;

(import chicken.bitwise srfi-4 ;;scheme.base
        chicken.fixnum chicken.foreign chicken.io
        srfi-4)

;; more or less taken from https://base64.dev/articles/base64-c
(foreign-declare "
static const char b64_enc_table[] =
    \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"
    \"abcdefghijklmnopqrstuvwxyz\"
    \"0123456789+/\";

int base64_encode(const uint8_t *in, const int in_start, const int in_end,
		   uint8_t *out, int out_start, int out_end) {

    size_t i, j;
    for (i = in_start, j = out_start; i + 2 < in_end; i += 3) {
        uint32_t n = ((uint32_t)in[i] << 16)
                   | ((uint32_t)in[i + 1] << 8)
                   |  (uint32_t)in[i + 2];
        out[j++] = b64_enc_table[(n >> 18) & 0x3F];
        out[j++] = b64_enc_table[(n >> 12) & 0x3F];
        out[j++] = b64_enc_table[(n >>  6) & 0x3F];
        out[j++] = b64_enc_table[ n        & 0x3F];
    }
    return j;
}
")

(define base64e/c (foreign-lambda int "base64_encode"
                             u8vector int int
                             u8vector int int))
(define base64e/scheme
  (let ()

    (define alphabet/default
      (list->u8vector
       (map char->integer
            (string->list
             "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"))))
    (define (lookup i) (u8vector-ref alphabet/default i))
    
    (lambda (in in-start in-end dest dest-start dest-end)
      (let ((stop (- in-end 2)))
        (let loop ((in-pos in-start)
                   (dest-pos dest-start))
          (if (fx<= in-pos stop)
              (let ((w (fx+      (fxshl (u8vector-ref in (fx+ in-pos 0)) 16)
                            (fx+ (fxshl (u8vector-ref in (fx+ in-pos 1))  8)
                                 (fxshl (u8vector-ref in (fx+ in-pos 2))  0)))))
                (u8vector-set! dest (fx+ dest-pos 0) (lookup (fxand (fxshr w -18) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 1) (lookup (fxand (fxshr w -12) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 2) (lookup (fxand (fxshr w  -6) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 3) (lookup (fxand (fxshr w  -0) #x3F)))

                (loop (fx+ in-pos 3) (fx+ dest-pos 4)))
              dest-pos))))))

(let ((in  (make-u8vector 4096 0))
      (out (make-u8vector (* (quotient (+ 2 4096) 3) 4))))
  (let loop ()
    (let* ((in-read (cond-expand (chicken-6 (read-bytevector! in))
                                 (chicken-5 (read-u8vector! #f in))
                                 (else (error "bad bad no 6"))))
           (dest-read
            ( ;; base64e/scheme
              base64e/c
             in 0 in-read  out 0 (u8vector-length out))))
      (unless (zero? in-read)
        (cond-expand
         (chicken-6 (write-bytevector out (current-output-port) 0 dest-read))
         (chicken-5 (write-u8vector   out (current-output-port) 0 dest-read)))
        (loop)))))

fix: using base643/scheme pasted by klm` 1 days ago

;;; testing base64 encoding algorithm (the non-padding part, anyway)
;;; chicken5.4.0 is at around 200MB/s and c6 is at around 100MB/s. a C implementation is
;;; included for reference, which , on my machine, does at around 2000MB/s for both C5 and C6.
;;;
;;; csc6git -v -m main -O5 bench64.scm
;;; pv -Ss 8G /dev/zero | ./bench64 >/dev/null
;;;  0:00:42 [93.3MiB/s] ...
;;;
;;; csc5 -m main -O5 bench64.scm -o bench64-c5
;;; pv -Ss 64G /dev/zero | ./bench64-c5 >/dev/null
;;;  0:00:14 [ 215MiB/s] ...
;;; csc6git -v -m main -O5 bench64.scm -o bench64-c
;;; [csi6g] klm@rex ~/p/chicken-base64 > pv -Ss 8G /dev/zero | ./bench64-c >/dev/null
;;;   0:00:04 [1.96GiB/s] ...
;;;
;;; 2 questions:
;;; (1) why does C6 perform worse than C5? I tried to dodge all UTF8/encoding mechanisms.
;;; (2) I might have expected this to do bettar than 10% of its C counterpart. Is there anything
;;;     that could be done to allow the Chicken compiler to improve on this?
;;;
;;; Note that I don't need to consider trailing or padding, I'm just interested in encoding
;;; large base64 chunks fast-ish. The corner-cases (padding, non-multiples of 3 byte input etc)
;;; doesn't warrant optimization. I'd love to see if the Scheme version of this alrogithm could
;;; compete with C, but I don't know if that's realistic.
;;;

(import chicken.bitwise srfi-4 ;;scheme.base
        chicken.fixnum chicken.foreign chicken.io
        srfi-4)

;; more or less taken from https://base64.dev/articles/base64-c
(foreign-declare "
static const char b64_enc_table[] =
    \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"
    \"abcdefghijklmnopqrstuvwxyz\"
    \"0123456789+/\";

int base64_encode(const uint8_t *in, const int in_start, const int in_end,
		   uint8_t *out, int out_start, int out_end) {

    size_t i, j;
    for (i = in_start, j = out_start; i + 2 < in_end; i += 3) {
        uint32_t n = ((uint32_t)in[i] << 16)
                   | ((uint32_t)in[i + 1] << 8)
                   |  (uint32_t)in[i + 2];
        out[j++] = b64_enc_table[(n >> 18) & 0x3F];
        out[j++] = b64_enc_table[(n >> 12) & 0x3F];
        out[j++] = b64_enc_table[(n >>  6) & 0x3F];
        out[j++] = b64_enc_table[ n        & 0x3F];
    }
    return j;
}
")

(define base64e/c (foreign-lambda int "base64_encode"
                             u8vector int int
                             u8vector int int))
(define base64e/scheme
  (let ()

    (define alphabet/default
      (list->u8vector
       (map char->integer
            (string->list
             "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"))))
    (define (lookup i) (u8vector-ref alphabet/default i))
    
    (lambda (in in-start in-end dest dest-start dest-end)
      (let ((stop (- in-end 2)))
        (let loop ((in-pos in-start)
                   (dest-pos dest-start))
          (if (fx<= in-pos stop)
              (let ((w (fx+      (fxshl (u8vector-ref in (fx+ in-pos 0)) 16)
                            (fx+ (fxshl (u8vector-ref in (fx+ in-pos 1))  8)
                                 (fxshl (u8vector-ref in (fx+ in-pos 2))  0)))))
                (u8vector-set! dest (fx+ dest-pos 0) (lookup (fxand (fxshr w -18) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 1) (lookup (fxand (fxshr w -12) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 2) (lookup (fxand (fxshr w  -6) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 3) (lookup (fxand (fxshr w  -0) #x3F)))

                (loop (fx+ in-pos 3) (fx+ dest-pos 4)))
              dest-pos))))))

(let ((in  (make-u8vector 4096 0))
      (out (make-u8vector (* (quotient (+ 2 4096) 3) 4))))
  (let loop ()
    (let* ((in-read (cond-expand (chicken-6 (read-bytevector! in))
                                 (chicken-5 (read-u8vector! #f in))
                                 (else (error "bad bad no 6"))))
           (dest-read
            (base64e/scheme
             ;; base64e/c ;; <--- replace with this procedure to try the faster C version
             in 0 in-read  out 0 (u8vector-length out))))
      (unless (zero? in-read)
        (cond-expand
         (chicken-6 (write-bytevector out (current-output-port) 0 dest-read))
         (chicken-5 (write-u8vector   out (current-output-port) 0 dest-read)))
        (loop)))))

modified version: 1000MB/s on C5 but still pasted by klm` 1 days ago

;;; EDIT: manually unwrapping `lookup` improves things dramatically on C5
;;;       unsure if C6 is able to do this too

(import chicken.bitwise srfi-4 ;;scheme.base
        chicken.fixnum chicken.foreign chicken.io
        srfi-4)

;; more or less taken from https://base64.dev/articles/base64-c
(foreign-declare "
static const char b64_enc_table[] =
    \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"
    \"abcdefghijklmnopqrstuvwxyz\"
    \"0123456789+/\";

int base64_encode(const uint8_t *in, const int in_start, const int in_end,
		   uint8_t *out, int out_start, int out_end) {

    size_t i, j;
    for (i = in_start, j = out_start; i + 2 < in_end; i += 3) {
        uint32_t n = ((uint32_t)in[i] << 16)
                   | ((uint32_t)in[i + 1] << 8)
                   |  (uint32_t)in[i + 2];
        out[j++] = b64_enc_table[(n >> 18) & 0x3F];
        out[j++] = b64_enc_table[(n >> 12) & 0x3F];
        out[j++] = b64_enc_table[(n >>  6) & 0x3F];
        out[j++] = b64_enc_table[ n        & 0x3F];
    }
    return j;
}
")

(define base64e/c (foreign-lambda int "base64_encode"
                             u8vector int int
                             u8vector int int))
(define base64e/scheme
  (let ()

    (define alphabet/default
      (list->u8vector
       (map char->integer
            (string->list
             "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"))))    

    (lambda (in in-start in-end dest dest-start dest-end)

      (let ((stop (- in-end 2)))
        (let myloop123 ((in-pos in-start)
                   (dest-pos dest-start))
          (if (fx<= in-pos stop)
              (let ((w (fx+      (fxshl (u8vector-ref in (fx+ in-pos 0)) 16)
                                 (fx+ (fxshl (u8vector-ref in (fx+ in-pos 1))  8)
                                      (fxshl (u8vector-ref in (fx+ in-pos 2))  0)))))
                (u8vector-set! dest (fx+ dest-pos 0) (u8vector-ref alphabet/default (fxand (fxshr w -18) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 1) (u8vector-ref alphabet/default (fxand (fxshr w -12) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 2) (u8vector-ref alphabet/default (fxand (fxshr w  -6) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 3) (u8vector-ref alphabet/default (fxand (fxshr w  -0) #x3F)))

                (myloop123 (fx+ in-pos 3) (fx+ dest-pos 4)))
              dest-pos))))))

(let ((in  (make-u8vector 4096 0))
      (out (make-u8vector (* (quotient (+ 2 4096) 3) 4))))
  (let loop ()
    (let* ((in-read (cond-expand (chicken-6 (read-bytevector! in))
                                 (chicken-5 (read-u8vector! #f in))
                                 (else (error "bad bad no 6"))))
           (dest-read
            (base64e/scheme
             ;; base64e/c ;; <--- replace with this procedure to try the faster C version
             in 0 in-read  out 0 (u8vector-length out))))
      (unless (zero? in-read)
        (cond-expand
         (chicken-6 (write-bytevector out (current-output-port) 0 dest-read))
         (chicken-5 (write-u8vector   out (current-output-port) 0 dest-read)))
        (loop)))))

faster version with alphabet in let* pasted by klm` 1 days ago

;;; sjaman pointed out: alphabet inside a let is faster than define

;; and as crzcrz pointed out, chicken has had
;; recent improvements on u8vector things, so
;; we need to stay on the very master tip.
;;
;; this gets me 1200MB/s on C6 which is the
;; fastest combination so far. pretty good
;; considering C can do 2000MB/s. but
;; I still can't use my convenient 
;; `lookup` function without a 50% performance
;; loss.

(import chicken.bitwise srfi-4 scheme.base
        chicken.fixnum chicken.foreign chicken.io
        srfi-4 chicken.number-vector)

(define base64e/scheme
  (let* ((alphabet/default (list->u8vector
                            (map char->integer
                                 (string->list
                                  "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"))))
         (lookup (lambda (i) (u8vector-ref alphabet/default i))))
      
    (lambda (in in-start in-end dest dest-start dest-end
                #!key )

      (let ((stop (- in-end 2)))
        (let myloop123 ((in-pos in-start)
                        (dest-pos dest-start))
          (if (fx<= in-pos stop)
              (let ((w (fx+      (fxshl (u8vector-ref in (fx+ in-pos 0)) 16)
                                 (fx+ (fxshl (u8vector-ref in (fx+ in-pos 1))  8)
                                      (fxshl (u8vector-ref in (fx+ in-pos 2))  0)))))
                (u8vector-set! dest (fx+ dest-pos 0) (u8vector-ref alphabet/default (fxand (fxshr w -18) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 1) (u8vector-ref alphabet/default (fxand (fxshr w -12) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 2) (u8vector-ref alphabet/default (fxand (fxshr w  -6) #x3F)))
                (u8vector-set! dest (fx+ dest-pos 3) (u8vector-ref alphabet/default (fxand (fxshr w  -0) #x3F)))

                (myloop123 (fx+ in-pos 3) (fx+ dest-pos 4)))
              dest-pos))))))

(let ((in  (make-u8vector 4096 0))
      (out (make-u8vector (* (quotient (+ 2 4096) 3) 4))))
  (let loop ()
    (let* ((in-read (cond-expand (chicken-6 (read-bytevector! in))
                                 (chicken-5 (read-u8vector! #f in))
                                 (else (error "bad bad no 6"))))
           (dest-read
            (base64e/scheme
             ;; base64e/c ;; <--- replace with this procedure to try the faster C version
             in 0 in-read  out 0 (u8vector-length out))))
      (unless (zero? in-read)
        (cond-expand
         (chicken-6 (write-bytevector out (current-output-port) 0 dest-read))
         (chicken-5 (write-u8vector   out (current-output-port) 0 dest-read)))
        (loop)))))

lookup vs no-lookup added by klm` 1 days ago

here's the C without the `lookup` helper:


/* myloop123 in base64e/scheme in k203 in k199 in k196 in k193 in k190 */
static C_word f_220(C_word t0,C_word t1,C_word t2){
C_word tmp;
C_word t3;
C_word t4;
C_word t5;
C_word t6;
C_word t7;
C_word t8;
C_word t9;
C_word t10;
C_word t11;
C_word t12;
C_word t13;
C_word t14;
C_word t15;
C_word t16;
C_word t17;
C_word t18;
C_word t19;
C_word t20;
C_word t21;
C_word t22;
C_word t23;
C_word t24;
C_word t25;
C_word t26;
C_word t27;
C_word t28;
C_word t29;
C_word t30;
C_word t31;
C_word t32;
C_word t33;
C_word t34;
C_word t35;
C_word t36;
loop:{}
if(C_truep(C_fixnum_less_or_equal_p(t1,((C_word*)t0)[2]))){
t3=C_u_fixnum_plus(t1,C_fix(0));
t4=C_u_i_u8vector_ref(((C_word*)t0)[3],t3);
t5=C_fixnum_shift_left(t4,C_fix(16));
t6=C_u_fixnum_plus(t1,C_fix(1));
t7=C_u_i_u8vector_ref(((C_word*)t0)[3],t6);
t8=C_fixnum_shift_left(t7,C_fix(8));
t9=C_u_fixnum_plus(t1,C_fix(2));
t10=C_u_i_u8vector_ref(((C_word*)t0)[3],t9);
t11=C_fixnum_shift_left(t10,C_fix(0));
t12=C_u_fixnum_plus(t8,t11);
t13=C_u_fixnum_plus(t5,t12);
t14=C_u_fixnum_plus(t2,C_fix(0));
t15=C_fixnum_shift_right(t13,C_fix(-18));
t16=C_u_fixnum_and(t15,C_fix(63));
t17=C_u_i_u8vector_ref(((C_word*)t0)[4],t16);
t18=C_u_i_u8vector_set(((C_word*)t0)[5],t14,t17);
t19=C_u_fixnum_plus(t2,C_fix(1));
t20=C_fixnum_shift_right(t13,C_fix(-12));
t21=C_u_fixnum_and(t20,C_fix(63));
t22=C_u_i_u8vector_ref(((C_word*)t0)[4],t21);
t23=C_u_i_u8vector_set(((C_word*)t0)[5],t19,t22);
t24=C_u_fixnum_plus(t2,C_fix(2));
t25=C_fixnum_shift_right(t13,C_fix(-6));
t26=C_u_fixnum_and(t25,C_fix(63));
t27=C_u_i_u8vector_ref(((C_word*)t0)[4],t26);
t28=C_u_i_u8vector_set(((C_word*)t0)[5],t24,t27);
t29=C_u_fixnum_plus(t2,C_fix(3));
t30=C_fixnum_shift_right(t13,C_fix(0));
t31=C_u_fixnum_and(t30,C_fix(63));
t32=C_u_i_u8vector_ref(((C_word*)t0)[4],t31);
t33=C_u_i_u8vector_set(((C_word*)t0)[5],t29,t32);
t35=C_u_fixnum_plus(t1,C_fix(3));
t36=C_u_fixnum_plus(t2,C_fix(4));
t1=t35;
t2=t36;
goto loop;}
else{
return(t2);}}


nice and tight. with the lookup, an extra C call is introduced: 

static C_word f_220(C_word t0,C_word t1,C_word t2){
C_word tmp;
C_word t3;
C_word t4;
C_word t5;
C_word t6;
C_word t7;
C_word t8;
C_word t9;
C_word t10;
C_word t11;
C_word t12;
C_word t13;
C_word t14;
C_word t15;
C_word t16;
C_word t17;
C_word t18;
C_word t19;
C_word t20;
C_word t21;
C_word t22;
C_word t23;
C_word t24;
C_word t25;
C_word t26;
C_word t27;
C_word t28;
C_word t29;
C_word t30;
C_word t31;
C_word t32;
loop:{}
if(C_truep(C_fixnum_less_or_equal_p(t1,((C_word*)t0)[2]))){
t3=C_u_fixnum_plus(t1,C_fix(0));
t4=C_u_i_u8vector_ref(((C_word*)t0)[3],t3);
t5=C_fixnum_shift_left(t4,C_fix(16));
t6=C_u_fixnum_plus(t1,C_fix(1));
t7=C_u_i_u8vector_ref(((C_word*)t0)[3],t6);
t8=C_fixnum_shift_left(t7,C_fix(8));
t9=C_u_fixnum_plus(t1,C_fix(2));
t10=C_u_i_u8vector_ref(((C_word*)t0)[3],t9);
t11=C_fixnum_shift_left(t10,C_fix(0));
t12=C_u_fixnum_plus(t8,t11);
t13=C_u_fixnum_plus(t5,t12);
t14=C_u_fixnum_plus(t2,C_fix(0));
t15=C_fixnum_shift_right(t13,C_fix(-18));
t16=(
/* /home/klm/prj/chicken-base64/bench64.scm:22: lookup */
  f_206(((C_word*)t0)[4],C_u_fixnum_and(t15,C_fix(63)))
);
t17=C_u_i_u8vector_set(((C_word*)t0)[5],t14,t16);
t18=C_u_fixnum_plus(t2,C_fix(1));
t19=C_fixnum_shift_right(t13,C_fix(-12));
t20=(
/* /home/klm/prj/chicken-base64/bench64.scm:23: lookup */
  f_206(((C_word*)t0)[4],C_u_fixnum_and(t19,C_fix(63)))
);
t21=C_u_i_u8vector_set(((C_word*)t0)[5],t18,t20);
t22=C_u_fixnum_plus(t2,C_fix(2));
t23=C_fixnum_shift_right(t13,C_fix(-6));
t24=(
/* /home/klm/prj/chicken-base64/bench64.scm:24: lookup */
  f_206(((C_word*)t0)[4],C_u_fixnum_and(t23,C_fix(63)))
);
t25=C_u_i_u8vector_set(((C_word*)t0)[5],t22,t24);
t26=C_u_fixnum_plus(t2,C_fix(3));
t27=C_fixnum_shift_right(t13,C_fix(0));
t28=(
/* /home/klm/prj/chicken-base64/bench64.scm:25: lookup */
  f_206(((C_word*)t0)[4],C_u_fixnum_and(t27,C_fix(63)))
);
t29=C_u_i_u8vector_set(((C_word*)t0)[5],t26,t28);
t31=C_u_fixnum_plus(t1,C_fix(3));
t32=C_u_fixnum_plus(t2,C_fix(4));
t1=t31;
t2=t32;
goto loop;}
else{
return(t2);}}

where 


/* lookup in k203 in k199 in k196 in k193 in k190 */
static C_word f_206(C_word t0,C_word t1){
C_word tmp;
C_word t2;{}
return(C_u_i_u8vector_ref(((C_word*)t0)[2],t1));}

this probably causes the 10-30% performance degrade. why isn't the C compiler able to inline this, though? and why isn't CHICKEN?

Your annotation:

Enter a new annotation:

Your nick:
The title of your paste:
Your paste (mandatory) :
What's the Makefile target to generate the bootstrap compiler of CHICKEN?