LispForum

i really like Lisp because it allows me to develop everything in the purest way possible. with all this white magic - like higher-order functions and macros - you can to pretty neat stuff. sometimes i wonder however what will happen to memory and performance when i cast some of this spells.
in OOP for example the dispatching of virtual functions has to happen somewhere, even if the language hides it away (like Java), the moon is still there. Lisp makes you aware of this, in Java you start to forget about this basic stuff. when i create a lot of functions with higher-order function at runtime, what will happen? how is the code of the function stored (function-pointers in cons-cells or bytecode)? is it interpreted everytime i call it or compiled beforehand and how long does the compilation take?
i'm aware that the compiler will take care of most situations in the release build and the outcome has to be monitored in real situations. but is there some information and guidance about what will happen when i do some of this stuff, so i can get a feeling about the major does and don'ts and rethink my architecture early on? i hope i made myself clear

hewih wrote:how is the code of the function stored (function-pointers in cons-cells or bytecode)? is it interpreted everytime i call it or compiled beforehand and how long does the compilation take?

That depends on the implementation. There are many implementations with different objectives. Of the open source ones, with which I am most familiar, SBCL compiles everything to native code all the time (there is an interpreter mode, but that is rarely useful), with good performance of resultant code, but the compilation itself is slow, CCL also compiles to native code, with somewhat less performant code, but faster compilation, CLISP uses bytecode (although it has JIT compiler now) and ECL compiles to C, and also uses bytecode for some things.

In general, if you are interested in what function is doing, you can always use DISASSEMBLE, which is a defined by standard Common Lisp function which prints the function in more or less the form it is compiled to. On SBCL it will be assembler listing of the platform you are on.

hewih wrote:but is there some information and guidance about what will happen when i do some of this stuff, so i can get a feeling about the major does and don'ts and rethink my architecture early on?

I don't remember seeing anything which would spell that out, and it is probably not possible, since performance is always relative to bottlenecks. Experience is key, as is profiling. Well, and basic awareness of time complexity of algorithms, not specific to Lisp, these days there are more and more "programmers" who do not understand the difference between a vector and linked list...

Just keep writing code, and possibly read the source of some good existing libraries. Anything done by Edi Weitz is usually presented as a good example. Especially cl-ppcre, which is very interesting regular expression engine with performance comparable to that of Perl.

hewih wrote:when i create a lot of functions with higher-order function at runtime, what will happen?

This reminds of an article. In general, firing up the entire compiler at runtime is neither necessary or a good idea, it is better to compile a restricted language, and it works equally well.

Some main suggestions offered in these situations, which may be helpful:

• Note that Common Lisp has built-in tools like DISASSEMBLE (lets you see what your code compiles to), and you can supply various hints (like "this is a small integer which fits in a word") which an enlightened compiler will use to generate faster code. (Note that it can be a bit tricky; for instance, in some implementations, code which you write at the repl might be less optimized than the same code compiled from a file, because it doesn't automatically COMPILE the repl code.)
• But typically, you can just first implement the thing, then use a profiler if you hit a bottleneck. In most cases, performance bottlenecks won't be the "obvious" ones. Unless you're working in a very restricted environment or something.
• CL has lots of ways to do something. So for example, if CLOS is too big, there's DEFSTRUCT. (Or the MOP, if you want to get crazy.) I recall DEFSTRUCT has all sorts of flexibility.
• You can do some due diligence and run a skeleton of the parts you worry about and depend on, to see if CL is a reasonable tool for your situation.
• Often, algorithmic efficiency will get you far enough for most things.
• Run to Lisp forums, or your implementor's mailing lists, and ask if there's implementation-specific things you can do.
• Foreign function interfaces let you write parts in a different language (like C).
• If all else fails, then consider your Lisp version to be a prototype, and implement in another language.

Lisp is quite fast, see this article:
http://www.norvig.com/python-lisp.html

Here is another article:
http://ilc2009.scheming.org/node/7
This article basically states that it is hard to compile some of Lisp features. But this is low-level esoteric stuff
not something important.

So higher-order functions and especially macros (basically search and replace text engines) are reasonable fast.

Another point is that access to Lisp lists are O(n). If you want the 1324. element of a list you have to follow 1323 pointers.


The general opinion is:
- Algorythms matter more than small implementation details
- Dont worry about performance, write code and optimize later. Dont optimize until the code is already to slow or
the product is finished

thx for your responses (btw Ramarren: it takes you an average of 40min to respond... i checked it )

i'm more interested in the overall performance traps you can walk into. for example in some languages the tell you to be aware of not creating temporary objects all the time, because the have to be allocated and the garbage collector is having a hard time to get rid of those unused objects. are there any equal things in CL you should be aware of?

> "first implement the thing, then use a profiler if you hit a bottleneck"
> "Dont worry about performance, write code and optimize later."

you're right of course. a list doesn't care if it is sorted by a bubble- or a quick-sort so i can worry about it later. the problem however comes with architecture and interfaces which i can't change too much after wards. sometimes you have to decide between expressiveness, flexibility and performance. and if make something very flexible (f.e. with fancy higher-order functions) i'm worried that this might have a huge performance impact and i can't optimize it. there is no efficient substitute for higher-order functions without loosing expressiveness and flexibility.

> Another point is that access to Lisp lists are O(n). If you want the 1324. element of a list you have to follow 1323 pointers.

i don't believe this is true. Lisp is more like a mathematical description of a program and the compiler takes care of the implementation details and lists will probably be implemented as arrays in most cases. however when i write fancy code it's becoming more and more difficult for the compiler to make optimizations.

hewih wrote:i don't believe this is true. Lisp is more like a mathematical description of a program and the compiler takes care of the implementation details and lists will probably be implemented as arrays in most cases. however when i write fancy code it's becoming more and more difficult for the compiler to make optimizations.

That is not true about Lisp any more than about most other languages. Many Common Lisp compilers are quite good for a dynamic language, but I don't think the specification even allows changing types, and a list is a well defined type with well defined characteristics. Despite what some people might be saying Lisp is not magic, and Common Lisp in particular is designed to be a practical/industrial language, which means a comprehensible performance model and some limits on semantics to make compilation more possible.

hewih wrote:for example in some languages the tell you to be aware of not creating temporary objects all the time, because the have to be allocated and the garbage collector is having a hard time to get rid of those unused objects

That particular thing doesn't apply to, for example, SBCL, since it has a generational garbage collector, so it can handle short lived objects really well.

hewih wrote:i'm worried that this might have a huge performance impact and i can't optimize it

Remember the principle "build one to throw away". You are not building a pyramid here, it is always possible to scrap the whole system and rebuild from scratch, incorporating things learnt from the first time. Although proper modularity, separation of concerns and all those other things help. But, as I have written, practice is key. Also, you can always publish your code to be mercilessly mocked, I mean, constructively criticised

Anyway, higher order functions as usually fast. Generic functions are quite fast, although perhaps not fast enough for insides of tight loops. Flexibility is usually good.

hewih wrote:(btw Ramarren: it takes you an average of 40min to respond... i checked it )

Well, I live mostly on the internet these days, so why not. Someone has to fight the (perhaps not entirely untrue) myth that Lisp community is hostile to newbies!

hewih wrote:lists will probably be implemented as arrays in most cases

You can pretty much rely on this never happening*. Your Lisp is not going to swap your data structures around. It's going to assume you know what you're doing and picked lists for a reason.

* The exception being if you are using a strange language made by a particularly deranged person.

hewih wrote:thx for your responses (btw Ramarren: it takes you an average of 40min to respond... i checked it )

i'm more interested in the overall performance traps you can walk into. for example in some languages the tell you to be aware of not creating temporary objects all the time, because the have to be allocated and the garbage collector is having a hard time to get rid of those unused objects. are there any equal things in CL you should be aware of?

If I remember correctly, Paul Graham's book Ansi Common Lisp talks about this issue and tells how you can implement an object pool. It might or might not be a good thing depending on how often you create new objects, how your code works, the size of the objects and on the implementation. This is a thing you can only check with a benchmark.

hewih wrote:[...]

i don't believe this is true. Lisp is more like a mathematical description of a program and the compiler takes care of the implementation details and lists will probably be implemented as arrays in most cases.

That is not true to any implementation I know. Even SBCL, which is known to be the fastest implementation around, represents lists as linked lists, and even walking through a list is slower than walking an array with a simple and declared type - say, a simple array of fixnums. Of course they are much more flexible, they can share tails, which can save you a lot of time instead of you having to copy an array, not to mention it is much easier and faster to attach a new element in the beginning of a list. The rule I use is to use lists when I need a set and arrays when I need an ordered tuple which does not change its size very often.

But, regarding possibility, Lisp machines used to represent lists as a mix of arrays and linked lists. Small lists were stored like an array, larger lists would have a small array of, e.g., 5 elements, then a pointer to the next sequence of elements in that list. So your idea is not that far from reality

I think hewih was referring to cdr coding. However, ISTR benchmarks show it is generally not a real win. Here are a couple quickly-found links.

http://www-2.cs.cmu.edu/Groups/AI/html/ ... doc-9.html
http://coding.derkeiler.com/Archive/Lis ... /1513.html

gugamilare wrote:But, regarding possibility, Lisp machines used to represent lists as a mix of arrays and linked lists. Small lists were stored like an array, larger lists would have a small array of, e.g., 5 elements, then a pointer to the next sequence of elements in that list. So your idea is not that far from reality

Yes, there is a theme in the Lisps where abstraction will cover up concrete implementations. The most similar example I can think of offhand is mentioned in this Clojure video, around 42:00.

In Common Lisp, "compiler macros," described nicely by Arthur Lemmens, is a somewhat related idea. It allows you to write a function which might during compile-time be replaced by a more performant one, given what's known during compile-time. These are different from normal macros.

(Unfortunately, there remain limits to the "sufficiently smart compiler." Common Lisp's compiler macros won't write themselves; and Clojure gives you guarantees about not changing O(...) performance from under your feet. Maybe one day Emacs will pop up animated paperclip, which says, "I see that you're writing an exponential-time algorithm over sets. Would you like one which runs in constant-time?")