aboutsummaryrefslogtreecommitdiffstats
path: root/lib/hipe/main/hipe.app.src
diff options
context:
space:
mode:
authorMagnus Lång <[email protected]>2016-03-18 11:20:42 +0100
committerMagnus Lång <[email protected]>2016-07-11 17:38:17 +0200
commit1bdaee9393a3cf45d7a62fba815c2a73ab637781 (patch)
treee6ad8a33cdfe03b25e8efc750e0231374d7b36f8 /lib/hipe/main/hipe.app.src
parent761e4679cd3963f09e6d1623734aa2c6e28d788a (diff)
downloadotp-1bdaee9393a3cf45d7a62fba815c2a73ab637781.tar.gz
otp-1bdaee9393a3cf45d7a62fba815c2a73ab637781.tar.bz2
otp-1bdaee9393a3cf45d7a62fba815c2a73ab637781.zip
hipe_icode_{bincomp,range}: Improve complexity
hipe_icode_bincomp:find_bs_get_integer/3 was quadratic for no good reason. By observing that NewSuccs and Rest are always disjoint, we can see that the worklist does not need to be a set. Furthermore, by replacing the ordset Visited with a map, we reduce complexity to (a very low) O(n lg n). On cuter_binlib, this change reduced the time for hipe_icode_bincomp from 60s to .25s. Using a gb_set for Visited gives .5s, and a sets:set 1s. We apply the same optimisation to hipe_icode_range.
Diffstat (limited to 'lib/hipe/main/hipe.app.src')
0 files changed, 0 insertions, 0 deletions