fast operators design considerations
I think about the right way of defining fast "algebras" ie. small objects with some operations between them.
For example, take a class Vector:
publicclass Vector{
publicfloat x,y;
...
}
and now we want to add some of them.
now there are several possibilitys:
1. "operator like"
Vector add(Vector second){
Vector result=new Vector();
result.x=x+second.x;
result.y=y+second.y;
return result;
}
2. "in-place"
Vector add(Vector second){
x+=second.x;
y+=second.y;
returnthis;
}
3. "to-place"
Vector add(Vector second, Vector result){
if (result==null) result=new Vector();
result.x=x+second.x;
result.y=y+second.y;
return result;
}
all this methods could be made static with one additional argument, and 2. or 3. could be typed void.
i know that 2. seems more like "+=", but i just want ONE add for clean structure. so here the control of cloning is to the caller himself.
so what to take? its clear that 1. should be at least performant since a object need to be generated every use. but for convinience, it removes any side-effects.
2. just works by its side effect if no return value is used, but thats not much in the fashion of well-known "+"...
3. is very flexible also problematic. it can fill or create the result, and can so deliver performance or convinince, at the price of an extra !=null condition. also this syntax is not clean for "not-in-place-ops"...
for example, an matrix multiplication could not store its result to one of its arguments. so in this style, a multiplyMatrix(Matrix multiplicant, Matrix result) had to check also this!=result AND multiplicant!=result.
Also the use of return value is allways needed here, where for Vector.add the result could be overwritten to "result" so the return result is not needed.
Iv'e looked at some Vector-classes found them very chaotic as they mostly mix some of the above models to gain performance and versatility. ..
But there must be some strong arguments to help decide for one useful structure, even when sometimes it takes some more code.
It seems senseful, that result could allways be stored at some rexisting place (this, "result") as object creation is the most costly operation, right?
thanks for ideas/viewpoints to this & many greetings
Paul
[3070 byte] By [
paulgeisa] at [2007-10-2 1:59:11]
Easy trick here. Make the Vector immutable.
Immutability is a wonderful attribute, I'm sure you'll love it. That reduces it to basically one form of add, that being
public Vector add(Vector v) {
return new Vector(x + v.x, y + v.y);
}
Trust me, you'll prefer it in the end.
~Cheers
yeah i really like to do so... it is in fact the most convenient way. but as i stated: that would be the least performant solution one can get i think. (please correct me if i'm wrong)
this is beacuse then every modification leads to a new object... and from "classical programming" old times.. i know that every instancing is quite as slow as dozens of manipulations...
Immutable objects have a memory penalty.
Though java's new is considerable faster than C++'s new/delete.
And the optimizers do some good thing when byte code converting.
Try using final and such, and measure!
The advantage of having no side effects must be exploited, however.
So functions with lazy evaluation, symbolic manipulation etcetera,
should be given some consideration.
An expression like u.add(v.add(w.add(z))) could be optimized for instance.
This is only possible if the algorithm contains costly "loops", so that
a symbolic precompilation is feasible.
Think of a matrix package.
Make classes, that give you a dataflow of the operations (no evaluation).
Have nice optimization on constants.
Variable x = new Variable();
Matrix a = new Matrix22(Cons.let(1), Cons.let(2), Const.let(3), x);
Matrix b = a.times(a);
Evaluator ev = new Evaluator();
Code code = ev.compile(b);
System.out.println("Code:");
code.list(System.out);
code.setParam("x", 4);
System.out.println("Result:");
code.eval();
Code:
int u = read("x");
int v = 1 + u;
write(7);
write(2*v);
write(3*v);
write(6 + u*u);
Result:
7 10
15 22
this kind of expression compiler is a realy nice idea...
i remember that physic simulation engines often have heavy varyiing linear systems so that some of them actually use even in realtime operation some kind of internal compilation of linear systems to reduce the amount of unneccesary variables or overdefining equations..
but as a start i like to design a consistent system with acceptable performance for massive data operations.. in c, you maybe would put your vectors directly to an array, which is impossible by java objects are allways handled by reference. so i think if an array of refferences in java is created, ok, its not really an array in memory, but if all vectors are new'ed in sequence, its possible they are located sequentially in memory so caches and other hardware optimisations get happy...
but this structure is only preserved, if this vectors are overwritten, as any calculation which modifies some of them otherwise would brake the natural memory alignment to some fragmented pattern given by program execution order and vm good will...
so immutability will be at loss here again...
that hardware considerations are of interest in java (although java hides them with full pleasure) turns out for me some time ago
for example: copying an 2dim array by a for loop was about 20 times as fast as transposing it into the new array; which was the same amount of java bytecode ops, only the memory access order differs...
so i don't deny that java can get native performance, but then the same design considerations must be taken as they would in c or others.
on the other hand, the immutable design is soo much niftier to code :-(
thanks
Paul
Your toPlace method has the performance beifits of both other approaches.
It is a generalization of the other two. It can work by creating a new Vector or you can "reuse" another vector you have floating around.
Vector a = new Vector(1,0);
Vector b = new Vector(2,0);
a = Vector.add(a, b);
a = a.add(a,b);
a = a.add(a,null);
Some convience methods to neaten it up and and you are all set.
The performance differences may not be as large as you think though. In jdk1.6 it will be even less in most situations. Escape optimization will enable many of the vector allocations to be entirely on the stack rather then on the heap.
Immutability, as an earlier poster said, is a useful trait in many situations. Are you willing to trade it for a performance gain that you haven't yet quantified.
Generational GCs (at least all that I know off) allocate objects sequentially in memory so they tend to be quite cache friendly. Many don't even require the "main-memory" to be synchronized when a new "thread-local-cache" allocation is performed (not often anyway).
matfud
I work in algorithmic geometry, and we do lots of coordinate system translation. The vector's coord system afilliation is represented in the name of the object.
Vector add for this purpose requires 3 arguments, two inputs (symmetrical) and one output. The main thing is the method signature supports 3 independent named vectors. C = A + B.
Vector a = new Vector(1,1);
Vector b = new Vector(2,2);
Vector c = Vector.add(a, b);
where:
public static Vector add(Vector a, Vector b) {
return new Vector (a.x+b.x, a.y+b.y);
{
This 3-argument form is the most natural, general-purpose, and concise way to define vector add.
When you need to keep the 3 named quantities distinct, this is the most streamlined and intuitive way to go. It's not going to run as fast as another form where the result vector isn't being created.
The advantage is it makes code easy to read and understand for novice programmers.
(I teach algorithmic geometry to Java beginners, and go to lengths to keep source code simple and intuitive).
