Opened 13 years ago

Closed 10 years ago

#1117 closed feature request (fixed)

[2,4..10] is not a good list producer

Reported by: br1@… Owned by:
Priority: lowest Milestone:
Component: Compiler Version: 6.6
Keywords: rewrite rules Cc:
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

I asked about this in @ghc, and Spencer Janssen had to say "enumFromTo is a good producer, but apparently enumFromThenTo is not". This means it doesn't fuse with good list consumers, forM_ in my case.

Change History (12)

comment:1 Changed 13 years ago by kirsten

enumFromThenTo looks like a good producer to me (it's defined in terms of map, or at least the default implementation is, just like the default implementations of enumFrom, enumFromThen, and enumFromTo). Can you be more specific about what problem you're seeing? If you have code using it that you would expect to be deforested that isn't, could you post a test case?

comment:2 Changed 13 years ago by br1@…

The function that should be changed is efdtInt in

http://darcs.haskell.org/packages/base/GHC/Enum.lhs

The comments acknowledge that it doesn't bother with rules and deforestation.

The code that brings this up is a step on the imperative eratosthenes sieve algorithm:

forM_ [2*i, 3*i .. n-1] (\j -> writeArray arr j False)

comment:3 Changed 13 years ago by kirsten

Ah, yes, I wasn't looking at the instance for int. So, what kind of speedup do you get for your code if you do define your own efdtInt in terms of foldr/build?

comment:4 Changed 13 years ago by igloo

Milestone: 6.6.1
Priority: normallow

I've set priority to low as we probably don't want to wait for this before releasing 6.6.1, but if it's done by then and looks beneficial then I can't see why it shouldn't go in.

comment:5 Changed 13 years ago by br1

Here are 3 versions of my code. fastest is with manual loops, fast with the build-based step, and slow with the standard one. The running times are

fastest 2.4 s fast 2.5 s slow 4.1 s

I supose the difference between fastest and fast could be squashed# by# someone# more# knowledgeable# than# me#.

I had to play a little with the definition of step, because at first fast took 6.3 s. These versions are stepfast and stepslow.

{-# OPTIONS_GHC -fbang-patterns #-} {-# OPTIONS_GHC -fglasgow-exts #-}

import GHC.Exts import Control.Monad.ST import Data.Array.ST import Control.Monad import Data.Int

n = (10000*1000) :: Int

fastest :: Int64 fastest = runST body where

body = do

arr <- newArray (0,n-1) 1
ST s (STUArray s Int Int) let loop i !count | i < n = do marcado <- readArray arr i case marcado of 0 -> loop (i+1) count 1 -> do let marcar j | j < n = do writeArray arr j 0 marcar (j+i) | otherwise = loop (i+1) (count+ fromIntegral i) marcar (i+i) | otherwise = return count loop 2 0

stepslow :: Int -> Int -> Int -> [Int] stepslow b s e = build (pp b s e) where

pp b s e cons nil | b <= e = cons b (pp (b+s) s e cons nil) pp b s e cons nil = nil

stepfast :: Int -> Int -> Int -> [Int] stepfast begin step end = build pp where

pp cons nil = kk begin where

kk current | current <= end = cons current (kk (current+step)) kk current | otherwise = nil

fast :: Int64 fast = runST body where

body = do

arr <- newArray (2,n-1) 1
ST s (STUArray s Int Int) let loop i !count | i < n = do marcado <- readArray arr i case marcado of 0 -> loop (i+1) count 1 -> do forM_ (stepfast (2*i) i (n-1)) (\j -> writeArray arr j 0) loop (i+1) (count + fromIntegral i) | otherwise = return count loop 2 0

slow :: Int64 slow = runST body where

body = do

arr <- newArray (2,n-1) 1
ST s (STUArray s Int Int) let loop i !count | i < n = do marcado <- readArray arr i case marcado of 0 -> loop (i+1) count 1 -> do forM_ [2*i, 3*i .. n-1] (\j -> writeArray arr j 0) loop (i+1) (count + fromIntegral i) | otherwise = return count loop 2 0

comment:6 Changed 13 years ago by simonpj

Milestone: 6.6.16.8
Priority: lowlowest

Good data. Duncan Coutts and Roman Leshchinskiy are planning to work on list fusion in the next month or two. Since that will change GHC's list libraries a lot, it'd be a bit of waste to fix the current libraries. So I propose to leave this. I'll make its priority low, but leave it open.

Simon

comment:7 Changed 12 years ago by igloo

Milestone: 6.8 branch_|_

comment:8 Changed 11 years ago by simonmar

Architecture: MultipleUnknown/Multiple

comment:9 Changed 11 years ago by simonmar

Operating System: MultipleUnknown/Multiple

comment:10 Changed 10 years ago by simonmar

difficulty: Easy (1 hr)Easy (less than 1 hour)

comment:11 Changed 10 years ago by daniel.is.fischer

Type of failure: None/Unknown

Seems fixed. Timings with 6.10.3: fastest 2.55s, fast 2.64s, slow 2.71s on average. I think that's good enough, suggest closing.

comment:12 Changed 10 years ago by simonmar

Resolution: fixed
Status: newclosed
Type of failure: None/UnknownRuntime performance bug

Indeed, looks like efdtInt now has a RULE. Thanks Daniel!

Note: See TracTickets for help on using tickets.