Re: [PATCH 3/3] winex11: Use TINN algorithm to speed up colour lookups. (try 2)
"Vitaly Budovski" <vbudovski(a)gmail.com> wrote:
Now that you got rid of sqrt calls usage of float numbers internally doesn't look justified (to me) anymore.
Only because in this instance it is used with integer data. It doesn't need to be limited to just integer values. Besides, what would be gained by changing it to integers as you suggest?
What would be gained is an additional speed. Since this code is supposed to be used to handle palette/color data there is no need to use floats at all. -- Dmitry.
Dmitry Timoshkov wrote:
"Vitaly Budovski" <vbudovski(a)gmail.com> wrote:
Now that you got rid of sqrt calls usage of float numbers internally doesn't look justified (to me) anymore.
Only because in this instance it is used with integer data. It doesn't need to be limited to just integer values. Besides, what would be gained by changing it to integers as you suggest?
What would be gained is an additional speed. Since this code is supposed to be used to handle palette/color data there is no need to use floats at all.
As I explained previously, this algorithm makes no assumptions about the data that is being queried. Just because in this case (patch 3) we are working with RGB colour data doesn't mean it is limited to only that. It will work with *any* values, as long as you can provide an appropriate distance function. For this reason, I do not think that limiting the distances to integer values makes much sense. Getting rid of the square root has some benefit because it is generally an expensive operation. I do not think that getting rid of floats would give any noticeable performance improvements.
"Vitaly Budovski" <vbudovski(a)gmail.com> wrote:
As I explained previously, this algorithm makes no assumptions about the data that is being queried. Just because in this case (patch 3) we are working with RGB colour data doesn't mean it is limited to only that. It will work with *any* values, as long as you can provide an appropriate distance function. For this reason, I do not think that limiting the distances to integer values makes much sense. Getting rid of the square root has some benefit because it is generally an expensive operation. I do not think that getting rid of floats would give any noticeable performance improvements.
I undrestand that the algorithm might be used for any data, but there is very slim chance that Wine will need that flexibility. At least so far it's proposed for use only for color/palette data, which is integer by its nature. -- Dmitry.
Dmitry Timoshkov wrote:
"Vitaly Budovski" <vbudovski(a)gmail.com> wrote:
Now that you got rid of sqrt calls usage of float numbers internally doesn't look justified (to me) anymore.
Only because in this instance it is used with integer data. It doesn't need to be limited to just integer values. Besides, what would be gained by changing it to integers as you suggest?
What would be gained is an additional speed. Since this code is supposed to be used to handle palette/color data there is no need to use floats at all.
While I cannot vouch for the accuracy, this might be of interest: http://lua-users.org/wiki/FloatingPoint
On 5/7/07, Duane Clark <fpga(a)pacbell.net> wrote:
Dmitry Timoshkov wrote:
"Vitaly Budovski" <vbudovski(a)gmail.com> wrote:
Now that you got rid of sqrt calls usage of float numbers internally doesn't look justified (to me) anymore.
Only because in this instance it is used with integer data. It doesn't need to be limited to just integer values. Besides, what would be gained by changing it to integers as you suggest?
What would be gained is an additional speed. Since this code is supposed to be used to handle palette/color data there is no need to use floats at all.
While I cannot vouch for the accuracy, this might be of interest: http://lua-users.org/wiki/FloatingPoint
Vitaly, I think I recommend using just integers, and make this private for DIBs. Speed is nice for what we can use it for. If someone later needs the float use, then we can create a separate float version and included where-ever it's used. There is nothing wrong with having two versions when each is justified. If you can get your code accepted I'll probably move it over to the DIB engine eventually. If the wined3d people want to use it, I could make it available somehow? Jesse
Jesse Allen wrote:
On 5/7/07, Duane Clark <fpga(a)pacbell.net> wrote:
Dmitry Timoshkov wrote:
"Vitaly Budovski" <vbudovski(a)gmail.com> wrote:
Now that you got rid of sqrt calls usage of float numbers internally doesn't look justified (to me) anymore.
Only because in this instance it is used with integer data. It doesn't need to be limited to just integer values. Besides, what would be gained by changing it to integers as you suggest?
What would be gained is an additional speed. Since this code is supposed to be used to handle palette/color data there is no need to use floats at all.
While I cannot vouch for the accuracy, this might be of interest: http://lua-users.org/wiki/FloatingPoint
Vitaly,
I think I recommend using just integers, and make this private for DIBs. Speed is nice for what we can use it for. If someone later needs the float use, then we can create a separate float version and included where-ever it's used. There is nothing wrong with having two versions when each is justified. If you can get your code accepted I'll probably move it over to the DIB engine eventually. If the wined3d people want to use it, I could make it available somehow?
Jesse
Both floats and integers have their share of problems. Since the square root operation has been removed, we are dealing with much larger numbers, potentially larger than can fit into unsigned int without looping back around. This is why I think keeping distances as floats is a good idea, since they can represent a much larger range of values. As I mentioned earlier, there is no noticeable performance difference between using floats and integers (cheap operations +-*) for the distances so I really don't see the reason for all the resistance. As for making this private for dibs, are you suggesting that I move the algorithm into the winex11 directory? I'm certain it could be useful in other areas too. There is a nearest colour function in gdi32 also, so once this patch gets accepted I will probably make use of it there too. Stefan also mentioned a possible use for the algorithm in wined3d.
"Vitaly Budovski" <vbudovski(a)gmail.com> wrote:
Both floats and integers have their share of problems. Since the square root operation has been removed, we are dealing with much larger numbers, potentially larger than can fit into unsigned int without looping back around. This is why I think keeping distances as floats is a good idea, since they can represent a much larger range of values.
Not really. sizeof(float) == 4, i.e. same as sizeof(int), but a float type carries much more information, therefore can't "deal with much larger numbers".
As I mentioned earlier, there is no noticeable performance difference between using floats and integers (cheap operations +-*) for the distances so I really don't see the reason for all the resistance.
Even if it looks like a "cheap" operation, floating point operations are much slower than an integer ones. -- Dmitry.
Dmitry Timoshkov wrote:
"Vitaly Budovski" <vbudovski(a)gmail.com> wrote:
Both floats and integers have their share of problems. Since the square root operation has been removed, we are dealing with much larger numbers, potentially larger than can fit into unsigned int without looping back around. This is why I think keeping distances as floats is a good idea, since they can represent a much larger range of values.
Not really. sizeof(float) == 4, i.e. same as sizeof(int), but a float type carries much more information, therefore can't "deal with much larger numbers".
Yes, but you agree that a float can represent much larger values than 4294967295? This is the point I'm trying to make.
As I mentioned earlier, there is no noticeable performance difference between using floats and integers (cheap operations +-*) for the distances so I really don't see the reason for all the resistance.
Even if it looks like a "cheap" operation, floating point operations are much slower than an integer ones.
Really, the performance difference is not noticeable in this instance. But I'm open to any ideas you may have as to how we could avoid using floats, yet not run into the overflow situations so easily. We could probably use division somewhere but I don't think that's actually any better performance-wise.
But I'm open to any ideas you may have as to how we could avoid using floats, yet not run into the overflow situations so easily. We could probably use division somewhere but I don't think that's actually any better performance-wise.
It is, when implemented via bit-shifts (very cheap). I know wine is written in pure C, but with a little C++ template magic you should be able to have fixed-point math that acts like floating, only having the compiler take care of the binary point at compile-time using the type system, and emitting only integer operations. Still wouldn't be as efficient as hand-designed fixed-point pumped through the optimizing compiler. I'm pretty sure ints are still much better performance-wise. That article you cited is not telling the whole story; no operation on a modern CPU is executed in a single cycle. The aggregate throughput when considering optimal pipelining may be one float instruction per cycle... but integer operations routinely achieve several (on a Core 2 I believe up to four instructions can be started into the pipelines per cycle, per core). There's also pipeline stalls and flushes to consider, where I believe further investigation will again show much bigger performance hits on floating-point. And no mention of SIMD was made whatsoever, which is capable of the highest performance in every discussion I've seen. Furthermore SIMD has built-in support for things like integer-multiply-keeping-only-the-most-significant-half and multiply-add, at least on x86 architecture, which if I'm not mistaken is still a wine requirement for running x86 PE files. And when you try to save space by using 32-bit float, you lose everywhere. 32-bit floating-point store involves rounding and is slow. As a result, compilers maintain high precision as long as possible, which means you lose repeatability (integer expressions tend to give the same results with or without optimizations, float -- do not). If you go to 64-bit floats, then you should compare against the range of 64-bit integers, which modern CPUs also support at full speed for basic operations.
participants (5)
-
Dmitry Timoshkov -
Duane Clark -
Jesse Allen -
richardvoigt＠gmail.com -
Vitaly Budovski