model: optimize get_last_conflict() search
authorBrian Norris <banorris@uci.edu>
Mon, 19 Nov 2012 21:10:07 +0000 (13:10 -0800)
committerBrian Norris <banorris@uci.edu>
Mon, 19 Nov 2012 21:16:36 +0000 (13:16 -0800)
commit77319560c9921c0d814ed30e55c07ead41836cbe
tree5816ece1f7edfc9d1c65affbbd07febd3c91e629
parent5cd52219ebdf8ecf620f028a7639c6c31ad17df4
model: optimize get_last_conflict() search

Relaxed operations should never require backtracking, so don't even
bother with searching the list in such cases. I ran some simple
benchmarking tests with linuxrwlocks (timing results below). Also, perf
shows a significant decrease in % time spent in
ModelAction::could_synchronize_with.

------------
Before:
------------

$ time ./run.sh test/linuxrwlocks.o -f 10 -m 10
Number of complete, bug-free executions: 7110
Number of redundant executions: 29
Number of buggy executions: 0
Number of infeasible executions: 43578
Total executions: 50717
Total nodes created: 63463

real 0m7.274s
user 0m6.596s
sys 0m0.652s

2.10%  linuxrwlocks.o  libmodel.so          [.] ModelAction::could_synchronize_with(ModelAction const*) const

------------
After:
------------

$ time ./run.sh test/linuxrwlocks.o -f 10 -m 10
Number of complete, bug-free executions: 7110
Number of redundant executions: 29
Number of buggy executions: 0
Number of infeasible executions: 43578
Total executions: 50717
Total nodes created: 63463

real 0m6.690s
user 0m6.000s
sys 0m0.664s

0.73%  linuxrwlocks.o  libmodel.so          [.] ModelAction::could_synchronize_with(ModelAction const*) const
model.cc