Improve using // in XPath performance

[naitoh]

When using // in XPath, the deeper the tag hierarchy, the slower it becomes due to the namespace acquisition process.
Caching namespace information improves performance when using // with XPath.

Benchmark (Comparison with rexml 3.4.1)

$ benchmark-driver benchmark/xpath.yaml Calculating ------------------------------------- rexml 3.4.1 master 3.4.1(YJIT) master(YJIT) REXML::XPath.match(REXML::Document.new(xml), 'a//a') 29.215 234.909 108.945 492.410 i/s - 100.000 times in 3.422925s 0.425697s 0.917898s 0.203083s Comparison: REXML::XPath.match(REXML::Document.new(xml), 'a//a') master(YJIT): 492.4 i/s master: 234.9 i/s - 2.10x slower 3.4.1(YJIT): 108.9 i/s - 4.52x slower rexml 3.4.1: 29.2 i/s - 16.85x slower 

• YJIT=ON : 4.52x faster
• YJIT=OFF : 8.04x faster

[tompng]

I have some concerns about maintainability because cache invalidation bug is hard to debug.
Namespace can be modified through add_attribute/delete_attribute and through attr_reader :attributes. It can bypass cache invalidation mechanism.

Here are some ideas of cache strategy.

1. Use a temporary cache and pass it as a method parameter

def node_test namespaces_cache = {} # Cache scope is enclosed in this method. # There is no need to worry about cache invalidation. call node.namespaces(namespaces_cache) to use the cache end def namespaces(cache = nil) if cache cache[self] ||= calculate_namespaces(cache) else calculate_namespaces end end

2. Automatically invalidate cache with immutable structure

def namespaces parent_namespaces = parent&.namespaces # If parent.namespaces or @attributes is changed, cache is automatically invalidated return @namespaces if parent_namespaces.equal?(@parent_namespaces) && @attrubutes.frozen? @attributes.freeze # Need to unfreeze before modifying @attributes @parent_namespaces = parent_namespaces @namespaces = @parent_namespaces.merge(@attributes).freeze end

[naitoh]

I have some concerns about maintainability because cache invalidation bug is hard to debug. Namespace can be modified through add_attribute/delete_attribute and through attr_reader :attributes. It can bypass cache invalidation mechanism.

Here are some ideas of cache strategy.

1. Use a temporary cache and pass it as a method parameter 

def node_test namespaces_cache = {} # Cache scope is enclosed in this method. # There is no need to worry about cache invalidation. call node.namespaces(namespaces_cache) to use the cache end def namespaces(cache = nil) if cache cache[self] ||= calculate_namespaces(cache) else calculate_namespaces end end

For maintainability, I have changed my mind about adopting policy 1 above.
Thanks!

[kou]

I have a bit concern about adding a cache (positional) argument to only some public namespace related APIs.

I feel that it may a bit ad-hoc approach. I'm not object this approach but can we improve our API?

For example, how about keeping a cache per document?

class XPathParser def parse path, nodeset path_stack = @parser.parse( path ) nodeset.first.document.enable_cache do # New document level cache is created and available in this block. # This API is thread unsafe. Users can't change this document in this block. match( path_stack, nodeset ) end end end

[naitoh]

I add Document#enable_namespaces_cache method to control whether caching is enabled or disabled.
What do you think?

[naitoh]

I have corrected the points you pointed out.
What do you think?

[naitoh]

I have corrected the points you pointed out.
What do you think?

[naitoh]

I have corrected the points you pointed out.
What do you think?

[kou]

Let's revisit this after #252. This implementation will be changed by #252.

[naitoh]

#252 merged, so I rebased this PR and updated.
What do you think?

[naitoh]

I have corrected the points you pointed out.
What do you think?

[naitoh]

I have corrected the points you pointed out.
What do you think?

[naitoh]

I have corrected the points you pointed out.
What do you think?

[naitoh]

I have corrected the points you pointed out.
What do you think?

[kou]

Thanks.