[GHC] #14762: Foreign.Marshal.Pool functions use inefficient O(n) operations
#14762: Foreign.Marshal.Pool functions use inefficient O(n) operations -------------------------------------+------------------------------------- Reporter: nh2 | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: | Version: 8.2.2 libraries/base | Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: Runtime Unknown/Multiple | performance bug Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- `Foreign.Marshal.Pool` uses `Data.List.delete` and `Data.List.elem` to determine whether a pointer is already in the pool and to delete them, as a result of `newtype Pool = Pool (IORef [Ptr ()])`. Thus repeated operations on pools with many entries can become very slow. If possible, we might consider using `Ord` on the `Ptr` and an O(log n) data structure instead of a `[Ptr]` list. Alternatively, we should warn in the docs that this is the case, but it seems better to just fix the implementation. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14762 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14762: Foreign.Marshal.Pool functions use inefficient O(n) operations -------------------------------------+------------------------------------- Reporter: nh2 | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): Sounds reasonable to me. Patches welcome! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14762#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14762: Foreign.Marshal.Pool functions use inefficient O(n) operations -------------------------------------+------------------------------------- Reporter: nh2 | Owner: sighingnow Type: bug | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by sighingnow): * owner: (none) => sighingnow -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14762#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14762: Foreign.Marshal.Pool functions use inefficient O(n) operations -------------------------------------+------------------------------------- Reporter: nh2 | Owner: sighingnow Type: bug | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by sighingnow): Replying to [comment:1 bgamari]:
Sounds reasonable to me. Patches welcome!
I'm willing to do the job. There's no tree data structure defined in base, could I add a minimal heap implementation in `Foreign/Marshal/Pool.hs` to support this patch ? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14762#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14762: Foreign.Marshal.Pool functions use inefficient O(n) operations -------------------------------------+------------------------------------- Reporter: nh2 | Owner: sighingnow Type: bug | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): Sounds reasonable to me. Let's just make sure there are adequate tests to demonstrate correctness. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14762#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14762: Foreign.Marshal.Pool functions use inefficient O(n) operations -------------------------------------+------------------------------------- Reporter: nh2 | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by sighingnow): * owner: sighingnow => (none) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14762#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC