In one of the SICP lectures:
http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/
There is an example of abstraction for making a rational number by
using a cons pair and creating the appropriate operations for rational
numbers. One of the students asked about the value of that because
the number had to be packed and unpacked to work with it.
Recently I've been working on some programming puzzles using Lisp to
implement my solutions. I found myself sometimes abstracting concepts
and other times just using the built in Lisp primitives just to get
the job done.
I agree that abstractions are a good thing for managing complexity and
expressing the semantics of the code so that a human reader knows what
is intended by the programmer. But many times those abstractions
appear to inflict extra CPU cycles on the solution. I know CPU time
is much cheaper than it used to be, but it is added to programmer time
when testing code.
So my question: In general, is it necessary to take a perfomance hit?
What are the standard steps of mitigating the hit (or reducing it)
when the answer is not no?
--
(when (or hope despair)
(error "Deal with life as it is."))
Try googling comp.lang.lisp for
author:pitman abstraction efficiency
author:pitman premature optimization
also see http://kantz.com/jason/writing/8-puzzle.htm
for an example of the optimization process.
For an example of wasting a lot of time and money being too specific,
look to Microsoft's perfidious string/character types. Maybe there
were other trade offs in their legacy world that were valuable at the
time, but now Unicode conversions in Microsoft C/C++ can ravage a
program.
If you use an abstract data type that actually means 'character' and
not 'x number of bits', you can do things with that type like write and
read it from external formats and you are much better off.
The MS dot net libraries still make the mistake of looking at a
character specifically as a 16 bit encoding and require special hacks
for surrogate characters outside that range. I'm not sure what
Allegro CL and Lispworks do with surrogate characters, but I imagine
their systems are in a much better position to handle them.
David Steuber wrote:
>
> I agree that abstractions are a good thing for managing complexity and
> expressing the semantics of the code so that a human reader knows what
> is intended by the programmer.
>...
> So my question: In general, is it necessary to take a perfomance hit?
> What are the standard steps of mitigating the hit (or reducing it)
> when the answer is not no?
Abstraction is the perfect example of a double-edged sword.
As you mention, abstraction helps the human better understand the
intention of the code. There is no universal reason why it can't help
the computer understand the intention of the code as well. However, if
the computer *doesn't* understand it, abstraction gives the human
enough leverage to absolutely overwhelm the CPU with computation.
Calculating Fibonacci numbers is a oft-used example where a
straightforward "abstract" description is completely inefficient.
Most computers are still stupider than most humans at most abstract
thought. For any new abstraction, chances are a human can think of a
better way to understand the problem than a computer can. However,
computers can be *taught*.
Given tools as powerful as Common Lisp, you can teach the computer to
transform your abstractions into efficient algorithms, if you know what
those algorithms are. Mechanisms such as macros allow all sorts of
custom transformations to your abstractions, including ones that
improve performance. You can gradually "grow" the compiler to encompass
more and more of your problem domain.
In that case, good abstraction can mean that you have developed an
excellent "intermediate form" for the problem, which contains all of
the information needed to support the optimization. Lisp lets you use
the abstract code as concrete data to feed to your domain-specific
compiler.
In less flexible languages, the partition between code and data makes
it harder to keep abstractions abstract. "Refactoring" the system as
you learn more about the problem becomes very cumbersome.
David Steuber <·····@david-steuber.com> writes:
> In one of the SICP lectures:
>
> http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/
>
> There is an example of abstraction for making a rational number by
> using a cons pair and creating the appropriate operations for rational
> numbers. One of the students asked about the value of that because
> the number had to be packed and unpacked to work with it.
>
> Recently I've been working on some programming puzzles using Lisp to
> implement my solutions. I found myself sometimes abstracting concepts
> and other times just using the built in Lisp primitives just to get
> the job done.
>
> I agree that abstractions are a good thing for managing complexity and
> expressing the semantics of the code so that a human reader knows what
> is intended by the programmer. But many times those abstractions
> appear to inflict extra CPU cycles on the solution. I know CPU time
> is much cheaper than it used to be, but it is added to programmer time
> when testing code.
>
> So my question: In general, is it necessary to take a perfomance hit?
No.
> What are the standard steps of mitigating the hit (or reducing it)
> when the answer is not no?
Use a good compiler.
Use compiler-macros and macros to implement your own optimizations.
Note that optimizing compilers can do better job when they know more
about the program (eg. if the types of the variables are know at
compilation time, then the optimizer can avoid the slow generic
functions). Using an abstract language there's more information in
the program to be able to better optimize. That is, when you design a
DSL, you can add declarations in the code generated by your macros to
easily and automatically improve the optimizations. But also, once
you've got a working DSL, you can compile it with a specific compiler
bypassing the generic CL compiler. For example, if your DSL allows
you to describe a ANN, instead of generating the ANN code with a lisp
compiler, you could write a ANN compiler that would directly generate
assembler code or even microcode for a specialized FGPA or ANN chip.
You don't have to always use (COMPILE-FILE ...), you can also write
your own compiler and use (MYDSL-COMPILE-FILE ...). But of course,
you only do that when you need ultra high optimization. Usually, the
lisp compiler is good enough.
--
__Pascal Bourguignon__ http://www.informatimago.com/
You never feed me.
Perhaps I'll sleep on your face.
That will sure show you.
Pascal Bourguignon <···@informatimago.com> writes:
> Note that optimizing compilers can do better job when they know more
> about the program (eg. if the types of the variables are know at
> compilation time, then the optimizer can avoid the slow generic
> functions). Using an abstract language there's more information in
> the program to be able to better optimize. That is, when you design a
> DSL, you can add declarations in the code generated by your macros to
> easily and automatically improve the optimizations. But also, once
> you've got a working DSL, you can compile it with a specific compiler
> bypassing the generic CL compiler. For example, if your DSL allows
> you to describe a ANN, instead of generating the ANN code with a lisp
> compiler, you could write a ANN compiler that would directly generate
> assembler code or even microcode for a specialized FGPA or ANN chip.
I'm not convinced that by passing the Lisp compiler is a great idea in
this context. In general it would be quite unlikely that you will
have anywhere near the knowledge or resources required to sort out the
nitpicky details (including thorough understanding of the chip
architecture, limits, and idioms) as compared to the Lisp code
generator authors. There are probably exceptions. But even so, if
you are going to go to that level, you should just write a separate
compiler for the language and have done with it.
I don't think this in anyway prevents you from optimizing the hell out
of your DSL that you compile down to base CL. In particular, the kind
of things that can really pay off (which are not really feasible for
the Lisp compiler to figure out) are all sorts of short cuts and code
motion which knowledge of the domain, use cases of the DSL, and
properties of your "RTL" for the DSL will enable. There are some
truly huge gains that can be achieved via this approach. Then for all
the low level stuff (peep hole optimization, scheduling, etc.) just
pass the buck to the Lisp compiler which should do this part very well.
/Jon
--
'j' - a n t h o n y at romeo/charley/november com
jayessay <······@foo.com> writes:
> Pascal Bourguignon <···@informatimago.com> writes:
>
>> Note that optimizing compilers can do better job when they know more
>> about the program (eg. if the types of the variables are know at
>> compilation time, then the optimizer can avoid the slow generic
>> functions). Using an abstract language there's more information in
>> the program to be able to better optimize. That is, when you design a
>> DSL, you can add declarations in the code generated by your macros to
>> easily and automatically improve the optimizations. But also, once
>> you've got a working DSL, you can compile it with a specific compiler
>> bypassing the generic CL compiler. For example, if your DSL allows
>> you to describe a ANN, instead of generating the ANN code with a lisp
>> compiler, you could write a ANN compiler that would directly generate
>> assembler code or even microcode for a specialized FGPA or ANN chip.
>
> I'm not convinced that by passing the Lisp compiler is a great idea in
> this context.
I'm speaking of cases where the target is special hardware that is not
taken into account by the lisp compiler, of special domain language
features that are not taken into account by the lisp compiler.
For example, the lisp compiler is concerned a lot with typed object
and it's a big factor in its slow code (boxing/unboxing etc). Instead
of fighting the compiler with this respect, it might be better to
spend one's time and effort in writting a new compiler that generate
binary code specialized for the domain (eg. you can implement quite
efficient neuron update code if you generate the assembler directly,
or you can generate Altivec (mmx, xmm, whatever) SIMD code directly if
the lisp compiler at hand doesn't parallelize for your.
> In general it would be quite unlikely that you will
> have anywhere near the knowledge or resources required to sort out the
> nitpicky details (including thorough understanding of the chip
> architecture, limits, and idioms) as compared to the Lisp code
> generator authors.
On the other hand, the lisp code generator authors don't necessarily
mind or don't necessarily have the resources to optimize code
generation for your application or for your target. Compiler become
good when compiler writers do look at specific applications and
optimize for these specific applications. How many time does it occur
for the small marked of lisp compilers?
So a better lisp implementation would be one where there are hooks to
allow you to generate parts of your own binary code. An accessible LAP
would be a good point.
> There are probably exceptions. But even so, if you are going to go
> to that level, you should just write a separate compiler for the
> language and have done with it.
>
> I don't think this in anyway prevents you from optimizing the hell out
> of your DSL that you compile down to base CL. In particular, the kind
> of things that can really pay off (which are not really feasible for
> the Lisp compiler to figure out) are all sorts of short cuts and code
> motion which knowledge of the domain, use cases of the DSL, and
> properties of your "RTL" for the DSL will enable. There are some
> truly huge gains that can be achieved via this approach. Then for all
> the low level stuff (peep hole optimization, scheduling, etc.) just
> pass the buck to the Lisp compiler which should do this part very well.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Wanna go outside.
Oh, no! Help! I got outside!
Let me back inside!
Pascal Bourguignon <···@informatimago.com> writes:
> jayessay <······@foo.com> writes:
>
> > I'm not convinced that by passing the Lisp compiler is a great idea in
> > this context.
>
> I'm speaking of cases where the target is special hardware that is not
> taken into account by the lisp compiler, of special domain language
> features that are not taken into account by the lisp compiler.
Ah. That was a misunderstanding on my part then. Of couse in such
cases generating the machine code from your DSL compiler makes sense.
> > In general it would be quite unlikely that you will
> > have anywhere near the knowledge or resources required to sort out the
> > nitpicky details (including thorough understanding of the chip
> > architecture, limits, and idioms) as compared to the Lisp code
> > generator authors.
>
> On the other hand, the lisp code generator authors don't necessarily
> mind or don't necessarily have the resources to optimize code
> generation for your application
For your application - exactly right. That is what I spoke of below.
> or for your target. Compiler become
This X-compiler aspect was the bit I did not notice before.
> > There are probably exceptions. But even so, if you are going to go
> > to that level, you should just write a separate compiler for the
> > language and have done with it.
> >
> > I don't think this in anyway prevents you from optimizing the hell out
> > of your DSL that you compile down to base CL. In particular, the kind
> > of things that can really pay off (which are not really feasible for
> > the Lisp compiler to figure out) are all sorts of short cuts and code
> > motion which knowledge of the domain, use cases of the DSL, and
> > properties of your "RTL" for the DSL will enable. There are some
> > truly huge gains that can be achieved via this approach. Then for all
> > the low level stuff (peep hole optimization, scheduling, etc.) just
> > pass the buck to the Lisp compiler which should do this part very well.
>
/Jon
--
'j' - a n t h o n y at romeo/charley/november com
Pascal Bourguignon <···@informatimago.com> writes:
> David Steuber <·····@david-steuber.com> writes:
> > So my question: In general, is it necessary to take a perfomance hit?
>
> No.
>
>
> > What are the standard steps of mitigating the hit (or reducing it)
> > when the answer is not no?
>
> Use a good compiler.
> Use compiler-macros and macros to implement your own optimizations.
>
> Note that optimizing compilers can do better job when they know more
> about the program (eg. if the types of the variables are know at
> compilation time, then the optimizer can avoid the slow generic
> functions). Using an abstract language there's more information in
> the program to be able to better optimize.
Pascal's suggestions are good, but there's also nothing that says you
can *only* use portable facilities. The standard provides some
structure for how to interscede in the compiler, but its greatest
value here is probably in encouraging implementors to have an attitude
of openness with their compilers. Once your macros have processed
their bodies, and your compiler-macros have been run, the compiler
tries to do its best. As a general rule, the tricks that a compiler
can do have to be general-purpose. There are quite a few techniques
that just can't be used in general-purpose compilers because it's a
bad trade off to increase the complexity of the code for the compiler
itself, makeing it less maintainable, and to increase the
computational complexity of compiling all lisp code -- just to get
better results for unusual cases. With open compilers like Python,
you can write your own transforms and optimizers to add techniques
that work well on your domain-specific code.
Writing optimizable abstractions is sometimes more difficult, because
it's one more thing to take into account when designing things. Then
writing an effecient implementation is more work than just writing a
working one. But the upshot is that Common Lisp makes it possible to
have clear, maintainable, efficient code, in the general case --
something that is probably possible only for dynamic, open languages.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
David Steuber <·····@david-steuber.com> writes:
> I agree that abstractions are a good thing for managing complexity and
> expressing the semantics of the code so that a human reader knows what
> is intended by the programmer. But many times those abstractions
> appear to inflict extra CPU cycles on the solution. I know CPU time
> is much cheaper than it used to be, but it is added to programmer time
> when testing code.
>
> So my question: In general, is it necessary to take a perfomance hit?
> What are the standard steps of mitigating the hit (or reducing it)
> when the answer is not no?
>
I think people often worry about performance hits too early and often
before they need to. My experience is that the best optimization is
always achieved by identifying the best data abstraction and algorithm
for the problem. If you worry about optimization at an early stage,
your likely to constrain how you do things too much and miss finding
better abstractions/algorithms - the thing about a good abstraction is
that it helps you understand the problem more. As you work on it and
refine your abstraction to represent your problem domain better, you
will often find new understanding which leads to better abstraction
which in turn leads to better efficiency.
Its only at the very last stage I ever begin to worry about
optimization. The extra cpu cycles etc used in early development is
usually negligable and the benefits of optimizing incorrrect
abstractions and algorithms is probably going to gain you nothing -
possibly even lose you time as you attempt to optimize code which is
later dropped anyway.
Tim
--
Tim Cross
The e-mail address on this message is FALSE (obviously!). My real e-mail is
to a company in Australia called rapttech and my login is tcross - if you
really need to send mail, you should be able to work it out!
Thanks for the interesting replies. Good food for thought.
As some of the people on #lisp know, I've been thrashing with ITA
Software's Two-Time Pad problem. In the end, I came up with a very
simple solution that uses a CLOS class for abstraction and even a
generic function call in an inner loop.
The code runs faster than all prior versions and I have no attempts to
micro-optimize the code with (declare (optimize speed)) anywhere.
The only embarrassing thing about it all is that the simplicity of the
solution makes the time spent seem rediculous.
I do wonder if there are better results at producing clear text
though. My text is good enough to do a net search and find the source
for the original. But a lot of it reads like nonsense.
So back on topic, I guess then that abstraction, when done properly,
can have an end result of even better performance.
--
My .sig file sucks. Can anyone recommend a better one?
On 18 Jul 2005 12:21:24 -0400, <·····@david-steuber.com> wrote:
>
>
> Thanks for the interesting replies. Good food for thought.
>
> As some of the people on #lisp know, I've been thrashing with ITA
> Software's Two-Time Pad problem.
>
> The only embarrassing thing about it all is that the simplicity of the
> solution makes the time spent seem rediculous.
Maybe. I'd bet that all the time you spent gave you the insight for
the "simple" solution. You did submit your solution?
--
[ingvar] Modelling forest damage by storms with regular expressions is...
a curious idea.
[Xach] before: ||| after: //_
[Xach] seems easy enough to me
GP lisper <········@CloudDancer.com> writes:
> On 18 Jul 2005 12:21:24 -0400, <·····@david-steuber.com> wrote:
> >
> > As some of the people on #lisp know, I've been thrashing with ITA
> > Software's Two-Time Pad problem.
> >
> > The only embarrassing thing about it all is that the simplicity of the
> > solution makes the time spent seem rediculous.
>
> Maybe. I'd bet that all the time you spent gave you the insight for
> the "simple" solution. You did submit your solution?
It was a twisty little maze that led me to the simple solution. I
went into it with a vague idea of how to solve it, but it did take all
that effort to get me to the end point. I did submit my solution. I
also submited solutions for Strawberry Fields and Palindromic Pangram
in the hopes that I would look better with three than just one.
Although I'm not particularly thrilled with my palindrome solution.
Now I just have to wait. I'm sure ITA receives dozens of applications
per day. I wonder if they have automated searching the text for the
correct answers. Kind of like headhunters and HR peeps grepping for
key words and phrases in a resume.
--
My .sig file sucks. Can anyone recommend a better one?
David Steuber wrote:
> So my question: In general, is it necessary to take a perfomance hit?
No, but ``in general'' it requires a great deal of care. Here's a very
simple example where you can lose a factor of n by choosing the wrong
abstraction to lift a two argument function (folding from the left
instead of the right, in this case).
? (setf x (loop repeat 1000 collect (list t)) y nil)
NIL
? (time (progn (reduce 'append x) nil))
;Compiler warnings :
; Undeclared free variable X, in an anonymous lambda form.
(PROGN (REDUCE 'APPEND X) NIL) took 98 milliseconds (0.098 seconds) to
run.
3,996,000 bytes of memory allocated.
NIL
? (time (progn (reduce 'append x :from-end t) nil))
;Compiler warnings :
; Undeclared free variable X, in an anonymous lambda form.
(PROGN (REDUCE 'APPEND X :FROM-END T) NIL) took 2 milliseconds (0.002
seconds) to run.
Of that, 1 milliseconds (0.001 seconds) were spent in The Cooperative
Multitasking Experience.
15,992 bytes of memory allocated.
NIL
? (equalp (reduce 'append x) (reduce 'append x :from-end t))
T
> What are the standard steps of mitigating the hit (or reducing it)
> when the answer is not no?
The usual answer is to give the compiler better information, or use
macros to unroll the abstractions yourself. Ideally, you want to use
high-level abstractions that admit a very efficient implementation,
even if you start off with a simpler, less efficient one. The standard
approach for this is to start with an asymptotically efficient
algorithm and then optimize the subroutines that the profiler says take
up the most time.
^L
(loop
(when (or hope despair)
(cerror "Deal with life as it is."
"What do I do now?")))
From: Joe Marshall
Subject: Re: Abstraction without performance penalty?
Date:
Message-ID: <vf2ynxx2.fsf@comcast.net>
···············@yahoo.com writes:
> (loop
> (when (or hope despair)
> (cerror "Deal with life as it is."
> "What do I do now?")))
Life has interactive restarts?
--
~jrm
Joe Marshall <·············@comcast.net> writes:
> ···············@yahoo.com writes:
>
> > (loop
> > (when (or hope despair)
> > (cerror "Deal with life as it is."
> > "What do I do now?")))
>
> Life has interactive restarts?
The common term is "mid-life crisis".
--
My .sig file sucks. Can anyone recommend a better one?