Posts Tagged With 'Programming' RSS Feed

Can a language make programming more fun?

pheaven — Mon, 03 Mar 2008 07:38:14 -0700

I've programmed in a range of languages. There are some that I really enjoy coding in, there are some I can put up with and there are some that frustrate and bore me. Having an interest in language design, I got somewhat curious about what it is that makes working with some languages more enjoyable than others.

A couple of questions came to me right away. First, there is probably a lot of personal preference here. What makes a language enjoyable for me to work in may well be what makes it frustrating to someone else, and vice versa. Second, languages are tools. I've said often enough that different languages are suited to different tasks, and you should pick the one that best fits the job at hand. How important a factor is whether one enjoys working in the language when trying to choose whether to use it in a project or not?

=== Personal Preference ===
I find the more limited range of language features in Java frustrating. I enjoy working in Perl and C# because there are a wider range of language features available to me. I enjoy being able to mix and match paradigms to the task at hand, and like the thought process associated with going through the options and picking the best one (or working out why other people chose a particular one when reading other people's code).

However, someone else may find Perl and, probably to a lesser degree, C# frustrating because the languages have many constructs that you have to learn and be aware of the interactions between to understand the code. They may therefore enjoy working in Java more because it takes less time to work out what is going on with a chunk of unfamiliar code, and you can dig into the changes or fixes that need doing more quickly.

While I know what my preference is on the rich vs. simple language continuum, I can understand why someone may have an opposite preference to me. I'm not sure that one is more correct than the other. I just know what I like.

There are many other things that people like or dislike about languages. Some of them include:
* Strong vs weak typing: those who prefer strong typing probably like it that the compilers makes them insert clear coercions because it catches some more mistakes, whereas those who prefer weak typing may be frustrated that the compiler can't just be smart enough to insert the coercion that they most likely meant for them in most cases
* More wordy vs more symbolic: some people prefer code to read like English, in which case they prefer more "wordy" languages like BASIC; others prefer to use more non-alphanumeric characters for syntax so it looks different to names of things
* Single paradigm vs multi-paradigm: some people feel it is better to have on paradigm almost enforced upon them, such as object orientation. Others find that this limits their creativity and want a much wider choice of language constructs.
There are many, many more; I'm sure people will point out others in the comments to this post.

=== Does it matter? ===
I think that, in general, people are more productive when they are enjoying what they are doing. I know that when I'm really enjoying a coding job, I'll tear through it, sometimes churning out hundreds of lines of code per day (working and with tests). Equally, when I'm bored with what I'm working on, I find myself glancing at the latest posts on Slashdot, checking if there's anyone I can bug on MSN or going to brew up yet more coffee. If you've got a language that you enjoy working in, you're potentially going to be more productive.

However, there's a flip side. If you put too much emphasis on what you enjoy working with, you may end up choosing a language that's not well suited to the task at hand. For example, no matter how much I enjoy working with Perl, it's just not the best thing to work with for building a Windows GUI application. If I instead work with one of the .Net languages or another language that has a really good tool chain associated with it for building Windows GUI applications, I'll will likely get the job done much more quickly.

=== Conclusions ===
I think it's safe to say that language preference is a secondary issue to choosing the correct tool for the job. First, identify those languages that are suitable for the task. That may be in part related to the language features, availability of compilers or interpreters for platforms you need to run on, what libraries and tools are on offer and corporate or business constraints. Then, if there's still more than one choice available to you, consider personal preference.

Do try...catch blocks hurt runtime performance?

pheaven — Tue, 19 Feb 2008 06:23:04 -0700

Recently, a friend mentioned that someone had told him that writing a try...catch block in C# (or substitute some other .Net language here) resulted in a "huge penalty" in terms of performance compared to if you had not written it. That is, merely writing such a block actually hurt program performance, even if an exception was never thrown. He didn't believe this was true, and rightly so - it's completely wrong. This post is a tidied up version of my explanation.

=== Inside a .Net Assembly ===
A .Net assembly, if we ignore various headers, consists of three things:
* Bytecode: a sequence of low-level instructions that specify the body of a method
* Metadata: a set of tables, a little bit like a database, describing higher level constructs such as classes, methods, signatures and so forth
* Heaps: places where string constants and other such things are stored
That is, bytecode is what we actually execute and the rest is there to describe the extra details. To give you an example of the interplay between them, consider a method call. The bytecode stream contains the call instruction, followed by a method token, which is actually an index into the methods table. The methods table in turn allows us to find out where the bytecode for the method we're calling starts, so we can execute it.

(As an aside, these lookups wouldn't be all that expensive to do per call, though in reality they likely won't actually happen more than once per call site, unless it's done through reflection or a delegate. That's because when the CLR JIT-compiles the bytecode, it can compile the method call down to call instructions at the CPU level that refer directly to the method being called. You don't need to know this bit; it's just here for the curious.)

=== How Exception Handlers Are Stored ===
The .Net CLR has a concept known as a "protected region". A protected region is a sequence of instructions that has an associated handler. In C# or VB.NET, the instructions in a protected region correspond to code in a try block. There are various types of handlers, including typed ones (that catch only a certain type of exception) and finally ones. Note that a try...catch...finally will result in two protected regions at the CLR level, one for the catch and one for the finally. The protected regions will cover the exact same sequence of instructions, just have different handler addresses.

Each method that has protected regions comes with a table of them. For each protected region, it contains four entries:
* The starting instruction in the bytecode for this protected region
* The number of bytes worth of instructions from the starting point that are protected
* The type of handler
* The location in the bytecode of the handler
They are ordered with innermost handlers coming first.

=== What happens at runtime ===
Here is the important part when it comes to performance when an exception is not thrown. Since the protected regions are stored in a table and are not in the bytecode, and because the CLR does not need to worry about the exception handlers unless an exception is thrown, then there is no runtime penalty for having a try...catch block. For finally handlers it is a little different, because we do need to run those even when we don't have exceptions. However, since we can compute what we will need to run when statically, the JIT compiler can still emit code that jumps to the finally handler at the appropriate time, making the execution overhead of one of those most likely just a jump and a return.

So that's most of the answer to the question that was asked, but for interest let's take a look at what happens when an exception is thrown. Provided the current method has protected regions, you scan through the table to find if there are any that cover the instruction where the exception was thrown and that are capable of handling it (they are looking for an exception of the correct type, for example). If there are multiple nested handlers that could handle the exception, the ordering of innermost first means that we will find the correct handler.

If we find a handler, we execute it. If we don't find one, we move down to the next method in the call stack and check if it has a suitable handler, keeping going until we find one (or we discover that the exception is user-unhandled and terminate the program). This means that the cost of throwing and catching an exception is dependent on how far down the call stack you have to go to find a handler.

From this we can conclude that .Net is optimized for the case where you do not get exceptions. Since exceptions are intended to happen only in exceptional (that is, unexpected) circumstances, this is a sensible design decision. If you inclined to use exceptions for ordinary flow control, this should give you another reason not to.

=== And the cost of a try...catch block is... ===
So what can we conclude? The overall cost of a try...catch block that never handles an exception is a few bytes of memory - or at worst a few words - for the entry in the protected regions table. The only possible runtime penalty is the extra time to load those extra few bytes into memory. Since they are stored way away from the JITted bytecode stream, it's highly unlikely you're going to incur any additional cache-misses at runtime as a result of the handler too. Thus, the cost is essentially nothing.

The cost of not handling an exception that you should have may well be that your program crashes. This results in unhappy customers, a hit to your reputation and development time to go and do a bug-fix, which will almost certainly be much greater than if you had put it in there in the first place. Obviously, protecting code that can not throw an exception under any circumstances is a waste of your development time. But otherwise, it's best to be safe rather than sorry, safe in the knowledge that even if an exception never does occur in that bit of code, it's not really costing anything anyway.

Saturday, 12 January 2008

Disi — Sat, 12 Jan 2008 21:13:08 -0700

I spent the whole day preparing worksheet and marksheets with formulas for Grade 10 IT and MATH. The other thing that I did was to make introduction of database easy using Delphi for the learners

Trimming strings

Actor — Wed, 02 Jan 2008 02:43:07 -0700

Here, for completeness without further comment, is the code for RTrim, LTrim and Trim which are included in the unit Tools.

      Function RTrim (Var S : String) : String ;
      {
         RTrim -- remove trailing blanks
      }
      Var
         i : Byte ;

      begin { RTrim }
         for i := Length(S) downto 1 do
            if S[i] > BLANK then begin
               S     := Copy(S,1,i) ;
               RTrim := S ;
               Exit
            end ;
         {
               if we reach this point then S contains only BLANKS
            so we return a null string
         }
         S     := '' ;
         RTrim := S
      end ; { RTrim }


      Function LTrim (Var S : String) : String ;
      {
         LTrim -- remove leading blanks
      }
      Var
         i : Byte ;

      begin { LTrim }
         for i := 1 to Length(S) do
            if S[i] > BLANK then begin
               S     := Copy(S,i,MAXSTR) ;
               LTrim := S ;
               Exit
            end ;
         {
               if we reach this point then S contains only BLANKS
            so we return a null string
         }
         S     := '' ;
         LTrim := S
      end ; { LTrim }


      Function Trim  (Var S : String) : String ;
      {
         Trim -- remove leading and trailing blanks
      }
      begin { Trim }
         S     := RTrim(S) ;
         S     := LTrim(S) ;
         Trim  := S
      end ; { Trim }

Entabbing

Actor — Fri, 28 Dec 2007 03:54:10 -0700

The next program in our project is EnTab which replaces runs of blanks in a text file by tabs and blanks. Here is the specification, i.e., the "manual"

PROGRAM
   EnTab -- convert runs of blanks into tabs

USAGE
   EnTab
FUNCTION
   EnTab copies its input to its output, replacing strings of blanks by
   tabs so that the output is visually the same as the input but contains
   fewer characters.  Tab stops are assumed to be set every 3 columns
   (i.e., 1, 4, 7, ...), so that each sequence of one to four blanks
   ending on a tab stop is replaced by a tab character.
BUGS
   1. EnTab is naive about backspaces, vertical motions and non-printing
      characters.
   2. EnTab will convert a single blank to a tab if it occurs at a tab
      stop, thus EnTab is not an exact inverse of DeTab.
   3. if any record in the input is longer than 255 char Entab will
      truncate that record to 255 char.

We first address how tab stops are to be represented in the program. Since we will next write the inverse program DeTab, we choose to write a unit, TabsUnit, to be used by both programs and thus ensure conformity between the two programs.

Here is the code for the unit TabsUnit:

Unit TabsUnit ;
{
   used by DeTab and EnTab
}
interface
   Uses
      Tools ;

   Type
      TabType  =  Set of Byte ;

   Var
      TabSet   :  TabType ;


   Procedure SetTabs ;

implementation

   Procedure SetTabs ;
   {
      SetTabs -- set initial tab stops
   }
   CONST
      TABSPACE = 3 ;    { 3 spaces per tab }

   Var
      i  :  Byte ;

   begin { SetTabs }
      for i := 0 to MAXSTR do
         if i MOD TABSPACE = 1 then
            Include (TabSet, i)
         else
            Exclude (TabSet, i)
   end ; { SetTabs }

end.

As you can see we choose to represent tab stop with a set of byte. Any number in the range 0 .. 255 that is a member of the set is a tab stop. The set is declared to be a user defined type TabType. The unit also declares a variable TabSet : TabType and a procedure SetTabs which sets a tab every three spaces.

Our first cut of the program itself is (in pseudocode) :

Program EnTab

begin
   while not eof
      read a string from standard input
      entab that string
      write the string to standard output
   end
end

This approach reduces the entire problem to one of entabbing a string. By reading in an entire string before entabbing it we are able to access any char in the string at any time and are not forced to deal with the data on-the-fly. The price we pay for this is that our program will not be able to handle records that are longer than the maximum length of a Turbo Pascal
string, 255 chars.

Our experience is that by approaching a programming problem from the viewpoint of how a human being would tackle it we reduce its complexity.
The question becomes "How would a human decide where to put tabs and what blanks to eliminate?" This question already breaks the problem into two parts that we can consider separately

(1)where do we put tabs? Obviously any space that immediately precedes a tab stop is a candidate for replacement by a tab.

(2)what blanks do we eliminate? Having completed the first step we simply delete any and all blanks that immediate precede a tab. Since it is possible, indeed quite likely, that more than one blank will precede a tab this needs to be done in a loop.

Here is our code for EnTab.

Program EnTab ;
{
   EnTab -- replace blanks with tabs and blanks
}
Uses
   Tools,
   TabsUnit ;

      Procedure EnTabStr (Var Str : String) ;
      {
         EnTab a single line
      }
      Var
         i  : Byte ;

      begin { EnTabStr }
         {
            first scan of the string - where to put tabs
         }
         for i := 1 to Length (Str) do
            if (Str[i] = BLANK) AND (i + 1 in TabSet) then
               Str[i]   := TAB ;
         {
            second scan of the string - what blanks to eliminate
         }
         for i := 1 to Length (Str) do
            if Str[i] = TAB then
               while Str[i - 1] = BLANK do begin
                  Delete(Str, i - 1, 1) ;
                  i := i - 1
               end
      end ; { EnTabStr }

Var
   Str      :  String ;
   TabStops :  TabType ;

begin { EnTab }
   SetTabs ;

   while NOT eof do begin
      ReadLn (Str) ;
      EnTabStr (Str) ;
      WriteLn (Str)
   end
end.  { EnTab }

As you can see, by working with a string we are able to scan the record and implant tabs, then [i]back up[/i] and scan the record again to eliminate blanks. You cannot back up if dealing with the data stream on-the-fly.

We have already acknowledged that the program contains a "bug" in not being able to handle records longer than 255 chars. We believe the bug is inconsequential and unlikely ever to manifest itself. If the bug is a problem there are ways to cure it without resorting to on-the-fly
processing. The first is to define a type LongString:

Type
   LongString = Record
      Len   :  Word ;
      LongS :  Array [1 .. 32767] of char
   end ;

Allowing a string up to 32767 char. This approach will require you to write several supporting routines: ReadLongString, WriteLongString, LongLength, LongDelete. You will also have to redefine how tabs are represented and detected since a set can have only 256 members. The simplest would be to have every position after 255 automatically be a tab stop. This suggests that one might be able to rewrite the main routing thus:

begin { EnTab }
   SetTabs ;

   while NOT eof do begin
      Read (Str) ;
      EnTabStr (Str) ;
      Write (Str) ;
      {
         if record is longer than 255 chars
      }
      while NOT eoln do begin
         Read(Ch) ;
         Write(Ch)
      end ;
      {
         move on to next record
      }
      ReadLn ;
      WriteLn
   end
end.  { EnTab }

Leaving the tabs representation and EnTabStr intact.

Finally, you could read each record into a typed file of char, effectively
giving a string representation that could be over two billion char long.
That should be enough for anybody.

I have not written, debugged or tested any code using this approach. I leave that to you.

Need For Speed: Performance Programming Tips

pheaven — Tue, 18 Dec 2007 02:51:07 -0700

Sometimes a program you have written just doesn't run fast enough. In this article I'm going to look at how (and how not) to approach such problems along with some tips for speeding things up in various cases.

=== Stop Right There! ===
The biggest mistake people make when trying to improve the performance of their programs is jumping straight in and trying to do it without first understanding where the bottleneck lies. Often the real performance issue may not lie where you think it does.

Tools for analyzing program performance are called profilers. They will tell you which functions and sometimes even which lines of the program are taking up what factor of the execution time. This is highly valuable information and can save you a lot of wasted time. Without it, you might set about optimizing a function or method that is only taking a tiny fraction of the execution time anyway.

For example, if you can make a function run in half the time it used to, but it only took 1% of your program's execution time, then you've maybe got half a percent faster. If you're sufficiently aware that you've got a performance problem to be hunting one down, getting half a percent faster isn't really going to help matters. Discovering that a given function contributes 20% of the execution time and getting the same kind of performance gain out of it, on the other hand, means your program overall gets 10% faster - a still modest gain, but at least one that's likely to be measurable.

I'm not writing this article targeted at any particular language, but profiling tools are out there for pretty much every mainstream language there is. Search this site. Google for it. Ask around on forums or ask your programming friends for recommendations. You could save yourself a lot of wasted time by using one.

=== You Could Try Cheating ===
Sometimes you can rely on the human nature of your users to avoid actually doing any performance enhancements at all. An application feels slow to a user if they are sat there waiting and don't notice anything changing for a long time. If you have something that takes ten seconds to do, it is likely to feel a lot slower if the application just freezes up for ten seconds than if it displays a progress bar that increments a step every second or so.

This phenomenon here is known as perceived speed. It's the reason that many large applications have splash screens: so the user gets some feedback telling them that the application actually is starting up, while in the background it loads all of the stuff it needs to. In the long run, you're actually making the whole thing take longer, since as well as loading the entire application you have to load the splash screen and its pretty graphics as well. It keeps users happy though, and makes it feel faster. That can be enough.

=== Optimizing Database Operations ===
I am endlessly surprised by the number of times the same old trick works for making slow database queries run a lot faster: adding indexes appropriately.

An index on a field makes lookups based on it a whole lot faster. That means that if you are using the field in the WHERE or JOIN clause of an SQL statement, you stand to gain by adding an index on it - especially in the case of JOINs.

Here is a query from the RSS generating script from my own personal site's blog.

SELECT          blog.id, blog.dateposted, blog.title, blog.rendered,
                COUNT(blog_comments.blogentryid)
FROM            blog
LEFT JOIN       blog_comments ON blog.id = blog_comments.blogentryid
GROUP BY        blog.id
ORDER BY        blog.id DESC
LIMIT           10

It had worked just fine a few months back, but then one day I noticed that Facebook had stopped importing posts from my blog. At first I thought the script was in some kind of infinite loop, but eventually I realized it was just running really, really slowly. What had gone wrong?

It turns out that in old, old posts in my blog, automated spambots had posted some 12,000 spam comments. That meant that when I did the JOIN of the blog_comments table, it was now having to find values of the blogentryid field - the foreign key to the blog posts table - to match each blog post.

Guess what? I'd forgot to put an index on the blogentryid field. I added the index, and suddenly the whole thing was running in around a second, rather than long enough to cause Facebook to time out on it. This is not the first time I have added appropriate indexes and seen incredible performance leaps: for one client I managed to bring a 3 minute long query down to a couple of seconds with such an approach. If your database queries are running slow, check your indexes before you start trying to tweak query itself.

=== Cache Stuff ===
Some programs do relatively complex or just plain time consuming computations to produce results or reports. Into the time consuming category falls calls to databases. To get a result, you send a query - potentially over the network - which then has to be interpreted by the database engine, which then gets the results and sends them back to the application - potentially over the network again - where they are then taken and placed into the data structures that the program is working with. That takes time.

If the data is not changing regularly or you can get away with showing slightly out of date data, you can improve performance by keeping copies of the results of recent queries around in memory. Then, the next time someone does the same query, you need not go to the database, or do the complex computation: you just return the result from the last time it was done.

This is known as caching. It is a trade-off: you are increasing memory usage of your application in order to decrease the time it takes, on average, to get a result. We do a lot of caching of things from databases here at Programmer's Heaven to keep the site running fast with some very, very modest hardware requirements. The small number of servers we have are kitted out with plenty of RAM, but hey, it's a lot cheaper than load balancing hardware.

=== Improving Algorithmic Complexity ===
Time for today's theoretical computer science lesson. Bear with me, because this matters if you want to be able to understand and potentially improve the performance of any algorithms in your code.

The reason that adding indexes to database fields works so well is because you are turning a linear lookup - where the database engine has to look over every row of the table - into perhaps a logarithmic order one if it's using a b-tree for the index, or even a constant order one if it's using a hash table.

Let me explain what I mean by the word order, since some people may not be familiar. Suppose we have a problem of size n - in the database case, n would be the number of records in the table. The order of an algorithm tells us how the time it takes scales with the size of the problem it is working on.

Let's take a simplified problem: we want to find all rows where field X has a value of 10. If we were scanning every row of the table to find those that matched the required condition, then we have to look at all n rows of the table. Therefore, the time it takes scales linearly with the size of the problem - the number of rows. Therefore, we say it is O(n), read "order n".

Suppose we add an index to the table on the field X. This creates a tree data structure of the values in the field across all rows in the table. The notable thing about it is what happens when you consider any node in the tree. If we are trying to locate rows where the field has a value of 10, the value of the node will either be equal to ten, less than ten or greater than ten. If it is equal to ten, then this node tells us what rows in the table have a value of ten. If it is greater than ten, we know that the value must lie in the left subtree. If it is less than ten, we know we must look in the right subtree.

If the tree is balanced - that is, each node has subtrees of equal size - then every time we visit one node in the tree, we half the number of other nodes we have to consider. This halving of the problem every time - or in fact cutting it by any constant factor - gives us something known as logarithmic order, written O(log(n)). As n grows, so does the time taken - but the rate of growth gets slower and slower as n increases.

=== An Example Of Algorithmic Improvement ===
We are implementing an application for an intelligence agency. We have a large list of names of people that they are tracking, and constantly have details of financial transactions coming in. If we see a transaction with the name of somebody were are tracking on it, then we need to raise the alarm as quickly as possible.

We don't want to hit the database every time, since that involves connecting to the database, doing a query and getting a result set back. Instead, we decide to keep the list in memory. We're coding it in C#, so our first instinct is, "OK, it's a list of names, which are strings, so let's use the generic List class".

So we declare it and fill it up from the database:

List<string> WeHaveOurEyeOnYou = new List<string>();
// Database loading code here

And every time we want to do a lookup, we use the Contains method:

if (WeHaveOurEyeOnYou.Contains(Transaction.Name))
{
    Console.WriteLine("OMG Terrorist!");
}

And it works.

Wanting to make good use of the theory we learned earlier, we think about the order of our algorithm. The Contains method is doing a linear scan through the list. Therefore, our algorithm is O(n). If the number of suspected terrorist we know about increases tenfold, then it takes ten times as long to do the check. Can we do better?

The List class also has a BinarySearch method. This relies on our list of names being sorted, so after out database loading code we do:

WeHaveOurEyeOnYou.Sort();

This is an order O(n*log(n)) operation, but we only have to do it once, not for every lookup, so it doesn't affect the lookup time. We then change the conditional to read:

if (WeHaveOurEyeOnYou.BinarySearch(Transaction.Name))

Given a sorted list, BinarySearch takes the name in the middle of the list and compares it to the name we are looking for. If it matches, we have our result. If not, we can forget about half of the list. We repeat this process until we get a match or no match. The halving of the problem every time gives us, as we learned earlier, logarithmic order - O(log(n)). The time taken now scales logarithmically with the the number of names - a whole lot better than linearly.

That's a good improvement, but can we do any better? The question is yes, but we're going to have to trade off some memory for it. There is a data structure that allows us to do constant time lookups - that is, the time it takes to do the lookup does not depend on the number of items at all! We write this as O(1). This data structure that does this is known as a hash, and in the .Net class library one such class that implements this is the generic Dictionary class.

How on earth does it achieve constant time lookups? We know that numerically indexing into an array is a constant time operation: no matter whether we are accessing element 10 or element 10,000 it takes the same amount of time. It's just a memory lookup. We know we can't index into an array using a string, but it turns out there are good ways that we can compute a integer value based upon the characters in a string that is:
* Within a given range
* Unlikely to be the same as the value calculated for a different string? This is known as hashing. Therefore, we set the range of values to be the number of items we have. Then we use the number that it generates as an index into an array of the values.

It is not quite this simple really - we are only promised that collisions are relatively unlikely, but they inevitably will happen. Therefore, we need a way to handle this.

This data structure is more complex that a simple list, and therefore takes more memory. However, we gain significant performance on large data sets when it comes to doing lookups. The only thing about the .Net Dictionary class is that it maps keys to values. In our case, we don't care about the value but just whether the hash contains the key. Therefore, we can declare our data structure like this:

Dictionary<string,bool> WeHaveOurEyeOnYou = new Dictionary<string,bool>;

We picked bool because it's small. The database loading code can then just add entries like this:

WeHaveOurEyeOnYou.Add(Name, true);

And lookups become:

if (WeHaveOurEyeOnYou.ContainsKey(Transaction.Name))

You had also better sprinkle in some comments about why you used a Dictionary when a List was the obvious thing to do. Otherwise, some programmer may come along later and decide to refactor the performance enhancements they don't understand out of your code, as they wonder why on earth you aren't just using a List.

=== Algorithmic Improvements Are A Big Win ===
In the previous example, we have made a huge improvement in the case where this is a lot of names. In general, algorithmic improvements will give you the biggest gains. Therefore, they are what you should be aiming for.

What algorithm to use is very problem specific, so I can't really give much in the way of general advice here. Certainly, you can try to analyze the algorithms and data structures that you are using to understand the algorithmic complexity (order) of the code you have written, though it can be genuinely hard to do such an analysis correctly at times. There are books of algorithms you can buy, and plenty of resources online too. I'm certainly no walking encyclopedia of algorithms, which is why I have a big thick book of them that I turn to when I'm looking for something better than the obvious way. Sometimes the better way is anything but obvious.

=== Go Parallel ===
There are two types of tasks: CPU bound and I/O bound ones. Those that are CPU bound require CPU time. The only way you can really improve things here is if you have multiple CPUs or cores at your disposal. If so, look at whether you can spawn a couple of threads (no more than one per execution core) and do parts of the execution in parallel.

The other type is I/O bound tasks. These depend on the network and disks, which are relatively slow. You might be able to take advantage of asynchronous I/O, where the operation returns immediately rather than blocking and reports back to you when the operation is complete. In the meantime, you can get on with doing other useful work.

The specifics of these are very situation specific and the options available then vary depending on what platform you are working on, so I won't even attempt to go any further here than just raising it as something you can consider. Parallelism is not a silver bullet, though, and the gains are pretty much never what you might wish for. Certainly, spawning two threads doing parts of a CPU bound task that you did in a single thread before is unlikely to come anywhere close to halving the overall execution time. If the threads have to communicate or are accessing the same areas of memory, that will certainly limit the gains you can get.

=== Last Resorts ===
There are many advantages to working in higher level, garbage collected languages over working in languages like C where you are very close to the hardware, but also forced to manage memory yourself. However, there are times when the reality simply is that writing parts of the code that are CPU bound and really do need to perform in C rather than some other language (especially dynamic ones like Perl and Python) is just going to give a big performance win. If you are working in such a language and are really stuck, consider this. It should not be your first consideration, though.

If none of the above work, you can always try to micro-optimize. This involves looking at bits of code and finding cute ways to make them run that tiny bit faster. Doing this often involves knowing things about the underlying architecture.

For example, if I am working in C# and .Net, I may have a program that does a lot of method calls on objects instantiated from some class. If the class is not sealed (final in Java terminology), then a lot of the time the lookup of which method to call will be done using the v-table, since the object could in fact be an instance of a subclass and the method could be overridden. If I mark the class as sealed, the compiler knows at compile time which method will be called, and can emit code that avoids the vtable lookup. The problem is that in doing this optimization you have prevented anyone from extending the class in question, which may have been a bad idea. Additionally, it will give a very small gain.

The side-effects of micro-optimization are often less clear (and sometimes completely impenetrable) code. Unless you are optimizing very tight loops for CPU bound tasks, this kind of approach probably isn't going to be much of a win.

=== Conclusion ===
Trying to optimize programs without first trying to understand why they are performing badly is commonly done, but also likely to waste your time. You are far better for getting a profiler to get some hard numerical data on the problem, so you can target your efforts. The biggest wins come from algorithmic improvements, caching and sometimes parallelization. Improving perceived speed can save you having to do any of them, though.

This article is far form the definitive guide to performance programming, and there are plenty of things I have not even touched on. I have instead tried to present some general techniques that I know from personal experience have actually delivered improvements, sometimes significant ones. I hope it has offered some guidance to anyone looking to speed up their sluggish programs.

I hate "== true"

Jonathan — Thu, 13 Dec 2007 09:19:07 -0700

If you've asked someone to look for something you left at their house, would you say, "give me a call if it's true that you found it"? No, you'd say "give me a call if you found it". So why do so many people write things like:

if (found == true)

Instead of the shorter, clearer, equivalent:

if (found)

Yes, I know, I shouldn't let refactoring get me so cranky.

Functional programming: what’s it all about?

pheaven — Mon, 03 Dec 2007 02:35:32 -0700

Most programmers today will be familiar with a number of programming paradigms. The age-old procedural programming paradigm, where a program is broken down into a number of procedures or routines, is still very much alive and the right solution for a number of problems. Object Oriented programming is one of the most popular and fashionable paradigms today, allowing for a good level of code re-use through mechanisms such as instance management (one class can be instantiated many times to give many objects), data hiding (think private variables in a class) and inheritance.

Another paradigm cross-cuts these two: that of imperative programming. This simply means that a program consists of a sequence of instructions that are executed one after the other (or at least appear to be; both the compiler and the CPU may well re-order instructions to improve performance when it does not affect the behavior of the program). In fact, when I was younger my definition of a computer program included the words “a sequence of instructions”.

At that time, probably like many programmers today, I hadn’t been exposed to any programming languages that worked differently to this. Java, C#, all of the many dialects of Basic, Pascal…all of these frequently used languages are imperative. This is not a bad thing; in fact, it’s psychologically comfortable for us as humans, since we tend to plan how to achieve a task by breaking it down into a set of steps or follow sequences of instructions ourselves (for example, when making food).

Today I’m going to talk a little about functional programming. If you’ve seen it before this may be nothing new. If you have not, then hopefully it challenges a few assumptions you may have made about programming and arms you with another approach to solving some problems. Just as you can fake out object orientation somewhat in languages without direct OOP support, you can use functional techniques in some non-functional languages.

=== ML ===
It is going to be useful to have a language to provide examples in. I have selected the Standard ML language, and you can download the Moscow ML interpreter for free, should you want to try some of the examples for yourself.

=== Yes, functional programming uses functions ===
A function takes one or more parameters and, based upon them, computes a value. This is sounding somewhat like procedural programming so far, but remember that we’re not supposed to be writing our programs as sequences of instructions. Instead, we will write programs by writing functions that call other functions to build up their result.

Let’s start off with a simple example: the function double, which multiplies a number by 2.

- fun double(x) = 2 * x;
> val double = fn : int -> int

The “-“ is the prompt in the Moscow ML interpreter. The rest of the first line is what I typed to define the function. The “x” in the brackets is the name of the parameter the function takes. Following the “=” is the computation that the function performs: multiplying the value passed as the parameter “x” by 2. I can apply this function to a value, for example the number 21:

- double(21);
> val it = 42 : int

Giving the answer 42, surrounded by words of cryptic wonder. But what on earth are these responses that the ML interpreter gives us?

=== An Aside On Type Inference ===
After I specified the function “double” the ML interpreter gave me a somewhat cryptic looking response.

> val double = fn : int -> int

Notice that I did not specify the type of the parameter “x” or the type of the function “double”. Instead, ML has worked out the type of the function for me. Intuitively, it has looked at the function, seen that we have multiplied the parameter by an integer (type “int”) and therefore inferred that the parameter “x” must be an integer too, and that the overall result of the function is also going to be an integer. It has therefore given it the type “int -> int”, the arrow symbol “->” denoting that this is a function type (rather than just the type of a simple value, such as the number 42 with just has type “int”) that takes a value of the type to the left of the arrow and returns a value of the type to the right of the arrow.

This is called type inference. Type inference is a process by which a compiler can determine the types of your variables and functions. This is unlike languages like C, C# and Java, where we write the types ourselves and the compiler just checks them. It is often (but not always) found in functional languages. The type that is inferred will always be displayed after a colon.

It’s worth noting that functional languages often have elaborate type systems, and if you want to really understand a language like ML then you have to understand the type system too. We’re simply using ML to understand functional programming here, so we will put the type system aside for today.

=== Composing functions ===
I said earlier that we build functions up from other functions. Here is an example of us defining a “triple” function in terms of the double function:

- fun triple(x) = x + double(x);
> val triple = fn : int -> int

We can see something in this program, however, that does not appear to be a function – the “+” operator. In other functional languages, you would be forced to write something more like:

+(x, double(x))

ML provides some nicer syntax, but conceptually you can think of it as just that – syntax that really maps to calling some addition function. In fact, if we have a language that only gives us functions (and no other built-in data types, such as the integers), it is possible to write a program to perform any computation that you would be able to in any other language you might have worked in. This property is called Turing Completeness, and I mention it here so you can see the true power of functional programming. Of course, a language with no basic data types would be impractical for any real world usage.

=== Name Binding – Liberation From Assignment ===
In a pure functional programming language, the concept of assigning a value to a variable does not exist. That is, there are no storage locations. When I have been using the “=” operator, it has not been doing assignment; instead, it has been doing something known as name binding. I can, for example, write the following code:

- val a = 21;
> val a = 21 : int
- triple(a);
> val it = 63 : int

You may be thinking “there is a storage location with name a”, but actually the correct way to think of this is “the name a is bound to the value 21”. When I use “a” as the parameter for the function “triple”, it is as if the value “21” is textually substituted in for “a”. If I later write the following:

- val a = "badger";
> val a = "badger" : string

Then the name “a” is now bound to the string value “badger”. Notice that the result of this is to give “a” a different type. This is fine because “a” does not refer to some storage location of a given type, it is just a name that refers to a value. To really make the semantics clear, consider this example:

- val multiplier = 5;
> val multiplier = 5 : int
- fun multiply(x) = multiplier * x;
> val multiply = fn : int -> int
- multiply(5);
> val it = 25 : int
- val multiplier = "badger";
> val multiplier = "badger" : string
- multiply(5);
> val it = 25 : int

Everything is as expected for the first six lines. However, when I re-bind the name “multiplier” to the string “badger”, the “multiply” function continues to use the value that the name was bound to when it was defined. Therefore the outcome of the multiply function does not change. This behavior is very different to the behavior you would get with assignment.

Having modifiable storage locations actually makes programs harder to reason about formally and to understand intuitively. Most programmers have learnt not to use global variables unless they really need to, since they can be modified by any part of the program at any point in time. Even the best C programmers have likely screwed up with pointers and spent hours tracking down the resultant problems at some point. It’s clear that assignment has its issues, and that getting away from it can help.

I’m not by any means saying that name binding is a good answer for all problems. Indeed, ML does provide you with references and a mutable (modifiable) store. Sometimes you need that for performance, or now and then because doing without it is just plain hard. You can comfortably write a lot of programs free of assignment, however.

Name binding is hard to take to everyday languages because they don’t really do it a great deal. Where they tend to do it, at least conceptually, is when passing parameters to a procedure or method. We can probably learn that assigning to parameters is a bad idea. I really don’t want to advocate not using any variables in a procedure and just expressing it entirely in terms of the parameters, but it follows that shorter procedures will need to introduce less extra variables. Writing many shorter procedures or methods rather than a single big long one has been common advice for ages anyway, though.

=== Recursion Replaces Iteration ===
The fact that there is no mutable storage means that loops as they exist in non-functional languages are not really possible. There is no way to have a counter for a for loop, for example. Therefore recursion tends to be used in its place. For example, we can re-write the following loop (written in pseudo code):

for i = 1 to x
    sum += i
next i

As the following functional program using recursion:

- fun sumfirst(x) = if x = 0
                    then 0
                    else x + sumfirst(x - 1);
> val sumfirst = fn : int -> int
- sumfirst(10);
> val it = 55 : int

A common response to this is that “recursion is slow”. This is true, but if we re-organise the program to maintain and pass on a running total:

- fun sumfirst(x,t) = if x = 0
                      then t
                      else sumfirst(x - 1, t + x);
> val sumfirst = fn : int * int -> int
- sumfirst(10,0);
> val it = 55 : int

Then the result of calling the function, in the recursive case, only depends on the function “sumfirst” itself. Therefore ML is able to make an optimisation called a tail call. This means that instead of making a new call frame, we re-use the current one, since it is no longer needed. This makes the program run faster than a recursive program normally would and, most importantly, it will not build up a large call stack and use a lot of memory. (While on the subject, Parrot, a virtual machine for dynamic languages, has a JIT compiler that can spot tails calls and sometimes can optimize them to loops at the machine code level, meaning recursively defined functions can be as fast as their loop-based counterparts.)

A recursive solution to a problem can often be very elegant, though be aware that tail calling isn’t implemented in many non-functional languages. Interestingly, the .Net CLR supports it.

=== List Processing and Pattern Matching ===
We can introduce a list containing the numbers from one to ten like this:

- val onetoten = [1,2,3,4,5,6,7,8,9,10];
> val onetoten = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] : int list

A list, unlike an array, is not mutable. We do not index into it at a certain point as we would with an array; instead we recursively move through the list. We can use the “cons” (written “::”) constructor to break a list into its first element (called the head) and the rest of the list (called the tail). The following function extracts the head of the list:

- fun head(h::t) = h;
! Toplevel input:
! fun head(h::t) = h;
!     ^^^^^^^^^^^^^^^
! Warning: pattern matching is not exhaustive
> val 'a head = fn : 'a list -> 'a
- head(onetoten);
> val it = 1 : int

We have been given a warning here, which cryptically tells us that we did not specify what to do in the case of an empty list. This means that we will get an exception if we try to pass an empty list to this function:

- head([]);
! Uncaught exception:
! Match

We may choose to return zero when the list is empty:

- fun head(h::t) = h
    | head([])   = 0;
> val head = fn : int list -> int
- head(onetoten);
> val it = 1 : int
- head([]);
> val it = 0 : int

The vertical bar introduces a highly powerful technique called pattern matching. You can think of it somewhat like overloading methods with the same name and different parameter lists. However, we specify all of the behaviors within the one function – only writing the name once. Here we use pattern matching to specify what to do in each of the possible cases: when there is an element in the list that we can extract and when there isn’t (one of which must always be the case). Inductive proofs of program correctness can often quite closely follow the structure of code like this.

=== Programs And Data Are Equivalent ===
Many programmers like to keep their program and the data it works on separated in their mind. We have variables that hold data and we pass them to procedures or methods that make up the program. In functional programming, however, functions are just another form of data too. That is, you can pass a function as a parameter to another function. We already saw this the other way round earlier, when I stated that you could encode any other data type (such as the integers) just using functions.

Some of the most useful examples involve dealing with lists. Let’s take our previous list of the integers between 1 and 10.

- val onetoten = [1,2,3,4,5,6,7,8,9,10];
> val onetoten = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] : int list

Now suppose I wanted to extract just the even elements of the list; I could write the following function:

- fun justevens ([])    = []
    | justevens (x::xs) = if x mod 2 = 0
                          then x :: justevens(xs)
                          else justevens(xs);
> val justevens = fn : int list -> int list
- justevens(onetoten);
> val it = [2, 4, 6, 8, 10] : int list

I could define a function to get just the odd elements of the list in a similar way:

- fun justodds([])    = []
    | justodds(x::xs) = if x mod 2 = 1
                        then x :: justodds(xs)
                        else justodds(xs);
> val justodds = fn : int list -> int list
- justodds(onetoten);
> val it = [1, 3, 5, 7, 9] : int list

However, we’ve now duplicated all of the code that moves through the list. It would be good to separate the condition that we want to use when choosing items from the list from the code to move through the list. We start by writing two “predicate” functions (a fancy name for functions that return a boolean) that will test whether a single integer is even or odd:

- fun iseven(x) = x mod 2 = 0;
> val iseven = fn : int -> bool
- fun isodd(x) = x mod 2 = 1;
> val isodd = fn : int -> bool
- iseven(2);
> val it = true : bool
- isodd(2);
> val it = false : bool

These return true or false depending on whether the number is even or odd. We will now write a function that takes a list and one of these predicate functions and uses the predicate to decide whether the element should be in the result list.

- fun filter([], p) = []
    | filter(x::xs, p) = if p(x)
                         then x :: filter(xs, p)
                         else filter(xs, p);
> val 'a filter = fn : 'a list * ('a -> bool) -> 'a list

We can now pass the “iseven” and “isodd” functions to the “filter” function. Then, when we call “p”, passing it the parameter “x”, it will call whatever function we passed. In fact, if you were to substitute the body of “iseven” or “isodd” in place of “p”, you’ll find that we get back to the same code as we had for the original two “justevens” and “justodds” functions we wrote earlier. The behaviour is the same, too:

- filter(onetoten, iseven);
> val it = [2, 4, 6, 8, 10] : int list
- filter(onetoten, isodd);
> val it = [1, 3, 5, 7, 9] : int list

However, our program is now shorter and exhibits better code re-use. A function that takes another function as a parameter is usually called a higher order function. When you are using this kind of technique, you are doing higher order programming.

=== Anonymous Functions ===
Anonymous functions are also commonly used in functional programming. That is, you can define a function without giving it a name. The syntax for this is “fn parameter list => body”. In the following example we define and pass a predicate function that checks if the value is less than 5.

- filter(onetoten, fn x => x < 5);
> val it = [1, 2, 3, 4] : int list

The ability to pass functions is one of the most useful techniques we can lift out of functional programming, and many languages have. C and C++ had function pointers. C# 1.0 had delegates, C# 2.0 introduced anonymous methods and C# 3.0 introduces syntax almost identical to the ML anonymous function syntax shown here. Perl, Python and Ruby all allow for higher order programming too.

=== So What Have We Learnt? ===
Functional programming isn’t scary nor solely for academics. It provides some pretty neat ideas, and the languages that most programmers are used to working in are starting to incorporate them. Here’s a summary.
* Writing a sequence of instructions isn’t the only way to write a program.
* A programming language that only had functions and nothing else would be totally impractical but you could still write any program in it that you wished.
* There is life without variables and assignment.
* Recursion can replace iteration, and with tail recursion that can be efficient.
* Lists are a way to do array like stuff in a functional language, and free us from worrying about bounds checking.
* Pattern matching is mighty and powerful and makes functional languages great for writing compilers. And writing compilers is fun and good for the soul, right?
* Higher order functions are making their way into everyday languages and can improve code re-use.

Basic on up

ErrorNoInteger — Thu, 04 Oct 2007 15:23:50 -0700

I remember back in the good old days, I was interested in computers, and I really wanted to know how they worked and how to control them. I kept wondering how people made those creative applications I used every day on the computer. I picked up a book at the library and read it. I was thrilled and the stuff it taught me. It introduced me to something I had never known before. It was called computer programming. I learned BASIC, the easiest language I know, I read it several times, from front to back. Now I wasn't sure how to use these, or how to use them on a computer, so I wrote them down on notebook paper. I made a lot of them, my own programs, and some samples from the book I was reading. Then one day my brother told me of a program called "QBasic". When I began using it, and ran my programs, I was extremely thrilled at the moment. I used it for several years, making programs as I wished. Later, Microsoft Visual Studio came out, and I used it. I installed the Visual Basic environment. I wasn't very familiar with the layout as compared to QBasic, but it seemed a lot easier to use when I got the hang of it. I was even greater impressed that I was able to make windows and forms just like the crazy killer apps of the day. I strengthened upon this, but I eventually found some boundaries to which Basic could not go...

Are Internal DSLs Really Just Well Designed APIs?

Jonathan — Wed, 03 Oct 2007 09:19:40 -0700

Well, I figured I may as well make the first post in my PH blog vaguely controversial. If the title's not enough for you, then let me go on to suggest that the Bible has some useful advice in it for those of us trying to decode the continual stream of acronyms that the computing industry likes to throw at us.

"What has been will be again,
 what has been done will be done again;
 there is nothing new under the sun."
    -- Ecclesiastes 1:9

One of the things that amuses me most about the computing industry is how we seem to keep getting shiny new names for the same old technologies, perhaps just applied in a different problem domain or using a different language.

I have a computer science background, and one of my classes was on the subject of Distributed Systems. Shortly after taking this class, I decided it was high time I found out what on earth this AJAX thing everybody was going on about really was. And I came away saying, "OK, so we use JavaScript to make method invocations on an object that in turn makes a request to a server, which then responds to that request and then we use what is sent back to make changes to the page through some other set of objects...what's the new technology here?" And the answer is: there's not really much in the way of new technology. It's the same old client/server request stuff that got branded Web Services a while back, coupled with what we were doing without the client/server stuff and calling DHTML (Dynamic HTML) years ago.

Don't get me wrong here. I'm not saying that web services or AJAX are bad things. I have seen both used powerfully, and use web services to good effect myself. But in terms of the technology, they are nothing revolutionary. It's just a combination of formats and languages applied to a specific problem domain.

With all that in mind, I've spent some time trying to work out what the deal is with DSLs. DSL is short for Domain Specific Language. This is a (formal) language of some kind that is suited to a very specific task. For example, MathML is a domain specific language suitable for describing mathematical formulas. DSLs break down into Internal DSLs and External DSLs. Internal DSLs are just subsets of an existing more general purpose language, whereas External DSLs are languages of their own.

The advantage of an internal DSL is that you do not need to write your own parser for it, and you can use any of the features of the general purpose programming language amongst the domain specific bits. The advantage of an external one is that you are creating a language all of your own and have all the freedom associated with doing so. The advantages of one approach are the disadvantages of the other.

I see a lot of people talking about Internal DSLs in the Perl and Ruby camps, often with one side saying language X is better at it and the other pointing out that you can do the same kind of thing in language Y. The thing is, the more I look at the examples from both sides, the more I am left thinking: if it's an internal DSL, you are just using the syntax provided by the programming language, and therefore how is creating an internal DSL any different to just defining a nice interface to the module/package/whatever that you are working on?

Nice interfaces to modules and good API design are both of great importance. They make libraries and frameworks easier to learn and use by new programmers, and make the code more clear to those who are maintaining it. So if the whole DSL thing has just got people asking, "how can we use (or abuse) the syntax of our programming language to create a good interface to our module", I welcome it. But I'm failing to see anything new.