Description

assignee = None
closed_at = None
created_at = <Date 2015-08-20.22:18:07.911>
labels = ['type-feature', 'library']
title = 'Provide a way for potentially long runtime difflib algorithms to be aborted by the caller (and report progress?)'
updated_at = <Date 2022-02-07.13:36:55.864>
user = 'https://github.com/jftuga'

activity = <Date 2022-02-07.13:36:55.864>
actor = 'vstinner'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Library (Lib)']
creation = <Date 2015-08-20.22:18:07.911>
creator = 'jftuga'
dependencies = []
files = ['40217']
hgrepos = []
issue_num = 24904
keywords = ['patch']
message_count = 5.0
messages = ['248919', '248920', '248921', '248922', '412718']
nosy_count = 5.0
nosy_names = ['tim.peters', 'rhettinger', 'gregory.p.smith', 'rbcollins', 'jftuga']
pr_nums = []
priority = 'normal'
resolution = None
stage = 'needs patch'
status = 'open'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue24904'
versions = ['Python 3.5']

Activity

1. jftuga commented on Aug 20, 2015

   

   jftugamannequin

   on Aug 20, 2015

   MannequinAuthor

   More actions

   SequenceMatcher in the difflib module contain ratio() and quick_ratio() methods which can take a long time to run with certain input. One example is two slightly different versions of jquery.min.js.

   I have written a patch against python-350b4 that adds a timeout to these methods. The new functionality also has the capability to "fall through" to the next quickest comparison method should a timeout occur. If a timeout does occur and using a fall through method is not desired, then -1 is returned for the ratio.

   I'd like this to be incorporated into Python 3.5.0 if it is not too late.
2. jftuga

   added

   stdlibStandard Library Python modules in the Lib/ directoryStandard Library Python modules in the Lib/ directory

   type-featureA feature request or enhancementA feature request or enhancement

   on Aug 20, 2015
3. vstinner commented on Aug 20, 2015

   

   vstinner

   on Aug 20, 2015

   Member

   More actions

   I'm not sure that it's a good idea to add a timeout to such algorithm. It can be very surprising to have a difference result depending on the system load (CPU usage of _other_ applications) and on the CPU performances.

   If you really want this result, I would prefer to design the feature outside the Python stdlib. You might modify the stdlib to allow incremental computation.

   About the patch itself, which kind of timer should be used? Monotonic clock? System clock? Process time (CPU time)?

   Maybe we can optimize the code?
4. rhettinger commented on Aug 20, 2015

   

   rhettinger

   on Aug 20, 2015

   Contributor

   More actions

   In general, it isn't good design to incorporate timeout logic in computation logic. What would be better is a general purpose, reusable, decoupled tool: run_with_time_limit(some_computation, some_args, time_limit). Such a tool might be based on separate process that can be timed or killed, it might use signals, or may be based on threading.Timer.

   I did a quick look around the net. Timeouts on diff APIs aren't common (i.e GNU diff doesn't have a timeout) but there are a couple of precedents (you aren't the first to have had concerns about the running time for unfavorable inputs).
5. rbtcollins commented on Aug 20, 2015

   

   rbtcollins

   on Aug 20, 2015

   Member

   More actions

   So - I'm with Victor and Raymond here. I think modifying difflib to provide external control over the poor-O components would permit many more benefits than just controlling time: you could wrap them in a timer module to get what this patch does, you could replace them with alternative implementations (e.g. parallel ones).
6. gpshead commented on Feb 7, 2022

   

   gpshead

   on Feb 7, 2022

   Member

   More actions

   The way I'd go about this is to support some form of periodic checkpoint in the algorithm where it checks in with code supplied by the difflib user. Traditionally that'd have been via callbacks, there might be an async style way to express that these days. Those could indicate that they want the operation to be aborted. If it is possible to estimate progress, supplying that as input to the checkpoint API would be useful.

   This leaves decision logic on when to abort something entirely up to the user rather than being clock based which is often not what the user wants.

   I'm re-titling the issue as the original patch and proposal of a timeout isn't the direction several core devs have suggested we head.

   Reacted by Petr Viktorin
7. gpshead

   changed the title [-]Patch: add timeout to difflib SequenceMatcher ratio() and quick_ratio()[/-] [+]Provide a way for potentially long runtime difflib algorithms to be aborted by the caller (and report progress?)[/+] on Feb 7, 2022
8. ezio-melotti

   transferred this issue fromon Apr 10, 2022

Issue actions