Activity

1. maathieu

   added

   docsDocumentation in the Doc dirDocumentation in the Doc dir

   on Jul 18, 2023
2. maathieu

   changed the title [-]A warning should be added to difflib about SequenceMatcher performance[/-] [+]A warning should be added to difflib documentation about SequenceMatcher performance[/+] on Jul 18, 2023
3. gaogaotiantian commented on Jul 18, 2023

   

   gaogaotiantian

   on Jul 18, 2023

   Member

   More actions

   Hi, could you maybe give an example (both the file and the code) for the issue? Maybe there are some low hanging fruits. I can't repro the several minutes result with 60k identical files.
4. rhettinger

   assigned

   tim-one

   on Jul 19, 2023
5. maathieu commented on Jul 20, 2023

   

   maathieu

   on Jul 20, 2023

   Author

   More actions

   Hi,

   Thanks for your reply. Maybe this can be me misunderstanding the use of autojunk, actually? I am writing a program that aims to generate deltas from successive versions of files, so I wanted to use SequenceMatcher.get_opcodes() to return me the sequence of instructions needed to turn one version of the file to the next one. In the documentation it is written that "junk" characters are ignored and that autojunk enables a heuristic that will automatically ignore popular characters. So to ensure the tool would return all possible changes and me being able to generate my files from the history of changes, I disabled the heuristic by setting it to false. But this comes at a huge performance cost.

   I wrote a test code below that shows the difference in performance between setting autojunk to true or false.

   """
   SequenceMatcher test when autojunk is false or true
   """
   
   import difflib,time
   
   t1 = time.time()
   
   with open("loremipsum.txt", "r") as f:
   	dat1 = f.read()
   
   # autojunk is false	
   match = difflib.SequenceMatcher(a=dat1, b=dat1, autojunk=False)
   res =match.get_opcodes()
   
   t2 = time.time()
   
   print("It roughly took %.1f seconds to run get_opcodes with autojunk set to False."%(t2-t1))
   
   # autojunk is true	
   match = difflib.SequenceMatcher(a=dat1, b=dat1, autojunk=True)
   res =match.get_opcodes()
   
   t3 = time.time()
   
   print("It roughly took %.1f seconds to run get_opcodes with autojunk set to True."%(t3-t2))

   loremipsum.txt
6. tim-one commented on Jul 20, 2023

   

   tim-one

   on Jul 20, 2023

   Member

   More actions

   It was intended to compare text files by lines, not by characters. But, as you've discovered, if you do it by characters anyway, it can be enormously expensive unless autojunk is enabled. That's why autojunk was introduced. Although:

   • It was more intended to avoid sync'ing on common "noise lines", like else: and # in Python source code compared by lines;, and,
   • It was a Bad Mistake to enable it by default. It can give surprising results.

   In your example, display match.bpopular after creating the match object with autojunk enabled. You'll discover that all the characters in ",acdegilmnoprstuv" are excluded from being considered as synchronization points. As the docs say, that's because each of those characters accounts for at least 1% of the total characters in the sequence. They're "common as mud".

   In fact, only 19 distinct characters aren't excluded:

   >>> len(match.b2j)
   19
   >>> ''.join(match.b2j)
   'Lybq.AjSk\nDhfzUwxNC'

   Of course it runs enormously faster to look only at the rarest characters.

   The opcodes produced should be "correct" either way. autojunk, and explicitly defining your own isjunk function, are ways to influence the "quality" of the diffs produced, and the time it takes to get them. not their correctness. Quality is subjective. The opcodes produced will change the first sequence to the second regardless.

   At an extreme, tell the class that everything "is junk" (pass lambda ch: True as the isjunk= argument). It will run very fast then, but you may be left hoping for a "smarter" diff 😉. The utmost extreme: a single opcode that says "replace the entire first sequence with the entire second sequence." That's always correct. regardless of the inputs.

   But notions of "junk" aren't just about speed. They can also be about quality. With no notion of junk, you can get diffs that sync up on what you consider to be regions of white noise; with a too-expansive notion of junk, diffs approaching the "utmost extreme" above.

   Reacted by Lenormand Julien
7. maathieu commented on Jul 20, 2023

   

   maathieu

   on Jul 20, 2023

   Author

   More actions

   Thanks, this is much more clear explained this way. Is it possible to consider including a similar explanation in the documentation?

   (more specifically that autojunk does not prevent get_opcodes() from returning a functional list of differences)
8. encukou commented on Sep 7, 2026

   

   encukou

   on Sep 7, 2026

   Member

   More actions

   The docs were updated in #118150. They now start off with text lines as the intended use case, then mention SequenceMatcher as the generalization, then a section on junk which includes "this heuristic can speed the algorithm up".

   I think that's enough for this issue, so I'll close. If anyone disagrees, shout :)
9. encukou

   closed this as completedon Sep 7, 2026