Searching for Better Software

Free Software Project Hosting Comparison

2012-01-31T01:11:00.000-03:30

There are three leading free software project hosting services. These services lead in number of hosted projects by a factor of 10 over their competition.

Name	Established	Projects
GitHub	2008	885, 000
Google Code	2006	250, 000
SourceForge	1999	432, 000

http://en.wikipedia.org/wiki/Comparison_of_open_source_software_hosting_facilities

For a free service like this, popularity and longevity are a good first approximation of which you should choose. A popular long lived service is likely to:

continue to last (an important consideration)
have good features and usability (that is why they are popular, hopefully)

However, sometimes first approximations are wrong. When I investigated the available services I found that all three of the above leaders meet my basic requirements, most importantly they all have git interfaces. However, there was a fourth service with an important differentiator: free private repositories. Most software project hosting services support private repositories for a fee, however BitBucket by Atlassian (the JIRA guys), supports private repositories with limited contributors. This is a very attractive option because ideally I’d like to do my experimentation in private.

To compare these 4 services my plan is to host an existing small project at each of them. I’ll let you know what I find out.

Do you have a favourite software project hosting service that I should be considering? What is so great about it?

Online Education

2012-01-24T22:37:00.000-03:30

Watch this amazing video of Sebastian Thrun talking about his experiences with his recent ai-class experiment and his next education project.

Wasted Hardware

2011-07-20T11:31:00.000-02:30

My laptop has 8GB of RAM, or approximately 150,000 novels worth.[1] It has 2 CPUs executing a total of 10^10 instructions per second, or enough instructions to make my cursor blink for 150 years.[2] Most of the time Windows Task Manager reports CPU utilization of less than 5% and memory utilization of less than 40%.

Why is my computer so lazy? Shouldn't it be doing more to help me? Wikipedia would fit in a GB of RAM or so, why do I have to look stuff up? Am I the only person depressed by the Task Manager?

[1] Assume compressed ASCII English text.
[2] Assume a sequence of on/off instructions executed 2 per second.

Technical Writing

2010-05-10T13:36:00.000-02:30

Writing well is hard. It is easy to write about technical topics in an inscrutable, boring, dry way. The ability to write about technical topics in a way that is clear and holds interest is a rare gift. Here are two recent examples of good writing I've seen:

Brian Hayes, The Easiest Hard Problem. Takes a technical paper on a topic that even the experts find tough and recasts it as something that everyone can understand and find interesting.

Alexey Radul, Propagation Networks: A Flexible and
Expressive Substrate for Computation. A Ph.D. dissertation on a new programming model. This one is not for the layman as the previous example, but you certainly do not need to be a Ph.D. candidate to understand or enjoy it.

Some US Senators Chastise Facebook

2010-04-28T09:40:00.000-02:30

Canada has had some success getting Facebook to respect their customers' privacy, now some US senators are requesting change. Facebook will be an ongoing problem for people who care about their privacy, because Mark Zuckerberg obviously doesn't.

McAfee Pays Home Users for Damages

2010-04-26T12:59:00.002-02:30

McAfee is offering to pay for damages for home users affected by the bad update they released recently.

Static Analysis

2010-04-22T14:37:00.000-02:30

As my wife calls them, there's a "how we done it good" article on static code analysis tools over at Dr. Dobb's.

Government Services

2010-04-21T10:03:00.002-02:30

This CBC article highlights some of the points from Chapter 1 of of the Auditor General's Spring 2010 Report. I still have to read the report, but according to the CBC, old hardware and software are putting the reliability of government services at risk. So they have a legacy problem, who hasn't?

Fuzz Testing

2010-04-06T09:55:00.000-02:30

Fuzz testing is used to test program interfaces for graceful handling of unexpected data. The interface is typically a data file format or network interface. In this article Microsoft tests Office file formats using a botnet. The article compares it to seti@home, but I doubt finding a bug in Office is as unlikely as finding intelligent signals from space.

Rogue Antivirus

2010-03-29T10:32:00.000-02:30

A computer of a friend of mine was infected by the rogue antivirus program, "Security Tool" over the weekend. This program hijacks the computer preventing it from running other programs, in particular it prevents the running of the process manager or the antivirus program. It masquerades as a legitimate antivirus program telling you the computer has X, Y or Z virus. And here is where the SCAM comes in, it then tells you to enter your credit card information to upgrade to the professional version so that it can remove the detected viruses.

Luckily this was not a hard problem to fix. I rebooted with a Knoppix Live CD, found the shortcut in the "Startup" folder, deleted the evil application, and rebooted back to Windows.

What can be done about this kind of problem?

Software Executes on Real Devices, not Abstract Ones

2010-03-14T12:47:00.000-02:30

This article, by a Mars Pathfinder engineer, about the recent Toyota problems has a great example of when testing the impossible paid off.

During Pathfinder development one particular test tested a logical impossibility; the return value of a function that always returned an even number was tested for evenness. Seemingly beyond reason, one time the test failed. It was later determined that an interrupt had reset some register flags so that when the code resumed it calculated the wrong thing. The lesson here is that software executes on real-world machines, not abstract ones, anything can happen.

Botnet Badguys Arrested

2010-03-03T11:21:00.001-03:30

Spanish police are reporting the arrest of three people responsible for the 13 million node Mariposa botnet. Evidence in the case includes personal data from over 8 hundred thousand people.

Defense Intelligence has a lot of interesting reading on this botnet.

Anybody Know what Time it is?

2010-03-02T11:05:00.000-03:30

Leap year calculations are simple and correct libraries exist. Why, then, is the Sony PlayStation 3 exhibiting a leap year bug?

Writing Security into the Contract

2010-02-19T16:53:00.001-03:30

The Application Security Procurement Language from the SANS Institute aims to enable buyers of custom software to make code writers responsible for checking the code and for fixing security flaws before software is delivered. The introduction includes a link to CWE's Top 25 Most Dangerous Programming Errors for 2010.

Open-PC

2010-01-20T10:47:00.000-03:30

A bit off topic, but I thought this looked interesting. The Open-PC group are specing PCs around supported and open hardware. In this context "supported and open" means there is enough documentation to write a Linux driver.

German government warns against using Microsoft Internet Explorer

2010-01-18T11:32:00.001-03:30

The government of the largest (most important) software market in Western Europe, Germany, is advising its citizens against using Microsoft Internet Explorer (MS IE). The reason has to do with the recent news of Google China being the target of corporate espionage allegedly by the Chinese government.

Clickjacking

2009-12-24T10:32:00.000-03:30

Clickjacking is yet another way to be attacked on the web.

On-line Security

2009-12-17T16:58:00.000-03:30

MessageLabs Intelligence: 2009 Annual Security Report is a very long report about on-line security in 2009. It is mostly concerned with the scope of the problem, but it also describes the most popular types of attack in a basic way.

Automated to Death

2009-12-17T11:24:00.000-03:30

Automated to Death in IEEE Spectrum is not strictly about seeking better software in the sense that I normally think about it, but it is a very interesting read.

Commercial Software Should Be Judged by the Same Standards as Other Commercial Products

2009-12-16T17:54:00.000-03:30

This Slashdot story links to an article containing the following quote from Prof. Tanenbaum:

“I think the idea that commercial software be judged by the same standards as other commercial products is not so crazy,” he says. “Cars, TVs, and telephones are all expected to work, and they are full of software. Why not standalone software? I think such legislation would put software makers under pressure to first make sure their software works, then worry about more bells and whistles.”

Hear, hear.

Lisp in C

2008-09-30T17:36:00.004-02:30

As an exercise, I implemented Paul Graham's, "The Roots of Lisp" in C. The result is available on Google Code.

Two comments I've received so far are:

Why C? Write in lisp if you want to learn lisp.
Why not go the other way, a C interpreter in lisp?

Of course these are both possible, and certainly, the best way to learn a language is to use it.

However, writing lisp interpreters in lisp hides a few details. For example, garbage collection does not even need mentioning because the underlying lisp handles it. Another example, is the interpretation of truth, a lisp implementation would not have to explicitly map the interpreted lisp's truth to the implementation languages truth. Finally, cond written in terms of cond does not have to decide what to return if none of the cases are true, it can be implicit. And there are other examples. By writing the interpreter in C, some of these details that I might have missed were made obvious.

Writing a C interpreter in lisp sounds like a fun project, but it also sounds like a bigger project. Maybe I'll take that on next, maybe I'll start by writing, "The Roots of C."

vi

2006-10-10T03:12:00.000-02:30

My vote in the great vi versus emacs debate:

I'll leave someone else to do: For everything else there's emacs.

PS. If you would like this graphic as encapsulated postscript, perhaps to print on a T-shirt, drop me a line.

Nelder-Mead Downhill Simplex Method

2006-10-10T03:02:00.000-02:30

A stylistic review the Nelder-Mead Downhill Simplex Method as presented in section 10.4 of "Numerical Recipes in C," 2nd ed., 2002.

Studying the code presented in Numerical Recipes did reveal a few things. First of all, the good news, is that I did not find any functional bugs. As near as I can tell, the algorithm works as advertised.

However, I still found several points to complain about. Since the code was designed this way, I won't mention the fact that their array indexing starts at 1, which will confuse all native C programmers. (Ok, I guess I will mention it. Tsk, tsk.) (Not that C programmers don't deserve what they get anyway.) Instead, I will talk about some of the other things I saw.

Sorting

The first problem is the use of the comma operator. Happily, they do not get it wrong the way most programmers get it wrong. That is, at least it works the way the author intended it to. In this case the author got it wrong by using it when it wasn't needed. (It is almost never needed.) The code I'm talking about is the code to determine ilo, ihi and inhi. This section contains several weaknesses, so I'll repeat it here (with my own spacing).

 1  /*
 2          First we must determine which point is the
 3          highest (worst), next-highest, and lowest
 4          (best), by looping over the points in the
 5          simplex.
 6  */
 7  ilo = 1;
 8  ihi = y[1] > y[2] ? ( inhi = 2 , 1 ) : ( inhi = 1 , 2 );
 9  for ( i = 1; i <= mpts; i++ ) {
10          if ( y[i] <= y[ilo] ) ilo = i;
11          if ( y[i] > y[ihi] ) {
12                  inhi = ihi;
13                  ihi = i;
14          }
15          else if ( y[i] > y[inhi] && i != ihi ) inhi = i;
16  }

First, note that mpts is guaranteed to be at least 2 since we require the objective function to take at least one argument, otherwise what is the point? Therefore, since indexing starts at 1 (yech!), y[1] and y[2] are valid.

On line 8, use of the ternary operator and the comma operators ensure that after initialization, y[ihi] >= y[inhi]. However, this effort turns out to be unnecessary because the subsequent for-loop is sufficient to make sure that the indices have the correct values. If the loop started at i = 2, then it would matter, but it doesn't, so it doesn't. What does matter, and which should be documented, is that ihi != inhi. Because of the simplex algorithm design this matters later on, and if it is not enforced by the initialization, the loop is not guaranteed to straighten it out, consider mpts == 2 && y[1] == y[2]. Therefore, it makes sense to simply write inhi = 1; ihi = 2; and let the for-loop sort it out.

Ignoring the silly indexing, the only change on line 9 is that i++ should be ++i. I can hear your shock from here. :) There is a very strong argument against this change, and that is that C programmers are used to writing it this way. Writing anything else means that native C programmers have to think about it, and it is obviously not worth thinking about (in C). I have two arguments for making this change. The first is that, as a programmer, you should say what you mean. If you mean increment i, then write ++i. If you mean copy i, increment i and get back the copy of i, then write i++. The second reason, related to the first, is that in C++ these two operations can be wildly different because they can be user-defined. This prevents the compiler from replacing one form with the other if it detects the return value is not used because it can be hard to determine if there may be side-effects that will be lost. The C compiler does not have this problem because it knows exactly what the increment operators do. That is, because i++ does more work, there may be an inefficiency found in C++ not found in C because the C++ compiler may not be able to easily call ++i instead. But the main reason is that you should say what you mean.

Line 10 should be y[i] < y[ilo] rather than y[i] <= y[ilo]. This is simply because there is no point in moving ilo unless the new point is actually lower. And again, in C++ there could be an efficiency gain. Imagine if y were an array of type complex and that these operators were designed to compare magnitudes. Then operator<=() might be equivalent to y[i] < y[ilo] || y[i] == y[ilo], where both < and == result in function calls that each calculate magnitudes for y[i] and y[ilo]. The result being that similar work is done twice.

Line 11 should be else if ( y[ihi] < y[i] ). I changed the ordering and used < instead of > for reasons related to the discussion above. In C++ it is conventional to implement < and == and to implement all other operators in terms of them, unless there is a good reason not to. Therefore, it is safer, from an efficiency point of view, to restrict which operators you use. The reason for the else is maybe even more subtle. It turns out that you can show by induction that it is only necessary to execute one of these if conditions, if any, on each pass. Therefore, the else gives us a slight efficiency gain. It can also be shown that it reduces the cyclomatic complexity of the for-loop body from 6 to 4.

The final change, on line 15, is to use < rather than >, for reasons already discussed.

The best changes from a C point of view were the initialisation of ihi and inhi, a change from <= to <, and the introduction of an else. From a C++ point of view, the changes involved more careful choice of operators. For the code as given, it probably does not matter, however you want to have good habits.

I should point out that searching and sorting algorithms are notoriously hard to get exactly right. In fact, there are likely still flaws and points that could be debated.

Reflecting the High Point

Read the comments on lines 3 and 9 in the following block of code carefully and compare them to the if-conditions that they follow.

 1  ytry = amotry( p, y, psum, ndim, funk, ihi, -1.0 );
 2  if ( ytry <= y[ilo] )
 3          /*
 4                  Gives a result better than the best point, so try an
 5                  additional extrapolation by a factor 2.
 6          */
 7          ytry = amotry( p, y, psum, ndim, funk, ihi, 2.0 );
 8  else if ( ytry >= y[inhi] ) {
 9          /*
10                  The reflected point is worse than the second-highest, so
11                  look for an intermediate lower point, i.e., do a
12                  one-dimensional contraction.
13          */
14          ysave = y[ihi];
15          ytry = amotry( p, y, psum, ndim, funk, ihi, 0.5 );
16          if ( ytry >= ysave ) {
17                  /*
18                          Can't seem to get rid of that high point. Better
19                          contract around the lowest (best) point.
20                  */

In both cases, the comment (or maybe the code) is wrong. So far my testing suggests that the code is correct and it is the comments that are wrong. This is a little unusual, it is usually easier to get the comments right and the code wrong. Incorrect comments usually indicate code that has been changed by someone who did not think to update the comments. I suppose I prefer incorrect comments over incorrect code, but I think I also prefer missing comments over incorrect comments. Incorrect comments confuse maintenance programmers because it is hard to know whether the documented behaviour or the coded behaviour is prefered. Incorrect comments are also bad because programmers who only read the comments will expect the code to behave according to the comments and may miss the bug in the associated code. TrollTech seems to be very good at dealing with this issue. It appears that they have a policy whereby the documentaton is always correct. If code deviates from the comments, the code is re-written to match the comment.

In this case the comments make stronger statements than the code. The comments use the words better than and worse than, however the code only says <= and >= which are better translated as better than or the same as and worse than or the same as. The point in the first case is that the simplex reflection appears to be a move in the right direction, so move farther. The point in the second case is that the simplex reflection did not move the high point below the next-highest point, so if we stop there we are fiddling with the same point next time around.

In fact, by re-writing the documentation so that it is clearer that the goal is to move the highest point below the next-highest point in order to ensure progress, we can also see a slight algorithmic improvement in the code. Line 14 records the old value of y[ihi] so that it can be compared to the new value returned by amotry(). This is not necessary because what we really want to compare to is y[inhi] as we did in the previous if-condition. Therefore, ysave can be removed from the code. This change simplifies the code and makes it a little more efficient.

Contracting about the Low Point

The final change I'll talk about involves re-using a variable for a purpose other than that for which it was intended, and doing so unnecessarily. Consider:

 1  for ( j = 1; j <= ndim; j++ )
 2          p[i][j] = psum[j] = 0.5 * ( p[i][j] + p[ilo][j] );
 3  y[i] = (*funk)(psum);

First, there is the j++ which I've commented on before. Second, I do not think it is required to dereference the function pointer, funk in order to call it, but it might be. But the main problem is the use of psum.

Without more context, this looks reasonable. What if I told you that psum was not used again until it is re-calculated a few lines later? In this case, I assume psum is being used because the author did not want to write y[i] = funk( p[i] ), but I do not see why not, and is it worth the cost of the extra assignments? More to the point, is it worth the confusion to the maintenance programmer who looks at line 3 and wonders why the objective function is being called with the simplex centroid vector, rather than one of the rows of the simplex as is usual? I think these three lines of code are simply evil.

Summary

The previous three sections raise what many people would consider to be nit-picky points. Afterall, the code appears to work. Even the changes that might impact efficiency will only make a small difference. From that point of view, the points are nit-picky. People will also say that by proposing nit-picky changes I risk breaking code that works. That is also true.

I personally do not find either of these arguments very persuasive. Correctness of functionality is not the only useful measuring stick that we can apply to code. Effectiveness of communication is also very important. Effective communication matters as much as functionality or efficiency because code has to be maintained. If some code is not observably correct, then it becomes a target for investigation when a bug is found. It is wasteful "debugging" code that is not the source of the problem. Similarly, even when code is correct it sometimes needs slight changes to support new requirements. It is wasteful verifying that the starting point is correct when it is, and it is time consuming understanding code that is not clear enough so that changes can be made safely. I believe that code that communicates effectively reduces the burden of testing. I would rather write clear code than test. As for the risk associated with making changes, you have to weigh the expected benefit against the expected cost. In general, the risk of getting a nit-picky change wrong is lower than the risk of getting a large change wrong. From this point of view, I prefer nit-picky changes. Second, while the benefit of a particular nit-picky change may be small, I think it is more important to consider the net effect over time. Small changes are a way of balancing the need for safety and the need for improvement.

In summary, I discussed the following improvements in the previous sections:

Avoid using the ternary and comma operators. In the index sorting algorithm, they can be removed. This is a good change because these operators (especially comma) are poorly understood by many programmers. It also removes some unnecessary complexity which simplifies communication.
Array indexing starts at 0. I did not recommend this change, because the algorithm is designed to be part of a library which behaves this way, but vector indexing should really start at 0. Starting at 1 is potentially confusing to C programmers.
Call operator++() instead of operator++(int), that is, prefix instead of postfix. This change makes most sense from a C++ point of view, since it is a good C++ habit. However, it also makes sense from a say what you mean point of view.
Prefer < over other comparison operators such as >. This is only because of C++ operator implementation conventions.
Use < instead of <= in the index sorting algorithm. This is perceived as reducing the amount of unnecessary work. In fact it might not since now more if-conditions will have to be evaluated.
Use else if instead of if in the index sorting algorithm. This is good because it reduces the amount of work that the algorithm does. You can also think of this as reducing the cyclomatic complexity of this block from 6 to 4.
Document invariants. By documenting the importance of ihi != inhi, it is safer to make changes to this code.
Documentation must agree with code. It is important that code and documentation agree so that there is no ambiguiity over what code should actually be doing.
Document why rather than what or how. By documenting the purpose of the code, the comments are complementary rather than repetative. In the particular case discussed regarding the results of amotry(), better comments lead to better code.
Remove extra variables. Extra variables add to what a programmer has to keep track of while trying to understand an algorithm. By removing ysave, there is that much less to worry about.
Do not re-use variables. The re-use of psum was simply evil. Re-using a variable because it has the same type is like saying any verb will do. It is confusing because the wrong meaning is conveyed. In this case it is even worse because it results in extra assignments and doesn't even save you any writing (which is the usual reason for doing it).