From kstars-devel Tue May 23 18:27:19 2006 From: Jason Harris Date: Tue, 23 May 2006 18:27:19 +0000 To: kstars-devel Subject: [Kstars-devel] profiling KStars Message-Id: <44735407.1010806 () 30doradus ! org> X-MARC-Message: https://marc.info/?l=kstars-devel&m=114840892829281 Hello, I've begun to work on trying to speed KStars up a bit. I've been trying to use callgrind to profile KStars, but I'm having trouble getting it to work. When I run kstars through callgrind, it always seems to crash when it finishes the startup sequence and draws the map (which is exactly the part I want to profile!). If anyone is interested in trying to help profile KStars, please reply. Even without the profiling results, I have some ideas on how we can save CPU cycles. One expensive procedure is that every time the skymap is recomputed, we need to determine whether each object is on-screen, based on its position in the sky relative to the current Focus point. The function we have for this (SkyMap::checkVisibility()) is fairly well-optimized, but it still needs to be run on every object in the database, so any savings in this function should have a big payoff. One idea is to use what's called a "hierarchical triangular mesh" (HTM). The concept is described in detail here: http://www.sdss.jhu.edu/htm/ but here is a basic description: We are dividing the celestial sphere into a large number of nested triangular sections. The toplevel division uses the Zenith, Nadir (anti-zenith), and the 4 cardinal points on the equator as vertices to divide the sky into 8 equilateral spherical triangles. Then, each of these can be divided into 4 sub-triangles by connecting the midpoints of each triangle's sides. Then each of *those* can be divided into 4 pieces the same way. You can continue this to as many levels as you like, dividing the sphere into smaller and smaller pieces. At a given level, any triangle can be identified by a simple integer, indicating its location at each level in the hierarchy. For example, you could have a triangle "+203102311201" (the leading "+/-" indicates northern vs. southern hemisphere, then you have digits 0-3 identifying which sub-triangle at the current level). I think I would probably use a binary two-bit representation for each level, instead of the digits 0123 (i.e., 0=="00", 1=="01", 2=="10", 3=="11"), so the above triangle ID would be "+100011010010110101100001", or +9,252,193 in decimal. Ok, so how does this help us? I think it can provide a way to tell very quickly whether a point is onscreen or not. For example, consider a case where the four corners of the current visible section are in the following triangles: +100011010010110101101001 +100011010010110101111000 +100011010010110101111011 +100011010010110101110001 We must be zoomed in pretty far, because these ID strings only differ near the end. In other words, they all share a common "parent" triangle, namely: +100011010010110101 Any point on the sky which is not also in that parent triangle is instantly rejected as being offscreen. So our checkVisibility() function can be reduced to a few bitwise comparisons of integers, which should be very fast indeed. However, we'd still need to run checkVisibility() on the entire object catalog every time. 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. I don't have all the details of exactly how this should be implemented, but I just wanted to share things that I'm thinking about here. Another idea I'm playing with is one that's come up before on this list: modifying SkyPoint to store the X,Y,Z coordinates of each point, instead of (or in addition to) the RA and Dec coordinates. This could improve the speed of calculating each object's position on the screen. Right now, we do spherical trigonometry on each SkyPoint and the SkyMap FocusPoint to determine the current screen cordinates of a given object, and these calculations are pretty expensive. If we stored the coordinates of each object as X,Y,Z, then we only need to do a simple multiplication to determine each object's screen coordinates (Xs, Ys): Xs = a1*X + b1*Y + c1*Z Ys = a2*X + b2*Y + c2*Z The important thing to realize here is that the numbers (a1,b1,c1,a2,b2,c2) would only need to be determined *once* for a given calculation of the sky. Then, we can loop through all objects and repeat the same multiplication on their (X,Y,Z) coordinates to determine their screen (Xs,Ys) coordinates! The a,b,c values basically represent the coefficients of a rotation matrix, plus some other stuff to account for the curent zoom level and the size of the SkyMap widget. I've done some preliminary testing, and it looks like this method may be about 3 to 4 times faster than our current SkyMap::getXY() function. Well, that's probably a lot to digest. Let me know what you think, and if you're willing to help implement this stuff. regards, Jason _______________________________________________ Kstars-devel mailing list Kstars-devel@kde.org https://mail.kde.org/mailman/listinfo/kstars-devel