Ideas toward the GC

36 views
Skip to first unread message

Jacko

unread,
Jan 4, 2011, 6:37:08 PM1/4/11
to

Jacko

unread,
Jan 4, 2011, 11:27:27 PM1/4/11
to
http://wp.me/1fZn6 explains it better on my new wordpress blog.

tomas

unread,
Jan 5, 2011, 3:47:20 AM1/5/11
to
Just a random observation not backed by links (but you can browse
precisely this newsgroup to gain more insights).

while non-reference-counting garbage collectors (especially mark-and-sweep,
more especially in their modern incarnations, like generational) are
definitely more complex, they tend to be more efficient (time and space)
than the reference-counting ones: they just touch less memory.

Regards
-- tomás

Alexandre Ferrieux

unread,
Jan 5, 2011, 4:31:25 AM1/5/11
to
On 5 jan, 05:27, Jacko <jackokr...@gmail.com> wrote:
> http://wp.me/1fZn6explains it better on my new wordpress blog.

Welcome to Tcl, which from the beginning has set as a principle this
notion of disallowing circular constructions by the very syntax of the
language and the everything-is-a-string semantics.

-Alex

Donal K. Fellows

unread,
Jan 5, 2011, 5:55:54 AM1/5/11
to
On Jan 5, 9:31 am, Alexandre Ferrieux <alexandre.ferri...@gmail.com>
wrote:

> Welcome to Tcl, which from the beginning has set as a principle this
> notion of disallowing circular constructions by the very syntax of the
> language and the everything-is-a-string semantics.

But you get the issue anyway, just with higher-level constructs than
values (e.g., objects). Right now that's not a particularly big deal,
as the things affected are all explicit-delete, but it would be wrong
to say that it's not going to be an issue in the future.

Donal.

Message has been deleted

Alexandre Ferrieux

unread,
Jan 5, 2011, 6:44:55 AM1/5/11
to
On Jan 5, 11:55 am, "Donal K. Fellows"

Yes; but let's not blame the pure, ideal EIAS for the sins of
some future compromise :P

-Alex

Jacko

unread,
Jan 6, 2011, 7:58:42 PM1/6/11
to

It's the pausing of mark sweep, that is the realtime issue, locking is
worse than deterministic slowness.

Jacko

unread,
Jan 6, 2011, 8:01:09 PM1/6/11
to
On Jan 5, 9:31 am, Alexandre Ferrieux <alexandre.ferri...@gmail.com>
wrote:
> On 5 jan, 05:27, Jacko <jackokr...@gmail.com> wrote:
>
> >http://wp.me/1fZn6explainsit better on my new wordpress blog.

>
> Welcome to Tcl, which from the beginning has set as a principle this
> notion of disallowing circular constructions by the very syntax of the
> language and the everything-is-a-string semantics.
>
> -Alex

linsert does a copy of item then?

jima

unread,
Jan 7, 2011, 3:35:50 AM1/7/11
to
I think the work Frederic Bonnet is doing with Colibri is related to
all this...

https://sourceforge.net/mailarchive/forum.php?forum_name=tcl9-colibri

In Colibri a generational GC is being used along with ropes as a
substitute for Tcl_Obj.

The idea, as I understand it, is to provide some grounds for future
efforts in tcl.

Best regards,

jima

tomas

unread,
Jan 7, 2011, 3:36:24 AM1/7/11
to
Jacko <jacko...@gmail.com> writes:

> On Jan 5, 8:47 am, tomas <to...@floh.bas23> wrote:

>> [reference-counting vs. non-reference-counting]


>
> It's the pausing of mark sweep, that is the realtime issue, locking is
> worse than deterministic slowness.

While I am no GC buff (far from it!), the mark-and-sweep GCs have
learned to do incremental (and, as far as I understand, the
"generational" trick seems to be what makes their performance). See e.g.

<http://www.hpl.hp.com/personal/Hans_Boehm/gc/>

for an example of what a (non-precise, in this case) "modern" GC can
do. Of course, compared to refcounting, they are fiendishly complex.

Regards
-- tomás

Alexandre Ferrieux

unread,
Jan 7, 2011, 4:32:43 AM1/7/11
to
On 7 jan, 02:01, Jacko <jackokr...@gmail.com> wrote:
> On Jan 5, 9:31 am, Alexandre Ferrieux <alexandre.ferri...@gmail.com>
> wrote:
>
> > On 5 jan, 05:27, Jacko <jackokr...@gmail.com> wrote:
>
> > >http://wp.me/1fZn6explainsitbetter on my new wordpress blog.

>
> > Welcome to Tcl, which from the beginning has set as a principle this
> > notion of disallowing circular constructions by the very syntax of the
> > language and the everything-is-a-string semantics.
>
> > -Alex
>
> linsert does a copy of item then?

Yes, unless the value is unshared (refcount==1). That's the COW (copy-
on-write) semantics, that allows Tcl's refcounting approach to be both
simple and efficient.

-Alex


Jacko

unread,
Jan 7, 2011, 3:10:50 PM1/7/11
to
On Jan 7, 9:32 am, Alexandre Ferrieux <alexandre.ferri...@gmail.com>

wrote:
> On 7 jan, 02:01, Jacko <jackokr...@gmail.com> wrote:
>
> > On Jan 5, 9:31 am, Alexandre Ferrieux <alexandre.ferri...@gmail.com>
> > wrote:
>
> > > On 5 jan, 05:27, Jacko <jackokr...@gmail.com> wrote:
>
> > > >http://wp.me/1fZn6explainsitbetteron my new wordpress blog.

>
> > > Welcome to Tcl, which from the beginning has set as a principle this
> > > notion of disallowing circular constructions by the very syntax of the
> > > language and the everything-is-a-string semantics.
>
> > > -Alex
>
> > linsert does a copy of item then?
>
> Yes, unless  the value is unshared (refcount==1). That's the COW (copy-
> on-write) semantics, that allows Tcl's refcounting approach to be both
> simple and efficient.
>
> -Alex

interesting to keep refcount at 1, umm, ...

Alexandre Ferrieux

unread,
Jan 7, 2011, 6:31:00 PM1/7/11
to
> interesting to keep refcount at 1, umm, ...

Yes. To take advantage at script level of those of the primitives that
are able to work in-place for refcount 1 (lrange, lreplace, etc), use
the so-called "K-free K": $x[unset x] or $x[set x {}]

set x [lrange $x[set x {}] 0 end-1]

-Alex

Jacko

unread,
Jan 7, 2011, 9:00:25 PM1/7/11
to
umm, yes it's the tortoise and the sleepy hare!!umm, yes it's the
tortoise and the sleepy hare!!

Andreas Leitgeb

unread,
Jan 12, 2011, 2:11:48 PM1/12/11
to
Alexandre Ferrieux <alexandre...@gmail.com> wrote:
> Yes. To take advantage at script level of those of the primitives that
> are able to work in-place for refcount 1 (lrange, lreplace, etc), use
> the so-called "K-free K": $x[unset x] or $x[set x {}]
> set x [lrange $x[set x {}] 0 end-1]

This gets mentioned here every once in a while. Each time I see it rather
with a sad eye.

Is this so extremely unobvious trick (tcl-programmers aren't even supposed
to care about refcounted objects in the first place) not rather a millstone
at tcl's leg - especially, as it is not just for toying around, but a
necessary measure to avoid a particular kind of performance drop.

A newbie getting exposed to these topics too soon, is more likely to
rethink his decision about tcl, than to see the "beauty" of "K-free K".
He'd ask himself: Tcl, a language, or Tcl, a bungle of magic spells? ;)


PS: btw.,
Has this K-thingie been discussed, yet?
proc Kthingie {var args} {
upvar 1 $var lv; set lv {}; set lv [uplevel 1 $args]
}
Kthingie x lrange $x 0 end-1

(by the time, x is unset inside the proc, all the substs have
been applied) Just couldn't come up with a crisp name for it.
(a real implementation would also pass on errors correctly.)

Donal K. Fellows

unread,
Jan 13, 2011, 4:55:04 AM1/13/11
to
On Jan 12, 7:11 pm, Andreas Leitgeb <a...@gamma.logic.tuwien.ac.at>
wrote:

> Has this K-thingie been discussed, yet?
>   proc Kthingie {var args} {
>        upvar 1 $var lv; set lv {}; set lv [uplevel 1 $args]
>   }
>   Kthingie x  lrange $x 0 end-1

You can get a bytecode-efficient version like this:

set x [lrange $x[set x {}] 0 end-1]

It's not very obvious though. :-) More to the point, it also has very
odd trace semantics, and if there's an error during the [lrange]
operation (e.g., because the variable didn't originally contain a
list) it leaves the variable in an unexpected state. These sort of
concerns mean that it's best left as a user-visible optimization
instead of applying it automatically.

Donal.

Alexandre Ferrieux

unread,
Jan 13, 2011, 10:33:26 AM1/13/11
to
On 13 jan, 10:55, "Donal K. Fellows"

<donal.k.fell...@manchester.ac.uk> wrote:
> On Jan 12, 7:11 pm, Andreas Leitgeb <a...@gamma.logic.tuwien.ac.at>
> wrote:
>
> > Has this K-thingie been discussed, yet?
> >   proc Kthingie {var args} {
> >        upvar 1 $var lv; set lv {}; set lv [uplevel 1 $args]
> >   }
> >   Kthingie x  lrange $x 0 end-1
>
> You can get a bytecode-efficient version like this:
>
>   set x [lrange $x[set x {}] 0 end-1]

Ahem, Donal .. Please look 2 messages up :D

-Alex

Andreas Leitgeb

unread,
Jan 13, 2011, 6:33:29 PM1/13/11
to

I'm sure he didn't miss that. More likely he chose a more subtle way to
indicate that the transition from my "solution" to the original would be
advisable, rather than the other way round.

Imho, the only real solution(*) to this would be a complete set for
"variable mutating" list-operations, that no longer would need those
K-tricks in order to be performant. (assuming that $x even was the only
ref to the object already)

*: I do consider the necessity of "explicit ref drop" a problem that needs a
solution.

Jacko

unread,
Jan 14, 2011, 12:22:05 AM1/14/11
to
The immutable Tcl_Obj.... preserve, release... no pointer backed
reference, only values.

Fine for what I need at present. Does make me wonder what the OOPs of
8.6 will contain...?

tomas

unread,
Jan 14, 2011, 3:40:23 AM1/14/11
to

Hi,

someone care to enlighten us newbies on "K-tricks"?

I mean -- I'm following ths discussion with interest and can glean some
vague idea that this K-trick has something to do with dropping early a
reference into something which would otherwise stick for too long, but
the details are somewhat over my head ;-D

Is there any reference to a wiki page, HOWTO, what not, where I could
educate myself?

Thanks
-- tomás

APN

unread,
Jan 14, 2011, 4:17:10 AM1/14/11
to

Donal K. Fellows

unread,
Jan 14, 2011, 4:55:59 AM1/14/11
to
On Jan 14, 8:40 am, tomas <to...@floh.bas23> wrote:
> someone care to enlighten us newbies on "K-tricks"?

They're named after K, which is one of the fundamental combinators and
which is used to produce a sort of constant function. But that's not
what we use it for. :-)

What's going on is that, at the C level, Tcl *values* are stored in
reference counted structures called Tcl_Objs. These can be efficiently
shared and passed around, but for Tcl's semantics to work right, can
only be modified when they're *not* shared. If they're shared, they
have to be copied first; the copy is unshared and can then be modified
at will.

Now, applying this knowledge to the specific case where we're going to
do a little list manipulating of a value in a variable and write it
back:

set x [lreplace $x 2 3 foo bar grill]

Where are the references held? Well, there's going to be one reference
in the variable (obviously!) and there's going to be another from the
argument list; that second reference has to happen because otherwise
we'd lose transient values such as the results of complicated
substitutions. But this means that the list value is shared! The
[lreplace] operation has to duplicate it, which is expensive
(especially for long lists). What do we want to do to make it cheaper?
Easy, we need to reduce the number of references held at the point
when [lreplace] works on the value. Since there's a mandatory
reference held as part of the argument list, the one we have to get
rid of is due to the variable.

So what does the K trick do here? Well, it lets us reduce the
reference count in the variable by changing it to something else or
unsetting it, while still using that value. There are many such
variations: here's one that's relatively clear:

set x [lreplace [lindex [list $x [unset x]] 0] 2 3 foo bar grill]

What have we done? Well, firstly most of the command is unchanged. All
we've done is replace $x with [lindex [list $x [unset x]] 0]. The only
part that is perhaps not immediately obvious to you is that [unset x]
does indeed have a result: the empty string. However, at the reference
level it's more interesting. Firstly, it adds another reference to the
value in 'x' (as part of the arguments to [list]). Then it unsets 'x',
which reduces the reference count back to 1; the rest of the
construction is just about extracting that value from the arguments to
[list] and converting it into a naked argument to [lreplace] (with no
net change to its reference count). That then means that the
[lreplace] has an unshared value to work with, and can hence do its
edits in place; that's faster.

The original K trick was similar, but used a helper procedure:

proc K {x y} {return $x}
set x [lreplace [K $x [unset x]] 2 3 foo bar grill]

The details are slightly different but the overall story is the same.
Moreover, in 8.5 there's a cheaper version that has less intermediate
state:

set x [lreplace $x[unset x] 2 3 foo bar grill]

This is a bit trickier as it relies on the fact that concatenation of
any value with the empty string is a specially optimized case. (In all
the above things, it all works just as well if you use [set x ""] for
[unset x]; any other constant would do too. Indeed, there's a real
sense in which unsetting a variable is just writing a NULL for its
contents instead of a value reference.)

Of course, if this is unclear then ignore it. Write your code in a
simple way first. Then if you think there's a problem with speed, use
[time] to check whether that's really so. Only use the tricks
described in this post if you're sure that the lack of clarity is
justified by the *measured* performance boost.

Donal.

Alexandre Ferrieux

unread,
Jan 14, 2011, 5:20:33 AM1/14/11
to
On 14 jan, 00:33, Andreas Leitgeb <a...@gamma.logic.tuwien.ac.at>
wrote:

> Alexandre Ferrieux <alexandre.ferri...@gmail.com> wrote:
> > On 13 jan, 10:55, "Donal K. Fellows"
> ><donal.k.fell...@manchester.ac.uk> wrote:
> >> On Jan 12, 7:11 pm, Andreas Leitgeb <a...@gamma.logic.tuwien.ac.at>
> >> wrote:
> >> > Has this K-thingie been discussed, yet?
> >> >   proc Kthingie {var args} {
> >> >        upvar 1 $var lv; set lv {}; set lv [uplevel 1 $args]
> >> >   }
> >> >   Kthingie x  lrange $x 0 end-1
> >> You can get a bytecode-efficient version like this:
> >>   set x [lrange $x[set x {}] 0 end-1]
> > Ahem, Donal .. Please look 2 messages up :D
>
> I'm sure he didn't miss that. More likely he chose a more subtle way to
> indicate that the transition from my "solution" to the original would be
> advisable, rather than the other way round.

Ah, sorry for being dense :}

> Imho, the only real solution(*) to this would be a complete set for
> "variable mutating" list-operations, that no longer would need those
> K-tricks in order to be performant. (assuming that $x even was the only
> ref to the object already)
>
> *: I do consider the necessity of "explicit ref drop" a problem that needs a
> solution.

Yes.

Here is an attempt:

proc inplace {vv args} {
uplevel 1 unset $vv
tailcall {*}$args
}

To be used this way:

set x [inplace x lrange $x 0 end-1]

Note that it works also with several references to x, even dynamic:

set v x
set x [inplace x [concat $x $x [set $v]]]

The idea being to unset just before calling the payload, but after all
its arguments have been computed.

However, this doesn't quite work :(
There's still a dangling reference:

% set x [list q w e r t];inplace
x ::tcl::unsupported::representation $x
value is a list with a refcount of 2, object pointer at 0x90286b8,
internal representation 0x9050f18:(nil), no string representation.

To be compared with:

% set x [list q w e r t]; ::tcl::unsupported::representation
$x[unset x]
value is a list with a refcount of 1, object pointer at 0x9028868,
internal representation 0x9050518:(nil), no string representation.

I suspect this is due to the tailcall not completely obliterating the
call frame, which is somehow keeping a reference to the passed
arguments. Miguel, help ?

-Alex

tomas

unread,
Jan 14, 2011, 5:20:47 AM1/14/11
to
APN <pal...@yahoo.com> writes:

> See http://wiki.tcl.tk/1923

Thanks a million!

I tried looking up in the wiki, but missed the most obvious, it seems
:-)

Regards
-- tomás

Alexandre Ferrieux

unread,
Jan 14, 2011, 7:46:06 AM1/14/11
to
On 14 jan, 06:22, Jacko <jackokr...@gmail.com> wrote:
>
> Does make me wonder what the OOPs of 8.6 will contain...?

Sorry, cannot parse :/
Care to elaborate ?

-Alex

Glenn Jackman

unread,
Jan 14, 2011, 10:30:34 AM1/14/11
to
At 2011-01-14 04:55AM, "Donal K. Fellows" wrote:
> On Jan 14, 8:40�am, tomas <to...@floh.bas23> wrote:
> > someone care to enlighten us newbies on "K-tricks"?
>
> They're named after K, which is one of the fundamental combinators and
> which is used to produce a sort of constant function. But that's not
> what we use it for. :-)

[... detailed, lucid explanation snipped ...]

Donal, thanks for that tutorial. It really clarified things for me and
others like me who are not versed in the Tcl internals.

> Of course, if this is unclear then ignore it. Write your code in a
> simple way first. Then if you think there's a problem with speed, use
> [time] to check whether that's really so. Only use the tricks
> described in this post if you're sure that the lack of clarity is
> justified by the *measured* performance boost.

That's is fantastic advice. "Avoid premature optimization"


--
Glenn Jackman
Write a wise saying and your name will live forever. -- Anonymous

miguel sofer

unread,
Jan 14, 2011, 1:24:31 PM1/14/11
to Alexandre Ferrieux
On 01/14/2011 07:20 AM, Alexandre Ferrieux wrote:
> There's still a dangling reference:
>
> % set x [list q w e r t];inplace
> x ::tcl::unsupported::representation $x
> value is a list with a refcount of 2, object pointer at 0x90286b8,
> internal representation 0x9050f18:(nil), no string representation.
>
> To be compared with:
>
> % set x [list q w e r t]; ::tcl::unsupported::representation
> $x[unset x]
> value is a list with a refcount of 1, object pointer at 0x9028868,
> internal representation 0x9050518:(nil), no string representation.
>
> I suspect this is due to the tailcall not completely obliterating the
> call frame, which is somehow keeping a reference to the passed
> arguments. Miguel, help ?
>

I believe the two refs are:
1. as an argument to [representation] (same as the other example)
2. as part of the list-to-be-evaled-in-the-tailcall, ie the former $args

tomas

unread,
Jan 15, 2011, 3:58:11 AM1/15/11
to
"Donal K. Fellows" <donal.k...@manchester.ac.uk> writes:

> On Jan 14, 8:40 am, tomas <to...@floh.bas23> wrote:
>> someone care to enlighten us newbies on "K-tricks"?
>
> They're named after K, which is one of the fundamental combinators and
> which is used to produce a sort of constant function. But that's not
> what we use it for. :-)

Thanks for your writeup. It was not only /very/ enjoyable to read...

> Of course, if this is unclear then ignore it [...]

...but made things crystal clear. You are my hero :-)

Regards
-- tomás

Alexandre Ferrieux

unread,
Jan 15, 2011, 4:35:06 AM1/15/11
to

OK thanks. And since, as you explained offline, the 2. is not easy to
fix, I thought about another approach: bytecode-level optimization.
Indeed,

set x [lrange $x 0 end-1]

translates to

push1 5 # "lrange"
loadScalar1 %v0 # var "x"
push1 6 # "0"
push1 7 # "end-1"
invokeStk1 4
storeScalar1 %v0 # var "x"

while a tip-131-inspired bytecode optimized might add:

push1 5 # "lrange"
loadScalar1 %v0 # var "x"
push1 6 # "0"
push1 7 # "end-1"
-> unsetScalar 1 %v0 # var "x"
invokeStk1 4
storeScalar1 %v0 # var "x"

*But* the problem is that it is not always safe. When the invokeStk'ed
function does not (directly nor indirectly) try to re-access the
variable, it is okay. But detecting whether it is the case or not is
(1) not doable at compile-time (esp. since lrange is a first-class
citizen, not a bytecode instruction), and (2) possibly costly at
runtime (and would require a specific conditional-unset instruction or
weak-reference mechanism)...

That's why I mentioned tip 131. Any news on that front ? ;-)

-Alex

Andreas Leitgeb

unread,
Jan 15, 2011, 6:03:24 AM1/15/11
to
Alexandre Ferrieux <alexandre...@gmail.com> wrote:
>> I believe the two refs are:
>> 1. as an argument to [representation] (same as the other example)
>> 2. as part of the list-to-be-evaled-in-the-tailcall, ie the former $args
> OK thanks. And since, as you explained offline, the 2. is not easy to
> fix, I thought about another approach: ... [ solution involving tip131 ;) ]

A real solution of course would not really require tip131.

Create a new command like: lprune lvar first last implemented in
C just about the same way as lappend is: no gap in the variable's
content time-line, no danger of loss of value on error, and still
enjoy the performance boon of casually skipping the "C" in COW.

Then add a similar thing for lreplace & linsert and we'd soon laugh about
those arcane times when script-writers still had to care for dropping
refcounts, when all they wanted was an inplace operation.

Alexandre Ferrieux

unread,
Jan 15, 2011, 11:15:24 AM1/15/11
to
On Jan 15, 12:03 pm, Andreas Leitgeb <a...@gamma.logic.tuwien.ac.at>
wrote:

Yes, but duplicating the [lrange, linsert, lreplace] family is exactly
what I hoped to avoid with [inplace].
What we've just seen is that [inplace] cannot be done in script, due
to subtle details in the timing of reference-dropping in [tailcall].
But that does not prevent from doing it as a C primitive. Care to tip
it ?

-Alex

Andreas Leitgeb

unread,
Jan 15, 2011, 1:17:29 PM1/15/11
to
Alexandre Ferrieux <alexandre...@gmail.com> wrote:
>> Create a new command like:  lprune lvar first last  implemented in
>> C just about the same way as lappend is:  no gap in the variable's
>> content time-line, no danger of loss of value on error, and still
>> enjoy the performance boon of casually skipping the "C" in COW.
> Yes, but duplicating the [lrange, linsert, lreplace] family is exactly
> what I hoped to avoid with [inplace].
> What we've just seen is that [inplace] cannot be done in script, due
> to subtle details in the timing of reference-dropping in [tailcall].

Not just due to those.

> But that does not prevent from doing it as a C primitive. Care to tip
> it ?

If I just saw a chance for a wrapper to combine these:
- no "wrong-value" gap (at least not visible to traces)
- no "value-lost" on error (but no keeping backup, either!)
- still avoid copies (assuming that $x was the only ref)
... (all three happily provided by e.g. lappend & lset)

The former two do not seem like possibly done for general payload.
That's why I think, a wrapper just cannot do it, not even one in C.

Alexandre Ferrieux

unread,
Jan 15, 2011, 1:27:58 PM1/15/11
to
On Jan 15, 7:17 pm, Andreas Leitgeb <a...@gamma.logic.tuwien.ac.at>
wrote:

(1) no "wrong-value" gap (at least not visible to traces): that one
is easy: just shy away as soon as a trace is detected; the Tcl core
does that all the time, for all kind of optimizations.

(2) no "value-lost" on error (but no keeping backup, either!): the
wrapper will keep hold of the single reference; it can easily poke it
back into the var on error.

(3) avoid copies: yeah, that's what it's all about. Now what ?

Sounds doable. Hmm.

-Alex

Andreas Leitgeb

unread,
Jan 16, 2011, 8:49:40 AM1/16/11
to
Alexandre Ferrieux <alexandre...@gmail.com> wrote:
>> If I just saw a chance for a wrapper to combine these:
> (1) no "wrong-value" gap (at least not visible to traces): that one
> is easy: just shy away as soon as a trace is detected; the Tcl core
> does that all the time, for all kind of optimizations.

I'm wondering, if lappend x ... also turns into a
set x [linsert $x end {*}$args]
when there are write-traces on x.

> (2) no "value-lost" on error (but no keeping backup, either!): the
> wrapper will keep hold of the single reference; it can easily poke it
> back into the var on error.

But it can do so only, if it can *trust* the actual operation to not
discard the one reference it officially has. If the object gets freed
in the payload-operation (like typically on error in the arguments
validation phase) then the backup has thereby gone awry, too.
Can this be fixed, generally?

> (3) avoid copies: yeah, that's what it's all about.

Just didn't want to omit it. Yeah, this should be taken for granted,
furtheron in this discussion.

With these wrappers, I think we do only marginally approach the real issue.
Making the task (of efficiently applying a function (like lrange) to the
value stored in a variable, and have the result be written back) as straight-
forward to the user as possible.
Unfortunately, the current straightforward way involves a copy, and the fix
to that (the $x[unset x]-idiom) is far away from being straightforward.

Some new idea:
proc reflexive {op xn args} {
upvar $xn x
verify that $op is a supported operation, like lrange, linsert,...
verify that [list $x {*}$args] would be valid arguments to the op.
do-C-magic to have exactly one ref for next line:
perform $op with $args on the TclObj (errors have been checked above)
sanitize internal state, eventually fire write traces
}
reflexive lrange x 0 end-1

After all, this is like having a new ensemble for the reflexive variants.

Alexandre Ferrieux

unread,
Jan 16, 2011, 1:13:43 PM1/16/11
to
On Jan 16, 2:49 pm, Andreas Leitgeb <a...@gamma.logic.tuwien.ac.at>
wrote:

> Alexandre Ferrieux <alexandre.ferri...@gmail.com> wrote:
> >> If I just saw a chance for a wrapper to combine these:
> >  (1) no "wrong-value" gap (at least not visible to traces): that one
> > is easy: just shy away as soon as a trace is detected; the Tcl core
> > does that all the time, for all kind of optimizations.
>
> I'm wondering, if lappend x ... also turns into a
>    set x [linsert $x end {*}$args]
> when there are write-traces on x.

No it doesn't, you are right. But here we're only threatened by unset
traces. And we can decide either to avoid doing anything in the
presence of an unset trace (which could be acceptable), or to simply
allow the unset trace to fire. In this case [inplace] could be renamed
[unsetting].

>
> >  (2) no "value-lost" on error (but no keeping backup, either!): the
> > wrapper will keep hold of the single reference; it can easily poke it
> > back into the var on error.
>
> But it can do so only, if it can *trust* the actual operation to not
> discard the one reference it officially has.  If the object gets freed
> in the payload-operation (like typically on error in the arguments
> validation phase) then the backup has thereby gone awry, too.  
> Can this be fixed, generally?

No, the details of arguments' lifecycle make it so that it's the
caller's responsibility to release refs after a call (successful or
not). (See POP_OBJECT in TEBCresume). So, even a refcount==1 value is
guaranteed not to be 'killed' by the callee.

> With these wrappers, I think we do only marginally approach the real issue.
> Making the task (of efficiently applying a function (like lrange) to the
> value stored in a variable, and have the result be written back) as straight-
> forward to the user as possible.
> Unfortunately, the current straightforward way involves a copy, and the fix
> to that (the $x[unset x]-idiom) is far away from being straightforward.
>
> Some new idea:
>   proc reflexive {op xn args} {
>      upvar $xn x
>      verify that $op is a supported operation, like lrange, linsert,...
>      verify that [list $x {*}$args]  would be valid arguments to the op.
>      do-C-magic to have exactly one ref for next line:
>      perform $op with $args on the TclObj (errors have been checked above)
>      sanitize internal state, eventually fire write traces
>   }
>   reflexive lrange x 0 end-1
>
> After all, this is like having a new ensemble for the reflexive variants.

Yeah, but it might be better to add a few if(s) in the existing C code
for lrange/linsert/lreplace to implement that ensemble, because the
above needs non-modular knowledge about the semantics of $op. For
example, detecting the problem before calling [lrange $x 0 foo]
implies duplicating lrange's GetIndexFromObj.

-Alex

Andreas Leitgeb

unread,
Jan 17, 2011, 10:23:03 AM1/17/11
to
Alexandre Ferrieux <alexandre...@gmail.com> wrote:
> On Jan 16, 2:49 pm, Andreas Leitgeb <a...@gamma.logic.tuwien.ac.at>
>> Alexandre Ferrieux <alexandre.ferri...@gmail.com> wrote:
>> >> If I just saw a chance for a wrapper to combine these:
>> >  (1) no "wrong-value" gap (at least not visible to traces): that one
>> > is easy: just shy away as soon as a trace is detected; the Tcl core
>> > does that all the time, for all kind of optimizations.
>> I'm wondering, if lappend x ... also turns into a
>>    set x [linsert $x end {*}$args]
>> when there are write-traces on x.
> No it doesn't, you are right. But here we're only threatened by unset
> traces.

So far I left out the distinction between (interims) [set x {}] and
[unset x], as it is just a minor aspect of the actual problem.
It has been already discussed soem time ago, that unsetting is much
worse than setting to {}. (unsetting destroys any upvar-linkage as
well as traces that were on the var. Also, the var is going to have
to be re-created, afterwards, which might not restore the var's
previous namespace-membership) Let's just forget about [unset] for
the rest of this discussion.

>> >  (2) no "value-lost" on error (but no keeping backup, either!): the
>> > wrapper will keep hold of the single reference; it can easily poke it
>> > back into the var on error.
>> But it can do so only, if it can *trust* the actual operation to not
>> discard the one reference it officially has.  If the object gets freed
>> in the payload-operation (like typically on error in the arguments
>> validation phase) then the backup has thereby gone awry, too.  
>> Can this be fixed, generally?
> No, the details of arguments' lifecycle make it so that it's the
> caller's responsibility to release refs after a call (successful or
> not). (See POP_OBJECT in TEBCresume). So, even a refcount==1 value is
> guaranteed not to be 'killed' by the callee.

You're talking about the C-level here. Surely, the (C-)call-layer where
object-lifetime management happens would be still one level below any
such *general* wrapper on the call-stack. My point here is, that we
cannot safely keep a ref, and then call into the level, that handles
object-lifetime, as we'd be bound to do for a *general* wrapper.
Seemingly, we need a solution more specific to each wrapped command,
to the point of having to hook into each's implementation to get it right.

At this point, we can just as well add new commands for each separately -
eventually organized into a new ensemble.

>> Some new idea:
>>   proc reflexive {op xn args} {
>>      upvar $xn x
>>      verify that $op is a supported operation, like lrange, linsert,...
>>      verify that [list $x {*}$args]  would be valid arguments to the op.
>>      do-C-magic to have exactly one ref for next line:
>>      perform $op with $args on the TclObj (errors have been checked above)
>>      sanitize internal state, eventually fire write traces
>>   }
>>   reflexive lrange x 0 end-1
>> After all, this is like having a new ensemble for the reflexive variants.
> Yeah, but it might be better to add a few if(s) in the existing C code
> for lrange/linsert/lreplace to implement that ensemble, because the
> above needs non-modular knowledge about the semantics of $op. For
> example, detecting the problem before calling [lrange $x 0 foo]
> implies duplicating lrange's GetIndexFromObj.

Well, yes, so be it. Sounds like water on my mills :-)

Andreas Leitgeb

unread,
Jan 28, 2011, 6:23:13 AM1/28/11
to
This is now unanswered for some time. Maybe you're just busy or missed
it, or lost interest in this discussion, or this article didn't show
up on your newsserver, or maybe it was just not worth an answer
for whatever reason.
It would be nice if you could let me know (eventually per email).

Alexandre Ferrieux

unread,
Jan 28, 2011, 8:19:49 AM1/28/11
to
On 28 jan, 12:23, Andreas Leitgeb <a...@gamma.logic.tuwien.ac.at>
wrote:

> This is now unanswered for some time. Maybe you're just busy or missed
> it, or lost interest in this discussion, or this article didn't show
> up on your newsserver, or maybe it was just not worth an answer
> for whatever reason.
> It would be nice if you could let me know (eventually per email).

Oh sorry; the truth is that it's slightly under my activation
threshold :P

- I'm disappointed that [tailcall]'s current implementation doesn't
allow my script-level [inplace] to work

- Miguel convinced me that it is far from trivial to fix

- I agree with you that, if someone was to address this need, the way
to go would be an ensemble with the obvious short list of subcommands

- given the fact that the K trick works, I have no personal
motivation to do it

- given the fact that the K trick works and is quickly mastered by
anyone who cares a bit about in-place performance, I have little
altruistic motivation to do it ;-)

So if you really want it, please TIP, and start working on the patch
(or maybe motivate someone else ?).
Sincerely sorry,

-Alex

Reply all
Reply to author
Forward
0 new messages