Repository navigation
Large overhead for drawing plots with lots of data points #94
Description
A private email from a person who noticed poor performance of the plot package when plotting millions of data points, prompted me to run some tests to see what the overhead of the actual plot package is on top of racket/draw (which is used for all the drawing). The result is that it is a lot.
There are two programs below (the second one has two variants):
- one is drawing a plot using
lines - the second one ,
do-manual-plotwill draw the plot using thedraw-linesdc<%>method, and do all plotting calculations itself - the third one,
do-manual-plot/individual-lineswill draw the plot using onedraw-linecall for each line segment, also doing all plotting calculations itself.
Here is the performance of the programs
| data points | plot | draw-lines | individual draw-line |
|---|---|---|---|
| 100 | 31ms | 15 ms | 15ms |
| 1'000 | 78ms | 15ms | 15ms |
| 10'000 | 920ms | 93ms | 156ms |
| 100'000 | 81'515ms | 3'046ms | 1'484ms |
| 1'000'000 | too long | 45'734ms | 16'634ms |
For large number of points, the time of the plot version becomes too large very quickly, much more than the time increase for draw-lines and draw-line versions. Note that plot ultimately uses the same draw package, so the plot package overhead is probably the plot time minus the draw-lines time.
I also found that, for large number of points, a single draw-lines call is much slower than multiple draw-line calls, one for each line -- this is somewhat counterintuitive, but I could not find an explanation for this...
#lang typed/racket
(require plot)
(: points (Listof (List Real Real)))
(define points (build-list 100000 (lambda ([x : Index]) (list x (random)))))
(time
(parameterize ([plot-decorations? #f])
(plot-bitmap (lines points #:color 6))))#lang racket
(require racket/draw
plot ;; just for plot-width, plot-height
)
(define (transform-points p)
(define-values (min-x min-y max-x max-y)
(for/fold ([min-x (first (first points))]
[min-y (second (first points))]
[max-x (first (first points))]
[max-y (second (first points))])
([point (in-list (rest points))])
(define x (first point))
(define y (second point))
(values (min min-x x) (min min-y y) (max max-x x) (max max-y y))))
(define dx (- max-x min-x))
(define dy (- max-y min-y))
(define w (plot-width))
(define h (plot-height))
(define (transform point)
(define x (first point))
(define y (second point))
(cons (* w (/ (- x min-x) dx))
(* h (- dy (/ (- y min-y) dy)))))
(map transform points))
(define (do-manual-plot points)
(define bm (make-object bitmap% (plot-width) (plot-height)))
(define dc (new bitmap-dc% [bitmap bm]))
(send dc set-pen (send the-pen-list find-or-create-pen "purple" 1 'solid))
(define plot-points (transform-points points))
(send dc draw-lines plot-points)
bm)
(define (do-manual-plot/individual-lines points)
(define bm (make-object bitmap% (plot-width) (plot-height)))
(define dc (new bitmap-dc% [bitmap bm]))
(send dc set-pen (send the-pen-list find-or-create-pen "purple" 1 'solid))
(define plot-points (transform-points points))
(for ([p1 (in-list plot-points)]
[p2 (in-list (rest plot-points))])
(send dc draw-line (car p1) (cdr p1) (car p2) (cdr p2)))
bm)
(define points (build-list 100000 (lambda (x) (list x (random)))))
(printf "individual draw-line calls~%")
(time (do-manual-plot/individual-lines points))
(printf "single draw-lines call~%")
(time (do-manual-plot points))
Activity
samth commentedon Apr 28, 2021
I started looking at this because I was worried it was Typed Racket-induced contract overhead, but that doesn't seem to be the case. One thing I did see is that
plotseems to do a bunch of other O(N) operations (for example, I think there are O(N) calls tostyled-segmentindraw-lines*in plot/private/common/draw.rkt).alex-hhh commentedon Apr 28, 2021
I think you are correct. This problem might indeed be limited just to the lines renderer itself. If using the
pointsrenderer,plottakes roughly the same amount of time as usingracket/drawdirectly. Using this program as a test:mfelleisen commentedon Apr 28, 2021
alex-hhh commentedon Jun 21, 2021
I spend some time investigating this issue and found the following:
styled-segmentanddraw-lines*are not used in this case (as was originally suggested by @samth), since the line style is'soliddraw-lines/pen-styledirectly calls thedraw-linesmethod on the device context (see the case for'solidpen style)plot/plot-lib/plot/private/common/draw.rkt
Line 431 in 6743d6b
current-inexact-millisecondsand, for 100000 points, rendering the entire plot takes 25390 ms and the draw lines call on the DC takes 22285 ms (87% of the time). Note that the timings are different than originally reported, as I ran the new tests on a different computer.It looks to me that, for large number of points, calling
draw-lineson thedc<%>interface using Typed Racket is slow -- @samth , is there a way to further investigate if this is indeed the case?For reference, this is the instrumentation I did:
And this is the program I ran:
alex-hhh commentedon Jun 21, 2021
I also converted to Typed Racket the program that uses
draw-linesdirectly (see issue description) and there is no performance problem with the draw-lines call -- this seems to be somehow related to the draw-lines call inside the plot package.samth commentedon Jun 21, 2021
I believe that Typed Racket program has no contract boundaries that aren't there always in plot -- ie, I don't think there's anything Typed Racket about your example.
To see if Typed Racket is the problem, I recommend the contract profiler -- if it shows a non-trivial percentage of time in contracts, particularly contracts that look to be types, then that's likely a problem. I think when I tried this before for my earlier comment that didn't happen.
alex-hhh commentedon Jun 22, 2021
Hi @samth , I am confused about
contract-profile. At first, I removed the "compiled" folders from the plot package, to ensure that the plot package code is instrumented, and contract profile showed that no significant time is spent on the contracts. Next, I removed the compiled folders from the draw library as well. When I ran contract profile again, I got the following:The lines starting with "***" are the printfs I added to the plot code. The contract profiler now shows that 95% of the time is spent in contracts, but the contract it flags is at the "entry" into the plot package (the "lines" renderer), which does not make much sense to me....
rfindler commentedon Jun 22, 2021
Looking at the implementation of
sequence/ccontract, it seems like it could benefit from some special cases for lists and maybe other things. For example, with the diff below, the contract(sequence/c integer?), when applied to short lists of integers is about 4x faster.samth commentedon Jun 22, 2021
My guess is that the contract cost is in the result contract, not shown in the print out, which is Renderer2d. That's an object which will impose cost on every method access.
samth commentedon Jun 22, 2021
One other thing, @alex-hhh, I think you meant to use
vs1in the call todraw-lines.samth commentedon Jun 22, 2021
I'm now much more confused. I tested with the following program:
This should have no Typed Racket-related contract boundaries -- all of the listed plot modules as written in Typed Racket. It has the same slow performance that @alex-hhh reports.
However, when I put a
printfwhere @alex-hhh did, thedcvalue is#(struct:wrapper-object:bitmap-dc% ...)which indicates that it's a contracted object. Unfortunately it seems likevalue-contractdoesn't do the right thing for such values; it produces#fon that value. Note thatbitmap-dc%is protected by its own class contract that is unrelated to Typed Racket, so that might be part of it.Furthermore,
raco contract-profileshows effectively no time in contracts for that program for me (as I expected). You shouldn't see different behavior from the contract profiler with and without compiled files, though, since the instrumentation is done at runtime.samth commentedon Jun 22, 2021
Removing the contract inside racket/draw doesn't remove the wrapper-object so I'm still confused.
alex-hhh commentedon Jun 22, 2021
This is from one of my earlier attempts to determine the step that takes a long time -- the last transformation,
(map cons-fl vs), is not technically needed, at least not in this test case. The rendering includes creating several copies of the list of points (with transformations), and I first thought that creating these intermediate lists is what take up the time, but, compared with the time it takes to execute thedraw-linescall, the other timings are negligible.samth commentedon Jun 25, 2021
Further investigation:
I put some printouts inside
class-internalto see what the contracts were. They are very close to the types ingui-types.rktin TR, but not exactly the same. For example:The wrapper objects are created with the following blame objects:
However, I can't seem to find the relevant contracts.
I also tried simply removing the use of
contractinconcretize-ictc-methodinclass-internal.rktand just producingmeth, but that did not change the performance.Conclusions so far:
samth commentedon Jun 25, 2021
Further investigation: the mysterious contract is applied as part of this line: https://github.com/racket/plot/blob/master/plot-lib/plot/private/no-gui/plot2d.rkt#L108
However, I don't know why there's a contract there.
bitmap-dc%on that line is imported fromtyped/racket/draw, which directly importsracket/draw/private/bitmap-dcwhich doesn't have any contracts. The class there inherits from various things that also don't have any contracts. So I'm very confused.samth commentedon Jun 27, 2021
At @rfindler's suggestion, I investigated @alex-hhh's hypothesis that calling
draw-lineson a dc in Typed Racket is the slow thing; fortunately that doesn't seem to be the case.Here's the timings I get, for slightly modified versions of Alex's program in the original report. They're almost identical between typed and untyped used of
racket/draw, and around 1 second in both cases. With Alex's (typed) program using plot, I get ~47 seconds. So there's definitely some large overhead in plot that I don't understand, but it isn't just that TR is slow when usingdraw-lines.The code I ran is at https://gist.github.com/samth/385182bcd0c1bc26795aa7e58a81f80b.
alex-hhh commentedon Jun 27, 2021
Hi @samth , I mentioned in a previous comment (#94 (comment)) that using draw-lines from TR does not have a performance problem and I was also puzzled by that....
samth commentedon Jun 28, 2021
One additional note -- I tried using
plot-pictinstead ofplot-bitmap, and that reduces the time to 1 second from 47 seconds, and more significantly, thedraw-linescall takes only 55 ms.samth commentedon Jun 28, 2021
One more piece of (not useful yet) investigation -- this code, which tries to be more like what
plotactually does, is also fast (in Typed Racket).alex-hhh commentedon Jun 28, 2021
I tried
plot-picttoo -- while creating the pict is fast, displaying the resulting pict in the REPL is just as slow (at least on my machine) -- the problem seems to be propagated to the pict drawing code.For what is worth, I also tried using
plot/dcon arecord-dc%and this is fast (although no actual drawing is done, just recording the draw commands). Creating the bitmap separately and usingplot/dcon abitmap-dc%is, however slow.samth commentedon Jun 28, 2021
@alex-hhh I believe that the pict construction is just saving a closure that then runs the expensive code, which then happens when the bitmap is draw.
If the problem is indeed a contract, then it's happening when either the bitmap or the bitmap-dc is created in
plot-bitmap. I checked theeq-hash-codeof thebitmap-dcboth when it's created (inplot-bitmap) and when it's used (indraw-lines/pen-style) and it's the same.A contracted version of that object is created when constructing the new
bitmap-dc%object, but printing out the continuation marks when the construction happens is unfortunately not illuminating.My current conclusions are:
draw-linesmethod takes orders of magnitude longer in one case than in another seems very likely to be caused by contracts or some other kind of indirection.One path forward is to try to construct a test program that is slow in the way plot is, by removing parts of the plot library until we get something smaller.
samth commentedon Jun 28, 2021
Here's another possibility. Below are the traces (from
record-dc%) of whatplotdoes, and what @alex-hhh's test program does, for 10 points. It may be that one of the additional commands makes the drawing much slower (clipping-region seems like the big difference).Plot
direct
mflatt commentedon Jun 28, 2021
If I'm reading correctly that smoothing is one of the differences, that could be significant.
samth commentedon Jun 28, 2021
Smoothing seems to be about a 4x slowdown on many individual
draw-linecalls and a 20x slowdown on one largedraw-linescall.mflatt commentedon Jun 28, 2021
To answer the question (that I now see) about why
draw-linesis slower than separatedraw-linecalls:draw-linesjoins consecutive lines with shaping of the shared point determined by a pen's join, whiledraw-linejust uses the pen cap on each end of each line.samth commentedon Jun 28, 2021
Having tested this in plot, if you remove the line
(send dc set-smoothing 'smoothed)inreset-drawing-paramsinplot-device.rkt, then drawing the points withplot-bitmaptakes approximately the same amount of time as drawing directly on abitmap-dc%.I'm not sure whether smoothing is needed for plot, but that seems to be the source of the overhead that this issue discusses.
alex-hhh commentedon Jun 28, 2021
Hi @samth and @mflatt , thanks for finding out the problem. I suspect smoothed drawing is slower because it involves reading back from the drawing buffer. When I did my testing, I only looked at the output for record dc for plot, and smoothing didn't jump out to me as a possible problem...
I will think about how to address this problem, as I don't think that simply disabling smoothing is a good idea -- there is a visible quality difference between a smoothed and non-smoothed plots (although not in the example showed in this issue).
racket-discourse-github-bot commentedon Jan 6, 2023
This issue has been mentioned on Racket Discussions. There might be relevant details there:
https://racket.discourse.group/t/why-is-plot-slower-with-unicode-symbols-in-ticks/1611/10