Enlightenment sought on use of K combinator
Helmut Giese
how do you remove the last element of a list? Well, that's easy. Just
say
set l [lreplace $l end end]
So far, so good. However, tonight I was browsing thru
http://mini.net/tcl/8539
a little gem that will find unmatched braces, brackets, etc. in your
scripts by Dan Smart (thanks Dan). And there I find
proc popBack {lst} {
upvar 1 $lst l
if {[llength $l]} {
set r [lindex $l end]
set l [lreplace [K $l [set l {}]] end end]
} else {
error "pop of empty list"
}
return $r
}
Huh?
set l [lreplace [K $l [set l {}]] end end] ;# ?????
Why this (seemingly more complicated) construct? There must be a
specific reason - after all, the author isn't exactly a Tcl amateur.
So here comes the $100 question:
Why formulate the removal of the a list's last element this way?
And - regardless of what anybody answers - :)
How on earth does one get to know this kind of thing?
Helmut (being really curious) Giese
R. T. Wurth
Answering your last question first, I first read about it right here
in the newsgroup. I think it may also be documented in the TIP that
introduced [lset]. I also think it might be referred to and
explained somewhere in the Wiki, but on a page on some other
subject.
Now on to the main subject. Consider:
set x [SomeFunctionOf $x]
In preparing the argumenst to [SomeFunctionOf], Tcl need merely find
the underlying TclObj referenced by x, and increment its reference
count. However, as soon as [SomeFunctionOf] attempts to modify the
value it receives, the interpreter discovers the reference count
requires making a copy. After [SomeFunctionOf] completes, its
result is assigned to x, causing the carefully-preserved former
value of x to be deleted.
Now consider:
proc K {x y} {return $x}
..
set x [SomeFunctionOf [K $x [set $x {}]]]
Here, the interpreter first prepares the [K] argument list. It
makes a reference to the value to which x refers, then clears x.
Since the old value still has an active reference (on the argument
list being prepared for [K], it is not deleted yet. Next, the
second argument to [k] is constructed, with the side effect of
decrementing the reference count of the object holding the value
formerly referenced by x. [K] then executes, returning that value,
which is then placed on the argument list of [SomeFunctionOf], The
proc [SomeFunctionOf] gets a reference to an object which has only
one reference, so when [SomeFunctionOf] needs to change it, the
interpreter is free to directly modify it without first making a
copy.
--
Rich Wurth / rwu...@att.net / Rumson, NJ USA
Consultant to the telecom industry
Egil Støren
> In article <3e6bc19...@News.CIS.DFN.DE>, hgi...@ratiosoft.com (Helmut Giese) wrote:
>
>>Hello out there,
>>how do you remove the last element of a list? Well, that's easy. Just
>>say
>> set l [lreplace $l end end]
>>
Hmm. I don't like this kind of programming very much. It goes against
the major single argument for using Tcl compared to other scripting
languages: simplicity. Would it not be possible to put this kind of
optimization into the compilation stage?
Egil Støren
Michael Schlenker
> R. T. Wurth wrote:
>> Now consider:
>> proc K {x y} {return $x}
>> ..
>> set x [SomeFunctionOf [K $x [set $x {}]]]
>> Here, the interpreter first prepares the [K] argument list. It makes
>> a reference to the value to which x refers, then clears x. Since the
>> old value still has an active reference (on the argument list being
>> prepared for [K], it is not deleted yet. Next, the second argument to
>> [k] is constructed, with the side effect of decrementing the reference
>> count of the object holding the value formerly referenced by x. [K]
>> then executes, returning that value, which is then placed on the
>> argument list of [SomeFunctionOf], The proc [SomeFunctionOf] gets a
>> reference to an object which has only one reference, so when
>> [SomeFunctionOf] needs to change it, the interpreter is free to
>> directly modify it without first making a copy.
>
>
> Hmm. I don't like this kind of programming very much. It goes against
> the major single argument for using Tcl compared to other scripting
> languages: simplicity. Would it not be possible to put this kind of
> optimization into the compilation stage?
This optimization is quite simple to do, just code an extension for this
special case, that does an in-place lreplace. This would be similar to
lset, that takes a list, not the values of a list as arguments.
Compilation isn't really an issue here, it is the copy-on-write semantic
of Tcl_Obj's that hits you here. [lreplace] isn't byte compiled yet.
Compiling this construct away would require a hint to the compiler, in
effect a special construct like the K combinator, so you wouldn't win
anything. How should the compiler otherwise detect, that the values you
give to lreplace are not used later? Traces and Introspection make this
really hard, even for proc local variables.
Simplicity is an issue, yes. But the current style is simple, use
lreplace and don't care about side effects, as they cannot happen, you
get a clean copy. The current style just isn't as efficient as it could
be, but it is simple. If you do lreplace on a small list you surely
don't mess with the K combinator, but if you have large lists and
performance gets an issue, you take the complex tools from your toolbox
to make it work.
Michael
Helmut Giese
I assume this should be " ... [set x {}]]]"
>Here, the interpreter first prepares the [K] argument list. It
>makes a reference to the value to which x refers, then clears x.
>Since the old value still has an active reference (on the argument
>list being prepared for [K], it is not deleted yet. Next, the
>second argument to [k] is constructed, with the side effect of
>decrementing the reference count of the object holding the value
>formerly referenced by x. [K] then executes, returning that value,
>which is then placed on the argument list of [SomeFunctionOf], The
>proc [SomeFunctionOf] gets a reference to an object which has only
>one reference, so when [SomeFunctionOf] needs to change it, the
>interpreter is free to directly modify it without first making a
>copy.
Thanks Rich,
for the clear expanation. I had to read it twice (trying to figure out
at which moment what is happening in which context), but then I
understood - so I thought.
I even had an idea. :) I figured, that by saying
set x [SomeFunctionOf [K $x [unset x]]]
instead of
set x [SomeFunctionOf [K $x [set x {}]]]
this would fit even better the goal of removing any unwanted
references to 'x'.
So I wrote a little script to test the relative performance of 3
different ways to [lreplace] (see below). I get surprising results:
Starting a plain Tclsh (8.4.1 on Win98) and sourcing my script
multiple times
- I get rather varying results for each run and
- for the list of 10000 the 'normal' lreplace takes longer - in all
other cases it is the fastest.
However, sourcing the script from withon TKCon I get rather stable
results and "the normal way to [lreplace]" is *always* fastest.
Hm, this gets me thinking that either
- my example use of K is inappropriate or
- my way of [time]ing does not what I intend to.
Any ideas?
Best regards
Helmut Giese
[test script]
proc K {x y} {set x}
proc lreplNorm {lst} {
upvar $lst l
set l [lreplace $l end end]
}
proc lreplK {lst} {
upvar $lst l
set l [lreplace [K $l [set l {}]] end end]
}
proc lreplKunset {lst} {
upvar $lst l
set l [lreplace [K $l [unset l]] end end]
}
# create some lists
for {set i 0} {$i < 100} {incr i} {lappend lst100 $i}
for {set i 0} {$i < 1000} {incr i} {lappend lst1000 $i}
for {set i 0} {$i < 10000} {incr i} {lappend lst10000 $i}
puts ""
puts "list has 100 elements"
puts "Normal lreplace:\t [time {set lst $lst100 ; lreplNorm lst}
1000]"
puts "lreplace with K:\t [time {set lst $lst100 ; lreplK lst} 1000]"
puts "lreplace with K & unset: [time {set lst $lst100 ; lreplKunset
lst} 1000]"
puts ""
puts "list has 1000 elements"
puts "Normal lreplace:\t [time {set lst $lst1000 ; lreplNorm lst}
1000]"
puts "lreplace with K:\t [time {set lst $lst1000 ; lreplK lst} 1000]"
puts "lreplace with K & unset: [time {set lst $lst1000 ; lreplKunset
lst} 1000]"
puts ""
puts "list has 10000 elements"
puts "Normal lreplace:\t [time {set lst $lst10000 ; lreplNorm lst}
1000]"
puts "lreplace with K:\t [time {set lst $lst10000 ; lreplK lst} 1000]"
puts "lreplace with K & unset: [time {set lst $lst10000 ; lreplKunset
lst} 1000]"
# [unset] lists for multiple sourcing
unset lst100
unset lst1000
unset lst10000
Michael Schlenker
> I even had an idea. :) I figured, that by saying
> set x [SomeFunctionOf [K $x [unset x]]]
> instead of
> set x [SomeFunctionOf [K $x [set x {}]]]
> this would fit even better the goal of removing any unwanted
> references to 'x'.
>
> So I wrote a little script to test the relative performance of 3
> different ways to [lreplace] (see below). I get surprising results:
> Starting a plain Tclsh (8.4.1 on Win98) and sourcing my script
> multiple times
> - I get rather varying results for each run and
> - for the list of 10000 the 'normal' lreplace takes longer - in all
> other cases it is the fastest.
>
> However, sourcing the script from withon TKCon I get rather stable
> results and "the normal way to [lreplace]" is *always* fastest.
>
> Hm, this gets me thinking that either
> - my example use of K is inappropriate or
> - my way of [time]ing does not what I intend to.
As the K combinator replaces the copying overhead with a proc call
overhead, it is only worth the trouble for large lists, where a copy
actually matters. If you use larger lists (take some 10000 words for
example, instead of ints), you will see the effect better.
Michael Schlenker
Andreas Leitgeb
> Hm, this gets me thinking that either
> - my example use of K is inappropriate or
> - my way of [time]ing does not what I intend to.
the K-combinator is, that the original Tcl_Object (bound to the
variable, whose value is to be replaced) previously had a reference
count of exactly 1, which (if I understood it right) is false in
all of your examples.
It might work better, if you don't reset the value of "lst" to $lst100...
(thereby re-creating a double-referenced object), but instead use lappend
inside the time-loop to compensate for the otherwise shrinking list.
e.g.:
% set lst $lst100 ; time {lappend lst last; lreplNorm lst} 1000
Maybe the upvar'ing inside the procedures also has an impact, but
I'm not sure about that.
--
Nichts ist schlimmer als zu wissen, wie das Unheil sich entwickelt,
und voll Ohnmacht zusehn muessen - das macht mich voellig krank...
-- (Musical Elisabeth; "Die Schatten werden laenger")
Helmut Giese
<Andreas...@siemens.at> wrote:
>Helmut Giese <hgi...@ratiosoft.com> wrote:
>> Hm, this gets me thinking that either
>> - my example use of K is inappropriate or
>> - my way of [time]ing does not what I intend to.
>I fear that may be the case here, because the relevant thing about
>the K-combinator is, that the original Tcl_Object (bound to the
>variable, whose value is to be replaced) previously had a reference
>count of exactly 1, which (if I understood it right) is false in
>all of your examples.
>
>It might work better, if you don't reset the value of "lst" to $lst100...
>(thereby re-creating a double-referenced object), but instead use lappend
>inside the time-loop to compensate for the otherwise shrinking list.
You're right. Works like a charm now - and is really impressive. See
my new posting below.
Best regards
Helmut Giese
Helmut Giese
Thanks. I now have an impressive test script. See my follow-up posting
Heiner Marxen
Helmut Giese <hgi...@ratiosoft.com> wrote:
>On Sun, 09 Mar 2003 23:29:13 GMT, rwu...@att.net (R. T. Wurth) wrote:
>
>So I wrote a little script to test the relative performance of 3
>different ways to [lreplace] (see below). I get surprising results:
>Starting a plain Tclsh (8.4.1 on Win98) and sourcing my script
>multiple times
>- I get rather varying results for each run and
>- for the list of 10000 the 'normal' lreplace takes longer - in all
>other cases it is the fastest.
>
>However, sourcing the script from withon TKCon I get rather stable
>results and "the normal way to [lreplace]" is *always* fastest.
>
>Hm, this gets me thinking that either
>- my example use of K is inappropriate or
>- my way of [time]ing does not what I intend to.
>
>Any ideas?
>Best regards
>Helmut Giese
>
> [test script]
>proc K {x y} {set x}
>
>proc lreplNorm {lst} {
> upvar $lst l
> set l [lreplace $l end end]
>}
>
>proc lreplK {lst} {
> upvar $lst l
> set l [lreplace [K $l [set l {}]] end end]
>}
>
The way you do this, there is always yet another reference to the list.
The value of $lst handed to [lreplace] is shared with $lst100, $lst1000
or $lst10000, respectively.
As a result, the K-trick does not yield a non-shared object.
I have modified your test script slightly:
proc K {x y} {set x}
proc lreplNorm {lst} {
upvar $lst l
set l [lreplace $l end end 77]
}
proc lreplK {lst} {
upvar $lst l
set l [lreplace [K $l [set l {}]] end end 77]
}
proc lreplKunset {lst} {
upvar $lst l
set l [lreplace [K $l [unset l]] end end 77]
}
# create some lists
for {set i 0} {$i < 100} {incr i} {lappend lst100 $i}
for {set i 0} {$i < 1000} {incr i} {lappend lst1000 $i}
for {set i 0} {$i < 10000} {incr i} {lappend lst10000 $i}
foreach v {lst100 lst1000 lst10000} {
set lst [lreplace [set $v] 0 0 -77]
puts ""
puts "before: list has [llength $lst] elements"
puts "Normal lreplace: [time {lreplNorm lst} 1000]"
puts "lreplace with K: [time {lreplK lst} 1000]"
puts "lreplace with K & unset: [time {lreplKunset lst} 1000]"
puts "after : list has [llength $lst] elements"
}
# [unset] lists for multiple sourcing
unset lst
unset lst100
unset lst1000
unset lst10000
And with tclsh I see output like:
before: list has 100 elements
Normal lreplace: 6 microseconds per iteration
lreplace with K: 5 microseconds per iteration
lreplace with K & unset: 5 microseconds per iteration
after : list has 100 elements
before: list has 1000 elements
Normal lreplace: 17 microseconds per iteration
lreplace with K: 5 microseconds per iteration
lreplace with K & unset: 5 microseconds per iteration
after : list has 1000 elements
before: list has 10000 elements
Normal lreplace: 596 microseconds per iteration
lreplace with K: 5 microseconds per iteration
lreplace with K & unset: 6 microseconds per iteration
after : list has 10000 elements
That's better, right? :-)
--
Heiner Marxen hei...@insel.de http://www.drb.insel.de/~heiner/
Helmut Giese
wrote:
[snipped original question including faulty script]
Helmut Giese
Egil Støren
> How should the compiler otherwise detect, that the values you
> give to lreplace are not used later?
My knowledge about the byte compiler is very poor, so maybe my arguments
are not easily applicable. But from the reasoning behind the use of the
K combinator, it seems the point is to reduce the reference count to the
object referenced by l (in the sentence below) by one:
set l [lreplace $l end end]
In a compilation stage it would only be neccessary for the compiler to
notice that the reference to the object due to l will disappear since l
will be set to a new value in the outer command.
> Traces and Introspection make this
> really hard, even for proc local variables.
Maybe so.
Egil
Donal K. Fellows
> I even had an idea. :) I figured, that by saying
> set x [SomeFunctionOf [K $x [unset x]]]
> instead of
> set x [SomeFunctionOf [K $x [set x {}]]]
> this would fit even better the goal of removing any unwanted
> references to 'x'.
> Hm, this gets me thinking that either
> - my example use of K is inappropriate or
> - my way of [time]ing does not what I intend to.
The whole thing depends on reference counts. If you can feed a list into
[lreplace] that has a reference count of one, [lreplace] can be much more
efficient in how it manipulates memory; chances are it won't need to copy large
amounts of the list or reallocate the main memory blocks used.
The [K] trick is there to make one specific case more efficient: where a
variable holds the only reference to a particular list value and you wish to
update the value being held in that variable. If there's another reference to
the value somewhere, the trick has negative value (slows things down and makes
the code much less clear.) Unfortunately, it is this that is slaying you in
your attempts to measure the performance...
(The reason I prefer to use the set-to-empty instead of the unset is really to
do with traces. I'd rather not have any unset traces run unless the variable is
really being removed. It's also about 10% slower in 8.4.1)
For a real test of the difference the [K] trick can make (though with [linsert]
instead of [lreplace]; the two commands have the same behaviour in this
respect), try these:
proc buildAlternatingList {size} {
set l {}
for {set i 0} {$i<$size} {} {
set idx [expr {[llength $l]/2}]
set l [linsert $l $idx [incr i] [incr i]]
}
return $l
}
proc K {x y} {set x}
proc buildAlternatingListK {size} {
set l {}
for {set i 0} {$i<$size} {} {
set idx [expr {[llength $l]/2}]
set l [linsert [K $l [set l {}]] $idx [incr i] [incr i]]
}
return $l
}
puts "Without K, size 10000: [time {buildAlternatingList 10000}]
puts "With K, size 10000: [time {buildAlternatingListK 10000}]
On this machine (which is a slow SGI O2, alas, but that makes it good for
bringing out timing details), that's 15140095 us (i.e. 15 seconds) vs. 538812 us
(.5 sec, or about 30 times faster)! And the time improvements will increase as
the list size gets longer.
Donal.
--
Donal K. Fellows http://www.cs.man.ac.uk/~fellowsd/ donal....@man.ac.uk
-- Thanks, but I only sleep with sentient lifeforms. Anything else is merely
a less sanitary form of masturbation.
-- Alistair J. R. Young <avatar...@arkane.demon.co.uk>
Helmut Giese
<donal.k...@man.ac.uk> wrote:
>The whole thing depends on reference counts. If you can feed a list into
>[lreplace] that has a reference count of one, [lreplace] can be much more
>efficient in how it manipulates memory; chances are it won't need to copy large
>amounts of the list or reallocate the main memory blocks used.
>
>The [K] trick is there to make one specific case more efficient: where a
>variable holds the only reference to a particular list value and you wish to
>update the value being held in that variable. If there's another reference to
>the value somewhere, the trick has negative value (slows things down and makes
>the code much less clear.) Unfortunately, it is this that is slaying you in
>your attempts to measure the performance...
>
>(The reason I prefer to use the set-to-empty instead of the unset is really to
>do with traces. I'd rather not have any unset traces run unless the variable is
>really being removed. It's also about 10% slower in 8.4.1)
>For a real test of the difference the [K] trick can make (though with [linsert]
>instead of [lreplace]; the two commands have the same behaviour in this
>respect), try these:
>
> proc buildAlternatingList {size} {
> set l {}
> for {set i 0} {$i<$size} {} {
> set idx [expr {[llength $l]/2}]
> set l [linsert $l $idx [incr i] [incr i]]
> }
> return $l
> }
> proc K {x y} {set x}
> proc buildAlternatingListK {size} {
> set l {}
> for {set i 0} {$i<$size} {} {
> set idx [expr {[llength $l]/2}]
> set l [linsert [K $l [set l {}]] $idx [incr i] [incr i]]
> }
> return $l
> }
>
> puts "Without K, size 10000: [time {buildAlternatingList 10000}]
> puts "With K, size 10000: [time {buildAlternatingListK 10000}]
That's also a nice example. With the help of some other's remarks I
had changed my original example, and now it's really, really
impressive (see my new posting a couple 'lines down).
Thanks
Helmut Giese
Donal K. Fellows
> Hmm. I don't like this kind of programming very much. It goes against
> the major single argument for using Tcl compared to other scripting
> languages: simplicity. Would it not be possible to put this kind of
> optimization into the compilation stage?
It's tricky to do this and get trace semantics right. Very, very tricky.