getElementsByTagName() is O(N^2)

[tstarling]

Description

DOMDocument::getElementsByTagName() and DOMElement::getElementsByTagName() return an iterator which does a linear time search for the current position, each time the position is moved to the next node. So completing the iteration of the node list takes O(N^2) time where N is the number of nodes in the list.

For example:

for ( $n = 1000; $n <= 16000; $n *= 2 ) {
	$doc = new DOMDocument;
	$root = $doc->createElement( 'root' );
	$doc->appendChild( $root );
	for ( $i = 0; $i < $n; $i++ ) {
		$root->appendChild( $doc->createElement( 'e' ) );
	}
	$t = -microtime( true );
	foreach ( $doc->getElementsByTagName( 'e' ) as $node );
	$t += microtime( true );
	print "$n\t$t\n";
}

resulted in this output:

1000    0.0031359195709229
2000    0.012067079544067
4000    0.050027132034302
8000    0.20300078392029
16000   0.76775693893433

It was likely faster prior to 3084e72. Since that commit in 2003, getElementsByTagName() is similar to the following pseudocode:

function getElementsByTagName( $root, $name ) {
	$i = 0;
	do {
		$node = findNextNode( $root, $name );
		for ( $j = 0; $node && $j < $i; $j++ ) {
			$node = findNextNode( $node, $name );
		}
		
		if ( $node ) {
			yield $node;
		}
		$i++;
	} while ( $node );
}

That commit was motivated by standards compliance. The standard says that the node list returned by getElementsByTagName() is live, that is, it must immediately reflect changes to the document. The standard has no concept of iteration, it only has an integer offset which can be passed to item(). The pseudocode above does correctly reproduce the quirks implied by the standard. For example:

$doc = new DOMDocument;
$doc->loadXML( '<root><e i="1"/><e i="2"/><e i="3"/><e i="4"/><e i="5"/><e i="6"/><e i="7"/><e i="8"/><e i="9"/><e i="10"/></root>' );
$root = $doc->documentElement;
foreach ( $doc->getElementsByTagName( 'e' ) as $node ) {
	print $node->getAttribute( 'i' ) . ' ';
	$root->removeChild( $node );
}
print "\n";

produces

1 3 5 7 9 

WebKit implements the standard efficiently by having an item cache and a length cache. The item cache allows efficient retrieval of an item which has an index close to the previously requested item. These caches are invalidated on tree mutation.

PHP has no concept of tree mutation event callbacks, so implementing this in PHP may be somewhat tedious.

PHP Version

PHP 8.2.6

Operating System

No response

[nielsdos]

Side note: I don't know what the other core people think, but I consider this as a feature request and as too risky to go into stable branches.

@tstarling
I created a proof-of-concept patch against the master branch that implements a coarse-grained caching strategy. It's nothing fancy. I just keep a counter that tracks how many times the document has been modified. Upon creation of an iterator, I store the current document's modification counter inside the iterator. If upon iteration the counter of the iterator and document match, then we know no modification took place and we can use the cached node. Otherwise, we'll fall back to the old slow codepath.
The reason I chose a counter is for performance: this is relatively lightweight, much more lightweight than the actual DOM modification themselves.
You might be wondering about counter overflow, this would indeed be a problem. I fixed this by using a saturating counter. If the counter is saturated then we will always take the old slow codepath. This means that even if 2^64 modifications occur on a 64-bit system, then the result will still be safe (albeit resulting in slower iteration).

I believe this is an acceptable trade-off. A more fine-grained approach is to have counters for each element tag type, but that has more impact on performance. The approach I propose is quite lightweight I think.
As you said, the libxml2 API does not expose a modification event callback, so I had to go through all the functions manually to see where an invalidation needs to occur.

There's still some TODOs for the patch to be ready, but you can find an early preview PR here: nielsdos#20
Let me know if this works for your use case.

[tstarling]

Side note: I don't know what the other core people think, but I consider this as a feature request and as too risky to go into stable branches.

Yes, I assume this would only be in master/8.3. #7478 was only allowed in PHP 8.1 which was then in RC status, and that was a fair bit simpler.

You might be wondering about counter overflow, this would indeed be a problem. I fixed this by using a saturating counter. If the counter is saturated then we will always take the old slow codepath. This means that even if 2^64 modifications occur on a 64-bit system, then the result will still be safe (albeit resulting in slower iteration).

At 1µs per modification it would take 585,000 years to overflow the counter, so I'm not terribly worried about overflow. I'm more worried about some unexpected code path causing tree modification without the counter being incremented -- it's fine for that to cause incorrect results, but it would be nice if we could have memory safety. Is it possible to keep the current node alive by incrementing the reference count in its dom_object?

Let me know if this works for your use case.

Today's use case needs foreach, and it also uses item() called with consecutive indexes although that could be replaced with foreach. I found out we have https://phabricator.wikimedia.org/T317255 which is a general tracking bug for "remove every usage of getElementsByTagName and fail CI if we ever see it again". For getElementsByTagName to be usable by naïve developers familiar with JS, we will need O(N) foreach, O(1) item() for consecutive indexes, and O(1) length.

But item() and length can be added later, building on your counter concept.

[tstarling]

There's still some TODOs for the patch to be ready, but you can find an early preview PR here: nielsdos#20
Let me know if this works for your use case.

I compiled it, it seems to work. Even without touching those item() calls, it reduces the time taken for my test case from 10.1s to 2.0s.

[nielsdos]

At 1µs per modification it would take 585,000 years to overflow the counter, so I'm not terribly worried about overflow. I'm more worried about some unexpected code path causing tree modification without the counter being incremented -- it's fine for that to cause incorrect results, but it would be nice if we could have memory safety. Is it possible to keep the current node alive by incrementing the reference count in its dom_object?

You're right. I amended it such that on 64-bit the overflow isn't checked for performance reasons.
The current node is already kept alive in the current code, so no use-after-free is possible.

Today's use case needs foreach, and it also uses item() called with consecutive indexes although that could be replaced with foreach. I found out we have https://phabricator.wikimedia.org/T317255 which is a general tracking bug for "remove every usage of getElementsByTagName and fail CI if we ever see it again". For getElementsByTagName to be usable by naïve developers familiar with JS, we will need O(N) foreach, O(1) item() for consecutive indexes, and O(1) length.

But item() and length can be added later, building on your counter concept.

I see the importance of improving the time complexity.
I'll work on item() and length too.