Okay, so I started using git for my new personal projects. I almost hate to admit that I really like it.
Just so I can find it again, I’m going to link to a page with some recommendations on commit messages that help make the most out of git. By following these rules, many git features can work even better. Not to mention they make tracking down a particular change easier.
So the problem was to make the following little algorithm really really fast:
My initial solution was slow. Very slow.
Using SQLite, the super-fast and super-lightweight SQL server, and the standard practice of using prepared statements and persistent DB connections didn’t help at all. I was just doing an insane amount of queries and it couldn’t handle it. The creation of a DB cursor was killing me (among other things). The thing is, most of the time I was expecting it to return an empty result set–that is, I was wasting all this time creating DB cursors and empty result sets when I was mostly just testing for the existence of a record.
My first attempt at speeding this up was to create a set (as in a std::set) in memory to hold all my key values. I thought that searching a set would be much quicker since it has less overhead than a DB query. Well, unfortunately, it seems that STL sets do have a lot of overhead. I replaced DB cursors with iterators. It did speed things up slightly, but not nearly enough.
Going into more complex data structures revealed Judy Arrays, a sort of trie on steroids. Since I only needed to test for existence with it, I was able to use the Judy1 variant, which is essentially a bit-set. I was quite impressed with the space requirements, at 1,000,000 entries, each entry was using (on average) 2 bytes. Although this is larger than a standard bit-set, the Judy array lets me resize it on-the-fly which I cannot do with a standard bit-set. So, for small data-sets, it uses very little space, and for larger data-sets it scales up nicely.
So, the space is good, but what really sold me was the speed. These things were fast. The official site says it is optimized to avoid cache-line fills. Their basic rational is that if, for example, a cache-miss takes at least 50 cycles and you can avoid it with more code that runs in at most 50 cycles, you win. This does come at a cost though since the code to do this is horribly complex. At 20,000 lines, some critics say that it is too complex. My thought is that I don’t care about the code in a library so long as it works and works fast–also, when’s the last time you looked at STLs code and said “wow, that’s so simple and short?”
So, in the end, using a Judy array in my project increased speed by a few orders of magnitude. For more information about the library or the technical rational, check out the official site: http://judy.sourceforge.net/.
http://sam.zoy.org/writings/programming/gprof.html
A shared library that you can LD_PRELOAD to fix profiling from within pthread. Something to do with a certain signal not being inherited after calling clone()–this library fixes that problem.
A while ago I started to play with Ruby on Rails. It was nice and all, but Ruby isn’t my language. I’ve never used it aside from playing with rails. PHP is where my experience lies for web development. Hence, I was quite happy when I stumbled upon Symfony.
Symfony is a PHP framework for developing webpages. So far, it is fairly intuitive (in that everything makes sense, not in that everything is obvious). So, I’m making a test site to see how it goes. How will it hold up?
So, here’s what I’ve learned during my time playing with video code: SDL has no idea what time it is! Let’s take a look at this problem and see what’s going on
Symptoms: The first time a video plays, it goes at what looks normal speed. Timings show its run-time is within 0.5 seconds of the expected length. After it comes up again, it is a little faster, not noticeably yet, but it is. After a number of iterations, it is playing at nearly twice its speed.
Debugging: So, first off, I made sure that the pts of the frames were correct. Yup, they all made sense and were what I expected them to be. Odd that the frame scheduled for 15 seconds was being shown 7 seconds into the file. I guess this means my video file itself is still okay, just my player is broke. Most of the videos I’m using are 15fps. So, next, I did something horrible. I hard coded the delay between frames. I ignored the pts entirely and just said that all frames are 66ms apart. At least this way, it won’t speed up, right? Wrong. The videos still sped up! The timing was entirely hard coded! How could they speed up?
Investigation: After this, I took a break because the idea that two delays of the same amount were actually different hurt my head a bit (or was it me hitting my head against the table in frustration?) Either way, a break. When I got back at it I started looking at the SDL source code. It was littered with gettimeofday calls–especially in its delay and timing functions. I guessed that perhaps clock skew was messing things up. There was another option instead of gettimeofday, clock_gettime, that could get time from a monotonic clock that never went backwards (it gives time since some undefined starting point). Unfortunately it didn’t solve my problem.
Solution: I should have followed the old saying “if you want something done right, do it yourself” right from the start. At this point, I just wrote off SDL’s timing as a lost cause and looked into other alternatives. After reading up on multimedia timers I decided to take advantage of Linux’s RTC device. The device node /dev/rtc can give timings at a quick enough pace for all my needs. I wrote a wrapper class around it (based somewhat on mplayer code) and set it to 1024 Hz. I made sure to create my code with a very similar API to SDL’s timer functions. That way, I could just drop my code in SDLs place and hopefully everything would work out nicely. Oddly enough, that’s exactly what happened. My videos now play without speeding up. Actually, they are playing much smoother as well (no jerkiness). Super-ultra good 
Conclusion: For a multimedia library, SDLs timers are sorely lacking. I would have expected them (in fact, I did expect them) to have multimedia quality and precision. I guess I’ll know for next time.
Perhaps one little flag was the source of many of my problems. Setting the flag CODEC_FLAG_EMU_EDGE in AVCodecContext seems to have reduced the CPU usage by about 50%. Setting lowres to true in AVCodecContext reduces CPU usage even more, but it drops the resolution to do it, and it shows.
I have “borrowed” some code from MPlayer to rotate my video. It works correctly and I still can use SDL’s accelerated YUV overlays. Only problem is that on my embedded system, the CPU shoots to 100%. Using MPlayer proper it comes in at 40% with the same video. Both my player and MPlayer use ffmpeg to decode the video. Both output using SDL’s YUV overlay (that uses Xvideo). Both players have about the same time between decoding frames (in fact, mine is a little quicker). Yet, my player is using more CPU and drops frames.
Both myself and my housemate/co-worker have been going over all of the player’s code, ffmpeg’s code, and MPlayer’s code trying to figure out what is causing this problem. So far, we’ve had no success. It is quite frustrating.
Why can’t people just have normally oriented screens?
Okay, I can’t stand certain things. I finally got ffmpeg decoding all our video files. I finally got SDL using Xvideo to display the frames. I finally got amazing performance in our core code path. I finally tested our app on a rotated (portrait) screen and found out the driver disables DRI when this is done! What the hell is that!? The Openchrome driver supports rotating the display, but as soon as you do that, it enables the shadowfb; and when it is enabled DRI is disabled. Ugh. Now, if I use a software video overlay (with software scaling and colourspace conversion) I can get it to work perfectly–just horribly slow. If I use Xvideo, it won’t work at all until I disable the rotation.
OpenGL might come to the rescue here. Since, under normal screen orientation, we have full DRI, OpenGL should work nicely. Time to play with some fancy texture magic.
many hours later
So my app now uses OpenGL to display the video frames. It actually runs at a decent speed at the moment–with arbitrary rotations.
many more hours later
Okay. So it works. It works great. It doesn’t convert from YUV to RGB in hardware. Stupid OpenGL with its lack of support for different colour formats. I have a software converter in place now, but since my whole purpose was to avoid doing stuff in software, I really really hate having it there.
I have finally been able to get SWT to work under MacOS X. One thing I can’t stand about SWT is that instead of choosing the appropriate jar file, it always chooses the first one in the library path. This makes it quite difficult to take advantage of Java’s architecture independence. What am I missing on this one? It shouldn’t be this complicated, right?
So after talking with our client, it seems that the GUI has lost some of the usability when it was rewritten. It is much more efficient and responsive now but it much less intuitive. I’m now taking a look at it, but this is my first major work on it since we started using SWT. So far, I much prefer Swing.
Taken from my graphics report:
Shadow volumes are implemented with help from the OpenGL stencil buffer. To create the volume, for every triangle that faces the light (dot product between the face’s normal and the light vector is > 0) three edges are added to a list. Duplicate edges are removed from this list. When done, the only edges in the list form a silhouette. These edges are extended to form a quad-based volume. From here, two rendering passes are made. First, with back-face culling on, the depth write disabled (but depth test still enabled), and the stencil operation set to increment. The second rendering pass has front-face culling on, depth write disabled (depth test still enabled), and the stencil operation set to decrement. Now, the full scene is rendered a final time with shadowing done where the stencil value is non-zero.
