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
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
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.
Yes; but let's not blame the pure, ideal EIAS for the sins of
some future compromise :P
-Alex
It's the pausing of mark sweep, that is the realtime issue, locking is
worse than deterministic slowness.
linsert does a copy of item then?
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
> 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
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, ...
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
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.)
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.
Ahem, Donal .. Please look 2 messages up :D
-Alex
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.
Fine for what I need at present. Does make me wonder what the OOPs of
8.6 will contain...?
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
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.
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
> 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
Sorry, cannot parse :/
Care to elaborate ?
-Alex
[... 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
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
> 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
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
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.
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
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.
(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
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.
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
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 :-)
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