Opened 15 months ago

Last modified 10 months ago

#15366 patch bug

GHC.Conc.Windows has a surprising queue

Reported by: dfeuer Owned by:
Priority: normal Milestone: 8.10.1
Component: Core Libraries Version: 8.4.3
Keywords: Cc: simonmar
Operating System: Windows Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D4967
Wiki Page:

Description

GHC.Conc.Windows seems to use [DelayReq] as a priority queue, and uses foldr to insert multiple elements into it. Unless these lists are always very short (are they?) that seems like a bad idea.

Change History (4)

comment:1 Changed 15 months ago by dfeuer

Operating System: Unknown/MultipleWindows

comment:2 Changed 15 months ago by dfeuer

Cc: simonmar added

CCing Simon Marlow, because he seems to have written this bit.

Is there some reason to use a list here rather than some sort of heap? The list version is around O(n^2)ish. With a heap, pending delays would be inserted into a heap, then when the time came merged with the heap of existing delays. The whole thing would be n log nish and probably rather fast. A pairing heap should work pretty well, although something with better real-time bounds might be better for preventing main-loop stalls.

comment:3 Changed 14 months ago by dfeuer

Differential Rev(s): Phab:D4967
Status: newpatch

comment:4 Changed 10 months ago by bgamari

Milestone: 8.8.18.10.1

This won't happen for 8.8.

Note: See TracTickets for help on using tickets.