unsafePtrCompare, anybody?

Simon Marlow simonmar@microsoft.com
Mon, 17 Sep 2001 09:42:26 +0100

> I'm writing an atom table for a compiler/interpreter, and it=20
> would be really=20
> nice to use unsafePtrLT to implement tree-based finite maps. =20
> For clarification, my atom table consists  of these three functions:=20
> mkAtom :: String -> IO Atom
> show  :: Atom -> String
> (=3D=3D)  :: Atom -> Atom -> Bool
> such that  =20
> 	mkAtom s >>=3D (return . show) =3D=3D return s
> and
> 	mkAtom . show =3D=3D return
> and=20
> 	atom =3D=3D atom'  <=3D>  show atom =3D=3D show atom'=20
> mkAtom looks up each string in a table stored in an global=20
> variable, and=20
> returns the atom stored in the table if it is there. =20
> Otherwise, it makes the=20
> string into an atom, inserts the atom into the table, and=20
> returns this new=20
> atom.
> The point of all of this is that now string equality, when=20
> strings are made=20
> into atoms, is just pointer equality, which is available as=20
> IOExts.unsafePtrEq.   =20

You might want to check out GHC's FastString module, which does
essentially this.  We use an explicit hash table, and each FastString
has a unique Id for fast comparison.

To solve your immediate problem, you could also take a look at the
StableName library, which lets you map any old Haskell value on to an
Int so you can build finite maps etc. (we use StableNames to build memo
tables).  There's a small garbage collector overhead for this, though.

> Of course, the misuses of unsafePtrEq aren't nearly as=20
> heinous as those of=20
> unsafePtrCompare.   On the other hand, it might be next to=20
> impossible to=20
> effectively use unsafePtrCompare in cases that it isn't=20
> completely safe to=20
> use, whereas there are plently of situations where=20
> unsafePtrEq is semi-safe=20
> to use.

I can't think of a way to use unsafePtrCompare safely :-)  The relative
ordering of objects isn't guaranteed to be stable under GC.