develooper Front page | perl.perl6.internals | Postings from July 2002

Re: More Keyed Questions

Thread Previous
Scott Walters
July 24, 2002 01:40
Re: More Keyed Questions
Message ID:

On Wed, 24 Jul 2002, Mike Lambert wrote:


I submit some patches a few days back, one with updates to the documentation
from my reverse engineering and probing efforts. I also implemented a patch
to make Array.PMC handle keys recursively. I'm kind of testing the waters
here. If they are accepted, I plan to do more documentation and take a
stab at bringing the core key ops up to snuff with the PDDs. 

> After seeing all the bruhaha on the list about keyed-ness, I thought I'd
> try my hand at it, to see if I could get any farther before running up
> into the wall. :)
> Here's my own list of questions...first, the main problem with keys, as I
> see it, is that there is no guiding PDD or spec that describes how they
> should work. As such, people can only learn from the code. And that's a
> mess. While basic key support is there, lots of things are
> half-implemented, or incorrectly implemented, and it's quite hard to get a
> coherent picture. At least, imho.

Right. I'm sometimes refered to code which gives no indication of how it is 
ultimately supposed to work, but when told how its supposed to work, it
starts to click together =)
> Where are keys going to be stored? Currently, they exist only on the
> system stack, and key_new and key_clone are unused. Will we eventually
> have free-floating keys? Should we create support that causes them to be
> stored in small-object pools?

The Core Ops document (generated from the .ops file itself) documents
string registers being used to hold KEY *s. If there is conflicting code
or documentation, please point me at it. Looking at the string API, I'm
pretty sure that example needs revision =)
> I see that certain ops accept a type called KEY, which acts exactly like
> INT. And I mean *exactly*. It pulls data from INT registers, and even the
> 'k' and 'kc' type translate into accesses that look exactly like 'i' and
> 'ic'.

The KEY * structure holds a KEY_ATOM which holds an int, a string, a number
or a PMC. The KEY * has a KEY * next field. Each node on the linked list
is an index. When a PMC is used as an index, rather than its value
being taken and stored in the list, the PMC itself is referenced. This
way, when something like
is compiled to bytecode, it could (and this depends on the optimizer and
isn't currently implemented) be turned into a key once, and that key could
be used everytime that expression is used, no matter what the values of the
scalars. Using an array as a key would request the array as a number,
which, for a perl array would be the number of elements in the array.
In order words, no special treatment is given to non-scalar PMCs. I
haven't looked at the Perl 6 grammar much, but I'm sure there are other ways
to do that. Personally, I find high level languages boring.
This is tricky because nothing in the code or documentation (before my patch)
suggests this - this lurks purely in the archives and Dan and Simon's brains =)

> Are we planning on having key creation and mutation operations? Where will
> these keys be stored in order to operate on them? INT registers? (Sorta
> how it is now, although it looks wrong). STR registers? (Means they need
> to be headered, DOD'ed, and a larger per-key size). Will they get their
> own registers, maybe only 8 deep?

Chatting with Dan on IRC, "maybe". I think the community would have to form a
coherent, informed plan, as well as a consensus. However, they will not be the
primary method for creating keys - the optimizer/language bytecode compiler
would. As far as where they are stored, I'm going to do some random thing
when I submit a patch, then when people reject the patch they'll be forced to
tell me where they *should* be stored ;)
> What about the possibility for constructing/operating on keys using a Key
> PMC. We could convert to/from real KEYs by using the PMC. This is
> basically just a sidestep of the above problem.

I and other people suggested this as a simple way to make the idea of KEYs
workable. However, the benefit as a means of optimization would be very
limited if the primary way of constructing keys was as very transient things
constructed from the values of PMCs. As it stands, the only real corner
case is subscripts which themselves change in depth frequently - for
this, Parrot would just fall back on non KEY * key'd lookup methods.
This is no great loss.

> Currently, I see:
> set_keyed_integer:
> PK*
> PI*
> *PI
> *PK
> set_keyed:
> PS*
> *PS
> PN*
> *PN
> set:
> What's the point of set_keyed versus set_keyed_integer naming? There
> doesn't seem to be any overlap at all, so set_keyed_integer could safely
> be named set_keyed.

keyed_integer is a special case that has nothing to do with the KEY * datastructure
at all. An immediate, constant integer is used as a lookup. This lookup doesn't
recurse through PMCs - the datum is contained immediately within the PMC
we're invoking the operation on. This would happen when:
....for example. In the case of
..... this wouldn't work, and a KEY * structure would have to be created that contained
integers in its nodes.
> Can we safely remove "set PPPP", due to the relative inefficiency in
> constructing dummy PMCs to call it? Wouldn't it be more efficient to split
> the call into two "set PP*",and "setP*P" calls?

In previous posts, I've made some suggestions for lessoning the proliferation of
accessors without damage performance. Changing the implementation of
using keyed source and targets combined to fetching the PMCs to a scratch register
or fetching references to atomic values, then performing the operations on immediate values,
for example. 
> Thanks,
> Mike Lambert
I hate duplication of effort. If you tackle any of this, please keep me posted.
On the other hand, if you do go after, I'd be happy just to try and help you.

Sorry for any inaccuracies in this note... this information is not authoratitive.
At worst, it could be viewed as gross speculation =)


Thread Previous Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About