[Kstars-devel] profiling KStars

[James Bowlin]

On Wednesday 24 May 2006 03:03 pm, Jason Harris wrote:
> > How often are the positions of the stars recalculated?
>
> Yes, the same issue will be even more important for solar system bodies.
> Precession would also be an issue here.

My inclination (no pun intended) would be to have the HTM index attached
to the "fixed stars" as much as possible (at a standard epoch perhaps?)
and deal with precession by changing where in the index we look.  I see
no reason to recalculate the entire index instead of just doing a simple 
conversion of the 4 corners of the skymap.  It seems to me that the 
primary purpose of the index is to provide a small superset of all visible 
objects given the 4 skymap corners.  It will probably also be useful for 
finding objects near the cursor, but again I think it is better to 
translate the queries than to recompute the index.

In general, an index is most useful when it doesn't have to be recomputed
often.  Ideally, we could store the indices of all our "fixed" objects in
a file so they don't have to be recomputed all of the time.  Even if 
objects move a few arc-seconds away from their indexed position would
should be able to compensate for this by enlarging the skymap rectangle
we look up in the HTM by the maximum drift.

This paper:  The Indexing of the SDSS Science 
Archivehttp://www.sdss.jhu.edu/htm/doc/adass99.ps
indicates that there is a standard form for the HTM index.  We should
probably try to adopt this standard unless there are compelling reasons
not to.


> > Yes.  The main benefit of HTM and other spatial indexes is achieved by
> > storing the objects in the index.
>
> Agreed.  We need to figure out how this is to coexist with our current
> object storage strategy, in which objects are stored in a
> Composite/Component hierarchy based on their object type.  Can the HTM
> tree coexist with this existing structure, or are we going to have to
> radically rethink the way we store SkyObjects (again!)

Yes, indexes can certainly co-exist.  It is just like having multiple
indexes in a database table.  No problem if you want to keep the current
way SkyObjects are stored.  The HTM index would then just contain pointers
(or references, if you prefer) to the actually SkyObjects.

> Our current system is optimized for modularity; each Component is
> responsible for updating itself, drawing itself, etc.  So, you just say
> to the master SkyMapComposite: "draw all objects", and it delegates the
> command to each of its children, who either draw themselves or delegate
> the command to their children (if any).  The great thing about this is
> that no one needs to know how to draw or update a Comet, except for
> CometComponent (for example).

This does not seem optimal to me.  It is very good that each type of object
just knows how to draw itself.  But the idea of telling each "type" to
draw itself and all of its children seems inefficient.  

> So how do we map that onto a HTM tree?  One simple idea is to have a
> separate SkyMapComposite for each region in the Mesh (and we'd need a
> mechanism by which moving objects can switch between different HTM
> Composites).  Another idea is to keep one SkyMapComposite, but each
> Component which represents a list of objects will be adapted to contain
> its own HTM tree instead of a simple QList of SkyObject pointers.
>
> Any ideas of a better way to do it?

I would tend towards having SkyMapComposites inside of HTM triangles
rather than having HTM indexes inside of SkyMapComposites.  To draw
the sky, you first find the part of the HTM index that is visible and then
you draw everything that is in that part of the index.  Whether it is one
list of objects inside of each triangle or several lists for the different
types of objects shouldn't matter too much as far as the index is 
concerned.

Things that move rapidly may need their own list that is entirely separate
from the HTM index.  This will depend on how rapidly things move and how
expensive it is to re-index an object.

I'm thinking that we would select certain levels of the HTM that would 
contain lists of the objects they contain but not every level would need
to have these lists.   Also, for stars, the larger triangles could just
have the brighter stars in their lists.  I don't know how many levels
would  need to have lists, but certainly we don't want to be going down
to the smallest triangles in order to draw a map of the entire sky --
that would take forever.

The paper I linked to above says that a 32 bit integer can store up to
14 levels and a 64 bit integer can store up to 30 levels.  The size of
the triangles at the 14th level are between 20 and 30 arcseconds long.

In this scenario I envision, the response to "draw all objects" would
be to give the HTM index the 4 skymap corners to get back a list of
triangles.  Each triangle would contain a list (or lists) of objects
that are inside it need to be drawn (if visible).


> Great, I'm really glad you're interested.  Let's keep the discussion
> going on the list, so we have a really good idea of what's required
> before we actually start hacking.

Yes.  For sure.  But I am very interested in seeing how fast the existing
HTM code is.  A ballpark idea of the speed could affect design decisions.

> Ah, I found a good overview on the KDE wiki:
>
> http://wiki.kde.org/tiki-index.php?page=KDE3To4

Thank you.  That looks like just what I asked for.


> We need to develop the infrastructure to support it first.  I tried to
> compile the HTM code provided at the JHU site I linked before, but I
> haven't gotten it to work yet.  I emailed the people who wrote it, but
> no one seems to be maintaining it now.  I suspect my problems are
> related to gcc-isms in their code that don't exist anymore.  The code is
> kind of ugly too.  Maybe we'd be better off doing our own
> implementation; it's conceptually pretty simple.

In reading their documentation, it looks like they have gone through
several iterations and have made a lot of progress in terms of speed
in each iteration.  

I too tried compiling the C++ code.  It seems to be failing on the newer
"standard" header files.  I am installing an older 2.95 version of gcc now
and maybe I will have better luck with it.  It could be that we just need
the older header files.  My goal is not to jam the existing HTM code into
Kstars now, rather I would like to get a reasonably optimized version of
HTM working so we can get an idea of how fast/slow it is.  Does this
sound reasonable to you?

I would be much more inclined towards fixing their code rather than writing
our own.  

I haven't seen any copyright or license notices in their code.
I would feel more comfortable if we know for certain the current status
of their code.  I hope they eventually answer your inquiries.  


-- 
Peace, James