Skip to Content.
Sympa Menu

xom-interest - Re: [XOM-interest] XOMTestCase.assertEquals() too slow

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: xom-interest AT lists.ibiblio.org
  • Subject: Re: [XOM-interest] XOMTestCase.assertEquals() too slow
  • Date: Thu, 25 Jan 2007 21:44:57 -0800

It's not clear why XOMTestCase.assertEquals() should be orders of
magnitude slower than parsing or serialization. All of these should
clearly be O(N) overall.

Turns out the comparison is implemented with an O(N^2) algorithm. It stems from the (unnecessary) stateless nature of getNonTextNode (expected, i) as used from XOMTestCase.compareChildren():

// now compare everything that isn't text using the original
// element objects
for (int i = 0; i < nonTextNodes; i++) {
Node expectedChild = getNonTextNode(expected, i);
Node actualChild = getNonTextNode(actual, i);
assertEquals(message, expectedChild, actualChild);
}

Because the 8 MB test document is wide (database dump style), with some 50000 elements under the root node this leads to > 10^9 scan steps. And here, we're lucky, as in practise, 8 MB is considered small...

Wolfgang.






Archive powered by MHonArc 2.6.24.

Top of Page