[Openmcl-devel] Performance benchmark results
emarsden at laas.fr
Wed Apr 24 08:02:35 EDT 2002
>>>>> "gb" == Gary Byers <gb at clozure.com> writes:
gb> So, if an overzealous compiler isn't a factor in explaining CLISP's
gb> results, clever algorithms do indeed seem to be the likely culprit.
gb> (Some amount of tweaking/compiler improvements could make the OpenMCL
gb> version faster, but I doubt if it would get 10X faster ...)
this is what the documentation for CLN has to say about speed tricks
(I'm not certain that CLISP uses CLN directly, but they're by the same
author so likely use similar techniques). For the tests that I run,
probably the use of GMP is the most important factor.
Speed efficiency is obtained by the combination of the following
tricks and algorithms:
* Small integers, being represented as immediate values, don't
require memory access, just a couple of instructions for each
* The kernel of CLN has been written in assembly language for some
CPUs (i386, m68k, sparc, mips, arm).
* On all CPUs, CLN may be configured to use the superefficient
low-level routines from GNU GMP version 3.
* For large numbers, CLN uses, instead of the standard O(N^2)
algorithm, the Karatsuba multiplication, which is an O(N^1.6)
* For very large numbers (more than 12000 decimal digits), CLN
uses Sch?nhage-Strassen multiplication, which is an
asymptotically optimal multiplication algorithm.
* These fast multiplication algorithms also give improvements in
the speed of division and radix conversion.
Eric Marsden <URL:http://www.laas.fr/~emarsden/>
Openmcl-devel mailing list
Openmcl-devel at clozure.com
More information about the Openmcl-devel