[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: jbarnett@charming.nrtc.northrop.com*Subject*: Fast SIGNUM equivalent*From*: Barry Margolin <barmar@Think.COM>*Date*: Wed, 9 Dec 1992 22:04:00 -0500*Cc*: slug@ai.sri.com*In-reply-to*: <9212100012.AA19029@charming.nrtc.northrop.com>

Date: Wed, 9 Dec 1992 19:12 EST From: jbarnett@charming.nrtc.northrop.com I have written a program that incorporates something like (CASE (SIGNUM (- I1 I2)) (1 ....) (0 ....) (-1 ....)) where I1 and I2 are fairly small, positive integers. This form is being executed a lot (hundreds of millions of times). Is there anyway to speed up the test-branch part of this enough to justify whatever pornography is necessary? Jeff Barnett I thought this might be better: (proclaim '(inline fixnum-compare)) (defun fixnum-compare (x y) (declare (fixnum x y)) (cond ((> x y) '>) ((= x y) '=) (t '<))) (case (fixnum-compare i1 i2) (> ...) (= ...) (< ...)) This version is either slower or faster than your version (on a 3650), depending on whether I1 is greater than or less than I2. You can see where that dependency comes from: the order of the COND and CASE clauses. If you know a priori which cases are more likely, you can optimize your source code for it. The speed of SIGNUM itself is also dependent on the sign of the argument; internally it contains (COND ((PLUSP NUMBER) 1) ((MINUSP NUMBER) -1) (T NUMBER))) By the way, this reminds me of my favorite missing optimization in the Symbolics compiler. A few releases ago they added optimization of CASE when the keys are all small, non-negative integers: it uses a jump table instead of a series of comparisons. However, this optimization would be appropriate whenever the keys are any dense set of integers; just subtract the value of the smallest one and use that as the jump table index. I sent the patch for this to Symbolics several years ago; however, jbarnett's original code still generates a series of tests. Changing it to (CASE (1+ (SIGNUM (- I1 I2))) (2 ....) (1 ....) (0 ....)) results in a jump table. However, my benchmark found that this generally was between the speeds of the above two versions. I believe this is due to SIGNUM's argument-dependency, and also because the jump table dispatch causes a pipeline break, whereas the 3650 normally prefetches the instruction after a conditional branch. I did finally manage to get a version that is consistently as fast or faster than any of the above. (proclaim '(inline (fixnum signum))) (defun fixnum-signum (x) (declare (fixnum x)) (cond ((plusp x) 1) ((minuxp x) -1) (t 0))) (case (1+ (fixnum-signum (- i1 i2))) (2 ...) (1 ...) (0 ...)) And the following is slightly faster than the above when (> i1 i2). (case (fixnum-signum (- i1 i2)) (1 ...) (0 ...) (-1 ...))

**References**:**Fast SIGNUM equivalent***From:*jbarnett@charming.nrtc.northrop.com

- Prev by Date:
**Fast SIGNUM equivalent** - Next by Date:
**Redefining select-c - summary of solutions** - Previous by thread:
**Fast SIGNUM equivalent** - Next by thread:
**RE: Fast SIGNUM equivalent** - Index(es):