`gr_polyline` takes ~25min draw 10M points on cario backend

[clouds56]

Most of time are wasting on sort_edges.
Maybe we should split points into chunks, each chunk has no more than say 1k points.

gr/lib/gks/plugin/cairoplugin.c

Lines 550 to 562 in c8a8395

	static void stroke(void)
	{
	int i;
	cairo_move_to(p->cr, p->points[0].x, p->points[0].y);
	for (i = 1; i < p->npoints; i++)
	{
	cairo_line_to(p->cr, p->points[i].x, p->points[i].y);
	}
	cairo_stroke(p->cr);
	p->npoints = 0;
	}

reproduce code

# %%
import numpy as np
import time
import gr

a = np.random.randn(100_000)

chunk_len = 100
n = len(a) // chunk_len
start_time = time.time()
gr.inline("png")
gr.setviewport(0.1, 0.9, 0.1, 0.9)
for i in range(n):
  chunk = a[i * chunk_len:(i + 1) * chunk_len+1]
  gr.polyline((np.arange(len(chunk)) + i * chunk_len) / len(a), (chunk - a.min()) / (a.max() - a.min()))
gr.show()
print(f"Elapsed time: {time.time() - start_time:.2f} seconds")
# result:
# chunk_len = 100_000 Elapsed time: 23.30 seconds
# chunk_len = 10_000 Elapsed time: 10.88 seconds
# chunk_len = 1_000 Elapsed time: 6.24 seconds
# chunk_len = 100 Elapsed time: 2.63 seconds
# chunk_len = 10 Elapsed time: 2.80 seconds

The stack trace look like this.

2257 gr_polyline  (in libGR.dylib) + 60  [0x163f7480c]
2257 gks_polyline  (in libGR.dylib) + 96  [0x163fcc750]
2257 gks_ddlk  (in libGR.dylib) + 244  [0x163fcb084]
2257 gks_cairoplugin  (in cairoplugin.so) + 6708  [0x14e804734]
2257 cairo_stroke  (in libcairo.2.dylib) + 56  [0x137338bc8]
2257 _cairo_default_context_stroke  (in libcairo.2.dylib) + 44  [0x1372a641c]
2257 _cairo_gstate_stroke  (in libcairo.2.dylib) + 500  [0x1372ae484]
2257 _cairo_surface_stroke  (in libcairo.2.dylib) + 392  [0x137320948]
2257 _cairo_image_surface_stroke  (in libcairo.2.dylib) + 128  [0x1372c0d10]
2257 _cairo_compositor_stroke  (in libcairo.2.dylib) + 144  [0x1372a1400]
2257 _cairo_compositor_stroke_impl  (in libcairo.2.dylib) + 292  [0x1372a15e4]
2257 _cairo_spans_compositor_stroke  (in libcairo.2.dylib) + 624  [0x13730cfb0]
2257 clip_and_composite_polygon  (in libcairo.2.dylib) + 460  [0x13730da3c]
2257 composite_polygon  (in libcairo.2.dylib) + 600  [0x13730e468]
2257 _cairo_tor_scan_converter_generate  (in libcairo.2.dylib) + 144  [0x137322420]
  1138 glitter_scan_converter_render  (in libcairo.2.dylib) + 812  [0x1373232cc]
  ! 1138 active_list_merge_edges_from_bucket  (in libcairo.2.dylib) + 36  [0x137323554]
  !   1119 merge_unsorted_edges  (in libcairo.2.dylib) + 48  [0x1373242d0]
  !   : 1119 merge_sorted_edges  (in libcairo.2.dylib) + 116,164,...  [0x1373244c4,0x1373244f4,...]
  !   19 merge_unsorted_edges  (in libcairo.2.dylib) + 36  [0x1373242c4]
  !     16 sort_edges  (in libcairo.2.dylib) + 280  [0x1373243f8]
  !     | 15 sort_edges  (in libcairo.2.dylib) + 280  [0x1373243f8]
  !     | + 13 sort_edges  (in libcairo.2.dylib) + 280  [0x1373243f8]
  !     | + ! 13 sort_edges  (in libcairo.2.dylib) + 280  [0x1373243f8]
  !     | + !   8 sort_edges  (in libcairo.2.dylib) + 280  [0x1373243f8]
  !     | + !   : 6 sort_edges  (in libcairo.2.dylib) + 280  [0x1373243f8]
  !     | + !   : | 4 sort_edges  (in libcairo.2.dylib) + 280  [0x1373243f8]
  !     | + !   : | + 2 sort_edges  (in libcairo.2.dylib) + 280  [0x1373243f8]
  !     | + !   : | + ! 2 sort_edges  (in libcairo.2.dylib) + 300  [0x13732440c]
  !     | + !   : | + !   2 merge_sorted_edges  (in libcairo.2.dylib) + 164,232  [0x1373244f4,0x137324538]
  !     | + !   : | + 2 sort_edges  (in libcairo.2.dylib) + 300  [0x13732440c]
  !     | + !   : | +   2 merge_sorted_edges  (in libcairo.2.dylib) + 72,284  [0x137324498,0x13732456c]
  !     | + !   : | 2 sort_edges  (in libcairo.2.dylib) + 300  [0x13732440c]
  !     | + !   : |   2 merge_sorted_edges  (in libcairo.2.dylib) + 72,332  [0x137324498,0x13732459c]
  !     | + !   : 2 sort_edges  (in libcairo.2.dylib) + 300  [0x13732440c]
  !     | + !   :   2 merge_sorted_edges  (in libcairo.2.dylib) + 72,124  [0x137324498,0x1373244cc]
  !     | + !   4 sort_edges  (in libcairo.2.dylib) + 300  [0x13732440c]
  !     | + !   : 4 merge_sorted_edges  (in libcairo.2.dylib) + 324,72,...  [0x137324594,0x137324498,...]
  !     | + !   1 sort_edges  (in libcairo.2.dylib) + 28  [0x1373242fc]
  !     | + 2 sort_edges  (in libcairo.2.dylib) + 300  [0x13732440c]
  !     | +   2 merge_sorted_edges  (in libcairo.2.dylib) + 116,120  [0x1373244c4,0x1373244c8]
  !     | 1 sort_edges  (in libcairo.2.dylib) + 300  [0x13732440c]
  !     |   1 merge_sorted_edges  (in libcairo.2.dylib) + 168  [0x1373244f8]
  !     3 sort_edges  (in libcairo.2.dylib) + 300  [0x13732440c]
  !       3 merge_sorted_edges  (in libcairo.2.dylib) + 124,208,...  [0x1373244cc,0x137324520,...]
  1100 glitter_scan_converter_render  (in libcairo.2.dylib) + 848  [0x1373232f0]
  ! 1016 sub_row  (in libcairo.2.dylib) + 404,476,...  [0x137323b34,0x137323b7c,...]
  ! 84 sub_row  (in libcairo.2.dylib) + 144  [0x137323a30]
  !   84 step  (in libcairo.2.dylib) + 28,12,...  [0x13732519c,0x13732518c,...]
  19 glitter_scan_converter_render  (in libcairo.2.dylib) + 300  [0x1373230cc]
    19 polygon_fill_buckets  (in libcairo.2.dylib) + 152,156,...  [0x137323478,0x13732347c,...]