Optimizing channel lookups
Alexandre Ferrieux
Whenever Tcl uses a channel, currently (8.5 too) it does *two*
hashtable lookups:
- it "retrieves" the channel table (in GetChannelTable) by a
lookup on key "tclIO":
Tcl_GetAssocData(interp, "tclIO", NULL);
- it looks up the channel itself from its name as key in this
channel table.
Question: Why the first lookup, with a static key ? Why not store a
pointer to the channel table as a field in the interp structure ?
-Alex
Don Porter
> Question: Why the first lookup, with a static key ? Why not store a
> pointer to the channel table as a field in the interp structure ?
Sounds relevant to Tcl Feature Request 1077194.
Hmmm.... although that mentions the "ekeko" proposal, it doesn't really
get into it. You might want to contact Miguel Sofer and ask if that
concept is spelled out anywhere.
Hmmm... a little bit more at: http://wiki.tcl.tk/ekeko
--
| Don Porter Mathematical and Computational Sciences Division |
| donald...@nist.gov Information Technology Laboratory |
| http://math.nist.gov/~DPorter/ NIST |
|______________________________________________________________________|
Alexandre Ferrieux
> Alexandre Ferrieux wrote:
> > Question: Why the first lookup, with a static key ? Why not store a
> > pointer to the channel table as a field in the interp structure ?
>
> Sounds relevant to Tcl Feature Request 1077194.
>
> Hmmm.... although that mentions the "ekeko" proposal, it doesn't really
> get into it. You might want to contact Miguel Sofer and ask if that
> concept is spelled out anywhere.
>
> Hmmm... a little bit more at:http://wiki.tcl.tk/ekeko
>
Do I interpret the picture well, in believing that the idea that the
interp struct is big and eclectic enough, so that all new additions
should only be through at least one indirection ? Are you serious
about this ? With a costly indirection like a hash table ? It's not
April Fool's day, right ?
-Alex
Michael Schlenker
It might be clever instead. Think about cpu cache usage. If you don't
need the whole structure all the time, you can improve performance with
such a strategy. Google for 'structure splitting'...
(see for example
http://research.microsoft.com/~trishulc/papers/definition_distr.ps
)
Michael
Alexandre Ferrieux
wrote:
That's a general statement that doesn't apply here. The delta of cache
misses induced by an extra 4-byte value added to a 12-byte-long
structure present in just one instance (one per interp obviously), is
ridiculously small, especially when compared with all the cycles lost
in doing a hash lookup (which may itself induce cache misses).
Sometimes Googling is not enough...
-Alex
Alexandre Ferrieux
wrote:
> ... an extra 4-byte value added to a 12-byte-long
> structure present in just one instance (one per interp obviously), is
> ridiculously small
The actual Tcl_Interp is actually much larger than the 12 bytes
visible in its "public" part. But this makes the relative effect of
the extra long even tinier...
-Alex
Joe English
>Don Porter wrote:
>>
>> Hmmm... a little bit more at:http://wiki.tcl.tk/ekeko
>
>Do I interpret the picture well, in believing that the idea that the
>interp struct is big and eclectic enough, so that all new additions
>should only be through at least one indirection ? Are you serious
>about this ? With a costly indirection like a hash table ? It's not
>April Fool's day, right ?
That's the general idea, yeah. Anything new that's attached to
an interp should start off life as AssocData; if it later proves
to be central/important/performance-critical enough, then it
can be promoted to have its own dedicated pointer in struct Interp.
If it's _really_ central and important, then it can be considered
as a candidate for inlining.
The channel table might be considered important enough to be promoted.
Conversely, there's a bunch of inlined stuff in struct Interp that
really ought to be pushed out.
This is less about performance than it is about maintainability.
The more stuff there is in struct Interp, the longer it takes each
time a developer scrolls through tclInt.h looking for something.
Channel lookups -- I'm guessing -- aren't performance-critical,
and skipping a hashtable lookup saves a few microseconds at best.
--Joe English
Joe English
>Alexandre Ferrieux wrote:
>> ... an extra 4-byte value added to a 12-byte-long
>> structure present in just one instance (one per interp obviously), is
>> ridiculously small
>
>The actual Tcl_Interp is actually much larger than the 12 bytes
>visible in its "public" part. But this makes the relative effect of
>the extra long even tinier...
How many millions of channel lookups do you suppose how many
thousands of users would need to perform before this would
make a perceptible difference? Would it ever?
I'm not saying this shouldn't be done, just saying that
there are considerations other than naked speed. Maintainability
is equally important -- more important, actually, because
the leaner the code the easier it is to find the _big_
improvements. And optimizing things that don't need to be
optimized is one of the worst ways a developer can spend time.
--Joe English
Don Porter
> Whenever Tcl uses a channel, currently (8.5 too) it does *two*
> hashtable lookups:
Is this true? Are you certain there's no Tcl_ObjType to cache
the lookup results? (This isn't my area, and I haven't gone
source diving to check.)
If there really isn't one, I would think that would be the
better answer.
(I suppose, unless the need for channels to cross thread
boundaries prevents this. Sigh.)
This is something to pursue with the channel maintainer(s).
DGP
bill...@alum.mit.edu
> (I suppose, unless the need for channels to cross thread
> boundaries prevents this. Sigh.)
Life was a lot simpler before threads, wasn't it?
Alexandre Ferrieux
>
> The channel table might be considered important enough to be promoted.
> Conversely, there's a bunch of inlined stuff in struct Interp that
> really ought to be pushed out.
Yes, that's exactly the point of my post :-)
> This is less about performance than it is about maintainability.
> The more stuff there is in struct Interp, the longer it takes each
> time a developer scrolls through tclInt.h looking for something.
True, but your first paragraph shows that a swap with another less-
important thing could be wise.
> Channel lookups -- I'm guessing -- aren't performance-critical,
> and skipping a hashtable lookup saves a few microseconds at best.
Yes, a few microseconds, and that's the order of magnitude of a [gets]
(~6us on my 1.7GHz P4 on a file in cache). So this means that
streamlining GetChannel could largely improve loops like
while {[gets $ch line]>=0} {do some simple thing}
I wouldn't dare to say that this is unimportant.
-Alex
Alexandre Ferrieux
Sure, man. Ol'good days :-)
-Alex
Alexandre Ferrieux
> Alexandre Ferrieux wrote:
> > Whenever Tcl uses a channel, currently (8.5 too) it does *two*
> > hashtable lookups:
>
> Is this true? Are you certain there's no Tcl_ObjType to cache
> the lookup results? (This isn't my area, and I haven't gone
> source diving to check.)
Yes.
> If there really isn't one, I would think that would be the
> better answer.
Yes, and I was thinking about TIPping a possible solution [*], but
given Joe's answer (who finds the optimization unneeded), I'm
wondering if it's worth the effort.
[*] So here it is, instead of a TIP :-)
The naive approach would be to directly put a (Tcl_Channel *) in the
int-rep of channel values (whose st-rep would be "file3" or "sock4"
etc).
However, this cannot work alone because of the lifecycle of the
various objects involved: if a channel is closed, its Tcl_Channel is
freed, but if values containing this channel remain in the system
(which is mots generally the case like in [close $ch] : $ch remains),
then their int-rep is a dangling pointer.
To solve this, I see two possibilities:
(1) if the Tcl_Channel structs all live in a preallocated contiguous
area (I welcome any enlightenment about this), the only thing to avoid
is unwanted reuse. In this case, a generation count can do the job
(but must be also stored alongside the pointer in the int-rep).
(2) Otherwise, being in a general malloc area, the dangling pointer
must not survive. In this case, the only thing to do is an extra
indirection structure, let's call it a ChannelRef, between the int-rep
of all channel values pointing to it, and the actual Tcl_Channel.
This ChannelRef has the following property:
- it is refcounted, giving the number of live Tcl_Obj values
whoe int-rep points to it. To be decremented on their deallocation.
- it points to a single Tcl_Channel which also has a pointer
to it.
- when the Tcl_Channel is closed, the ChannelRef's 'closed'
flag is set to true.
This way, the ChannelRef and the true Tcl_Channel have separate
lifecycle, ensuring safety. Most notably, if something reuses a
channel value after closing it, the int-rep still points to the
ChannelRef which is still alive thanks to refcounting, but
unambiguously knows that the channel has been closed. The ChannelRef
eventually disappears when its refcount drops to zero, if it so
happens before the end of Time.
Now, whichever of (1) or (2) applies, we have a safe way of cacheing
channel references or pointer in the int-rep of channel values. Of
course the Channel Table is still needed for cases where the int-rep
is lost or invalidated or the value comes from string land. But its
use is much rarer than today...
-Alex
Donal K. Fellows
> I wouldn't dare to say that this is unimportant.
I would. :-)
I/O syscalls take *ages* compared to any hashing of short strings.
Donal.
Alexandre Ferrieux
Sorry, but hashing a constant string is against my religion.
-Alex
Donal K. Fellows
> Sorry, but hashing a constant string is against my religion.
Your religion includes the tenet "Optimize early! Optimize often!"
does it?
Donal.
Alexandre Ferrieux
wrote:
No. Simplify early and often, yes.
Replacing a hash lookup of a constant by a simple indirection may be
saving few CPU cycles (though this has yet to be quantified), but more
importantly it saves many human brain-cycles of people looking into
the code and asking themselves "Why on earth did they hide this
there ???".
For extensions it is entirely different: AssocData is perfectly
indicated for them, in allowing a "runtime-piggyback" of the interp
struct. But for the core it just sounds unselessly complicated.
-Alex
Donal K. Fellows
> Replacing a hash lookup of a constant by a simple indirection may be
> saving few CPU cycles (though this has yet to be quantified), but more
> importantly it saves many human brain-cycles of people looking into
> the code and asking themselves "Why on earth did they hide this
> there ???".
But hardly anyone looks through the code. You're arguing for doing a
bunch of work for next to no return on that investment other than
"making it easier for you to dig through the code". Hashing a short
string *really* is fast. I measured it two weeks ago, and for situations
involving channels (i.e. with I/O syscalls in the mix, which *are* slow)
the overhead is negligible. I'll continue to argue this until you
present evidence (i.e. measured timings) otherwise. Yes, doing this will
take effort; might as well be yours since it bothers you so much. :-)
Donal.