94471 - document order info should move from DOMHelper to Node

Status: VERIFIED FIXED

(Core :: XSLT, defect, P1)

Description

[Axel Hecht]

We take a great hit in the performance jimmy by having order info being separate
from the node. They gotta be one object.
Order info needs to conform to this:
Documents are ordered consistently, see last paragraph in
http://www.w3.org/TR/xslt.html#function-document.
This could be done with comparing the document urls, but we may live with just
comparing the pointers.
http://www.w3.org/TR/xpath#dt-document-order says that document order goes
element - namespace nodes - attributes - children.
The order info should support that. Attributes have an order given by the 
document. Though Jonas would like to postpone that. (Please don't)
See bug 94456 on ramblings about attribute nodes.

Axel

Comment 1

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Note to self: "attribute::*" needs to return a sorted nodeset

Comment 2

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

adding some dependencies. For standalone I need some way of walking from an 
attribute node to it's ownerElement and that code currently lives in the patch 
for bug 76070

Comment 3

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

pushing

Comment 4

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: Patch v1

Comment 5

[Axel Hecht]

why put txOrderInfo in XMLDOMUtils? I'd prefer to have them in dom.h and the 
node impls. (XMLDOMUtils should be just as evil as DOMHelper.)
Is the function signature of txOrderInfo::compareTo really good?
How about method CompareOrderInfo(txOrderInfo* first, txOrderInfo* second), or
even Nodes? DOM3 has greetings, compareTreePosition.
txOrderInfo* Node::getOrderInfo() is way to malloc happy. You create and delete
the array for each recursion. Get the nodes on a stack, and allocate the 
PRUint32 array once.
The actual node sorting algorithm shouldn't rely on whether we cache the order
info, or not. Get that routine close to DOM3, at least in steps, if at all 
possible. 

Axel

Comment 6

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

> why put txOrderInfo in XMLDOMUtils? I'd prefer to have them in dom.h and the
> node impls. (XMLDOMUtils should be just as evil as DOMHelper.)

The reason i didn't want to put it in there is that we need the same code for 
both standalone and module. However we will hopefully in the future be able to 
use some moz-functions to do documentorder so i agree it's the way to go.

> Is the function signature of txOrderInfo::compareTo really good?
> How about method CompareOrderInfo(txOrderInfo* first, txOrderInfo* second), or
> even Nodes? DOM3 has greetings, compareTreePosition.

Good idea. I created a compareDocumentPosition(Node* aOther) function (didn't 
want to use the same as DOM3 since we don't quite do the same thing). So the 
OrderInfo class is now just a private struct in Node/NodeDefinition. This 
should make it very easy to switch to a mozilla implementation once one exist.

> txOrderInfo* Node::getOrderInfo() is way to malloc happy. You create and
> delete the array for each recursion. Get the nodes on a stack, and allocate
> the PRUint32 array once.

Actually i just create the array for each recursion, they are not deleted until 
the node goes away. Consider if we create OrderInfo for 100 siblings, instead 
of getting the orderinfo for the ancestors of those siblings 100 times i only 
do it once. This is the usual speed vs. memory tradeoff problem. I would say 
that for now we should go with speed, but once we don't rely on orderinfo so 
heavily we could reevaluate (actually then we might even be able to get rid of 
orderinfo entierly...)

> The actual node sorting algorithm shouldn't rely on whether we cache the order
> info, or not. Get that routine close to DOM3, at least in steps, if at all 
> possible. 

Done. I now just do node1->compareDocumentOrder(node2)

Comment 7

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: ver 2

Comment 8

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

this missed the train

Comment 9

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

I said "this missed the train" damnit!

Comment 10

[Axel Hecht]

spawned bug 104219 for discussion of mozilla attribute nodes. That 
Attr::getChildIndex code looks bad, and we should be able to get that easily
without doing some extra bad foo in the wrappers.

Comment 11

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: sync with tip and take advantage of ns-dom in Attr::getChildIndex()

Comment 12

[Axel Hecht]

PRUint32 Node::getChildIndex(Node* aParent)
could be 
PRUint32 Node::getChildIndex(), right?
The non-nsIContent fallback in module Node::getChildIndex deals with which 
nodes?
Didn't apply yet.

Comment 13

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

The |Node* aParent| argument is for performance. We do an |getParentNode| 
in ::getOrderInfo, so i didn't wanna do it again in ::getChildIndex.

The non-nsIContent fallback is for children of attribute nodes, I.E. in 
practice it'll probobly never happen. It's one of those things that can be 
improved once nsIAttr exists.

Comment 14

[Axel Hecht]

"fold that function" was the answer to #1, IIRC.
How about a NS_ASSERTION for that code we shouldn't call?

Comment 15

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: fold ::getChildIndex into Node::getOrderInfo

Comment 16

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

folding done. Didn't add the assertion since it's no illigal, only unlikly that 
it happens. It'll only happen for expressions like "foo/@bar/text()"

Comment 17

[Axel Hecht]

the source/xml/dom/mozImpl/MozillaAttr.cpp chunk is not supposed to be there,
right? (Looks like a nsdoom merge foo)

Could we get two constructors for OrderInfo? one for no parent order, and one
with parent order, using , mSize(aSize) syntax? That gives less cycles, IIRC.

Node::OrderInfo* Node::getOrderInfo() could use early returns instead of breaks
probobly->probably
I doubt that we can do foo/@bar/text() anyway. At least for module.

Don't
for (i = 0; i < parent->getChildNodes()->getLength(); ++i) 
instead do the sibling iterator dance.

For the record, on my machine, the veiligheid testcase of bug 95249 speeds up
by a factor of 10 for standalone. *bang*

Comment 18

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

> the source/xml/dom/mozImpl/MozillaAttr.cpp chunk is not supposed to be there,
> right? (Looks like a nsdoom merge foo)

err, sorry about that, leftovers from ::getChildIndex()

> Could we get two constructors for OrderInfo? one for no parent order, and one
> with parent order, using , mSize(aSize) syntax? That gives less cycles, IIRC.

Actually OrderInfo is just a struct without any constructors these days, so no 
cycles are lost.

> Node::OrderInfo* Node::getOrderInfo() could use early returns instead of
> breaks

hrm, to be honest i don't like either one, but I like breaks better for some 
reason, can't really say why... Would it be ok to keep the breaks?

> probobly->probably

Done

> I doubt that we can do foo/@bar/text() anyway. At least for module.

Actually, it works in both standalone and module. Which makes us fail two xalan 
axes tests, since xalan seems to assume that attributes don't have children.

> Don't
> for (i = 0; i < parent->getChildNodes()->getLength(); ++i) 
> instead do the sibling iterator dance.

Done

> For the record, on my machine, the veiligheid testcase of bug 95249 speeds up
> by a factor of 10 for standalone. *bang*

YAO!! I didn't think that the speedgain would be that big since peterv found 
those swaped-arguments-on-hashing bug. But this is GREAT news!

Comment 19

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: address Axels comments

Comment 20

[Axel Hecht]

Comment on attachment 55339 [details] [diff] [review]
address Axels comments

please do the early returns, other than that
r=[e-mail]

Comment 21

[Peter Van der Beken [:peterv]]

Comment on attachment 55339 [details] [diff] [review]
address Axels comments

>+/*
>+ * Compares document position of this node relative to another node
>+ */
>+PRInt32 Node::compareDocumentPosition(Node* aOther)
>+{
>+  OrderInfo* myOrder = getOrderInfo();
>+  OrderInfo* otherOrder = aOther->getOrderInfo();
>+  if (!myOrder || !otherOrder)
>+      return -1;

I'd do

+  if (!mOrderInfo)
+      getOrderInfo();
+  OrderInfo* otherOrder = aOther->getOrderInfo();
+  if (!mOrderInfo || !otherOrder)
+      return -1;

to avoid the getOrderInfo() in the most common case.
Your call though, not a showstopper.

>+    mOrderInfo->mSize = parentOrder->mSize+1;
Spaces around +

>+    for (n = 0; n < parentOrder->mSize; n++)
>+        mOrderInfo->mOrder[n] = parentOrder->mOrder[n];
You could just memcpy

>+                mOrderInfo->mOrder[n] = index + kTxChildIndexOffset;
Maybe kTxChildIndexOffset + index?

>+                sorted.add(k+1, node);
k + 1

r=peterv with Pike's and my comments fixed.

Comment 22

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: address remaining comments

Comment 23

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

I didn't do the

> +  if (!mOrderInfo)
> +      getOrderInfo();

or

> Maybe kTxChildIndexOffset + index?

since i like the current way better. Everything else is done though

Comment 24

[Axel Hecht]

Comment on attachment 55487 [details] [diff] [review]
address remaining comments

NodeDefinition.cpp includes string.h, that shouldn't happen.
other than that, r=me

Comment 25

[Axel Hecht]

yeah, right, it should.
r=me

Comment 26

[Johnny Stenback (:jst)]

- In Node::~Node(), and in NodeDefinition::~NodeDefinition(), in stead of
manually deleting mebemrs of members before deleting the member itself, why not
add a destructor to the member and let it deal with tearing itself down?

- In Node::OrderInfo* Node::getOrderInfo(), you declare a local variable named
'nsID', which is also a the name of a struct in mozilla (nsIID is typedefed to
nsID), so you *might* get warnings from this.

Other than that, sr=jst

Comment 27

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

checked in... Thanks for reviews people!

Comment 28

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

er, i guess i should mark it fixed too

Comment 29

[Axel Hecht]

we didn't verify for a long time.
I really checked, so VERIFIED.