#8456: Control flow optimisations duplicate blocks --------------------------------------------+------------------------------ Reporter: jstolarek | Owner: jstolarek Type: bug | Status: new Priority: highest | Milestone: 7.8.1 Component: Compiler | Version: 7.7 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: 8275 | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Changes (by jstolarek): * owner: => jstolarek Comment:
It looks like the condition is reversed Yes, you're right.
what you actually wanted to do was look in the range of the map, not the domain. Argh... I don't know why I assumed that it looks in the range :-/
searching the range of a map is O(n) operation According to documentation of !IntMap `lookup` has O(min(n,W)) complexity:
Many operations have a worst-case complexity of O(min(n,W)). This means that the operation can become linear in the number of elements with a maximum of W -- the number of bits in an Int (32 or 64). I'm not sure if I understand correctly, but this means that for n < W `lookup` is linear, right?
I suggest just deleting this condition. If the block is in the shortcut_map, then it will also have another predecessor (the call itself), and we won't attempt to concatenate with it. Not any more - see third guard and `update_cont` function. I wanted to avoid this kind of hidden invariants, because they often cause us trouble.
My idea here would be to replace {{{ , hasNotBeenMappedTo b' shortcut_map }}} with {{{ , Nothing <- mapLookup b' shortcut_map }}} Would that be acceptable? I think that for the most time we keep a small number of entries in `shortcut_map`, so `lookup` will be linear, but then again if these numbers are small it shouldn't be that much of a problem? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8456#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler