Opened 20 months ago

Last modified 19 months ago

#14762 new bug

Foreign.Marshal.Pool functions use inefficient O(n) operations

Reported by: nh2 Owned by:
Priority: normal Milestone:
Component: libraries/base Version: 8.2.2
Keywords: Cc: nh2
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Change History (5)

comment:1 Changed 20 months ago by bgamari

Sounds reasonable to me. Patches welcome!

comment:2 Changed 20 months ago by sighingnow

Owner: set to sighingnow

comment:3 in reply to:  1 Changed 20 months ago by sighingnow

Replying to 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 ?

comment:4 Changed 20 months ago by bgamari

Sounds reasonable to me. Let's just make sure there are adequate tests to demonstrate correctness.

comment:5 Changed 19 months ago by sighingnow

Owner: sighingnow deleted
Note: See TracTickets for help on using tickets.