integer speed

[barton-willis]

Hi,

I'm a developer for the Maxima Computer Algebra system. Our testsuite has some new tests that require dividing 1000s of numbers with tens of thousands of digits. Maxima compiled with Clozure CL is much slower on these tests than is Maxima compiled with SBCL. Here is a little demonstration of the speed of arithmetic on large integers

(defun integer-speed ()
  (let ((a (expt 10007 8000))
        (b (expt 10009 8000)))
      (time (/ a b))
      (time (gcd a b))
      (time (floor a b))
     0)) 

Using Clozure CL, I get

? (integer-speed)
(/ A B)
took 3,581,000 microseconds (3.581000 seconds) to run.
During that period, and with 4 available CPU cores,
     3,578,125 microseconds (3.578125 seconds) were spent in user mode
             0 microseconds (0.000000 seconds) were spent in system mode
 128 bytes of memory allocated.
(GCD A B)
took 3,491,000 microseconds (3.491000 seconds) to run.
During that period, and with 4 available CPU cores,
     3,468,750 microseconds (3.468750 seconds) were spent in user mode
             0 microseconds (0.000000 seconds) were spent in system mode
 96 bytes of memory allocated.
(FLOOR A B)
took 0 microseconds (0.000000 seconds) to run.
During that period, and with 4 available CPU cores,
     0 microseconds (0.000000 seconds) were spent in user mode
     0 microseconds (0.000000 seconds) were spent in system mode
 13,376 bytes of memory allocated.
0

For one bit of Maxima code, I was able to find a workaround that replaced divide with floor. That greatly increased the speed of these new tests.

Using SBCL, these same three tests are fast:

* (integer-speed)
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  441 processor cycles
  0 bytes consed

Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  444 processor cycles
  0 bytes consed

Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  458 processor cycles
  0 bytes consed

0

Any tips on making big number arithmetic faster under Clozure? Thanks.

--Barton Willis

[phoe]

SBCL is very likely constant-folding all function calls since A and B are effectively constant, so you're comparing apples with oranges. You need to construct your test function differently - have A and B be arguments to the function rather than variables in the code and then redo the test by calling (integer-speed (expt 10007 8000) (expt 10009 8000)).

…

On 10.03.2023 08:02, Barton Willis wrote: Hi, I'm a developer for the Maxima Computer Algebra system. Our testsuite has some new tests that require dividing 1000s of numbers with tens of thousands of digits. Maxima compiled with Clozure CL is much slower on these tests than is Maxima compiled with SBCL. Here is a little demonstration of the speed of arithmetic on large integers |(defun integer-speed () (let ((a (expt 10007 8000)) (b (expt 10009 8000))) (time (/ a b)) (time (gcd a b)) (time (floor a b)) 0)) | Using Clozure CL, I get |? (integer-speed) (/ A B) took 3,581,000 microseconds (3.581000 seconds) to run. During that period, and with 4 available CPU cores, 3,578,125 microseconds (3.578125 seconds) were spent in user mode 0 microseconds (0.000000 seconds) were spent in system mode 128 bytes of memory allocated. (GCD A B) took 3,491,000 microseconds (3.491000 seconds) to run. During that period, and with 4 available CPU cores, 3,468,750 microseconds (3.468750 seconds) were spent in user mode 0 microseconds (0.000000 seconds) were spent in system mode 96 bytes of memory allocated. (FLOOR A B) took 0 microseconds (0.000000 seconds) to run. During that period, and with 4 available CPU cores, 0 microseconds (0.000000 seconds) were spent in user mode 0 microseconds (0.000000 seconds) were spent in system mode 13,376 bytes of memory allocated. 0 | For one bit of Maxima code, I was able to find a workaround that replaced divide with floor. That greatly increased the speed of these new tests. Using SBCL, these same three tests are fast: |* (integer-speed) Evaluation took: 0.000 seconds of real time 0.000000 seconds of total run time (0.000000 user, 0.000000 system) 100.00% CPU 441 processor cycles 0 bytes consed Evaluation took: 0.000 seconds of real time 0.000000 seconds of total run time (0.000000 user, 0.000000 system) 100.00% CPU 444 processor cycles 0 bytes consed Evaluation took: 0.000 seconds of real time 0.000000 seconds of total run time (0.000000 user, 0.000000 system) 100.00% CPU 458 processor cycles 0 bytes consed 0 | Any tips on making big number arithmetic faster under Clozure? Thanks. --Barton Willis — Reply to this email directly, view it on GitHub <#443>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADSZHKXV2MVIWHAZLRJNXP3W3LGYJANCNFSM6AAAAAAVWBI3WA>. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[metayan]

(defun integer-div (a b)
  (/ (expt a 8000) (expt b 8000)))

(defun integer-gcd (a b)
  (gcd (expt a 8000) (expt b 8000)))

(defun integer-floor (a b)
  (floor (expt a 8000) (expt b 8000)))

(defun integer-speed (n)
  (time (loop repeat n :do (integer-div 10007 10009)))
  (time (loop repeat n :do (integer-gcd 10007 10009)))
  (time (loop repeat n :do (integer-floor 10007 10009))))

(integer-speed 100)

CCL v1.12.1-9-g14dd8939

(LOOP REPEAT N :DO (INTEGER-DIV 10007 10009))
took 278,513,538 microseconds (278.513550 seconds) to run.
1,371 microseconds (  0.001371 seconds, 0.00%) of which was spent in GC.
During that period, and with 8 available CPU cores,
277,662,020 microseconds (277.662020 seconds) were spent in user mode
428,254 microseconds (  0.428254 seconds) were spent in system mode
7,753,600 bytes of memory allocated.
15 minor page faults, 0 major page faults, 0 swaps.

(LOOP REPEAT N :DO (INTEGER-GCD 10007 10009))
took 313,856,210 microseconds (313.856200 seconds) to run.
7,117 microseconds (  0.007117 seconds, 0.00%) of which was spent in GC.
During that period, and with 8 available CPU cores,
311,402,770 microseconds (311.402770 seconds) were spent in user mode
821,759 microseconds (  0.821759 seconds) were spent in system mode
7,750,400 bytes of memory allocated.
263 minor page faults, 0 major page faults, 0 swaps.

(LOOP REPEAT N :DO (INTEGER-FLOOR 10007 10009))
took 295,881 microseconds (0.295881 seconds) to run.
1,511 microseconds (0.001511 seconds, 0.51%) of which was spent in GC.
During that period, and with 8 available CPU cores,
294,064 microseconds (0.294064 seconds) were spent in user mode
3,463 microseconds (0.003463 seconds) were spent in system mode
9,078,400 bytes of memory allocated.
43 minor page faults, 0 major page faults, 0 swaps.

SBCL 2.3.2

Evaluation took:
  2.837 seconds of real time
  2.836301 seconds of total run time (2.834850 user, 0.001451 system)
  99.96% CPU
  7,077,789,456 processor cycles
  21,168,288 bytes consed
  
Evaluation took:
  2.886 seconds of real time
  2.885644 seconds of total run time (2.879589 user, 0.006055 system)
  100.00% CPU
  7,200,638,554 processor cycles
  21,183,808 bytes consed
  
Evaluation took:
  0.281 seconds of real time
  0.281690 seconds of total run time (0.280378 user, 0.001312 system)
  [ Run times consist of 0.003 seconds GC time, and 0.279 seconds non-GC time. ]
  100.36% CPU
  702,770,592 processor cycles
  9,108,576 bytes consed

[svspire]

SBCL uses GMP code to do the heavy lifting for bignums while CCL does it all in Lisp. I'm planning on rewriting CCL's bignum implementation to use e.g. Karatsuba multiplication and more assembly language which should alleviate some of these issues.

It's on the agenda.

[barton-willis]

Good to hear that you all are planning to rewrite CCL's bignum code. When it's available, I'll test it using Maxima.

For Maxima, I'll likely commit a patch that replaces a circa 1968 bit of code that uses a combination of / and rem with something like

  (multiple-value-bind (q r) (floor a b)
                   ;; when the remainder vanishes, return the quotient; else rat-error.
                   (if (eql 0 r) q (rat-error "CQUOTIENT: quotient is not exact"))))))

This change speeds up these new tests by a factor of about 15. Thanks to all who responded.