User interface design for mere mortals

Last night I started perusing the book "User interface design for mere mortals" to see if I could learn something.

Throughout the book, several interesting side topics caught my attention. These include a history of UI's, paper prototyping (www.paperprototyping.com), help systems (robohelp), and psychological types (Briggs and Myers).

The book also mentioned the Archy interface, which I found quite interesting. Archy led me to Enso, and Enso led me to Gnome Go. I started using Gnome Go last night, and I can't believe I hadn't heard of it before. The perfect complementary tool for someone who is used to tab completing (and recursive searching) in a bash shell and who has recently started using Spotlight in MacOSX for a similar purpose.

After looking into the Go source, I realize I should really get to know some more libraries (Gconf, dbus) and other technologies (Mono, C-sharp).

Domesticated beaver

No, it's not that kind of "beaver".

Today, while riding through the river valley (in Edmonton), I noticed a man crouched down by the side of the river bank, with a beaver standing right beside him. At first I thought maybe it was as stuffed animal or something, but this guy was actually hand feeding this beaver, who was just chillin' on his back legs, munching away.

I stopped and waited for my girlfriend to catch up--and we just looked and watched these two.

There is often a beaver lurking around that part of the river, but I have never seen one so close to people. Eventually we continued on our way, slightly happier after seeing some beaver. On my way back through the river valley (several hours later, after helping my old man paint his house), climbing a hill, I saw a woman standing with her bike on the side of the trail. I thought nothing of it, and continued to pedal by, making sure to avoid eye contact and look in the other direction. And sure enough, in the trees on the river bank, I saw a beaver standing there looking out in the trail (only a couple of feet from the side of it). Surely it was the same beaver as he was maybe 50 feet from where we had seen him earlier. And surely the woman was staring at how unbothered this beaver was by humans, not unlike we were hours before.

I will have to start increasing the outings to this particular part in the valley, as today's events, combined with others (e.g., people walking their pot-belly pig through the trails in the river valley), it seems like a pretty good place to find randomness.

Multi-grid

I recently learned about multi-grid methods and was trying to use them in an optic flow setting. I wasn't getting the speed-up that was suggested by a paper on the subject, so I figured that perhaps my reduction or prolongation operators were wrong. To test their correctness I decided to try and solve some simpler problems: a 1D Poisson problem; a 2D Poisson problem; and a 2D non-linear poison like problem. In all cases I used a Gauss-Siedel relaxation. In all my tests I simply ran a multi-grid solver (w-cycle) and then used only the relaxation (Gauss-Siedel) to solve the problem to the same residual.

For the linear problems (Poisson) I am not convinced that MG is the fastest approach. But in the 1D case, it was possible to get speed-ups of 3.3, 14.2, and 38 for problem sizes of 256, 512, and 1024 respectively.

For the 2D linear problem, on sizes of 64x64, 128x128, and 256x256 the speed-ups were 4.8, 14.6, and 51. I have yet to try and solve one of these sparse problems with a generic sparse linear equation solver, but I think the MG solver would be faster. For example, the 256^2 problem took roughly 3.5 seconds, a 512^2 takes about 18.2, and 1024^2 takes roughly 1 minute. Keep in mind the 1024^2 problem is a 1e6 x 1e6 linear system with a million unknowns.

For the nonlinear 2D problem (which is most similar to my target application) the gains were even more apparent. For problems of size 32x32 the Gauss-Siedel method with frozen coefficients had extremely poor convergence. In the same problem size it was possible to see 1000-fold speed-ups. Since the Gauss-Siedel solver alone was extremely slow, I was not able to get results on any larger systems. The non-linear versions also had some strange behaviour, where the residual of the equation system would actually increase after prolonging the coarse grid solution (this would of course decrease after the pre-smoothing for the next iteration).

Back to the optic flow problem. Confident after seeing the improvements in these toy examples, I went back to the optic flow problem. I think that the prolongation and restriction operators in this case are implemented correctly. I didn't see the speed-ups mentioned in the literature (close to 500 or so vs. a Gauss-Siedel solver); mine were closer to 15 or so. The good news is that a single wcycle gives almost real-time performance (as in the paper), where it is possible to get roughly 1 frame-per-second on 400x300 images.

get_video, keepvid, and youtube videos

keepvid doesn't seem to be working anymore for grabbing videos from youtube. In the past, I needed a video from Metacafe and couldn't find a utility for getting the video, and the source in the page didn't reveal any obvious links.

As a reminder to myself, the tcpdump command is somewhat helpful in this situation:

tcpdump -A -i eth0 -s 10000 | grep -A6 -B6 "GET"

Using the above command (I think the -s 10000 is redundant), it is somewhat easy to find the command to grab a video. With you tube videos (be sure to set the fmt= parameter to whatever you want) and redirect your browser to the www.youtube.com/watch?... page). The tcpdump will show you the GET get_video?video_id... that you need to grab your video. I think with the newer formats, you may need to use the videoplayback?id GETs.

Still need to write a script to process that stuff for me.

perly pie

Thats right, perl "-p -i -e"!

This command is your friend for replacing strings in a batch of documents at once. As I am not a frequent perl user I tend to forget the order syntax for specifying search/replace, but know the rough format contains a "/s" a "/" and a "/g". I tend to try out a quick command line version trial with stdin before going to the full replace. Today I did the test with

perl -p -i -e 's/goodbye/hello/g'

As it worked first try, I then accidentally used the above command in my "find" expression to do my desired replace (e.g., "find ./ perl -p -i -e 's/hello/goodbye/g' {} \;" ). I totally wasn't thinking, as I really wanted to replace occurences of an old host name in the ".svn/entries" files with a new one. Unfortunately, there were actually occurrences of hello in some binary files (I guess I had blender files with objects called hello). Blender then opened these screwed up files without error but containing no objects (the change in length must have 'effed the offsets in the binary). Luckily these were the only files affected and it was easy enough to change. In the future I'll have to make sure to replace the above command with the appropriate search/replace string and a "-name" to find.

OOps.

wxWidgets documentation

Last week I was porting a wxWidget application to the Mac, which shouldn't be all that painful, but I was having trouble with the application opening command line arguments.

Being one of the first GUI programs that used the command line for loading files, I didn't realize that the command arguments (e.g, "open -a myapp.app anargument", don't get passed in through argv/argc). After doing some digging, I turned up a reference for MacOpenFile in the wxPython port. I looked at the current versions documentation (wx 2.8.x) to see if this was something available in the c++ libraries as well. Didn't appear to be on their page (and doesn't come up if you search the site for MacOpenFile). WTF wxDocs?

Anyway, MacOpenFile does exist but just doesn't appear to be documented (in the common docs that is). It is really too bad because I suspect that most people would check wxApp first for alternatives methods to access command line arguments. Instead, you end up wasting time scouring the web for others with similar problems.

I meant to post this right after I had found the solution so I could tag the blog with all the things I had searched for. Unfortunately, I waited more than a week and no longer remember what I had searched.

float cast underflow slow

Today I noticed that some of code that just blended some images was being really slow dependent on some of the coefficients used in the blending. After checking the coefficients for strange values (nans/infs), for which there were none, it was still slow. The problem was only appearing in one function used for blending (some integer code that used floating coefficients that were casted from doubles). The problem didn't appear when strictly using floating point arithmetic. Turns out it is due to slow casting from double to float when there is underflow.

Some timing results for casting from double to double (d), double to float (f), double to integer (i), for test program, included below:

Without optimization
time for d (init=1e-30) 0.013476
time for f (init=1e-30) 0.012164
time for i (init=1e-30) 0.016217
time for d (init=1e-50) 0.019088
time for f (init=1e-50) 0.229608
time for i (init=1e-50) 0.019010

Without optimization (-O3)
time for d (init=1e-30) 0.005358
time for f (init=1e-30) 0.004038
time for i (init=1e-30) 0.003713
time for d (init=1e-50) 0.004566
time for f (init=1e-50) 0.135538
time for i (init=1e-50) 0.003527

You can see the floating point cast is something like 30x slower for the value of 1e-50 (where there is underflow) as opposed to the case of 1e-30 where there is no underflow.

Try the code for yourself.

#!/bin/sh

cat <<EOF > _f_.cc
#include 
#include 
#include 
#include 
#include 

template 
void test(int m, double init){
  double * v = new double[m];
  T * f = new T[m];
  struct timeval tv;
  gettimeofday(&tv, 0);

  for(int its=0; its< 20; its++){
    v[0] = init;
    double * vptr = v;
    for(int i=0; i< m; i++){
      *(vptr++) = v[0];
      f[i] = ((T)v[i]);
    }
  }
  struct timeval tva, el;
  gettimeofday(&tva, 0);
  timersub(&tva, &tv, &el);
  printf("time for %s (init=%g) %lf\n", typeid(T).name(), init, double(el.tv_sec) + double(el.tv_usec)/1e6);
  delete [] f;
  delete [] v;
}

int main(int ac, char * av[]){
  int m = 100000;

  test(m, 1e-30);
  test(m, 1e-30);
  test(m, 1e-30);
  
  test(m, 1e-50);
  test(m, 1e-50);
  test(m, 1e-50);
  return 0;
}
EOF

echo "Without optimization"
g++ _f_.cc -lm -o _f_
./_f_

echo "Without optimization (-O)"
g++ _f_.cc -lm -o _f_ -O
./_f_

echo "Without optimization (-O3)"
g++ _f_.cc -lm -o _f_ -O3
./_f_

echo "Without optimization (-O3)"
g++ _f_.cc -lm -o _f_ -O3 -mmmx -msse
./_f_

rm _f_.cc _f_