diff options
| author | Magnus Lång <[email protected]> | 2016-03-18 11:20:42 +0100 |
|---|---|---|
| committer | Magnus Lång <[email protected]> | 2016-07-11 17:38:17 +0200 |
| commit | 1bdaee9393a3cf45d7a62fba815c2a73ab637781 (patch) | |
| tree | e6ad8a33cdfe03b25e8efc750e0231374d7b36f8 /lib/compiler/src/v3_life.erl | |
| parent | 761e4679cd3963f09e6d1623734aa2c6e28d788a (diff) | |
| download | otp-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/compiler/src/v3_life.erl')
0 files changed, 0 insertions, 0 deletions