efficient vector math...

[BGB]

sorry if I am missing something obvious here, but I am hoping for
suggestions on a relatively efficient general-purpose way to handle
vector math and similar (in the sense of geometric vectors...).

I will likely be writing any code myself, so the request is for ideas
for a general design.

this is for a personal project (most of the rest of the project uses C,
but this will be for the Java part of the project). Java isn't really my
main language FWIW...



purposes and requirements:
performance should be good, and interface should also be nice (if possible);
the app will be soft real-time on a custom JVM (JavaME style), and the
GC is slow and so avoiding GC (by minimizing garbage) is preferable (so
user will not experience stalls);
it doesn't need to deal with arbitrary N-sized vectors, only 2, 3, and 4
element vectors (XYZW), and also Quaternions;
likely vector size and usage will be considered as part of the type (a
Vec2 is not a Vec3 which is not a Vec4 which is not a Quat);
the vectors will potentially be recalculated frequently and in large
numbers;
....


so, a few possibilities:

A, immutable vectors:
pros: clean interface, supports merging and sharing vectors, ...
cons: many vectors may be created, likely creating lots of garbage.

B, mutable vectors:
pros: likely to reduce garbage (most recalculation can reuse existing
vectors);
cons: vectors can't be shared (since they may change without warning),
and the interface is more awkward (vector values are copied, meaning
vectors need to be provided to use for storing temporary values, ...).

C, supporting both (as different types):
pros: can mix and match as needed;
cons: 2x or 3x as many types (mutable and immutable versions of each
size, 3x if both versions are subclasses of a common abstract type),
more awkward class names to distinguish them, more methods, ...

D, supporting both (as different operations on the same type):
pros: allows mixing and matching use-patterns (general);
cons: use-case ambiguity (need to infer intended use from context).


arrays and indices ("float[] vecs=new float[nvecs*4];" or similar):
pros: errm... likely compact memory...
cons: likely overly ugly/awkward.

I have been considering this matter over the past several days.
leaning at the moment is for option D.


example classes:
basic: Vec2, Vec3, Vec4, Quat
multi-typed (option C):
Vec2a, Vec3a, Vec4a, Quata //abstract
Vec2c, Vec3c, Vec4c, Quadc //constant/immutable
Vec2n, Vec3n, Vec4n, Quatn //mutable

Vec#c and Vec#n would be subtypes of Vec#a, so methods accepting the
abstract forms would accept both, with the mutable and immutable forms
differing in terms of their external behavior.

options B and D would likely use a "pool" for freed vectors of a given
type (garbage reduced by manually "freeing" spare vectors, whereas A
would likely try to do a lookup and on failure create a new vector).

matrix math may also be considered.


suggestions, opinions, or other options?...

 

[markspace]

sorry if I am missing something obvious here, but I am hoping for
suggestions on a relatively efficient general-purpose way to handle
vector math and similar (in the sense of geometric vectors...).

1. Sorry but tl;dr.

2. Don't reinvent the wheel.

<http://kenai.com/projects/jogl/>

<https://java3d.dev.java.net/>

<http://www.jmonkeyengine.com/>

 

[Tom Anderson]

Use immutable vectors.

Whatever method you go for, there will be garbage, reusage or both.
Anything you write yourself will be less efficient than the GC written
by the Java library programmers.

He's talking about running this on his own VM, so the GC written by the
Java VM (not library) programmers is immaterial.

Although perhaps he might be better off writing something which makes
garbage, and spending his spare brain power on improving his GC.

tom

 

[BGB]

He's talking about running this on his own VM, so the GC written by the
Java VM (not library) programmers is immaterial.

Although perhaps he might be better off writing something which makes
garbage, and spending his spare brain power on improving his GC.

yeah...

it is custom written, and I have determined roughly aligns with the Java
ME CLDC profile in terms of the supported language subset.


I am using a concurrent conservative mark/sweep collector.

being a conservative GC, the stalls are a bit steep, and the thing
doesn't do reference counting, meaning that any garbage produced will
pollute the heap until the GC runs (garbage minimization is then a major
concern...).

note that it is concurrent, but does use a SW write barrier, and any
thread hitting this write barrier during a GC pass will sleep until the
GC completes (effectively stalling any threads which try to write to the
heap during a GC, which in Java's case, is pretty much any of them).


note, I don't use a precise GC mainly for the fact that the GC is mostly
also used for a large amount of C code, and is not specific to my
mimi-JVM. precise GC's are notably more of a hassle to work with from C
(since one has to track GC roots and similar, and be very careful with
assignments, ...), so I am not so inclined to use them.


or such...

 

[BGB]

Use immutable vectors.

Whatever method you go for, there will be garbage, reusage or both.
Anything you write yourself will be less efficient than the GC written
by the Java library programmers.

note: this would apply if I were using a standard JVM.
I am not for sake of the project.

You do not specify which calculations need to be done with the
vectors. When you write your immutable vectors you can 'cheat' and
write some special methods that do some of the very common
calculations in a non-immutable way internally while exposing an
immutable interface. IIRC BigInteger does this, there is a mutable
internal class that BI uses for intermediate values that is never
exposed in the class interface.

3D engine scripting stuff...

this will not be for anything rendering related (luckily), but will have
to deal with things such as (potentially) entity AI's and moving objects
around in the scene graph (projectiles, ...).

typical calculations are likely to be vector addition, subtraction,
cross product, ...

If you are worried about speed then you may well find more problems
with the C / Java interface than with GC.

I have considered the above...

however, my JNI implementation is not likely to be a big issue, since
the JNI interface is basically just a thin wrapper over the machinery
used internally, and also the thing is currently using an interpreter
anyways (I have not yet gotten around to writing a JIT for JBC yet).


but, the main performance worry at the moment is the GC, since this
thing causes obvious pauses when it runs...

 

[BGB]

1. Sorry but tl;dr.

2. Don't reinvent the wheel.

<http://kenai.com/projects/jogl/>

<https://java3d.dev.java.net/>

<http://www.jmonkeyengine.com/>

Note:
non-standard/custom-written JVM running inside a modified Quake2 engine
(as an intended extension/replacement of the standard "gamex86.dll"
mechanism...).

so, these libs will do me little good absent going through the pain of
porting them or implementing them myself (which would likely require
more of the JavaSE featureset, vs the currently planned JavaME CLDC only
support), unless there is some specific design note worth considering...


note: the VM also interacts with another custom VM/language (BGBScript,
which is based partly on JavaScript and ActionScript, and mostly
implements ECMA-262-5th Ed...).

actually, both VM's share the same underlying implementation and
MM/GC/OO facilities (the same machinery does Class/Instance and
Prototype OO).


or such...

 

[Arne Vajhøj]

sorry if I am missing something obvious here, but I am hoping for
suggestions on a relatively efficient general-purpose way to handle
vector math and similar (in the sense of geometric vectors...).

I will likely be writing any code myself, so the request is for ideas
for a general design.

this is for a personal project (most of the rest of the project uses C,
but this will be for the Java part of the project). Java isn't really my
main language FWIW...



purposes and requirements:
performance should be good, and interface should also be nice (if
possible);
the app will be soft real-time on a custom JVM (JavaME style), and the
GC is slow and so avoiding GC (by minimizing garbage) is preferable (so
user will not experience stalls);
it doesn't need to deal with arbitrary N-sized vectors, only 2, 3, and 4
element vectors (XYZW), and also Quaternions;
likely vector size and usage will be considered as part of the type (a
Vec2 is not a Vec3 which is not a Vec4 which is not a Quat);
the vectors will potentially be recalculated frequently and in large
numbers;
...


so, a few possibilities:

A, immutable vectors:
pros: clean interface, supports merging and sharing vectors, ...
cons: many vectors may be created, likely creating lots of garbage.

B, mutable vectors:
pros: likely to reduce garbage (most recalculation can reuse existing
vectors);
cons: vectors can't be shared (since they may change without warning),
and the interface is more awkward (vector values are copied, meaning
vectors need to be provided to use for storing temporary values, ...).

C, supporting both (as different types):
pros: can mix and match as needed;
cons: 2x or 3x as many types (mutable and immutable versions of each
size, 3x if both versions are subclasses of a common abstract type),
more awkward class names to distinguish them, more methods, ...

D, supporting both (as different operations on the same type):
pros: allows mixing and matching use-patterns (general);
cons: use-case ambiguity (need to infer intended use from context).

In general: A

With your special restrictions: B

Never C and D - they seem to combine the worst of A and B.

Arne

 

[Arne Vajhøj]

Use immutable vectors.

Whatever method you go for, there will be garbage, reusage or both.
Anything you write yourself will be less efficient than the GC written
by the Java library programmers.

Hm.

It is not unusual that specialized solutions are more efficient
than general solutions.

If you are worried about speed then you may well find more problems
with the C / Java interface than with GC.

He said that he would be using a custom JVM with a very slow GC, so ...

Arne

 

[BGB]

Hm.

It is not unusual that specialized solutions are more efficient
than general solutions.

yeah, dropping back in an array of spares may be faster than waiting for
the GC to reclaim the memory (via good old mark/sweep), and if anything
may shave off the amount of garbage some.

but, yes, this is mostly an artifact of a GC, which is decidedly not
very good (performance wise), but in general it works well provided one
can avoid a GC (usually this is done via semi-manual MM, IOW, actually
freeing stuff...).


whether or not this would be faster in a JVM with an actually decent GC
is an open question. I have my reasons here though (for both a GC and a
custom-written VM).

He said that he would be using a custom JVM with a very slow GC, so ...

yeah...

500ms or 1s or more is typical, ... which is very obvious in an
interactive 3D engine...

 

[BGB]

In general: A

With your special restrictions: B

I guess I will have to agree here...
A is cleaner, and likely a fast GC would clean things up effectively
without any obvious stalls (like in a real JVM).

B works because it can minimize garbage, despite being a little less
elegant.

Never C and D - they seem to combine the worst of A and B.

yeah, I guess I agree...


C seems like it would add too much complexity to be worthwhile...

D yeah, I guess is likely to be unreasonably error prone, and violates
the ideal of a single object that does a single thing in a single way
(similar object that does similar things in multiple ways).


so, plain mutable vectors it is probably...


well, there is a reason I posted this on usenet...

 

[John B. Matthews]

so, plain mutable vectors it is probably...

This simulation,

<http://sites.google.com/site/drjohnbmatthews/kineticmodel>

uses a mutable 2D org.gcs.kinetic.Vector:

<http://sites.google.com/site/drjohnbmatthews/kineticmodel/code#Vector>

Alternatively, JScicence offers a more general, immutable
org.jscience.mathematics.vector.Vector. It uses Javolution's stack
allocation feature to reduce garbage collection.

<http://www.jscience.org/>

 

[Kevin McMurtrie]

sorry if I am missing something obvious here, but I am hoping for
suggestions on a relatively efficient general-purpose way to handle
vector math and similar (in the sense of geometric vectors...).

I will likely be writing any code myself, so the request is for ideas
for a general design.

this is for a personal project (most of the rest of the project uses C,
but this will be for the Java part of the project). Java isn't really my
main language FWIW...



purposes and requirements:
performance should be good, and interface should also be nice (if possible);
the app will be soft real-time on a custom JVM (JavaME style), and the
GC is slow and so avoiding GC (by minimizing garbage) is preferable (so
user will not experience stalls);
it doesn't need to deal with arbitrary N-sized vectors, only 2, 3, and 4
element vectors (XYZW), and also Quaternions;
likely vector size and usage will be considered as part of the type (a
Vec2 is not a Vec3 which is not a Vec4 which is not a Quat);
the vectors will potentially be recalculated frequently and in large
numbers;
...


so, a few possibilities:

A, immutable vectors:
pros: clean interface, supports merging and sharing vectors, ...
cons: many vectors may be created, likely creating lots of garbage.

B, mutable vectors:
pros: likely to reduce garbage (most recalculation can reuse existing
vectors);
cons: vectors can't be shared (since they may change without warning),
and the interface is more awkward (vector values are copied, meaning
vectors need to be provided to use for storing temporary values, ...).

C, supporting both (as different types):
pros: can mix and match as needed;
cons: 2x or 3x as many types (mutable and immutable versions of each
size, 3x if both versions are subclasses of a common abstract type),
more awkward class names to distinguish them, more methods, ...

D, supporting both (as different operations on the same type):
pros: allows mixing and matching use-patterns (general);
cons: use-case ambiguity (need to infer intended use from context).


arrays and indices ("float[] vecs=new float[nvecs*4];" or similar):
pros: errm... likely compact memory...
cons: likely overly ugly/awkward.

I have been considering this matter over the past several days.
leaning at the moment is for option D.


example classes:
basic: Vec2, Vec3, Vec4, Quat
multi-typed (option C):
Vec2a, Vec3a, Vec4a, Quata //abstract
Vec2c, Vec3c, Vec4c, Quadc //constant/immutable
Vec2n, Vec3n, Vec4n, Quatn //mutable

Vec#c and Vec#n would be subtypes of Vec#a, so methods accepting the
abstract forms would accept both, with the mutable and immutable forms
differing in terms of their external behavior.

options B and D would likely use a "pool" for freed vectors of a given
type (garbage reduced by manually "freeing" spare vectors, whereas A
would likely try to do a lookup and on failure create a new vector).

matrix math may also be considered.


suggestions, opinions, or other options?...

Option A is the clean way but GC costs will completely dominate the CPU.
GC is indeed fast, but it's nowhere near as fast as small vector
operations.

Option B works but it brittle when caching and sharing is involved.
Mutable keys destroy many types of caches.

Option C: I've done mixed class types for bitmap rendering where
intermediate stages needed caching. Immutable was the special case
because caching and sharing were few compared to the many calculations.
The abstract base class for both supported all read operations and
defined methods getMutable() and getImmutable(). The
getMutable/getImmutable implementations returned the 'this' reference or
a new object as needed. No casting or 'instanceof' was needed.


D sounds messy.

 

[BGB]

sorry if I am missing something obvious here, but I am hoping for
suggestions on a relatively efficient general-purpose way to handle
vector math and similar (in the sense of geometric vectors...).

I will likely be writing any code myself, so the request is for ideas
for a general design.

this is for a personal project (most of the rest of the project uses C,
but this will be for the Java part of the project). Java isn't really my
main language FWIW...



purposes and requirements:
performance should be good, and interface should also be nice (if possible);
the app will be soft real-time on a custom JVM (JavaME style), and the
GC is slow and so avoiding GC (by minimizing garbage) is preferable (so
user will not experience stalls);
it doesn't need to deal with arbitrary N-sized vectors, only 2, 3, and 4
element vectors (XYZW), and also Quaternions;
likely vector size and usage will be considered as part of the type (a
Vec2 is not a Vec3 which is not a Vec4 which is not a Quat);
the vectors will potentially be recalculated frequently and in large
numbers;
...


so, a few possibilities:

A, immutable vectors:
pros: clean interface, supports merging and sharing vectors, ...
cons: many vectors may be created, likely creating lots of garbage.

B, mutable vectors:
pros: likely to reduce garbage (most recalculation can reuse existing
vectors);
cons: vectors can't be shared (since they may change without warning),
and the interface is more awkward (vector values are copied, meaning
vectors need to be provided to use for storing temporary values, ...).

C, supporting both (as different types):
pros: can mix and match as needed;
cons: 2x or 3x as many types (mutable and immutable versions of each
size, 3x if both versions are subclasses of a common abstract type),
more awkward class names to distinguish them, more methods, ...

D, supporting both (as different operations on the same type):
pros: allows mixing and matching use-patterns (general);
cons: use-case ambiguity (need to infer intended use from context).


arrays and indices ("float[] vecs=new float[nvecs*4];" or similar):
pros: errm... likely compact memory...
cons: likely overly ugly/awkward.

I have been considering this matter over the past several days.
leaning at the moment is for option D.


example classes:
basic: Vec2, Vec3, Vec4, Quat
multi-typed (option C):
Vec2a, Vec3a, Vec4a, Quata //abstract
Vec2c, Vec3c, Vec4c, Quadc //constant/immutable
Vec2n, Vec3n, Vec4n, Quatn //mutable

Vec#c and Vec#n would be subtypes of Vec#a, so methods accepting the
abstract forms would accept both, with the mutable and immutable forms
differing in terms of their external behavior.

options B and D would likely use a "pool" for freed vectors of a given
type (garbage reduced by manually "freeing" spare vectors, whereas A
would likely try to do a lookup and on failure create a new vector).

matrix math may also be considered.


suggestions, opinions, or other options?...

Option A is the clean way but GC costs will completely dominate the CPU.
GC is indeed fast, but it's nowhere near as fast as small vector
operations.

Option B works but it brittle when caching and sharing is involved.
Mutable keys destroy many types of caches.

Option C: I've done mixed class types for bitmap rendering where
intermediate stages needed caching. Immutable was the special case
because caching and sharing were few compared to the many calculations.
The abstract base class for both supported all read operations and
defined methods getMutable() and getImmutable(). The
getMutable/getImmutable implementations returned the 'this' reference or
a new object as needed. No casting or 'instanceof' was needed.


D sounds messy.

yeah.


in my implementation (a custom-written mini-JVM with a slow GC and no
JIT), option B is probably the best overall...

although sadly I am busy enough recently that I haven't gotten around to
implementing it as of yet...


the revised 'Option C' is an interesting idea, I may consider it...

I will guess it does not support direct access: 'vec.x' (since one needs
to either make it final or not final, or rely on good graces that one
does not assign it in the immutable case...).

I guess, "vec.getX()" or "vec.x()" should also work.


(below is untested, just assuming that javac will not barf...).


idly thinking here:
public class Vec3
{
private static final int MAX=1024;
private static Vec3[] cache;
private static int nCache;

private double x, y, z;

static {
cache=new Vec3[MAX];
nCache=0;
}

public Vec3()
{ this(0, 0, 0); }
public Vec3(double x, double y, double z)
{ this.x=x; this.y=y; this.z=z; }

public float x() { return x; }
public float y() { return y; }
public float z() { return z; }

public void x(double v) { x=v; }
public void y(double v) { y=v; }
public void z(double v) { z=v; }

public void set(double x, double y, double z)
{ this.x=x; this.y=y; this.z=z; }
public void set(Vec3 v)
{ x=v.x; y=v.y; z=v.z; }

public void addn(Vec3 v)
{ x+=v.x; y+=v.y; z+=v.z; }
public void subn(Vec3 v)
{ x-=v.x; y-=v.y; z-=v.z; }

public Vec3 add(Vec3 v)
{ return Vec3.at(x+v.x, y+v.y, z+v.z); }
public Vec3 sub(Vec3 v)
{ return Vec3.at(x-v.x, y-v.y, z-v.z); }

public double dot(Vec3 v)
{ return x*v.x + y*v.y + z*v.z; }

....

public Vec3 at(double x, double y, double z)
{
Vec3 tmp;
if(nCache>0)
{
tmp=cache[--nCache];
tmp.set(x, y, z);
return tmp;
}
return new Vec3(x, y, z);
}

public void free()
{
if(nCache<MAX)
cache[nCache++]=this;
}

}


an immutable case (implicit subclass?) could possibly disallow the
destructive methods (they are no-op or throw an exception), and probably
an 'Vec3.at(x, y, z)' method could be used to cache immutable vectors
(likely merged by epsilon and hashed).

something like:

public int hash()
{
long ix, iy, iz, i; //long is overkill?...
ix=(long)(x/EPSILON);
iy=(long)(y/EPSILON);
iz=(long)(z/EPSILON);

i=((ix*4294967291L+iy)*4294967291L+iz)*4294967291L;
return (int)(i>>>32);
}

public Vec3 at(double x, double y, double z)
{
Vec3 tmp;
int h;

h=hash()&1023;

tmp=cache[h];
if(tmp && tmp.isAt(x, y, z))
return tmp;
tmp=new ImmutableVec3(x, y, z);
cache[h]=tmp;
return tmp;
}


or such...

 

[BGB]

(below is untested, just assuming that javac will not barf...).

grr...

more than a few obvious problems in this one...

oh well, fixed a few of them after copy/paste/edit/compile...
well, alas, these sorts of errors are typical and expected...

idly thinking here:
public class Vec3

public class Vec3 extends Object

{

protected static final double EPSILON=0.000001;
(epsilon is arbitrary but should work...)

private static final int MAX=1024;
private static Vec3[] cache;
private static int nCache;

(still private: subclass has its own cache)

private double x, y, z;

protected double x, y, z;
(because subclass needs to see it...).

static {
cache=new Vec3[MAX];
nCache=0;
}

public Vec3()
{ this(0, 0, 0); }
public Vec3(double x, double y, double z)
{ this.x=x; this.y=y; this.z=z; }

public float x() { return x; }
public float y() { return y; }
public float z() { return z; }

public double x() { return x; }
public double y() { return y; }
public double z() { return z; }

(note: getX()/... would be a bit much added typing...).

public void x(double v) { x=v; }
public void y(double v) { y=v; }
public void z(double v) { z=v; }

public void set(double x, double y, double z)
{ this.x=x; this.y=y; this.z=z; }
public void set(Vec3 v)
{ x=v.x; y=v.y; z=v.z; }

public void addn(Vec3 v)
{ x+=v.x; y+=v.y; z+=v.z; }
public void subn(Vec3 v)
{ x-=v.x; y-=v.y; z-=v.z; }

public Vec3 add(Vec3 v)
{ return Vec3.at(x+v.x, y+v.y, z+v.z); }
public Vec3 sub(Vec3 v)
{ return Vec3.at(x-v.x, y-v.y, z-v.z); }

(I don't figure having both destructive and non-destructive ops hurts
too much here...).

public double dot(Vec3 v)
{ return x*v.x + y*v.y + z*v.z; }

...

public Vec3 at(double x, double y, double z)

public static Vec3 at(double x, double y, double z)

{
Vec3 tmp;
if(nCache>0)
{
tmp=cache[--nCache];
tmp.set(x, y, z);
return tmp;
}
return new Vec3(x, y, z);
}

public void free()
{
if(nCache<MAX)
cache[nCache++]=this;
}

'free()' is decidedly "dangerous", but anyways if cache gets full extras
fall to GC... this is mostly for cases where one knows the vector is
garbage. this operation is no-op for ImmutableVec3.

}


an immutable case (implicit subclass?) could possibly disallow the
destructive methods (they are no-op or throw an exception), and probably
an 'Vec3.at(x, y, z)' method could be used to cache immutable vectors
(likely merged by epsilon and hashed).

something like:

public int hash()

public static int hash(double x, double y, double z)

{
long ix, iy, iz, i; //long is overkill?...

(still dunno, long is slow and possibly overkill, but dividing by
EPSILON will give large numbers, and it is preferable to be able to hash
as many bits as reasonable, even despite a lot of these bits being
discarded anyways...).

ix=(long)(x/EPSILON);
iy=(long)(y/EPSILON);
iz=(long)(z/EPSILON);

i=((ix*4294967291L+iy)*4294967291L+iz)*4294967291L;
return (int)(i>>>32);
}

public int hash()
{ return hash(x, y, z); }

both above merged into Vec3.

for clarity:
public boolean isAt(double x, double y, double z)
{
if(Math.abs(this.x-x)>EPSILON)return false;
if(Math.abs(this.y-y)>EPSILON)return false;
if(Math.abs(this.z-z)>EPSILON)return false;
return true;
}


below is for ImmutableVec3:

public Vec3 at(double x, double y, double z)

public static Vec3 at(double x, double y, double z)

{
Vec3 tmp;
int h;

h=hash()&1023;

h=hash(x, y, z)&1023;
(errm... yeah...)

tmp=cache[h];

tmp=immCache[h];
(renamed for clarity...).

if(tmp && tmp.isAt(x, y, z))

if(tmp!=null && tmp.isAt(x, y, z))

return tmp;
tmp=new ImmutableVec3(x, y, z);
cache[h]=tmp; immCache[h]=tmp;

return tmp;
}

ImmutableVec3 currently makes destructive operations no-op, but
preferable would be to throw something (since if one tries to modify an
immutable vector something is obviously wrong...).

would likely have to make a new exception though as there don't appear
to be any obvious choices.


yes, conceptually awkward, but likely most workable...