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

Vitaliy Margolen wine-devel at kievinfo.com
Fri May 4 19:53:51 CDT 2007


Vitaly Budovski wrote:
> 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.
And what is so special about subtracting one from the other?

>> 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.
And the problem is what? Any pointer is compatible with void* (not other
way around).

Vitaliy Margolen.



More information about the wine-devel mailing list