Version française
Home     About     Download     Resources     Contact us    
Browse thread
References, compact bollean values (and other questions)
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Seth J. Fogarty <sfogarty@g...>
Subject: References, compact bollean values (and other questions)
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.