Re: Xalan sort algorithm performance?

[Scott Boag/Cambridge/IBM]

It's a mergesort (see Robert Sedgewick's Algorithms book).  An issue may be the match-and-select it has to do, though these should be cached so that once the match-and-select is done, only the comparison need be made.  At one time I am under the impression that our sorting was comparatively pretty good.  But it's been I while since I've been in that code.

You might want to root around in the org.apache.xalan.transformer.NodeSorter code, or do a line profile of that class.

-scott

Martin Dengler <[EMAIL PROTECTED]> wrote on 03/20/2003 04:17:27 PM:

> Hi,
>
>    Please yell if this is an FAQ or my googling skills need help.
>
>    What sorting algorithm does Xalan use -- and what is the algorithm(s)
> runtime and memory footprint in big-O notation?
>
>    I am using Xalan to sort large XML documents: approx 3 levels deep of
> a tree with 2-20,000 first child (attached to root) nodes and 30
> grandchildren per child node.  Sorting is done on an attribute of the
> grandchild nodes.  The performance -- especially in memory usage -- is
> abysmal: 10-60 seconds sort time, memory usage is at least O(n^2).
>
>    I've read the w3c performance pointers, but cutting the document down
> and doing fewer transforms really doesn't cut it (neither are applicable
> to a one-pass sort of a large document).
>
>    Are there any ways to change the sort algortihm's memory/runtime
> behavior?
>
> Thanks,
> Martin
>
> PS -- test specs: Xerces, Xalan (latest), Solaris 2.8, JVM 1.2.2_07, Sun
> E450, 2GB real mem, 1GB JVM heap, 2x450mhz processors.
> [attachment "signature.asc" deleted by Scott Boag/Cambridge/IBM]