Re: [Caml-list] References, compact bollean values (and other questions)

[Brian Hurt <bhurt@spnz.org>]

On Thu, 3 Nov 2005, Seth J. Fogarty wrote:

> First question: I notice references are implemented using mutable
> records. Does this imply tuples of references are slower than mutable
> records?
> I.E.
> type a = int ref * int ref * int ref
> vs
> type a = {mutable a : int; mutable b : int; mutable c : int}

The mutable structure will almost certainly be less memory and faster. 
The tuple of structures will be a tuple of three pointers to three 
different mutable integers.  The structure will simply be three integers, 
stored unboxed in the structure.

A usefull trick for answering these sorts of questions is to use ocamlopt 
-S and look at the generated assembly code.

>
> Second: I need a non-varient data type.
> It needs to store three integers and six mutable boolean.
> I would like this to be done as compactly as possible, ideally in 128
> contiguious bits.

The best way to store multiple booleans compactly and mutable is as 
bitfields in an int.  As such, a structure like:

type t = { x: int; y: int; z: int; mutable bitfield: int }

is probably your best bet.  Note that the above structure takes up only 40 
bytes of memory on 64-bit systems, 20 bytes on 32-bit systems.

>
> Will either records or tuples store these contiguously?
> If I use tuples and references, will ocamlc 'compact' booleans, or
> give them 32 bits each? I think this is highly unlikely.
> If I use records, will ocamlc 'compact' booleans, or give them 32 bits each?
> If I use an integer to represent all six booleans, is there an easy
> way to gain access to/flip a single bit? I can only find shifting
> operations in pervasives

Ocaml will generall give a full word to every individual variable, even 
booleans and chars.  The pervasives module is automatically opened, so 
anything in it is automatically available to you.  So you can write code 
like:

let get_bool3 s = ((s.bitfield lsl 3) land 1) != 0;;

Note that Ocaml will rather aggressively inline this function, so it's not 
that expensive.

>
> Third question: How aggressive/intelligent is the ocamlc inlining?
> Should I worry about inlining functions that I expect to be used
> millions of times?

The general rule here is that you don't need to worry about it.  One thing 
to remember is that function calls aren't that expensive.  On modern 
hardware, I've timed function calls as costing about 1.5 clock cycles. 
This is compared to 100-350+ clock cycles for a cache miss.  I wouldn't 
worry about it.

Look up the post I made a couple of days ago, my list for what order you 
should optimize in.  Frankly, it's sounding a lot like you're prematurely 
optimizing.

Brian