gh-63416: Speed up assertEqual on long sequences #27434

jdevries3133 · 2021-07-28T23:02:16Z

This incorporates changes started by @eamanu:

Fix bpo-19217
fix unnecessary space and solve @gpshead comments
fix test
bpo-19217: fix failing test in unittest's test suite
bpo-19217: add blurb

Additionally, I added two commits to make this ready-to-merge

revert changes to difflib.py
add regression test

https://bugs.python.org/issue19217

Issue: Calling assertEquals for moderately long list takes too long #63416

…-assertEq

sweeneyde · 2021-07-29T14:34:18Z

I'd recommend changing the PR title to something affirmative, e.g. "Speed up assertEqual on long sequences"

jdevries3133 · 2021-07-29T17:44:47Z

I'd recommend changing the PR title to something affirmative, e.g. "Speed up assertEqual on long sequences"

I will! That's definitely more descriptive, thank you.

ambv

To sum up comments:

Please add the new variant to assertMultiLineEqual as well;
Please adapt the test cases to be pathological (you can use my suggestion) with the original code for both strings and lists;
Please change the test to simply execute the diff, don't measure time at all. If it becomes too slow, we'll know just by the fact it became super slow.

Lib/unittest/test/test_case.py

bedevere-bot · 2021-07-29T19:3 8000 2:44Z

A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated.

Once you have made the requested changes, please leave a comment on this pull request containing the phrase I have made the requested changes; please review again. I will then notify any core developers who have left a review that you're ready for them to take another look at this pull request.

And if you don't make the requested changes, you will be poked with soft cushions!

jdevries3133 · 2021-07-30T20:49:18Z

Please add the new variant to assertMultiLineEqual as well

@ambv before I go any further, I went ahead and made the change from ndiff to unified_diff in a different branch on my fork. Look at the README:

https://github.com/jdevries3133/cpython/tree/[bpo-19217](https://bugs.python.org/issue19217)-ideas

By the way, there is one other problematic use of ndiff in assertDictEqual:

cpython/Lib/unittest/case.py

Lines 1134 to 1136 in 48a6255

    
           diff = ('\n' + '\n'.join(difflib.ndiff( 
        
                          pprint.pformat(d1).splitlines(), 
        
                          pprint.pformat(d2).splitlines())))

Reproducing the issue is similar to the others:

import unittest

class TestDictDiffSlow(unittest.TestCase):

    def test_slow_assert_equal_dict(self):
        d1 = { i : i * 2 for i in range(10000) }
        d2= { i : i for i in range(10000) }
        self.assertDictEqual(d1, d2)


if __name__ == '__main__':
    unittest.main()

I'm happy to fix all the failing tests, and there are quite a few, but the change from ndiff to unified_diff does change the diff messages a lot, as well. I know you noted this and are aware of it, but you can look at that branch to see more examples. Here are a few:

Before:

- Once upon a time,
?            ^^^^
+ Once upon an age,
?            ^^^^
  there was a boy named Tim.
- Here had some tiny knuckles
- and in his pocket, a slim jim.+ He had some wise old sages
+ who told him how to swim.

After:

AssertionError: 'Once upon a time,\nthere was a boy named Tim.\nHere [50 chars]jim.' != 'Once upon an age,\nthere was a boy named Tim.\nHe ha[44 chars]wim.'
--- +++ @@ -1,4 +1,4 @@
-Once upon a time,
+Once upon an age,
 there was a boy named Tim.
-Here had some tiny knuckles
-and in his pocket, a slim jim.
+He had some wise old sages
+who told him how to swim.

Before:

AssertionError: {'foo': 1, 'bar': 2} != {'foo': 2, 'bar': 2}
- {'bar': 2, 'foo': 1}
?                   ^

+ {'bar': 2, 'foo': 2}
?

After:

AssertionError: {'foo': 1, 'bar': 2} != {'foo': 2, 'bar': 2}
--- 
+++ 
@@ -1 +1 @@
-{'bar': 2, 'foo': 1}
+{'bar': 2, 'foo': 2}

Other Options

I don't know if these are any good, but maybe there are other options to fix this bug:

Check size of Input

Check size of input value before passing to diff.ndiff. Use diff.unified_diff only for large inputs

This has the advantage of reducing test breakage
It also maintains the nice ergonomics of ndiff in most cases

Make `ndiff` a Better Generator

Patch ndiff to generate output (behave like a generator)

ndiff currently returns a generator, but it never seems to yield with the problematic inputs.
if it could yield output continuously without getting locked up, we could do this:

output_lines = []
for line in difflib.ndiff(a, b):
    if len(output_lines) > self.maxDiff:
        break
    output_lines.append(line)

Łukasz, I don't really understand enough to know if these are really paths forward, or if it's better to just forge ahead with replacing ndiff with unified_diff everywhere. I'm hoping you can provide some guidance!

ambv · 2021-08-02T16:51:32Z

Good thinking about having a threshold above which we can switch to unified_diff from ndiff. However, the problem isn't size of input but number of changes between them. As you saw, your original example was a list of 10,000 elements with a single change and that worked sub-second for both algorithms. The example I gave is a 1,000 elements and takes 150s because there are 10 changes.

I guess what I'm saying is that it isn't at all clear how our threshold should be calculated. How about this:

since unified_diff is always fast, just calculate it;
if there are fewer than, say, 25 lines starting with - or + in the resulting diff, then also run ndiff and return that instead.

As part of testing here you should deliberately try to come up with examples where the "25 diff lines" limit is still too big. If you can't find any after a good round of trying to break it, then maybe you can double the limit. And try breaking it then.

I mean, you can spend as much or as little time on this as you wish. But I agree with you that we can tweak this into a solution that is both fast and preserves nice diffs for most use cases.

…assertEq

* Now, we switch between difflib.ndiff and difflib.unified_diff based on input size. * Threshold is sort of arbitrary, but seems to be working in the limited test cases I've written * The full test suite is passing, with only very minor tweaks to existing tests!

jdevries3133 · 2021-08-04T03:44:20Z

@ambv I converted this to a draft, but I do have an implementation of what we discussed now. You'll notice a few # ambv: ... comments sprinkled throughout. It seems like the idea is working well in general. Test breakage is very minimal, and tests are passing. I'm looking forward to hearing what you think, and thanks!

TODO

This is why I've marked it as a draft:

finish writing test_ndiff_to_unified_diff_breaking_point_varied_inputs
brainstorm and test more edge cases
incorporate feedback on this initial draft

ambv

I like where this is going. Looking forward to the next iteration.

Lib/unittest/case.py

Lib/unittest/test/test_case.py

tim-one · 2022-02-08T03:43:13Z

And another, to show that ndiff can easily be provoked into cubic time. On my box, it takes over 2 minutes to complete the case of 2 inputs with 512 lines each, where each line has under a dozen characters. But this is a best case for unified_diff, since no two lines are equal.

from difflib import ndiff
from time import perf_counter as now
import sys
sys.setrecursionlimit(2000) # so the 512 case completes
count = 16
while True:
    ax = [f"a{i:010d}" for i in range(count)]
    bx = [s.replace("a", "b") for s in ax]
    start = now()
    ignore = list(ndiff(ax, bx))
    finish = now()
    print(count, finish - start)
    count *= 2

6D40

gpshead

It sounds like we're basically trading one regressive performance situation for another.

Someone can always wind up unhappy. Without the ability to bail out if computation is taking too long, we should take Tim's suggestion of going to a linear "first differing element" highlight approach when inputs are "too large", followed by our generic a != b printing code.

I blindly suggest: max(len(a), len(b)) > 500 prevent calling unified_diff and max(len(a), len(b)) > 200 prevents calling ndiff. Just based on the worst case timings.

those default values used to tune that could be TestCase attributes that people could override themselves if they want (assumed to be rare), much like maxDiff is today.

more to do

tim-one · 2022-02-08T19:57:58Z

You can get sharper estimates by cheating a bit: build your own SequenceMatcher object:

sm = difflib.SequenceMatcher(None, a, b)

That much is worst-case linear time.

Then

b2j = sm.b2j
sum(len(b2j[line]) for line in a if line in b2j)

is the total number of times a unified diff will go around its innermost loop. It's cheating because b2j is an unadvertised implementation detail. In the dead-simple quadratic-time unified diff example I posted, that will return len(a)**2. Decide accordingly. In the cubic-time ndiff example I posted, it will return 0.

If that's "cheap enough", you can go on to take a guess at worst-case ndiff time (which is never cheaper than unified diff time). Go through sm.get_opcodes(), and look at each "replace" opcode. All and only those block pairs are attacked by ndiff (beyond what a unified diff does). The 5-tuple opcode is of the form:

("replace", i1, i2, j1, j2)

Then

len1 = i2 - i1
len2 = j2 - j1
ouch = len1 * len2 * min(len1, len2)

sets ouch to an upper bound on the number of times the "fancy replace" function will go around to process that block pair (including recursive calls). Sum that over all "replace" opcodes.

If that's "cheap enough", ndiff can be called without worry.

tim-one · 2022-02-08T22:33:04Z

I should add that my sketch of ndiff's upper bound ignores the lan1 * len2 distinct diffs done, one for each pair of lines. Those are "1-level" unified-like diffs, so the upper bound on what those take could be computed via the other method. But computing len1 * len2 of those too threatens to make the worst case of upper-bound-finding challenge the worst case of actually doing the diff 😉.

As a practical matter, though, under the current implementation I think that can be ignored. autojunk defaults to True, and the fancy diff implementation doesn't override it. If there are many duplicate letters across both lines (where unified diff's worst cases come from), autojunk acts to ignore them entirely.

…assertEq

…thon into bpo-19217-slow-assertEq

jdevries3133 · 2022-02-09T01:25:15Z

Wow, thank you Tim and Gregory – it's a joy to learn from your discussion on this issue; I'm having fun!!

So, here's basically what we have on the table:

To graph it out:

--- Option #1 ---
( current implementation )

                                 -- affordable --> ndiff
                                /
risky unified_diff cost calc ---
                                \
                                 -- too expensive --> unified_diff



--- Option #2 ---
( Tim's suggestion )
 
                          -- very pricy --> first_differing_element
                         /
O(n) custom cost calc --- --- somewhat pricy --> unified_diff
                         \
                          -- downright bargain --> ndiff

So, first things first, @tim-one, do you have any interest in having Option #2 being part of the difflib API? If so, there's nothing more to do here – the path forward would be to add that feature to difflib and consume it from unittest.

Otherwise, I feel like this is the path forward I'd take with this PR, should continuing appear to be the best option:

fix the inaccurate docstring tim pointed out
add test cases for unified_diff's worst case scenarios. Assert that the "autojunk heuristic" continues being used, which the suggested new heuristic depends on

Note that I'm thinking not to implement Tim's O(n) cost calculation and "first differing element" style diff for expensive inputs. I wouldn't rule it out, I just feel like this heuristic in combination with the autojunk heuristic doesn't edge cases behind, but that assumption might turn out to be incorrect – it'd need to be tested more thoroughly.

Tim and Gregory, what do you think?

tim-one · 2022-02-09T02:52:47Z

No, I don't see folding any of this into difflib. This issue report has been open for nearly a decade for a reason 😉. That is, it's muddy, and there is no evident "solution".

Far as I'm concerned, the user wrote a low-quality test if the things it's asserting are equal are so large that it's not dead obvious what to show them if the assertion fails. I'm fine with dumping a million lines of text with no indication of where a difference may be - it's what they asked for, after all 😉.

As a thoroughly practical matter, why not just use unified diff, period? It's hard to provoke into pathological behavior, provided autojunk is allowed to turn itself on (which it will do, in truly otherwise-pathological cases).

It seems bizarre on the face of it too to expect a user to make sense of that there may be multiple diff formats produced, depending on things they have no understanding of.

ndiff was designed to produce high-quality diffs of source code files edited by humans, aimed at human consumption by many eyeballs. Cost was not a concern. A one-shot failing test doesn't merit that expense, or that consideration.

BTW, if you want to be more extreme, I was wrong: the b2j member of a SequenceMatcher object is a documented feature. So it's not "cheating" to use it.

jdevries3133 · 2022-02-09T04:17:31Z

Far as I'm concerned, the user wrote a low-quality test if the things it's asserting are equal are so large that it's not dead obvious what to show them if the assertion fails. I'm fine with dumping a million lines of text with no indication of where a difference may be - it's what they asked for, after all 😉.

The only issue is (if I understand correctly) that currently, millions of lines of text are not dumped as they're generated. Rather, the program hangs – because the big diff is not streamed to stdout as it's being generated; it's just being loaded into memory. Is there a way to just blast the diff into stdout as it's being generated instead of holding it in memory? This would be a better user experience imo, because at least the user can see what is happening.

To your point, users are obviously being a bit abusive of the testing library, but it should also be assumed that assertEqual will do something other than just lock up in linear time. Maybe we can dispatch diff generation to another thread, and quit generating the diff after a timeout? I agree that it's more of an issue if the test suite is gross and convoluted, but there are a lot of gross and convoluted tests out there. I see a lot of generators in difflib, but I'm not sure if something like this is possible?

I'm sorry to backpedal to entirely new solutions, and I know this isn't really the place to discuss it, but your criticism is 100% valid and I'd like to forge a path forward.... moreover, I want to slay the 9-year-old bug :(

As a thoroughly practical matter, why not just use unified diff, period? It's hard to provoke into pathological behavior, provided autojunk is allowed to turn itself on (which it will do, in truly otherwise-pathological cases).

I have tried this; it causes a lot of breakage of unittest's own test suite, which just makes it annoying, but it could be done. Hopefully asserting against failed test output is not a thing outside of unittest's own test suite.......

gpshead · 2022-02-09T04:50:27Z

The only issue is (if I understand correctly) that currently, millions of lines of text are not dumped as they're generated. Rather, the program hangs – because the big diff is not streamed to stdout as it's being generated; it's just being loaded into memory. Is there a way to just blast the diff into stdout as it's being generated instead of holding it in memory?

Non-linear diff algorithms don't work that way. It isn't a sequential algorithm, it's trying to find a best/minimalish fit of differences. Otherwise the diff between 1 3 5 7 9 and 1 3 4 5 7 9 would be -5 -7 -9 +4 +5 +7 +9 done via a linear O(n) algorithm.

Sure someone would see it when running tests locally in their terminal, but so much of testing is done on CI test automation systems these days where it's all or nothing and you don't bother to get a result or see progress - you just wait for the entire suite to give a pass or fail and if it fails you look at its processed output and ultimately logs if needed.

Just use unified_diff is one solution as Tim notes. nothing wrong with that. it'd work (yay autojunk logic?)!

One other thing to consider is that we intentionally limit the size of printed artifacts for the base case of assertEqual via the https://github.com/python/cpython/blob/main/Lib/unittest/util.py common_shorten_repr code. We should do that with sequence comparisons as well. When the the sum of the sequence lengths is more items than some constant (make it a TestCase attribute to let people override it if they want - "400" sounds nice as it should never hang forever), skip diffing and just fall back to raw _baseAssertEqual() behavior. We could also add a TestCase attribute that is the diff function to use. The point being that it would allow people to override it and supply their own if desired.

100% agreed that people get away with writing test cases that go overboard today. but this is easy to do when writing tests that pass as it's only on failures winding up in a poor behavior corner case of the library that you'd even think about it being an issue. until then everything is extremely convenient to all involved.

tim-one · 2022-02-09T05:33:12Z

Ironically, difflib used to - long ago - pump out differences "left to right" as it went along. The algorithm is based on finding the longest contiguous matching substring, then recursively do the same on the pieces "to the left" and "to the right" of that match. So there's nothing in theory to prevent delivering the deltas on the left part before the right part starts.

But as the comments in get_matching_blocks() (which everything else builds on) say, that blew the recursion stack in some extreme cases. So it was rewritten to work with an explicit stack of slice pairs to work on, and a list of partial matching-block results that's sorted into "increasing order" at the end. That's the wait-until-the-end choke point.

It's still the case that ndiff's "fancy replace" algorithm can blow the recursion stack, though.

In any case, the autojunk=False quadratic-time cases for a unified diff are hung during the very first call to find_longest_match(). and nothing of any kind can be delivered before that finishes.

@gpshead, autojunk is a really ugly hack, introduced purely for speed with insufficient thought. While it generally works well for comparing sequences of strings, it's often a disaster when comparing two long strings. In the latter case, almost every character "looks like junk", so will not be used as a synch point. The diffs that result can be of laughably poor quality. But, ya, you get them fast 😉. I'm not sure autojunk should exist at all, but it definitely should not have been enabled by default ☹️ .

As to spinning off a thread to do the diff, that's why this issue report will never be closed - everyone who looks at it eventually refuses to settle for a "good enough!" partial solution 😉.

iritkatriel

This has merge conflicts now.

bedevere-bot · 2022-11-25T11:29:28Z

A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated.

Once you have made the requested changes, please leave a comment on this pull request containing the phrase I have made the requested changes; please review again. I will then notify any core developers who have left a review that you're ready for them to take another look at this pull request.

jdevries3133 · 2022-11-26T17:56:34Z

@tim-one I have not stopped thinking about this problem.

As to spinning off a thread to do the diff, that's why this issue report will never be closed - everyone who looks at it eventually refuses to settle for a "good enough!" partial solution 😉.

OK so it seems pretty well established that any heuristic will only achieve minimizing the set of possible inputs that would cause a big slowdown. My question to Tim and the other core developers in this thread is: do you see any possible solution that could potentially cause this ticket to be closed?

In this category (ticket closers), I think that spawning, babysitting, and possibly aborting a worker thread is possibly the most bulletproof idea. The only thing I worry about is whether python's execution model will cause the parent thread to be blocked while the diffing library dead spins, causing a race condition where the child can't be aborted. I think this wouldn't be the case, but I'm sure that someone here can advise as to whether that might be a problem.

On the broad topic of heuristics, it seems clear to me that any heuristic is effectively just a band-aid that won't block the full set of problematic inputs without being extremely aggressive, like the heuristic that @gpshead suggested:

I blindly suggest: max(len(a), len(b)) > 500 prevent calling unified_diff and max(len(a), len(b)) > 200 prevents calling ndiff. Just based on the worst case timings.

At the same time, I consider an extremely aggressive heuristic or simply abandoning ndiff entirely to be a breaking change. I believe that callers do have expectations about the STDOUT of python's unit tests, regardless of whether we consider that to be an officially stable part of the API. There are regression tests in our codebase that break when test output changes, further reinforcing this assertion.

To wrap up the heuristic discussion, it seems like the forgone conclusion is that heuristics are just icing on the cake – they don't address the first principles issues, and a heuristic too aggressive might constitute a breaking change.

Tim & other core devs in the thread, my ultimate question is, do you sponsor a thread-based solution as a complete solution to the root problem we're trying to address here? Is there any other solution you'd sponsor as a complete enough solution to close the ticket? If not, are there any solutions that you'd sponsor enough to want it to be merged since it improves the ergonomics here, even if it's not a complete solution?

gpshead · 2022-11-27T08:26:49Z

No threads.

stdout from tests are not an API. Anyone depending on that has made a mere change detector, that's their problem. Regardless we wouldn't significantly change the output in a bugfix backport.

A heuristic to avoid potential regressive performance behaviors for something simpler is the best that can be done.

Hamiltonicity · 2025-04-09T15:54:52Z

Just a quick note to say that I just ran face-first into this now 12-year-old bug, so it's still out there and causing problems. For whatever it's worth I would be thoroughly on board with any "good enough" solution.

tim-one · 2025-04-09T17:00:29Z

Try things again under current main branch (3.14.0a6+)? ndiff's fancy_replace() was changed from worst-case quadratic time on its own to worst-case linear time. The short test I posted here before used to take over 2 minutes at 512 lines, but now takes under a tenth of a second.

tim-one · 2025-04-09T18:47:48Z

This is the commit that change ndiff:

#119105

tim-one · 2025-04-09T22:04:00Z

And this earlier test case:

import unittest

class TestDictDiffSlow(unittest.TestCase):

    def test_slow_assert_equal_dict(self):
        d1 = { i : i * 2 for i in range(10000) }
        d2= { i : i for i in range(10000) }
        self.assertDictEqual(d1, d2)


if __name__ == '__main__':
    unittest.main()

completes in well under 2 seconds now (under current main branch). I never did wait long enough for it to complete in a released Python (at least 15 minutes elapsed before I gave up).

…rtEq

AA-Turner · 2025-04-09T22:28:35Z

Lib/unittest/case.py

+    udiff_differing_lines = [l for l in udiff
+                             if l.startswith(('-', '+'))]


Suggested change

udiff_differing_lines = [l for l in udiff

if l.startswith(('-', '+'))]

udiff_differing_lines = [l for l in udiff if l.startswith(('-', '+'))]

AA-Turner · 2025-04-09T22:28:50Z

Lib/unittest/case.py

+
+    # inspect unified_diff output
+    num_difflines = len(udiff_differing_lines)
+    total_diffline_length = sum(len(l) for l in udiff_differing_lines)


Suggested change

total_diffline_length = sum(len(l) for l in udiff_differing_lines)

total_diffline_length = sum(map(len, udiff_differing_lines))

AA-Turner · 2025-04-09T22:29:51Z

Lib/unittest/case.py

+    hand, unified_diff's cost is the same as the cost of producing `diff`
+    by itself: O(a + b).
+
+    See bpo-19217 for additional context.


Suggested change

See bpo-19217 for additional context.

See gh-63416 for additional context.

tim-one · 2025-04-11T00:19:21Z

If I haven't been clear enough, I'm questioning whether this PR should just be closed, unmerged. The worst cases of ndiff are so very much faster now (for 3.14) that I don't believe a practical problem still exists. Yes, ndiff is still slower than a line-only "unified diff", but no longer much so in an O() sense, outside of contrived cases. All the cases discussed in this PR's history now complete in at worst a few seconds (down from hours in some cases!).

eamanu and others added 8 commits December 17, 2018 20:04

Fix bpo-19217

20fde31

fix unnecessary space and solve @gpshead comments

6996d8a

fix test

adfcf6d

Merge remote-tracking branch 'temp/fix_bpo-19217' into bpo-19217-slow…

ddebcfa

…-assertEq

bpo-19217: fix failing test in unittest's test suite

81900d4

bpo-19217: add blurb

e5cb7bc

revert changes to difflib.py

6955d81

add regression test

46f5e29

bedevere-bot added the awaiting review label Jul 28, 2021

the-knights-who-say-ni added the CLA signed label Jul 28, 2021

jdevries3133 mentioned this pull request Jul 28, 2021

Fix bpo-19217: Calling assertEquals for moderately long list takes too long #11204

Closed

jdevries3133 changed the title ~~bpo-19217: slow assertEq for moderate length list~~ Speed up assertEqual on long sequences Jul 29, 2021

ambv requested changes Jul 29, 2021

View reviewed changes

bedevere-bot removed the awaiting review label Jul 29, 2021

bedevere-bot added the awaiting changes label Jul 29, 2021

ambv changed the title ~~Speed up assertEqual on long sequences~~ bpo-19217: Speed up assertEqual on long sequences Jul 29, 2021

jdevries3133 added 2 commits August 3, 2021 16:12

Merge branch 'main' of github.com:python/cpython into bpo-19217-slow-…

847bfc4

…assertEq

jdevries3133 marked this pull request as draft August 4, 2021 03:34

fix: remove now-unused imports from test_case.py

1dd1bcd

ambv reviewed Aug 10, 2021

View reviewed changes

jdevries3133 added 3 commits August 12, 2021 11:05

merge upstream python/cpython:main

1f45b28

add variably scaled test cases, misc updates & revisions

988740a

move Test_HeuristicDiff beneath main tests

4661f75

gpshead reviewed Feb 8, 2022

View reviewed changes

jdevries3133 added 2 commits February 8, 2022 18:04

Merge branch 'main' of github.com:python/cpython into bpo-19217-slow-…

c4d6f38

…assertEq

Merge branch 'bpo-19217-slow-assertEq' of github.com:jdevries3133/cpy…

9e6a464

…thon into bpo-19217-slow-assertEq

JacekBzdak mannequin mentioned this pull request Apr 10, 2022

Calling assertEquals for moderately long list takes too long #63416

Open

ezio-melotti removed the CLA signed label Jul 13, 2022

iritkatriel requested changes Nov 25, 2022

View reviewed changes

bedevere-bot added awaiting changes and removed awaiting merge labels Nov 25, 2022

AA-Turner added 2 commits April 9, 2025 23:22

Merge remote-tracking branch 'upstream/main' into bpo-19217-slow-asse…

0ad029f

…rtEq

Remove annotations

4c5175c

AA-Turner changed the title ~~bpo-19217: Speed up assertEqual on long sequences~~ gh-63416: Speed up assertEqual on long sequences Apr 9, 2025

AA-Turner reviewed Apr 9, 2025

View reviewed changes

jdevries3133 closed this Apr 30, 2025

		udiff_differing_lines = [l for l in udiff
		if l.startswith(('-', '+'))]

	total_diffline_length = sum(len(l) for l in udiff_differing_lines)
	total_diffline_length = sum(map(len, udiff_differing_lines))

	See bpo-19217 for additional context.
	See gh-63416 for additional context.

Uh oh!

gh-63416: Speed up assertEqual on long sequences #27434

gh-63416: Speed up assertEqual on long sequences #27434

Uh oh!

Conversation

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Other Options

Check size of Input

Make ndiff a Better Generator

Uh oh!

Uh oh!

Uh oh!

TODO

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Make `ndiff` a Better Generator