Efficient Sets for Small Enumerations

[David Place]

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:[hidden email]


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Jean-Philippe Bernardy]

David F. Place <d <at> vidplace.com> writes:

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?

Cheers,
JP.




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[David 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:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ben Franksen-2]

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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[David 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.

--------------------------------
David F. Place
mailto:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Jean-Philippe Bernardy]

On 4/3/06, David F. Place <[hidden email]> wrote:

>
> 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.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[David Place]

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:[hidden email]

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe