[meld/meld-3-16] misc: Fix performance of interval merging (bgo#768300)

[Kai Willadsen <kaiw src gnome org>]

commit d176eae8283bcff563d995aed460f17062220d99
Author: Kai Willadsen <kai willadsen gmail com>
Date:   Sat Jul 2 08:28:05 2016 +1000

    misc: Fix performance of interval merging (bgo#768300)
    
    Interval merge was constantly pop()ing from the list head, which is very
    slow on standard Python lists. Just moving to a deque gets rid of this
    from profiles on large lists of ignored intervals.

 meld/misc.py |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)
---
diff --git a/meld/misc.py b/meld/misc.py
index aa13538..60b5eef 100644
--- a/meld/misc.py
+++ b/meld/misc.py
@@ -18,6 +18,7 @@
 """Module of commonly used helper classes and functions
 """
 
+import collections
 import os
 import errno
 import shutil
@@ -480,12 +481,12 @@ def merge_intervals(interval_list):
     if len(interval_list) < 2:
         return interval_list
 
-    interval_list.sort()
-    merged_intervals = [interval_list.pop(0)]
+    interval_list = collections.deque(sorted(interval_list))
+    merged_intervals = [interval_list.popleft()]
     current_start, current_end = merged_intervals[-1]
 
     while interval_list:
-        new_start, new_end = interval_list.pop(0)
+        new_start, new_end = interval_list.popleft()
 
         if current_end >= new_end:
             continue