References, compact bollean values (and other questions)

References, compact bollean values (and other questions)

[Seth J. Fogarty]

So I am implementing a DPLL procedure for CNF sat. This is the first
time, for me, that I've been programming in ocaml that speed is
absolutely critical. I will have a small code base running for
literally days on end. Thus I have some speed/efficiently questions.

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}

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.

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

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

Fourth question: If you got this far and still want to help, is there
anything obviously wrong with the following imperitive linked list
implementation in terms of speed? I expect traversal to be rare. I
have defined add, delete, and insert operations (that are easily
undoable).

type 'a ll = Nul | Node of 'a * 'a ll ref | Head of 'a ll ref
type 'a llptr = 'a ll * 'a ll (*the predecessor and the node pointed to.*)
type 'a undo = 'a ll ref * 'a ll
let undo ((a, b) : 'a undo) = a := b
let delete (llptr : 'a llptr) : 'a undo =
   match llptr with
     |(Head b, (Node (_, b') as deleted))
     |(Node (_, b), (Node (_, b') as deleted)) -> b := !b'; (b, deleted)
     |_ -> failwith "delete"

--
Seth Fogarty             sfogarty@[gmail.com|rice.edu|livejournal]
Neep-neep at large    AIM: Sorrath
"I know there are people in this world who do not love their fellow
human beings - and I hate people like that" --Tom Lehrer.

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

[Brian Hurt]

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

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

[skaller]

On Thu, 2005-11-03 at 18:20 -0600, Brian Hurt wrote:
> 
> 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.

Yes but note it depends what you are doing.

A field is NOT a first class value. A reference is.
So if you use functional update to rebuild a record,
you are not tickling the write barrier -- true even
if a field is a reference.

So it depends what you are doing with these records, IMHO.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net