Yesterday I wrote small function that resembles data processing I need
for a benchmark. Here is the program.
(defun test (n)
(set 'list-of-nodes ())
(dotimes (j n)
(time (progn
(dotimes (i 10000)
(push (set 'new-node (list () ())) list-of-nodes)
(push (set 'random-old-node
(nth (if (= i j 0)
0
(random (+ (* j 10000) i))
)
list-of-nodes
)
)
(cadr new-node)
)
(push new-node (cdr random-old-node))
)
(print (* 10000 (1+ j)))
)
)
)
)
Then I loaded and executed it in REPL of Clisp/Windows XP/Pentium 4-
3.4GHz/1GB with following results:
[6]> (test 10)
10000
Real time: 0.25 sec.
Run time: 0.25 sec.
Space: 400328 Bytes
20000
Real time: 0.640625 sec.
Run time: 0.640625 sec.
Space: 400328 Bytes
GC: 1, GC time: 0.03125 sec.
30000
Real time: 0.984375 sec.
Run time: 0.984375 sec.
Space: 400328 Bytes
40000
Real time: 1.390625 sec.
Run time: 1.390625 sec.
Space: 400328 Bytes
GC: 1, GC time: 0.03125 sec.
50000
Real time: 1.75 sec.
Run time: 1.75 sec.
Space: 400328 Bytes
60000
Real time: 2.25 sec.
Run time: 2.25 sec.
Space: 400328 Bytes
GC: 1, GC time: 0.015625 sec.
70000
Real time: 2.765625 sec.
Run time: 2.765625 sec.
Space: 400328 Bytes
GC: 1, GC time: 0.03125 sec.
80000
Real time: 3.25 sec.
Run time: 3.25 sec.
Space: 400328 Bytes
90000
Real time: 3.90625 sec.
Run time: 3.890625 sec.
Space: 400328 Bytes
GC: 1, GC time: 0.078125 sec.
100000
Real time: 4.359375 sec.
Run time: 4.359375 sec.
Space: 400328 Bytes
NIL
[7]>
Now, I wonder how slow/fast it is compared with other Lisp
implementations/platforms, to know is it worth think about changing, or
I can stay where I am. So, I'd like to ask members of the group to load
the file and execute (test 10) in their favorite Lisp so we can compare
it.
Thanx.
Majorinc wrote:
> Yesterday I wrote small function that resembles data processing I need
> for a benchmark. Here is the program.
>
> (defun test (n)
> (set 'list-of-nodes ())
> (dotimes (j n)
> (time (progn
> (dotimes (i 10000)
> (push (set 'new-node (list () ())) list-of-nodes)
> (push (set 'random-old-node
> (nth (if (= i j 0)
> 0
> (random (+ (* j 10000) i))
> )
> list-of-nodes
> )
> )
> (cadr new-node)
> )
> (push new-node (cdr random-old-node))
> )
> (print (* 10000 (1+ j)))
> )
> )
> )
> )
Your code is very non-idiomatic. Two important things:
- Your use of set is highly unusual. The ANSI CL specification states
that set is a deprecated operator, and there are good reasons for this.
Foremostly, set exclusivly operates on global variables, doesn't keep
the local contexts of different functions separated, and is probably
very inefficient.
- If you are using nth to access elements in a list, then you haven't
understood the various opportunities to use and build your own
datastructures yet. You should only rarely use nth to access elements in
a list, especially not in benchmarks because it is a very slow
operation. Lists can be very useful and have their advantages, but this
is definitely not one of them.
- You shouldn't put closing parentheses in their own lines. This makes
your code very unreadable and wastes valuable vertical space on your
screen. If you think that putting them on single lines, then you simply
don't have enough experience with programming in Lisp and using the
right editors to support Lisp syntax. No mildly experienced Lispers does
what you are doing here.
These observation strongly indicate that you haven't learned enough of
the very basics of Lisp yet and are at the very beginning of learning
the language. It is highly recommended that you pick a good tutorial
(like "Practical Common Lisp", "Successful Lisp" or "Paradigms of
Artificial Intelligence Programming") before wasting your time on
benchmarks that are very likely not to tell you anything useful at all.
You will have a much better understanding what the important elements
are that contribute to, or diminish, performance only at a much later stage.
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
In article <···············@individual.net>, ··@p-cos.net
says...
>
> Your code is very non-idiomatic. Two important things:
Ouch.
>
> - Your use of set is highly unusual. The ANSI CL specification states
> that set is a deprecated operator, and there are good reasons for this.
> Foremostly, set exclusivly operates on global variables, doesn't keep
> the local contexts of different functions separated, and is probably
> very inefficient.
So what? It is still in standard, and I like it more than setq
and setf, because I prefer functions to macros and special
operators - if possible. Is it completely out of base? Of
course it is not, it is just another opinion, and you failed to
_clearly_ demonstrate that it is wrong.
Ad hoc claim "set is probably very inefficient" is strange to
me; in fact, it is wrong - at least in Clisp.
[13]> (time (dotimes (i 1000000)))
Real time: 0.8125 sec.
Run time: 0.8125 sec.
Space: 728 Bytes
NIL
--------------------
[14]> (time (dotimes (i 1000000)(setq x 100)))
Real time: 1.0 sec.
Run time: 1.0 sec.
Space: 736 Bytes
NIL
-------------------
[11]> (setf y (quote x))
X
[12]> (time (dotimes (i 1000000)(set y 100)))
Real time: 1.015625 sec.
Run time: 1.015625 sec.
Space: 736 Bytes
NIL
--------------------
[5]> (time (dotimes (i 1000000)(set 'x 100)))
Real time: 1.078125 sec.
Run time: 1.078125 sec.
Space: 736 Bytes
NIL
---------------------
[4]> (time (dotimes (i 1000000)(setf x 100)))
Real time: 1.875 sec.
Run time: 1.875 sec.
Space: 40000756 Bytes
GC: 76, GC time: 0.1875 sec.
NIL
>
> - If you are using nth to access elements in a list, then you haven't
> understood the various opportunities to use and build your own
> datastructures yet. You should only rarely use nth to access elements in
> a list, especially not in benchmarks because it is a very slow
> operation. Lists can be very useful and have their advantages, but this
> is definitely not one of them.
Well, this could be more important - but again it is wrong
logic. Using that logic, recursive definition of Fibonacci
numbers is useless benchmark, because it is not efficient way
for calculations of Fibonacci numbers!
Now, I'm sure that if you think carefully, you'll find quite a
few good reasons why benchmarks do not necessarily to implement
best possible algorithm/data structure for a given problem.
>
> - You shouldn't put closing parentheses in their own lines. This makes
> your code very unreadable and wastes valuable vertical space on your
> screen. If you think that putting them on single lines, then you simply
> don't have enough experience with programming in Lisp and using the
> right editors to support Lisp syntax. No mildly experienced Lispers does
> what you are doing here.
We already discussed it, but again, although I've seen
arguments pro and contra, I failed to see clear demonstration
that )))) is better than C style. However, question of style is
clearly not important!!
>
> These observation strongly indicate that you haven't learned enough of
> the very basics of Lisp yet and are at the very beginning of learning
> the language. It is highly recommended that you pick a good tutorial
> (like "Practical Common Lisp", "Successful Lisp" or "Paradigms of
> Artificial Intelligence Programming") before wasting your time on
> benchmarks that are very likely not to tell you anything useful at all.
> You will have a much better understanding what the important elements
> are that contribute to, or diminish, performance only at a much later stage.
It has no sense. Look, what would you do if I told you that,
say, Aldor is superior languge to Lisp? Would you spend two
years to learn it, or would you try to write few benchmarks
very first day, just to make some opinion? For example, that
already mentioned Fibonacci recursive function?
Benchmark tests are not blood oaths, for God sake; they are
almost everyday activity, useful for very different purposes,
for very different kinds of needs ... strange that I have to
explain that.
Majorinc wrote:
> In article <···············@individual.net>, ··@p-cos.net
> says...
> >
> > - Your use of set is highly unusual. The ANSI CL specification states
> > that set is a deprecated operator, and there are good reasons for this.
> > Foremostly, set exclusivly operates on global variables, doesn't keep
> > the local contexts of different functions separated, and is probably
> > very inefficient.
>
> So what? It is still in standard, and I like it more than setq
> and setf, because I prefer functions to macros and special
> operators - if possible.
Why? To me it makes little difference whether a form is a function,
special-form or macro.
> Is it completely out of base? Of
> course it is not, it is just another opinion, and you failed to
> _clearly_ demonstrate that it is wrong.
In many lisp implementation 'set' is much slower than 'setq', though I
don't think it's universal. Your benchmark below indicates that it
isn't in normal interpreted clisp.
It often is in other implementations though, see other peoples posts.
You appear to have done your tests (for this and the previous example)
using the clisp prompt interpreter. This isn't AFAIK really intended
to run things fast, it's for convience. To do real coding with Clisp
you would compile code to a fasl file, so this is the most
representative thing to benchmark.
> > - If you are using nth to access elements in a list, then you haven't
> > understood the various opportunities to use and build your own
> > datastructures yet. You should only rarely use nth to access elements in
> > a list, especially not in benchmarks because it is a very slow
> > operation. Lists can be very useful and have their advantages, but this
> > is definitely not one of them.
>
> Well, this could be more important - but again it is wrong
> logic. Using that logic, recursive definition of Fibonacci
> numbers is useless benchmark, because it is not efficient way
> for calculations of Fibonacci numbers!
Personally, I think that recursive definition of fibonacci numbers *is*
a useless benchmark for exactly this reason. A good speed benchmark is
something that represents a real problem, not something optimized to
the nth degree, but not something implemented naively either.
> Now, I'm sure that if you think carefully, you'll find quite a
> few good reasons why benchmarks do not necessarily to implement
> best possible algorithm/data structure for a given problem.
Good benchmarks should make a reasonable job of representing real code,
which is normally not perfect, but not entirely bad.
> It has no sense. Look, what would you do if I told you that,
> say, Aldor is superior languge to Lisp? Would you spend two
> years to learn it, or would you try to write few benchmarks
> very first day, just to make some opinion? For example, that
> already mentioned Fibonacci recursive function?
>
> Benchmark tests are not blood oaths, for God sake; they are
> almost everyday activity, useful for very different purposes,
> for very different kinds of needs ... strange that I have to
> explain that.
I wouldn't do that. If I wanted to know how fast something was I'd use
a real program, maybe one someone else had written in the language.
Toy benchmarks are useless for representing the general case, worse
than not benchmarking at all. Its fairly easy to prove that any given
language is slow (or indeed fast) with them. They're most useful to
see how fast a given bit of code that is actually needed in a real
program will run.
Majorinc wrote:
> In article <···············@individual.net>, ··@p-cos.net
> says...
> So what? It is still in standard, and I like it more than setq
> and setf, because I prefer functions to macros and special
> operators - if possible. Is it completely out of base? Of
> course it is not, it is just another opinion, and you failed to
> _clearly_ demonstrate that it is wrong.
If you want to get input from experts on comp.lang.lisp, you should
respect their expertise. If you want to simply confirm your own
prejudices, you can do that all on your own.
>
> Ad hoc claim "set is probably very inefficient" is strange to
> me; in fact, it is wrong - at least in Clisp.
'set' basically cannot work on values that a compiler would place in a
CPU register.
> >
> > - If you are using nth to access elements in a list, then you haven't
> > understood the various opportunities to use and build your own
> > datastructures yet. You should only rarely use nth to access elements in
> > a list, especially not in benchmarks because it is a very slow
> > operation. Lists can be very useful and have their advantages, but this
> > is definitely not one of them.
>
> Well, this could be more important - but again it is wrong
> logic. Using that logic, recursive definition of Fibonacci
> numbers is useless benchmark, because it is not efficient way
> for calculations of Fibonacci numbers!
Fibonacci is a perfect example of an artificial benchmark, which
exposes some of the pitfalls of straightforward recursive
implementations of 'naturally' recursive specifications. It typically
has little relevance to real-world applications.
> Now, I'm sure that if you think carefully, you'll find quite a
> few good reasons why benchmarks do not necessarily to implement
> best possible algorithm/data structure for a given problem.
> We already discussed it, but again, although I've seen
> arguments pro and contra, I failed to see clear demonstration
> that )))) is better than C style. However, question of style is
> clearly not important!!
>
>
> It has no sense. Look, what would you do if I told you that,
> say, Aldor is superior languge to Lisp? Would you spend two
> years to learn it, or would you try to write few benchmarks
> very first day, just to make some opinion? For example, that
> already mentioned Fibonacci recursive function?
Ah, yes, the tyranny of experts, always trying to quash the love of the
amateur.
Tell me, how do you like the violin? Do you listen to Itzhak Perlman
play, or do you just pick up the instrument with no experience and try
to play it. Sounds ugly, doesn't it?
Grow up, or stop trolling.
In article <························@f14g2000cwb.googlegroups.com>,
············@gmail.com says...
>
> Ah, yes, the tyranny of experts, always trying to quash the love of the
> amateur.
>
> Tell me, how do you like the violin? Do you listen to Itzhak Perlman
> play, or do you just pick up the instrument with no experience and try
> to play it. Sounds ugly, doesn't it?
>
> Grow up, or stop trolling.
What an idiot!
Majorinc wrote:
> In article <···············@individual.net>, ··@p-cos.net
> says...
> >
> > - Your use of set is highly unusual. The ANSI CL specification states
> > that set is a deprecated operator, and there are good reasons for this.
> > Foremostly, set exclusivly operates on global variables, doesn't keep
> > the local contexts of different functions separated, and is probably
> > very inefficient.
>
> So what? It is still in standard, and I like it more than setq
> and setf, because I prefer functions to macros and special
> operators - if possible. Is it completely out of base? Of
> course it is not, it is just another opinion, and you failed to
> _clearly_ demonstrate that it is wrong.
If you are the expert in what is right or wrong, why are you asking
questions here?
>
> We already discussed it, but again, although I've seen
> arguments pro and contra, I failed to see clear demonstration
> that )))) is better than C style. However, question of style is
> clearly not important!!
Style seems to be quite important to others in the group (see their
postings). If it is `clearly not important' to you, then why do you
persist in doing the wrong thing? You are like a motorist that drives
on the wrong side of the road. Clearly, either side will get you to
your destination, and there is no obvious advantage to everyone driving
on the left as opposed to everyone driving on the right.
In article <························@g49g2000cwa.googlegroups.com>,
··········@gmail.com says...
> If you are the expert in what is right or wrong, why are you asking
> questions here?
I'm certainly not an expert in Lisp. This thread started with my search
for dif. compilers/OS/comps but it appears that people were interested
in other issues ...
> You are like a motorist that drives
> on the wrong side of the road.
Hm, side of the road is more than style .. long/short hair maybe.
Plus, it appears that all the people who use )))) use in the same time
Emacs or some other editor that can do it. So, they can always reformat
code for their need - I cannot because I do not use such editor.
Majorinc, Kazimir <····@email.com> wrote:
> In article <························@g49g2000cwa.googlegroups.com>,
> ··········@gmail.com says...
> > You are like a motorist that drives
> > on the wrong side of the road.
>
> Hm, side of the road is more than style .. long/short hair maybe.
I think Joe Marshall was more accurate, in his (certainly expert)
advice. In Structure and Interpretation of Computer Programs, the
authors make the point that writing code is about communicating with
humans as well as communicating with machines. If you wish others to
understand what you write, you should write as they expect to read it.
I suppose it is theoretically possible for someone literate in Arabic
or Russian to read text transliterated to a Latin character set, but if
I were asking a literate person to help me learn either language, I
would first learn to write in Arabic script or Cyrillic. Similarly, it
is theoretically possible for a Lisp programmer to read Lisp code when
formatted as C, but rude to expect him to do so.
> Plus, it appears that all the people who use )))) use in the same time
> Emacs or some other editor that can do it. So, they can always reformat
> code for their need - I cannot because I do not use such editor.
Using an editor which cannot match parentheses will cause *much* more
frustration in your use of Lisp than any amount of flamage you will get
in comp.lang.lisp. Pick the right tool for the job.
Majorinc schrieb:
> Plus, it appears that all the people who use )))) use in the same time
> Emacs or some other editor that can do it. So, they can always reformat
> code for their need - I cannot because I do not use such editor.
If I would not use Emacs (or another lisp aware editor) I think I would
do it like you did and use the C-style of placing the brackets.
You probably don't want to use Emacs because it uses different
key-bindings as most other editors do.
Perhaps http://jabberwocky.sourceforge.net/ works better for you.
André
--
Majorinc wrote:
> Plus, it appears that all the people who use )))) use in the same time
> Emacs or some other editor that can do it. So, they can always reformat
> code for their need - I cannot because I do not use such editor.
This should be among the top 3 of your todo list. It doesn't have to be
Emacs, but depending on your platform, you can also try out one of the
IDEs of Allegro Common Lisp, Corman Lisp, LispWorks or (to a lesser
extent) Macintosh Common Lisp. They all offer trial versions. That they
are commercial implementations and not open source doesn't matter for
learning purposes, especially for learning the very basic concepts. You
can always switch to an open source implementation later on.
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
In article <···············@individual.net>, ··@p-cos.net says...
> Majorinc wrote:
>
> > Plus, it appears that all the people who use )))) use in the same time
> > Emacs or some other editor that can do it. So, they can always reformat
> > code for their need - I cannot because I do not use such editor.
>
> This should be among the top 3 of your todo list. It doesn't have to be
> Emacs, but depending on your platform, you can also try out one of the
> IDEs of Allegro Common Lisp, Corman Lisp, LispWorks or (to a lesser
> extent) Macintosh Common Lisp. They all offer trial versions. That they
> are commercial implementations and not open source doesn't matter for
> learning purposes, especially for learning the very basic concepts. You
> can always switch to an open source implementation later on.
Well, my proposal to you is to give up from editor that supports ))))
and switch to some normal editor. First few hours it might feel strange,
but in few days you'll feel like you are free again ...
You don't believe me? Oh well...
Majorinc wrote:
> Well, my proposal to you is to give up from editor that supports ))))
> and switch to some normal editor. First few hours it might feel strange,
> but in few days you'll feel like you are free again ...
My proposal to you is to give up from computer and switch to typewriter.
First few hours it might feel strange, but in a few days we'll feel like
we are free again.
Majorinc wrote:
> In article <···············@individual.net>, ··@p-cos.net says...
>
>>Majorinc wrote:
>>
>>>Plus, it appears that all the people who use )))) use in the same time
>>>Emacs or some other editor that can do it. So, they can always reformat
>>>code for their need - I cannot because I do not use such editor.
>>
>>This should be among the top 3 of your todo list. It doesn't have to be
>>Emacs, but depending on your platform, you can also try out one of the
>>IDEs of Allegro Common Lisp, Corman Lisp, LispWorks or (to a lesser
>>extent) Macintosh Common Lisp. They all offer trial versions. That they
>>are commercial implementations and not open source doesn't matter for
>>learning purposes, especially for learning the very basic concepts. You
>>can always switch to an open source implementation later on.
>
> Well, my proposal to you is to give up from editor that supports ))))
> and switch to some normal editor. First few hours it might feel strange,
> but in few days you'll feel like you are free again ...
>
> You don't believe me? Oh well...
I have used both approaches, and know the difference.
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
Majorinc wrote:
> In article <···············@individual.net>, ··@p-cos.net says...
> > Majorinc wrote:
> >
> > > Plus, it appears that all the people who use )))) use in the same time
> > > Emacs or some other editor that can do it. So, they can always reformat
> > > code for their need - I cannot because I do not use such editor.
> >
> > This should be among the top 3 of your todo list. It doesn't have to be
> > Emacs, but depending on your platform, you can also try out one of the
> > IDEs of Allegro Common Lisp, Corman Lisp, LispWorks or (to a lesser
> > extent) Macintosh Common Lisp. They all offer trial versions. That they
> > are commercial implementations and not open source doesn't matter for
> > learning purposes, especially for learning the very basic concepts. You
> > can always switch to an open source implementation later on.
>
> Well, my proposal to you is to give up from editor that supports ))))
> and switch to some normal editor. First few hours it might feel strange,
> but in few days you'll feel like you are free again ...
>
> You don't believe me? Oh well...
I have used both types of editors. I now use one that can match
parenthesis to edit every programming language I write, not only lisp,
but also C.
It's very useful indeed because when you close a parenthesis you have
an idea about which expression you are ending. The editor however
knows, and sometimes proves you wrong about it. This gives you a form
of feedback about your code and allows many small errors to be
corrected without needing to resort to the compiler.
In article <1137489880.310058.75460
@g43g2000cwa.googlegroups.com>, ·············@antenova.com
says...
> Majorinc wrote:
> > In article <···············@individual.net>, ··@p-cos.net says...
> > > Majorinc wrote:
> > >
> > > > Plus, it appears that all the people who use )))) use in the same time
> > > > Emacs or some other editor that can do it. So, they can always reformat
> > > > code for their need - I cannot because I do not use such editor.
> > >
> > > This should be among the top 3 of your todo list. It doesn't have to be
> > > Emacs, but depending on your platform, you can also try out one of the
> > > IDEs of Allegro Common Lisp, Corman Lisp, LispWorks or (to a lesser
> > > extent) Macintosh Common Lisp. They all offer trial versions. That they
> > > are commercial implementations and not open source doesn't matter for
> > > learning purposes, especially for learning the very basic concepts. You
> > > can always switch to an open source implementation later on.
> >
> > Well, my proposal to you is to give up from editor that supports ))))
> > and switch to some normal editor. First few hours it might feel strange,
> > but in few days you'll feel like you are free again ...
> >
> > You don't believe me? Oh well...
>
> I have used both types of editors. I now use one that can match
> parenthesis to edit every programming language I write, not only lisp,
> but also C.
I use Scite. It does match parenthesis, but it does not
automatically reformate text to )))) style.
On 2006-01-16 19:51:04 +0000, Majorinc, Kazimir <·····@email.com> said:
> Plus, it appears that all the people who use )))) use in the same time
> Emacs or some other editor that can do it. So, they can always reformat
> code for their need - I cannot because I do not use such editor.
The *free* (as in: not for money) LispWorks Personal Edition
provides an editor that is not Emacs and that does both reformatting
(indenting) and parentheses matching.
--
JFB
Majorinc, Kazimir <·····@email.com> writes:
>> You are like a motorist that drives
>> on the wrong side of the road.
>
> Hm, side of the road is more than style .. long/short hair maybe.
>
> Plus, it appears that all the people who use )))) use in the same time
> Emacs or some other editor that can do it. So, they can always reformat
> code for their need - I cannot because I do not use such editor.
You could at the very minimum ask clisp to format your code correctly
before pasting it here:
[173]>(pprint '(defun test (n)
(set 'list-of-nodes ())
(dotimes (j n)
(time (progn
(dotimes (i 10000)
(push (set 'new-node (list () ())) list-of-nodes)
(push (set 'random-old-node
(nth (if (= i j 0)
0
(random (+ (* j 10000) i))
)
list-of-nodes
)
)
(cadr new-node)
)
(push new-node (cdr random-old-node))
)
(print (* 10000 (1+ j)))
)
)
)
))
(DEFUN TEST (N) (SET 'LIST-OF-NODES NIL)
(DOTIMES (J N)
(TIME
(PROGN
(DOTIMES (I 10000) (PUSH (SET 'NEW-NODE (LIST NIL NIL)) LIST-OF-NODES)
(PUSH
(SET 'RANDOM-OLD-NODE
(NTH (IF (= I J 0) 0 (RANDOM (+ (* J 10000) I))) LIST-OF-NODES))
(CADR NEW-NODE))
(PUSH NEW-NODE (CDR RANDOM-OLD-NODE)))
(PRINT (* 10000 (1+ J)))))))
--
__Pascal Bourguignon__ http://www.informatimago.com/
I need a new toy.
Tail of black dog keeps good time.
Pounce! Good dog! Good dog!
On 2006-01-17 00:48:38 +0000, Pascal Bourguignon <····@mouse-potato.com> said:
> Majorinc, Kazimir <·····@email.com> writes:
>>> You are like a motorist that drives
>>> on the wrong side of the road.
>>
>> Hm, side of the road is more than style .. long/short hair maybe.
>>
>> Plus, it appears that all the people who use )))) use in the same time
>> Emacs or some other editor that can do it. So, they can always reformat
>> code for their need - I cannot because I do not use such editor.
>
> You could at the very minimum ask clisp to format your code correctly
> before pasting it here:
>
> [173]>(pprint '(defun test (n)
> (set 'list-of-nodes ())
> (dotimes (j n)
> (time (progn (dotimes (i 10000)
> (push (set 'new-node (list () ())) list-of-nodes)
> (push (set 'random-old-node
> (nth (if (= i j 0)
> 0 (random (+ (* j 10000)
> i))
> )
> list-of-nodes )
> )
> (cadr new-node)
> )
> (push new-node (cdr random-old-node))
> ) (print (* 10000 (1+ j)))
> )
> ) )
> ))
>
> (DEFUN TEST (N) (SET 'LIST-OF-NODES NIL)
> (DOTIMES (J N)
> (TIME
> (PROGN
> (DOTIMES (I 10000) (PUSH (SET 'NEW-NODE (LIST NIL NIL)) LIST-OF-NODES)
> (PUSH
> (SET 'RANDOM-OLD-NODE
> (NTH (IF (= I J 0) 0 (RANDOM (+ (* J 10000) I))) LIST-OF-NODES))
> (CADR NEW-NODE))
> (PUSH NEW-NODE (CDR RANDOM-OLD-NODE)))
> (PRINT (* 10000 (1+ J)))))))
May I suggest to
(setf *print-case* :downcase)
prior to the reformatting ?
(-:
--
JFB
On Tue, 17 Jan 2006 04:04:55 +0100, Pascal Bourguignon
<····@mouse-potato.com> wrote:
Wow! That has got to be the most elaborate joke I ever saw :)
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On Tue, 17 Jan 2006 09:50:27 +0100, John Thingstad
<··············@chello.no> wrote:
> On Tue, 17 Jan 2006 04:04:55 +0100, Pascal Bourguignon
> <····@mouse-potato.com> wrote:
>
> Wow! That has got to be the most elaborate joke I ever saw :)
>
Naw, the Brainfuck programming language is :)
http://en.wikipedia.org/wiki/Brainfuck
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Joe Marshall wrote:
> Majorinc wrote:
>
>>In article <···············@individual.net>, ··@p-cos.net
>>says...
>>
>>>- Your use of set is highly unusual. The ANSI CL specification states
>>>that set is a deprecated operator, and there are good reasons for this.
>>>Foremostly, set exclusivly operates on global variables, doesn't keep
>>>the local contexts of different functions separated, and is probably
>>>very inefficient.
>>
>>So what? It is still in standard, and I like it more than setq
>>and setf, because I prefer functions to macros and special
>>operators - if possible. Is it completely out of base? Of
>>course it is not, it is just another opinion, and you failed to
>>_clearly_ demonstrate that it is wrong.
>
>
> If you are the expert in what is right or wrong, why are you asking
> questions here?
>
>
>>We already discussed it, but again, although I've seen
>>arguments pro and contra, I failed to see clear demonstration
>>that )))) is better than C style. However, question of style is
>>clearly not important!!
>
>
> Style seems to be quite important to others in the group (see their
> postings). If it is `clearly not important' to you, then why do you
> persist in doing the wrong thing? You are like a motorist that drives
> on the wrong side of the road.
No, he is like Ilias, aka The Newby With All the Answers. I think this
syndrome has earned its place in the psychiatric handbook.
We had another one a few months ago, and I must say they are more fun
than a barrel full of monkeys.[1]
kenny (wondering why monkeys in a barrel are a benchmark for fun)
[1] No animals were harmed in this metaphor.
Kenny Tilton <·············@nyc.rr.com> writes:
> We had another one a few months ago, and I must say they are more fun
> than a barrel full of monkeys.[1]
>
> kenny (wondering why monkeys in a barrel are a benchmark for fun)
>
> [1] No animals were harmed in this metaphor.
^non-human
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
<Majorinc>; "Kazimir" <·······@chem.pmf.hr> wrote in message
·······························@news.carnet.hr...
>
> Ad hoc claim "set is probably very inefficient" is strange to
> me; in fact, it is wrong - at least in Clisp.
>
> --------------------
> [5]> (time (dotimes (i 1000000)(set 'x 100)))
> Real time: 1.078125 sec.
> Run time: 1.078125 sec.
> Space: 736 Bytes
> NIL
> ---------------------
> [4]> (time (dotimes (i 1000000)(setf x 100)))
> Real time: 1.875 sec.
> Run time: 1.875 sec.
> Space: 40000756 Bytes
> GC: 76, GC time: 0.1875 sec.
> NIL
>
SETF is a macro, calling it in CLISP as you have cause
the macro gets expanded every time through the loop,
try compiling it.
[1]> (defun foo() (setf x 3))
FOO
[2]> (defun bar() (set 'x 3))
BAR
[3]> (compile 'foo)
WARNING in FOO :
X is neither declared nor bound,
it will be treated as if it were declared SPECIAL.
FOO ;
1 ;
1
[4]> (compile 'bar)
WARNING in BAR :
Function SET is deprecated. This function name is anachronistic. Use SETF
SYMBOL
-VALUE instead.
BAR ;
1 ;
1
[5]> (time (dotimes (i 100000) (foo)))
Real time: 1.101584 sec.
Run time: 0.8912816 sec.
Space: 736 Bytes
NIL
[6]> (time (dotimes (i 100000) (bar)))
Real time: 1.1816992 sec.
Run time: 0.9613824 sec.
Space: 736 Bytes
NIL
As for the parentheses, feel free to write them however makes you most
comfortable, but when you post the code take the time to reformat it,
the majority of people here prefer 'lisp-style', you'll get more people
looking at the code and less complaints.
--
Geoff
On 2006-01-16 18:11:02 +0000, "Geoffrey Summerhayes"
<·············@hotmail.com> said:
> SETF is a macro, calling it in CLISP as you have cause
> the macro gets expanded every time through the loop,
> try compiling it.
I must applaud your patience. Reading the OP replies wasn't
very enticing to provide any further help. His insult to the
violin remark clearly shows he hasn't got a clue.
Many thanks for responding anyway. I'm sure that many
newbies, (myself included) learnt another tidbit in their
road to Lisp :-)
Best Regards
--
JFB
On 2006-01-16 15:55:09 +0000, Majorinc, Kazimir <·······@chem.pmf.hr> said:
If you sincerely beleive that:
> However, question of style is clearly not important!!
then you have picked the wrong language! Lisp is not for you.
--
JFB
Am 16.01.2006 16:55 Uhr schrieb "Majorinc, Kazimir" unter
<·······@chem.pmf.hr> in ··························@news.carnet.hr:
> In article <···············@individual.net>, ··@p-cos.net
> says...
>
>
>>
>> Your code is very non-idiomatic. Two important things:
>
> Ouch.
>
>>
>> - Your use of set is highly unusual. The ANSI CL specification states
>> that set is a deprecated operator, and there are good reasons for this.
>> Foremostly, set exclusivly operates on global variables, doesn't keep
>> the local contexts of different functions separated, and is probably
>> very inefficient.
>
> So what? It is still in standard, and I like it more than setq
> and setf, because I prefer functions to macros and special
> operators - if possible. Is it completely out of base? Of
> course it is not, it is just another opinion, and you failed to
> _clearly_ demonstrate that it is wrong.
Well, with this attitude you will probably get many helpful responses.
Why are you using special variables?
The Lisp style you write went out of fashion maybe twenty years
ago.
>
> Ad hoc claim "set is probably very inefficient" is strange to
> me; in fact, it is wrong - at least in Clisp.
>
> [13]> (time (dotimes (i 1000000)))
> Real time: 0.8125 sec.
> Run time: 0.8125 sec.
> Space: 728 Bytes
> NIL
> --------------------
> [14]> (time (dotimes (i 1000000)(setq x 100)))
> Real time: 1.0 sec.
> Run time: 1.0 sec.
> Space: 736 Bytes
> NIL
> -------------------
> [11]> (setf y (quote x))
> X
> [12]> (time (dotimes (i 1000000)(set y 100)))
> Real time: 1.015625 sec.
> Run time: 1.015625 sec.
> Space: 736 Bytes
> NIL
> --------------------
> [5]> (time (dotimes (i 1000000)(set 'x 100)))
> Real time: 1.078125 sec.
> Run time: 1.078125 sec.
> Space: 736 Bytes
> NIL
> ---------------------
> [4]> (time (dotimes (i 1000000)(setf x 100)))
> Real time: 1.875 sec.
> Run time: 1.875 sec.
> Space: 40000756 Bytes
> GC: 76, GC time: 0.1875 sec.
> NIL
Do you understand the difference between special variables
and lexical variables? Global and local?
Do you understand the difference between the interpreted
top-level forms and the usage of the compiler in CLISP?
>> - If you are using nth to access elements in a list, then you haven't
>> understood the various opportunities to use and build your own
>> datastructures yet. You should only rarely use nth to access elements in
>> a list, especially not in benchmarks because it is a very slow
>> operation. Lists can be very useful and have their advantages, but this
>> is definitely not one of them.
>
> Well, this could be more important - but again it is wrong
> logic. Using that logic, recursive definition of Fibonacci
> numbers is useless benchmark, because it is not efficient way
> for calculations of Fibonacci numbers!
>
> Now, I'm sure that if you think carefully, you'll find quite a
> few good reasons why benchmarks do not necessarily to implement
> best possible algorithm/data structure for a given problem.
You can benchmark algorithm implementations that have no
real-world usage. That's fine. But don't forget to benchmark
the code that people actually tend to write, when they
want an efficient implementation.
>> - You shouldn't put closing parentheses in their own lines. This makes
>> your code very unreadable and wastes valuable vertical space on your
>> screen. If you think that putting them on single lines, then you simply
>> don't have enough experience with programming in Lisp and using the
>> right editors to support Lisp syntax. No mildly experienced Lispers does
>> what you are doing here.
>
> We already discussed it, but again, although I've seen
> arguments pro and contra, I failed to see clear demonstration
> that )))) is better than C style. However, question of style is
> clearly not important!!
Sure it is important. You want to show your code to other people -
atleast that is what you did. You need to write code to
run it on a computer - but you also need to write code for others
to read and understand it.
In the Common Lisp 'community' very few people use your indentation
style. Most people think it is a waste of whitespace. If you
want to communicate effectively with those, you better format
your code so that we can read it.
I took your code in an editor and reformatted it to make it readable.
Additionally you also might find out why the majority of
Common-Lisp-Programmers prefers the other way to format code.
>> These observation strongly indicate that you haven't learned enough of
>> the very basics of Lisp yet and are at the very beginning of learning
>> the language. It is highly recommended that you pick a good tutorial
>> (like "Practical Common Lisp", "Successful Lisp" or "Paradigms of
>> Artificial Intelligence Programming") before wasting your time on
>> benchmarks that are very likely not to tell you anything useful at all.
>> You will have a much better understanding what the important elements
>> are that contribute to, or diminish, performance only at a much later stage.
>
> It has no sense. Look, what would you do if I told you that,
> say, Aldor is superior languge to Lisp? Would you spend two
> years to learn it, or would you try to write few benchmarks
> very first day, just to make some opinion? For example, that
> already mentioned Fibonacci recursive function?
I would read the Aldor manual in a few hours to understand
what is all about. Then I would try to write a few little
programs with it. Maybe even measure some performance. But
that would not be the first thing I'd do.
>
> Benchmark tests are not blood oaths, for God sake; they are
> almost everyday activity, useful for very different purposes,
> for very different kinds of needs ... strange that I have to
> explain that.
>
You sure, you want to use Lisp? Not C?
Majorinc, Kazimir <·······@chem.pmf.hr> writes:
> In article <···············@individual.net>, ··@p-cos.net
> says...
>
>
>>
>> Your code is very non-idiomatic. Two important things:
>
> Ouch.
>
>>
>> - Your use of set is highly unusual. The ANSI CL specification states
>> that set is a deprecated operator, and there are good reasons for this.
>> Foremostly, set exclusivly operates on global variables, doesn't keep
>> the local contexts of different functions separated, and is probably
>> very inefficient.
>
> So what? It is still in standard, and I like it more than setq
> and setf, because I prefer functions to macros and special
> operators - if possible. Is it completely out of base? Of
> course it is not, it is just another opinion, and you failed to
> _clearly_ demonstrate that it is wrong.
>
> Ad hoc claim "set is probably very inefficient" is strange to
> me; in fact, it is wrong - at least in Clisp.
>
> [13]> (time (dotimes (i 1000000)))
> Real time: 0.8125 sec.
> Run time: 0.8125 sec.
> Space: 728 Bytes
> NIL
TIME should be forbidden to newbies like '...
[166]>
(defun b1 () (dotimes (i 10000000)))
(defun b2 () (dotimes (i 10000000)(setq x 100)))
(defun b3 () (setf y (quote x)) (dotimes (i 10000000)(set y 100)))
(defun b4 () (dotimes (i 10000000)(set 'x 100)))
(defun b5 () (dotimes (i 10000000)(setf x 100)))
B1
[167]> B2
[168]> B3
[169]> B4
[170]> B5
[171]> (dolist (f '(b1 b2 b3 b4 b5)) (compile f))
WARNING in B2 :
X is neither declared nor bound,
it will be treated as if it were declared SPECIAL.
WARNING in B3 :
Y is neither declared nor bound,
it will be treated as if it were declared SPECIAL.
WARNING in B3 :
Function SET is deprecated. This function name is anachronistic. Use SETF SYMBOL-VALUE instead.
WARNING in B3 :
Y is neither declared nor bound,
it will be treated as if it were declared SPECIAL.
WARNING in B4 :
Function SET is deprecated. This function name is anachronistic. Use SETF SYMBOL-VALUE instead.
WARNING in B5 :
X is neither declared nor bound,
it will be treated as if it were declared SPECIAL.
NIL
[172]> (dolist (f '(b1 b2 b3 b4 b5)) (time (funcall f)))
Real time: 1.606793 sec.
Run time: 1.6 sec.
Space: 0 Bytes
Real time: 1.834046 sec.
Run time: 1.84 sec.
Space: 0 Bytes
Real time: 2.804893 sec.
Run time: 2.79 sec.
Space: 0 Bytes
Real time: 2.700981 sec.
Run time: 2.67 sec.
Space: 0 Bytes
Real time: 2.000579 sec.
Run time: 1.84 sec.
Space: 0 Bytes
NIL
[173]>
Results: empty loop: 1.6
setq x 1.84
set 'x 2.79
set y 2.67
setf x 1.84
> We already discussed it, but again, although I've seen
> arguments pro and contra, I failed to see clear demonstration
> that )))) is better than C style. However, question of style is
> clearly not important!!
Because you're programming in Lisp, not in C! But don't worry, write
intensively Lisp for a month or two and you'll be converted like us.
I started too putting (some) closing parentheses on their own lines.
> Benchmark tests are not blood oaths, for God sake; they are
> almost everyday activity, useful for very different purposes,
> for very different kinds of needs ... strange that I have to
> explain that.
The problem is that until you know the ins and outs of the language,
you cannot write a significant benchmark, and you cannot interpret it
correctly.
In the case of lisp, the most important benchmark is to take a C
expert programmer, and a Lisp expert programmer, and give them the
same non-trivial problem and measure how much time (therefore how much
money you must pay them) then take to develop the solution. You can
add the run-time if you want.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Logiciels libres : nourris au code source sans farine animale."
In article <··············@thalassa.informatimago.com>, ····@mouse-
potato.com says...
> >
> > [13]> (time (dotimes (i 1000000)))
> > Real time: 0.8125 sec.
> > Run time: 0.8125 sec.
> > Space: 728 Bytes
> > NIL
>
> TIME should be forbidden to newbies like '...
What's that bullshit? You are trying to make an impression that you
believe that results clearly confirm your side? I didn't bought it. What
a joke.
>
> In the case of lisp, the most important benchmark is to take a C
> expert programmer, and a Lisp expert programmer, and give them the
> same non-trivial problem and measure how much time (therefore how much
> money you must pay them) then take to develop the solution. You can
> add the run-time if you want.
Now, that is only part of your post which is true. My opinion is that
really Lisp has one of the best potentials of all PL, however, outcome
clearly depends of available built-in functions and standard libraries.
And although Lisp probably excelled in 1970's or early '80s, today it is
not that simple any more.
Majorinc wrote:
> In article <··············@thalassa.informatimago.com>, ····@mouse-
> potato.com says...
> > TIME should be forbidden to newbies like '...
>
> What's that bullshit? You are trying to make an impression that you
> believe that results clearly confirm your side? I didn't bought it. What
> a joke.
The point (not bullshit at all) was that, when doing benchmarking, or
any kind of scientific measurement, you must be careful to understand
what it is you are measuring.
Did you read his nicely formatted table of results, which you snipped?
There are many mistakes that can be made in this area, particularly in
Lisp.
One key error often made is to inadvertently include the time necessary
for the Lisp compiler to work. Many Lisp implementations work by
compiling the user's input expression-by-expression before computing
it. That can often take longer than the execution of the compiled code;
ironically, this happens most for those compilers that make the effort
to generate especially fast code.
C programmers don't make this mistake because invoking the compiler is
a separate manual step, while Lisp implementations often hide it.
A related error is to time the code *without* compiling it, because
*other* Lisp implementations fall back on an interpreter when the code
is not compiled. C programmers don't make this mistake because the UNIX
kernel does not automatically recognized .c files and their contents as
executable.
C programmers, of course, can make different mistakes in their
benchmarks.
You will do much better in life by assuming that those taking the time
to reply to you have a valid point, instead of quickly labelling them
as assholes spouting bullshit.
Majorinc wrote:
> > In the case of lisp, the most important benchmark is to take a C
> > expert programmer, and a Lisp expert programmer, and give them the
> > same non-trivial problem and measure how much time (therefore how much
> > money you must pay them) then take to develop the solution. You can
> > add the run-time if you want.
>
> Now, that is only part of your post which is true. My opinion is that
> really Lisp has one of the best potentials of all PL, however, outcome
> clearly depends of available built-in functions and standard libraries.
> And although Lisp probably excelled in 1970's or early '80s, today it is
> not that simple any more.
Which bit of the standard library of lisp do you believe is inferior to
that of other langauges?
In article <1137490145.929522.12770
@g49g2000cwa.googlegroups.com>, ·············@antenova.com
says...
> Which bit of the standard library of lisp do you believe is inferior to
> that of other langauges?
For me data structures (and algorithms) are the most important.
Majorinc wrote:
> In article <1137490145.929522.12770
> @g49g2000cwa.googlegroups.com>, ·············@antenova.com
> says...
> > Which bit of the standard library of lisp do you believe is inferior to
> > that of other langauges?
>
> For me data structures (and algorithms) are the most important.
I'd agree with that too, but above you mentioned that you thought that
other languages had better standard libraries. In what way do you
think they're better?
In article <1137589187.743959.221300
@o13g2000cwo.googlegroups.com>, ·············@antenova.com
says...
> I'd agree with that too, but above you mentioned that you thought that
> other languages had better standard libraries. In what way do you
> think they're better?
As far as I see, Lisp supports only one kind of list, and very
few operations on graphs made of cons; arrays and hash tables.
Not even sets are real data structure but set operations are
implemented on lists (and I see that some of these operations
convert lists to hash tables.)
Two languages I used previously, C++ and Unicon have more
extensive libraries for data structures, C++ STL for
practically everything, and Icon Program Library for most
important data types like lists, sets, multisets ... I believe
that other popular languages are same.
On Wed, 18 Jan 2006 16:19:02 +0100, <Majorinc> wrote:
> In article <1137589187.743959.221300
> @o13g2000cwo.googlegroups.com>, ·············@antenova.com
> says...
>
>
>> I'd agree with that too, but above you mentioned that you thought that
>> other languages had better standard libraries. In what way do you
>> think they're better?
>
> As far as I see, Lisp supports only one kind of list, and very
> few operations on graphs made of cons; arrays and hash tables.
> Not even sets are real data structure but set operations are
> implemented on lists (and I see that some of these operations
> convert lists to hash tables.)
>
> Two languages I used previously, C++ and Unicon have more
> extensive libraries for data structures, C++ STL for
> practically everything, and Icon Program Library for most
> important data types like lists, sets, multisets ... I believe
> that other popular languages are same.
>
>
The key is in the way it all fits together.
In time and with experience you might see.
It is extesible just not as extensive.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Majorinc wrote:
> In article <1137589187.743959.221300
> @o13g2000cwo.googlegroups.com>, ·············@antenova.com
> says...
>
>
> > I'd agree with that too, but above you mentioned that you thought that
> > other languages had better standard libraries. In what way do you
> > think they're better?
>
> As far as I see, Lisp supports only one kind of list, and very
> few operations on graphs made of cons; arrays and hash tables.
> Not even sets are real data structure but set operations are
> implemented on lists (and I see that some of these operations
> convert lists to hash tables.)
Lisp supports more than one kind of list, linearly, singly linked lists
are called "proper lists", and have operations that can be done on
them. However you can make doubly linked lists, circular lists, trees
etc, they're called "improper lists".
I quite agree about sets, it would be very useful to have set
operations outside of those that operate on lists.
I don't know that there are very few operations on graphs made of
"cons, arrays and hash tables", what is missing?
BTW none of the operations convert lists to hash-tables (AFAIK), the
alist operations simply treat lists themselves as a lookup mechanism.
This is not efficient when lookups are needed on large blocks of data.
Alist ops are made for situations where a list may be iterated through,
or looked up.
"Rob Thorpe" <·············@antenova.com> writes:
> BTW none of the operations convert lists to hash-tables (AFAIK), the
> alist operations simply treat lists themselves as a lookup mechanism.
> This is not efficient when lookups are needed on large blocks of data.
> Alist ops are made for situations where a list may be iterated through,
> or looked up.
Well, it would be fairly easy to write an alist-to-hash-table function.
One area where alists are handy is if you want to have a fairly
lightweight mechanism for temporarily changing the binding of a
particular key, and then recovering the original binding later.
I found this useful for dealing with things that can change, like xml
namespace mappings. I did this by pushing all newly defined namespace
mappings from processing a particular tag onto an alist of mappings and
then just remembering how many were encountered. When exiting the
processing of that tag, the appropriate number of bindings were popped,
leaving the original list in place.
--
Thomas A. Russ, USC/Information Sciences Institute
In article <························@z14g2000cwz.googlegroups.com>,
·············@antenova.com says...
> Lisp supports more than one kind of list, linearly, singly linked lists
> are called "proper lists", and have operations that can be done on
> them. However you can make doubly linked lists, circular lists, trees
> etc, they're called "improper lists".
> I don't know that there are very few operations on graphs.
> what is missing?
All these structures can be built in Lisp, from cons - like they can be
build in C, Pascal, even in Fortran; but they are not already there, as
type and operations on them, not even heaps or double-linked lists.
Compare Lisp with STL containers or Boost Graph Library which is on its
way to become standard...
>
> BTW none of the operations convert lists to hash-tables (AFAIK), the
> alist operations simply treat lists themselves as a lookup mechanism.
> This is not efficient when lookups are needed on large blocks of data.
> Alist ops are made for situations where a list may be iterated through,
> or looked up.
I just tested subsetp function in Clisp, and it was much faster than I
expected. Once lists were to big, it returned error "hash table too
big" which explains why they're very fast.
Majorinc wrote:
> In article <························@z14g2000cwz.googlegroups.com>,
> ·············@antenova.com says...
>
> > Lisp supports more than one kind of list, linearly, singly linked lists
> > are called "proper lists", and have operations that can be done on
> > them. However you can make doubly linked lists, circular lists, trees
> > etc, they're called "improper lists".
> > I don't know that there are very few operations on graphs.
> > what is missing?
>
> All these structures can be built in Lisp, from cons - like they can be
> build in C, Pascal, even in Fortran; but they are not already there, as
> type and operations on them, not even heaps or double-linked lists.
> Compare Lisp with STL containers or Boost Graph Library which is on its
> way to become standard...
The part about C, Pascal, and Fortran is absurd. Cons cells are fully
generic; they can point to other cons cells OR to any other Lisp
object. This is virtually impossible in those languages. Furthermore,
Lisp automatically manages the storage issues which come about because
the generic nature of cons cells allows for circular structures.
I'll concede that sufficient template meta-programming will make
something like it possible in C++. But comparing that monstrosity to
the simplicity of cons cells in Lisp is a stretch.
In article <·······················@g14g2000cwa.googlegroups.com>,
············@gmail.com says...
> The part about C, Pascal, and Fortran is absurd. Cons cells are fully
> generic; they can point to other cons cells OR to any other Lisp
> object. This is virtually impossible in those languages.
Its the problem of dynamic data typing vs static data typing. In Lisp
program, same variable can have integer value, and later float, in
C/Pascal it cannot. I like dynamic typing far more, but it is not
specific to data structures.
> Furthermore,
> Lisp automatically manages the storage issues which come about because
> the generic nature of cons cells allows for circular structures.
Yes, that's really good thing.
>
> I'll concede that sufficient template meta-programming will make
> something like it possible in C++. But comparing that monstrosity to
> the simplicity of cons cells in Lisp is a stretch.
Lisp has simpler syntax, no doubt.
However, it is not that big advantage that it can compare with ease of
importing, say, dequeue, set or multiset from C++ STL ...
Majorinc, Kazimir <·····@email.com> writes:
> All these structures can be built in Lisp, from cons - like they can be
> build in C, Pascal, even in Fortran; but they are not already there, as
> type and operations on them, not even heaps or double-linked lists.
> Compare Lisp with STL containers or Boost Graph Library which is on its
> way to become standard...
Doubly-linked lists is probably the one item that I haven't found on the
list of what you are interested in.
Lots of these libraries already exist. Unfortunately they may not be
quite as easy to find as STL or even Boost. But with any luck the
Common Lisp Gardeners project may help with that.
It does seem that having a better index to existing libraries would go a
long way toward addressing complaints about a dearth of libraries in
Lisp.
In any case, some starting points for finding such libraries are
http://www.alu.org/ Lisp Resources
http://www.cliki.net/
http://www.cs.cmu.edu/afs/cs.cmu.edu/project/ai-repository/ai/lang/lisp/
--
Thomas A. Russ, USC/Information Sciences Institute
From: drewc
Subject: Re: Help with one benchmark test needed
Date:
Message-ID: <87psmnw0sm.fsf@rift.com>
Majorinc, Kazimir <·····@email.com> writes:
> In article <························@z14g2000cwz.googlegroups.com>,
> ·············@antenova.com says...
>
>> Lisp supports more than one kind of list, linearly, singly linked lists
>> are called "proper lists", and have operations that can be done on
>> them. However you can make doubly linked lists, circular lists, trees
>> etc, they're called "improper lists".
>> I don't know that there are very few operations on graphs.
>> what is missing?
>
> All these structures can be built in Lisp, from cons - like they can be
> build in C, Pascal, even in Fortran; but they are not already there, as
> type and operations on them, not even heaps or double-linked lists.
> Compare Lisp with STL containers or Boost Graph Library which is on its
> way to become standard...
Ok, so we are comparing available libraries to available libraries. Good.
now, i've never used STL containers or Boost (Although i most
certainly would if forced to work in c++), so i'm not sure what they
support, but CL-CONTAINERS[1] has pretty comprehensive collection of
data structures. If Gary King's other libraries are any indication, it
is probably quite complete and of high-quality.
Here is a list:
abstract-container Inherited by all container classes, this is a good
place to put those pesky superclasses you need...
abstract-queue
alist-container
array-container
associative-container
associative-container-mixin
bag-container
basic-queue
biassociative-container-mixin
binary-search-tree
bounded-vector-container
container-node-mixin
container-uses-nodes-mixin
contents-as-array-mixin
contents-as-hashtable-mixin
contents-as-list-mixin
dlist-container A double-linked list
dlist-container-node A double-linked list node
filtered-iterator-mixin
flexible-vector-container
forward-iterator
heap-container
i-know-my-node-mixin
initial-contents-mixin
iteratable-container-mixin
k-best-heap-container Stores the k *best*
values where *best* is defined by sorter. This means that the item at
the to...
keyed-associative-container
keyed-bag/set-container
list-container
list-iterator
many-child-node
many-ordered-child-node A node with many ordered children is a vector
many-unordered-child-node Children are unordered
non-associative-container-mixin A non associative container should
implement at least empty-p, empty, insert-item and delete-item...
package-container
parent-node-mixin A mixin for nodes with parent pointers
priority-queue-on-container
quad-tree
red-black-tree
ring-buffer
rooted-tree-container Base class of all trees with roots.
set-container
simple-associative-container
sorted-dlist-container A
persistently sorted double-linked list sorted-list-container A list
container that keeps its items sorted as needed. This uses 'sort' so
it best for small con...
sparse-array-container
stable-associative-container
stack-container
test-container-mixin
union-find-container
unique-value-iterator-mixin
vector-container
All that just an ASDF-INSTALL away. And you get all the advantages of
lisp over C++. Imagine that. Next please.
--
drewc at tech dot coop
[1] http://common-lisp.net/project/cl-containers/
Majorinc wrote:
> In article <···············@individual.net>, ··@p-cos.net
> says...
>
>>Your code is very non-idiomatic. Two important things:
>
> Ouch.
>
>>- Your use of set is highly unusual. The ANSI CL specification states
>>that set is a deprecated operator, and there are good reasons for this.
>>Foremostly, set exclusivly operates on global variables, doesn't keep
>>the local contexts of different functions separated, and is probably
>>very inefficient.
>
> So what? It is still in standard, and I like it more than setq
> and setf, because I prefer functions to macros and special
> operators - if possible.
Setq and setf would also be wrong at those places where you have used
set. You don't seem to understand the concept of local variables. That's
a very basic notion, and a newsgroup is not the right place to discuss
such low-level basic fundamentals that are covered in all tutorials.
> Is it completely out of base?
Yes.
> Of
> course it is not, it is just another opinion, and you failed to
> _clearly_ demonstrate that it is wrong.
I don't need to demonstrate anything. These things are already
demonstrated well enough in several other publications, some of which I
have already pointed out.
>>- If you are using nth to access elements in a list, then you haven't
>>understood the various opportunities to use and build your own
>>datastructures yet. You should only rarely use nth to access elements in
>>a list, especially not in benchmarks because it is a very slow
>>operation. Lists can be very useful and have their advantages, but this
>>is definitely not one of them.
>
> Well, this could be more important - but again it is wrong
> logic. Using that logic, recursive definition of Fibonacci
> numbers is useless benchmark, because it is not efficient way
> for calculations of Fibonacci numbers!
>
> Now, I'm sure that if you think carefully, you'll find quite a
> few good reasons why benchmarks do not necessarily to implement
> best possible algorithm/data structure for a given problem.
An important issue in benchmarking is that you have a good idea of what
you are _actually_ measuring. It doesn't seem to me that you have such
an idea. You rather seem to just measure random code that noone with
enough Lisp experience would actually write.
>>- You shouldn't put closing parentheses in their own lines. This makes
>>your code very unreadable and wastes valuable vertical space on your
>>screen. If you think that putting them on single lines, then you simply
>>don't have enough experience with programming in Lisp and using the
>>right editors to support Lisp syntax. No mildly experienced Lispers does
>>what you are doing here.
>
> We already discussed it, but again, although I've seen
> arguments pro and contra, I failed to see clear demonstration
> that )))) is better than C style.
It can't be demonstrated. A good rational argument is that putting each
closing parenthesis on a line of its own wastes vertical space. You have
a better understanding of your programs if you can see more of it at the
same time. That's why code compression in general is a good idea. See,
for example, http://www.paulgraham.com/power.html - which is not a proof
of my claims, just a hint.
The advantage of lining up closing parentheses is something that you
should try out and see for yourself, instead of asking for
"demonstrations". I have made the experience quite a few times that
people got it by just seeing me demo how I write Lisp code in an editor
that supports it (LispWorks in my case). Trying it out for yourself is
probably even better.
>>These observation strongly indicate that you haven't learned enough of
>>the very basics of Lisp yet and are at the very beginning of learning
>>the language. It is highly recommended that you pick a good tutorial
>>(like "Practical Common Lisp", "Successful Lisp" or "Paradigms of
>>Artificial Intelligence Programming") before wasting your time on
>>benchmarks that are very likely not to tell you anything useful at all.
>>You will have a much better understanding what the important elements
>>are that contribute to, or diminish, performance only at a much later stage.
>
> It has no sense. Look, what would you do if I told you that,
> say, Aldor is superior languge to Lisp? Would you spend two
> years to learn it, or would you try to write few benchmarks
> very first day, just to make some opinion? For example, that
> already mentioned Fibonacci recursive function?
My typical approach to learning a new language is to try to implement
some large program that I would know how to write in a language that I
already know, so that I can compare the different trade-offs and
benefits. My first Common Lisp project was an implementation of the Java
Virtual Machine - a program that I wouldn't have dared to write on my
own in any other language. It worked pretty smoothly. Furthermore, it
was a just-in-time compiler, so from a performance point of view, it
should be quite good. (However, I didn't perform any benchmarks on the
resulting code because it would have cost too much time.)
I wouldn't try to play around with toy examples and especially not with
micro benchmarks, because they don't buy you anything at all. That's a
well-known fact.
See, for example, a relatively new paper at
http://www-plan.cs.colorado.edu/diwan/vertical-prof-oopsla.pdf - or here
is something more Lisp-related:
http://p-cos.net/lisp-ecoop/submissions/Rhodes.pdf
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
Majorinc, Kazimir <·······@chem.pmf.hr> writes:
> In article <···············@individual.net>, ··@p-cos.net
> > - Your use of set is highly unusual. The ANSI CL specification states
> > that set is a deprecated operator, and there are good reasons for this.
> > Foremostly, set exclusivly operates on global variables, doesn't keep
> > the local contexts of different functions separated, and is probably
> > very inefficient.
>
> So what? It is still in standard, and I like it more than setq
> and setf, because I prefer functions to macros and special
> operators - if possible. Is it completely out of base?
Look at this example of the use of SET
CL-USER> (defvar *variable-name* 'x)
*VARIABLE-NAME*
CL-USER> (defun clear (symbol)
(set symbol 0))
CLEAR
CL-USER> (let ((x 1))
(declare (special x))
(let ((x 2))
(declare (special x))
(print x)
(clear *variable-name*)
(print x))
(print x)
(clear *variable-name*)
(print x))
2
0
1
0
0
This exhibits the use of SET to access variables using the
symbols that name them. This is peculiar to special
bindings. It doesn't work with lexical bindings, and it is
deliberate that it doesn't work with lexical bindings, not
least because the restriction enables compiler
optimisations.
For example, stripping out the inner binding of x and
letting it default to be lexical:
(let ((x 2))
(print x)
(clear *variable-name*)
(print x))
Lexical variables have lexical scope, in contrast to the
indefinite scope of special variables. Consequently the
complier can use the fact that X is lexical, not special, to
figure out that CLEAR cannot get at X. This allows it to do
a source level optimisation, eliminating x, resulting in the
code
(print 2)
(clear *variable-name*)
(print 2)
In using SET, you are accessing specialised functionality,
which you probably are not goint to use (special variables
only have dynamic extent in contrast to the indefinite
extent of lexical variables), and which may have performance
implications. This is bad for the relevance of the timings
that you get from your benchmarks.
Alan Crowe
Edinburgh
Scotland
Majorinc wrote:
> In article <···············@individual.net>, ··@p-cos.net
> says...
>
>
> >
> > Your code is very non-idiomatic. Two important things:
>
> Ouch.
>
> >
> > - Your use of set is highly unusual. The ANSI CL specification states
> > that set is a deprecated operator, and there are good reasons for this.
> > Foremostly, set exclusivly operates on global variables, doesn't keep
> > the local contexts of different functions separated, and is probably
> > very inefficient.
Life could be easier for you if you would listen to Pascal. He is a
very experienced Common Lisp user.
Do not play childish and listen. Nobody awaits your outcome with Common
Lisp. There are better coders alive.
I was always happy when people gave me some new insights and pointed me
into new directions.
Sir Franics Drake
Btw: It would be easier if you post your background. There are
trillions of hordes of programmers out there who will chose a
programming language based on some useless benchmarks whereas their
daily coding life consits of mundane ordinary business stuff like
writing things to files. Do you plan to run a climate model with your
code?
In article <1137496626.362209.64220
@f14g2000cwb.googlegroups.com>, ··········@hotmail.com says...
> Life could be easier for you if you would listen to Pascal. He is a
> very experienced Common Lisp user.
>
> Do not play childish and listen. Nobody awaits your outcome with Common
> Lisp. There are better coders alive.
Another asshole.
Majorinc, Kazimir <·······@chem.pmf.hr> writes:
>
> In article <···············@individual.net>, ··@p-cos.net
> says...
>
>
> >
> > Your code is very non-idiomatic. Two important things:
>
> Ouch.
>
> >
> > - Your use of set is highly unusual. The ANSI CL specification states
> > that set is a deprecated operator, and there are good reasons for this.
> > Foremostly, set exclusivly operates on global variables, doesn't keep
> > the local contexts of different functions separated, and is probably
> > very inefficient.
>
> So what? It is still in standard, and I like it more than setq
> and setf, because I prefer functions to macros and special
> operators - if possible.
Why? You don't seem to mind using the PUSH macro. What possible reason
could you have to not want to use standard macros and special operators?
> Is it completely out of base? Of
> course it is not, it is just another opinion, and you failed to
> _clearly_ demonstrate that it is wrong.
Of course it is. You just don't understand the language well enough to
realize that. That makes your arrogance doubly annoying.
Well, let's see:
Global variables were mentioned.
Lack of local context was mentioned.
The fact that the standard deprecates it's use was mentioned.
Efficiency
These are all well-founded TECHNICAL grounds for avoiding the use of SET
in most lisp code. It, like EVAL, has a few places where it would be
the right thing to use, but this is definitely not one of them. You
should use LET and lexical variables instead of special variables. This
is certainly clear enough to most technical readers of this newsgroup.
As for efficiency, accessing global (special) variables is what is
claimed to be bad, since they have to be handled properly for their
specialness to be preserved. Local variables can be easily put into
registers by the compiler.
Perhaps you should not be so quick to disparage the opinions of Lisp
practioners with many years of experience. But I suppose that is really
only necessary if you were interested in actually learning something.
> Ad hoc claim "set is probably very inefficient" is strange to
> me; in fact, it is wrong - at least in Clisp.
>
> [13]> (time (dotimes (i 1000000)))
> Real time: 0.8125 sec.
> Run time: 0.8125 sec.
> Space: 728 Bytes
> NIL
> --------------------
> [14]> (time (dotimes (i 1000000)(setq x 100)))
> Real time: 1.0 sec.
> Run time: 1.0 sec.
> Space: 736 Bytes
> NIL
> -------------------
> [11]> (setf y (quote x))
> X
> [12]> (time (dotimes (i 1000000)(set y 100)))
> Real time: 1.015625 sec.
> Run time: 1.015625 sec.
> Space: 736 Bytes
> NIL
> --------------------
> [5]> (time (dotimes (i 1000000)(set 'x 100)))
> Real time: 1.078125 sec.
> Run time: 1.078125 sec.
> Space: 736 Bytes
> NIL
> ---------------------
> [4]> (time (dotimes (i 1000000)(setf x 100)))
> Real time: 1.875 sec.
> Run time: 1.875 sec.
> Space: 40000756 Bytes
> GC: 76, GC time: 0.1875 sec.
> NIL
Perhaps if you used compiled functions, your timing would actually have
some relevance to this discussion. Timing uncompiled code does not
produce any useful information. I would also expect that if you
compiled things, any decent lisp implementation would generate
equivalent code for (SETQ X ...) and (SETF X ...) and a good one would
even generate the equivalent code for (SET 'X ...). But that still
misses the point about using lexical variables.
Not only that, but your test always uses global variables, so you miss
out entirely on the scope limitation and compilation benefits of using
lexical variables. I'll bet if you tested that you would see a
difference.
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas A. Russ schrieb:
> These are all well-founded TECHNICAL grounds for avoiding the use of SET
> in most lisp code. It, like EVAL, has a few places where it would be
> the right thing to use, but this is definitely not one of them.
Do you have some examples or usage patterns at hand where SET is used
in the right place?
André
--
"=?iso-8859-1?q?Andr=E9_Thieme?=" <······························@justmail.de> writes:
>
> Thomas A. Russ schrieb:
>
> > These are all well-founded TECHNICAL grounds for avoiding the use of SET
> > in most lisp code. It, like EVAL, has a few places where it would be
> > the right thing to use, but this is definitely not one of them.
>
> Do you have some examples or usage patterns at hand where SET is used
> in the right place?
Actually, not off-hand. I'm not really sure that I've ever used it,
although if you were writing your own interpreter it could come in
handy. The only place where using SET buys you anything is when you
want to assign values to a variable whose name you don't know at compile
time. Unless you are doing some sort of language I don't see much call
for that.
Oh, wait. I can actually think of a situation where one might use it,
although it may be a bit contrived and certainly doesn't require this
approach. If one wanted to have some type of interface, say for setting
program options, that is driven by a declarative representation, you
could perhaps do something like:
(defparameter *options-list* '((*process-carefully* :boolean t)
(*maximum-time-seconds* :integer 600)
...))
(defun set-options-dialog (options-list)
(loop for (var type default)
do (set var (get-option var type default))))
And then have the GET-OPTION do some appropriate prompt and value
checking for a variable. This would involve using SYMBOL-VALUE as
well as SET.
--
Thomas A. Russ, USC/Information Sciences Institute
In article <···············@sevak.isi.edu>,
Thomas A. Russ <···@sevak.isi.edu> wrote:
> And then have the GET-OPTION do some appropriate prompt and value
> checking for a variable. This would involve using SYMBOL-VALUE as
> well as SET.
Yeah, but you can (setf (symbol-value symbol) value), which is why
SET is deprecated. :)
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
"Andr� Thieme" <······························@justmail.de> writes:
> Thomas A. Russ schrieb:
>
>> These are all well-founded TECHNICAL grounds for avoiding the use of SET
>> in most lisp code. It, like EVAL, has a few places where it would be
>> the right thing to use, but this is definitely not one of them.
>
> Do you have some examples or usage patterns at hand where SET is used
> in the right place?
Yes. In the implementation of the SETF expander for SYMBOL-VALUE. And
that's the only place.
-Peter
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
Majorinc, Kazimir <·····@email.com> writes:
> Yesterday I wrote small function that resembles data processing I need
> for a benchmark. Here is the program.
>
> (defun test (n)
> (set 'list-of-nodes ())
> (dotimes (j n)
> (time (progn
> (dotimes (i 10000)
> (push (set 'new-node (list () ())) list-of-nodes)
> (push (set 'random-old-node
> (nth (if (= i j 0)
> 0
> (random (+ (* j 10000) i))
> )
> list-of-nodes
> )
> )
> (cadr new-node)
> )
> (push new-node (cdr random-old-node))
> )
> (print (* 10000 (1+ j)))
> )
> )
> )
> )
Look how this is nicer:
(defun test (n)
(let ((list-of-nodes '()))
(dotimes (j n)
(time (dotimes (i 10000 (print (* 10000 (1+ j))))
(let ((new-node (list '() '())))
(push new-node list-of-nodes)
(let ((random-old-node (nth (if (= i j 0)
0
(random (+ (* j 10000) i)))
list-of-nodes)))
(push random-old-node (cadr new-node))
(push new-node (cdr random-old-node)))))))))
In addition to Pascal Constanza's comments, what do you hope to learn
by doing:
(time
(let ((list '#1=(#1# . #1#))) ; (ignore this line for now)
(dotimes (random 10000) (setf list (cdr list)))))
?
You'll just get random times!
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush
Majorinc, Kazimir wrote:
> Yesterday I wrote small function that resembles data processing I need
> for a benchmark. Here is the program.
>
> (defun test (n)
> (set 'list-of-nodes ())
> (dotimes (j n)
> (time (progn
> (dotimes (i 10000)
> (push (set 'new-node (list () ())) list-of-nodes)
> (push (set 'random-old-node
> (nth (if (= i j 0)
> 0
> (random (+ (* j 10000) i))
> )
> list-of-nodes
> )
> )
> (cadr new-node)
> )
> (push new-node (cdr random-old-node))
> )
> (print (* 10000 (1+ j)))
> )
> )
> )
> )
;; Changes:
;;
;; 1. Use a more appropriate data structure.
;; 2. Keep the list of nodes in reverse order to facilitate
;; adding nodes.
;; 3. Don't use global variables everywhere; it slows things
;; down unnecessarily.
;; 4. Don't use SET; it doesn't work with local variables,
;; and typically slows things down with global ones.
;; 5. Choose the random element in a more perspicuous (and
;; more likely to be what was actually intended) way.
;; 6. Use SECOND rather than CADR, for clarity.
;; 7. Compile the code.
(defun test (n)
(let ((nodes (make-array 0 :adjustable t :fill-pointer t)))
(dotimes (iteration n)
(time
(dotimes (i 10000)
(let ((new-node (list () ())))
(vector-push-extend new-node nodes)
(let ((random-node (aref nodes (random (length nodes)))))
(push random-node (second new-node)))))))))
(compile 'test)
(test 10)
; Evaluation took:
; 0.01 seconds of real time
; 0.003791 seconds of user run time
; 0.0 seconds of system run time
; 8,026,180 CPU cycles
; 0 page faults and
; 371,432 bytes consed.
;
; Evaluation took:
; 0.0 seconds of real time
; 0.004 seconds of user run time
; 0.0 seconds of system run time
; 7,993,124 CPU cycles
; 0 page faults and
; 371,096 bytes consed.
;
[7 similar results elided]
; Evaluation took:
; 0.0 seconds of real time
; 0.002996 seconds of user run time
; 0.0 seconds of system run time
; 7,425,040 CPU cycles
; 0 page faults and
; 240,000 bytes consed.
;
That was CMU CL. Here's CLISP:
Real time: 0.008774 sec.
Run time: 0.008767 sec.
Space: 371096 Bytes
Real time: 0.02263 sec.
Run time: 0.015536 sec.
Space: 371080 Bytes
GC: 1, GC time: 0.006753 sec.
Real time: 0.027598 sec.
Run time: 0.020337 sec.
Space: 240000 Bytes
GC: 1, GC time: 0.011689 sec.
Real time: 0.050022 sec.
Run time: 0.04205 sec.
Space: 502152 Bytes
GC: 1, GC time: 0.032883 sec.
Real time: 0.008864 sec.
Run time: 0.008865 sec.
Space: 240000 Bytes
Real time: 0.015536 sec.
Run time: 0.008934 sec.
Space: 240000 Bytes
Real time: 0.025553 sec.
Run time: 0.019083 sec.
Space: 764296 Bytes
GC: 1, GC time: 0.009331 sec.
Real time: 0.023966 sec.
Run time: 0.023898 sec.
Space: 240000 Bytes
GC: 1, GC time: 0.01487 sec.
Real time: 0.009145 sec.
Run time: 0.008918 sec.
Space: 240000 Bytes
Real time: 0.009905 sec.
Run time: 0.00911 sec.
Space: 240000 Bytes
Speedup factor using CLISP: approximately 30 for the first
iteration, increasing to approximately 400 for the last.
Extra speedup factor using a Lisp that compiles to native code:
another factor of 3.
Moral: benchmarking code that no one would ever want to run
is pointless.
--
Gareth McCaughan
.sig under construc
I wrote:
> Speedup factor using CLISP: approximately 30 for the first
> iteration, increasing to approximately 400 for the last.
>
> Extra speedup factor using a Lisp that compiles to native code:
> another factor of 3.
>
> Moral: benchmarking code that no one would ever want to run
> is pointless.
Another moral: comparing timings on two different machines
is stupid, especially when one of them isn't described.
I beg your pardon. My box is an Athlon 64 3200+ running
in 32-bit mode; it's probably comparable in speed to your
P4 at 3.4GHz. Running your TEST function under CLISP,
I found that (compiled or interpreted) the code ran at
about the same speed as yours at first, and quite a bit
slower later on. I think the P4 has rather better memory
bandwidth for "streamy" code than the Athlon 64, which
might explain that. The difference between compiled and
interpreted code is small for your TEST because almost
all the time is spent in NTH.
--
Gareth McCaughan
.sig under construc
In article <··············@g.mccaughan.ntlworld.com>,
················@pobox.com says...
> I wrote:
>
> > Speedup factor using CLISP: approximately 30 for the first
> > iteration, increasing to approximately 400 for the last.
> >
> > Extra speedup factor using a Lisp that compiles to native code:
> > another factor of 3.
> >
> > Moral: benchmarking code that no one would ever want to run
> > is pointless.
>
> Another moral: comparing timings on two different machines
> is stupid, especially when one of them isn't described.
> I beg your pardon.
For god sake, if you did not used bullshit communication in
your last post, you wouldn't need to explain here because there
is nothing to explain.
But tell me one thing. Your program is faster, however, I
expect that time also depends quadratically on n. Is it right?
Kazimir Majorinc wrote:
> For god sake, if you did not used bullshit communication in
> your last post, you wouldn't need to explain here because there
> is nothing to explain.
What "bullshit communication" did I use, please?
You claimed that the following is bullshit:
| Moral: benchmarking code that no one would ever want to run
| is pointless.
But it isn't bullshit. It is (like most things anyone
says in contexts where they don't want to bore listeners
or readers senseless) slightly simplified. Here is the
expanded version:
| Moral: benchmarking code that is uncharacteristic of
| anything anyone would ever want to run is pointless,
| unless it simplifies and clarifies the measurement of
| some specific facet of performance that is relevant
| in more realistic code.
So, for instance, a dumb recursive Fibonacci number
benchmark has some value as a measure of your implementation's
function call overhead (maybe), so it might be worth doing
even though it's not the way you'd ever choose to calculate
Fibonacci numbers.
There are probably still exceptions. Be that as it may,
your code is not one of them. It isn't a tightly focused
microbenchmark that sacrifices realism for the sake of
illuminating one aspect of performance. (It does, in fact,
serve pretty well as a benchmark for the NTH function,
but if that was the real aim you could have made it much
simpler.) It has all the untidiness of real-life code
while not being the sort of code anyone should be using
in real life. As a benchmark, it combines the worst of both
worlds.
> But tell me one thing. Your program is faster, however, I
> expect that time also depends quadratically on n. Is it right?
No, it is wrong, as you could have discovered yourself
in two minutes by trying it.
I removed the internal call to TIME, to reduce verbosity,
and ran my version of the program as follows:
(defun time-several ()
(loop for i upfrom 10 to 50 by 10 do (gc :full t) (time (test i))))
(Always doing a GC first reduces the variance and,
if anything, tends to increase the extent to which
running more iterations makes the test take longer.
In other words, it isn't going to make the results
look linear if they're really quadratic.)
Here are the results of doing that several times; each row
reports on one run of the above, with times in elapsed seconds
on my machine. The implementation is CMU CL. The TIME-SEVERAL
function was compiled, though that should make very little
difference. Using (say) the "user run time" figure instead
of elapsed time makes very little difference, too.
0.04 0.08 0.13 0.25 0.30
0.04 0.08 0.15 0.25 0.28
0.05 0.08 0.13 0.25 0.29
0.04 0.08 0.14 0.25 0.29
That's about as linear as anyone could hope for.
--
Gareth McCaughan
.sig under construc
In article <··············@g.mccaughan.ntlworld.com>,
················@pobox.com says...
>
> 0.04 0.08 0.13 0.25 0.30
> 0.04 0.08 0.15 0.25 0.28
> 0.05 0.08 0.13 0.25 0.29
> 0.04 0.08 0.14 0.25 0.29
>
> That's about as linear as anyone could hope for.
>
Aha, I looked closer to the program. If memory is not
fragmented, as it is the case here then vector-push-extend does
not need to displace array, so one call requires constant time
and whole test is linear. Right?
Thenx.
Kazimir Majorinc wrote:
[me:]
>> That's about as linear as anyone could hope for.
[Kazimir:]
> Aha, I looked closer to the program. If memory is not
> fragmented, as it is the case here then vector-push-extend does
> not need to displace array, so one call requires constant time
> and whole test is linear. Right?
That might sometimes apply. But, even if there is so much
fragmentation that the array needs to be copied every time
it increases in size, linear time is still possible using
the old geometrically-increasing allocation trick: when
asked to add one element to the size of the array, you
actually multiply the size by some constant bigger than 1.
This means that the overhead from reallocation increases
at most linearly in the size the array reaches.
--
Gareth McCaughan
.sig under construc
>
> Real time: 0.008774 sec.
> Run time: 0.008767 sec.
...
> Run time: 0.00911 sec.
> Space: 240000 Bytes
>
> Speedup factor using CLISP: approximately 30 for the first
> iteration, increasing to approximately 400 for the last.
>
> Extra speedup factor using a Lisp that compiles to native code:
> another factor of 3.
Well, thank you for at least half way honest answer.
>
> Moral: benchmarking code that no one would ever want to run
> is pointless.
Ouch, again bullshit.