Gambit-list Février 2015

gambit-list@iro.umontreal.ca

24 participants
33 discussions

Gambit versus Python+GMP: Timing for Chudnovskys' algorithm for pi
by Bradley Lucier 07 Avr '22

07 Avr '22

Bakul Shah wrote a particularly elegant Scheme program for Chudnovskys' algorithm for pi based on the Common Lisp program here: https://bitbucket.org/tarballs_are_good/numericl/src/5fe8fe7089f48ab1c8a388… Nick Craig-Wood wrote a Python program using the GMP multiprecision library that appears to use exactly the same algorithm here: http://www.craig-wood.com/nick/articles/pi-chudnovsky/ I modified both programs a bit and include them here. They time the calculation of $10^n$ digits of pi for $n=1,2,3,4,5,6,7$. The results are heine:~/programs/gambiteer/gambit> !py python pi_chudnovsky_bs_gmpy.py 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679 ('chudnovsky_gmpy_mpz_bs: digits', 10, 'time', 1.0967254638671875e-05) ('chudnovsky_gmpy_mpz_bs: digits', 100, 'time', 3.0040740966796875e-05) Last 5 digits 70679 OK ('chudnovsky_gmpy_mpz_bs: digits', 1000, 'time', 0.00025582313537597656) Last 5 digits 01989 OK ('chudnovsky_gmpy_mpz_bs: digits', 10000, 'time', 0.00386810302734375) Last 5 digits 75678 OK ('chudnovsky_gmpy_mpz_bs: digits', 100000, 'time', 0.0834801197052002) Last 5 digits 24646 OK ('chudnovsky_gmpy_mpz_bs: digits', 1000000, 'time', 1.655979871749878) Last 5 digits 58151 OK ('chudnovsky_gmpy_mpz_bs: digits', 10000000, 'time', 30.67442488670349) Last 5 digits 55897 OK heine:~/programs/gambiteer/gambit> gsi chud1.scm Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10, CPU time: 0.. Last 5 digits 26535. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100, CPU time: 0.. Last 5 digits 70679. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000, CPU time: .004. Last 5 digits 1989. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000, CPU time: .028. Last 5 digits 75678. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000, CPU time: .472. Last 5 digits 24646. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 6.448. Last 5 digits 58151. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000000, CPU time: 98.612. Last 5 digits 55897. So it appears that for this algorithm applied to large integers, GMP's bignum routines are about 3-4 times as fast as Gambit's bignum routines. Not so bad. For smaller bignums, GMP has a bigger advantage. The C program gmp-chudnovsky.c includes certain optimizations to this basic algorithm: http://gmplib.org/pi-with-gmp.html ftp://ftp.gmplib.org/pub/misc/gmp-chudnovsky.c On my machine, compiled with gcc -O3 -march=native -o gmp-chudnovsky gmp-chudnovsky.c -lgmp -lm the CPU times for 1,000,000 and 10,000,000 digits are 1.064 and 18.200 seconds, respectively. This is with a somewhat older machine model name : Intel(R) Core(TM)2 Quad CPU Q8200 @ 2.33GHz running Ubuntu 13.04 with heine:~/programs/gambiteer/gambit> gcc -v Using built-in specs. COLLECT_GCC=gcc COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.7/lto-wrapper Target: x86_64-linux-gnu Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.7.3-1ubuntu1' --with-bugurl=file:///usr/share/doc/gcc-4.7/README.Bugs --enable-languages=c,c++,go,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.7 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.7 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --with-system-zlib --enable-objc-gc --with-cloog --enable-cloog-backend=ppl --disable-cloog-version-check --disable-ppl-version-check --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu Thread model: posix gcc version 4.7.3 (Ubuntu/Linaro 4.7.3-1ubuntu1) heine:~/programs/gambiteer/gambit> gsi -v v4.6.9 20130607151908 x86_64-unknown-linux-gnu "./configure '--enable-single-host' '--enable-multiple-versions' '--enable-shared'" and the Ubuntu-provided GMP 5.0.5. (I'm sure the GMP folks have a better way to build GMP on my machine than the "generic" 64-bit version provided by Ubuntu.) Brad

7 18

object->u8vector as tree shaker?
by Bradley Lucier 29 Mar '15

29 Mar '15

Marc: It's not quite clear to me what object->u8vector does with procedures. I was thinking that if it pulled in all the functions not in system libraries, then it could be used as a tree-shaker. This is only a vague thought, but I find its interesting. Brad

3 6

Newbie Checking in
by Duke Normandin 04 Mar '15

04 Mar '15

Is this list active? Access to the archives seems to be hosed!! -- Duke ><>

4 9

Help with starting bitset library
by Bradley Lucier 26 Fév '15

26 Fév '15

Marc: I started writing a bitset library to leverage the bitwise-* operations. I need some help in working with type macros, etc. Can you look at the simple code below and tell me how to express it in the right way? Also, your define-prim-nary implements a fold operation, which is much, much slower for bitwise operations than just 1. Making sure all arguments are exact ints. 2. Determining the size of the resulting bignum (to be possibly normalized to a fixnum later) from the sizes and signs of the arguments. 3. Allocating the final bignum and destructively modifying it based on the arguments. Should I look into that a bit? Brad The start of bitsets.scm follows. (##include "../lib/header.scm") ;; accessors and constructors are not inlined unless I add ;; the following declaration. ;; Is that why you write constructors and accessors as macros? (declare (inlining-limit 300)) (define-structure ##bitset body) (define-prim (##bitset-union bs1 bs2) (##define-macro (type-error-on-x) `'(1)) (##define-macro (type-error-on-y) `'(2)) (if (##bitset? x) (if (##bitset? y) (make-##bitset (##bitwise-ior (##bitset-body x) (##bitset-body y))) (type-error-on-y)) (type-error-on-x))) (define-prim-nary (bitset-union x y) (make-##bitset 0) (if (##bitset? x) x '(1)) (##bitset-union x y) macro-force-vars macro-no-check (##pair? ##fail-check-bitset))

1 0

Type predicates in _system.scm
by Bradley Lucier 25 Fév '15

25 Fév '15

Marc: A typical type predicate in _system.scm is (define-prim (##ratnum? obj) (and (##subtyped? obj) (##eq? (##subtype obj) (macro-subtype-ratnum)))) Should all these uses of ##eq? be changed to ##eqv? Also, it seems that you're set up to deserialize meroon objects, but not to serialize them. Is that easily fixed? Brad

2 2

Just so I got it right: ___device_tcp_client_read/write_raw_virt doing *len_done = 0; return ___FIX(___NO_ERR); makes Gambit's IO scheduler select() and reiterate?
by Mikael 25 Fév '15

25 Fév '15

Marc, Not super important at all but part of auditing, just to check that I understand this correctly: If a blocking Gambit IO operation (e.g. that would be a |read-subu8vector|/|write-subu8vector| with a positive |need| value or a |read-byte|/|write-byte|) is currently being invoked on a TCP port, and the respective ___device_tcp_client_read_raw_virt or ___device_tcp_client_write_raw_virt procedure invoked does *len_done = 0; return ___FIX(___NO_ERR); , then in response to it doing that, will Gambit's IO scheduler (presuming there's no constraint from TCP port timeout settings) wait for the socket to show readability or writability respectively using select() and then reiterate the procedure? E.g., * |read-byte| is invoked. * The TCP port's read buffer is empty so Gambit invokes ___device_tcp_client_read_raw_virt, and it does *len_done = 0; return ___FIX(___NO_ERR); . * In response to that, Gambit does select() for readability (not writability) on the socket, and after some while there socket is found to have more data available to be read. * In response to that, Gambit re-invokes ___device_tcp_client_read_raw_virt. This time it gives 5 bytes. The first of those bytes will become the |read-byte| call's result. Thanks, Mikael

2 2

macro-check-index
by Bradley Lucier 25 Fév '15

25 Fév '15

Marc: Where is macro-check-index defined, and, more importantly, what does it do? Brad

2 1

Any big-time bit-twiddlers out there?
by Bradley Lucier 23 Fév '15

23 Fév '15

Do any of you Gambit users rely on fast execution of the bitwise-* and *-bit-field operations on bignums? I’m thinking about (a) cleaning up the implementation and (b) speeding things up a bit. But, is there any point? Brad

3 2

New builtins in upcoming gcc 5.0.0 that may speed up bignum arithmetic
by Bradley Lucier 23 Fév '15

23 Fév '15

I just noticed this in https://gcc.gnu.org/gcc-5/changes.html # A new set of built-in functions for arithmetics with overflow checking has been added: |__builtin_add_overflow|, |__builtin_sub_overflow| and |__builtin_mul_overflow| and for compatibility with clang also other variants. These builtins have two integral arguments (which don't need to have the same type), the arguments are extended to infinite precision signed type, |+|, |-| or |*| is performed on those, and the result is stored in an integer variable pointed to by the last argument. If the stored value is equal to the infinite precision result, the built-in functions return |false|, otherwise |true|. The type of the integer variable that will hold the result can be different from the types of the first two arguments. The following snippet demonstrates how this can be used in computing the size for the |calloc| function: void * calloc (size_t x, size_t y) { size_t sz; if (__builtin_mul_overflow (x, y, &sz)) return NULL; void *ret = malloc (sz); if (ret) memset (res, 0, sz); return ret; } On e.g. i?86 or x86-64 the above will result in a |mul| instruction followed by a jump on overflow. Maybe we can exploit this to improve the speed of bignum arithmetic. Brad

2 2

Conditional compilation based on backend
by Guillaume Cartier 23 Fév '15

23 Fév '15

Hi, I want to expand a macro based on what backend (c, js, ...) is currently used to compile the file. Does the backend install a cond-expand symbol that I can reference or else is there a way to know what is the current backend from my macro? Thanks, Guillaume Cartier

2 1

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

Gambit-list Février 2015