Skip to Content.
Sympa Menu

xom-interest - Re: [XOM-interest] Canonicalizer Performance

xom-interest AT lists.ibiblio.org

Subject: XOM API for Processing XML with Java

List archive

Chronological Thread  
  • From: Wolfgang Hoschek <wolfgang.hoschek AT mac.com>
  • To: John Cowan <cowan AT ccil.org>
  • Cc: 'Elliotte Harold' <elharo AT metalab.unc.edu>, 'xom-interest' <xom-interest AT lists.ibiblio.org>
  • Subject: Re: [XOM-interest] Canonicalizer Performance
  • Date: Mon, 28 Aug 2006 12:39:26 -0700

On Aug 28, 2006, at 12:16 PM, John Cowan wrote:

Michael Kay scripsit:

I don't think there's any "should" about it. There's no moral obligation for
software designers to handle pathological cases well (or at all); on the
contrary, one has to optimize for the most common case. I don't think it's
unreasonable to take the view that this example is pathological.

I agree, but I also would point out that the slope you are standing on is
dangerously slippery. TagSoup used to have a fixed limit on the length
of an attribute value; now the only limit is that of a Java String object,
because I found documents in the wild with tens of thousands of keywords,
often repetitive, in title attributes. It's one thing to handle such
cases inefficiently, quite another to fail to handle them at all.

We don't want to have parser authors claiming conformance to XML 1.0
and then failing because parameter entities are pathological (though
the Billion Laughs attack *is* pathological) ...


Assuming a small number of namespaces in scope at any given moment seems a very reasonable stance to me, based on common patterns seen in real world usage. I certainly woulnd't mind degradation in the pathologic case (large N), but I wouldn't design it to fail, by way of (somewhat arbitrary) static limits.

I should add that sometimes the worst-case can be handled almost as well as the best-case by changing the underlying data structure and associated algorithms, yielding more uniform run time behaviour at the expense of, say, 10% loss for the best-case. Optimization (and complexity) trade-offs regarding worst-case / best-case behaviour are on a case by case basis. For example, changing the NamePool from a fixed hash table to a form of dynamically resizable hash table (or having it overflow into a dynamic table for the pathologic case) may or may not fall into that category, I don't know.

Wolfgang.





Archive powered by MHonArc 2.6.24.

Top of Page