Hi all, As a learning exercise, I am experimenting in chess/alpha-beta search/bitboards. In this domain lot of bitwise operations are required. My goal is to keep learning scheme and Gambit, therefore I will be happy to stay with what I have right now if the only option is to switch to C et similia.
I am asking here for an advice in improving runtime speed crunching bitwise operations on u64 integers since I have no experience using scheme and Gambit. Looking at the documentation I see that fixnum is providing some help but I apparently u64 integers are not "compatible" with fixnum operations
(fixnum? 18446744073709551615)
#f
Can you share suggestions for my next exercise? Thank you in advance
Paolo
Afficher les réponses par date
On 3/31/20 3:50 PM, Paolo Montrasi wrote:
I am asking here for an advice in improving runtime speed crunching bitwise operations on u64 integers since I have no experience using scheme and Gambit. Looking at the documentation I see that fixnum is providing some help but I apparently u64 integers are not "compatible" with fixnum operations
(fixnum? 18446744073709551615)
#f
Can you share suggestions for my next exercise
That may be possible using some of Gambit's low-level, internal, unsafe, very-bad-indeed routines for manipulating bignum "adigits" (for "addition digits", although they're the size used for many other things), which are 64 bits, unsigned, on 64-bit machines. (They're only 14 bits wide in the universal backend, though.)
You'll find these routines in _num.scm:
;;; Sets x[i] to x[i] & y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-and! x i y j))
;;; Sets x[i] to ~x[i] & y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-andc1! x i y j))
;;; Sets x[i] to x[i] & ~y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-andc2! x i y j))
;;; Sets x[i] to ~(x[i] ^ y[j]) (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-eqv! x i y j))
;;; Sets x[i] to x[i] | y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-ior! x i y j))
;;; Sets x[i] to ~(x[i] & y[j]) (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-nand! x i y j))
;;; Sets x[i] to ~(x[i] | y[j]) (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-nor! x i y j))
;;; Sets x[i] to !x[i] (accessing x as adigits) (define-prim (##bignum.adigit-bitwise-not! x i))
;;; Sets x[i] to ~x[i] | y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-orc1! x i y j))
;;; Sets x[i] to x[i] | ~y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-orc2! x i y j))
;;; Sets x[i] to x[i] ^ y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-xor! x i y j))
There's also
(define-prim (##bignum.make k x complement?)
which makes a new bignum with k adigits, copying x if it's given, and complementing things if the last argument is #t. It may be easier to just call
(define-prim (##bignum.copy x) (##bignum.make (##bignum.adigit-length x) x #f))
Using one of
(define ##bignum.adigit-ones (##fixnum->bignum -1)) ;; the 0th adigit is all ones (define ##bignum.adigit-zeros (##fixnum->bignum 0)) ;; the 0th adigit is all zeros
as a starter.
Now, ##bignum.adigit-ones and ##bignum.adigit-zeros are unnormalized bignums, as could be many other results one can get by using these routines that manipulate adigits, so I wouldn't try to print them using the usual library routines, but this could get you started.
Brad
Hi Brad, thank you for your suggestion. I ended up in testing something similar to the following example
(define (u64-xor . args-list) (##bignum.normalize! (fold (lambda (x big) (let ((x-big (if (fixnum? x) (##fixnum->bignum x) x))) (##bignum.adigit-bitwise-xor! big 0 x-big 0) big)) (##bignum.make 2 ##bignum.adigit-zeros #f) args-list)))
it worked but with no noticeable improvements and this fact helped me in looking elsewhere to find speed problems … I found a lot of them in my code of course ;-)
Well I tried to do my best to fix most of the performance issues and I am now pretty happy with what I have come to, therefore I point you to my code in case you are looking for a fun "chess scheme" challenge.
https://github.com/pmon/coronachess https://github.com/pmon/coronachess
Thank you for your help, my best Paolo
Il giorno 01 apr 2020, alle ore 19:15, Bradley Lucier lucier@purdue.edu ha scritto:
On 3/31/20 3:50 PM, Paolo Montrasi wrote:
I am asking here for an advice in improving runtime speed crunching bitwise operations on u64 integers since I have no experience using scheme and Gambit. Looking at the documentation I see that fixnum is providing some help but I apparently u64 integers are not "compatible" with fixnum operations
(fixnum? 18446744073709551615)
#f Can you share suggestions for my next exercise
That may be possible using some of Gambit's low-level, internal, unsafe, very-bad-indeed routines for manipulating bignum "adigits" (for "addition digits", although they're the size used for many other things), which are 64 bits, unsigned, on 64-bit machines. (They're only 14 bits wide in the universal backend, though.)
You'll find these routines in _num.scm:
;;; Sets x[i] to x[i] & y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-and! x i y j))
;;; Sets x[i] to ~x[i] & y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-andc1! x i y j))
;;; Sets x[i] to x[i] & ~y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-andc2! x i y j))
;;; Sets x[i] to ~(x[i] ^ y[j]) (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-eqv! x i y j))
;;; Sets x[i] to x[i] | y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-ior! x i y j))
;;; Sets x[i] to ~(x[i] & y[j]) (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-nand! x i y j))
;;; Sets x[i] to ~(x[i] | y[j]) (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-nor! x i y j))
;;; Sets x[i] to !x[i] (accessing x as adigits) (define-prim (##bignum.adigit-bitwise-not! x i))
;;; Sets x[i] to ~x[i] | y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-orc1! x i y j))
;;; Sets x[i] to x[i] | ~y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-orc2! x i y j))
;;; Sets x[i] to x[i] ^ y[j] (accessing x and y as adigits) (define-prim (##bignum.adigit-bitwise-xor! x i y j))
There's also
(define-prim (##bignum.make k x complement?)
which makes a new bignum with k adigits, copying x if it's given, and complementing things if the last argument is #t. It may be easier to just call
(define-prim (##bignum.copy x) (##bignum.make (##bignum.adigit-length x) x #f))
Using one of
(define ##bignum.adigit-ones (##fixnum->bignum -1)) ;; the 0th adigit is all ones (define ##bignum.adigit-zeros (##fixnum->bignum 0)) ;; the 0th adigit is all zeros
as a starter.
Now, ##bignum.adigit-ones and ##bignum.adigit-zeros are unnormalized bignums, as could be many other results one can get by using these routines that manipulate adigits, so I wouldn't try to print them using the usual library routines, but this could get you started.
Brad
On 4/26/20 9:48 AM, Paolo wrote:
Well I tried to do my best to fix most of the performance issues and I am now pretty happy with what I have come to, therefore I point you to my code in case you are looking for a fun "chess scheme" challenge.
Cool! It looks like a nice project.
I looked at your code a bit. I usually add the following declarations when working with code that generally does not work with flonums:
(declare (standard-bindings) + (extended-bindings) + (mostly-fixnum) (not safe) (block))
And, it seems that if you rename the "bitwise" functions then the compiler doesn't inline checks for fixnum arguments and use the inlined fixnum operations. I filed an issue:
https://github.com/gambit/gambit/issues/535
If you redefine u64-and, etc., as macros, like
@@ -214,16 +216,24 @@ ; int "___return(__builtin_ffsl(___arg1) - 1);"))
; (define (u64-and . args-list) (fold u64c-and #xFFFFFFFFFFFFFFFF args-list)) -(define u64-and bitwise-and) +; (define u64-and bitwise-and) +(define-macro (u64-and . rest) + `(bitwise-and ,@rest))
; (define (u64-ior . args-list) (fold u64c-ior 0 args-list)) -(define u64-ior bitwise-ior) +; (define u64-ior bitwise-ior) +(define-macro (u64-ior . rest) + `(bitwise-ior ,@rest))
; (define (u64-xor . args-list) (fold u64c-xor 0 args-list)) -(define u64-xor bitwise-xor) +; (define u64-xor bitwise-xor) +(define-macro (u64-xor . rest) + `(bitwise-xor ,@rest))
; (define u64-not u64c-not) -(define u64-not bitwise-not) +; (define u64-not bitwise-not) +(define-macro (u64-not . rest) + `(bitwise-not ,@rest))
; (define u64-shift u64c-shift) (define (u64-shift n i) (u64-and #xFFFFFFFFFFFFFFFF (arithmetic-shift n i))) @@ -232,10 +242,14 @@ (define (u64-mult a b) (u64-and #xFFFFFFFFFFFFFFFF (* a b)))
; (define bitwise-bit-count c-bitcount) -(define bitwise-bit-count bit-count) +; (define bitwise-bit-count bit-count) +(define-macro (bitwise-bit-count . rest) + `(bit-count ,@rest))
; (define bitscan-fwd c-bitscan-fwd) -(define bitscan-fwd first-bit-set) +; (define bitscan-fwd first-bit-set) +(define-macro (bitscan-fwd . rest) + `(first-bit-set ,@rest))
; (define reset-ls1b c-reset-ls1b) (define (reset-ls1b bits) (u64-and bits (- bits 1)))
then you get a small but noticeable speedup.
Brad
Marc
On Apr 26, 2020, at 9:48 AM, Paolo pmontrasi@gmail.com wrote:
Hi Brad, thank you for your suggestion. I ended up in testing something similar to the following example
(define (u64-xor . args-list) (##bignum.normalize! (fold (lambda (x big) (let ((x-big (if (fixnum? x) (##fixnum->bignum x) x))) (##bignum.adigit-bitwise-xor! big 0 x-big 0) big)) (##bignum.make 2 ##bignum.adigit-zeros #f) args-list)))
it worked but with no noticeable improvements and this fact helped me in looking elsewhere to find speed problems … I found a lot of them in my code of course ;-)
Well I tried to do my best to fix most of the performance issues and I am now pretty happy with what I have come to, therefore I point you to my code in case you are looking for a fun "chess scheme" challenge.
https://github.com/pmon/coronachess
Thank you for your help, my best Paolo
Nice! I’ll have to try it out… As you noticed the name Gambit has its origins in chess… I used to play regularly. A gambit is a kind of scheme… and it is a calculated risk (which felt quite appropriate for my PhD work which was also risky).
To do high speed calculations on raw 64 bit integers, I would tend to use u64vectors (or even u8vectors) to store the 64 bit integers and to drop down to C when some operation on these integers must be done without creating bignums. Something along these lines:
(declare (standard-bindings) (extended-bindings) (not safe) )
(c-declare "#define ELEM0(u64vect) ___BODY_AS(u64vect,___tSUBTYPED)[0]")
(define-macro (u64-xor! v1 v2) ;; v1[0] = v1[0] ^ v2[0] `(##c-code "ELEM0(___ARG1) ^= ELEM0(___ARG2);" v1 v2))
(define v1 (u64vector #x0123456789ABCDEF)) (define v2 (u64vector #x00FF00FF00FF00FF))
(println (number->string (u64vector-ref v1 0) 16)) (println (number->string (u64vector-ref v2 0) 16))
(u64-xor! v1 v2)
(println (number->string (u64vector-ref v1 0) 16))
You could create a small library of such macros for the various 64 bit operations, and try to avoid as much as possible conversions to and from bignums which probably incurs a high overhead in your application.
Marc
On Apr 26, 2020, at 6:20 PM, Marc Feeley feeley@iro.umontreal.ca wrote:
(c-declare "#define ELEM0(u64vect) ___BODY_AS(u64vect,___tSUBTYPED)[0]")
(define-macro (u64-xor! v1 v2) ;; v1[0] = v1[0] ^ v2[0] `(##c-code "ELEM0(___ARG1) ^= ELEM0(___ARG2);" v1 v2))
He originally had similar code:
; (define u64c-and ; (c-lambda (unsigned-int64 unsigned-int64) ; unsigned-int64 "___return(___arg1 & ___arg2);”))
Would inlining the code as you did give better performance instead of using a c-lambda?
Brad
With a c-lambda the procedure itself and the conversion functions have to be called, and this adds considerable overhead on such a tiny piece of code. A ##c-code has no overhead.
Marc
On Apr 26, 2020, at 7:14 PM, Lucier, Bradley J bradley.j.lucier.1@purdue.edu wrote:
On Apr 26, 2020, at 6:20 PM, Marc Feeley feeley@iro.umontreal.ca wrote:
(c-declare "#define ELEM0(u64vect) ___BODY_AS(u64vect,___tSUBTYPED)[0]")
(define-macro (u64-xor! v1 v2) ;; v1[0] = v1[0] ^ v2[0] `(##c-code "ELEM0(___ARG1) ^= ELEM0(___ARG2);" v1 v2))
He originally had similar code:
; (define u64c-and ; (c-lambda (unsigned-int64 unsigned-int64) ; unsigned-int64 "___return(___arg1 & ___arg2);”))
Would inlining the code as you did give better performance instead of using a c-lambda?
Brad
On Sun, 26 Apr 2020 22:23:03 -0400 Marc Feeley feeley@iro.umontreal.ca wrote:
With a c-lambda the procedure itself and the conversion functions have to be called, and this adds considerable overhead on such a tiny piece of code. A ##c-code has no overhead.
those lovely surprizes; if only there was a reference in the manual ;-)
These days I ran into bitwise operation within needs too. I my case composing network packages efficiently.
Q: What's the effect of `(declare (not safe))` in this context? Will c-lambda's still generate the type check operations (which I *really* welcome during development) or should I consider using cond-expand (on which feature btw?) to use ##c-code for performance sake?
Best
/Jörg
Thanks Marc, I see the point in bignums conversion and I am trying your suggested approach. Mostly I have u64vectors with multiple elements to use in the bitwise operation and being able to reference / use one of the arbitrary elements in the vector could avoid in converting to/from bignums using u64vector-ref / u64-vector-set! , if I understood your point.
I tried the following code but it is not working
(c-declare "#define ELEM_N(u64vect,index) ___BODY_AS(u64vect,___tSUBTYPED)[index]")
(define-macro (u64-xor! v1 i1 v2 i2) `(##c-code "ELEM_N(___ARG1,___ARG2) ^= ELEM_N(___ARG3,___ARG4);" ,v1 ,i1 ,v2 ,i2))
running
(define u64one-bits (u64vector 1)) (define v7 (make-u64vector 10 0)) (pretty-print v7) (u64-xor! v7 0 u64one-bits 0) (u64-xor! v7 1 u64one-bits 0) ; trying to use the second element with index 1 (pretty-print v7)
I get the following
#u64(0 0 0 0 0 0 0 0 0 0) #u64(1 0 0 0 1 0 0 0 0 0)
… of course that was an easy but incorrect guess ;-) Is there a way to declare a macro that gets the index of the vector as parameter?
Thanks Paolo
Il giorno 27 apr 2020, alle ore 00:20, Marc Feeley feeley@iro.umontreal.ca ha scritto:
Marc
On Apr 26, 2020, at 9:48 AM, Paolo pmontrasi@gmail.com wrote:
Hi Brad, thank you for your suggestion. I ended up in testing something similar to the following example
(define (u64-xor . args-list) (##bignum.normalize! (fold (lambda (x big) (let ((x-big (if (fixnum? x) (##fixnum->bignum x) x))) (##bignum.adigit-bitwise-xor! big 0 x-big 0) big)) (##bignum.make 2 ##bignum.adigit-zeros #f) args-list)))
it worked but with no noticeable improvements and this fact helped me in looking elsewhere to find speed problems … I found a lot of them in my code of course ;-)
Well I tried to do my best to fix most of the performance issues and I am now pretty happy with what I have come to, therefore I point you to my code in case you are looking for a fun "chess scheme" challenge.
https://github.com/pmon/coronachess
Thank you for your help, my best Paolo
Nice! I’ll have to try it out… As you noticed the name Gambit has its origins in chess… I used to play regularly. A gambit is a kind of scheme… and it is a calculated risk (which felt quite appropriate for my PhD work which was also risky).
To do high speed calculations on raw 64 bit integers, I would tend to use u64vectors (or even u8vectors) to store the 64 bit integers and to drop down to C when some operation on these integers must be done without creating bignums. Something along these lines:
(declare (standard-bindings) (extended-bindings) (not safe) )
(c-declare "#define ELEM0(u64vect) ___BODY_AS(u64vect,___tSUBTYPED)[0]")
(define-macro (u64-xor! v1 v2) ;; v1[0] = v1[0] ^ v2[0] `(##c-code "ELEM0(___ARG1) ^= ELEM0(___ARG2);" v1 v2))
(define v1 (u64vector #x0123456789ABCDEF)) (define v2 (u64vector #x00FF00FF00FF00FF))
(println (number->string (u64vector-ref v1 0) 16)) (println (number->string (u64vector-ref v2 0) 16))
(u64-xor! v1 v2)
(println (number->string (u64vector-ref v1 0) 16))
You could create a small library of such macros for the various 64 bit operations, and try to avoid as much as possible conversions to and from bignums which probably incurs a high overhead in your application.
Marc
Hi all, the macro approach is giving about x2 speed even if not all bitwise operation are using it. Still I am using bignums to pass around bit boards in my code.
compiled binary with regular bitwise operation
position fen r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1 perft depth 4 info string depth= 4 nodes= 4085603 time= 9604. nps= 425406
compiled binary with the macro approach
position fen r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1 perft depth 4 info string depth= 4 nodes= 4085603 time= 5795. nps= 705022
I had to fix lots of bottlenecks in my code to see the nice boost this low level code can give. Thanks!
Paolo
Il giorno 27 apr 2020, alle ore 00:20, Marc Feeley feeley@iro.umontreal.ca ha scritto:
Marc
On Apr 26, 2020, at 9:48 AM, Paolo pmontrasi@gmail.com wrote:
Hi Brad, thank you for your suggestion. I ended up in testing something similar to the following example
(define (u64-xor . args-list) (##bignum.normalize! (fold (lambda (x big) (let ((x-big (if (fixnum? x) (##fixnum->bignum x) x))) (##bignum.adigit-bitwise-xor! big 0 x-big 0) big)) (##bignum.make 2 ##bignum.adigit-zeros #f) args-list)))
it worked but with no noticeable improvements and this fact helped me in looking elsewhere to find speed problems … I found a lot of them in my code of course ;-)
Well I tried to do my best to fix most of the performance issues and I am now pretty happy with what I have come to, therefore I point you to my code in case you are looking for a fun "chess scheme" challenge.
https://github.com/pmon/coronachess
Thank you for your help, my best Paolo
Nice! I’ll have to try it out… As you noticed the name Gambit has its origins in chess… I used to play regularly. A gambit is a kind of scheme… and it is a calculated risk (which felt quite appropriate for my PhD work which was also risky).
To do high speed calculations on raw 64 bit integers, I would tend to use u64vectors (or even u8vectors) to store the 64 bit integers and to drop down to C when some operation on these integers must be done without creating bignums. Something along these lines:
(declare (standard-bindings) (extended-bindings) (not safe) )
(c-declare "#define ELEM0(u64vect) ___BODY_AS(u64vect,___tSUBTYPED)[0]")
(define-macro (u64-xor! v1 v2) ;; v1[0] = v1[0] ^ v2[0] `(##c-code "ELEM0(___ARG1) ^= ELEM0(___ARG2);" v1 v2))
(define v1 (u64vector #x0123456789ABCDEF)) (define v2 (u64vector #x00FF00FF00FF00FF))
(println (number->string (u64vector-ref v1 0) 16)) (println (number->string (u64vector-ref v2 0) 16))
(u64-xor! v1 v2)
(println (number->string (u64vector-ref v1 0) 16))
You could create a small library of such macros for the various 64 bit operations, and try to avoid as much as possible conversions to and from bignums which probably incurs a high overhead in your application.
Marc
-
Bradley Lucier -
Jörg F. Wittenberger -
Lucier, Bradley J -
Marc Feeley -
Paolo -
Paolo Montrasi