[EMAIL PROTECTED] wrote on 01/04/2006 08:26:18 AM:
> Dear Xerces committers,
>
> I was evaluating the performance of the XML Schema enumeration language
> element and did detect that it does not scale very well, when the number
of
> enumeration data is scaled within a single enumeration. All other tested
> language elements do scale with the size of the input file (the xml
> instance).
<snip/>
> The reason for this N*N complexity lies in following method (Xerces
250):
>
> package org.apache.xerces.impl.dv.xs;
> public class XSSimpleTypeDecl implements XSSimpleType {
> private void checkFacets(ValidatedInfo validatedInfo) throws
> InvalidDatatypeValueException {
>
> ....
> //enumeration
> if ( ((fFacetsDefined & FACET_ENUMERATION) != 0 ) ) {
> boolean present = false;
> for (int i = 0; i < fEnumeration.size(); i++) {
> if (fEnumeration.elementAt(i).equals(ob)) {
> present = true;
> break;
> }
> }
> if(!present){
> throw new
> InvalidDatatypeValueException("cvc-enumeration-valid",
> new Object []
> {content, fEnumeration.toString()});
> }
> }
>
> .....
>
>
> The for-loop is executed N/2 times in average, if N is the number of
> enumeration data elements. This for-loop causes the non scaling
performance.
The code is quite different in Xerces 2.7.1 but it's still doing a linear
search.
> I would like to suggest to re-implement this part using a hastable
instead
> of a linear list. Would some committer be interested in implementing
this
> change?
For small values of N the hashtable might have poorer performance compared
to searching a list. I'd favor having a choice between a list and a
hashtable depending on the size of the enumeration. I implemented
something similar for attribute scanning (which wasn't scaling well) a
couple years back. I'll take a look at it. Thanks for bringing this to our
attention.
> Is this the "right" mailing list for this issue?
[email protected] might have been a better place to post this but
we're not that picky. :)
> I can provide more details if requested.
>
>
> Best regards
>
> Juergen Pill
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [EMAIL PROTECTED]
> For additional commands, e-mail: [EMAIL PROTECTED]
>
Michael Glavassevich
XML Parser Development
IBM Toronto Lab
E-mail: [EMAIL PROTECTED]
E-mail: [EMAIL PROTECTED]
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
