Coding Gorilla

Visual Studio 2010 has some interesting new features, one of which is parallel programming. This simple example, written in C# and F#, tests the difference between serial and parallel computations of Fibonacci numbers. The example uses the System.Threading.Tasks.Parallel.For method. Indeed, there is about a 4-fold improvement on my quad-core multiprocessor for long computations but not for short computations. There is a trade-off between the size of the computation versus the overhead to create, schedule, and synchronize threads.
Continue reading “Parallel programming with .NET”

When I first learned that Google released the source code for their new operating system, I was determined to try it out. Unless you have been living in the Styx for the last year, you must have read that it described by many as a revolution in operating systems (1, 2), and that it will spell the end to Microsoft’s dominance in operating system software (3). So, when Google opened up the source code to developers (4), I decided to download the code, build the operating system, and give it a spin. In particular, I was interested in how fast it would boot because that was one of the most important design considerations.
Continue reading “A peek at the Google Chromium OS”

In the past, there used to be the Microsoft PowerToys for Windows XP which would add in the capability of invoking a Cmd shell on a directory through Windows Explorer.  You could right click on the diretory, and it would have a pop-up item available to do just that.  But, PowerToys is not supported for Vista.  Instead, Microsoft added the capability directly into the OS.  To execute a Cmd shell on a directory, hold the SHIFT key while doing a mouse right click, and select “Open Command Window Here”.

Unfortunately, Cmd is not my favorite shell–if you can even call it that.  I like using the Bourne-Again Shell (bash), which is available with the Cygwin package (http://cygwin.com).  Here is a handy little Regedit script I developed which seems to do the trick.

Windows Registry Editor Version 5.00
[HKEY_LOCAL_MACHINE\SOFTWARE\Classes\Folder\shell\Bash Prompt]
@="Bash Prompt"
[HKEY_LOCAL_MACHINE\SOFTWARE\Classes\Folder\shell\Bash Prompt\command]
@="cmd /k \"pushd %1 && set CHERE_INVOKING=y && c:\\cygwin\\bin\\bash.exe -il\""

NOTE: An updated version of this registry hack which uses mintty is available at http://codinggorilla.com/code/cs-mintty.reg.

This post is about computing the nearest common ancestor.  It is the result of a month or so of reading papers and implementation.  Although there has been a lot of research into the problem, there are no implementations online of the two main algorithms presented.  Worse, examples in the papers are practically useless.  For example, the Alstrup-Gavoille-Kaplan-Rauhe (AGKR) algorithm was first described in a technical report in August 2001, but it did not contain an example.  In 2002, it was presented at a conference but again it did not contain an example.  Finally, in 2004, it was published in a peer-reviewed journal and contained an example, albeit still incomplete.
Continue reading “Computing the nearest common ancestor”

I wrote a program in the last day to determine the fastest method of seven implementations that I found over the Web that solves the operation “floor(log2(int))”. This operation takes an integer and determines the position of the topmost bit that is one. So, for example floor(log2(0x2)) would be 1, floor(log2(0x52)) would be 6. This operation is important in finding the nearest common ancestor of a tree (more on this in a book that I am writing).
Continue reading “Bit hacks to compute floor(log2(int))”

Feeling bored and looking for some fun, I wrote a Netgear router monitor program. This is what programmers do.  I was interested in seeing what websites were accessed through the router at my home.  While there is a log available via the router, the buffer in a router are notoriously small and data that are only a few minutes old are lost.  This tool fixes that by polling the router every few seconds.  The tool looks for router that is a model WGR614v6, but other Netgear routers may work.  For other routers, I would expect a change to the code to parse the output.
Continue reading “Netgear router monitor”

Finally, I seem to be making some headway into graph drawing.  Over ten years ago, I had a similar problem.  In 1999, I worked for a company that sold a UML modeling tool, but I did not like the way it worked.  I tried to convince management that it needed changes to make it more useful,  but they brushed me off. So, I decided to try to write a UML modeling tool on my own.   Moreover, I wanted to expand my knowledge of computer science to include graph drawing, which is the field in computer science that tries to find two- or three-dimensional representations for graphs.   Unfortunately, I never succeeded in writing the tool at that time. I did not have enough time to learn graph  drawing because of a job change.  I spent several weeks trying to learn the subject,  but I was not able to grasp even the most basic algorithms.
Continue reading “Tree graph drawing”

Call me old fashioned for working on compiler technologies. But recently, I was interested in displaying a parse tree generated by a parser that I am writing.  For several weeks I read some well-known papers on tree layout, then implemented the algorithms described in these papers.  To my chagrin, this took a lot longer than I expected.  Am I losing it as a software engineer?
Continue reading “Expecting more”