Big Integers
With the csc compiler and the -f or -fixnum-arithmetic option (Assume all numbers are fixnums) my benchmarks appear to be quite fast compared to racket of chez scheme. When running a benchmark that uses big integers (such as the pollard rho), execution times are almost twice as long as racket or chez. Is there an egg or alternate code to improve the efficiency of big integers? I would have thought there would be interface to gmp.
Re: Big Integers
Hello Peter, Thanks for the reply. The elapsed timings for the program rho3rec are: chicken 5.3.0: 33.6 secondsRacket v8.2 [cs] : 18.1 secondsDr Racket : 20.6 seconds (1 MB memory) The program uses the Pollard rho algorithm to find a factor of 2^257 -1. The program is highly recursive, but I have a non recursive version that has the same timing as the above. I am using an AMD Ryzen 5600 cpu and 32 GB of main memory. I tried all of the csc options that appeared related to speed, and the maximum improvement was 0.1 seconds. The one option I did not get to work was -heap-size 1000M where I varied the size from 1000M to 1M. In all cases I would get the run time message[panic] out of memory - heap full - execution terminated I have include the program listing below and also as an attachment. Regards,Doug ;#lang racket ;; uncomment for racket (define (rho n u v c iter prod) (let* ( [u1 (modulo (+ (* u u) c) n)] [v1 (modulo (+ (* v v) c) n)] [v2 (modulo (+ (* v1 v1) c) n)] [done #f] [max_iter 3000] [iter2 (+ iter 1)] [prod2 (modulo (* prod (- u1 v2)) n)] ) (if (= (modulo iter2 150) 0) (begin ; modulo true (let ( [g (gcd prod2 n) ] ) (if (and (> g 1) (< g n)) (begin ; factor (display "factor = ") (display g) (newline) (display "iterations = ") (display iter2) (newline) (set! done #t) ) (set! prod2 1) ; no factor ) ; end if factor ) ; end let ) ; end begin for modulo true #f ;action for modulo false ) ; end major if (if (and (< iter2 max_iter) (not done)) (rho n u1 v2 c iter2 prod2) (if done ; either found factor or max iterations (display "normal termination \n") #f ) ; if done ) ; if and ) ; end let*) (let ( [n (- (expt 2 257) 1)] [u 2] [v 11] [c 7] [iter 1] [prod 1] ) (display "factor n = ") (display n) (newline) (time (rho n u v c iter prod))) ;;; On Tuesday, May 21, 2024 at 12:13:55 AM MDT, Peter Bex wrote: (sending again, forgot to CC the users list) On Mon, May 20, 2024 at 03:23:54PM +, T.D. Telford wrote: > With the csc compiler and the -f or -fixnum-arithmetic option (Assume all > numbers are fixnums) my benchmarks appear to be quite fast compared to racket > of chez scheme. When running a benchmark that uses big integers (such as the > pollard rho), execution times are almost twice as long as racket or chez. Hello there! When we initially added bignum support in core (it used to be an egg), we spent quite a bit of effort optimizing various benchmarks, and on several of these (but not all of course), at the end CHICKEN performed *better* than several other Schemes, including Racket (which wasn't Chez-based at the time). It's quite possible that Chez Scheme has some optimized routines that other Schemes don't have, which we could learn from. If you have a specific benchmark that's slow, it would be helpful if you could share the code so we can have a look what it is exactly that slows things down. > Is there an egg or alternate code to improve the efficiency of big integers? > I would have thought there would be interface to gmp. While GMP is optimized to the hilt, it won't necessarily improve speed. The original "numbers" egg which provided add-on support for bignums was based on GMP and slow as molasses. Mediocre numeric code that's deeply integrated with the garbage collector and compilation strategy can easily outperform supremely bummed code that has to go through the FFI on every call. Again, if you can share some benchmarking code we can have a look if there are any obvious bottlenecks. Cheers, Peter ;; recursive ;;#lang racket;; uncomment for racket (define (rho n u v c iter prod) (let* ( [u1 (modulo (+ (* u u) c) n)] [v1 (modulo (+ (* v v) c) n)] [v2 (modulo (+ (* v1 v1) c) n)] [done #f] [max_iter 3000] [iter2 (+ iter 1)] [prod2 (modulo (* prod (- u1 v2)) n)] ) (if (= (modulo iter2 150) 0) (begin; modulo true (let ( [g (gcd prod2 n) ] ) (if (and (> g 1) (< g n)) (begin ; factor (display "factor = ") (display g) (newline) (display "iterations = ") (display iter2) (newline) (set! done #t) ) (set! prod2 1) ; no factor ) ; end if factor ) ; end let ) ; end begin for modulo true #f ;action for modulo false ) ; end major if (if (and (< iter2 max_iter) (not done))
Big Integers on Chicken
Hello Peter, I should have mentioned that I am using linux mint 21.3 Regards,Doug
Re: Big Integers
Hello Mario, Yes, please add the program to the chicken-benchmarks. Regards,Doug On Wednesday, May 22, 2024 at 12:50:56 PM MDT, Mario Domenech Goulart wrote: Hi Doug, On Tue, 21 May 2024 21:35:33 + (UTC) "T.D. Telford" wrote: > Thanks for the reply. The elapsed timings for the program rho3rec are: > > chicken 5.3.0: 33.6 seconds > Racket v8.2 [cs] : 18.1 seconds > Dr Racket : 20.6 seconds (1 MB memory) > > The program uses the Pollard rho algorithm to find a factor of 2^257 -1. The > program is highly recursive, but I have a > non recursive version that has the same timing as the above. I am using an > AMD Ryzen 5600 cpu and 32 GB of main memory. > > I tried all of the csc options that appeared related to speed, and the > maximum improvement was 0.1 seconds. > > The one option I did not get to work was > -heap-size 1000M > where I varied the size from 1000M to 1M. In all cases I would get the > run time message > [panic] out of memory - heap full - execution terminated > > I have include the program listing below and also as an attachment. > > Regards, > Doug > > ;;; > ;;#lang racket ;; uncomment for racket > > (define (rho n u v c iter prod) > (let* ( [u1 (modulo (+ (* u u) c) n)] > [v1 (modulo (+ (* v v) c) n)] > [v2 (modulo (+ (* v1 v1) c) n)] > [done #f] > [max_iter 3000] > [iter2 (+ iter 1)] > [prod2 (modulo (* prod (- u1 v2)) n)] ) > > (if (= (modulo iter2 150) 0) > (begin ; modulo true > (let ( [g (gcd prod2 n) ] ) > (if (and (> g 1) (< g n)) > (begin ; factor > (display "factor = ") (display g) (newline) > (display "iterations = ") (display iter2) (newline) > (set! done #t) > ) > (set! prod2 1) ; no factor > ) ; end if factor > ) ; end let > ) ; end begin for modulo true > #f ;action for modulo false > ) ; end major if > > (if (and (< iter2 max_iter) (not done)) > (rho n u1 v2 c iter2 prod2) > (if done ; either found factor or max iterations > (display "normal termination \n") > #f > ) ; if done > ) ; if and > ) ; end let* > ) > > (let ( [n (- (expt 2 257) 1)] [u 2] [v 11] [c 7] [iter 1] [prod 1] ) > (display "factor n = ") (display n) (newline) > (time (rho n u v c iter prod)) > ) > > ;;; Thanks for providing the program. Would it be ok to add it as a benchmark program to https://github.com/mario-goulart/chicken-benchmarks? All the best. Mario -- http://parenteses.org/mario
Re: Improve "busy" numeric code's performance [was: Re: Big Integers]
With patch 0001 the elapsed time went from 33.7 seconds to 24.5 seconds. With patch 0002 the elapsed time went to 23.4 seconds. Good work -- Doug On Wednesday, May 22, 2024 at 08:54:49 AM MDT, Peter Bex wrote: On Wed, May 22, 2024 at 02:42:38PM +0200, Peter Bex wrote: > Attached are two patches, one which has this bigger improvement, and > another which is a minor improvement which translates to shaving about > a second of runtime off your program (at least on my machine). The minor patch was incorrect. I copied some code from C_s_a_i_remainder into C_s_a_i_modulo inline, but that code had an early return for the case where both numbers are flonums. This code needs to be adjusted to handle the case when the arguments aren't of the same sign, just like we do after returning from integer_divrem(). I'm sending both patches again for your convenience. The second patch has a fix for the aforementioned issue. Cheers, Peter
-heap-size problem ?
I recently posted a problem using big numbers that ran quite a bit slower than the current Racket. Peter Bex supplied 2 patches that were a great improvement. While trying to increase the speed I used the csc option -heap-size 1000M where I varied the size from 1000M to 1M. I have 32 GB of memory and use linux mint 21.3. In all cases I would get the run time message[panic] out of memory - heap full - execution terminated If I don't use this option, the program runs ok. The program is very recursive and uses big numbers (80 to 160 decimal digits). Any ideas why this would occur?
