SRL Archive - Suggestions

Hey there,

Not so long ago, Wizzup created a thread about structuring the FindColor unit to make it expandable, while maintaining speed. I came with the idea to abstract the comparing function by using a JIT compiler. Today, I put that idea to the test to see if it would be an option. The results aren't astonishing, but are decent to say the least. I didn't use a real JIT compiler, but rather a (compiled) template. This means it will hopefully be easier to port to other platforms.

This is what the template looks like for cts 0:

function func_template(R, G, B: SizeInt): Boolean;
begin
  Result :=
    (Abs(R - MagicNumber2) <= MagicNumber) and
    (Abs(G - MagicNumber3) <= MagicNumber) and
    (Abs(B - MagicNumber4) <= MagicNumber);
end;
procedure __next; begin end;

Instead of using 2 colors for input to compare, I use 1 hardcoded set of RGB values. The tolerance is also hardcoded (notice the MagicNumbers). To create a runtime compare function for a specified color and tolerance, I just "copy" the function and change the MagicNumbers to the real RGB and tolerance values. This will result in a function in memory which will always compare to a certain color using a certain tolerance.

As you only have to pass a single color, it's faster than other compare functions, while maintaining an abstract interface. With CTS 0 it is a bit slower than inlining the algorithm, but with CTS 1 it is actually faster. I haven't tried it with other algorithms, but I suspect it'll be a faster approach for those too.

Currently, the code is Windows-only, but porting it to Linux shouldn't be hard (hopefully it'll only be a matter of changing the VirtualAlloc to mmap). A downside is that I did not get function calling to work in the copied function, so color converting algorithms will have to be inlined. All in all, it was a nice experiment.

I added the source (including a binary) to this post. I hope it may help some people in the future :)

~Nielsie95

Sounds Like you had a Fun and productive experiment. :)

~BraK

Heh. Very nice!

Worthy of another branch in Simba git? :D

E: Also, the thread niels talked about: http://villavu.com/forum/showthread.php?p=812479#post812479

Besides the implementation being kind of hackish, this is a brilliant idea. Might be better to do some of this at compile time, i.e. build these findcolor functions individually at compile time and convert them into machine code (byte array) and record the positions of the local variables? Mostly I'm suspect of the way you found the size of the function (not that it doesn't work in this case) but I don't believe procedures are guaranteed to be placed in order

It's very hacky indeed. You'll also get problems when the numbers aren't byte aligned in the code, but I guess that's not a problem for x86. Using precompiled code is an option, but would require more work as you also have to take platform/calling convention into account (to get the best results, you'll need a precompiled template for every platform).

Wizzup, feel free to implement it in another branch :p

Question: if you put a label in the code, is the fpc compiler capable of giving you the memory address of the label? This functionality (if what i said isn't clear) exists in gcc http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html and would make this process very stable and expandable. (might even be worth writing a simple C file to generate the functions and linking it in).

Unfortunately, I don't think that's possible with FPC :( Before resorting to C, I think it's better to just test it and see if it's a viable option (maybe this'll already work on most platforms?).

[speculation] Color searching is a something that sounds like could be perfectly vectorized. After all, you take some data, perform some calculations then store (afterwards compare if it's right). Can't we use some cool SIMD asm optimisation in Simba to further increase the speed? Right now it seems pretty inefficient to me to do like 4 calculations per loop iteration, if we could just do 4 calculations on the whole set.. [/speculation]

From: Markus
[speculation] Color searching is a something that sounds like could be perfectly vectorized. After all, you take some data, perform some calculations then store (afterwards compare if it's right). Can't we use some cool SIMD asm optimisation in Simba to further increase the speed? Right now it seems pretty inefficient to me to do like 4 calculations per loop iteration, if we could just do 4 calculations on the whole set.. [/speculation]

Yes, but that would require very recent CPU's I suppose. SIMD certainly is another option, but I suggest we do this in stages. ;)

P4 (2001) or Athlon64 (2003) according to Wikipedia for SSE2. MMX will be in pretty much every CPU that can run RS. MMX can do 2 integers simultaneously vs 4 for SSE. The idea is good and I'm sure it'll make it faster, but I'm not sure how hard it is to implement. I know FPC (kind of) supports it, but the code will not compile if you do not compile it with SSE/MMX flags on.

And it won't work on other architectures than x86. :)

E: It's certainly worth trying / testing. It's just that currently I was looking at some ways to easily implement a lot of CTS'es. Previously we had them all in an if-statement and it was generally nasty and not maintainable. In the cts-rework branch we tested a different method, which involved lots of code duplication but was a _bit_ maintainable. Funny enough the best approach seems to me now is comparison functions per cts (like in the jit), because these are quite maintainable and the overhead of passing args would be solved with a struct. Although that would cost additional copies to actually get it into the struct, but that may be negligible.

you know i thought i understood what your talking about in theory but it really sounds like it makes very little difference considering the previous works well to say the least…

of course clearly i havnt the foggiest because apparently everyone else thinks its genius…
for all intensive purposes would u mind showing some numbers and an exagerated example to really show the difference? hardly any use except to satisfy my curiousity so dont bother if your busy..

The previous solution does work pretty well indeed, but the code is pretty messy and hard to expand (currently you need to implement a new CTS separately in every function). A solution would be to abstract the color comparison functions, but that means you'll have to pass a lot of information. This way, you still keep it abstract, but you only have to pass one color to compare. The first color is hardcoded in the function, which should be more efficient than using values passed to the function (in theory).

Granted the FPC compiler is complete shit compared to gcc, but I've been testing to see what the REAL difference between these various methods are. C++0x code follows, be warned.

#include <cstdlib>
#include <cstring>
#include <iostream>
#include <time.h>
#include <functional>
#include <sys/mman.h>

#define magic1 0x69691337
#define magic2 0xABCD9001
#define magic3 0xCAFEBEBE
#define magic4 0x42424242

#define sizeof_function(x) ( (unsigned long) (&(__endof_##x)) - (unsigned long) (&x)) 
#define endof_function(x) volatile int __endof_##x() {}

typedef std::function<bool(int,int,int)> lambda_compare;
typedef int (*compare)(int r, int g, int b);

volatile int __cts1_template(int r, int g, int b) {
    int R = magic1, G = magic2, B = magic3, tol = magic4;
    R -= r;
    G -= g;
    B -= b;
    return (R*R + G*G + B*B) <= tol;
}
endof_function(__cts1_template);
compare gen_cts1(int R, int G, int B, int tol) {
    int len = sizeof_function(__cts1_template);
    compare func = (compare)mmap(NULL, len, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);
    memcpy((void*)func,(void*)&__cts1_template,len);
    
    char* bytes = (char*)func;
    int max = (len/4)*4, i;
    for (i = 0; i < max; i++, bytes++) {
        switch(*(int*)bytes) {
            case magic1: *(int*)bytes = R; break;
            case magic2: *(int*)bytes = G; break;
            case magic3: *(int*)bytes = B; break;
            case magic4: *(int*)bytes = tol*tol; break;
        }
    }
    
    return func;
}

void free_cts1(compare func) {
    munmap((void*)func,sizeof_function(__cts1_template));
}

int cts1(int R, int G, int B, int r, int g, int b, int tol) __attribute__((noinline));
int cts1(int R, int G, int B, int r, int g, int b, int tol) {
    R -= r;
    G -= g;
    B -= b;
    return (R*R + G*G + B*B) <= tol*tol;
}

inline int inline_cts1(int R, int G, int B, int r, int g, int b, int tol) {
    R -= r;
    G -= g;
    B -= b;
    return (R*R + G*G + B*B) <= tol*tol;
}

lambda_compare lambda_cts1(int R, int G, int B, int tol) {
    tol *= tol;
    return [R,G,B,tol](int r, int g, int b) { r -= R; g -= G; b -= B; return (r*r + g*g + b*b) <= tol; };
} 

int main() {
    clock_t start,end;
    int times = 100000000,r,g,b,R=128,G=128,B=128,tol=20,count;
    lambda_compare lambda;
    compare func;
    
    start = clock();
    count = 0;
    for (int i = 0; i < times; i++) {
        r = rand()%256;
        g = rand()%256;
        b = rand()%256;
        if (r|g|b) count++;
    }
    end = clock();
    double offset = (double)(end - start)/CLOCKS_PER_SEC*1000.0*1000.0*1000.0/times;
    std::cout << "Time offset " << offset << "ns\n";
    
    start = clock();
    lambda = lambda_cts1(R,G,B,tol);
    count = 0;
    for (int i = 0; i < times; i++) {
        r = rand()%256;
        g = rand()%256;
        b = rand()%256;
        if (lambda(r,g,b)) count++;
    }
    end = clock();
    std::cout << "lambda_cts1 (" << count << ") took " << (double)(end - start)/CLOCKS_PER_SEC*1000.0*1000.0*1000.0/times - offset << " ns\n";
    
    start = clock();
    func = gen_cts1(R,G,B,tol);
    count = 0;
    for (int i = 0; i < times; i++) {
        r = rand()%256;
        g = rand()%256;
        b = rand()%256;
        if (func(r,g,b)) count++;
    }
    free_cts1(func);
    end = clock();
    std::cout << "gen_cts1 (" << count << ") took " << (double)(end - start)/CLOCKS_PER_SEC*1000.0*1000.0*1000.0/times - offset << " ns\n";
    
    start = clock();
    count = 0;
    for (int i = 0; i < times; i++) {
        r = rand()%256;
        g = rand()%256;
        b = rand()%256;
        if (inline_cts1(R,G,B,r,g,b,tol)) count++;
    }
    end = clock();
    std::cout << "inline_cts1 (" << count << ") took " << (double)(end - start)/CLOCKS_PER_SEC*1000.0*1000.0*1000.0/times - offset << " ns\n";
    
    start = clock();
    count = 0;
    for (int i = 0; i < times; i++) {
        r = rand()%256;
        g = rand()%256;
        b = rand()%256;
        if (cts1(R,G,B,r,g,b,tol)) count++;
    }
    end = clock();
    std::cout << "cts1 (" << count << ") took " << (double)(end - start)/CLOCKS_PER_SEC*1000.0*1000.0*1000.0/times - offset << " ns\n";
    
    return 0;
}

We see that I tested four methods. Regular function call, inlined function call, nielsie95 style generated function, and lambda functions just for the hell of it. Note that my comparison method is identical for each style, each uses the same base color and tolerance (not that it matters), and is tested against 100,000,000 random colors. I also calculated (roughly) the time the simulation takes without the comparison and subtracted out that value for completeness. I've run this many times and the values I will quote are accurate +/- 2ns.

benland100@bland:~/Desktop/segfault$ g++-4.5 -std=c++0x -O3 lambda.cpp -o lambda
benland100@bland:~/Desktop/segfault$ ./lambda 
Time offset 81.4ns
lambda_cts1 (198901) took 17.2 ns
gen_cts1 (199635) took 11.9 ns
inline_cts1 (198078) took 8 ns
cts1 (198849) took 11.9 ns

What do we learn here? These functions run faster than you can probably imagine. Lambda functions, as expected for high level programming, are rather slow. BUT the generated and regular function calls are rather close (to be fair, since I say +/- 2ns, they could be at most 4ns apart, either direction). This is an unbelievable short amount of time, and is only 50% of the time (i.e. a 50% increase). IMHO, this is NOT in ANY circumstance worth the hacked solution of generating a function. Note that the inlined function is consistently faster, as one would expect. Note again that if the code that has been inlined can fit into the cache, this time is cut by nearly an order of magnitude. CLEARLY inline is the way to go, and when that won't do, regular function calls are sufficient (pointers included).

I confirmed by looking at the assembly code that the functions here were inlined when appropriate and not inlined when I did not want them to be, so my numbers are accurate. In the code Nielsie95 used (through no fault of his own) the two comparison methods generated radically different (and rather shitty) machine code due to FPC being a fail. As fate would have it, the non-generated version made horrible use of registers and memory access, while the generated function worked fairly well (i suspect the use of sqr() caused problems in optimization). Care should be taken to ensure the code in pascal produces good machine code, as this has more of an effect on speed than ANY sort of algorithmic changes.

tl;dr The differences between the four tested methods amount to less than a second after 100,000,000 (one hundred million) comparisons. This difference is negligible, as the entire RS screen is only around 500,000 pixels. Spend less time trying to hack off a few NANOSECONDS from the comparison routines though dirty and confusing methods and make the code pretty / better for actual optimization.

From: BenLand100
Granted the FPC compiler is complete shit compared to gcc, but I've been testing to see what the REAL difference between these various methods are. C++0x code follows, be warned.

#include <cstdlib>
#include <cstring>
#include <iostream>
#include <time.h>
#include <functional>
#include <sys/mman.h>

#define magic1 0x69691337
#define magic2 0xABCD9001
#define magic3 0xCAFEBEBE
#define magic4 0x42424242

#define sizeof_function(x) ( (unsigned long) (&(__endof_##x)) - (unsigned long) (&x)) 
#define endof_function(x) volatile int __endof_##x() {}

typedef std::function<bool(int,int,int)> lambda_compare;
typedef int (*compare)(int r, int g, int b);

volatile int __cts1_template(int r, int g, int b) {
    int R = magic1, G = magic2, B = magic3, tol = magic4;
    R -= r;
    G -= g;
    B -= b;
    return (R*R + G*G + B*B) <= tol;
}
endof_function(__cts1_template);
compare gen_cts1(int R, int G, int B, int tol) {
    int len = sizeof_function(__cts1_template);
    compare func = (compare)mmap(NULL, len, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);
    memcpy((void*)func,(void*)&__cts1_template,len);
    
    char* bytes = (char*)func;
    int max = (len/4)*4, i;
    for (i = 0; i < max; i++, bytes++) {
        switch(*(int*)bytes) {
            case magic1: *(int*)bytes = R; break;
            case magic2: *(int*)bytes = G; break;
            case magic3: *(int*)bytes = B; break;
            case magic4: *(int*)bytes = tol*tol; break;
        }
    }
    
    return func;
}

void free_cts1(compare func) {
    munmap((void*)func,sizeof_function(__cts1_template));
}

int cts1(int R, int G, int B, int r, int g, int b, int tol) __attribute__((noinline));
int cts1(int R, int G, int B, int r, int g, int b, int tol) {
    R -= r;
    G -= g;
    B -= b;
    return (R*R + G*G + B*B) <= tol*tol;
}

inline int inline_cts1(int R, int G, int B, int r, int g, int b, int tol) {
    R -= r;
    G -= g;
    B -= b;
    return (R*R + G*G + B*B) <= tol*tol;
}

lambda_compare lambda_cts1(int R, int G, int B, int tol) {
    tol *= tol;
    return [R,G,B,tol](int r, int g, int b) { r -= R; g -= G; b -= B; return (r*r + g*g + b*b) <= tol; };
} 

int main() {
    clock_t start,end;
    int times = 100000000,r,g,b,R=128,G=128,B=128,tol=20,count;
    lambda_compare lambda;
    compare func;
    
    start = clock();
    count = 0;
    for (int i = 0; i < times; i++) {
        r = rand()%256;
        g = rand()%256;
        b = rand()%256;
        if (r|g|b) count++;
    }
    end = clock();
    double offset = (double)(end - start)/CLOCKS_PER_SEC*1000.0*1000.0*1000.0/times;
    std::cout << "Time offset " << offset << "ns\n";
    
    start = clock();
    lambda = lambda_cts1(R,G,B,tol);
    count = 0;
    for (int i = 0; i < times; i++) {
        r = rand()%256;
        g = rand()%256;
        b = rand()%256;
        if (lambda(r,g,b)) count++;
    }
    end = clock();
    std::cout << "lambda_cts1 (" << count << ") took " << (double)(end - start)/CLOCKS_PER_SEC*1000.0*1000.0*1000.0/times - offset << " ns\n";
    
    start = clock();
    func = gen_cts1(R,G,B,tol);
    count = 0;
    for (int i = 0; i < times; i++) {
        r = rand()%256;
        g = rand()%256;
        b = rand()%256;
        if (func(r,g,b)) count++;
    }
    free_cts1(func);
    end = clock();
    std::cout << "gen_cts1 (" << count << ") took " << (double)(end - start)/CLOCKS_PER_SEC*1000.0*1000.0*1000.0/times - offset << " ns\n";
    
    start = clock();
    count = 0;
    for (int i = 0; i < times; i++) {
        r = rand()%256;
        g = rand()%256;
        b = rand()%256;
        if (inline_cts1(R,G,B,r,g,b,tol)) count++;
    }
    end = clock();
    std::cout << "inline_cts1 (" << count << ") took " << (double)(end - start)/CLOCKS_PER_SEC*1000.0*1000.0*1000.0/times - offset << " ns\n";
    
    start = clock();
    count = 0;
    for (int i = 0; i < times; i++) {
        r = rand()%256;
        g = rand()%256;
        b = rand()%256;
        if (cts1(R,G,B,r,g,b,tol)) count++;
    }
    end = clock();
    std::cout << "cts1 (" << count << ") took " << (double)(end - start)/CLOCKS_PER_SEC*1000.0*1000.0*1000.0/times - offset << " ns\n";
    
    return 0;
}

We see that I tested four methods. Regular function call, inlined function call, nielsie95 style generated function, and lambda functions just for the hell of it. Note that my comparison method is identical for each style, each uses the same base color and tolerance (not that it matters), and is tested against 100,000,000 random colors. I also calculated (roughly) the time the simulation takes without the comparison and subtracted out that value for completeness. I've run this many times and the values I will quote are accurate +/- 2ns.

benland100@bland:~/Desktop/segfault$ g++-4.5 -std=c++0x -O3 lambda.cpp -o lambda
benland100@bland:~/Desktop/segfault$ ./lambda 
Time offset 81.4ns
lambda_cts1 (198901) took 17.2 ns
gen_cts1 (199635) took 11.9 ns
inline_cts1 (198078) took 8 ns
cts1 (198849) took 11.9 ns

What do we learn here? These functions run faster than you can probably imagine. Lambda functions, as expected for high level programming, are rather slow. BUT the generated and regular function calls are rather close (to be fair, since I say +/- 2ns, they could be at most 4ns apart, either direction). This is an unbelievable short amount of time, and is only 50% of the time (i.e. a 50% increase). IMHO, this is NOT in ANY circumstance worth the hacked solution of generating a function. Note that the inlined function is consistently faster, as one would expect. Note again that if the code that has been inlined can fit into the cache, this time is cut by nearly an order of magnitude. CLEARLY inline is the way to go, and when that won't do, regular function calls are sufficient (pointers included).

I confirmed by looking at the assembly code that the functions here were inlined when appropriate and not inlined when I did not want them to be, so my numbers are accurate. In the code Nielsie95 used (through no fault of his own) the two comparison methods generated radically different (and rather shitty) machine code due to FPC being a fail. As fate would have it, the non-generated version made horrible use of registers and memory access, while the generated function worked fairly well (i suspect the use of sqr() caused problems in optimization). Care should be taken to ensure the code in pascal produces good machine code, as this has more of an effect on speed than ANY sort of algorithmic changes.

Thanks for the benchmark, I don't have any critique on it now, I think. Aside from the fact that the code footprint is still small, which isn't the case for Simba.
I wonder if it's any different in FPC, though.

From: BenLand100
tl;dr The differences between the four tested methods amount to less than a second after 100,000,000 (one hundred million) comparisons. This difference is negligible, as the entire RS screen is only around 500,000 pixels. Spend less time trying to hack off a few NANOSECONDS from the comparison routines though dirty and confusing methods and make the code pretty / better for actual optimization.

Point taken, although you must admit optimising is always fun. I know you've already seen the thread, but now you're gained some more theoretical insight as well as some more information about the context, want to take a look a this thread (http://villavu.com/forum/showthread.php?t=64908) and help decide on the ``best'' way to make the current code pretty?

Mainly, what do you think about the subprocedures? (see first post) AFAIK this is the only way to do inline without having a ``case'' for each and every cts. (As you can see in my last post that makes a big difference)
If you use a pointer to the current CTS comparison method, you can't inline it.

E: So, my conclusion for now is to keep it as subprocedures but make the actual comparison method inline. (That is, pass the two colours as RGB (with or without? struct) and in the loop call the cts_X_comparison() method. Any comments on that?

Thanks for looking into this, BenLand :) I guess we should just go for a cleaner solution then.