[PATCH 3/3] winex11: Use TINN algorithm to speed up colour lookups.

[Vitaly Budovski]

Vitaliy Margolen wrote:
> Vitaly Budovski wrote:
>   
>> Make use of the Triangle Inequality Nearest Neighbour algorithm to find the
>> nearest colour more efficiently than a simple linear search. The improvements
>> are most noticeable with a palette of 256 colours. Testing shows approximately
>> 3-4x performance increase for 256 colours.
>> ---
>>     
>
> Overall idea looks good, however the big problem with it is use of float
> point numbers. Fortunately you can get rid of them and use integers
> instead. Because you never use the distance in the calculations, but
> only to compare against other distances, you can skip "sqrt" and just
> compare squares, as the original code does. That will give you even more
>  speed improvements.
>   

Thanks for the tip. Unfortunately in this instance it will not work as I 
do in fact query more than a < b. See the nearest function in patch 2.
> Few more nitpicks about this and other patches in the series:
>   
>> +static int compare_distance(const void *left, const void *right)
>> +{
>> +    const struct tinn *l = left;
>> +    const struct tinn *r = right;
>>     
>
> Please don't use void pointers. Use typed pointers, especially that you
> cast them to a hard-coded type.
>
>   

The qsort function I use internally takes that particular function pointer.
>> +const void *init_tinn(struct tinn *dest, const void *buf, size_t num,
>> +    size_t size, float (*distance)(const void *, const void *))
>> +{
>> +    size_t i;
>> +    size_t ref = rand() % num;
>>     
> I'm not so sure using random reference point really necessary.
>
>   

This is actually very important. By randomly selecting a reference 
point, the chance that we get worst-case linear performance out of the 
algorithm becomes extremely small.
>> +static struct tinn tinnPalette[256];
>> +
>>     
>
> This won't work well with multi-threaded apps. You probably should make
> it on the stack for each X11DRV_DIB_SetImageBits_* function. Especially
> that some need only 2 elements. Btw, how big of the gain/loss whill
> there be for 1-bit and 4-bit DIBs?
>
>   

I'm sure you are right. I'll change the array allocation as you suggest. 
I'm sure you mean the X11DRV_DIB_GetImageBits_* though. As a percentage 
probably quite significant, linear would be reasonably fast for small 
sized palettes though. Although this algorithm will never really be any 
slower.
>> +                    q.rgbRed = srcval.peRed;
>> +                    q.rgbGreen = srcval.peGreen;
>> +                    q.rgbBlue = srcval.peBlue;
>>     
>
> Looks much better, if written as:
> q = srcval;
>   

I guess it does. I had to do a lot of copy+paste though so I kept the 
format the same throughout, since colors are not always retrieved in 
that way.
>   
>> -                                      ((srcval >>  7) & 0xf8) | /* r */
>> -                                      ((srcval >> 12) & 0x07),
>> -                                      ((srcval >>  2) & 0xf8) | /* g */
>> -                                      ((srcval >>  7) & 0x07),
>> -                                      ((srcval <<  3) & 0xf8) | /* b */
>> -                                      ((srcval >>  2) & 0x07) ) << (7-(x&7)) );
>> +
>> +                            q.rgbRed = ((srcval >>  7) & 0xf8) |
>> +                                ((srcval >> 12) & 0x07);
>> +                            q.rgbGreen = ((srcval >>  2) & 0xf8) |
>> +                                ((srcval >>  7) & 0x07);
>> +                            q.rgbBlue = ((srcval <<  3) & 0xf8) |
>> +                                ((srcval >>  2) & 0x07);
>>     
> What happened to the comments and alignment?
>
> Vitaliy Margolen.
>
>
>   

The comments are not really needed now. First of all they weren't very 
descriptive, and also I'm now assigning the colors to individual bytes 
which are named appropriately so it is easy to see what they refer to. 
The code looks to be aligned I think.