Obvious, isn’t it?
30, Nov, 2019Did you know that sign of this determinant checks on which side of plane abc, a point d is:
| ax ay az 1 | | ax-dx ay-dy az-dz | | bx by bz 1 | == | bx-dx by-dy bz-dz | | cx cy cz 1 | | cx-dx cy-dy cz-dz | | dx dy dz 1 |
Or whether vector ab turns around in direction of cd (a second interpretation). A little cleaner than cross/dot product version. And less floating point errors.
- Posted by michal in
- Add a comment
The more articles…
30, Nov, 2019…I want to read, the more I am finding on Wayback Machine archive.org. Is the knowledge disappearing?
On the other hand, the more I read about the 3D Boolean operations, the more I think there is a knowledge to be still found there…
- Posted by michal in
- Add a comment
One year before spotted
19, Nov, 2019The bug was something like this:
int total_size;
if (something) {
int total_size = message_size + some_other_size;
} else {
total_size = message_size;
}
if (total_size > max_buf) {
...
}
This is another case (after http://www.butterwec … y:entry180913-210507) against free placement of variable locations…
- Posted by michal in
- Add a comment
More vege?
30, Oct, 2019The programming these days got really 0xBEEFFULL. And really unsigned long long int is quite long for u64 type (ups. I almost forgot, for “at least” u64 type). And yes you may omit int (which sounds like you may omit salad, but please eat meat).
- Posted by michal in
- Add a comment
GL bugs fun
17, Oct, 2019- Intel’s driver thought it would be funny to blend RGBA_INTEGER attachment with object ID information.
- AMD’s driver like to multisample the same RGBA_INTEGER attachment, linearly…
- Posted by michal in
- Add a comment
Wavefront OBJ
8, Oct, 2019When do you know that format is truly interchangeable?
When you start to edit/transform/convert it with grep, cat and sed!
- Posted by michal in
- Add a comment
Did you know that initializer?
1, Oct, 2019
int a[8] = { [2] = 2, [5] = 5 }; /* 0, 0, 2, 0, 0, 5, 0, 0 */
- Posted by michal in
- Add a comment
When OOP really fails?
29, Jun, 2019When reading of few hundreds 3D meshes from files, loading them to gfx card and displaying on screen is faster than updating GUI list of these objects.
- Posted by michal in
- Add a comment
The common sense
26, May, 2019ARGB8888 - 8 bits of alpha, 8 bits of red, 8 bits of green, 8 bits of blue
ARGB4444 - 4 bits of alpha, 4 bits of red, 4 bits of green, 4 bits of blue
RGB565 - 5 bits of red, 6 bits of green, 5 bits of blue
RGB332 - 3 bits of red, 3 bits of green, 2 bits of blue
YUV422 - ??? !!!
- Posted by michal in
- 23 comments
Fixing a square to a root
6, May, 2019I am implementing a small math library for my new game. It is fixed precision based (8.8 bit), as target processor (apollo-core 68080) has some SSE-like extensions for it. I encountered a problem - I need to normalize a vector. So, the length shall be computed
len = sqrt(a.x*a.x + ...)
and then each component needs to be divided by it a.x /= len. So my trivial approach was to get sqrt() function from the math.c. So, the fixed number is converted to the float, the square root is computed and the result is converted back to fixed number. This approach has some drawback through:
- The conversions are expensive.
- The processor has floating point unit but it does not have sqrt function - it is ~250 CPU cycles long procedure!
- Each component need to be divided, but the processor does not have vector division (only multiplication in vector mode, the division is only scalar).
So, let’s go with some research. Quite good summary of these methods is available on wikipedia http://en.wikipedia. … mputing_square_roots. The easiest one is Newton-Raphson method (Babylonian) - it is iterative method where each step is an average of current guess x and a geometric grow rate of the guess and input number s, that is 0.5 (x + s/x) or in code:
short fixsqrt(short a) {
int s = a;
int x = 1 << 8;
for (int i = 0; i < N; ++i) {
x = (x + (s << 8) / x) >> 1;
}
return x;
}
It is very stable and robust method. But there is a (slow) division. The other method is to compute the inverse square root directly - also with Newton’s method. The next step is calculated from x = 0.5*x*(3-s*x*x). And here is problem, the method is not so stable. Sources, which I have found seemed even to demonize that instability - that we need to make a very good guess, make some Babylonian iteration first, that it is totally unstable using a fixed precision. I couldn’t find a good material on the subject. But, we only need to look at the equation. Let’s see, the RHS of the equation shall be positive (as the result shall be). The 1.0 seemed to be quite good starting point previously. So, maybe we only need to assume that 3 > s > 0? Few computations, and looks good. But, I have range up to s = 8F.FF. Few seconds later and solution found - sqrt(s) == sqrt(4 * s’) == 2 sqrt(s’). We may divide s by 4 and then the resultant 1/sqrt(s) divide by 2. Of course using shifts, not divisions. Let’s see:
short fixisqrt(short a) {
int s = a;
int x = 1 << 8;
int n = 0;
while (s >= 0x300) {
s = s >> 2;
++n;
}
for (int i = 0; i < N; ++i) {
x = (0x300 - ((((s * x) >> 8) * x) >> 8)) * x >> 9;
}
return x >> n;
}
This seems to work, the process converges smoothly, errors are small and there is no single division. Tested on all possible (8.8 bit) numbers, the relative error was less than 0.01 for whole range. As the result is the inverse of square root now each component of the vector may multiplied by it (not divided) to be normalized. This implementation is now ready to be handcrafted with AMMX vector unit.
- Posted by michal in
- Add a comment
AoS vs SoA
26, Apr, 2019Math and performance can be complicated. Most interesting transformations acts on 3-vector (a position, normal, …), but SIMD instructions acts on powers-of-two - eg. on 4 or 8 components. One may use homogeneous coordinates with 4-vectors (wher w component is distinction between vector and pseudovector) and use 4×4 matrix for general transformations (translation/rotation/dilation/shears…). However, most useful are only translation, rotation and uniform scaling. And most efficient (by means of number of operations) implementation of those transformations is to use 3×3 matrix (rotation/dilation) paired with translation vector. This reduces computation from 16 multiplies and 12 additions to only 9 multiplies (matrix) and 9 additions (6 for matrix multiply 3 for translation).
But, the common way of storing 3 vectors as array is to store components in the interleaved form (x0, y0, z0, x1, y1, z1, x2, …). Or more straight way:
struct {
type x;
type y;
type z;
} vectors[];
It also named AoS, the Array of Structures. So the trivial approach would require to load unaligned that, mask of last vector, and omit 1/4 of vector operations to do the job. More, advanced approach would load 4 consecutive vectors and shuffle them, so each operation will act on x, y or z component of consecutive four vectors. But, maybe we can eliminate shuffling?
This can be done by arranging vector components in separate arrays (x0, x1, x2,…) (y0, y1,…) (z0,…) in C:
struct {
type *x;
type *y;
type *z;
} vectors;
It is so called SoA - the Struct of Arrays. Now, vectors can be loaded an transformed without any additional operations. However, this also may have some drawbacks. We need to use 3x more address registers (one for each array) - as these are spare on x86/amd64 - possibly loading and storing them (ah why PowerPC hasn’t won?!). This maybe solved also by storing these arrays one by one so from one address next may be reached - but this mostly will require additional instructions (or use of some more fat instructions). Also the cache management may be more challenging - we may need also to hint processor about what shall be in cache.
So, is there any golden bullet. Yes, it is. The AoSoA - array of structs of arrays. Simply write it down:
struct {
type x[4]; /* 4 or whatever fits in your SIMD register */
type y[4];
type z[4];
} vectors[];
In this arrangement we only need one address register for input (possibly another for output), there is only one stream which goes through the cache to the CPU and all SoA optimizations are in place.
So, long live the AoSoA!
p.s. Have you seen that, I did not specify the type? Isn’t it a float? But, that is another story…
- Posted by michal in
- 110 comments
Compilers can surprise
18, Apr, 2019Today I was testing one exotic compiler (vbcc) on exotic platform (Amiga). I had function
static inline f32v4 f32v4_add(f32v4 a, f32v4 b) {
return (f32v4) {a.x+b.x, a.y+b.y, a.z+b.z, a.w+b.w};
}
and a macro
#define F32V4_ADD(a, b) (f32v4) { (a).x+(b).x, (a).y+(b).y, (a).z+(b).z, (a).w+(b).w }
I was iterating (two fors) in tight loop adding two consecutive values, something like:
arr[i] = f32v4_add(a[i-1], a[i-2])
The macro version on average was 3.7 times faster! But, why? Looking into assembler I have found that function was properly inlined. However, there was some magic around loop handling, address registers and addressing modes of fmove operations. Optimizer got lost by this inline function.
p.s. The gcc was slower than both.
- Posted by michal in
- Add a comment
Structure initialization
16, Apr, 2019Let say we have structure in C:
struct A {
int x;
int y;
};
You may initialize it three ways:
struct A a; a.x = ... a.y = ...
or
struct A a = { ..., ... };
or
struct A a = { .x = ..., .y = ... };
You may say what the difference?! But, there may be huge. Let say you implemented it, and then after years, after dozens of uses, someone modifies the A:
struct A {
int x;
int z;
int y;
};
The last pattern saves the day…
p.s. What interesting C++ does not yet have it! It will in 2020. Ugh… But, even more - in current C++20 proposition, even when using designated initializers, these initializers must appear in order. With C++ - no save of the day, only the a doomsday. What a wonderful language!
- Posted by michal in
- Add a comment
The root of all anvils (and evil)
9, Apr, 2019So many times, I saw a such object:
{
...
bool a;
bool b;
bool c;
bool d;
...
}
So many times it ended the same. The objects were constructed in millions. Memory consumption was high, unaligned accesses with cache misses run through the app because that class was 65 bytes…
But, you may optimize this latter? Really? Not, so.
The object structure reflected, how it was serialized. The fastest way was push it as a binary blob to our internal format. We cannot convert all the legacy data. Now, even if we optimize the run time, we have hard time on load and save - we need a parser. Congratulations one thing optimized, another has been made slower.
All that was needed from he beginning:
{
...
int a:1;
int b:1;
int c:1;
int d:1;
...
}
- Posted by michal in
- Add a comment
Local shoot in the foot
8, Apr, 2019Everyone knows that locals are good? A short story of one event.
We do not want to have globals. Pass it through an argument. But there is so many things to be passed. An item, it’s modifiers, an environment, an … From foo0 to foo1, from foo1 to foo2, from foo2 to…, … to bar. Uff, yes we passed whole set of arguments to foo:
void bar(int e, int f, int g, int h, int x, int y, int a, int b, int c, int e, int d);
so lets run:
void bar(e, f, g, x, h, y, a, b, c, e, d);
Works well for test data, compiles without warning. Good job!?
- Posted by michal in
- Add a comment
Global shoot in the foot
8, Apr, 2019What can go wrong with globals? A short story of one event..
First there was an single task app, a server. It run on single data. The service relay on a characteristic parameter - the world size. It is passed by client to the server on the initialization of connection.
Next design iteration. The client-server approach is too slow. Change the interface and make it a library. The library will be intialized with the parameter. We are good. Still we use on single data at a time.
Its refactor time, make an easy api. - Initialization will be automatic on incoming data. World size set by heuristic. Oh no, we don’t have time for internals cleanup, global stays.
Some time after. Hey, we have more items which can be processed. Make init/do the thing with the lib in the loop. Looks good, works well. We are still single threaded.
Time passes. We have so many items to be processed. It takes long. Let’s speed up it a little. Run the library procedure for each item in separate thread. Few lines of code and looks good. Tests passed. Push to master.
Few months later - hey I run the tasks for multiple data at once. The results seems to be corrupted… And of course nobody remembered the global. It looked like array out of bound access - but valgrind found nothing. Sometimes crashed - maybe double free? A day later…
- Posted by michal in
- Add a comment