Physics Halloween costume ideas

Real time view of where Wikipedia edits are coming from

In one of my classes this semester we have had a sequence of assignments dealing with a program that finds strings in files (a simpler “grep”). Initially, the program just searched files. For the second assignment additional options were added and we had to descend into directories recursively. Recursive directory descent proves to be nontrivial because when you follow symbolic links you may enter a directory loop. This would cause infinite recursion, which is clearly not good.

The solution is to keep track of your position on a stack. A stack is a natural data structure for any recursive process. For example, when functions are called recursively data and positions are kept track of on the system stack. Each directory on a POSIX system is uniquely identified by its inode number and its device number (obtained from a stat() call). I created a linked list of nodes with inode and device numbers as well as the full file path for error reporting. To detect directory loops, my program pushed onto the directory stack each time a new directory is encountered and a recursive call is made. When the recursive function returned, the directory stack was popped off. Each time push is called the stack is searched all the way to the bottom, looking for a node with the same inode,device pair. If one is found the stack can be printed and the descent aborted.

The third assignment was to modify this program to search directories in a multithreaded manner using pthreads. Each time a directory is encountered, a thread is created to process it (up to certain limits after which the directory is processed in line). Clearly this presents a problem for the directory stack data structure. The stack needs to be maintained as threads are launched so loops can be prevented. However, clearly the threads cannot be manipulating a single stack - nodes would be interleaved and messed up.

One way to deal with this is to copy the stack each time you launch a thread, then pass the copy to the thread. When the thread is finished it free()s the copy. This satisfies the problem. The stacks do not need to be identical, they just need to converge at some point near the bottom. These stack copies will also get progressively larger as you move deeper into a directory tree. Altogether, it involves a lot of allocating, copying, and deallocating, as well as additional memory usage.

Better way: Branching stack. A branching stack is similar to a standard stack, having operations push() and pop(). The branching stack introduces a new operation called branch(). This operation simply creates a new top-of-stack pointer and points it to the same place. This yields a lightweight copy of the stack. Each copy can be pushed onto and this will result in two different stacks which converge at the branch point. The copy shouldn’t pop off below the branch point - this would corrupt the shared portion of the stack. But our application dictates that this won’t happen because there will be an equal number of pushes and pops. This is a beautiful solution and it doesn’t even require modifying the node structure! all memory below each branch point is shared.

There is still an issue with regards to threads. What happens if a lightweight copy is created, passed to a newly created thread, then the original thread finishes processing the directory and goes to pop off the stack? The memory at the point will be freed(), but there might still be other threads above this node on the stack! If the memory is freed they will not be able to check for loops or print them out. The solution is to add a reference count to each node in the stack, initially zero. The reference count at the top of the stack is incremented each time a branch is performed. When a thread is done with the branch of the directory stack (and at the top of the branch section), it performs a join() operation which decrements the reference count at the tops of the branch stack.

Now, when a pop() operation is performed the reference count is checked. If it is nonzero, it blocks with a conditional wait. When a join() operation reduces the reference count to zero, it signals the waiting pop() operation which can continue. Obviously appropriate synchronization is also needed. Still, this is much better than the original solution. The memory usage is much smaller and the working set is more likely to fit in cache. Furthermore, branching is an extremely simple operation, simply copying a pointer and incrementing a counter. Similarly for joining.

This version does introduce blocking in the pop() operation. But for the most part this does not affect performance - the parallel gain is from processing a few directories in parallel not launching hundreds of threads which is what happens if you do not limit a version that copies. And, blocking threads consume no CPU. Even when processing deep directory trees, my program’s memory usage rarely climbs above 1MB.

Below is a visualization of this data structure after a branch.

I took some nice photos of people playing Ultimate Frisbee earlier this afternoon. The light was just right for most of it. I shot with fairly wide apertures and very fast shutter speeds. Shooting with the 85mm prime was nice, but the best pics came only when the action was close. Doing this kind of shooting has reinforced my desire for the Canon EF 70-200 f/2.8L IS which would provides the best focal lengths, zoom, a wide aperture, and IS. The image below was shot using ISO 100, f/2.2, with a 1/3200 exposure (aperture priority mode).

View all ultimate photos.

This morning I caught some photos of Katz giving herself a tongue bath. She is very cute, and I swear she was posing for the camera. These are all shots with my EF 85mm lens, with lighting using the Canon 580EX II flash with the Demb Flash Diffuser. The Demb basically combines a variable tilt bounce card (which can also tilt completely down for a ceiling bounce only) and a piece of plastic that attaches to the front with velcro and can be easily removed or repositioned. Most of these were shot with the reflector tilted completely down, giving mostly ceiling light with the plastic diffuser catching a bit of light and throwing it forward to fill in shadows.

Unlike the built in bounce card on the 580EX II, the Demb Diffuser can be placed with the short edge of the flash facing forward - this allows you to simply tilt the flash head to take vertical (portrait) orientation photos with the flash. The 580EX II is a serious workhorse.. I just kept shooting again and again and the flash recycles very fast. I use rechargeable NiMH batteries which work quite well, in fact, the batteries had not been recharged since the last time I used them and they were fine (a bit warm when I took them out at the end). With the Demb diffuser stealing some of the flash power, the flash head does get quite warm as well after heavy use! It is a serious unit.

Check out the barbs on her tongue. It makes for a comb-like surface ideal for grooming.

Larger sizes starting here and going forward. Check out some full size originals.

The week of November 12th I will be heading to Portland, Oregon for the DLNA Plugfest. This marks a new milestone as the first time I’ve ever traveled on a business trip (sadly, I will not be traveling business class :). The plugfest is a week long event where vendors who are members of DLNA will get a chance to test their devices for interoperability, as well as test with out product which is a test suite for the DLNA devices guidelines. I was also invited to the previous plugfest in Tampere, Finland, but alas I was in the UK for my honeymoon during the Finland Plugfest.

Unfortunately, I’ll be missing some class. But it works out well since that week is a short one due to a UNH Holiday and avoids scheduled tests. Plus, there is a decent chance I may be able to attend a plugfest in the spring as well, in either Europe (currently undecided between France and Spain) or Japan. Pretty sweet!

Last weekend Gennie introduced me to Scrabulous, a facebook app for networked scrabble play. On Monday night I realized you could select French as a language and started a game with Gennie. Well, I lost.. But it was quite close and the game ended when she had a q and I had a w and we couldn’t find any place to put them.

Much fun.

For today’s bike ride I took Wednesday Hill Road into the center of Lee, NH then back via Lee Hook Road and NH 155. This was a very intense 14 mile ride! Wednesday Hill Road starts out with gradual rolling hills. About half way down there is an elk farm with elk lounging out and a small vineyard.. after this point is the first short but very steep hill. From there on out until the center of Lee it is just up and down and up and down, all very steep.

View Larger Map

All about CPU Caching.

Lately I have been trying to do my ten mile bike ride route on Mondays and Wednesdays after I get out of class at 16:00. Today, I had to go to the ATM and the Farmer’s Market (in sequence :) so I got home a bit later - with the fading light I decided to do a shorter but more intense ride. The total distance was around 5.6 miles. It felt quite good. My legs have definitely gained strength and hills are a lot easier. Between that and the shorter distance of this ride the final hill was easily conquered and I didn’t even feel tired at the crest. Wahoo!

View Larger Map