Requirements on Optimizers

[David Lee]

Interesting idea
In the java and c++ case the libraries are more implementations then specifications
And in particular the collection classes (both Languages) the classes themselves
Are architected around separating specific algorithm models from abstract non algorithmic interfaces.

I don't see quite the same thing in either xquery languages or stdlibs

However I do see it in implementation extensions

Maybe when xquery libs achieve the same maturity as java and c++ libs well start to see algorithmic metrics as part of the docs if not the specs  

David A Lee
 

On Jul 25, 2010, at 12:10 AM, Pavel Minaev <http://x-query.com/mailman/listinfo/talk> wrote:

> Nonetheless it's fairly common, though typically not in the languages
> themselves, but rather libraries. ISO C++ defines algorithmic
> complexity for both standard containers and standard algorithms, for
> example. Java does the same for its collection library.
> 
> In case of XQuery, the language itself, being more high-level, covers
> most of the same ground as collection/algorithm libraries in other
> languages, so it seems reasonable that it should be subject to similar
> treatment.
> 
> On Sat, Jul 24, 2010 at 8:58 PM, David Lee <http://x-query.com/mailman/listinfo/talk> wrote:
>> I don't believe it is appropriate in am language spec to require any such thing
>> That is the realm of implementations
>> 
>> Sooo many holes to fall into when specs start specifying performance concerns
>> 
>> 
>> David A Leet
>> 
>> On Jul 24, 2010, at 11:26 PM, Pavel Minaev <http://x-query.com/mailman/listinfo/talk> wrote:
>> 
>>> On Sat, Jul 24, 2010 at 3:22 PM, Michael Kay <http://x-query.com/mailman/listinfo/talk> wrote:
>>>> Statements like "will actually be evaluated" turn out to be rather difficult
>>>> to test, and they aren't always meaningful in the context of a particular
>>>> implementation. What do you do, for example, if the 1000000 is actually $N,
>>>> and [5] is actually [$M], and $N is known statically, and the implementation
>>>> decides to evaluate
>>>> 
>>>> (for $i in 1 to $N return $i * $i)
>>>> 
>>>> at compile time into an array? You then get constant performance
>>>> (independent of $M or $N) at run-time but a higher cost at compile time and
>>>> more memory used by the compiled code. Is the spec really going to say
>>>> whether or not that's an acceptable strategy for implementors to adopt?
>>> 
>>> I think the spec should not be defined in terms of what gets evaluated
>>> when (and whether), but rather in terms of algorithmic complexity. So
>>> for your example, the requirement is that the upper bound is O($M) -
>>> this is of course deliberately ignoring the cost of calculating the
>>> individual items. Any strategy that can provably match that (or be
>>> faster) is fine. And, of course, this is strictly about runtime -
>>> compile-time costs (assuming there is a "compile", even) are best left
>>> for implementations to define for themselves - it's not something that
>>> matters for portability.
>>> 
>>>> I agree predictability of performance is a very significant problem - not
>>>> just across products, but within a single product. Part of the answer, I
>>>> think, is to make performance less reliant on good optimization. In XSLT,
>>>> the key() function goes a long way towards this: by giving programmers a
>>>> tool to control when indexes are built and used, performance of many join
>>>> constructs becomes much more predictable even though the spec doesn't
>>>> actually mandate how key() is implemented (no-one would buy a product that
>>>> implemented it as a serial search).
>>> 
>>> Indeed, something analogous to fn:key - though for XQuery it would
>>> probably make more sense to have some kind of a "sequence index" data
>>> type and a set of related functions (to create indices from sequences,
>>> and to query them) would be a very interesting addition, and would
>>> leave practically no rope for the optimizer to hang itself. Of course,
>>> it would, at the same time, hand over plenty of the same to the
>>> programmer... but at least then there is a _portable_ way for anyone
>>> out there to make their own choice :)
>>> _______________________________________________
>>> http://x-query.com/mailman/listinfo/talk
>>> http://x-query.com/mailman/listinfo/talk
>> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://x-query.com/pipermail/talk/attachments/20100725/33ca5dde/attachment.htm