commit 429306595b1733b0f3f732c26ae216b463a807e6
Author: David Malcolm <dmalcolm(a)redhat.com>
Date: Wed Dec 21 17:03:02 2011 -0500
cpychecker: optimize Trace.get_all_var_region_pairs()
Running 9c2b81d2abf89c238c785fcf189e101067549eb1 (plus local changes) on
rpm's python/rpmmodule.c showed a big slowdown analyzing that code's
"initModule" function.
Analysis with the profiler showed a big spike in
Trace.get_all_var_region_pairs()
as called by get_description_for_region()
Changing it to use a set (rather than a list) removes the slowdown, presumably
due to avoiding the cost of "in" on a list inside the loop, changing it from
O(N^2) to O(N), where N is the number of items.
For reference, here's the old profile:
Wed Dec 21 16:17:18 2011 .libs/rpmmodule.c.initModule.refcount-profile
5491244 function calls (5490966 primitive calls) in 29.004 seconds
Ordered by: cumulative time
List reduced from 159 to 20 due to restriction <20>
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 29.004 29.004 <string>:2(<module>)
1 0.040 0.040 29.004 29.004 /home/david/coding/gcc-python/gcc-python/fixing-rpm/libcpychecker/refcounts.py:2747(check_refcounts)
113 0.004 0.000 27.433 0.243 /home/david/coding/gcc-python/gcc-python/fixing-rpm/libcpychecker/absinterp.py:2540(get_description_for_region)
113 24.435 0.216 27.277 0.241 /home/david/coding/gcc-python/gcc-python/fixing-rpm/libcpychecker/absinterp.py:2488(get_all_var_region_pairs)
25429 1.683 0.000 2.770 0.000 /usr/lib64/python2.7/_abcoll.py:368(items)
257/1 0.007 0.000 1.506 1.506 /home/david/coding/gcc-python/gcc-python/fixing-rpm/libcpychecker/absinterp.py:2624(iter_traces)
248 0.001 0.000 1.374 0.006 /home/david/coding/gcc-python/gcc-python/fixing-rpm/libcpychecker/absinterp.py:1816(get_transitions)
247 0.002 0.000 1.368 0.006 /home/david/coding/gcc-python/gcc-python/fixing-rpm/libcpychecker/absinterp.py:1830(_get_transitions_for_stmt)
179 0.005 0.000 1.274 0.007 /home/david/coding/gcc-python/gcc-python/fixing-rpm/libcpychecker/absinterp.py:1941(_get_transitions_for_GimpleCall)
161 0.002 0.000 1.138 0.007 /home/david/coding/gcc-python/gcc-python/fixing-rpm/libcpychecker/refcounts.py:1743(impl_PyModule_AddIntConstant)
3784073 1.123 0.000 1.123 0.000 /usr/lib64/python2.7/collections.py:97(__iter__)
175 0.002 0.000 0.901 0.005 /home/david/coding/gcc-python/gcc-python/fixing-rpm/libcpychecker/refcounts.py:358(set_exception)
175 0.313 0.002 0.498 0.003 /home/david/coding/gcc-python/gcc-python/fixing-rpm/gccutils.py:49(get_global_vardecl_by_name)
184 0.271 0.001 0.412 0.002 /home/david/coding/gcc-python/gcc-python/fixing-rpm/gccutils.py:34(get_global_typedef)
176 0.001 0.000 0.393 0.002 /home/david/coding/gcc-python/gcc-python/fixing-rpm/libcpychecker/types.py:59(get_PyObjectPtr)
481 0.003 0.000 0.384 0.001 /home/david/coding/gcc-python/gcc-python/fixing-rpm/libcpychecker/absinterp.py:1244(copy)
962 0.004 0.000 0.374 0.000 /usr/lib64/python2.7/collections.py:178(copy)
964 0.009 0.000 0.371 0.000 /usr/lib64/python2.7/collections.py:58(__init__)
1303416 0.359 0.000 0.361 0.000 {isinstance}
964 0.104 0.000 0.359 0.000 /usr/lib64/python2.7/_abcoll.py:483(update)
libcpychecker/absinterp.py | 7 +++----
1 files changed, 3 insertions(+), 4 deletions(-)
---
diff --git a/libcpychecker/absinterp.py b/libcpychecker/absinterp.py
index 678e4b7..5de228f 100644
--- a/libcpychecker/absinterp.py
+++ b/libcpychecker/absinterp.py
@@ -2475,15 +2475,14 @@ class Trace(object):
def get_all_var_region_pairs(self):
"""
- Get the list of all (LHS,region) pairs in region_for_var within all of
+ Get the set of all (LHS,region) pairs in region_for_var within all of
the states in this trace, without duplicates
"""
- result = []
+ result = set()
for s_iter in self.states:
for var_iter, r_iter in s_iter.region_for_var.items():
pair = (var_iter, r_iter)
- if pair not in result:
- result.append(pair)
+ result.add(pair)
return result
def var_points_unambiguously_to(self, r_srcptr, r_dstptr):