Re: [Ocaml-lib-devel] a bug in BitSet?

[Bardur A. <oca...@sc...>]

On Sun, Dec 19, 2004 at 03:07:03PM +0200, Janne Hellsten wrote:

[--snip--]
> >If they're changed to behaving in a non-destructive way,
> >then the names should *definitely* be changed. For the
> >sake of consistency I would suggest using the same names
> >as are used in the standard library's Set:
> >
> >    union, inter, diff
> 
> I will add non-destructive union, diff and inter and make the old ones use 
> the new non-destructive ones.  They will make unite et al. just a little 
> slower -- but I guess slower is better than unsafely reading past the 
> arrays.

Speed is irrelevant if the correctness isn't there. So,
always go for correctness over speed. If someone is
concerned about the speed they can always implement/submit
a faster version later.

> 
> I wonder if anyone has any ideas about the Obj.magic trickery in BitSet? 
> To me it seems that using string.[] with int_of_char would do the same 
> thing.  Is it just an optimization?

Yes, Obj.magic is basically just a typecast... which works
as long as the internal representations of types are
"compatible" in some useful way. An example: If I recall
correctly,

     ('a list)

is compatible with the record type

     { elem : 'a; tail : mutable 'a list }

In this case Obj.magic can be exploited to implement lists
with mutable tails (and similar trickery).

I'm no expert on OCaml optimization, but I believe there
is a considerable performance benefit in using unsafe_get
(bget), unsafe_set (bset), etc. because you can avoid
bounds checking and always get proper inlining. Whether
this level of optimization is really necessary for BitSet
I'll leave as an exercise for the reader. :)

> I would assume that ocamlopt with proper inlining should
> be able to do pretty good job on it without the added
> trickery.

I don't think the compiler is currently clever enough (or
maybe the language semantics are not strict enough?) to do
all the needed inlining, and the bounds checking would
still slow you down.

> 
> It would be nice to be able to compile ExtLib with bounds
> checking on, at least when running the test suite.
> 

I think compiling without bounds checking for "release"
builds is unwise since it may obscure serious bugs which
haven't been caught by the test suite. It's basically rude
to anyone using the library to (possibly) obscure bugs
within the library this way.

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

God is REAL unless explicitly declared INTEGER.
                                       Unknown FORTRAN programmer