Opened 6 years ago

Last modified 5 months ago

#3606 new bug

The Ord instance for unboxed arrays is very inefficient

Reported by: blarsen Owned by: ekmett
Priority: lowest Milestone: 7.12.1
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 Revisions:

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 (16)

comment:1 Changed 6 years ago by blarsen

  • Architecture changed from Unknown/Multiple to x86_64 (amd64)
  • Keywords array performance Ord added
  • Operating System changed from Unknown/Multiple to Linux

comment:2 Changed 6 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 6 years ago by igloo

  • difficulty set to Unknown
  • Milestone set to 6.12 branch

comment:4 Changed 6 years ago by simonmar

  • Type changed from bug to run-time performance bug

comment:5 Changed 6 years ago by simonmar

  • Type of failure set to Runtime performance bug

comment:6 Changed 5 years ago by igloo

  • Milestone changed from 6.12 branch to 6.12.3

comment:7 Changed 5 years ago by igloo

  • Milestone changed from 6.12.3 to 6.14.1
  • Priority changed from normal to low

comment:8 Changed 4 years ago by igloo

  • Milestone changed from 7.0.1 to 7.0.2

comment:9 Changed 4 years ago by igloo

  • Milestone changed from 7.0.2 to 7.2.1

comment:10 Changed 4 years ago by igloo

  • Milestone changed from 7.2.1 to 7.4.1

comment:11 Changed 3 years ago by igloo

  • Milestone changed from 7.4.1 to 7.6.1
  • Priority changed from low to lowest

comment:12 Changed 3 years ago by igloo

  • Milestone changed from 7.6.1 to 7.6.2

comment:13 Changed 19 months ago by hvr

  • Description modified (diff)
  • Keywords performance Ord removed
  • Milestone changed from 7.6.2 to 7.10.1
  • Operating System changed from Linux to Unknown/Multiple

comment:14 Changed 8 months ago by thoughtpolice

  • Component changed from libraries (other) to Core Libraries
  • Owner set to ekmett

Moving over to new owning component 'Core Libraries'.

comment:15 Changed 5 months ago by thoughtpolice

  • Milestone changed from 7.10.1 to 7.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 5 months 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.

Note: See TracTickets for help on using tickets.