3 ms·
> The naïve algorithm in float averages 4.81 µs, Bresenham’s algorithm averages at 1.84 µs, my fixed point variation at 1.74 µs. The Fixed point implementation
by vanderZwan 10y ago
> The naïve algorithm in float averages 4.81 µs, Bresenham’s algorithm averages at 1.84 µs, my fixed point variation at 1.74 µs. The Fixed point implementation runs about 5% faster. Which isn’t all that much, but still better than Bresenham’s; and much better than the naïve version using mixed floats and integers.
> The situation is similar on the 64 bits machine, but the advantage of fixed point vanishes. Both methods takes very similar times: fixed point averages at 0.85 µs and Bresenham 0.84 µs, a difference of about 1%. However, the naïve implementation is still very far behind, at 2.96 µs.
When you said "easily beaten" I kind of expected more than just a 1-5% performance improvement.
There is also another (potential) problem with fixed point: it works by adding up rounded numbers:
> The only thing we need, is to compute the slope m as a fixed point number rather than a floating point number.
As a result, the fixed point might create rendering artefacts from adding up a rounded number repeatedly. This makes the whole thing an apples-to-oranges comparison:
- floating point method that does multiply/divide every iteration
- fixed point that adds a rounded fraction
- Bresenham that does unrounded fraction adding by splitting the fraction into an accumulator and divisor (Bresenham is actually really simple primary school math with some geometry on top)
To make a truly fair comparison, we should add a version that precomputes the floating point fraction, and adds that each iteration; I suspect the main slowdown of the naive floating point algorithm is the repeated multiply/divides more than the cast to integer, not the casts.
- rwallace 10y ago> I suspect the main slowdown of the naive floating point algorithm is the repeated multiply/divides more than the cast to integer, not the casts. You'd be surprised. Last time I tried it, casting a floating point number to an integer was many times slower than floating point multiply.
- vanderZwan 10y agoNow that you mention it, I know the basic "add/sub is faster than multiply is much faster than divide" order, but I have no idea how it compares to casts.. why isn't that ever mentioned anywhere?
- rwallace 10y agoI'm guessing for the same reason casts are slow; they're not bottlenecks for the most common number crunching workloads, so it doesn't occur to anyone they might be bottlenecks for somewhat less common ones.