226124 - Cleanup transformiix walkers

Status: NEW

(Core :: XSLT, defect, P3)

Description

[Peter Van der Beken [:peterv]]

Follow up bug to bug 151002. I postponed taking care of some reviewer's comments
and there's some other changes I wanted to do after landing that bug's patch.

Comment 1

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

Comments and thoughts 


The old way of merging nodesets (txNodeSet::add) is AFAICT faster. The new code
hopes that the nodes in the resulting nodeset comes in chunks bigger then one
from both nodesets, which on average isn't the case.


In txNodeSet::indexOf:
You could get rid of |counter| and just return |pos - mStart|. The |mStart ==
mEnd| test isn't really needed.


Would it be better to make the txXPathNode copy-ctor public then to make
txNodeSet a friend?


I'm slightly nervous about txForwardContext holding on to a reference rather
then containing a txXPathNode. For example if they use a node from a nodeset the
nodeset can't be modified before the context dies. txSingleNodeContext has the
same issue.


In module txXPathNodeUtils::getOwnerDocument:
You could even want to try to go to a parent and get the document through there
if aNode doesn't have a nodeinfo.


In module txXPathNodeUtils::comparePosition
We should probably look into a more "correct" handling for orphaned nodes as
long as it doesn't affect performance of "normal" nodes.


The pattern:
nsRefPtr<txNodeSet> newSet;
recycler->getNonSharedNodeSet(oldSet, newSet);
res->addAndTransfer(newSet);

is supoptimal if oldSet was shared (clone and then transfer out from). A better
solution would be

if (oldSet->isShared())
  res->add(oldSet);
else
  res->addAndTransfer(oldSet);


Is addAndTransfer really buying us anything? Or is the overhead of
function-pointer functioncalls costing us more then just only doing add. I might
be worth investigating removing |add| and always do |addAndTransfer| by cloning
shared nodesets first. It might also be possible to speed up all alternatives by
creating a function in txXPathNodeUtils that could copy a list of nodes (would
do memcpy for our implementations).


Is the mark-n-sweep speeding things up or is the extra memory-alloc costing more
then getting a new nodeset (which should be recycled most of the time).


Right now having txXPathNode and txXPathNodeUtils separated doesn't buy us
anything since both the copy-ctor and the dtor is called in "cross-walker" code.
Either we could create more functions in txXPathNodeUtils and really typedef
txXPathNode to Node* on standalone. Or we could go full ahead and move the
functions in txXPathNodeUtils to txXPathNode. This should not create any
additional code, we'd just let the compiler (not optimizer) do the job for us.


We should have an txXPathNodeUtils::isOfType that tests if a node is a certain
type. Module can do that a lot faster then getting the node-type. If we want it
really fast we can even have ::isElement, ::isAttribute etc functions. Another
way of doing it is to have an inlined ::isOfType and rely on the optimizer to
optimize things into the same code as ::isElement etc.


Module txXPathNodeUtils::getLocalName could be written slightly faster by
calling GetNodeInfo rather then IsContentOfType(nsIContent::eELEMENT). That will
avoid a virtual call in case the content is an element and not make a difference
otherwise.

Comment 2

[Axel Hecht]

nodetype stuff is bug 227003

Comment 3

[Peter Van der Beken [:peterv]]

> In txNodeSet::indexOf:
> You could get rid of |counter| and just return |pos - mStart|. The |mStart ==
> mEnd| test isn't really needed.

Done.

> Would it be better to make the txXPathNode copy-ctor public then to make
> txNodeSet a friend?

No, but I've added a clone function in txXPathNodeUtils.

> I'm slightly nervous about txForwardContext holding on to a reference rather
> then containing a txXPathNode. For example if they use a node from a nodeset
> the nodeset can't be modified before the context dies. txSingleNodeContext has
> the same issue.

I still don't think this needs to change.

> In module txXPathNodeUtils::comparePosition
> We should probably look into a more "correct" handling for orphaned nodes as
> long as it doesn't affect performance of "normal" nodes.

What do you propose as more "correct"?

> Right now having txXPathNode and txXPathNodeUtils separated doesn't buy us
> anything since both the copy-ctor and the dtor is called in "cross-walker"
> code. Either we could create more functions in txXPathNodeUtils and really
> typedef txXPathNode to Node* on standalone. Or we could go full ahead and move
> the functions in txXPathNodeUtils to txXPathNode. This should not create any
> additional code, we'd just let the compiler (not optimizer) do the job for us.

I disagree since I want to keep txXPathNode abstract. (for example to be able to
typedef txXPathNode to Node* in standalone)

> Module txXPathNodeUtils::getLocalName could be written slightly faster by
> calling GetNodeInfo rather then IsContentOfType(nsIContent::eELEMENT). That
> will avoid a virtual call in case the content is an element and not make a
> difference otherwise.

Done.

I tried doing add always (no function-pointers), it gave a small increase in
performance in XSLTBench, though I doubt the timing is accurate enough to be
sure. I'm attaching a patch that redoes addAndTransfer (renaming it to add,
which I don't like but I'm still looking for a better name), it also gave a
small increase, again no idea how accurate that is. I'd appreciate comments.
Next thing I'll go measure removing the changes in the add logic and removing
mark-n-sweep I guess. Working on Transformiix used to be fun.

Trunk
chess-fo/chess.xsl	587.38 ms	19971 ms	7.56
jenitennison/page.xsl	42.18 ms	23075 ms	0.91
jenitennison/markme.xsl	53.20 ms	9895 ms	1.44
schematron/schematron-basic.xsl	14.65 ms	11938 ms	0.55
schematron/wai.xsl	4.82 ms	16647 ms	0.39
spec-html/xmlspec.xsl	934.48 ms	21493 ms	47.22
mathml/mathmlc2p.xsl	26.11 ms	20363 ms	2.66
dsd/article2html.xsl	18.11 ms	17291 ms	0.77
nitf/nitf-stylized.xsl	12.29 ms	12067 ms	0.46
rdf/rdft.xsl	5.35 ms	13157 ms	0.49
recipes/recipes.xsl	17.35 ms	14471 ms	0.57
sp.xsl/sp.xsl	10.08 ms	25442 ms	0.38
topic-xtm/cogx2xtm.xsl	16.98 ms	12820 ms	0.71
Total: 218630 ms

No function-pointers
chess-fo/chess.xsl	589.47 ms	20042 ms	7.44
jenitennison/page.xsl	42.07 ms	23013 ms	0.96
jenitennison/markme.xsl	53.08 ms	9872 ms	1.23
schematron/schematron-basic.xsl	14.54 ms	11853 ms	0.53
schematron/wai.xsl	4.75 ms	16405 ms	0.45
spec-html/xmlspec.xsl	920.91 ms	21181 ms	6.79
mathml/mathmlc2p.xsl	26.02 ms	20297 ms	1.10
dsd/article2html.xsl	18.01 ms	17201 ms	0.45
nitf/nitf-stylized.xsl	12.26 ms	12035 ms	0.86
rdf/rdft.xsl	5.31 ms	13050 ms	0.47
recipes/recipes.xsl	17.25 ms	14389 ms	0.46
sp.xsl/sp.xsl	10.07 ms	25429 ms	0.38
topic-xtm/cogx2xtm.xsl	16.88 ms	12741 ms	0.70
Total: 217508 ms

Current patch
chess-fo/chess.xsl	584.09 ms	19859 ms	8.17
jenitennison/page.xsl	42.63 ms	23317 ms	0.84
jenitennison/markme.xsl	52.89 ms	9838 ms	1.31
schematron/schematron-basic.xsl	14.37 ms	11709 ms	0.50
schematron/wai.xsl	4.70 ms	16216 ms	0.46
spec-html/xmlspec.xsl	927.87 ms	21341 ms	100.70
mathml/mathmlc2p.xsl	25.48 ms	19875 ms	3.78
dsd/article2html.xsl	17.75 ms	16955 ms	0.54
nitf/nitf-stylized.xsl	12.18 ms	11956 ms	0.85
rdf/rdft.xsl	5.25 ms	12905 ms	0.43
recipes/recipes.xsl	17.14 ms	14294 ms	0.45
sp.xsl/sp.xsl	10.00 ms	25247 ms	0.39
topic-xtm/cogx2xtm.xsl	16.75 ms	12647 ms	0.72
Total: 216159 ms

Comment 4

[Peter Van der Beken [:peterv]]

Attachment: v1

Comment 5

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

Nothing of what i commented on were requirements. Everything that I thought was
neccesary we delt with in the original bug, i wouldn't have given my r=
otherwise. I just wanted to get my non-critical thoughts in print for you guys
to evaluate (and so it wouldn't get lost in case we wanted to squeeze more
performance). I'm sorry that i wasn't clear on that.

Comment 6

[Axel Hecht]

> Is the mark-n-sweep speeding things up or is the extra memory-alloc costing
> more then getting a new nodeset (which should be recycled most of the time).

The recycled nodeset is not guaranteed to have enough memory to hold the new
nodeset. And this depends highly on the ratio of original nodes to new nodes, too.
I'd not evaluate this before we find out what to do with txPredicatedNodeTest,
though.

> I disagree since I want to keep txXPathNode abstract. (for example to be able 
> to typedef txXPathNode to Node* in standalone)

typedef doesn't work, I tried that back when I created the first standalone 
walker. typedef doesn't mix with 
class txXPathNode;
that we use at a few places.

Comment 7

[Peter Van der Beken [:peterv]]

> The old way of merging nodesets (txNodeSet::add) is AFAICT faster. The new
> code hopes that the nodes in the resulting nodeset comes in chunks bigger then
> one from both nodesets, which on average isn't the case.

Old add
chess-fo/chess.xsl	588.71 ms	20016 ms	11.33
docbook-xsl/html/docbook.xsl	skipped
jenitennison/page.xsl	43.13 ms	23592 ms	0.83
jenitennison/markme.xsl	50.29 ms	9354 ms	0.94
schematron/schematron-basic.xsl	14.53 ms	11840 ms	0.59
schematron/wai.xsl	4.60 ms	15864 ms	0.50
spec-html/xmlspec.xsl	865.96 ms	19917 ms	40.03
xsltdoc/xsltdoc.xsl	skipped
mathml/mathmlc2p.xsl	25.06 ms	19543 ms	2.44
dsd/article2html.xsl	17.30 ms	16522 ms	1.26
nitf/nitf-stylized.xsl	11.83 ms	11619 ms	0.54
rdf/rdft.xsl	5.20 ms	12766 ms	0.42
recipes/recipes.xsl	17.01 ms	14185 ms	0.63
sp.xsl/sp.xsl	9.62 ms	24285 ms	0.53
topic-xtm/cogx2xtm.xsl	16.54 ms	12491 ms	0.62
Total: 211994 ms

New add
chess-fo/chess.xsl	583.50 ms	19839 ms	9.41
docbook-xsl/html/docbook.xsl	skipped
jenitennison/page.xsl	42.34 ms	23162 ms	0.76
jenitennison/markme.xsl	50.03 ms	9305 ms	0.87
schematron/schematron-basic.xsl	14.49 ms	11812 ms	0.53
schematron/wai.xsl	4.62 ms	15939 ms	0.49
spec-html/xmlspec.xsl	854.22 ms	19647 ms	5.09
xsltdoc/xsltdoc.xsl	skipped
mathml/mathmlc2p.xsl	25.00 ms	19497 ms	2.84
dsd/article2html.xsl	17.32 ms	16541 ms	0.68
nitf/nitf-stylized.xsl	11.86 ms	11651 ms	0.50
rdf/rdft.xsl	5.20 ms	12780 ms	0.40
recipes/recipes.xsl	16.98 ms	14163 ms	0.79
sp.xsl/sp.xsl	9.62 ms	24282 ms	0.51
topic-xtm/cogx2xtm.xsl	16.45 ms	12423 ms	0.57
Total: 211041 ms

Comment 8

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

Regarding more correct handling for orphan subtrees:

What I mean by correct handling are two things:
* Nodes in a single orphan subtree should have a relative order when compered
  to other nodes in that same subtree. This order is decided by the
  "document-position" in that subtree.

* Given two different subtrees, A and B, either all nodes in A should be after
  all nodes in B, or all nodes in B should be after all nodes in A.

Or to put it shortly; an orphan subtree should act like a normal tree. The
relative order of subtrees and trees doesn't matter.

The reason for this is so that you can perform XPath or XSLT on a subtree.

The following seems like problems in the current code:

* If the two nodes are both in the same orphaned subtree we will just compare
  their root-nodes (which of course will be the same).

* The two |if|-statments on 766 and 770 assumes that both nodes are in the same
  tree and doesn't take into account that the other node might be an orphan.


We could simplify the code a bit which should make it easier to fix the two
above problems. If the |document| and |otherDocument| tests were removed from
line 761 we would place all orphan subtrees before all real trees, which IMHO is
an ok thing to do. After that you'd know that either both nodes live in the same
tree, or both nodes come from orphan subtrees.

Comment 9

[Peter Van der Beken [:peterv]]

Attachment: v1.1

Comment 10

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

The added @@ -767,6 +762,20 @@ block isn't needed if you remove the 
|document && otherDocument|

test further up.

Comment 11

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

err, in modules txXPathNodeUtils::comparePosition that is.

Comment 12

[Axel Hecht]

+class txSpecialXPathNode
+{
+public:
+    operator PRBool() const
+    {
+        return mValid;
+    }

...

That is a pretty evil hack, IMHO. You end up with checking a document reference,
which only works due to the operator overload.
The code still looks buggy though (wasn't that one of the infamous reasons
why operator overloading is bad?).
I'd rather go without that. The one place where I saw that, you actually knew
if you succeeded a few lines above, you could have just set rv there.
Much nicer, and it persists the info that that rv once had (if it did, don't 
recall, and do I wanna search for if()s? naah)

Comment 13

[Peter Van der Beken [:peterv]]

Attachment: v1.2

Comment 14

[Axel Hecht]

Comment on attachment 174169 [details] [diff] [review]
v1.2

Could you clear up the ownership in txExecutionState::mLoadedDocuments?

In txXPathNode.h, could you move function definitions available in both
versions outside the #ifdefs?

I still need to actually apply that patch to a tree to understand the nodeset
diffs, though.

Comment 15

[Peter Van der Beken [:peterv]]

(In reply to comment #14)
> (From update of attachment 174169 [details] [diff] [review] [edit])
> Could you clear up the ownership in txExecutionState::mLoadedDocuments?

I've added some comments. The basic problem is that we want the hash to own all
the documents except for the source document, which is owned by the caller. We
could solve this differently by making the standalone processor not own its
source document (module doesn't have the problem because its documents are
refcounted). It's not trivial though, so I'd like to keep it for now.

Comment 16

[Peter Van der Beken [:peterv]]

Attachment: v1.3

Comment 17

[Axel Hecht]

Comment on attachment 195403 [details] [diff] [review]
v1.3

Could I get an merged-to-tip version of this?
txMozillaXPathTreeWalker.cpp and txXSLTPatterns.cpp don't apply anymore :-(.
Sorry.

Comment 18

[Peter Van der Beken [:peterv]]

Attachment: String changes