🔒 Locked

Fast Vector Math library for .Net

Started by teichgraf Feb 29, 2008 at 3:38 AM 14 replies 20.2k views

Original Post

Feb 29, 2008 at 3:38 AM

Hello I am searching for a non-commercial fast vector algebra library, which has bindings for .Net and implements some object-oriented features like operator overloading. It would also be good if it uses SIMD instructions. All .Net math libraries that I found are either commercial or they don't support a nice interface. Maybe I have to port a C/C++ lib on my own. But I don't want to reinvent the wheel. :( Thanks in advance. [Edited by - teichgraf on February 29, 2008 4:05:41 AM]

Sirisian

Feb 29, 2008 at 1:17 PM

Microsoft.DirectX reference.

Mike.Popoloski

Feb 29, 2008 at 1:25 PM

You can take a look at SlimDX, which contains a rather full featured math library. Most of it is implemented in C#, whereas some is passed on to D3DX through C++/CLI.

In our case, we found that even though D3DX uses asm and per-machine optimizations to make its library as fast as possible, it was still beneficial for us to reimplement a lot of the functionality because the cost of interop and marshaling was so high.

teichgraf

Mar 2, 2008 at 8:58 AM

Thanks for the replies!
I thought that I have to implement it. :-(
Fortunately I don't need a full featured math lib.

So what could be the fastest way to code a vector3d / vector2d class with a nice interface to use.
The nicest would be if I have a VectorN class with all operators and Vector3 / Vector2 which are derived from VectorN. So i don't have to implement the operators twice. But I think this is also slow because of the virtual calls and for-loops in the operators.
Maybe it could be the fastest to implement the Vector3 / Vector2 separate as structs or sealed classes?

How could I implement them for float and double without having separate classes. With C# generics I don't know how to do this like in C++. ?

I would appreciate it if I could get some advice on this.

Thanks in advance.

Ezbez

Mar 2, 2008 at 9:07 AM

The problem with a VectorN abstract base class is that the operators would take VectorNs as parameters. However, a Vector3 cannot be added to a Vector2. The same goes for most operations. This means that you'd really want one operator to take two Vector3s and another to take two Vector2s, but none to take one Vector3 and one Vector2. However, all you'd have is ones that take both VectorNs which could be given one of each vector type.

Fiddler

Mar 2, 2008 at 9:25 AM

One other problem, possibly greater, is that classes have hidden overhead (the ability to inherit and implement interfaces comes at a cost). Moreover, they cannot be allocated on the stack, and have worse locality of reference when compared to structs (which are value objects).

OpenTK also comes with a fairly full-featured math library (Vectors, Matrices, Quaternions). As a bonus, it contains both single precision and double precision structs, which will come in handy in the future when video cards will support 64bit precision. It also works on all platforms, not just windows. No SIMD though.

If you are using .Net 3.0, you can use WPF math functions too (full-featured, too).

[Edited by - Fiddler on March 2, 2008 10:25:21 AM]

teichgraf

Mar 2, 2008 at 1:29 PM

Thanks again for the answers.

OpenTK sounds interesseting. But I miss a Matrix33 and a VectorN class. Maybe I could extent the OpenTK lib.
At the moment I use Tao.OpenGl for rendering. So it should be no problem to switch to OpenTK.

By the way, how could one use SIMD instructions in C#?

unsafe{	__asm	{	}}

Geoff C

Mar 2, 2008 at 5:32 PM

I am on a same or similar search. The only reason it might be similar and not the same is that I am looking for one written with managed code and not just with an interface. (This might not fit your speed requirement?)

So far, the most promising I have found in the price range we are discussing are the Sharp3d Math Library at CodePlex from ekampf (forgot the person's name). It is written in C# and has online suggestions, one of which is to convert calls to fields instead of properties for a 15-20% speed improvement (if I remember the suggestion correctly).

There is also a great discussion of a C# Vector Type at CodeProject by Richard Potter which has lots of good information and feedback with other people's opinions on how it should be coded (much of which the author took). The boxing/unboxing problem when structs are used with collection classes is solved in the NetFramework 2.0 with generics (methinks).

Good luck!
-- Geoff

cignox1

Mar 3, 2008 at 1:02 AM

Another possible problem I see with a generic class is that unless you specialize pretty much all basic methods, you will end up with a lot of loops "for (int i = 0; i < vector_size; i++) ..." wich are not a really good thing for performance. I don't know how much smart is the compiler, nor generics have some features to avoid this, but if you must specialize the operations then you loose the gain of a generic vector anyway...

teichgraf

Mar 3, 2008 at 2:19 AM

Thank for the infos.

@Geoff C: I would also prefer a managed version.
I have also found the Sharp3D lib. at Codeplex and many other. But I think the project is dead (see the source code commits). ?
The Codeproject implementation looks nice.

teichgraf

Mar 3, 2008 at 4:21 AM

I have made some performance tests for three Vector3 float structs: OpenTK, Sharp3D and the Vector struct from Richard Potters Codeproject Codeproject .
For the test I used my own built OpenTK, a own built Sharp3D Dll and a separate Dll-project for Potters Vector3 class. I converted Potters Vector3 to float.

Here are the results for the release build:

Testing 30.000.000 iterations.OpenTK Add Func         - 00:00:00.3910775OpenTK Add Op           - 00:00:01.3609497Sharp3 Add Func         - 00:00:01.0324446Sharp3 Add Op           - 00:00:01.6581686Potter Add              - 00:00:01.6894548OpenTK Sub Func         - 00:00:00.3754344OpenTK Sub Op           - 00:00:01.3609497Sharp3 Sub Func         - 00:00:01.0480877Sharp3 Sub Op           - 00:00:01.6738117Potter Sub              - 00:00:01.6581686OpenTK Mul Scalar Func  - 00:00:00.3597913OpenTK Mul Scalar Op    - 00:00:01.2983773Sharp3 Mul Scalar Func  - 00:00:01.0637308Sharp3 Mul Scalar Op    - 00:00:01.7676703Potter Mul Scalar       - 00:00:01.5643100OpenTK Div Scalar Func  - 00:00:00.5005792OpenTK Div Scalar Op    - 00:00:01.2670911Sharp3 Div Scalar Func  - 00:00:01.7676703Sharp3 Div Scalar Op    - 00:00:02.3621081Potter Div Scalar       - 00:00:02.3777512OpenTK Dot              - 00:00:00.9855153Sharp3 Dot              - 00:00:01.0011584Potter Dot              - 00:00:01.2201618OpenTK Cross Copy       - 00:00:01.5799531OpenTK Cross Ref        - 00:00:00.4380068Sharp3 Cross            - 00:00:01.7363841Potter Cross            - 00:00:01.8615289OpenTK Length           - 00:00:00.7821550Sharp3 Length           - 00:00:00.7821550Potter Length           - 00:00:04.2082447OpenTK Length Squared   - 00:00:00.3754632Sharp3 Length Squared   - 00:00:00.3598189OpenTK Normalize        - 00:00:02.0024704Sharp3 Normalize        - 00:00:02.7533968Potter Normalize        - 00:00:10.3252380OpenTK Normalize Fast   - 00:00:02.1589134

It seems that the methods from OpenTK are the fastest. It's hardly surprising that passing the arguments by ref is significant faster than the usually copy pass.

Here is the complete Source code for my performance test:

using System;using System.Collections.Generic;using System.Text;namespace PerfTest_Vector3{   class Program   {      private delegate void TestDel();      static void Main(string[] args)      {         // Init.         Random rand = new Random();         float scalar = (float)rand.NextDouble();         float x1 = (float)rand.NextDouble();         float y1 = (float)rand.NextDouble();         float z1 = (float)rand.NextDouble();         float x2 = (float)rand.NextDouble();         float y2 = (float)rand.NextDouble();         float z2 = (float)rand.NextDouble();         OpenTK.Math.Vector3 tk1 = new OpenTK.Math.Vector3(x1, y1, z1);         OpenTK.Math.Vector3 tk2 = new OpenTK.Math.Vector3(x2, y2, z2);         OpenTK.Math.Vector3 tk3 = new OpenTK.Math.Vector3();         Sharp3D.Math.Core.Vector3F sh1 = new Sharp3D.Math.Core.Vector3F(x1, y1, z1);         Sharp3D.Math.Core.Vector3F sh2 = new Sharp3D.Math.Core.Vector3F(x2, y2, z2);         Sharp3D.Math.Core.Vector3F sh3 = new Sharp3D.Math.Core.Vector3F();         Vector3F rp1 = new Vector3F(x1, y1, z1);         Vector3F rp2 = new Vector3F(x2, y2, z2);         Vector3F rp3 = new Vector3F();         const int iters = 30000000;                  // Test         Console.WriteLine("Testing {0:n} iterations.", iters);         Console.WriteLine();         // Test Add         Test("OpenTK Add Func        ", iters, delegate() { OpenTK.Math.Vector3.Add(ref tk1, ref tk2, out tk3); });         Test("OpenTK Add Op          ", iters, delegate() { tk3 = tk1 + tk2; });         Test("Sharp3 Add Func        ", iters, delegate() { Sharp3D.Math.Core.Vector3F.Add(sh1, sh2, ref sh3); });         Test("Sharp3 Add Op          ", iters, delegate() { sh3 = sh1 + sh2; });         Test("Potter Add             ", iters, delegate() { rp3 = rp1 + rp2; });         Console.WriteLine();         // Test Sub         Test("OpenTK Sub Func        ", iters, delegate() { OpenTK.Math.Vector3.Sub(ref tk1, ref tk2, out tk3); });         Test("OpenTK Sub Op          ", iters, delegate() { tk3 = tk1 - tk2; });         Test("Sharp3 Sub Func        ", iters, delegate() { Sharp3D.Math.Core.Vector3F.Subtract(sh1, sh2, ref sh3); });         Test("Sharp3 Sub Op          ", iters, delegate() { sh3 = sh1 - sh2; });         Test("Potter Sub             ", iters, delegate() { rp3 = rp1 - rp2; });         Console.WriteLine();         // Test Mul Scalar         Test("OpenTK Mul Scalar Func ", iters, delegate() { OpenTK.Math.Vector3.Mult(ref tk1, scalar, out tk3); });         Test("OpenTK Mul Scalar Op   ", iters, delegate() { tk3 = tk1 * scalar; });         Test("Sharp3 Mul Scalar Func ", iters, delegate() { Sharp3D.Math.Core.Vector3F.Multiply(sh1, scalar, ref sh3); });         Test("Sharp3 Mul Scalar Op   ", iters, delegate() { sh3 = sh1 * scalar; });         Test("Potter Mul Scalar      ", iters, delegate() { rp3 = rp1 * scalar; });         Console.WriteLine();         // Test Div Scalar         Test("OpenTK Div Scalar Func ", iters, delegate() { OpenTK.Math.Vector3.Div(ref tk1, scalar, out tk3); });         Test("OpenTK Div Scalar Op   ", iters, delegate() { tk3 = tk1 / scalar; });         Test("Sharp3 Div Scalar Func ", iters, delegate() { Sharp3D.Math.Core.Vector3F.Divide(sh1, scalar, ref sh3); });         Test("Sharp3 Div Scalar Op   ", iters, delegate() { sh3 = sh1 / scalar; });         Test("Potter Div Scalar      ", iters, delegate() { rp3 = rp1 / scalar; });         Console.WriteLine();         // Test Dot         Test("OpenTK Dot             ", iters, delegate() { scalar = OpenTK.Math.Vector3.Dot(tk1, tk2); });         Test("Sharp3 Dot             ", iters, delegate() { scalar = Sharp3D.Math.Core.Vector3F.DotProduct(sh1, sh2); });         Test("Potter Dot             ", iters, delegate() { scalar = rp1.DotProduct(rp2); });         Console.WriteLine();         // Test Cross         Test("OpenTK Cross Copy      ", iters, delegate() { tk3 = OpenTK.Math.Vector3.Cross(tk1, tk2); });         Test("OpenTK Cross Ref       ", iters, delegate() { OpenTK.Math.Vector3.Cross(ref tk1, ref tk2, out tk3); });         Test("Sharp3 Cross           ", iters, delegate() { sh3 = Sharp3D.Math.Core.Vector3F.CrossProduct(sh1, sh2); });         Test("Potter Cross           ", iters, delegate() { rp3 = rp1.CrossProduct(rp2); });         Console.WriteLine();         // Test Length         Test("OpenTK Length          ", iters, delegate() { scalar = tk1.Length; });         Test("Sharp3 Length          ", iters, delegate() { scalar = sh1.GetLength(); });         Test("Potter Length          ", iters, delegate() { scalar = rp1.Magnitude; });         Console.WriteLine();         // Test Length Squared         Test("OpenTK Length Squared  ", iters, delegate() { scalar = tk1.LengthSquared; });         Test("Sharp3 Length Squared  ", iters, delegate() { scalar = sh1.GetLengthSquared(); });         Console.WriteLine();         // Test Normalize         Test("OpenTK Normalize       ", iters, delegate() { tk1.Normalize(); });         Test("Sharp3 Normalize       ", iters, delegate() { sh1.Normalize(); });         Test("Potter Normalize       ", iters, delegate() { rp1.Normalize(); });         Console.WriteLine();         // Test Normalize Fast         Test("OpenTK Normalize Fast  ", iters, delegate() { tk1.NormalizeFast(); });         Console.WriteLine();         Console.WriteLine();         Console.WriteLine("Finished");         Console.ReadLine();      }      private static void Test(string prefix, int iters, TestDel testFunc)      {         DateTime start = DateTime.Now;         for (int i = 0; i < iters; i++)         {            testFunc();         }         TimeSpan span = DateTime.Now - start;         Console.WriteLine("{0} - {1}", prefix, span);      }   }}

Ezbez

Mar 3, 2008 at 4:37 AM

Quote:
Original post by cignox1
Another possible problem I see with a generic class is that unless you specialize pretty much all basic methods, you will end up with a lot of loops "for (int i = 0; i < vector_size; i++) ..." wich are not a really good thing for performance. I don't know how much smart is the compiler, nor generics have some features to avoid this, but if you must specialize the operations then you loose the gain of a generic vector anyway...

Oops! I think you're thinking of the wrong type of vector! There's the math "vector" that the OP is looking for which is a direction and a speed/distance. And there's also the container that you're talking about. Easy mistake to make.

Julian90

Mar 3, 2008 at 6:59 AM

Quote:
Original post by Ezbez
Quote:
Original post by cignox1
Another possible problem I see with a generic class is that unless you specialize pretty much all basic methods, you will end up with a lot of loops "for (int i = 0; i < vector_size; i++) ..." wich are not a really good thing for performance. I don't know how much smart is the compiler, nor generics have some features to avoid this, but if you must specialize the operations then you loose the gain of a generic vector anyway...

Oops! I think you're thinking of the wrong type of vector! There's the math "vector" that the OP is looking for which is a direction and a speed/distance. And there's also the container that you're talking about. Easy mistake to make.

No, I think he was thinking a maths vector, someone mentioned a VectorN class from which a Vector2 and Vector3 would derive and he was referring to the need to loop in implementing (for example) addition in a VectorN class.

Quote:
Original post by Ezbez
The problem with a VectorN abstract base class is that the operators would take VectorNs as parameters. However, a Vector3 cannot be added to a Vector2. The same goes for most operations. This means that you'd really want one operator to take two Vector3s and another to take two Vector2s, but none to take one Vector3 and one Vector2. However, all you'd have is ones that take both VectorNs which could be given one of each vector type.

You can avoid the Vector2 + Vector3 problem by using generics plus phantom types, the VectorN has an unused generic type parameter (say N) then Vector2 and Vector3 both supply different (private) types for N preventing a Vector2 being added to a Vector3. Doing this also means that all of the size information is available for the compiler at compiler time however I don't think the compiler will take advantage of this to optimize the code for Vector2 and Vector3.

cignox1

Mar 4, 2008 at 1:25 AM

Quote:
Original post by Julian90
Quote:
Original post by Ezbez
Quote:
Original post by cignox1
Another possible problem I see with a generic class is that unless you specialize pretty much all basic methods, you will end up with a lot of loops "for (int i = 0; i < vector_size; i++) ..."

Oops! I think you're thinking of the wrong type of vector! There's the math "vector" that the OP is looking for which is a direction and a speed/distance. And there's also the container that you're talking about. Easy mistake to make.

No, I think he was thinking a maths vector, someone mentioned a VectorN class from which a Vector2 and Vector3 would derive and he was referring to the need to loop in implementing (for example) addition in a VectorN class.

Yes, that's what I was refering to.

teichgraf

Mar 4, 2008 at 1:50 AM

Quote:
cignox1
Yes, that's what I was refering to.

I also pointed this out in a previous post:

Quote:
Original post by teichgraf
The nicest would be if I have a VectorN class with all operators and Vector3 / Vector2 which are derived from VectorN. So i don't have to implement the operators twice. But I think this is also slow because of the virtual calls and for-loops in the operators.

But I have another question:

Quote:
Original post by Fiddler
OpenTK also comes with a fairly full-featured math library (Vectors, Matrices, Quaternions).As a bonus, it contains both single precision and double precision structs, which will come in handy in the future when video cards will support 64bit precision.

I did not found double and float structs. There are only float structs in the current implementation.
And how can one write generics in .Net 2.0 for double and float. Such as Vector3 ... ?

Thanks in advance.

Fiddler

Mar 12, 2008 at 4:26 AM

Quote:
I did not found double and float structs. There are only float structs in the current implementation.
And how can one write generics in .Net 2.0 for double and float. Such as Vector3 ... ?

Thanks in advance.

Check out the code from SVN. We are adding a whole lot of functionality to the math library for the upcoming version (possibly by this weekend), including Bezier curves, double precision structures and linear algebra operators.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.