My Bézier curve code was not optimal, so I decided to learn how to profile with SBCL. In particular, I was not yet doing a binary search of the sampled points, neither was I doing an interpolation to recover the parameter t. Finally, I was sampling the curve at a fixed high frequency (probably too high for most cases). So I changed a list to an array, implemented binary search and interpolation to recover t, and set the sample frequency at 2x the number of division points.
SBCL profiling is very easy. The overall performance here is probably bound by the file write, which explains why the overall time for the top level function is more or less constant. But check out the other function timings and the “consed” column. The sample frequency change is clear in the number of calls to DECASTELJAU.
Before:
VECTO-TEST> (watch '(tenths-test-bezier "test.png"))
seconds | consed | calls | sec/call | name
----------------------------------------------------------
0.278 | 26,952,592 | 1 | 0.278034 | TENTHS-TEST-BEZIER
0.093 | 10,288,576 | 26,576 | 0.000004 | VEC-LENGTH
0.037 | 10,236,064 | 26,525 | 0.000001 | POINT-DISTANCE
0.015 | 1,607,920 | 12,624 | 0.000001 | INTERP-SINGLE
0.003 | 385,024 | 32,990 | 0.0000001 | MAKE-POINT
0.002 | 0 | 92,607 | 0.0000000 | XCOORD
0.000 | 0 | 1 | 0.000000 | BEZIER-POINTS
0.000 | 1,834,496 | 51 | 0.000000 | FIND-BEZIER-PARAM
0.000 | 36,864 | 1 | 0.000000 | POLYLINE-LENGTH
0.000 | 73,664 | 1 | 0.000000 | SAMPLE-BEZIER
0.000 | 8,192 | 51 | 0.000000 | BEZIER-POINT-AND-NORMAL-AT
0.000 | 339,968 | 1,001 | 0.000000 | DECASTELJAU
0.000 | 8,192 | 51 | 0.000000 | NORMAL
0.000 | 16,384 | 51 | 0.000000 | NORMALIZE
0.000 | 16,384 | 51 | 0.000000 | SCALE
0.000 | 40,960 | 51 | 0.000000 | ROTATE
0.000 | 2,076,672 | 6,312 | 0.000000 | INTERP
0.000 | 16,384 | 51 | 0.000000 | -POINT
0.000 | 0 | 92,607 | 0.000000 | YCOORD
----------------------------------------------------------
0.428 | 53,938,336 | 291,603 | | Total
After:
VECTO-TEST> (watch '(tenths-test-bezier "test.png"))
seconds | consed | calls | sec/call | name
---------------------------------------------------------
0.439 | 26,773,984 | 1 | 0.438705 | TENTHS-TEST-BEZIER
0.004 | 253,952 | 912 | 0.000005 | INTERP
0.004 | 12,288 | 101 | 0.000035 | POINT-DISTANCE
0.000 | 16,384 | 1 | 0.000000 | BEZIER-POINTS
0.000 | 32,768 | 393 | 0.000000 | FIND-BEZIER-PARAM
0.000 | 24,576 | 1 | 0.000000 | SAMPLE-BEZIER
0.000 | 16,384 | 51 | 0.000000 | BEZIER-POINT-AND-NORMAL-AT
0.000 | 32,768 | 101 | 0.000000 | DECASTELJAU
0.000 | 57,296 | 152 | 0.000000 | VEC-LENGTH
0.000 | 0 | 51 | 0.000000 | NORMAL
0.000 | 8,192 | 51 | 0.000000 | NORMALIZE
0.000 | 16,384 | 51 | 0.000000 | SCALE
0.000 | 0 | 51 | 0.000000 | ROTATE
0.000 | 175,856 | 1,824 | 0.000000 | INTERP-SINGLE
0.000 | 0 | 51 | 0.000000 | -POINT
0.000 | 0 | 2,535 | 0.000000 | YCOORD
0.000 | 0 | 2,535 | 0.000000 | XCOORD
0.000 | 16,384 | 1,166 | 0.000000 | MAKE-POINT
---------------------------------------------------------
0.446 | 27,437,216 | 10,028 | | Total
A couple of “it would be nice ifs” struck me while writing this code: IWBNI LOOP could collect into any sequence, not just a list; and IWBNI there was a CL equivalent of Haskell’s scanl. Both of these lacks could be solved (if they aren’t already and I’ve just overlooked them) but my CL macro skills aren’t all that yet.