Where in the Lispworks manuals would I find information about optimization?
Suppose I have a test function such as
(defun test1 (n) (dotimes (k n) (+ n 2)))
and I invoke it as (test1 10000000) just to see how long it takes.
What kind of decoration and/or optimization would make it fastest?
And why does it seem to be only a few times slower interpreted than compiled?
I would think interpreting it would take many times longer than executing it,
since it hardly does anything.
I also tried testing the heap limit of the personal edition of Lispworks, and
it seems to be somewhere near 10 MB. Does that sound right, or am I
measuring it wrong? I also noticed that my code to test it ran very slowly,
which was what got me interested in speed testing and optimization. Not to
optimize my code to test the heap limit, but just to find out what kind of
optimization is available in general.
In article <··································@4ax.com>,
··········@questions.com wrote:
> Where in the Lispworks manuals would I find information about
> optimization?
I don't have Lispworks, but in this case we can use portable techniques.
> Suppose I have a test function such as
>
> (defun test1 (n) (dotimes (k n) (+ n 2)))
>
> and I invoke it as (test1 10000000) just to see how long it takes.
>
> What kind of decoration and/or optimization would make it fastest?
In this particular case, the best way to optimize your function is to
notice that it always returns the same value and has no side effect, so
you can use a portable language feature:
(define-compiler-macro test1 (n) nil)
In general, optimization is something you want to do to a program that
produces correct results but doesn't run fast enough. Optimizing
functions like the one above is a waste of time as you'll never need
them.
^L
Louis Theran <······@cs.umass.edu> writes:
> In this particular case, the best way to optimize your function is to
> notice that it always returns the same value and has no side effect, so
> you can use a portable language feature:
>
> (define-compiler-macro test1 (n) nil)
I think both ACL and MCL (don't have them at hand right now to
verify) might actually have compiled away the DOTIMES themselves in
this case.
--
(espen)
>>>>> On Sun, 13 May 2001 04:21:55 GMT, lispnewbie ("ln") writes:
ln> (defun test1 (n) (dotimes (k n) (+ n 2)))
ln> and I invoke it as (test1 10000000) just to see how long it takes.
ln> What kind of decoration and/or optimization would make it fastest?
ln> And why does it seem to be only a few times slower interpreted than compiled?
I only spent a few minutes fooling around with this, but I
don't think I'm seeing the same things that you're seeing.
According to TIME, the compiled version runs 119 times faster than
interpreted. However, a closer look shows that running it compiled
is really a little over 300 times faster. Also, the interpreter
conses like crazy for this function! It goes up linearly with the
argument, and for my test case of N = 1,050,000, the interpreter
produced 11 MB of garbage. The compiled version doesn't cons at all,
unless of course you start using bignums.
Adding an INTEGER declaration to the compiled program will more than
halve the program size (from 377 to 173) and result in a further speedup.
This could potentialy give you an additional 90% speed increase.
Restricting the argument to FIXNUM will speed things up a little bit more.
Also adding a declaration for the inner variables takes the program down
to 105 instructions but it will not work if passed a bogus argument.
You can eliminate 4 instructions by adding (OPTIMIZE (SPEED 3) (SAFETY 0)).
If you want a version that will not crash, you can leave out the inner
declaration and keep the OPTIMIZE; that version is 148 instructions,
and still happens to use a generic comparison as part of the DOTIMES.
Note that optimizations are implementation specific, and compilers are
even allowed to entirely ignore them. The main thing to understand
about optimizations is: before worrying about them or doing anything,
you should profile your entire application and determine where the
real bottlenecks are. The whole point in Lisp of not having to make
any type declarations is not only that you can add them in later,
but that you can change parts of your program around (for example, use
new algorithms in the implementation of your functions) without having
to redesign the rest of the program to make it work. Optimizing is
an activity that begins when the initial implementation of the entire
application is complete - not something you fiddle with along the way.
On Sun, 13 May 2001 07:37:52 GMT, Christopher Stacy
<······@spacy.Boston.MA.US> wrote:
>I only spent a few minutes fooling around with this, but I
>don't think I'm seeing the same things that you're seeing.
The number of iterations I gave it was 10 times bigger than yours. It turns
out that it allocates a lot of memory then, both interpreted and compiled,
which makes the speed meaningless other than as a measure of how fast it
allocates memory.
Fixnums seem to be 24 bits, because overflowing a 24-bit signed integer is
what makes it slow down and allocate memory. (Found by noticing at what
number of iterations it starts happening.)
A better test, using a nested loop to keep the numbers smaller, uses about
nine machine cycles per iteration. That's pretty close to the best C
compilers, and it isn't even decorated at all.
>>>>> On Sun, 13 May 2001 14:34:49 GMT, lispnewbie ("lispnewbie") writes:
lispnewbie> On Sun, 13 May 2001 07:37:52 GMT, Christopher Stacy
lispnewbie> <······@spacy.Boston.MA.US> wrote:
>> I only spent a few minutes fooling around with this, but I
>> don't think I'm seeing the same things that you're seeing.
lispnewbie> The number of iterations I gave it was 10 times bigger than yours. It turns
lispnewbie> out that it allocates a lot of memory then, both interpreted and compiled,
lispnewbie> which makes the speed meaningless other than as a measure of how fast it
lispnewbie> allocates memory.
I think I said all that: that's what bignums are.
lispnewbie> A better test, using a nested loop to keep the numbers smaller, uses about
lispnewbie> nine machine cycles per iteration. That's pretty close to the best C
lispnewbie> compilers, and it isn't even decorated at all.
You didn't ask for a better program, you asked what kinds of
compiler optimizations were possible for the one you had written.
What you have discovered by writing a different program is that
you might be able to avoid consing bignums.
>>>>> On Sun, 13 May 2001 14:34:49 GMT, lispnewbie ("lispnewbie") writes:
lispnewbie> On Sun, 13 May 2001 07:37:52 GMT, Christopher Stacy
lispnewbie> <······@spacy.Boston.MA.US> wrote:
>> I only spent a few minutes fooling around with this, but I
>> don't think I'm seeing the same things that you're seeing.
lispnewbie> The number of iterations I gave it was 10 times bigger than yours. It turns
lispnewbie> out that it allocates a lot of memory then, both interpreted and compiled,
lispnewbie> which makes the speed meaningless other than as a measure of how fast it
lispnewbie> allocates memory.
I think I said all that: that's what bignums are.
lispnewbie> A better test, using a nested loop to keep the numbers smaller, uses about
lispnewbie> nine machine cycles per iteration. That's pretty close to the best C
lispnewbie> compilers, and it isn't even decorated at all.
You didn't ask for a better program, you asked what kinds of
compiler optimizations were possible for the one you had written.
What you have discovered by writing a different program is that
you might be able to avoid consing bignums.
Sorry I wasted my time answering your question.