https://github.com/python/cpython/commit/e91c11449cad34bac3ea55ee09ca557691d92b53 commit: e91c11449cad34bac3ea55ee09ca557691d92b53 branch: 3.13 author: Miss Islington (bot) <[email protected]> committer: colesbury <[email protected]> date: 2025-12-24T13:26:07Z summary:
[3.13] gh-142145: Avoid timing measurements in quadratic behavior test (gh-143105) (#143140) Count the number of Element attribute accesses as a proxy for work done. With double the amount of work, a ratio of 2.0 indicates linear scaling and 4.0 quadratic scaling. Use 3.2 as an intermediate threshold. (cherry picked from commit 57937a8e5e293f0dcba5115f7b7a11b1e0c9a273) Co-authored-by: Sam Gross <[email protected]> files: M Lib/test/test_minidom.py diff --git a/Lib/test/test_minidom.py b/Lib/test/test_minidom.py index 69fae957ec7fc9..46249e5138aed5 100644 --- a/Lib/test/test_minidom.py +++ b/Lib/test/test_minidom.py @@ -2,7 +2,6 @@ import copy import pickle -import time import io from test import support import unittest @@ -178,23 +177,36 @@ def testAppendChild(self): def testAppendChildNoQuadraticComplexity(self): impl = getDOMImplementation() - newdoc = impl.createDocument(None, "some_tag", None) - top_element = newdoc.documentElement - children = [newdoc.createElement(f"child-{i}") for i in range(1, 2 ** 15 + 1)] - element = top_element - - start = time.monotonic() - for child in children: - element.appendChild(child) - element = child - end = time.monotonic() - - # This example used to take at least 30 seconds. - # Conservative assertion due to the wide variety of systems and - # build configs timing based tests wind up run under. - # A --with-address-sanitizer --with-pydebug build on a rpi5 still - # completes this loop in <0.5 seconds. - self.assertLess(end - start, 4) + def work(n): + doc = impl.createDocument(None, "some_tag", None) + element = doc.documentElement + total_calls = 0 + + # Count attribute accesses as a proxy for work done + def getattribute_counter(self, attr): + nonlocal total_calls + total_calls += 1 + return object.__getattribute__(self, attr) + + with support.swap_attr(Element, "__getattribute__", getattribute_counter): + for _ in range(n): + child = doc.createElement("child") + element.appendChild(child) + element = child + return total_calls + + # Doubling N should not ~quadruple the work. + w1 = work(1024) + w2 = work(2048) + w3 = work(4096) + + self.assertGreater(w1, 0) + r1 = w2 / w1 + r2 = w3 / w2 + self.assertLess( + max(r1, r2), 3.2, + msg=f"Possible quadratic behavior: work={w1,w2,w3} ratios={r1,r2}" + ) def testSetAttributeNodeWithoutOwnerDocument(self): # regression test for gh-142754 _______________________________________________ Python-checkins mailing list -- [email protected] To unsubscribe send an email to [email protected] https://mail.python.org/mailman3//lists/python-checkins.python.org Member address: [email protected]
