Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Avoiding (beginners') allocation mistakes in this sequence of vector functions in C

Context: I've decided to re-write my 3D graphics script, which evolved in Python, to C for speed. This involves me learning C. The part of the program in question caches normals information about a 3D mesh.

There are 3 vector operations called in sequence here (pretty standard: vector subtraction to get edge vector, cross product and average), which I would like to be as fast as possible, so I'm trying to avoid storing anything needlessly on the heap...and copying my structs too many times. However, I also am aware that if I return pointers I'll point to mem space which isn't valid any more.

This how I would try to write all three functions (generally speaking: struct copy in, struct copy out, rather than pointers).

typedef struct vector vector;
struct vector{
    double x,y,z;
};

vector vect(vector a, vector b){
    vector res;
    res.x = b.x - a.x; 
    res.y = b.y - a.y;
    res.z = b.z - a.z;
    return res;
}

vector cross(vector a, vector b){
    vector res;
    res.x = a.y*b.z - a.z*b.y;
    res.y = a.z*b.x - a.x*b.z;
    res.z = a.x*b.y - a.y*b.x;
    return res;
}

vector avg (vector a, vector b){
    vector res;
    res.x = (a.x + b.x)/2;
    res.y = (a.y + b.y)/2;
    res.z = (a.z + b.z)/2;
    return res;
}

And this is how it's called:

m->Tpolynormals[i] = avg(cross( vect(*p->verts[0], *p->verts[1]),
                                vect(*p->verts[1], *p->verts[2]) ),
                         cross( vect(*p->verts[2], *p->verts[3]),
                                vect(*p->verts[3], *p->verts[0]) )
                        );

Is this fairly efficient or is there a faster way to do it? I know I can experiment and "make it work", but at this point I'd like to make sure the foundations are solid. - Thanks

Edit: added my struct definition above, as someone obviously pointed out, duh. The coordinates are doubles (it's what my 3D package outputs) and system is 64-bit.

like image 388
DailyFrankPeter Avatar asked Jun 30 '16 16:06

DailyFrankPeter


2 Answers

"Avoiding (beginners') allocation mistakes" vs. "I would like to be as fast as possible,"

Which is more important?

If code needs to be as fast as possible, try a number of approaches and profile them to see what works best for you. You will make mistakes.

The sizeof vector is in the border region of providing a general answer to what is best, passing vector by value or its address. Best to try both

1) Pass vector by value. OP seems to understand that well.

vector vect(vector a, vector b){
    vector res;
    res.x = b.x - a.x; 
    res.y = b.y - a.y;
    res.z = b.z - a.z;
    return res;
}

2) Pass vector by its address. Create intermediate result locations. This seems to be the part OP is uncertain.

void V_vect(vector *res, const vector *a, const vector *b){
    res->x = b->x - a->x; 
    res->y = b->y - a->y;
    res->z = b->z - a->z;
}

// usage example
vector res1;
vector res2;
V_vect(&res1, p->verts[0], p->verts[1]);
V_vect(&res2, p->verts[1], p->verts[2]);
vector res3;
V_cross(&res3, &res1, &res2);

V_vect(&res1, p->verts[2], p->verts[3]);
V_vect(&res2, p->verts[3], p->verts[0]);
vector res4;
V_cross(&res4, &res1, &res2);

V_avg(&m->Tpolynormals[i], &res3, &res4);

In particular, recommend to avoid re-using memory in the same call as in below. That could be a rookie mistake, both in function and code performance.

V_cross(&res2, &res1, &res2);

A way to speed things when passing the address is to use restrict. This allows a compiler to know the calling code is using pointers to areas that do not overlap. This allows for certain compiler optimizations.

void V_vect(vector * restrict res, const vector * restrict a, const vector * restrict b){
    res->x = b->x - a->x; 
    res->y = b->y - a->y;
    res->z = b->z - a->z;
}

With restrict the 1st below call is undefined behavior as it overlaps the vectors.

// V_cross(&res2, &res1, &res2);  // bad
V_cross(&res4, &res1, &res2);  // good

Try various approaches (including @Jonathan Leffler compound literal idea and @Jonathan Leffler inline idea) and uses what works well for you.

like image 55
chux - Reinstate Monica Avatar answered Nov 15 '22 21:11

chux - Reinstate Monica


If you want to minimize the amount of data being copied around, you can pass in pointers to the input and output parameters. That would mean however that you can't chain function calls together as you do above, and it means you'd need to have temp variables to hold the result of each call.

For example:

void vect(vector *a, vector *b, vector *res){
    res->x = b->x - a->x; 
    res->y = b->y - a->y;
    res->z = b->z - a->z;
}

// similarly for the other two

Then to call them:

vector vect1, vect2, vect3, vect4, cross1, cross2;
vect(p->verts[0], p->verts[1], &vect1);
vect(p->verts[1], p->verts[2], &vect2);
vect(p->verts[2], p->verts[3], &vect3);
vect(p->verts[3], p->verts[0], &vect4);
cross(&vect1, &vect2, &cross1);
cross(&vect3, &vect4, &cross2);
avg(&cross1, &cross2, &m->Tpolynormals[i]);
like image 25
dbush Avatar answered Nov 15 '22 21:11

dbush