I often hear about people taking measures to avoid "consing". Is
consing simply allocating more memory? How do you get a feel more how
much is too much?
For example, I have a recursive function that expands lispy SQL
expressions into a tree of strings that can be printed out, a space
between each and sent to the DBMS. Running the following (after
compiling perf-test)...
(defun perf-test ()
(loop for i below 10000000
do
(sql-expand '(select (1 2)))))
(time (perf-test))
...gave me this output on SBCL
Evaluation took:
36.421 seconds of real time
35.86224 seconds of user run time
0.056004 seconds of system run time
[Run times include 1.608 seconds GC run time.]
0 calls to %EVAL
0 page faults and
2,240,000,904 bytes consed.
That seems like a lot of consing but I don't really know. If it is,
how does one go about reducing it.
Cheers,
Andy
On Sep 6, 12:55 pm, Andy Chambers <··············@googlemail.com>
wrote:
> I often hear about people taking measures to avoid "consing". Is
> consing simply allocating more memory?
Yes.
> How do you get a feel for how much is too much?
It all depends on the situation. Consing in an inner loop of a
compute-bound application could be a problem. In most other cases it
probably isn't. It comes down to what fraction of its time the
application spends consing and collecting the resulting garbage. What
is acceptable will depend on the type of application, but broadly
speaking, I'd say that if the app is spending more than half its time
doing these things, the consing probably deserves a little attention.
For some classes of app the goal might be 20%; for others, 75% or even
more might be acceptable (it's not worth optimizing a program that
will only be run rarely).
Minimizing consing is an old habit that people picked up in the days
when machines were much slower, main memories were much smaller, and
garbage collectors were less sophisticated. While there certainly
still are occasions when it matters, I think on the whole that the
topic receives more attention than it deserves these days.
-- Scott
Andy Chambers wrote:
> I often hear about people taking measures to avoid "consing". Is
> consing simply allocating more memory? How do you get a feel more how
> much is too much?
What you have to watch out for is an exponential explosion because one
has a recursive deal in a super heavy hitter computation such that what
looks like a small amount of consing actually gets kicked off a
kabillion times.
In your test you have (I think) done an unrealistic number of expansions
given that the subject is I/O.
>
> For example, I have a recursive function that expands lispy SQL
> expressions into a tree of strings that can be printed out, a space
> between each and sent to the DBMS. Running the following (after
> compiling perf-test)...
>
> (defun perf-test ()
> (loop for i below 10000000
> do
> (sql-expand '(select (1 2)))))
Step 1: Change that to be a typical real-world query.
Step 2: Time 10k expansions.
Step 3: Time 10k actually doing the I/O. This number may be
unrealistically low if the DBMS does some fancy cacheing, but I expect
the number will dwarf the first number anyway.
Step 4: Compare and contrast.
Bottom-line: relax. There is nothing special about consing to worry
about, except the heavy-hitter scenario I outlined first. As always with
performance concerns, what matters is real-world sloth, and where that
comes from can be surprising so do not overthink it while coding.
kt
Kenny wrote:
> Andy Chambers wrote:
>
>> I often hear about people taking measures to avoid "consing". Is
>> consing simply allocating more memory? How do you get a feel more how
>> much is too much?
>
>
> What you have to watch out for is an exponential explosion because one
> has a recursive deal in a super heavy hitter computation such that what
> looks like a small amount of consing actually gets kicked off a
> kabillion times.
>
> In your test you have (I think) done an unrealistic number of expansions
> given that the subject is I/O.
>
>>
>> For example, I have a recursive function that expands lispy SQL
>> expressions into a tree of strings that can be printed out, a space
>> between each and sent to the DBMS. Running the following (after
>> compiling perf-test)...
>>
>> (defun perf-test ()
>> (loop for i below 10000000
>> do
>> (sql-expand '(select (1 2)))))
>
>
> Step 1: Change that to be a typical real-world query.
> Step 2: Time 10k expansions.
> Step 3: Time 10k actually doing the I/O
.../and/ doing something entertaining with the data thus obtained...
kt
. This number may be
> unrealistically low if the DBMS does some fancy cacheing, but I expect
> the number will dwarf the first number anyway.
> Step 4: Compare and contrast.
>
> Bottom-line: relax. There is nothing special about consing to worry
> about, except the heavy-hitter scenario I outlined first. As always with
> performance concerns, what matters is real-world sloth, and where that
> comes from can be surprising so do not overthink it while coding.
>
> kt
Andy Chambers <··············@googlemail.com> writes:
> I often hear about people taking measures to avoid "consing". Is
> consing simply allocating more memory? How do you get a feel more how
> much is too much?
>
> For example, I have a recursive function that expands lispy SQL
> expressions into a tree of strings that can be printed out, a space
> between each and sent to the DBMS. Running the following (after
> compiling perf-test)...
>
> (defun perf-test ()
> (loop for i below 10000000
> do
> (sql-expand '(select (1 2)))))
>
> (time (perf-test))
>
> ...gave me this output on SBCL
>
> Evaluation took:
> 36.421 seconds of real time
> 35.86224 seconds of user run time
> 0.056004 seconds of system run time
> [Run times include 1.608 seconds GC run time.]
> 0 calls to %EVAL
> 0 page faults and
> 2,240,000,904 bytes consed.
>
> That seems like a lot of consing but I don't really know. If it is,
> how does one go about reducing it.
(truncate 2240000904 10000000) --> 224 bytes. This doesn't seem too
much to expand a SQL expression. It's about only 28 cons cells.
What are you complaining about?
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Do not adjust your mind, there is a fault in reality"
-- on a wall many years ago in Oxford.
In article <··············@hubble.informatimago.com>,
···@informatimago.com (Pascal J. Bourguignon) wrote:
> Andy Chambers <··············@googlemail.com> writes:
>
> > I often hear about people taking measures to avoid "consing". Is
> > consing simply allocating more memory? How do you get a feel more how
> > much is too much?
> >
> > For example, I have a recursive function that expands lispy SQL
> > expressions into a tree of strings that can be printed out, a space
> > between each and sent to the DBMS. Running the following (after
> > compiling perf-test)...
> >
> > (defun perf-test ()
> > (loop for i below 10000000
> > do
> > (sql-expand '(select (1 2)))))
> >
> > (time (perf-test))
> >
> > ...gave me this output on SBCL
> >
> > Evaluation took:
> > 36.421 seconds of real time
> > 35.86224 seconds of user run time
> > 0.056004 seconds of system run time
> > [Run times include 1.608 seconds GC run time.]
> > 0 calls to %EVAL
> > 0 page faults and
> > 2,240,000,904 bytes consed.
> >
> > That seems like a lot of consing but I don't really know. If it is,
> > how does one go about reducing it.
>
>
> (truncate 2240000904 10000000) --> 224 bytes. This doesn't seem too
> much to expand a SQL expression. It's about only 28 cons cells.
> What are you complaining about?
-> The 2GB consed in his example. If an application
would do n of these expansions (don't know what
his application does) then it conses n times 224 bytes.
--
http://lispm.dyndns.org/
Rainer Joswig wrote:
> In article <··············@hubble.informatimago.com>,
> ···@informatimago.com (Pascal J. Bourguignon) wrote:
>
>
>>Andy Chambers <··············@googlemail.com> writes:
>>
>>
>>>I often hear about people taking measures to avoid "consing". Is
>>>consing simply allocating more memory? How do you get a feel more how
>>>much is too much?
>>>
>>>For example, I have a recursive function that expands lispy SQL
>>>expressions into a tree of strings that can be printed out, a space
>>>between each and sent to the DBMS. Running the following (after
>>>compiling perf-test)...
>>>
>>>(defun perf-test ()
>>> (loop for i below 10000000
>>> do
>>> (sql-expand '(select (1 2)))))
>>>
>>>(time (perf-test))
>>>
>>>...gave me this output on SBCL
>>>
>>>Evaluation took:
>>> 36.421 seconds of real time
>>> 35.86224 seconds of user run time
>>> 0.056004 seconds of system run time
>>> [Run times include 1.608 seconds GC run time.]
>>> 0 calls to %EVAL
>>> 0 page faults and
>>> 2,240,000,904 bytes consed.
>>>
>>>That seems like a lot of consing but I don't really know. If it is,
>>>how does one go about reducing it.
>>
>>
>>(truncate 2240000904 10000000) --> 224 bytes. This doesn't seem too
>>much to expand a SQL expression. It's about only 28 cons cells.
>>What are you complaining about?
>
>
> -> The 2GB consed in his example. If an application
> would do n of these expansions (don't know what
> his application does) then it conses n times 224 bytes.
>
Well if his application sends ten million queries to the DBMS I wager
224 bytes each (deftly handled I wager because of the tight loop and
short life time) will be the last of his performance worries.
kt
P� Sat, 06 Sep 2008 21:55:30 +0200, skrev Andy Chambers
<··············@googlemail.com>:
> I often hear about people taking measures to avoid "consing". Is
> consing simply allocating more memory? How do you get a feel more how
> much is too much?
>
> For example, I have a recursive function that expands lispy SQL
> expressions into a tree of strings that can be printed out, a space
> between each and sent to the DBMS. Running the following (after
> compiling perf-test)...
>
> (defun perf-test ()
> (loop for i below 10000000
> do
> (sql-expand '(select (1 2)))))
>
> (time (perf-test))
>
> ...gave me this output on SBCL
>
> Evaluation took:
> 36.421 seconds of real time
> 35.86224 seconds of user run time
> 0.056004 seconds of system run time
> [Run times include 1.608 seconds GC run time.]
> 0 calls to %EVAL
> 0 page faults and
> 2,240,000,904 bytes consed.
>
> That seems like a lot of consing but I don't really know. If it is,
> how does one go about reducing it.
>
> Cheers,
> Andy
Looks like a lot to me. That is about 2.2 Kb pr iteration.
I can't say why since you haven't provided the code for select.
In general map and friends work on the entire list and return a new list.
If you are not interested in the original list you might want to work
destructively on the list.
Classic example.
(let (result)
(dolist (e list (reverse result))
(push (process e) result))
The problem here is that result is in the opposite order and in order to
get things right you have to reverse it. But reverse returns a copy of the
list result. In this case it is better to use nreverse as it re-uses the
cons cells. In general it is better to reuse IF it doesn't produce side
effects on the data sent to the function.
Another example:
(reduce #'+ number-list)
This calls it self recursively on each pair of elements and then on the
result of the adding until all elements are merged.
So you create a lot of temporary data.
Instead you could write (loop for e in number-list summing e) which
creates much less temporary data.
Yet another example:
(defun xxx ()
(list a b c d))
(let ((x (xxx))
(let ((a (first x)) (b (second x)) (c (third x)) (d (fourth x)))
...
Creates a list and returns the values. If you are only interested in the
values you can use
(defun xxx ()
(values a b c d))
(multiple-value-bind (a b c d) (xxx)
....
This allocates the values on the stack rather than on the heap wich is
faster.
For all processors accessing registers and stack is much faster than
having to access memory so operations that can be done in registers
without temporary storing them in memory should be preferred. An intro
into assembler programming might help you grasp the efficiency model.
(disassemble 'function) allows you to see the assembly code the compiler
generated.
In general you kinda have to know how the Lisp functions work to see how
much waste they create.
If you are willing to use a bit of money "Paradigms in AI programming" by
Peter Norvig has a couple of chapters on optimizing Lisp programs.
--------------
John Thingstad
John Thingstad <·······@online.no> wrote:
+---------------
| skrev Andy Chambers <··············@googlemail.com>:
| > (loop for i below 10000000
...
| > Evaluation took:
...
| > 2,240,000,904 bytes consed.
...
| Looks like a lot to me. That is about 2.2 Kb pr iteration.
+---------------
You slipped a decimal point. It's only 224 bytes/iteration.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Sep 6, 5:39 pm, "John Thingstad" <·······@online.no> wrote:
> (reduce #'+ number-list)
>
> This calls it self recursively on each pair of elements and then on the
> result of the adding until all elements are merged.
> So you create a lot of temporary data.
> Instead you could write (loop for e in number-list summing e) which
> creates much less temporary data.
Yeah, a shame CL doesn't enforce tail-calls optimization.
namekuseijin escribi�:
> On Sep 6, 5:39 pm, "John Thingstad" <·······@online.no> wrote:
>> (reduce #'+ number-list)
>>
>> This calls it self recursively on each pair of elements and then on the
>> result of the adding until all elements are merged.
>> So you create a lot of temporary data.
>> Instead you could write (loop for e in number-list summing e) which
>> creates much less temporary data.
>
> Yeah, a shame CL doesn't enforce tail-calls optimization.
Why "shame"? Shouldn't that be "pity" at most? But even so, please take
note that we hate the word "enforce".
Leandro
On 8 set, 20:04, Leandro Rios <··················@gmail.com> wrote:
> namekuseijin escribió:
> > On Sep 6, 5:39 pm, "John Thingstad" <·······@online.no> wrote:
> >> This calls it self recursively on each pair of elements and then on the
> >> result of the adding until all elements are merged.
> >> So you create a lot of temporary data.
> >> Instead you could write (loop for e in number-list summing e) which
> >> creates much less temporary data.
>
> > Yeah, a shame CL doesn't enforce tail-calls optimization.
>
> Why "shame"? Shouldn't that be "pity" at most?
No, see below.
> But even so, please take
> note that we hate the word "enforce".
And yet, you enforce an imperative paradigm by making it difficult to
achieve unrestricted recursion and, thus, programming with Higher-
Order function and function composition.
namekuseijin wrote:
> On 8 set, 20:04, Leandro Rios <··················@gmail.com> wrote:
>
>>namekuseijin escribi�:
>>
>>>On Sep 6, 5:39 pm, "John Thingstad" <·······@online.no> wrote:
>>>
>>>>This calls it self recursively on each pair of elements and then on the
>>>>result of the adding until all elements are merged.
>>>>So you create a lot of temporary data.
>>>>Instead you could write (loop for e in number-list summing e) which
>>>>creates much less temporary data.
>>
>>>Yeah, a shame CL doesn't enforce tail-calls optimization.
>>
>>Why "shame"? Shouldn't that be "pity" at most?
>
>
> No, see below.
>
>
>>But even so, please take
>>note that we hate the word "enforce".
>
>
> And yet, you enforce an imperative paradigm by making it difficult to
> achieve unrestricted recursion and, thus, programming with Higher-
> Order function and function composition.
Why stop there? A few more leaps and you'll have missing tail-call
optimization as the second shooter on the grassy knoll.
hth, kt
namekuseijin wrote:
> On 8 set, 20:04, Leandro Rios <··················@gmail.com> wrote:
>> namekuseijin escribi�:
>>> On Sep 6, 5:39 pm, "John Thingstad" <·······@online.no> wrote:
>>>> This calls it self recursively on each pair of elements and then on the
>>>> result of the adding until all elements are merged.
>>>> So you create a lot of temporary data.
>>>> Instead you could write (loop for e in number-list summing e) which
>>>> creates much less temporary data.
>>> Yeah, a shame CL doesn't enforce tail-calls optimization.
>> Why "shame"? Shouldn't that be "pity" at most?
>
> No, see below.
>
>> But even so, please take
>> note that we hate the word "enforce".
>
> And yet, you enforce an imperative paradigm by making it difficult to
> achieve unrestricted recursion and, thus, programming with Higher-
> Order function and function composition.
Most (all?) CL implementations provide a way to switch TCO on.
Few (no?) Scheme implementations provide a way to switch TCO off.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Sep 9, 4:52 am, Pascal Costanza <····@p-cos.net> wrote:
> Most (all?) CL implementations provide a way to switch TCO on.
Why not on by default?
> Few (no?) Scheme implementations provide a way to switch TCO off.
Why would anyone want to do that?
P� Tue, 09 Sep 2008 17:28:57 +0200, skrev namekuseijin
<············@gmail.com>:
> On Sep 9, 4:52�am, Pascal Costanza <····@p-cos.net> wrote:
>> Most (all?) CL implementations provide a way to switch TCO on.
>
> Why not on by default?
>
It is on by default on almost all compilers.
You have to set debug to 3 to turn it off.
>> Few (no?) Scheme implementations provide a way to switch TCO off.
>
> Why would anyone want to do that?
To help in debugging.
--------------
John Thingstad
On Sep 9, 12:55 pm, "John Thingstad" <·······@online.no> wrote:
> På Tue, 09 Sep 2008 17:28:57 +0200, skrev namekuseijin
> <············@gmail.com>:
> > On Sep 9, 4:52 am, Pascal Costanza <····@p-cos.net> wrote:
> >> Few (no?) Scheme implementations provide a way to switch TCO off.
>
> > Why would anyone want to do that?
>
> To help in debugging.
Crashing a loop by introducing an artificial limitation (no tco) that
wasn't there in the first place will help in debugging what? The
crash?
namekuseijin <············@gmail.com> writes:
> On Sep 9, 12:55��pm, "John Thingstad" <·······@online.no> wrote:
> > P�� Tue, 09 Sep 2008 17:28:57 +0200, skrev namekuseijin ��
> > <············@gmail.com>:
> > > On Sep 9, 4:52��am, Pascal Costanza <····@p-cos.net> wrote:
> > >> Few (no?) Scheme implementations provide a way to switch TCO off.
> >
> > > Why would anyone want to do that?
> >
> > To help in debugging.
>
> Crashing a loop by introducing an artificial limitation (no tco) that
> wasn't there in the first place will help in debugging what? The
> crash?
Have you ever tried debugging a recursive function when there is only
one call to it showing on the stack? You can't even use the very handy
TRACE macro to see what it's doing, since there is, be definition, only
a single function call whose arguments can be looked at.
As you gain more experience in computer science, you will learn that
having flexibility and options turns out to be a big advantage in
building large and complex systems. Focusing on one particular method
of doing things and ignoring the other options may work fine for small,
academic examples, but in real systems it gets in the way of success.
--
Thomas A. Russ, USC/Information Sciences Institute
namekuseijin wrote:
> On Sep 9, 12:55 pm, "John Thingstad" <·······@online.no> wrote:
>> P� Tue, 09 Sep 2008 17:28:57 +0200, skrev namekuseijin
>> <············@gmail.com>:
>>> On Sep 9, 4:52 am, Pascal Costanza <····@p-cos.net> wrote:
>>>> Few (no?) Scheme implementations provide a way to switch TCO off.
>>> Why would anyone want to do that?
>> To help in debugging.
>
> Crashing a loop by introducing an artificial limitation (no tco) that
> wasn't there in the first place will help in debugging what? The
> crash?
The variable bindings of all the intermediate iterations/recursions.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Sep 9, 1:48 pm, Pascal Costanza <····@p-cos.net> wrote:
> namekuseijin wrote:
> > On Sep 9, 12:55 pm, "John Thingstad" <·······@online.no> wrote:
> >> På Tue, 09 Sep 2008 17:28:57 +0200, skrev namekuseijin
> >> <············@gmail.com>:
> >>> On Sep 9, 4:52 am, Pascal Costanza <····@p-cos.net> wrote:
> >>>> Few (no?) Scheme implementations provide a way to switch TCO off.
> >>> Why would anyone want to do that?
> >> To help in debugging.
>
> > Crashing a loop by introducing an artificial limitation (no tco) that
> > wasn't there in the first place will help in debugging what? The
> > crash?
>
> The variable bindings of all the intermediate iterations/recursions.
Oh, come on! This isn't Haskell. Just put a print before returning
the parameter to the call.
On Tue, 09 Sep 2008 10:01:45 -0700, namekuseijin wrote:
> On Sep 9, 1:48 pm, Pascal Costanza <····@p-cos.net> wrote:
>> namekuseijin wrote:
>> > On Sep 9, 12:55 pm, "John Thingstad" <·······@online.no> wrote:
>> >> På Tue, 09 Sep 2008 17:28:57 +0200, skrev namekuseijin
>> >> <············@gmail.com>:
>> >>> On Sep 9, 4:52 am, Pascal Costanza <····@p-cos.net> wrote:
>> >>>> Few (no?) Scheme implementations provide a way to switch TCO off.
>> >>> Why would anyone want to do that?
>> >> To help in debugging.
>>
>> > Crashing a loop by introducing an artificial limitation (no tco) that
>> > wasn't there in the first place will help in debugging what? The
>> > crash?
>>
>> The variable bindings of all the intermediate iterations/recursions.
>
> Oh, come on! This isn't Haskell. Just put a print before returning the
> parameter to the call.
Judging by your debugging techniques, you appear to be under the
impression that you are posting to c.l.fortran.
Tamas
On Sep 9, 2:15 pm, Tamas K Papp <······@gmail.com> wrote:
> On Tue, 09 Sep 2008 10:01:45 -0700, namekuseijin wrote:
> > On Sep 9, 1:48 pm, Pascal Costanza <····@p-cos.net> wrote:
> >> namekuseijin wrote:
> >> > On Sep 9, 12:55 pm, "John Thingstad" <·······@online.no> wrote:
> >> >> På Tue, 09 Sep 2008 17:28:57 +0200, skrev namekuseijin
> >> >> <············@gmail.com>:
> >> >>> On Sep 9, 4:52 am, Pascal Costanza <····@p-cos.net> wrote:
> >> >>>> Few (no?) Scheme implementations provide a way to switch TCO off.
> >> >>> Why would anyone want to do that?
> >> >> To help in debugging.
>
> >> > Crashing a loop by introducing an artificial limitation (no tco) that
> >> > wasn't there in the first place will help in debugging what? The
> >> > crash?
>
> >> The variable bindings of all the intermediate iterations/recursions.
>
> > Oh, come on! This isn't Haskell. Just put a print before returning the
> > parameter to the call.
>
> Judging by your debugging techniques, you appear to be under the
> impression that you are posting to c.l.fortran.
You guys are purposefully crashing a recursive call and looking at the
call stack for a clue! That doesn't sound any more advanced than
strategically located prints or having fun with C core dumps...
namekuseijin <············@gmail.com> writes:
> On Sep 9, 2:15 pm, Tamas K Papp <······@gmail.com> wrote:
>> On Tue, 09 Sep 2008 10:01:45 -0700, namekuseijin wrote:
>> > On Sep 9, 1:48 pm, Pascal Costanza <····@p-cos.net> wrote:
>> >> namekuseijin wrote:
>> >> > On Sep 9, 12:55 pm, "John Thingstad" <·······@online.no> wrote:
>> >> >> På Tue, 09 Sep 2008 17:28:57 +0200, skrev namekuseijin
>> >> >> <············@gmail.com>:
>> >> >>> On Sep 9, 4:52 am, Pascal Costanza <····@p-cos.net> wrote:
>> >> >>>> Few (no?) Scheme implementations provide a way to switch TCO off.
>> >> >>> Why would anyone want to do that?
>> >> >> To help in debugging.
>>
>> >> > Crashing a loop by introducing an artificial limitation (no tco) that
>> >> > wasn't there in the first place will help in debugging what? The
>> >> > crash?
>>
>> >> The variable bindings of all the intermediate iterations/recursions.
>>
>> > Oh, come on! This isn't Haskell. Just put a print before returning the
>> > parameter to the call.
>>
>> Judging by your debugging techniques, you appear to be under the
>> impression that you are posting to c.l.fortran.
>
> You guys are purposefully crashing a recursive call and looking at the
> call stack for a clue! That doesn't sound any more advanced than
> strategically located prints or having fun with C core dumps...
Surely you don't really think that without eliminating tail calls,
every recursive function is guaranteed to blow the stack.
namekuseijin wrote:
> On Sep 9, 1:48 pm, Pascal Costanza <····@p-cos.net> wrote:
>> namekuseijin wrote:
>>> On Sep 9, 12:55 pm, "John Thingstad" <·······@online.no> wrote:
>>>> P� Tue, 09 Sep 2008 17:28:57 +0200, skrev namekuseijin
>>>> <············@gmail.com>:
>>>>> On Sep 9, 4:52 am, Pascal Costanza <····@p-cos.net> wrote:
>>>>>> Few (no?) Scheme implementations provide a way to switch TCO off.
>>>>> Why would anyone want to do that?
>>>> To help in debugging.
>>> Crashing a loop by introducing an artificial limitation (no tco) that
>>> wasn't there in the first place will help in debugging what? The
>>> crash?
>> The variable bindings of all the intermediate iterations/recursions.
>
> Oh, come on! This isn't Haskell. Just put a print before returning
> the parameter to the call.
Are you really that behind wrt support from development environments?
I can interrupt a long-running recursion and then get a view of all
active stack frames, with all the variable bindings. I can edit the
variable bindings, assign new values, and restart from an arbitrary
stack frame, to explore what's going on. I can get inspectors and
browsers to view the objects stored in variable bindings, see their
classes and (if available) slots, modify any of those, and then just
continue execution.
I don't see how a print statement would give me a similar level of
convenience during debugging.
You sound like one of those static typing guys. ("I cannot imagine how
to use that myself, so I will disallow this for everyone else.")
Pascal
P.S.: It would be better if Common Lisp had a more explicit and more
reliable way of enforcing TCO. Currently, every implementation has its
own combination of safety, optimization and debug settings to get TCO. A
declaration (declare (optimize (tail-calls 3))) would be better (the
exact semantics of which are probably hairy, so there is probably a good
reason why that's not in, but still...).
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Sep 9, 10:24 am, Pascal Costanza <····@p-cos.net> wrote:
> P.S.: It would be better if Common Lisp had a more explicit and more
> reliable way of enforcing TCO.
I don't think anyone has ever picked up on this suggestion, but I'll
post it once again as I still think it's the right thing. I think
there should be a declaration that allows one to specify a set of top-
level functions that should be mutually tail-recursive; that is, any
tail-call from one function within such a set to another within the
same such set is guaranteed to be compiled tail-recursively; all other
calls would consume stack. (Ideally, this would apply to functions
declared by LABELS as well.)
This would allow one to build FSA-like structures out of functions in
the Scheme style, which is the thing that's hard to do without TCO
(and which can be quite handy), without compromising debuggability in
the normal case.
-- Scott
On Sep 9, 2:24 pm, Pascal Costanza <····@p-cos.net> wrote:
> I can interrupt a long-running recursion and then get a view of all
> active stack frames, with all the variable bindings. I can edit the
> variable bindings, assign new values, and restart from an arbitrary
> stack frame... modify any of those, and then just
> continue execution.
True. Sorry, I forgot this is CL we're talking about. The ultimate
dynamic environment for debugging crippled programs on-the-go.
On Sep 9, 8:17 pm, namekuseijin <············@gmail.com> wrote:
> True. Sorry, I forgot this is CL we're talking about. The ultimate
> dynamic environment for debugging crippled programs on-the-go.
You know, here in the real world we regard that kind of facility as a
feature. I don't know about you, but I deal with systems which really
can't be just taken down for debugging because of some problem (we try
to get maintenance outages but that typically takes months). The
single most interesting development in the last few years on these
systems is good quality, non-intrusive, dynamic debugging & tracing.
--tim
From: Tobias C. Rittweiler
Subject: Re: What is expensive about consing
Date:
Message-ID: <87iqt5nmak.fsf@freebits.de>
namekuseijin <············@gmail.com> writes:
> Oh, come on! This isn't Haskell. Just put a print before returning
> the parameter to the call.
You can do that in Haskell, too. The ignorance you showed in this thread
is obnoxiously annoying.
-T.
On Sep 9, 4:37 pm, "Tobias C. Rittweiler" <····@freebits.de.invalid>
wrote:
> namekuseijin <············@gmail.com> writes:
> > Oh, come on! This isn't Haskell. Just put a print before returning
> > the parameter to the call.
>
> You can do that in Haskell, too.
Not until very recently.
On 2008-09-09, namekuseijin <············@gmail.com> wrote:
> On 8 set, 20:04, Leandro Rios <··················@gmail.com> wrote:
>> namekuseijin escribi�:
>> > On Sep 6, 5:39 pm, "John Thingstad" <·······@online.no> wrote:
>> >> This calls it self recursively on each pair of elements and then on the �
>> >> result of the adding until all elements are merged.
>> >> So you create a lot of temporary data.
>> >> Instead you could write (loop for e in number-list summing e) which �
>> >> creates much less temporary data.
>>
>> > Yeah, a shame CL doesn't enforce tail-calls optimization.
>>
>> Why "shame"? Shouldn't that be "pity" at most?
>
> No, see below.
>
>> But even so, please take
>> note that we hate the word "enforce".
>
> And yet, you enforce an imperative paradigm by making it difficult to
> achieve unrestricted recursion and, thus, programming with Higher-
> Order function and function composition.
Tail recursion is just thinly-disguised goto.
Common Lisp provides goto in the form of GO. Using macros, you can implement
tail recursion using GO.
Search comp.lang.lisp for "argtags" and "tailprog".
With these macros, you can directly implement a design that requires tail
calls. It exhibit the right space complexity (since it really is goto)
and port across Common Lisp implementations.
On Sep 9, 8:24 pm, Kaz Kylheku <········@gmail.com> wrote:
> On 2008-09-09, namekuseijin <············@gmail.com> wrote:
>
>
>
> > On 8 set, 20:04, Leandro Rios <··················@gmail.com> wrote:
> >> namekuseijin escribió:
> >> > On Sep 6, 5:39 pm, "John Thingstad" <·······@online.no> wrote:
> >> >> This calls it self recursively on each pair of elements and then on the
> >> >> result of the adding until all elements are merged.
> >> >> So you create a lot of temporary data.
> >> >> Instead you could write (loop for e in number-list summing e) which
> >> >> creates much less temporary data.
>
> >> > Yeah, a shame CL doesn't enforce tail-calls optimization.
>
> >> Why "shame"? Shouldn't that be "pity" at most?
>
> > No, see below.
>
> >> But even so, please take
> >> note that we hate the word "enforce".
>
> > And yet, you enforce an imperative paradigm by making it difficult to
> > achieve unrestricted recursion and, thus, programming with Higher-
> > Order function and function composition.
>
> Tail recursion is just thinly-disguised goto.
>
> Common Lisp provides goto in the form of GO. Using macros, you can implement
> tail recursion using GO.
>
> Search comp.lang.lisp for "argtags" and "tailprog".
>
> With these macros, you can directly implement a design that requires tail
> calls. It exhibit the right space complexity (since it really is goto)
> and port across Common Lisp implementations.
Well. Tail recursion should work across function boundaries.
Of course, debugging a set of mutually recursive functions with tail
calls is not all that fun.
Cheers
--
Marco
On Sep 9, 3:24 pm, Kaz Kylheku <········@gmail.com> wrote:
> With these macros, you can directly implement a design that requires tail
> calls. It exhibit the right space complexity (since it really is goto)
> and port across Common Lisp implementations.
And yet more ugly syntax to the rescue. I'm sure you can even come up
with a similar reader macro to #'
Why don't you go all the way and embrace the Perl way of syntatic
shortcuts: sigils! ;)
On Sep 9, 7:24 pm, Kaz Kylheku <········@gmail.com> wrote:
> Tail recursion is just thinly-disguised goto.
I disagree. It's quite hard to write code using GOTO which is as hard
to read as code which uses extensive tail-calls. And more tempting
since it's "clean" while gotos are "dirty". When I was more active on
CLL I used to delight in posting example solutions for obvious
homework questions which made extensive use of tail calls and
functional abstraction, and were, in my opinion and by design, utterly
incomprehensible (someone is going to search for these now, and it
will turn out that they were not as bad as I remember: that's probably
because I never posted the really nasty ones).
In real production code I have taken code which relied on TCO and
changed it to use GOTO to improve readability.
--tim
On Sep 10, 4:53 am, Tim Bradshaw <··········@tfeb.org> wrote:
> In real production code I have taken code which relied on TCO and
> changed it to use GOTO to improve readability.
So, you exchanged parametrized GOTO for plain labeled GOTO for
readability? Yeah, sounds like an improvement...
On Sep 10, 5:33 pm, namekuseijin <············@gmail.com> wrote:
> So, you exchanged parametrized GOTO for plain labeled GOTO for
> readability? Yeah, sounds like an improvement...
Yes. I changed code which was in fact using GOTO all over the place
but lied about this, pretending to be "structured" by dressing up the
GOTOs as function calls, to code which was honest and clear about what
it did. That was an improvement.
(I wrote both versions of the code BTW so I'm not being rude about
anyone's code but mine).
Tim Bradshaw wrote:
> On Sep 10, 5:33 pm, namekuseijin <············@gmail.com> wrote:
>
>
>>So, you exchanged parametrized GOTO for plain labeled GOTO for
>>readability? Yeah, sounds like an improvement...
>
>
> Yes. I changed code which was in fact using GOTO all over the place
> but lied about this, pretending to be "structured" by dressing up the
> GOTOs as function calls, to code which was honest and clear about what
> it did. That was an improvement.
>
> (I wrote both versions of the code BTW so I'm not being rude about
> anyone's code but mine).
Listen, if you ever get to feeling all black helicopterish and need to
rag on someone else's code, Costanza (not the funny one) suggests you
might want to look at Cells (and I would have to agree).
hth, kzo
On Sep 24, 6:03 am, Kenny <·········@gmail.com> wrote:
> Listen, if you ever get to feeling all black helicopterish
You do realise that we have already had you abducted, and all of this
is merely a simulation we've constructed to keep you happy? In
reality you're in one of our secure units, awaiting vivisection.
Tim Bradshaw wrote:
> On Sep 24, 6:03 am, Kenny <·········@gmail.com> wrote:
>
>
>>Listen, if you ever get to feeling all black helicopterish
>
>
> You do realise that we have already had you abducted, and all of this
> is merely a simulation we've constructed to keep you happy?
I was wondering why the United States was about to elect a black President.
> In
> reality you're in one of our secure units, awaiting vivisection.
Oh. Can you pipe in a week of Anna Kournikova first?
thx, kt
On Sep 24, 6:43 pm, Kenny <·········@gmail.com> wrote:
> I was wondering why the United States was about to elect a black President.
Yeah, we made that up: in the real world it's going to be another
Clinton I'm afraid.
On the other hand, in the real world you still have investment banks
(is that a good thing?)
Tim Bradshaw wrote:
> On Sep 24, 6:43 pm, Kenny <·········@gmail.com> wrote:
>
>
>>I was wondering why the United States was about to elect a black President.
>
>
> Yeah, we made that up: in the real world it's going to be another
> Clinton I'm afraid.
>
Yawn.
Hey, that beauty queen miss congeniality candidate who /starts out/
refusing supoenas has been fun...where /do/ you get these crazy ideas?!
But fix your vocab DB, you have all the characters calling Eskimo Boy a
"snow machine" racer. (It's /snowmobile/.)
> On the other hand, in the real world you still have investment banks
> (is that a good thing?)
Ah, that,too? Shoulda known: the guy testifying that the Wall street
execs involved in the workout should still be allowed to have huge
salaries or there might be a "brain drain" of these geniuses...pass my
regards along to whoever wrote that one, Seinfeld should have material
so good.
kzo
Kenny <·········@gmail.com> wrote:
> Tim Bradshaw wrote:
> > On Sep 24, 6:03 am, Kenny <·········@gmail.com> wrote:
> >
> >
> >>Listen, if you ever get to feeling all black helicopterish
> >
> >
> > You do realise that we have already had you abducted, and all of this
> > is merely a simulation we've constructed to keep you happy?
>
> I was wondering why the United States was about to elect a black President.
>
> > In reality you're in one of our secure units, awaiting vivisection.
>
> Oh. Can you pipe in a week of Anna Kournikova first?
>
For you, Kenny? The best we can do is to have Palin do the vivisection
with a rusty hunting knife while wearing a bikini. Moose, optional.
On 24 set, 02:03, Kenny <·········@gmail.com> wrote:
> Listen, if you ever get to feeling all black helicopterish and need to
> rag on someone else's code, Costanza (not the funny one) suggests you
> might want to look at Cells (and I would have to agree).
I see. Or will see...
On Wed, 24 Sep 2008 01:03:02 -0400, Kenny <·········@gmail.com> wrote:
>Listen, if you ever get to feeling all black helicopterish
Everyone knows the 3 letter agencies all fly white helicopters.
George
On 25 sep, 07:52, George Neuner <········@comcast.net> wrote:
> On Wed, 24 Sep 2008 01:03:02 -0400, Kenny <·········@gmail.com> wrote:
> >Listen, if you ever get to feeling all black helicopterish
>
> Everyone knows the 3 letter agencies all fly white helicopters.
Which is why Tim has tfeb.org, duh.
On Sep 25, 9:17 am, "Thomas F. Burdick" <········@gmail.com> wrote:
> Which is why Tim has tfeb.org, duh.
Actually that's because, once upon a time, the Texas Farm Bureau had
TFB. Now it seems to be some wretched domain squatter, which is
annoying because I guess it must have been available at some point in
the interim (though actually my initials are TFEB so may be that is
not too bad).
Heh, I notice that you've given up on the whole ····@" mail address
though, clearly you are quailing under the might of my vast helicoper
fleet hovering over you at all times :-).
--tim
On 25 sep, 10:40, Tim Bradshaw <··········@tfeb.org> wrote:
> On Sep 25, 9:17 am, "Thomas F. Burdick" <········@gmail.com> wrote:
>
> > Which is why Tim has tfeb.org, duh.
>
> Actually that's because, once upon a time, the Texas Farm Bureau had
> TFB. Now it seems to be some wretched domain squatter, which is
> annoying because I guess it must have been available at some point in
> the interim (though actually my initials are TFEB so may be that is
> not too bad).
Wow, looks like it's been squatted since at least 2001 (according to
the wayback machine).
> Heh, I notice that you've given up on the whole ····@" mail address
> though, clearly you are quailing under the might of my vast helicoper
> fleet hovering over you at all times :-).
You may have successfully bullied Google into disallowing three-letter
usernames just to prevent me from having ···@gmail.com, but your black
helicopters disguised as French military copters don't scare me! They
are loud, though. I continue to use tfb as a login! (But yeah, for
public email it look's like it's tburdick and tfburdick for now. Had
to abandon the Berkeley account when it got so overwhelmed with spam
that it took hours just to forward mail to google.)
Hey, wait a minute ... those copters don't have spam-loaded missiles,
do they?
On Sep 26, 10:52 am, "Thomas F. Burdick" <········@gmail.com> wrote:
> Hey, wait a minute ... those copters don't have spam-loaded missiles,
> do they?
That stuff you think is spam: that *is* the helicopters.
And now for something completely different: $7E11 / 3E8 = $2,333 per
head. Per capita GDP $46,000, so about a 5% once-off tax.
On Sep 25, 6:52 am, George Neuner <········@comcast.net> wrote:
> Everyone knows the 3 letter agencies all fly white helicopters.
yeah. We don't let them have the black ones.
namekuseijin <············@gmail.com> wrote:
+---------------
| "John Thingstad" <·······@online.no> wrote:
| > (reduce #'+ number-list)
| > This calls itself recursively on each pair of elements and then on the
| > result of the adding until all elements are merged.
| > So you create a lot of temporary data.
| > Instead you could write (loop for e in number-list summing e) which
| > creates much less temporary data.
|
| Yeah, a shame CL doesn't enforce tail-calls optimization.
+---------------
In the case of REDUCE, the whole TCO thing is a red herring, IMHO.
What CL *really* needs here is just a small tweak to REDUCE, to add
one additional keyword argument, :MAX-ARITY, that permits REDUCE to
use a larger arity than 2 on the intermediate applications of the
function being REDUCEd. It might be defined this way:
Function REDUCE
Syntax:
reduce function sequence &key key from-end start end
initial-value max-arity => result
...
max-arity -- a designator for tha maximum number of arguments
to be used during each application of FUNCTION.
The default is 2 (also denoted by a NIL argument).
An argument of T denotes a value of CALL-ARGUMENTS-LIMIT.
...
And in the "Description:" section, change these two paragraphs:
REDUCE uses a binary operation, FUNCTION, to combine the elements
of sequence bounded by start and end.
The FUNCTION must accept as arguments two elements of sequence or
the results from combining those elements. The function must also
be able to accept no arguments.
to these:
REDUCE uses an N-ary (default binary) operation, FUNCTION,
to combine the elements of sequence bounded by start and end.
The FUNCTION must accept as arguments MAX-ARITY elements of
sequence or the results from combining those elements. The
function must also be able to accept any number of arguments
less than MAX-ARITY, including none.
With this change, (REDUCE #'+ NUMBER-LIST :MAX-ARITY T) could be
implemented *VERY* efficiently, and could even be coded by the
compiler to use whatever SIMD or vector (e.g., SSE2/3) instructions
were available on the platform.
Plus, it would improve improve portability, since the above is
almost as easy to type as (APPLY #'+ NUMBER-LIST), and would
thus discourage that latter, unsafe-for-portability practice.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> namekuseijin <············@gmail.com> wrote:
> +---------------
> | "John Thingstad" <·······@online.no> wrote:
> | > (reduce #'+ number-list)
> | > This calls itself recursively on each pair of elements and then on the
> | > result of the adding until all elements are merged.
> | > So you create a lot of temporary data.
> | > Instead you could write (loop for e in number-list summing e) which
> | > creates much less temporary data.
> |
> | Yeah, a shame CL doesn't enforce tail-calls optimization.
> +---------------
>
> In the case of REDUCE, the whole TCO thing is a red herring, IMHO.
>
> What CL *really* needs here is just a small tweak to REDUCE, to add
> one additional keyword argument, :MAX-ARITY, that permits REDUCE to
> use a larger arity than 2 on the intermediate applications of the
> function being REDUCEd. It might be defined this way:
No need to complexify its interface as reduce can be implemented
using a fixed amount of temp space even without TCO (my only gripe
is calling it an "optimization" is like putting an item on sale
after increasing its price). Perhaps the OP is thinking of something
like foldr in haskell?
Where tailcalls really help is in implementing a finite state machine
as a set of mutually recursive procedures (as Scott pointed out). But
even there uglier alternatives exist!
Bakul Shah <············@bitblocks.com> wrote:
+---------------
| Rob Warnock wrote:
| > What CL *really* needs here is just a small tweak to REDUCE, to add
| > one additional keyword argument, :MAX-ARITY, that permits REDUCE to
| > use a larger arity than 2 on the intermediate applications of the
| > function being REDUCEd. It might be defined this way:
|
| No need to complexify its interface as reduce can be implemented
| using a fixed amount of temp space even without TCO...
+---------------
CL:REDUCE's interface is *already* quite complex, with five ANSI-mandated
keyword args already [:KEY :FROM-END :START :END :INITIAL-VALUE]. One more
keyword would hardly be "complexifying" it.
As others have noted, in the case of #'+ if all the compiler would use
is an underlying 2-arg machine instruction (or 2-in/1-out, for RISC),
then :MAX-ARGS doesn't buy you much. But that's just the simplest case.
A :MAX-ARGS keyword might be very useful if either:
1. The compiler knew about & could use some underlying vector arithmetic,
such as x86 SSE{2,3}; or,
2. The function being REDUCE'd is both *expensive* to call and
inherently variadic [but with little incremental overhead per
additional argument]. In that case, operating on "bunches" of
args at a time could be a real performance boost. A possibly
worst-case example of this would be if each function call required
a setup/teardown of a network connection [think SQL database access],
or allocating/releasing a bunch of slave processors [Google-style
MAP/REDUCE], etc.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Sep 10, 12:12 pm, ····@rpw3.org (Rob Warnock) wrote:
> CL:REDUCE's interface is *already* quite complex, with five ANSI-mandated
> keyword args already [:KEY :FROM-END :START :END :INITIAL-VALUE]. One more
> keyword would hardly be "complexifying" it.
Nothing like cramming several different overlapping functions into a
single one with complex interface and mutually exclusive parameters
for purposes of having an industrial-strength swiss-army-knife.
namekuseijin <············@gmail.com> writes:
> On Sep 10, 12:12 pm, ····@rpw3.org (Rob Warnock) wrote:
>> CL:REDUCE's interface is *already* quite complex, with five ANSI-mandated
>> keyword args already [:KEY :FROM-END :START :END :INITIAL-VALUE]. One more
>> keyword would hardly be "complexifying" it.
>
> Nothing like cramming several different overlapping functions into a
> single one with complex interface and mutually exclusive parameters
> for purposes of having an industrial-strength swiss-army-knife.
None of those are mutually exclusive.
On Sep 10, 5:17 pm, Paul Donnelly <·············@sbcglobal.net> wrote:
> namekuseijin <············@gmail.com> writes:
> > On Sep 10, 12:12 pm, ····@rpw3.org (Rob Warnock) wrote:
> >> CL:REDUCE's interface is *already* quite complex, with five ANSI-mandated
> >> keyword args already [:KEY :FROM-END :START :END :INITIAL-VALUE]. One more
> >> keyword would hardly be "complexifying" it.
>
> > Nothing like cramming several different overlapping functions into a
> > single one with complex interface and mutually exclusive parameters
> > for purposes of having an industrial-strength swiss-army-knife.
>
> None of those are mutually exclusive.
:FROM-END :START :END look suspiciously mutually exclusive. At least,
very confusing...
namekuseijin <············@gmail.com> writes:
> On Sep 10, 5:17��pm, Paul Donnelly <·············@sbcglobal.net> wrote:
> > namekuseijin <············@gmail.com> writes:
> > > On Sep 10, 12:12��pm, ····@rpw3.org (Rob Warnock) wrote:
> > >> CL:REDUCE's interface is *already* quite complex, with five ANSI-mandated
> > >> keyword args already [:KEY :FROM-END :START :END :INITIAL-VALUE]. One more
> > >> keyword would hardly be "complexifying" it.
> >
> > > Nothing like cramming several different overlapping functions into a
> > > single one with complex interface and mutually exclusive parameters
> > > for purposes of having an industrial-strength swiss-army-knife.
> >
> > None of those are mutually exclusive.
>
> :FROM-END :START :END look suspiciously mutually exclusive. At least,
> very confusing...
Not if you actually read the specification and see what they mean. And
the confusion is greatly reduced [sorry] by the fact that :START and
:END are very common keywords for any of the sequence functions.
Furthermore, all (?) of the mapping functions and many others that
manipulate sequences take the :FROM-END argument as well.
And they are orthogonal items.
:START and :END allow you to extract a subsequence on which to operate.
:FROM-END tells you what direction to go when processing the
:(sub)sequence.
Now, of course, in a minimal language you could easily do without the
:START and :END arguments -- by just inserting an explicit SUBSEQUENCE
call -- but they are present not only for convenience, but also because
they can improve the efficiency of the code by obviating the need to
make a copy of the part of the sequence one wants to process.
--
Thomas A. Russ, USC/Information Sciences Institute
Rob Warnock wrote:
> Bakul Shah <············@bitblocks.com> wrote:
> +---------------
> | Rob Warnock wrote:
> | > What CL *really* needs here is just a small tweak to REDUCE, to add
> | > one additional keyword argument, :MAX-ARITY, that permits REDUCE to
> | > use a larger arity than 2 on the intermediate applications of the
> | > function being REDUCEd. It might be defined this way:
> |
> | No need to complexify its interface as reduce can be implemented
> | using a fixed amount of temp space even without TCO...
> +---------------
>
> CL:REDUCE's interface is *already* quite complex, with five ANSI-mandated
> keyword args already [:KEY :FROM-END :START :END :INITIAL-VALUE]. One more
> keyword would hardly be "complexifying" it.
It would be complexifying it further but never mind! I see that the
plot has been lost already. I thought (reduce #'+ number-list) was
just a wordy CL way to write +/number-array as in APL. Silly me.
Anyway, your reasons have nothing to do with tailcalls.
From: Tobias C. Rittweiler
Subject: Re: What is expensive about consing
Date:
Message-ID: <87wshk8jcb.fsf@freebits.de>
····@rpw3.org (Rob Warnock) writes:
> namekuseijin <············@gmail.com> wrote:
> +---------------
> | "John Thingstad" <·······@online.no> wrote:
> | > (reduce #'+ number-list)
> | > This calls itself recursively on each pair of elements and then on the
> | > result of the adding until all elements are merged.
> | > So you create a lot of temporary data.
> | > Instead you could write (loop for e in number-list summing e) which
> | > creates much less temporary data.
Perhaps I'm dense, but I don't see where REDUCE (when performing a left
fold) creates much more temporary data than the LOOP version. If REDUCE
is open coded, very similiar code could be generated.
And as REDUCE represents a very specific kind of iteration, it's easier
for implementators to optimize the resulting code than for a general
iteration facility like LOOP.
> With this change, (REDUCE #'+ NUMBER-LIST :MAX-ARITY T) could be
> implemented *VERY* efficiently, and could even be coded by the
> compiler to use whatever SIMD or vector (e.g., SSE2/3) instructions
> were available on the platform.
In practise, it'd probably be slower because of &rest list allocation.
-T.
P� Wed, 10 Sep 2008 11:02:12 +0200, skrev Tobias C. Rittweiler
<···@freebits.de.invalid>:
> ····@rpw3.org (Rob Warnock) writes:
>
>> namekuseijin <············@gmail.com> wrote:
>> +---------------
>> | "John Thingstad" <·······@online.no> wrote:
>> | > (reduce #'+ number-list)
>> | > This calls itself recursively on each pair of elements and then on
>> the
>> | > result of the adding until all elements are merged.
>> | > So you create a lot of temporary data.
>> | > Instead you could write (loop for e in number-list summing e) which
>> | > creates much less temporary data.
>
> Perhaps I'm dense, but I don't see where REDUCE (when performing a left
> fold) creates much more temporary data than the LOOP version. If REDUCE
> is open coded, very similiar code could be generated.
>
It COULD but on my implementation it doesn't. Optimation is about knowing
how things work, not how they could work.
Thruth is you can't rely on reduce being efficient on memory. Look at the
stack trace/disassembly and see.
There is a more efficient family of map function in the 'series' library.
It uses lazy evaluation to achieve better performance for functional
processing.
If you dislike loop and need performance it's worth a look.
> And as REDUCE represents a very specific kind of iteration, it's easier
> for implementators to optimize the resulting code than for a general
> iteration facility like LOOP.
loop reduces to a tagbody/go combo. So although some types of optimation
like loop unrolling, moving of invariant code out of loop etc. can't be
counted on, the stack use can.
--------------
John Thingstad
On Sep 9, 8:18 pm, ····@rpw3.org (Rob Warnock) wrote:
>
> With this change, (REDUCE #'+ NUMBER-LIST :MAX-ARITY T) could be
> implemented *VERY* efficiently, and could even be coded by the
> compiler to use whatever SIMD or vector (e.g., SSE2/3) instructions
> were available on the platform.
Why can't (REDUCE #'+ NUMBER-LIST) be compiled just as efficiently
now?
-- Scott
Scott Burson <········@gmail.com> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) wrote:
| > With this change, (REDUCE #'+ NUMBER-LIST :MAX-ARITY T) could be
| > implemented *VERY* efficiently, and could even be coded by the
| > compiler to use whatever SIMD or vector (e.g., SSE2/3) instructions
| > were available on the platform.
|
| Why can't (REDUCE #'+ NUMBER-LIST) be compiled just as efficiently now?
+---------------
Hmmm... You're right, it could. And, in fact, could also be for
any function whose signature is lexically apparent to the compiler.
But :MAX-ARGS might still be useful if the REDUCE call were inside
a separately-compiled routine that accepted a function argument...
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Tue, 09 Sep 2008 22:18:56 -0500, Rob Warnock wrote:
[snip alternate definition of CL:REDUCE]
>
> Plus, it would improve improve portability, since the above is
> almost as easy to type as (APPLY #'+ NUMBER-LIST), and would
> thus discourage that latter, unsafe-for-portability practice.
Hi Rob,
how is (APPLY #'+ NUMBER-LIST) unportable? To my novice eyes it looks very
elegant.
Adam
awhite <·······@iinet.net.au> writes:
> On Tue, 09 Sep 2008 22:18:56 -0500, Rob Warnock wrote:
>
> [snip alternate definition of CL:REDUCE]
>
>>
>> Plus, it would improve improve portability, since the above is
>> almost as easy to type as (APPLY #'+ NUMBER-LIST), and would
>> thus discourage that latter, unsafe-for-portability practice.
>
> Hi Rob,
>
> how is (APPLY #'+ NUMBER-LIST) unportable? To my novice eyes it looks very
> elegant.
Because of call-arguments-list. The portable form is:
(if (< (length number-list) call-arguments-limit)
(apply (function +) number-list)
(reduce (function +) number-list))
--
__Pascal Bourguignon__ http://www.informatimago.com/
ADVISORY: There is an extremely small but nonzero chance that,
through a process known as "tunneling," this product may
spontaneously disappear from its present location and reappear at
any random place in the universe, including your neighbor's
domicile. The manufacturer will not be responsible for any damages
or inconveniences that may result.
Pascal J. Bourguignon <···@informatimago.com> wrote:
+---------------
| awhite <·······@iinet.net.au> writes:
| > Rob Warnock wrote:
| >> Plus, it would improve improve portability, since the above is
| >> almost as easy to type as (APPLY #'+ NUMBER-LIST), and would
| >> thus discourage that latter, unsafe-for-portability practice.
| >
| > how is (APPLY #'+ NUMBER-LIST) unportable? To my novice eyes
| > it looks very elegant.
|
| Because of call-arguments-list. The portable form is:
|
| (if (< (length number-list) call-arguments-limit)
| (apply (function +) number-list)
| (reduce (function +) number-list))
+---------------
Yup. What Pascal said... ;-}
That's why I keep suggesting[1] that slightly-enhanced CL:REDUCE.
-Rob
[1] Well, A quick search shows that I've only suggested it about
four times (1998, 2003, 2004, 2008). Note that previously I
suggested that the new keyword be called :MAX-ARGS rather
than :MAX-ARITY -- I have no clue why I went with the latter
this time. Doing an APROPOS in CMUCL suggests that :MAX-ARGS
would probably be a better choice.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> Pascal J. Bourguignon <···@informatimago.com> wrote:
> +---------------
> | awhite <·······@iinet.net.au> writes:
> | > Rob Warnock wrote:
> | >> Plus, it would improve improve portability, since the above is
> | >> almost as easy to type as (APPLY #'+ NUMBER-LIST), and would
> | >> thus discourage that latter, unsafe-for-portability practice.
> | >
> | > how is (APPLY #'+ NUMBER-LIST) unportable? To my novice eyes
> | > it looks very elegant.
> |
> | Because of call-arguments-list. The portable form is:
> |
> | (if (< (length number-list) call-arguments-limit)
> | (apply (function +) number-list)
> | (reduce (function +) number-list))
> +---------------
>
> Yup. What Pascal said... ;-}
>
> That's why I keep suggesting[1] that slightly-enhanced CL:REDUCE.
Seems to me to be a good idea. You should write a CDR.
--
__Pascal Bourguignon__
On Wed, 10 Sep 2008 08:12:12 +0200, Pascal J. Bourguignon wrote:
[non-guaranteed CL:APPLY for arbitrarily sized lists]
> Because of call-arguments-list. The portable form is:
>
> (if (< (length number-list) call-arguments-limit)
> (apply (function +) number-list)
> (reduce (function +) number-list))
Ah, thanks. That sucks for execution speed, though! O(N) for the CL:LENGTH
operation on a list, when (depending on domain, of course), you're very
unlikely to exceed call-arguments-limit (4096 on my local CLISP) in a
single list.
But even if you take Rob's good suggestion of a :max-args keyword, is
there an efficient way of splitting variable-length lists into chunks?
You still need to traverse each cons (via ELT or similar) to chop them up.
Either way of doing it (CL:REDUCE vs split-into-c-a-l-sizes and then
CL:APPLY on each list) still seems like O(N2) performance either way.
Adam
>>>>> "awhite" == awhite <·······@iinet.net.au> writes:
awhite> On Wed, 10 Sep 2008 08:12:12 +0200, Pascal J. Bourguignon wrote:
awhite> [non-guaranteed CL:APPLY for arbitrarily sized lists]
>> Because of call-arguments-list. The portable form is:
>>
>> (if (< (length number-list) call-arguments-limit)
>> (apply (function +) number-list)
>> (reduce (function +) number-list))
awhite> Ah, thanks. That sucks for execution speed, though! O(N) for the CL:LENGTH
awhite> operation on a list, when (depending on domain, of course), you're very
awhite> unlikely to exceed call-arguments-limit (4096 on my local CLISP) in a
awhite> single list.
There are examples of people using maxima where they call apply with
lists much longer than 4096. This doesn't work very well on Clisp.
Ray
P� Wed, 10 Sep 2008 11:11:04 +0200, skrev awhite <·······@iinet.net.au>:
> On Wed, 10 Sep 2008 08:12:12 +0200, Pascal J. Bourguignon wrote:
>
> [non-guaranteed CL:APPLY for arbitrarily sized lists]
>
>> Because of call-arguments-list. The portable form is:
>>
>> (if (< (length number-list) call-arguments-limit)
>> (apply (function +) number-list)
>> (reduce (function +) number-list))
>
> Ah, thanks. That sucks for execution speed, though! O(N) for the
> CL:LENGTH
> operation on a list, when (depending on domain, of course), you're very
> unlikely to exceed call-arguments-limit (4096 on my local CLISP) in a
> single list.
>
> But even if you take Rob's good suggestion of a :max-args keyword, is
> there an efficient way of splitting variable-length lists into chunks?
> You still need to traverse each cons (via ELT or similar) to chop them
> up.
>
> Either way of doing it (CL:REDUCE vs split-into-c-a-l-sizes and then
> CL:APPLY on each list) still seems like O(N2) performance either way.
>
> Adam
Normally I do that in human RAM. According to the spec you can't rely on
call-argument-limit to be higher that 50. However the lowest limit of any
existing implementation is as far as I know 2048. If you have an idea of
how big the list is likely to be you can just choose one or the other.
--------------
John Thingstad
>>>>> "John" == John Thingstad <·······@online.no> writes:
John> Normally I do that in human RAM. According to the spec you can't rely
John> on call-argument-limit to be higher that 50. However the lowest limit
John> of any existing implementation is as far as I know 2048. If you have
John> an idea of how big the list is likely to be you can just choose one
John> or the other.
You need to try more Lisps. GCL has a limit of 64. Some googling
indicates that Lispworks has a limit of 300.
Ray
P� Wed, 10 Sep 2008 15:07:21 +0200, skrev Raymond Toy
<···········@ericsson.com>:
> You need to try more Lisps. GCL has a limit of 64. Some googling
> indicates that Lispworks has a limit of 300.
>
> Ray
Funny about GCL. That is the Lisp most people use with Maxima.
ECL has limit 65536. LispWorks limit is 2047.
(I have all Lisp's that run under Windows (GCL, ECL, CLISP, SBCL, Corman,
Allegro, LispWorks) here, but I mostly use LispWorks.)
--------------
John Thingstad
In article <···············@rtp.ericsson.se>,
Raymond Toy <···········@ericsson.com> wrote:
> >>>>> "John" == John Thingstad <·······@online.no> writes:
>
> John> Normally I do that in human RAM. According to the spec you can't rely
> John> on call-argument-limit to be higher that 50. However the lowest limit
> John> of any existing implementation is as far as I know 2048. If you have
> John> an idea of how big the list is likely to be you can just choose one
> John> or the other.
>
> You need to try more Lisps. GCL has a limit of 64. Some googling
> indicates that Lispworks has a limit of 300.
>
> Ray
I see 50 :-( .
--
http://lispm.dyndns.org/
>>>>> "Rainer" == Rainer Joswig <······@lisp.de> writes:
Rainer> In article <···············@rtp.ericsson.se>,
Rainer> Raymond Toy <···········@ericsson.com> wrote:
>> >>>>> "John" == John Thingstad <·······@online.no> writes:
>>
John> Normally I do that in human RAM. According to the spec you can't rely
John> on call-argument-limit to be higher that 50. However the lowest limit
John> of any existing implementation is as far as I know 2048. If you have
John> an idea of how big the list is likely to be you can just choose one
John> or the other.
>>
>> You need to try more Lisps. GCL has a limit of 64. Some googling
>> indicates that Lispworks has a limit of 300.
>>
>> Ray
Rainer> I see 50 :-( .
With gcl or lispworks?
Ray
In article <···············@rtp.ericsson.se>,
Raymond Toy <···········@ericsson.com> wrote:
> >>>>> "Rainer" == Rainer Joswig <······@lisp.de> writes:
>
> Rainer> In article <···············@rtp.ericsson.se>,
> Rainer> Raymond Toy <···········@ericsson.com> wrote:
>
> >> >>>>> "John" == John Thingstad <·······@online.no> writes:
> >>
> John> Normally I do that in human RAM. According to the spec you can't rely
> John> on call-argument-limit to be higher that 50. However the lowest limit
> John> of any existing implementation is as far as I know 2048. If you have
> John> an idea of how big the list is likely to be you can just choose one
> John> or the other.
> >>
> >> You need to try more Lisps. GCL has a limit of 64. Some googling
> >> indicates that Lispworks has a limit of 300.
> >>
> >> Ray
>
> Rainer> I see 50 :-( .
>
> With gcl or lispworks?
>
> Ray
Neither.
"John Thingstad" <·······@online.no> writes:
>
> (reduce #'+ number-list)
>
> This calls it self recursively on each pair of elements and then on the
> result of the adding until all elements are merged.
> So you create a lot of temporary data.
> Instead you could write (loop for e in number-list summing e) which
> creates much less temporary data.
Shouldn't the compiler transform the one into the equivalent of the other?
--
Robert Uhl <http://public.xdi.org/=ruhl>
You see, in the post-televisual world we read. --John Gipson
* "John Thingstad" <·················@pandora.alfanett.no> :
Wrote on Sat, 06 Sep 2008 22:39:07 +0200:
|
| Another example:
|
| (reduce #'+ number-list)
|
| This calls it self recursively on each pair of elements and then on
| the result of the adding until all elements are merged. So you create
| a lot of temporary data. Instead you could write (loop for e in
| number-list summing e) which creates much less temporary data.
I did not see this being debunked clearly: this is completely false.
How did you come up with this nonsense?
--
Madhu
P� Thu, 11 Sep 2008 06:39:10 +0200, skrev Madhu <·······@meer.net>:
> * "John Thingstad" <·················@pandora.alfanett.no> :
> Wrote on Sat, 06 Sep 2008 22:39:07 +0200:
> |
> | Another example:
> |
> | (reduce #'+ number-list)
> |
> | This calls it self recursively on each pair of elements and then on
> | the result of the adding until all elements are merged. So you create
> | a lot of temporary data. Instead you could write (loop for e in
> | number-list summing e) which creates much less temporary data.
>
> I did not see this being debunked clearly: this is completely false.
> How did you come up with this nonsense?
> --
> Madhu
>
Ok perhaps that was a bad example. Implementations have gotten better and
don't use the naive approach anymore.
Ran some tests (LispWorks 5.1):
(defun test-reduce (list)
(reduce #'+ list))
(defun test-loop (list)
(loop for e in list summing e))
(defun random-data ()
(loop repeat 1000000 collect (random 1.0)))
CL-USER 3 > (progn (setf *data* (random-data)) (values))
CL-USER 8 > (time (test-reduce *data*))
Timing the evaluation of (TEST-REDUCE *DATA*)
User time = 0.796
System time = 0.000
Elapsed time = 0.812
Allocation = 8001932 bytes
0 Page faults
500029.3
CL-USER 9 > (time (test-loop *data*))
Timing the evaluation of (TEST-LOOP *DATA*)
User time = 0.796
System time = 0.000
Elapsed time = 0.813
Allocation = 8004416 bytes
0 Page faults
500029.3
So we have got similar amounts of allocation and time.
Sample implementation (CormanLisp source):
;;; ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
;;; REDUCE
;;; ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
(defun reduce (function sequence
&key (key #'identity)
from-end
(start 0)
end
(initial-value nil initial-value-present-p))
(let (length)
(multiple-value-setq (length end)
(validate-bounding-indices sequence start end))
(let* ((subseq-length (- end start))
(reduce-steps (if initial-value-present-p
subseq-length
(1- subseq-length)))
(canonical-fun (if from-end
#'(lambda (a b) (funcall function b a))
function)))
(cond ((= 0 subseq-length)
(if initial-value-present-p
initial-value
(funcall function)))
((= 1 subseq-length)
(let ((elt (elt sequence start)))
(if initial-value-present-p
(funcall canonical-fun initial-value (funcall key elt))
(funcall key elt))))
((listp sequence)
(let* ((sublist (if from-end
(nthcdr (- length end) (reverse sequence))
(nthcdr start sequence)))
(value (if initial-value-present-p
initial-value
(funcall key (pop sublist)))))
(dotimes (s reduce-steps value)
(setq value (funcall canonical-fun
value
(funcall key (pop sublist)))))))
((vectorp sequence)
(let* ((step (if from-end -1 1))
(index (if from-end (1- end) start))
(value (if initial-value-present-p
initial-value
(prog1 (funcall key (aref sequence index))
(setq index (+ index step))))))
(dotimes (s reduce-steps value)
(setq value (funcall canonical-fun
value
(funcall key (aref sequence index))))
(setq index (+ index step)))))
(t
(error "Not a sequence: ~S" sequence))))))
--------------
John Thingstad
In article
<····································@e53g2000hsa.googlegroups.com>,
Andy Chambers <··············@googlemail.com> wrote:
> I often hear about people taking measures to avoid "consing". Is
> consing simply allocating more memory? How do you get a feel more how
> much is too much?
'consing' means the creation of fresh Lisp objects (of whatever type).
If the Lisp system gives you a fresh new object then it needs to find
some space to allocate it. If there is not enough space then
it has to provide that space (doing a garbage collection,
compacting used memory, reduce fragmentation, etc.).
When it has found enough space for the new object, it has to
initialize the object before handing it over. For example
a call to MAKE-ARRAY will return an array with the contents
initialized to something (NIL for example). It will not
return objects that contain random bit patterns. Each
object created is a valid Lisp object and if it has components
(like a vector, a string, a CLOS object will have components),
these components will be something valid to the Lisp system.
In earlier years the main memory of most systems was small
compared to the Lisp system's size. For example on a Lisp Machine
of the early 80s the typical main memory was something
like 16 MB (4 MegaWords) and the size of the booted Lisp image was often
larger. The used virtual address space was even larger
(dozens or even hundreds of MB). In this setting garbage
collection often had to work over virtual memory, accessing
the disk to scan memory pages - which is slow - especially
since the disk interfaces also were slow. So a lot of clever things
were done to avoid consing, to improve the locality of
data and to avoid touching the disk during memory management.
In the last years for many applications (most of the Lisp applications
that have been written and used in the past 50 years)
there is plenty main memory and (incremental) garbage collection
in physical memory tends to be quick. Though there are
some Lisp applications that are using huge amounts
of memory (say hundred and more GB), so the problem has
shown up again for these applications. But the majority
of applications can be written without much optimization
of consing.
Still it may be useful to think about consing and understand
how to reduce it.
A typical problem is: read a file line by line, process
the line somehow and write a new file line by line.
What is the problem here? READ-LINE returns a new string
every time it is called. Since the line is processed, a new
string has to be allocated and it will be written to
the other file. So for each line of the input file,
at least two strings will be created and both will be
immediately garbage. If the input file has a lot of
lines, this will be a lot of garbage.
What would one do to get rid of that consing? One
would use a special version of READ-LINE which takes
a line buffer as an argument. This line buffer can
be reused. It will return the line in the line buffer.
Common Lisp provides adjustable arrays with a fill pointer
that can be used for this purpose.
So that means in this case that for a file of one thousand
lines, instead of consing two thousand strings, consing just two
can be enough.
>
> For example, I have a recursive function that expands lispy SQL
> expressions into a tree of strings that can be printed out, a space
> between each and sent to the DBMS. Running the following (after
> compiling perf-test)...
>
> (defun perf-test ()
> (loop for i below 10000000
> do
> (sql-expand '(select (1 2)))))
>
> (time (perf-test))
>
> ...gave me this output on SBCL
>
> Evaluation took:
> 36.421 seconds of real time
> 35.86224 seconds of user run time
> 0.056004 seconds of system run time
> [Run times include 1.608 seconds GC run time.]
> 0 calls to %EVAL
> 0 page faults and
> 2,240,000,904 bytes consed.
>
> That seems like a lot of consing but I don't really know. If it is,
> how does one go about reducing it.
Well, you created 2GB worth of Lisp objects, GC took 1.6 seconds and
there is some time included for allocation of these objects in the
36 seconds. 1.6 seconds GC time does not look much. It would
be interesting to know how much time was spend consing the
objects. For example when a GC is generational and all the allocations
and the garbage collections happened in one generation
(of some relatively small size) then all you pay for is the
consing time and the GC time. If your allocation pattern is
different, say all the 2GB memory will be allocated in one go
(like consing a large list of objects),
then I would think about reducing the amount of memory that is
used.
Your software did 10 million iterations and each iteration (assuming that
allocation is constant in this case) consed something like 200 bytes.
If there are core routines in your software, which are constantly
creating a lot of objects that are immediately garbage, this may burn
a lot of cycles on the machine and it may useful to reduce
the overall consing rate (this may also reduce power consumption
of the machine used). As I said GCs can cope with high consing
rates, but still it may be useful to avoid the consing - even
if it is only to make the GC less busy. Lisp systems typically
have to deal with the consing of a lot of small
objects that contain a lot of pointers. Since the runtimes
are optimized for this case, one can get away for a lot of
applications without much manual memory management.
>
> Cheers,
> Andy
--
http://lispm.dyndns.org/
On Sep 6, 10:51 pm, Rainer Joswig <······@lisp.de> wrote:
> a call to MAKE-ARRAY will return an array with the contents
> initialized to something (NIL for example). It will not
> return objects that contain random bit patterns.
Arrays are not always initialized, I think:
[http://www.lispworks.com/documentation/HyperSpec/Body/f_mk_ar.htm]
> If initial-element is not supplied, the consequences of later
> reading an uninitialized element of new-array are undefined unless
> either initial-contents is supplied or displaced-to is non-nil.
Carlos
In article
<····································@a70g2000hsh.googlegroups.com>,
············@gmail.com wrote:
> On Sep 6, 10:51�pm, Rainer Joswig <······@lisp.de> wrote:
> > a call to MAKE-ARRAY will return an array with the contents
> > initialized to something (NIL for example). It will not
> > return objects that contain random bit patterns.
>
> Arrays are not always initialized, I think:
> [http://www.lispworks.com/documentation/HyperSpec/Body/f_mk_ar.htm]
> > If initial-element is not supplied, the consequences of later
> > reading an uninitialized element of new-array are undefined unless
> > either initial-contents is supplied or displaced-to is non-nil.
>
> Carlos
In practice arrays elements are initialized to some Lisp value
(NIL or 0 often, or some type dependent value).
The standard also allows the
slot to be uninitialized, so that an array access
to such an unitialized array element can be detected.
That would probably mean that the array elements are set
to some internal marker that marks the element as
uninitialized. It also could be possible that
the array contains random data - but I can't remember
any implementation doing this (though that does not
mean that there isn't one, for example when safety is 0).
--
http://lispm.dyndns.org/
On Sep 7, 1:19 am, Rainer Joswig <······@lisp.de> wrote:
> It also could be possible that
> the array contains random data - but I can't remember
> any implementation doing this (though that does not
> mean that there isn't one, for example when safety is 0).
I thought I had seen that behaviour (random data in an uninitialized
double-float array) with optimized (speed 3) SBCL code. It seems I was
wrong, but it happens in AllegroCL and LispWorks (at least on MacOSX/
Intel):
(defun uninitialized-array-demo ()
(declare (optimize (speed 3)))
(let ((random-data (make-array 5 :element-type 'double-float)))
(loop for entry across random-data collect entry)))
I also found that CLISP initilizes the array to NIL, even if it is
supossed to contain numbers.
Carlos
In article
<····································@k30g2000hse.googlegroups.com>,
············@gmail.com wrote:
> On Sep 7, 1:19�am, Rainer Joswig <······@lisp.de> wrote:
> > It also could be possible that
> > the array contains random data - but I can't remember
> > any implementation doing this (though that does not
> > mean that there isn't one, for example when safety is 0).
>
> I thought I had seen that behaviour (random data in an uninitialized
> double-float array) with optimized (speed 3) SBCL code. It seems I was
> wrong, but it happens in AllegroCL and LispWorks (at least on MacOSX/
> Intel):
>
> (defun uninitialized-array-demo ()
> (declare (optimize (speed 3)))
> (let ((random-data (make-array 5 :element-type 'double-float)))
> (loop for entry across random-data collect entry)))
Interesting. Thanks for the info!
Though all array elements are returned as double-floats.
Same for LispWorks and fixnums.
>
> I also found that CLISP initilizes the array to NIL, even if it is
> supossed to contain numbers.
>
> Carlos
--
http://lispm.dyndns.org/
On Sep 7, 10:58 am, Rainer Joswig <······@lisp.de> wrote:
> In article
> <····································@k30g2000hse.googlegroups.com>,
>
>
>
> ············@gmail.com wrote:
> > On Sep 7, 1:19 am, Rainer Joswig <······@lisp.de> wrote:
> > > It also could be possible that
> > > the array contains random data - but I can't remember
> > > any implementation doing this (though that does not
> > > mean that there isn't one, for example when safety is 0).
>
> > I thought I had seen that behaviour (random data in an uninitialized
> > double-float array) with optimized (speed 3) SBCL code. It seems I was
> > wrong, but it happens in AllegroCL and LispWorks (at least on MacOSX/
> > Intel):
>
> > (defun uninitialized-array-demo ()
> > (declare (optimize (speed 3)))
> > (let ((random-data (make-array 5 :element-type 'double-float)))
> > (loop for entry across random-data collect entry)))
>
> Interesting. Thanks for the info!
>
> Though all array elements are returned as double-floats.
>
> Same for LispWorks and fixnums.
>
>
>
> > I also found that CLISP initilizes the array to NIL, even if it is
> > supossed to contain numbers.
>
> > Carlos
>
> --http://lispm.dyndns.org/
LispWorks (at least 5.1 on OS X) will also initialize bit arrays to
unpredictable values:
CL-USER 11 > (make-array 10 :element-type 'bit)
#*0000010010
CL-USER 12 > (make-array 10 :element-type 'bit)
#*0000000000
CL-USER 13 > (make-array 10 :element-type 'bit)
#*0000010001
I wouldn't be surprised if other implementations did (or didn't) do
similar things.
//JT
On Sep 7, 9:23 pm, Joshua Taylor <···········@gmail.com> wrote:
> LispWorks (at least 5.1 on OS X) will also initialize bit arrays to
> unpredictable values:
>
> CL-USER 11 > (make-array 10 :element-type 'bit)
> #*0000010010
>
> CL-USER 12 > (make-array 10 :element-type 'bit)
> #*0000000000
>
> CL-USER 13 > (make-array 10 :element-type 'bit)
> #*0000010001
>
> I wouldn't be surprised if other implementations did (or didn't) do
> similar things.
I had only tested using (declare (optimize speed)); I'm surprised this
happens also with the default compilation settings.
Apparently this is the case for all the types that can be "optimized":
when the number of bits is fixed (as in bit, fixnum, single-float, or
(signed-byte 11)) the array contains random data.
In most other cases (rational,integer,bignum,float,(un)signed-
byte,...) the array is initialized to NIL, which is not even a valid
value. An interesting exception is character, initialized to #\Null
On 2008-09-06, Andy Chambers <··············@googlemail.com> wrote:
> I often hear about people taking measures to avoid "consing". Is
Basically, there are often very simple, easy things you can do, which don't
hinder the maintainability of your code, but reduce its memory consumption.
Taking these steps is good coding practice.
It's like brushing your teeth.
> (defun perf-test ()
> (loop for i below 10000000
> do
> (sql-expand '(select (1 2)))))
>
> (time (perf-test))
Did you compile the function? If not, you are measuring parameters over
interpreted code. Compiling can make a difference to bytes consed, not only
execution speed.
> ...gave me this output on SBCL
>
> Evaluation took:
> 36.421 seconds of real time
> 35.86224 seconds of user run time
> 0.056004 seconds of system run time
> [Run times include 1.608 seconds GC run time.]
> 0 calls to %EVAL
> 0 page faults and
> 2,240,000,904 bytes consed.
>
> That seems like a lot of consing but I don't really know.
Two gigabytes of consing, but it did take ten million iterations.
That's only 220 bytes per iteration.
What is the real impact of this on you actual your program?
Does it matter that SQL-EXPAND over (SELECT (1 2)) requires 220 bytes?
We generally look at consing not so much because we are concerned about memory
use, but rather because we are concerned about speed. It's just another facet
of tuning the execution speed. More consing means more execution overhead. GC
is bad for performance because it requires the machine to spend cycles looking
over a graph of reachable objects. Not only does GC itself take time, but it
evacuates data out of caches, so that when control returns to the program, it
runs slower for a while.
We don't know when the GC will run, but, as a form of amortized analysis, we
can attribute the cost of GC to the consing which leads up to it. Every little
allocation incurs a ``debt'' which is ``paid'' as part of a large lump sum when
GC occurs. A function which conses a lot might not necessarily be penalized
much for that consing, but some subsequent computation might be.
By attributing the GC penalty to the consing, we can treat it like any other
attribute of an operation which impacts performance. Bytes consed translate to
time spent (some of it now, and some of it later). The approach is the same:
profile the code, or otherwise identify ``hotspots'' where a lot of consing is
happening, and focus on those.
Hence the question: does it matter that SQL-EXPAND over (SELECT (1 2)) requires
220 bytes? It will probably matter if it's executed in an inner loop over
millions of iterations.
This is exactly like the question ``does it matter that operation X takes Y
machine cycles''. It obviously depends on how frequently the program executes
operation X: what is the total time that is spent inside X, added up over all
of the calls to X over some interesting slice of the program's lifetime.
On Sep 6, 3:55 pm, Andy Chambers <··············@googlemail.com>
wrote:
> I often hear about people taking measures to avoid "consing". Is
> consing simply allocating more memory? How do you get a feel more how
> much is too much?
>
> For example, I have a recursive function that expands lispy SQL
> expressions into a tree of strings that can be printed out, a space
> between each and sent to the DBMS. Running the following (after
> compiling perf-test)...
>
> (defun perf-test ()
> (loop for i below 10000000
> do
> (sql-expand '(select (1 2)))))
>
> (time (perf-test))
>
> ...gave me this output on SBCL
>
> Evaluation took:
> 36.421 seconds of real time
> 35.86224 seconds of user run time
> 0.056004 seconds of system run time
> [Run times include 1.608 seconds GC run time.]
> 0 calls to %EVAL
> 0 page faults and
> 2,240,000,904 bytes consed.
>
> That seems like a lot of consing but I don't really know. If it is,
> how does one go about reducing it.
>
> Cheers,
> Andy
Yes, in Lisp informal jargon, "consing" means allocating Lisp
objects. The usual recommendation to "avoid consing" is usually not
that the consing per se is slow, but that if you do a lot of consing,
you are probably creating a lot of garbage, and the worry is that your
program will spend a lot of time in the garbage collector, and thus be
slow and have long pauses.
When I was first programming in Lisp in 1976, avoiding consing was
very important, especially inside inner loops, if you wanted your
program to perform well. These days it is far less important, because
garbage collector technology is phenomenally better now.