#3606: The Ord instance for unboxed arrays is very inefficient --------------------------------------------+------------------------------ Reporter: blarsen | Owner: Type: bug | Status: new Priority: lowest | Milestone: 7.10.1 Component: libraries (other) | Version: 6.10.4 Resolution: | Keywords: array Operating System: Unknown/Multiple | Architecture: x86_64 Type of failure: Runtime performance bug | (amd64) Test Case: | Difficulty: Unknown Blocking: | Blocked By: | Related Tickets: --------------------------------------------+------------------------------ Changes (by hvr): * keywords: array, performance, Ord => array * os: Linux => Unknown/Multiple * milestone: 7.6.2 => 7.10.1 Old description:
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.
New description: 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`: {{{#!hs 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. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/3606#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler