Is it possible to improve the performance of line()?

[ceball]

I started with examples/timeseries.ipynb, modifying to have only one column:

In a bit of an ugly process, I then time canvas.line() and canvas.points() for increasing repeats of the dataframe:

line seems to be a lot slower than points:

(Sorry for the screenshots, but github doesn't seem to allow notebooks to be attached.)

[ceball]

I just looked at the source code and see line uses agg=any() by default, while points uses agg=count() by default. So just a note to confirm that the findings above don't change much if I use the same reduction for both line and points.

[jbednar]

Joseph or Greg had some ideas about how to speed it up, but fundamentally lines should always be slower than points because points just increments one bin, while line needs to solve the equation for a line and increment every point along the way.

[ceball]

Yes, I guess the title should have been more like, 'Is line the expected amount slower than points?', or maybe, 'Can line be made faster?'.

[jbcrail]

My immediate suggestions for performance gains are:

1. Switch to integer-specific Bresenham line-drawing algorithm

We currently use the more general algorithm that supports both ints and floats. However, by the time we need to draw a line, the points have been mapped to an integer space so float support is redundant.

2. Switch line-clipping algorithm

We currently use Cohen-Sutherland for clipping a line to a bounding box, but the Liang-Barsky algorithm is considered significantly more efficient.

[jbednar]

I'd be very happy to try both suggestions; we're using line a lot in some performance-critical applications, so anything will help...

[jbednar]

It would be nice to re-run those benchmarks now that #495 has been merged.