[Kstars-devel] profiling KStars

[Jason Harris]

Hi James,

James Bowlin wrote:
> On Tuesday 23 May 2006 12:27 pm, Jason Harris wrote:
>> I've begun to work on trying to speed KStars up a bit.
> 
> Both projects sound very exciting.  In addition to HTM and kd-trees
> there are other spatial indexes such as r-trees but I think that HTM
> will be the way to go because it is optimized for the special case
> where all the objects are on the surface of a sphere.  The beauty of
> HTM is that the index of each object is fixed and totally independent
> of the other objects in the data set.  With kd-trees and r-trees the
> resulting index is data-dependent which can slow things down.  The
> HTM is like a generalization of kd-trees applied to the special case
> of the surface of a sphere.  It is a generalization because it is not
> exactly a "binary space partitioning"  because it is not binary but
> it is a space (surface) partitioning.
> 
> This leads to my first question:  I know there are parameters in the
> HIP files that deal with the drift of stars on the celestial sphere.
> How often are the positions of the stars recalculated?  The spatial
> index will have to be recalculated/re-adjusted whenever these positions
> are updated so the frequency of these updates will affect design decisions.
> 
Yes, the same issue will be even more important for solar system bodies. 
  Precession would also be an issue here.

> On Tuesday 23 May 2006 12:27 pm, Jason Harris wrote:
>> Maybe we  could also store objects in a hierarchical list structure
>> that mimics the HTM, which would allow us to skip entire sections of
>> objects based on their position within the tree.
> 
> 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!)

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).

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 am interested in working on both projects suggested.  The indexing
> project is the most exciting to me but getting rid of unneeded
> transcendental function calls is always a good/fun thing too.

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.

> I'm trying to install qt4, kde4, etc. now.  I found Jason's "QT4 Pep
> Talk" in this mailing list but I still don't know how to install
> kdelibs4_snapshot.  I found the kdelibs4_snapshot section of the KDE
> source repository but even the INSTALL and README files there did not
> discuss downloading and where I should put things and how not to break
> my current KDE, etc.
> 
That message is surely very out of date.  I can try to put together an 
updated version.  The short version is, read the file 
COMPILING-WITH-CMAKE in the root directory of the kdelibs4_snapshot 
directory.  Ah, I found a good overview on the KDE wiki:

http://wiki.kde.org/tiki-index.php?page=KDE3To4

It's very complete and up-to-date, but it does contain some weird 
syntax.  For example, who types:
echo http://www.cmake.org/files/v2.4/cmake-2.4.2.tar.gz | xargs wget
instead of:
wget http://www.cmake.org/files/v2.4/cmake-2.4.2.tar.gz
??

> If I can get kstars-4 up and running, I would like to try putting the
> HIP stars into an HTM, unless someone else is already working on this
> or there is something better for me to be doing.

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.


thoughts?

Jason