Opened 11 years ago

Closed 11 years ago

#2643 closed proposal (fixed)

Optimized IntMap / IntSet construction from sorted input

Reported by: sedillard Owned by: igloo
Priority: normal Milestone: Not GHC
Component: libraries (other) Version: 6.8.3
Keywords: containers Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


Currently the "fromAscList" functions for building IntMaps and IntSets are aliases for fromList. Building a trie in linear time from sorted input is not magic, and results in a considerable performance increase. See this post:

My impression was that the list generally approved of the patch, but for some reason its never been applied so I'm creating a ticket for it here. Tests are included in the patch. Really it just modifies an existing test (which was fromAscList xs == fromList xs) so that it's no longer vacuous.

Attachments (1)

fromAscList_BF.patch (70.0 KB) - added by sedillard 11 years ago.

Download all attachments as: .zip

Change History (4)

Changed 11 years ago by sedillard

Attachment: fromAscList_BF.patch added

comment:1 Changed 11 years ago by igloo

difficulty: Unknown
Milestone: Not GHC

comment:2 Changed 11 years ago by igloo

Owner: set to igloo

comment:3 Changed 11 years ago by igloo

Resolution: fixed
Status: newclosed

Applied, thanks!

Note: See TracTickets for help on using tickets.