[Kstars-devel] HTM circle/rectange timing results

[James Bowlin]

I created two simple timing loops (in C, not Perl) to test the timing
of intersect_circle() vs. intersect_rect().  I am using the Perl interface
which has been incredibly useful.

In these examples, I am using a level 5 mesh which will average 16 stars
per triangle.

For small areas, the circle beats out the rectangle by a factor of 4.3.
For an area of roughly 1 degree^2, both circle() and rectangle() find the
same three triangles:

  10000 level 5, 1-degree rects took 6.11 seconds
  1637 rectangles/second

  10000 level 5, 1-degree circles took 1.43 seconds
  6993 circles/second

This makes sense.  The time is dominated by the construction of the
constraints and the rectangle has 4 times as many constraints as the
circle.

For a larger area, roughly 10 degrees x 10 degrees, about 70 triangles
are returned and the speed advantage of the circle decreases:

  1000 level 5, 10-degree rects took 2.27 seconds
  441 rectangles/second

  1000 level 5, 10-degree circles took 0.85 seconds
  1176 circles/second

Note that both the circle() and rectangle() significantly slowed down 
on the larger area.  The rectangle is over 4x slower and the circle
is almost 6x slower.

When we increase the areas to 100 x 100 degrees the slowdown continues.
Both circle() and rectangle() are returning about 500 triangles (out
of 8,192, which is about 1/16th of the total). 

  100 level 5, 100-degree rects took 1.60 seconds
  62 rectangles/second

  100 level 5, 100-degree circles took 0.96 seconds
  104 circles/second

The lead of the circle is now less than a factor of 2.  But the big news
is the overall slowdown as the number of returned triangles increases.
The rectangle is now 25x slower and the circle() is 67x slower.


Size  Triangles  Rect-Time  Circle-Time Circle-Time/Triangle
----  ---------  ---------  ----------- --------------------
  1       3         0.61 ms     0.14 ms    46 us
 10      70         2.3  ms     0.85 ms    12 us
100     510        16.0  ms     9.6  ms    18 us

To put this in perspective, Kstars is clipping/plotting 200k objects
per second, which is 5 us/object.  So the time to make a small circle
intersection is roughly the same as plotting 30 objects.  The time
for the large circle intersection is the same as plotting 2,000 objects.

Conclusions:

  1) The circle is significantly faster than the rectangle.
     The only reason to keep rectangles around is as an
     aid to diagnostics.

  2) There is a significant speed cost when large numbers of
     triangles are returned.  In the test cases the time increased
     by a factor of almost 100.  We know that we can get a lot of
     this speed back by adding additional, courser meshes for larger
     views.  I don't know if the time savings is worth the extra
     complexity and possibly size.  Perhaps, it will suffice to
     just use a courser primary mesh like a level 3 or level 4.
     I think I will look at these next.


One more thing.  I'm still running kstars-3.5.x and perhaps this has
already been changed in the 4.x branch, but I think it would be really
cool to have the option to have the magnitude limit actually scale with
the zoom factor.  Right now in the 3.5 branch there is one "zoomed in"
limit and another "zoomed out" limit.  Likewise the "show XXX for stars
brighter than YY" limit could be made to scale with the zoom factor.
That way when the user zooms in, fainter and fainter stars appear and
more and more labels appear so that the density of stars and labels on
the screen roughly stays constant.  Then as the user continues to zoom
in, the on-screen density decreases because we've reached the limit of
our catalog.  I think these should be options in addition to the current 
ones which do have their uses. 


-- 
Peace, James