[GHC] #9159: cmm case, binary search instead of jump table
#9159: cmm case, binary search instead of jump table ------------------------------+-------------------------------------------- Reporter: wojteknar | Owner: Type: bug | Status: new Priority: low | Milestone: Component: Compiler | Version: 7.8.2 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: Runtime performance bug Unknown/Multiple | Test Case: Difficulty: Unknown | Blocking: Blocked By: | Related Tickets: | ------------------------------+-------------------------------------------- I'm not sure if this is qualifies as a bug or feature request. For case expressions where the scrutinee is Int#,or Int, or probably anything else numerical, GHC generates binary search, where a jump table could easily be used instead. The functions toChunk1# and toChunk2# yield suboptimal code. I found a satisfactory workaround, toChunk3# uses Enum and it is fine. For the attached code it probably does not matter much, but I have 65 cases in my real code, trying to implement a variant of ByteString, which will have the lowest possible storage overhead (just the info table pointer == one word) for lengths up to 64 bytes. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9159 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9159: cmm case, binary search instead of jump table --------------------------------------------+------------------------------ Reporter: wojteknar | Owner: Type: bug | Status: new Priority: low | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Comment (by simonpj): That is `toChunk3#`? Would you like to offer a patch? Thanks Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9159#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9159: cmm case, binary search instead of jump table --------------------------------------------+------------------------------ Reporter: wojteknar | Owner: Type: bug | Status: new Priority: low | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Comment (by wojteknar):
That is toChunk3#?
I'm referring to the functions in the attached file.
Would you like to offer a patch?
Way beyond my skills, sorry. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9159#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9159: cmm case, binary search instead of jump table --------------------------------------------+------------------------------ Reporter: wojteknar | Owner: Type: feature request | Status: new Priority: low | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Changes (by rwbarton): * type: bug => feature request Comment: Presumably the case on an `Int#` uses a binary search because there's no reason the cases need to be consecutive integers: imagine you change the last case to `1000000# -> Chunk08 w#`. Now a jump table is not a good idea. The case on a `Nat` knows that the tag integer identifying the constructor will be in the range from 0 to 8. We would need some heuristic for when to use binary search vs. a jump table (or perhaps both, if the cases to be matched consist of multiple ranges of consecutive integers). Maybe worth looking into what C compilers do. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9159#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9159: cmm case, binary search instead of jump table --------------------------------------------+------------------------------ Reporter: wojteknar | Owner: Type: feature request | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Changes (by wojteknar): * priority: low => lowest Comment: Okay, this really is a corner case of case statement. For one range the heuristics could be "fill factor". For multiple ranges it gets really difficult. The workaround with Enum and tagToEnum# works fine. Perhaps I should just close this ticket? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9159#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9159: cmm case, binary search instead of jump table --------------------------------------------+------------------------------ Reporter: wojteknar | Owner: Type: feature request | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime performance bug | Unknown/Multiple Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Comment (by arotenberg): For comparison: The Java Virtual Machine has two instructions called `tableswitch` and `lookupswitch`, which are normally implemented as a lookup table and a binary search, respectively. [http://cr.openjdk.java.net/~forax/lambda/src/share/classes/com/sun/tools/jav... Here] is the code javac uses to decide whether to generate a `tableswitch` or `lookupswitch` for a `switch` statement: {{{ // Determine whether to issue a tableswitch or a lookupswitch // instruction. long table_space_cost = 4 + ((long) hi - lo + 1); // words long table_time_cost = 3; // comparisons long lookup_space_cost = 3 + 2 * (long) nlabels; long lookup_time_cost = nlabels; int opcode = nlabels > 0 && table_space_cost + 3 * table_time_cost <= lookup_space_cost + 3 * lookup_time_cost ? tableswitch : lookupswitch; }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9159#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9159: cmm case, binary search instead of jump table -------------------------------------+------------------------------------- Reporter: wojteknar | Owner: Type: feature request | Status: new Priority: lowest | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #10137 | Differential Revisions: -------------------------------------+------------------------------------- Changes (by rwbarton): * related: => #10137 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9159#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9159: cmm case, binary search instead of jump table -------------------------------------+------------------------------------- Reporter: wojteknar | Owner: Type: feature request | Status: closed Priority: lowest | Milestone: Component: Compiler | Version: 7.8.2 Resolution: duplicate | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #10137 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by thomie): * status: new => closed * resolution: => duplicate Comment: This was fixed in #10137, to be released with ghc-8.0. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9159#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9159: cmm case, binary search instead of jump table -------------------------------------+------------------------------------- Reporter: wojteknar | Owner: (none) Type: feature request | Status: closed Priority: lowest | Milestone: Component: Compiler | Version: 7.8.2 Resolution: duplicate | Keywords: CodeGen Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #10137 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => CodeGen -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9159#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC