Opened 7 years ago

Last modified 4 years ago

#7309 new bug

The Ix instance for (,) leaks space in range

Reported by: nomeata Owned by:
Priority: normal Milestone:
Component: Core Libraries Version: 7.6.1
Keywords: Cc: carter.schonwald@…
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 (last modified by igloo)

(at least if you take leak to mean unexpected space behaviour).

This was brought to my attention via http://stackoverflow.com/questions/12780497/puzzling-memory-behavior-in-haskell where someone created a 6×10^6-array and was surprised that showing the array caused an additional (3+2)*8*10^6 bytes to be used. The reason (as far as I could tell) was this code:

instance (Ix a, Ix b) => Ix (a, b) where
    range ((l1,l2),(u1,u2)) = [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]

in Arr.GHC. The result of range (l2,u2) is shared between every step in the first component of the index.

I guess it is reasonable to expect that the result of range is never worth sharing (is it?). I am not entirely sure what the best, cleanest, alternative implementation is, though. (At least not without a working dontshare annotation ;-))

Change History (7)

comment:1 Changed 7 years ago by simonpj

difficulty: Unknown

Aha. See #7206, still on my stack, but would be delighted if someone took this on.

comment:2 Changed 7 years ago by nomeata

Would #7206 really help here? After all, the problematic code is polymophic, so there is not a concrete range that could be inlined to a cheapBuild.

In code where the tuple-range is inlined and the concrete range functions of the element types are known (as in the second example in the stack exchange question), things already work out nicely as the foldr/builder fusion actually kicks in.

comment:3 Changed 7 years ago by carter

Cc: carter.schonwald@… added

comment:4 Changed 6 years ago by igloo

Description: modified (diff)

comment:5 Changed 6 years ago by igloo

Milestone: _|_

Milestone _|_ to match #7206.

comment:6 Changed 5 years ago by thoughtpolice

Component: libraries (other)Core Libraries
Owner: set to ekmett

Moving over to new owning component 'Core Libraries'.

comment:7 Changed 4 years ago by thomie

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