Common Lisp SBCL loop performance tweaks

Question

I'm using Project Euler problem 5 brute force method to test out performance tweaking CL code. I'm new to the language and want to know how to do such things. I wrote a C implementation, which runs in about 1.3 seconds. My initial, naive CL implementation runs in around 15 seconds.

Here's my initial CL code

(defpackage :problem-5 (:use #:cl) (:export :divides-even-p :has-all-divisors :smallest-multiple) ) (in-package :problem-5) (defun divides-even-p (num divisor) (= 0 (rem num divisor)) ) (defun has-all-divisors (num start stop) (loop for divisor from start to stop do (cond ((not (divides-even-p num divisor)) (return-from has-all-divisors nil)) ) (+ divisor 1) ) t ) (defun smallest-multiple (n) (do ((multiple 1 (+ multiple 1))) ((has-all-divisors multiple 1 n) (format t "~A" multiple)) )) (time (smallest-multiple 20))

The tricks I've read about up til now are 1) optimize for speed and safety, 2) inline functions and 3) explicitly set variable types. Applying those things, I get the following code

(defpackage :problem-5 (:use #:cl) (:export :divides-even-p :has-all-divisors :smallest-multiple) ) (in-package :problem-5) (declaim (optimize (speed 3) (safety 0)) (inline divides-even-p) (inline has-all-divisors) ) (defun divides-even-p (num divisor) (declare (type integer num divisor)) (zerop (rem num divisor)) ) (defun has-all-divisors (num start stop) (declare (type integer num start stop)) (loop for divisor of-type integer from start to stop do (cond ((not (divides-even-p num divisor)) (return-from has-all-divisors nil)) ) ) t ) (defun smallest-multiple () (do ((multiple 1 (+ multiple 1))) ((has-all-divisors multiple 2 20) (format t "~A" multiple)) )) (time (smallest-multiple))

Now when I run that version, it runs in 7 seconds instead of 15. 2x speed up, so in the right direction. What else can be done to speed it up? The most glaring thing to me is the do loop in smallest-multiple. For one, I couldn't figure out how to specify a type for the multiple variable. How do you do that? Is there a better way to do open ended loops that would produce less code? How would you go about trying to increase the performance from here? The C code runs in about 1.3 seconds, so I'd be happy getting it down to 2 or 3 seconds.

Applying brute force is not incompatible with avoiding needless work. You want to have a number that is a multiple of all values from 2 to 20, in particular 20. So start from 20 and step by 20 (this works for C too). — coredump
– coredump, Commented Jun 18, 2019 at 8:11

Svante · Accepted Answer · 2019-06-18 07:49:57Z

For one, you can use fixnum instead of integer. The latter encompasses all integers, the former only those that fit into a machine word minus a few tag bits (typically something around 61 or 62 bits).

The declaration in a do loop comes at the start of the body:

(do ((m 1 (1+ m))) ((has-all-divisors m 2 20) m) (declare (fixnum m)))

You could also use loop here:

(loop :for m :of-type fixnum :upfrom 1 :when (has-all-divisors m 2 20) :do (return m))

Code improvements:

Please don't leave parentheses lying around like nail clippings.
Use if for a two-branch conditional.

Loop has an always keyword:

(loop :for divisor :of-type fixnum :from start :to stop :always (divides-even-p num divisor))

Martin Buchmann · Accepted Answer · 2019-06-18 11:03:15Z

I am not a complete expert in CL but would like to give some advice, which you might find helpful.

General style

You should not leave closing parenthesis on a extra line. See e.g. here for some remarks on style. Furthermore, a documentation string would help others and yourself in the future to understand your code.

Performance

I haven't reviewed my own solution of this problem but I guess specifying fixnum instead of integer will lead to another factor of 2 in performance and should be possible for this problem.

Loop

You could write has-all-divisors more idiomatic using loops always clause:

(defun has-all-divisors (num start stop) (declare (type fixnum num start stop)) (loop for divisor of-type fixnum from start to stop always (divides-even-p num divisor)))

Alternative solution

If I remember this problem correctly, you could use another algorithm which should be way faster. Collect all prime factors of the integers from 2 to 20 and build their product.

Collectives™ on Stack Overflow

Common Lisp SBCL loop performance tweaks

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related