From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA18275; Sun, 1 Jun 2003 19:51:01 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA18259 for ; Sun, 1 Jun 2003 19:51:00 +0200 (MET DST) Received: from mail.exomi.com (mail.exomi.com [217.169.64.72]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h51HoxT25305 for ; Sun, 1 Jun 2003 19:50:59 +0200 (MET DST) Received: from exomi.com (unknown [10.0.5.5]) by mail.exomi.com (Postfix) with ESMTP id 80E925D03; Sun, 1 Jun 2003 20:50:58 +0300 (EEST) Date: Sun, 1 Jun 2003 20:50:57 +0300 Subject: Re: [Caml-list] implementing bit vectors in OCaml Content-Type: text/plain; charset=US-ASCII; format=flowed Mime-Version: 1.0 (Apple Message framework v552) Cc: caml-list@inria.fr To: nr@eecs.harvard.edu (Norman Ramsey) From: Ville-Pertti Keinonen In-Reply-To: <20030601170317.002EF12F9CE@flatcoat.eecs.harvard.edu> Message-Id: <990DE004-9459-11D7-B7B0-000393863F70@exomi.com> Content-Transfer-Encoding: 7bit X-Mailer: Apple Mail (2.552) X-Spam: no; 0.00; caml-list:01 vectors:01 scrutinizing:99 interfacing:01 implemented:01 pointers:01 floats:01 arrays:01 tagged:01 ocaml:01 optimizer:02 native:02 inline:03 interface:03 abstract:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > 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