Re: [Caml-list] implementing bit vectors in OCaml

[Ville-Pertti Keinonen <will@exomi.com>]

> We have a program that is spending a lot of time in set operations,
> and we're thinking of trying an imperative implementation based on bit 
> vectors.
> I would hope that the basis of such an implementation would be an array
> of native integers, but on scrutinizing the manual (espeically the 
> chapter
> on interfacing to C), I have concluded that such a thing is not 
> possible.
> Our choices appear to be
>
>   * An array of native integers, which will be implemented as an array
>     of pointers to native integers, because integers are boxed.
>
>   * An array of tagged integers, which will be less efficient as
>     dividing by 31 is more expensive than shifting.

I'd think that an obvious alternative would be to use custom blocks, 
which can basically be arrays of abstract values of whatever size you 
want to treat them as.

This should be evident based on the information on interfacing to C, if 
you are willing to implement the interface in C.  Of course the obvious 
problem with this approach would be the inefficiency of not being able 
to inline operations on this array.

If the optimizer were smart enough (I don't think it currently is), 
OCaml code treating strings (or even arrays of floats) as bit vectors 
might be a reasonably efficient approach.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners