Opened 8 years ago

Last modified 20 months ago

#3606 new bug

The Ord instance for unboxed arrays is very inefficient

Reported by: blarsen Owned by:
Priority: lowest Milestone:
Component: Core Libraries Version: 6.10.4
Keywords: array Cc:
Operating System: Unknown/Multiple Architecture: x86_64 (amd64)
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by hvr)

The Ord instance for unboxed arrays defined in Data.Array.Base results in code that makes lots of heap allocations and is very slow.

For the record, the Ord instance is defined as so in Data.Array.Base:

instance (Ix ix, Ord e, IArray UArray e) => Ord (UArray ix e) where
    compare = cmpUArray

{-# INLINE cmpUArray #-}
cmpUArray :: (IArray UArray e, Ix i, Ord e) => UArray i e -> UArray i e -> Ordering
cmpUArray arr1 arr2 = compare (assocs arr1) (assocs arr2)

The assocs calls don't appear to be deforested away, and hence, when using the Ord functions on unboxed arrays, the performance is bad to the point of making them unusable.

It seems reasonable to me that compare for unboxed arrays could be implemented strictly, in a tight loop, without any heap allocations at all.

Change History (19)

comment:1 Changed 8 years ago by blarsen

Architecture: Unknown/Multiplex86_64 (amd64)
Keywords: array performance Ord added
Operating System: Unknown/MultipleLinux

comment:2 Changed 8 years ago by duncan

And we cannot make it fuse using build/foldr because it is a zipWith consumed by a foldl.

comment:3 Changed 8 years ago by igloo

difficulty: Unknown
Milestone: 6.12 branch

comment:4 Changed 8 years ago by simonmar

Type: bugrun-time performance bug

comment:5 Changed 8 years ago by simonmar

Type of failure: Runtime performance bug

comment:6 Changed 7 years ago by igloo

Milestone: 6.12 branch6.12.3

comment:7 Changed 7 years ago by igloo

Milestone: 6.12.36.14.1
Priority: normallow

comment:8 Changed 7 years ago by igloo

Milestone: 7.0.17.0.2

comment:9 Changed 7 years ago by igloo

Milestone: 7.0.27.2.1

comment:10 Changed 6 years ago by igloo

Milestone: 7.2.17.4.1

comment:11 Changed 6 years ago by igloo

Milestone: 7.4.17.6.1
Priority: lowlowest

comment:12 Changed 5 years ago by igloo

Milestone: 7.6.17.6.2

comment:13 Changed 4 years ago by hvr

Description: modified (diff)
Keywords: performance Ord removed
Milestone: 7.6.27.10.1
Operating System: LinuxUnknown/Multiple

comment:14 Changed 3 years ago by thoughtpolice

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

Moving over to new owning component 'Core Libraries'.

comment:15 Changed 3 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:16 Changed 3 years ago by thoughtpolice

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:17 Changed 2 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:18 Changed 2 years ago by thomie

Owner: ekmett deleted

comment:19 Changed 20 months ago by thomie

Milestone: 8.0.1
Note: See TracTickets for help on using tickets.