Crell, 2 months ago

@beberlei @nielsdos But what was the actual fix?

nielsdos, 2 months ago

@Crell @beberlei The important part was avoiding O(n) insertion of the namespace by adding it at the front of the "old namespace" list instead of the back. To be more specific, make sure it's added at the second position within the linked list, the actual front position wouldn't work due to API constraints of libxml (the first namespace must always be the XML namespace).
With the new DOM classes, all of this mess is avoided because we no longer need namespace reconciliation.

Crell, 2 months ago

@nielsdos @beberlei Ah, so the same class of issue as array_push() vs array_shift()? Avoid needing to reindex?

timwolla, 2 months ago

@Crell @nielsdos @beberlei No. Looking at the code it's a single-linked list. To insert at the end you need to traverse it in full. Effectively:

$item = $listStart;
while ($item->next !== null) {
$item = $item->next;
}
assert($item->next === null);
$item->next = $newItem;

Reindexing is not a thing for linked lists, because they don't have an index.

timwolla, 2 months ago

@Crell @nielsdos @beberlei With the fix roughly doing:

$item = $listStart;
$newItem->next = $item->next;
$item->next = $newItem;

avoiding the loop.