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

RE: fingertree (was: Discover data patterns or Create data pa

• From: "Michael Kay" <mike@s...>
• To: "'Dimitre Novatchev'" <dnovatchev@g...>,<xml-dev@l...>
• Date: Mon, 22 Sep 2008 08:04:25 +0100

> A good example of a problem that can be completely 
> eliminated: use a Finger-Tree-based sequence for all 
> sequences, then there is no need to worry to convert from one 
> sequence type to another (of course, the items still need to 
> be of the same type). Not to mention the gains in efficiency.
> 

Well, perhaps it was reading your blog that triggered me to use this
example. But I don't believe it's generally the case that for any given
interface, there is one implementation that will be optimum (or even "good
enough") across all usage patterns.

On the specific question of the fingertree and its possible use as an
implementation of XPath 2.0 sequences in memory, I'm a little sceptical.
Firstly, XSLT/XPath implementations try to avoid storing sequences in memory
wherever possible, relying instead on lazy evaluation and pipelining.
Secondly, where operations are performed on sequences, the original input
usually comes from a path expression - that is, an iterator over nodes in an
XML tree. In your performance measurements, to show the superiority of this
data structure, you had to suppress Saxon's optimizations by writing
obfuscatory code to defeat the optimizer. I would be more interested if you
could show that real programs benefit even when you allow the optimizer (and
lazy evaluation / pipelining) to do its work.

You also apply the data structure to storage of strings. For string
operations (such as substring and concat), Saxon isn't currently using lazy
evaluation or pipelining; but it could, and my instinct is that this could
match the benefits you are seeing for the kind of application you are using
as a test case.

(Reading this through, it sounds too dismissive. I'm not rejecting the idea,
I'm just expressing initial scepticism).

Michael Kay

• References:
  • Re: Discover data patterns or Create data patterns?
    • From: "Dimitre Novatchev" <dnovatchev@g...>