CODEWITHSUNDEEP
c#f#functional-programmingocaml
zer0ne
zer0ne

Reputation: 423

How to make this functional-style code more performant while maintaining its syntax

I would like to write this operation 

Matrix.Multiply(source,target)
target.Add(offsets)

in this mathematical style

target = Matrix * source + offsets;

However, I'm also concerned about performance. (In fact, the above operation will be run in a tight loop.) I don't want to create a new vector for each matrix-vector multiplication and another new vector for the vector addition.

How can I implement the above operation in C# or F# (or any functional language that you know) so that style and performance can be both achieved?

Sorry for this naive question. I'm sure this desire is so fundamental.

Upvotes: 3

Views: 276

Answers (4)

Mike Perrenoud
Mike Perrenoud

Reputation: 67898

Making the assumption that the Matrix class is yours, you can overload the operators:

public static Matrix operator *(Matrix x, Matrix y)
{
    return Matrix.Multiply(x, y);
}

public static Matrix operator +(Matrix x, OffsetsType offsets)
{
    x.Add(offsets);
    return x;
}

So, this expression (which is a modification of the one in your question because in your question you are multiplying Matrix by source and that doesn't make sense):

target = target * source + offsets;

broken out, would look like this:

var z = Matrix.Multiply(target, source);
z.Add(offsets);
target = z;

Upvotes: 2

gasche
gasche

Reputation: 31459

A well-known technique, that is for example at the heart of the Repa library of high-performance numeric arrays, is to define on top of the basic "2D array of integer" structure a higher-level data structure that delays the operations you want to perform, along with an intepretation/normalization function that will finally perform those operations, applying any optimization it deems profitable.

Concretely, in your example, and I think most current answers have missed this, you want A * B + C to be rewritten not into

add(multiply(A,B), C)

or in OO styl e

A.multiply(B).add(C)

but instead

multiply_and_add(A,B,C)

where multiply_and_add is a specialez, lower-level operation that does both operations at once and is more optimized. Similarly, it is well-known that for arbitrary matrices A, B, C, D, the product A * B * C * D may be more efficiently computed as A * ((B * C) * D) rather than A * (B * (C * D))), depending on the operand dimensions. So a purely local approach (expressing each operation on arrays of integers) does not work, you need expression-global rewrites for optimal efficiency -- as done by the hackish template libraries in C++.

The solution is to move from int array array to a refined datatype, for example:

type matrix =
  | Raw of int array array
  | Add of matrix * matrix
  | Mult of matrix * matrix

and then provide a eval : matrix -> int array array function that "interprets" those matrix descriptions (in essence abstract syntax trees of matrix operations) by possibly applying domain-specific optimizations. For a naive example:

let rec eval = function
  | Raw m -> m
  | Add(Mult(a,b), c) | Add(c, Mult(a,b)) ->
    multiply_and_add (eval a) (eval b) (eval c)
  | Add (a, b) -> add (eval a) (eval b)
  | Mult (a, b) -> mult (eval a) (eval b)

You can then define the syntactic sugar of your liking to make the matrix constructors easier to read.

module Matrix = struct
  let (!) m = Raw m
  let (+) a b = Add (a, b)
  let (*) a b = Mult (a, b)
end

let ... = eval Matrix.(!A * !B + !C)

Upvotes: 10

Robert Rouhani
Robert Rouhani

Reputation: 14678

If performance is your largest concern, the fastest way to do this is to define Matrix as a struct if it isn't already, then use ref/out parameters instead of ones that create a lot of copies.

public void Multiply(ref Matrix left, ref Matrix right, out Matrix result)

This is the approach taken by a number of C# game/graphics frameworks.

There's also this very interesting article about optimizing OpenTK's matrix multiplication, which might give you ideas about how to further speed up matrix operations: Making OpenTK matrix multiplication faster

Of course, if you matrix class isn't of a fixed size, then this information is largely useless.

Upvotes: 0

Brendan Hill
Brendan Hill

Reputation: 3742

You can create custom operators for your classes:

http://msdn.microsoft.com/en-us/library/8edha89s.aspx

This gives you the syntax you want, but still functional programming behind the scenes. Performance will be no different since .NET will just compile your operator-using code to be function-calling instead.

Upvotes: -1

Related Questions