Often when writing algorithms which involve set operations on small enumerations, I start off using Data.Set. I soon find performance requires rewriting that code to use bitwise operations. I miss the nice interface of Data.Set and the type checking of using a proper data type. So, as an exercise in writing a library, I wrote out an implementation of bitwise set operations using the interface of Data.Set with a couple of extensions. It provides an abstract interface and type checking. Using GHC -O3, code compiles right down to the primitive bit-twiddling operators. My example program (a sudoku solver) runs several times faster. I'll be grateful for any feedback on this. Perhaps something like it would be useful included in the standard libraries. Cheers, David -------------------------------- David F. Place mailto:d@vidplace.com
David F. Place
On Apr 3, 2006, at 10:02 AM, Jean-Philippe Bernardy wrote:
I'm currently writing and evolution to the standard collection package that can be found here:
http://darcs.haskell.org/packages/collections/
We integrate your module there. What would you say?
Sure. I'd be honored. -------------------------------- David F. Place mailto:d@vidplace.com
On Monday 03 April 2006 14:19, David F. Place wrote:
Often when writing algorithms which involve set operations on small enumerations, I start off using Data.Set. I soon find performance requires rewriting that code to use bitwise operations. I miss the nice interface of Data.Set and the type checking of using a proper data type.
So, as an exercise in writing a library, I wrote out an implementation of bitwise set operations using the interface of Data.Set with a couple of extensions. It provides an abstract interface and type checking. Using GHC -O3, code compiles right down to the primitive bit-twiddling operators. My example program (a sudoku solver) runs several times faster.
I'll be grateful for any feedback on this. Perhaps something like it would be useful included in the standard libraries.
I wondered about the Ord instance. Wouldn't it be faster to compare (word-) representations? Ben
On Apr 3, 2006, at 1:31 PM, Benjamin Franksen wrote:
wondered about the Ord instance. Wouldn't it be faster to compare (word-) representations?
I thought about that some. Since the set representation is based completely on the enumeration, it would be possible for the type being collected to have a different implementation of Ord. For instance: newtype LowerCaseAlpha = LCA Char deriving (Eq, Show) instance Enum LowerCaseAlpha where fromEnum (LCA x) = (fromEnum x) - (fromEnum 'a') toEnum x = LCA $ toEnum $ x + (fromEnum 'a') instance Ord LowerCaseAlpha where compare (LCA a) (LCA b) | a == b = EQ | a > b = LT | a < b = GT Perverted, but possible. -------------------------------- David F. Place mailto:d@vidplace.com
On 4/3/06, David F. Place
On Apr 3, 2006, at 1:31 PM, Benjamin Franksen wrote:
wondered about the Ord instance. Wouldn't it be faster to compare (word-) representations?
I thought about that some. Since the set representation is based completely on the enumeration, it would be possible for the type being collected to have a different implementation of Ord. For instance:
newtype LowerCaseAlpha = LCA Char deriving (Eq, Show)
instance Enum LowerCaseAlpha where fromEnum (LCA x) = (fromEnum x) - (fromEnum 'a') toEnum x = LCA $ toEnum $ x + (fromEnum 'a')
instance Ord LowerCaseAlpha where compare (LCA a) (LCA b) | a == b = EQ | a > b = LT | a < b = GT
Perverted, but possible.
I don't think there is a requirement for the Ord class to be equal to "compare a b = compare (toAscList a) (toAscList b)". I'd say it's safe to simply compare the bits representation. Besides, I've integrated your module to the package I'm busy setting up. http://darcs.haskell.org/packages/collections/Data/Set/Enum.hs (I'm accepting patches -- most notably if someone wishes to complete the haddock documentation) FWIW, it passed the standard regression testsuite for Sets flawlessly. I'm thinking of removing the UniverseSet class though. It seems to me that Bounded serves the purpose just right. Cheers, JP.
On Apr 3, 2006, at 5:38 PM, Jean-Philippe Bernardy wrote:
I don't think there is a requirement for the Ord class to be equal to "compare a b = compare (toAscList a) (toAscList b)". I'd say it's safe to simply compare the bits representation.
Hmm. OK.
Besides, I've integrated your module to the package I'm busy setting up.
http://darcs.haskell.org/packages/collections/Data/Set/Enum.hs
Cool.
(I'm accepting patches -- most notably if someone wishes to complete the haddock documentation)
I'll look into it.
FWIW, it passed the standard regression testsuite for Sets flawlessly.
I do quality work.
I'm thinking of removing the UniverseSet class though. It seems to me that Bounded serves the purpose just right.
Does that mean we lose the unary `complement` function? I am rather fond of that. -------------------------------- David F. Place mailto:d@vidplace.com
participants (3)
-
Benjamin Franksen -
David F. Place -
Jean-Philippe Bernardy