[GHC] #14762: Foreign.Marshal.Pool functions use inefficient O(n) operations

[GHC]

#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