search

goto100 / xpath

DOM 3 Xpath implemention and helper for node.js
MIT License
223 stars 71 forks source link

Improve performance by applying binary search to nodes #108

Open cleydyr opened 2 years ago

cleydyr commented 2 years ago

I've been looking #97 and I've noticed that applying binary search to certain parts of the algorithm is possible taking into account that the node lists are fully ordered by the pair (lineNumber, columnNumber).

The performance has improved significatively and all existing tests continue to pass.

Can you take a look at this?

Thank you.

JLRishe commented 1 year ago

Hello, thank you for submitting this PR and I'm sorry I have left it unresponded for so long.

Your proposed change hinges on the use of the .lineNumber property on XML nodes, which is a library-specific feature of the @xmldom/xmldom package. It is not part of the DOM standard. The xpath package is designed to work with any standards-compliant DOM implementation, and I believe your change would make it such that this package would only work with DOMs from the xmldom package.

I'm not completely opposed to the idea of taking advantage of the lineNumber feature when it's available, but if that were to happen, your change would have to include sufficient feature detection to determine whether or not to use lineNumber and switch off between implementations appropriately.

JLRishe commented 1 year ago

Thanks to the conversation here I've learned that xmldom now supports compareDocumentPosition, which I believe would make your changes to nodeOrder largely irrelevant - your change currently assumes the use of xmldom, but the code you've added would never be reached if the DOM is from a recent versoin xmldom, because of the if statement on line 3004.

Regarding your changes to XNodeSet#add, it looks like they assume that the nodes in the node set are sorted, but there is no guarantee that they are sorted. In fact, I think they are deliberately left unsorted, for performance reasons, so using a binary search there would not be appropriate and would introduce incorrect behavior. Please let me know if you think I'm mistaken about that.