[fitz-dev] Ideas for name contexts (atom repositories)

[Raph Levien]

On Thu, Feb 20, 2003 at 05:30:08PM -0800, Raph Levien wrote:
> On Thu, Feb 20, 2003 at 08:59:59AM -0500, Antony Courtney wrote:
[snip]

> > Or (even better) you could just have a single intern table shared by all 
> > live dict instances, and use explicit allocation or deallocation of 
> > dict's along with presence/absence of keys in all live dicts as a basis 
> > for GC or refcounting.  Again, this would look just like callee-managed 
> > storage of the names to the client of the dict API, and hence should 
> > isolate the client from the GC/ref-counting complexity.
> 
> This is, I believe, (1b). The question of refcnt discipline pain is a
> good one. One reason for using names rather than strings in the dict
> API is to speed lookups. I think I may have missed the possibility of
> supplying dict API calls that use strings rather than interned names;
> then the refcnt management is hidden under the interface (insert takes
> ownership of the ref; lookup has a short-lifetime ref, and in fact you
> can avoid refcnt memory traffic on lookup; if the string doesn't exist
> in the name table, then the lookup will fail anyway).
> 
> > What do you think?
> 
> I'm still mulling it over.

I've put some more thought into it, and Tor and I have also hashed
through it in some detail (npi). I believe the (1b) approach is indeed
the winner.

In particular, while the (3) approach (12 string bytes in each dict
slot) is definitely appealing, I think it's not quite as good. One
specific instance is pdf content stream parsing and then dispatch of
the operator names: because this table is fairly large, it's going to
make a lot more sense to intern the parsed name once and look it up as
an int, than to do a bunch of string comparisons (no matter how
optimized) in the dict lookup. Another infelicity is that you still
have to have a method for dealing with names other than dictionary
keys, with all the complexity that entails.

Let me outline the chosen approach in a bit more detail.

The name table has essentially global scope. Its lifetime is basically
the same as a FitzCtx, and I'm tempted to actually stash it in there.

For direct access to atoms, the primary interface is an "intern" call,
which takes a C string as an argument (data/size as a variant), and
returns the atom. If the atom does not already exist in the table, it
is added. In either case, the refcnt of the atom is incremented; the
caller takes ownership.

Similarly, there's an unref call, with the usual semantics. After
doing a unref, in general the client cannot assume anything about the
atom value. I'm thinking of a debugging mode, similar in concept to
Electric Fence, so that unref'ing atoms forces the value to change,
and any attempt to reference a freed atom is immediately flagged.

Each dict owns the refs for all its keys. Most clients will use insert
and lookup methods that pass in C strings (or data/size). Through this
interface, no special refcnt handling is needed (whew!). As mentioned
before, the implementation of these methods can be a bit clever;
insert must increment the refcnt, but lookup can use a non-refcnt'ed
version of the intern method. If the atom doesn't already exist, then
the dictionary lookup must fail. If it does exist, then its lifetime
is short, so doesn't need to be refcnt'ed. In this way, there is no
write traffic to the name table for lookup operations.

As an optimization, clients expecting to look up the same keys a large
number of times may choose to intern the name, store it in some
longer-term context, use dict lookup (and insert) methods that take an
atom, and finally unref these names on destruction of the context.
Interning will be fast, so it's unlikely this optimization will result
in a significant performance gain, but it's there.

Similarly, dynamic objects of type "name" will hold a reference to
the atom, and will unref it on obj destruction. Thus, the same
mechanism is used for dict keys and other names.

For seat-of-the-pants performance estimation, I measured the intern
speed of last summer's Fitz prototype, at roughly 220ns per name.  By
comparison, zlib decompression is about 40ns per (decompressed)
byte. Thus, if all you're doing is decompressing a stream of names and
interning them, CPU load ought to be roughly equally balanced. This
suggests that we're neither wasting our time worrying about
performance of name processing, nor committing to horrible
inefficiency.

If anybody has serious objections to this scheme, now is a good time
to bring them up. Otherwise, I think we're good to go.

Raph