- 2007/2/13, Grant Olson <olsongt@...>:
> I've got some rather large records that contain a bunch of OpenGL vertex

the {md3 with surfaces=new_surfaces} contruct make a copy of the old

> information. These also have associated textures. Sometimes these get

> 're-skinned' where I replace the OpenGL textures with something like:

>

> {md3 with surfaces=new_surfaces}

>

> Quick spot checking of the memory seems to be okay, but I just wanted to

> confirm if this copy operation is or isn't copying the contents of other

> immutable fields within the record, in particular the extremely large vertex

> data that is maintained in a different field. I can change my approach if

> it is.

md3. Then all a record really contain in the "C" meaning of contain,

is integer and pointer. So your extremely large data is not copied,

only the pointer to it is. - On Wednesday 14 February 2007 07:17, Joel Reymont wrote:
> So what is the efficient alternative (thinking of Zippers in Haskell)?

Exactly as Lukasz said, you must convey whether or not a substitution was made

and, when no substitutions are made, you must return the input expression.

Physical equality is perfect for this. If no substitution is made then you

return the input unaltered and the caller can verify this by noticing that

the return value is physically equal to the original. Many other languages

(e.g. SML) do not provide physical equality AFAIK.

As Lukasz suggested, you can use other approaches like boxing the result with

None indicating that no substitution was made, but boxing is slow, or you can

raise an exception (e.g. Exit) if no substitution was made. Physical equality

is probably faster though, as it just compares pointers and the "exceptional"

route is the most common route in term rewriting.

In terms of software engineering, factor out the recursion into a separate

function, so you have a recursive higher-order rewrite function that accepts

a rule function.

The naive implementation is:

let rec rewrite rule e = match e with

| `Int _ | `Var _ -> rule e

| `Add(f, g) -> rule(`Add(rewrite rule f, rewrite rule g))

| `Mul(f, g) -> rule(`Mul(rewrite rule f, rewrite rule g));;

Using physical equality we can write:

let compose2 f g e f' op g' = if f==f' && g==g' then e else op f' g'

let ( +: ) f g = `Add(f, g)

let ( *: ) f g = `Mul(f, g)

let rec rewrite rule e = match e with

| `Int _ | `Var _ -> rule e

| `Add(f, g) -> compose f g e (rewrite rule f) ( +: ) (rewrite rule g)

| `Mul(f, g) -> compose f g e (rewrite rule f) ( *: ) (rewrite rule g)

The subst function can be written in terms of this optimised rewrite function:

let subst var value = rewrite (function `Var v when v=var -> value | e -> e)

This does only minimal copying. When implementing a term rewriter, like

Mathematica, this is one of the single most important optimisations. You can

even improve this optimisation by tagging expressions to avoid traversing

them again when they have already been completely rewritten according to a

given set of rules.

This optimisation applies to lots more than just term rewriting. Consider a

simple insertion sort designed to be fast for almost-sorted lists (one of my

entries on Code Codex):

# let rec sort = function

| [] -> []

| h1::t as list -> match sort t with

| h2::t when h1>h2 -> h2::sort(h1::t)

| t' -> if t==t' then list else h1::t';;

val sort : 'a list -> 'a list = <fun>

Thanks to physical equality, this returns as much of the original list as

possible, doing no allocation when applied to a sorted list. (If you

replace "if t==t' then list else h1::t'" with "h1::t'" then this function

will always copy the entire list)

When using immutable data structures in performance-critical code, you must

leverage this technique to avoid copying at all costs. This is particularly

important to remember because performance profiling does not explain the

problem but, rather, simply indicates a large amount of time spent in the GC

with no indication of which function is generating all the garbage.

--

Dr Jon D Harrop, Flying Frog Consultancy Ltd.

OCaml for Scientists

http://www.ffconsultancy.com/products/ocaml_for_scientists