[GHC] #10837: Constant-time indexing of closed type family axioms
#10837: Constant-time indexing of closed type family axioms -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: new Priority: low | Milestone: Component: Compiler | Version: 7.11 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: Compile-time Unknown/Multiple | performance bug Test Case: | Blocked By: Blocking: | Related Tickets: Differential Revisions: | -------------------------------------+------------------------------------- Right now `CoAxiom` stores a list of `CoAxBranch`es in a `BranchList`. But it would be useful to actually have a constant-time indexing into axioms. One code fragment when I really wanted to have this feature is in `TcValidity.checkValidCoAxiom`: {{{#!hs -- Replace n-th element in the list. Assumes 0-based indexing. replace_br :: [CoAxBranch] -> Int -> CoAxBranch -> [CoAxBranch] replace_br brs n br = take n brs ++ [br] ++ drop (n+1) brs }}} I believe this code could be rewritten in a much more efficient way using constant-time indexing. The new data structure should most likely have a type that indicates whether the axiom is branched or not. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/10837> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#10837: Constant-time indexing of closed type family axioms -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: patch Priority: low | Milestone: Component: Compiler | Version: 7.11 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: Phab:D1261 -------------------------------------+------------------------------------- Changes (by goldfire): * status: new => patch * differential: => Phab:D1261 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/10837#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#10837: Constant-time indexing of closed type family axioms -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: patch Priority: low | Milestone: Component: Compiler | Version: 7.11 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: Phab:D1261 -------------------------------------+------------------------------------- Comment (by Richard Eisenberg <eir@…>): In [changeset:"cd2840a784f4136a8cfdb704124e892430ad9ead/ghc" cd2840a/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="cd2840a784f4136a8cfdb704124e892430ad9ead" Refactor BranchLists. Now we use Array to store branches. This makes sense because we often have to do random access (once inference is done). This also vastly simplifies the awkward BranchList type. This fixes #10837 and updates submodule utils/haddock. }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/10837#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#10837: Constant-time indexing of closed type family axioms -------------------------------------+------------------------------------- Reporter: jstolarek | Owner: Type: task | Status: closed Priority: low | Milestone: Component: Compiler | Version: 7.11 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: Phab:D1261 -------------------------------------+------------------------------------- Changes (by goldfire): * status: patch => closed * resolution: => fixed Comment: No need for a test case. Do //not// merge. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/10837#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC