Sunday, June 17, 2018

AMD64/X86_64 General Purpose Registers

The 64 Bit registers consist of 16 general purpose registers, made up of the original 8 registers included in the original 16 and 32 bit CPU and still available in the 16 bit and 32 bit modes.

The original AX, BX, CX and DX registers are further subdivided into high-low pairs AH/AL, BH/BL, CH/CL, DH/DL, however the use of the high portion is not supported by all of the operations, which is indicated by those registers shaded in light grey in the tables below.

The registers are expanded to 64 Bit and are accessed by prefixing the original 16 Bit register names with 'R', as in RAX, RBX, RCX, RDX etc. in addition 8 new general purpose registers have been introduced simply as numbered registers R8..R15. The new registers also provide additional registers used to access the sub elements of the registers by adding B, W, D suffix to the register name to access the least significant 8 bits, 16 bits and 32 bits respectively.

In addition to the expanded registers set R8..R15, new registers SIL, DIL, BPL and SPL have been added in 64 bit mode to provide access to the least significant 8 bits of the RSI, RDI, RBP and RSP registers

The addition of the new registers and the improved uniformity introduced for accessing the sub elements of the registers have made register management much simpler. Code can be made more efficient by using the faster registers to store intermediate data, needing to spill over to slower memory less frequently.

Sunday, November 6, 2016

Cross Compile for Raspberry PI on Windows 10

Cross Compiling for Raspberry PI or other ARM based devices capable of running Linux, on Windows 10 using the "Window subsystem for Linux" (aka Bash on Windows) is now as simple as cross compiling on native Linux.

To learn more about the Windows subsystem for Linux and how to activate it you can follow the instructions here.

Once you have completed that you can follow these steps to install the toolchain required to cross compile for the Raspberry PI.

Step 1 - Make sure your environment is up to date
$ sudo apt-get update
$ sudo apt-get upgrade 
Step 2 - Install the development tools
$ sudo apt-get install -y build-essential gcc-arm-linux-gnueabi g++-arm-linux-gnueabi 
For the very basics, that is it...

Let's try build some code and get it to run on the Raspberry PI

Step 3 - Create a source directory

In the bash shell you can create a "source" folder in the user directory and switch to the directory by issuing the following commands
$ mkdir ~/source
$ cd ~/source
The first command will create a "source" directory in the current users home directory, the second will change the current directory to the newly created "source" directory.

Step 4 - Write some code

First we will launch the nano text editor, in the Windows bash shell, by issuing the following
$ nano test.cpp 
This command will open the nano editor and set the file name to "test.cpp". Enter the following code in the editor window
#include <iostream>
int main() 
   std::cout << "Hello from your Raspberry PI!" << std::endl;
   return 0; 

Press "Ctrl-X" followed by "y" followed by "enter". 

Now you should be back at the command prompt in the source directory we created earlier. Issuing the "ls" command should show that we have a new file called "test.cpp". 

Step 5 - Compiling using the cross compiler

Next, we can compile the code for the Raspberry PI using the following command  
$ arm-linux-gnueabi-g++ test.cpp -o test 
This will start the compiler, which will compile the test.cpp file and if you have entered the code correctly, create an executable binary file called "test". If you have any errors you can go back to step 4 above and use the same commands to edit the file and fix any errors you might have encountered. 

Assuming you had no errors, you should now have a binary file on your machine called "test". This is the executable that is ready to run on an ARM based device running Linux, like your Raspberry PI. We can confirm that it is indeed not compatible with the x64 architecture of your Windows machine by trying to execute the code as follow. 
$ ./test 
The application should fail to execute and give a messages along the lines of 

bash: ./test: cannot execute binary file: Exec format error. 

This is because the binary is not in the correct format for the platform you are trying to execute it on. We need to copy the binary over to your Raspberry PI and try execute the binary there.

Step 6 - Copy the binary to the Raspberry PI

I am going to assume that you already have your Raspberry PI on the network and have identified the IP address, if not you can use Google or Bing to go get to that point.

In my case, my Raspberry PI is on the network and has been assigned an IP address of

  Note:You need to replace the IP addresses below with the IP address of  your Raspberry PI.

To copy the binary from your windows machine to the Raspberry PI we can use secure copy (scp), this is a Unix/Linux command to securely copy files between two machines using a secure shell. The Windows subsystem for Linux makes these commands available to you "natively" from within the bash shell.

Enter the command below to copy the file from the Windows machine to your Raspberry PI (remember to change the IP address to the IP of your Raspberry PI)
$ scp test pi@ 
If this is the first time you are setting up a secure connection to the Raspberry PI from bash, either using scp or ssh you will be prompted to confirm that you trust the target machine, you can enter "yes" to have the host signature entered into your local known hosts file.

Note: If you took too long to confirm the host, the underlying connection might have been broken, in that case you can just reissue the scp command above.

Next you will need to enter the password, the default password for the "pi" user is "raspberry" which you can enter in response to the password prompt. When the command completes without errors, the binary should be copied over to your Raspberry. Let's go check...

Step 7 - Executing the binary on the Raspberry PI

From within the bash shell on your Windows machine, you can now ssh to to the Raspberry PI. If you prefer you could use Putty, but since we have the capability to use the Windows bash shell to do this I am going to stick with that. The next command will open a ssh session to your Raspberry PI, again, remember to use the IP address for your Raspberry and not the IP address in the example (unless of course your IP matches the on in the example :) )
$ ssh pi@
Next, you will be prompted for the password for the user "pi", enter "raspberry" and you should now have an interactive secure session with your Raspberry PI. You can identify that you are interacting with the Raspberry and not the local shell by looking at the prompt, it should be a bright green prompt with the following text.
pi@raspberrypi:~ $ 
If you see the above, you know you are now remotely interacting with the Raspberry. Entering "ls" command should list the "test" file, also in bright green, that you copied from the Windows machine.

Lets try executing the binary and see if we have more luck than we did when executing it earlier on the Windows machine.

At the prompt enter "./test", you should then see the following

pi@raspberrypi:~ $ ./test
Hello from your Raspberry PI! 

If you see that then it worked! You compiled a source file on your Windows machine, using the ARM tools to target an ARM based Linux distribution, copied the file to the target device and executed it. How awesome is that???

There is still much more to this, but this should get you started cross compiling on Windows for your Raspberry PI. Best of all, this will also work for other ARM based devices capable of running Linux, like the BeagleBone Black for example.

For a more complete experience, take a look at:

VisualGDB - Use Visual Studio to target a range of embedded devices and Linux devices
Visual C++ for Linux development - Use Visual Studio to compile and deploy to ARM based Linux devices

Tuesday, February 9, 2016

Learning a little TypeScript - Implementing a generic Queue collection

Not being much of a JavaScript guy, other than dabbling when I needed a little client side script, I thought I should probably join the rest of the world and move away from the comfort of C/C++ and C#. Taking baby steps I tried my hand at TypeScript first. I thought others might find my first attempt useful.

Wanting to try out classes and generics, I decided to implement a toy collection class. The snippet  is loosely based on the .NET generic Queue collection interface and implements a similar collection in TypeScript.

Without further ado, here is my very first TypeScript snippet.

And here is a quick and dirty sample showing how the queue could be used

Wednesday, July 9, 2014

Taking my hobby playing with embedded devices to the next level

I have been playing around with all sorts of embedded micro-controllers, ranging from the Atmel AVRs on the Arduino boards, to the powerful ARM Cortex processors running .NETMF and plenty of native code in-between. I recently decided I wanted to try my hand at FPGA, it looked totally foreign and it is not like anything else I had ever done.

All I can say is I am hooked, having the power to construct a processor or logic array to your liking just feels cool. I started off just over a week ago and I took it slow, implementing half-adders then full-adders until I eventually build a full ALU. My goal is to build a custom processor designed to run the Pascal PCode generated by the original UCSD-Pascal compilers.

So far I have not had much to show for it, everything toggles a few LEDs drives a few 7-Segment displays etc. Today I thought I would start playing with the clock management features, the thing with the clocks is without an oscilloscope you cannot really see if things are happening the way you expect. So I thought I would kill two birds with one stone. I will eventually need to generate video output and I need a custom clock to generate the right frequency to get the monitor to display the video data at the target resolution.

The Paplio board that I am using has a Xilinx Spartan 6 FPGA which is being clocked at 32MHz, I was able to synthesize a frequency of 64MHz, close enough to the 65MHz required to support VGA 1024x768 signal. This is not the limit, I am sure it can still go higher, I just have not tried it yet.

Here is a quick video of the system in action

Here is a link to the hardware that I am using

Saturday, September 8, 2012

New Gadgeteer Hardware and More...

Christmas came early... I ordered a bunch of kit that arrived yesterday, just in time for the weekend.

Development Boards
FEZ Hydra Basic Kit
FEZ Cerberus Mainboard
ST Development Board (STM32F4Discovery)

Newhaven - LCD Character Display
USB Client SP Module
RS232 Module
OLED Display Module (128x128)
Ethernet ENC28 Module
Extender Module

So far I have tested the OLED, it is much smaller than I expected but it is really a nice little screen. I can see it being very useful for low volume data that needs to be displayed.

The real fun so far was the Newhaven LCD Character display. I am a software guy, so having to solder does not make me feel comfortable. Don't get me wrong, soldering a few header pins on to a board is no issue.

The data sheet for the display refers to jumpers being set to select the communication mode for the display. but when I opened the device there were no jumpers to be found. A quick Bing search and it turns out that what they call jumper are really two pads on the board that need to be shorted. And those pads sit right next to the processor on the display controller.

When I finally decided to bite the bullet and drop a little solder between the pads, my 11 year old daughter came to check-up on what I was doing. She saw the tiny area I was tackling with what seems like a huge soldering iron and promptly offered to help, she suggested I put that the board under a magnifying glass, which I did and the end result I finally wrote a 'Hello World' .NETMF application.


Let me tell you I was quite relieved when it all worked.

Now to start playing with the STM32F4 Discovery board...

Saturday, May 26, 2012

Mini-Pacman on Miniature Arcade Console

I recently blogged about some of the stuff I am playing with on the .NET Micro Framework Gadgeteer platform. Kenny Spade from the TinyCLR community forums has kindly built a miniature arcade and put up a video of Mini-Pacman running on the arcade.

It is so cool to see your work move from a bunch of loose pieces lying around on a desk to something that looks so polished. Thanks Kenny!

Sunday, May 20, 2012

Playing with .NET Micro Framework and Gadgeteer

I am sure most people have heard about the .NET Micro Framework and more recently Gadgeteer. While I have had a keen interest for sometime, I never got around to purchasing any of the hardware until about 3 weeks ago.

Here are a few things I have done in my endeavor to learn more about the framework and the embedded devices.

The first application I developed was a little Pac man clone, I made the source for this available on codeplex just follow this link

More recently, I have been writing a ray-casting engine in the style of Wolfenstein 3D. Eventually I hope to release this as well, with a simple interface that others can use to develop games of this style.

Here is the latest video of the ray-casting engine.

I will post updates as I make more progress.

I am doing this on the FEZ Spider from GHI Electronics

Sunday, October 2, 2011

My first attempt at using the HTML 5 Canvas

Today I found myself wondering what kind of performance I can get with Javascript and the new HTML 5 Canvas. Looking for something fun to implement quickly I dug up some code for a demo I did of the Silverlight WriteableBitmap and started porting that to Javascript.

Now I am not much of a Javascript guy, in fact I can safely say that this is probably the most Javascript I have written, probably more than all other previous attempts at playing with Javascript put together.

So why am I writing about this if I lack so much experience, well to be honest, it is because I was actually quite surprised by the results and I thought it would be worth sharing.

I did the initial development using IE 9, and I was impressed by the performance, I hit the test page using Firefox 7, Google Chrome 14 and Safari 5.1. By far Firefox was the slowest, IE 9, Chrome and Safari all performed really well on my Window 7 box. So if you are viewing this in Firefox, try it with IE 9 and see if your experience is similar.

Tuesday, September 6, 2011

Practical Algorithms and Data Structures : Arrays–Part 1

To understand arrays, you first need to understand some basic concepts of how computer memory is managed. This is going to be a very high-level explanation with many over simplifications, basically I hope to share just enough to ensure that you don’t get lost when we get into the details of arrays.

You can think of computer memory as a collection of blocks which are placed sequentially one after the other in a row. Each block is uniquely identified by a number, this number in known as a memory address. For example, the first block would be at memory address 0 the next at memory address 1 and so on until you reach the last block.

Each of of these blocks or memory locations can store a single piece of data, this piece of data is known as a byte. A byte is made-up of 8 bits where each bit can have a binary state of either ‘1’ or ‘0’, 256 unique combinations of 1s and 0s can be formed for a byte. The interpretation or meaning associated to each of these patterns depends on what part of the system is looking at the data and how it has chosen to interpret the data. For example if your application is interpreting the data in the memory area as letters of the alphabet you might choose to interpret the bit pattern 01000001 as the upper case letter ‘A’. If on the other hand your application is treating the data as a numerical quantity representing someone's age for example, that same bit pattern would be interpreted as the numeric value 65. (See note 1 below)

More complex data can be represented by combining the patterns of multiple memory locations and interpreting those patterns appropriately. Let me give you an example.

Suppose you wanted to store a string of characters in memory, you could choose to store that string with a length prefix which indicates how many characters are in the string, and the subsequent memory locations would contain the bytes that represent each character of the string.

String in memory

The above image represents a string stored in memory with a length prefix of 5. Memory location 0 contains the bit pattern for the number 5 indicating that the next 5 memory locations contain the character data of the string. Memory location 1 contains the bit pattern 01100011 which has the numeric value of 99, but because we know this is a character of a string we will map this to the character ‘c’ (We are using an ASCII mapping here, see note 2 below), the ‘r at memory address 3 is encoded as 01110010 which represents the numeric value 114. This mapping is done for the 5 memory locations after the length prefix.

Similarly we need encoding mechanisms to store large numeric integer values, real numbers which can represent fractions of a whole number etc. As you might have already realized, the data stored in a single memory location can be quite limiting having only 256 possible values. That is not much to work with, it might be fine for storing your age, but what about the population of a country? As with the example above where we used multiple memory locations to store a string, a similar solution can be found for storing larger numbers that will require multiple memory locations which when interpreted as a whole represent a larger numeric value. For example, using 4 memory locations we have a total of 32 bits of data which gives you 4,294,967,295 unique bit patterns which covers us for the population for any country in the world, we need to go even bigger if we want to store the entire population of the world however.

The important thing here is that you know up front how to interpret the various pieces of information stored in the memory and how many bytes make up a single unit of information.

As you can imagine, these encodings get quite complex, fortunately you rarely need to deal with these low level details, for the most part the details are nicely taken care of for us by the higher level tools that we use to write our software.

The important take away from this post, is that more complex data representations can require multiple memory locations to store a single instance of data.

Prev – Introduction

* Notes:

  1. The bit patterns are not random, they follow a numbering scheme known as the binary system. Read more about this here.
  2. Interpreting the bit patterns as characters is done using a look-up table, in this case I have used the ASCII table which you can read more about here.

Saturday, July 9, 2011

Practical Algorithms and Data Structures : Introduction

Welcome to the first of hopefully many posts on Algorithms and Data Structures.

One of the areas of computer science that I have always felt drawn to is the study of algorithms. That is not to say that I have developed any kind of specialized expertise in the field, but I do find it tremendously interesting and continuously strive to expand on my understanding and ability to apply algorithms effectively.

For me at least, the best way to evolve my knowledge of a topic is to attempt to explain some aspect of the particular topic to someone else. On countless occasions I have found that by answering questions and having my explanations challenged, has enabled me to reach new levels of that “Aha” moment when suddenly a topic that I thought I understood just became that much clearer.

Now you might be wondering why I would even bother writing something like this, especially given all the material out there covering this specific area. Well other than my selfish motivation to learn more in the process, I have also realized that so many developers today lack the basics in terms of even the simplest algorithms. They might know the terminology and sometimes not even that, but as soon as you start probing on the specifics of the algorithms, how to decide which algorithm to use under which circumstance etc. things start to go sideways.

Why is it the case, that so many practicing developers today find themselves lacking in this area? Well I guess, the truth is that with all the excellent tooling and libraries accompanying  most languages and development platforms today, very few people need to actually delve into the depths of the algorithms and data structures they use. Everything is right there, got a list and want to find something in it, just call Find, Search, IndexOf or whatever function is documented to find an item in the list and be done with it. There is definitely nothing wrong with this, these libraries are professionally developed, robust and already used by thousands of developers so they are well QA’d. There is however tremendous value in having a good understanding of the algorithms and data structures you use.

If you understand your data, and you know what it is you need to do with that data, the next step is selecting the most appropriate data structure to store your data. Algorithms and data structures are tightly coupled together, often the data structures you use to store your data will determine which algorithms can be used efficiently on the data. While most data structures can be searched, what will vary is how efficiently that search can be performed, depending on the underlying data structure or even the ordering of the data in the structure. Having an understanding of the various data structures and the corresponding algorithms can help you choose the most efficient way to work with your data and ensure your software does not buckle under the pressure of huge data volumes just because you selected the wrong data structure and/or algorithm to manipulate and manage your data. Selecting the right algorithm for the job often it the key to a successful outcome, but to do that you need to understand the pros and cons of what is available to you.

With this series of blog posts I hope to share some of my learning's and at the same time gain a deeper level of understanding as we explore the algorithms and data structures together. I invite you to participate in this series, if you know a better way to implement something or have a better approach to explaining a specific algorithm, please share with us and help enrich our journey.

What are Data Structures?

Data structures are the containers that you use to store and manage the data for your application.

As we design and develop software, one of the decisions we need to make is what data types to use to store the application specific data. If we where developing a simple contact management system, in which we can enter contact information and later retrieve that information, we would need to define how the contacts would be represented internally within the system i.e. the data elements that represent a contact, such as first name, last name, address, email address, mobile number, date of birth etc. as well as the data types used to store each of these elements, how multiple contacts will be maintained and managed within the system, all of which help define the data structures that will be required to build a functional system.

However simply looking at the data requirements is not always enough, we also need to look at the algorithms we intend to apply to these data structures, how will we manipulate the data, perform searches, sort the data etc.. As we will discover through this series, the intended algorithms will have a bearing on the data structures we might select to represent the data in the system.

What is an Algorithm?

An algorithm is a recipe or set of instructions that can be followed to solve a specific type of problem.

Assume we have chosen to store our contacts from earlier in a list in which we can access each contact by walking through the list item by item, like paging through a book. We now need to find an algorithm we can use to search through the list to locate a contact by last name. How would you go about that? Given what we know about the data structure, the obvious solution would be to iterate through the list of contacts comparing the last name element to the search key. If you find a match you can stop the iteration and return the instance of the contact that was found, otherwise if you reach the end of the list and no match was found you return some indication that the contact does not exist. These steps describe what is known as a Sequential Search.

There are situations where using the simple Sequential Search algorithm might not be the best option and could severely hurt the performance of your system. For example, if the list in question contained a significant number of items and you need to perform frequent searches to determine the existence of an item in the list, this could quickly become a bottleneck. Every time we search for an item that does not exist, we will be iterating through the entire list just to determine that the item does not exist, in the best case the item we are searching for is found quickly within the first few items of the list, while on other occasions the item might only be found towards the end of the list. We will look at this in a little more depth in the section on Big-O notation.

Let’s look at one possible alternative, we could use a Binary Search. This algorithm can be significantly more efficient than a Sequential Search, especially in the worst case scenarios where the item being searched is either not in the list or it exists far from the beginning of the list. However, to be able to use the Binary Search, the collection of items will need to conform to the basic requirements of the Binary Search.

  1. The list of items must be sorted
  2. The list structure must support what is often called random access. i.e. we should be able to access item 83 in a list of 100 items without needing to iterate over the first 82 items.

Given the above constraints are met, for the moment we will ignore the cost of ensuring the data is sorted, while not insignificant, for the purposes of the discussion we will choose to ignore it for now, we can use the Binary Search algorithm to introduce some significant optimization.

Here is a quick introductory example of the basics of the Binary Search algorithm.

First you select the item in the middle of the list, in a list of 100 items that will be item 50. Now compare item 50 (the midpoint item) to the search key, if it is a match we can terminate the search and return item, if the search key is greater than the midpoint item then we know that, if the item exists, it must be in the second half of the list. We know this because the list is sorted, therefore if the the search key is greater than the midpoint item, if must be greater than all the items preceding the midpoint item. And visa versa, if the search key is less than the midpoint item, then a potentially matching item would be in the first half of the list. Can you see how with a single comparison we have eliminated half of the items to be searched?

Having determined which half of the list the item might be in, you can repeat the same logic on that subset of the data. Having narrowed the list of items down to a subset of 50, you can again select the midpoint item and compare it to the search key, which will either be a match or indicate that the search key potentially exists in the top or bottom half of the subset. After 2 comparisons we have eliminated roughly 75% of the items to be searched. You can continue until you either find the item or run out of items to search which would indicate that the item does not exist in the list.

We will cover both the Sequential and Binary Search in more detail later, for now I just want to use this to demonstrate how selecting the right algorithm for the job can make a difference and how the nature of the data might influence the algorithms you can use. And it also leads us into the next topic and that is Big-O notation.

Big-O notation

I am sure you have at some point seen or read about Big-O notation even if you did not know what it meant. If you spent anytime reading about algorithms you might have seen something like the following O(n), O(log n) or O(n3). And if you wondered what it all means, I will try to give a very brief non-mathematical description of how you can make some basic sense of this notation.

When selecting an algorithm there are a number of factors that you might have to take into consideration. For desktops or server based applications your primary criteria might be performance, where you want to select the algorithm that is going to give you the best performance regardless of the amount of memory the algorithm requires to be executed. On the other hand, on mobile devices you might be more concerned about the memory requirements of a particular algorithm. In either case, we need some way to represent this these characteristics of an algorithm, this representation needs to be simple enough that just by looking at it I can tell if one algorithm will perform better than another or if it will be more memory efficient without needing to read or understand the complex mathematical analysis of each algorithm. For our purposes we will focus on the performance aspect and discuss the memory aspect later when we work with actual algorithms.

Big-O notation gives us a concise notation that captures the performance characteristics of an algorithm over a collection of items. Basically we can see at a glace if the algorithm performance will degrade rapidly, linearly or gradually as the number of items in the collection increases. Of course as we saw earlier algorithms have best case scenarios as well as worst case scenarios, Big-O notation represents the average case, so looking at the Big-O for a Binary Search I can say that on average the Binary Search will out perform a Sequential Search. That does not mean it will always out perform the Sequential Search, remember, if the matching item is first in the list the Sequential Search will find it immediately, while the Binary Search will need to perform a few iterations before finding that the first item is the matching item, but on average we would expect that the Binary Search will perform better for real world searches.

Using Big-O notation, the Sequential Search would be described as an O(n) algorithm, where n represents the number of items the algorithm will be working with. If we searched a list of 10 items then n=10 and if we searched a list of 1000 items then n=1000. From this we can conclude that on average the algorithm performs linearly, if we double the number of items the average search time will double, so the relationship between the number of items and the execution time is linear.

How does that compare to our Binary Search algorithm, well without getting into the details now, I will tell you that a Binary Search is an O(log n) algorithm. This means that as the number of items increase the execution time increases logarithmically. Mathematically log(n) < n were n is a positive integer (see the table below), therefore we can say that Binary Search is faster than a Sequential search.

Lets look a quick analysis, if the item that I am searching for is the first item in a list of 1,000,000 items then the Sequential Search will clearly out perform the Binary Search which is going to jump to the middle of the list, see that the item is in the first half of the list and half that portion and so on for a total of 20 comparisons before locating the target item at the beginning of the list. However if the item being searched was the last item in the list then the Sequential Search would require 1,000,000 comparisons while the Binary Search worst case would not be more than 20 comparisons. So the worst case of the Binary Search of a collection of sorted items is 20 comparisons while the sequential search will exceed this worst case for when searching of any of the 999 980 that are after the first 20 items in the list.

What we have seen here is that the Sequential Search has a best case execution of O(1), that is constant time regardless of the number of items in the list, of course this is the absolute best case when you are lucky enough to have the item you are looking for be the first item in the list. While the worst case if the item is the last item or the item does not exist at all will be O(n) which is also the average case.

The Binary Search also has a best case scenario of O(1), that is when the item you are searching for happens to be the item in the middle of the list, in which case the item would be found on the first comparison, but the average case is O(log n).

n O(1) O(n) O(log n) O(n log n) O(n2)
1 1 1 0 0 1
10 1 10 3.32 33.22 100
100 1 100 6.64 664.39 10000
1000 1 1000 9.97 9965.78 1000000
10000 1 10000 13.29 132877.12 100000000
100000 1 100000 16.61 1660964.05 10000000000
1000000 1 1000000 19.93 19931568.57 1000000000000

Looking at the above table you see a comparison of some Big-O representations for various values of n. This should give you a feel for how one algorithm would perform relative to another based on the Big-O of the algorithm. The best general purpose sorting algorithms today are O(n log n) algorithms.

Given the speed of computers today, even the worst performing algorithms will appear to perform efficiently for small values of n. That is why it is very important to understand the volume of data that your system might need to work with and make sure you test with volumes that are representative of what you expect to see in the production environment.

When selecting your algorithms, make sure that you fully grasp the context in which the algorithm will be used and how that scope might change overtime as your system hopefully becomes more and more popular.

If you would like to see a visual representation of the table above take a look at my Big-O Visualizer. Note this application requires Silverlight 4.

Next: Arrays – Part 1