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 TAA17254; Sun, 1 Jun 2003 19:02:14 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA17119 for ; Sun, 1 Jun 2003 19:02:13 +0200 (MET DST) Received: from mail.eecs.harvard.edu (bowser.eecs.harvard.edu [140.247.60.24]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h51H2CH10976 for ; Sun, 1 Jun 2003 19:02:13 +0200 (MET DST) Received: from cersei.eecs.harvard.edu (cersei.eecs.harvard.edu [140.247.60.39]) by mail.eecs.harvard.edu (Postfix) with ESMTP id 77AA854C4C9 for ; Sun, 1 Jun 2003 13:02:12 -0400 (EDT) Received: from flatcoat.eecs.harvard.edu (dialup-67.75.18.13.Dial1.Boston1.Level3.net [67.75.18.13]) by cersei.eecs.harvard.edu (Postfix) with ESMTP id 29FC3AE508 for ; Sun, 1 Jun 2003 12:06:18 -0400 (EDT) Received: by flatcoat.eecs.harvard.edu (Postfix, from userid 32074) id 002EF12F9CE; Sun, 1 Jun 2003 13:03:17 -0400 (EDT) To: caml-list@inria.fr Subject: [Caml-list] implementing bit vectors in OCaml Message-Id: <20030601170317.002EF12F9CE@flatcoat.eecs.harvard.edu> Date: Sun, 1 Jun 2003 13:03:17 -0400 (EDT) From: nr@eecs.harvard.edu (Norman Ramsey) X-Spam: no; 0.00; ramsey:01 vectors:01 scrutinizing:99 interfacing:01 implemented:01 pointers:01 persuaded:01 unboxed:01 untagged:01 arrays:01 compiler:01 tagged:01 ocaml:01 norman:01 float:02 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. How would the gurus recommend that we proceed? Is there a better, still efficient data structure for a set of small integers? Could the compiler gods be persuaded to provide unboxed representations for arrays of untagged integers, as is already done for `float array'? Norman ------------------- 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