[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: String interning (Was: Binary XML == "spawn of t

• To: xml-dev@l...
• Subject: Re: String interning (Was: Binary XML == "spawn of the devil" ?)
• From: Tyler Close <tyler@w...>
• Date: Thu, 31 Jul 2003 21:57:52 -0400
• In-reply-to: <oprs67voa5ezizxn@localhost>
• References: <15725CF6AFE2F34DB8A5B4770B7334EE022DC6D0@h...> <E19iLFp-0000C3-00@c...> <oprs67voa5ezizxn@localhost>

On Thursday 31 July 2003 19:36, Mike Champion wrote:
> On Thu, 31 Jul 2003 17:46:32 -0400, Tyler Close <tyler@w...> wrote:
> > For an example of a binary format that supports efficient string
> > interning, without a penalty to generality, see:
> >
> > http://www.waterken.com/dev/Doc/code/
>
> Very interesting point/idea.

Thanks.

> AFAIK much of the overhead of XML text
> parsing that the binary infoset advocates complain about is in the Unicode
> encoding/decoding and raw string processing (e.g, looking at every
> character to see where an element ends rather than having a stored length).

The Waterken(TM) Doc code format uses a chunked representation for
encoding a string.  This provides the speed benefits of a length
prefix without creating an unlimited buffering requirement.

>  Likewise, a number of alternative infoset serializations use the "stream
> of SAX events" metaphor, that sounds a bit like what that document
> describes.

Same basic idea.

> But  that doesn't sound like "string interning" to me (and "interning" is
> not mentioned in that document).

Notice that all the meta data (ie: the string identifiers) are
stored in a set of string registers. Subsequent uses of a string
specify the index of the string to use. This results in each
string identifier being instantiated just once. The singleton
instance is the interned instance.

> I thought "interning" was more of a
> technique for keeping compiled code small by referencing redundant strings
> via their hash values.

It's more to do with fast lookup than memory savings. The hash
only gets computed once and equality checks are just pointer
comparisons. Same thinking is at work in the Doc code format.

> That basic idea is certainly used in all sorts of
> compression schemes ....but are you sure that's what the Waterken
> serialization model is doing?

Pretty sure. I designed it.

> I suppose the Waterken(TM) stuff is IP-encumbered up the wazoo, eh?

The license is specified on the Waterken(TM) Doc homepage. It is
Open Source. See:

http://www.waterken.com/dev/Doc/

Tyler

• References:
  • RE: Binary XML == "spawn of the devil" ?
    • From: "Bullard, Claude L (Len)" <clbullar@i...>
  • String interning (Was: Binary XML == "spawn of the devil" ?)
    • From: Tyler Close <tyler@w...>
  • Re: String interning (Was: Binary XML == "spawn of the devil" ?)
    • From: Mike Champion <mc@x...>

• Prev by Date: Re: reaching humans (was Re: Extract A Subset of a W3C XML Schema?)
• Next by Date: Re: reaching humans (was Re: Extract A Subsetof a W3C XML Schema?)
• Previous by thread: Re: String interning (Was: Binary XML == "spawn of the devil" ?)
• Next by thread: RE: Binary XML == "spawn of the devil" ?
• Index(es):
  • Date
  • Thread