Donnie’s Blog

Normally I don’t like to write anything on my blog if I don’t really understand what I’m writing about, but I have an interesting problem to solve, and I figured that I might as well state the problem before diving in and trying to solve it. That way, if any of my smart friends have any ideas then I can find out what they are, and if not, at least I will have clarified the requirements in my own mind.
(more…)

I was pleased to note that South has recently been recommended as a good solution to the whole problem of database schema migration when using Django. I have been using South in csman for over a month now, and it has just been great. I still back up the database before applying a schema-migration to the production system (no sense in being a complete idiot), but so far every time I’ve had to make a schema change, the process has been completely flawless.

So, I can definitely recommend South too!

In general, it’s still very wise to try to change schemas as infrequently as possible, so I tend to batch up my changes, but South has almost completely removed my worries about making schema changes in my Django projects. It’s a great tool.

Using Django for csman has mostly been a positive experience, although there have been a few wrinkles along the way. I just ran into another one today, which is quite frustrating — one of my pages takes about ten seconds to render, and nobody wants to wait ten seconds! Fortunately it’s for the teachers and not the students; if it were for the students, there would be no end of whining!

This page includes a LOT of database queries, almost to the point where I should be embarrassed, except for the fact that I hacked this thing together as quickly as possible, so actually I’m proud that it has as many features as it has. But for 130 students and around 15 assignments, the server-side code issues around 2000 queries, and you don’t need to be a genius to know that this just won’t be very fast.

But surprisingly enough, only about half the time is spent in database land; the rest of the time is spent rendering the Django template. I was quite surprised by this! I thought it would be much faster than that, but evidently not. There are three nested loops in the template, iterating over a large amount of data, so in retrospect it’s no surprise, but an hour ago I was sure that I needed to optimize the database interactions, not the template rendering. Now I see that the database code is only half of the problem.

All I did to find this was to add a couple of print statements around my view code to see how much time was actually spent in the database queries. I’m glad I did; I would have been completely befuddled, otherwise. It just goes to prove that old bit of software engineering wisdom, that if you try to optimize a system before you’ve actually profiled it, you probably won’t fix the real bottleneck.

I think I can fix this issue by creating a custom template-tag that will move some of the rendering into Python code, instead of being run in the template engine. The more I can incorporate into Python, the better off I’ll probably be. This may also help with the database side of things, because if I have clever template tags, then I can do less preparation with the data, and therefore fetch larger amounts of data from the back-end in one shot.

I just wrote up a new programming note about how to do syntax-highlighted diff output using Pygments and Python’s difflib library, in a Django website. It’s available here.

I implemented this feature for csman, a homework submission and grading system I have been implementing for the last couple of months, to use with the CS1, CS4, and CS11 classes that Mike Vanier and I teach. All of these classes have a similar homework-submission model, much like the model in real software projects: you write the code, and if it’s not good enough, you have to fix it.

Of course, grading redos is always a little annoying, so if you have a tool that lets you view a diff of the old submission and the new submission, it becomes very simple to see if the student actually fixed everything you told them to fix. (Sometimes they don’t. It’s very annoying when this happens.)

Anyway, it’s a cool little feature, to be able to see syntax-highlighted diff output on csman, but it definitely still needs a lot of work. The main issue is that frequently the files are too wide to display side-by-side, unless you happen to have a nice large monitor like I do. So, the problem really requires the effective use of scrollbars, both horizontal scrollbars to allow the diff-output to be visible in a smaller window, and also vertical scrollbars since otherwise those horizontal scrollbars are going to be waaayy at the bottom of your web page.

So, I have some work to do on that problem, but for now I’ll stick with what I have. It does the job, and one day when I learn more client-side JavaScript, maybe I’ll fix that kind of stuff up to be more snazzy.

Lately I have been tinkering with a simple little 3D graphics program in my spare time. To support my various graphics and math projects I have put together a simple C++ math library including matrices, vectors, and the like. My matrices are stored in row-major order, like most matrices in C/C++ programs, but OpenGL uses column-major order. “Simple,” I think, “I just need to transpose my orientation matrices before passing them to OpenGL!”

But it just wouldn’t work. See if you can figure out why:

  template<class T, int dim> class SquareMatrix {
    ...
    /** Transpose the matrix. **/
    void transpose() {
      for (int r = 0; r < dim; r++) {
        for (int c = 0; c < dim; c++) {
          // Diagonal elements don't need transposing!
          if (r == c) continue;

          T tmp = getElem(r, c);
          setElem(r, c, getElem(c, r));
          setElem(c, r, tmp);
        }
      }
    }
    ...
  };

Last night I was looking for interesting programming problems, and I came across this page about the Möbius Function. It’s a pretty simple idea, although I have no idea how August Möbius came up with the idea in the first place.

Given a positive integer n, the Möbius function μ(n) returns:

• 0 if the number is a multiple of a square
• -1 if the number has an odd number of distinct prime factors
• 1 if the number has an even number of distinct prime factors

The n = 1 case is a special case; μ(1) is defined to return 1.

I thought this would be a fun little problem to play around with; it’s all about generating the list of prime factors for the input value. A number is a multiple of a square if it has any duplicate prime factors; for example, 12 = 2 × 2 × 3, so it is a multiple of a square, and μ(12) = 0.

An interesting little related problem is to find runs of numbers for which μ(n) is 0. For example, the first run of three multiples of squares is {48, 49, 50}. The first run of six square-multiples starts at 22020.

So, I wrote a Scheme program to implement the Möbius Function, and to find runs of square-multiples; here it is if you want to take a look! It was pretty fun, although the program starts to get annoyingly slow when hunting for runs of 7 or 8 square-multiples. I would have to upgrade to a much faster language if I were going to do something like that. Or perhaps there’s something I can improve in my implementation…

The summer break is finally here, and I for one am very excited about this summer. This year I have a SURF student helping me out with the implementation of my “educational database system” in Java. The working name is currently NanoDB, although I am certainly open to other suggestions.

(more…)

A few days ago there was this Slashdot article about a serious Linux kernel security hole. Since I was running a version of Linux that had the issue, I thought I had better patch it on my server ASAP.

My machine basically has nobody on it, so I am really not worried about somebody using the exploit directly. But, I do have a number of network services, like my mailserver, webserver, SSH server - and if any of those has a vulnerability, I sure don’t want somebody using that to get root access on my box!

So, last night I manually patched my kernel source, rebuilt my kernel, and rebooted the machine. It was exciting and nerve-wracking; since it’s been so long since I built a kernel myself (2000? 2001? It was at DALi I am sure…), I didn’t know if I would get it right! Then there’s the fact that I am running RAID1 on my boot partition, and I wasn’t sure how the kernel update would go with that.

But, everything went fine. The machine rebooted fine, and when I tried the exploit on the patched system, nothing bad happened. All my services started back up without a hitch.

It was kind of exciting!

Saturday, November 10 was the ACM regional programming contest. Caltech won yet again… Go Caltech!

This year was definitely one of the least intentional wins. There was little interest in an ACM programming contest track for CS11, so we just didn’t have one. Then, two weeks before the contest was scheduled, some all-star students expressed interest in going, so we arranged it. And they won! Caltech rocks.

Anyway. Hopefully we won’t do it this way ever again. Next year I want to really try to drum up interest in the contest and actually get 3 or 4 teams out there. But at least we were able to land the win this year!

I just added a new programming note about a project I have been tinkering with lately. The project is a Buddhabrot image generator. Right now I am still working on generating some images so I will add those tomorrow, but tonight I wrote up a page about some of the interesting things I learned from this little project. So, check it out. Hopefully you will find it interesting too.