Programmers Dojo

I had a buddy ask me about learning the Scheme programming language... so I figured I'd write a blog post about it! First a very short history. A long time ago (in 1958) there was born a language called Lisp.  Lisp is actually the second oldest high level language but that's a different post.  Lisp split into two main branches Common Lisp and Scheme. Common Lisp is quite large and has lots of features including a full OO system.  Scheme on the other hand is as stripped down as is practical.  For comparison the Common Lisp spec has ~1100 pages while the Scheme R5RS spec has 50 pages. That being said Scheme has low level primitives which allow you to build high level primitives. There are lots of great resources out there for learning Scheme and I'm going to list a few here. Textbooks: The Scheme Programming Language The Little Schemer The Seasoned Schemer Structure and Interpretation of Computer Programs  - AKA: SICP Free textbooks: How to Design P

The  top500 list has been swamped by x86 machines over the last several years.  Anyone who knows me is aware that I am NO fan of the x86 ISA. Somewhat heartening is that the most recent list seen a resurgence in other architectures.  The Power architecture from IBM has been a fixture on the list for a long and is still a strong contender even though it has fallen to No. 12 from No. 9 last time and No. 1 in November of 2007. A Sparc machine has captured the No. 1 place this year and is actually as powerful as the the No. 2 through No. 6 systems combined. The Chinese MIPS based Loongson processor is starting to make some noise and the Dawning 6000 is reported to eventually reach a Petaflop in computing power. One other note is that an increasing number of machines in the top500 list rely heavily on GPUs.  The No. 2 machine on the current list, the Chinese Tianhe-1a machine, is comprised of 14,336 Intel Xeon processors and 7,168 Nvidia Tesla GPUs. Now I guess we just hav

Programmers are artisans.  We are masters of tools... or at least should be. I see many programmers fail to focus on their tools.  The programmer himself is the most important part of the equation right?  Well, yes, but that doesn't mean tools cannot amplify his or her abilities. Even the worlds greatest carpenter will be hampered with substandard tools. There are a set of common tools that every developer should be familiar with.  I am going to focus on C/C++ Unix development but this list is easily translated into other environments. 1. Your editor. This is where you are going to spend most of your time.  On Linux you have a many choices but every developer should know one of Emacs or Vi.  I'm an Emacs guy so I won't talk about Vi much, and besides... there is nothing your OS can do that my Emacs can't. :) Editors are highly sophisticated programs with huge arrays of features.  The better you are at running your editor the more time you will save yourself i

Now you don't just have to imagine! http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Jeff Vitter is the provost and executive vice chancellor and the Roy A. Roberts Distinguished Professor at the University of Kansas. I just stumbled across his page and found a great book on external memory algorithms and data structures external memory algorithms and data structures. IE: algorithms and data structures to use when your dataset is too large to fit in main memory. He has many other papers on his site including several on external memory graph algorithms. Here's the link... http://www.ittc.ku.edu/~jsv/Papers/catalog/

Here is a great article about tackling a difficult problem. http://softwarecreation.org/2011/stuck-on-a-big-hard-programming-task-read-this/

So, If we were to calculate the first billion primes how much ram would we need? At the end the primes won't fit in a 32bit integer.  If we store them all in 64bit integers we'd need 8GB. Even if they all fit in 32bit integers we'd still need 4GB of storage just to store the list. Seeing at my little machine has 4GB ram that isn't going to work either. How about just storing the intervals between primes? For the first primes (2, 3, 5, 7, 11, 13, 17) we would store (2, 1, 2, 2, 4, 2, 4) Using a byte for every interval less than 128 and a short for the rest lets us store the first billion primes in just about 1GB.  Now that we can do! Maybe we can do even better though...

Our next version works just like the previous sieve but works on a segment of the number line at a time. That might be why it is called a  segmented sieve . Now we are sieving multiples of the primes from 1M numbers at a time, adding those primes to the list and then moving on to the next 1M numbers. I hit 140M primes in 60 seconds on my box... but now I run into a new problem.  This version of the sieve quickly consumes all the memory in my box and slows to a crawl.  To progress we will need to find a more efficient way of storing the primes we have found.

I've implemented a basic sieve to see if it does any better than trial division. While trial division found the first million primes in 8.28 seconds the sieve does the same task in 0.84 seconds.  That's a little better! Running the sieve on the range [2..1,000,000,002) yields 50,847,534 primes in 78.14 seconds.  I'm currently storing a byte for each number so that means I'm using 1GB ram.  We can't just keep increasing the range because we will eventually run out of memory.  Even storing a single bit for each number (we only need to know if it has been crossed our or not) would only divide this by a factor of 8. Perhaps we can work on a section of the number line at a time?

Another way to generate a list of primes is through the Sieve of Eratosthenes . Essentially you create a long list of numbers starting at 2. 1. Set p equal to 2.  This is your first prime. 2. Cross out every pth number because they are all divisible by p. 3. The first number after p which hasn't been crossed out is the new prime. 4. Repeat from setup 2. As an example lets take the number line from 2 to 10. list = 2, 3, 4, 5, 6, 7, 8, 9, 10 1. p = 2 2. list = 2 , 3, 4 , 5, 6 , 7, 8 , 9, 10 3. p = 3 4. goto 2 2. list = 2 , 3 , 4 , 5, 6 , 7, 8 , 9 , 10 3. p = 5 4. goto 2 2. list = 2 , 3 , 4 , 5, 6 , 7, 8 , 9 , 10 3. p = 7

Using the list from an earlier post here is a simple prime generator. trial_division.c This will generate one million primes in around 8 seconds on my machine.  Not bad but I think we can probably do better.

As promised, another graph but at a larger scale.  This should give some general idea for real performance on desktop class machines. I think I might attempt an out of core implementation of graph500.

Quick graph I created of the reference graph500 implementations and my bgl implementation on my home box. The data sizes are small enough that we see heavy cache effects.  I'll run another set at the larger graph sizes so that we can get a better picture of relative performance.

Because I don't have enough to do... I decided to start trying to implement the graph500 benchmark in the boost graph library and then the parallel boost graph library. I've got a very simply implementation working using an adjacency_list and a BFS visitor but I'm sure I can do much better. On my box: seq-csr at scale 20 is ~3.5e+07 TEPS adjacency-list at scale 20 is ~5.0e+07 TEPS (TEPS: traversed edges per second) I'll work on this one a bit more and then try a compressed sparse row graph.

Found on  Lambda the Ultimate  ( a great programming languages blog btw ) A great article  on programming languages through history and the truth of their claims. From the article: While still a relatively young field, computer science has a vast body of knowledge in the domain of programming languages. When a new language is introduced, its designers make claims which distinguish their language from previous languages. However, it often feels like language designers do not feel a pressing need to back these claims with evidence beyond personal anecdotes. Peer reviewers are likely to agree. In this paper, we present preliminary work which revisits the history of such claims by examining a number of language design papers which span the history of programming language development. We focus on the issue of claim-evidence correspondence, or determining how often claims are or are not backed by evidence. These preliminary results confirm that unsupported claims have been around since t

C Craft  is a great article about C including discussion on the good, the bad, and why you can't eat just one. Quote from the preface: Let me open with a disclaimer. What follows is an unabashedly opinionated diatribe certain to offend many programmers. Craftsmen inevitably grow defensive of their favourite tools and practices. Rather than respect this natural sensitivity, I will exploit it, shamelessly intensifying the vitriol for attention. I care little whether one applauds or deplores my views; I mainly want my audience to feel compelled to read on. However, I try to be informative as well as incendiary. Whether one finds my statements profound or unsound, whether one abhors or adores my examples, and whether one is amused or bemused by my observations, I hope one leaves wiser.

For our list of primes we need a list (naturally).  The best way to understand data structures is to implement them in a low level language.  Since I don't feel like inflicting ASM on everyone (although I do like assembler) we will use the next best thing.  C Out list needs a data element (the found prime) and a pointer to the next element. In C that looks like this. struct prime_elem_s {   uint64_t prime;   struct prime_elem_s *next; }; typedef struct prime_elem_s prime_elem_t; We define a structure containing the current prime and a pointer to the next element.  Then we define a type prime_elem_t to refer to that structure. In this case we want to add elements to the end of the list so we will also need a tail pointer.  We will create a list header which will keep a head and tail pointer as well as the number of elements in the list. typedef struct {   uint64_t length;   prime_elem_t *head;   prime_elem_t *tail; } prime_list_t; Now we can write a function whic

I like to do small programming exercises to keep my skills sharp.  Unfortunately I sometimes get a little carried away with them. Problem: generate a list of primes numbers. Sounds simple right?  Well lets start to look at this.  First lets define what prime numbers are.  A prime number  is a number which is divisible by only itself and one.  A simple way to test if a number if prime is by  trial division .  To test to see if a number is prime you check whether it is division by any prime less then the square root of that number. The general algorithm for finding the list of primes by trial division is therefore the following. list of primes = {2, 3} for each number begining at 4   check to see if it is divisible by any prime less then the square root of number   if number is prime then append it to list of primes Well go through a sample implementation then see what we can do to improve it.

And now for Big-O notation.  It's not about mecha and it involves math... don't worry I'll keep the math light. Big-O notation is a measure of an algorithms scaling based on input size.  Every operation on a data structure is an algorithm and Big-O lets us know how expensive they are going to be. As an example lets look at a stack of cards. Picking the top card off of a stack of cards takes the same amount of time if there are 6 cards in the stack or 600 cards in the stack.  This only every takes 1 operation regardless of the size of the stack so this is O(1).  The operation is constant.  Even if the stack was in a box which needed to be opened first, hence taking 2 operations, this would still be O(1) because it doesn't grow with input size. Finding a specific card in the stack is more difficult in a stack of 600 than in a stack of 6 however. On average you have to look at 3 cards on the stack of 6 and 300 cards on the stack of 600.  This means that on average you

Now for a forest of trees. Trees are likely the most varied of all data structures.  There are specialized trees for applications in computer graphics, astrophysics, engineering, text processing, databases, and compression (just to name a few).  Trying to categorize trees into a small number of bins is somewhat pointless but I'll describe some of the broader types. First some terminology. The top of the tree is the root.   This is the only node in the tree which has no parents. The parent of a node is the node which is higher in the tree.  A node will only ever have one parent. The children  of a node are all the nodes which are connected and one step lower in the tree. An interior  node is one which has both a parent and at least one child. A  leaf  node is one which has no children. The height  of a tree is the distance from the root to the lowest child. The depth of a node is the distance from the root to that node. Now for some distinguishing characteristics of trees. What

Hashes begin with an array.  That array is indexed with a mathematical function called a hash function.  Since the hash function is based on the key of the element you can jump "close" to the right element very quickly. The main distinction between types of hashes is in how they handle collisions. In a closed hash you iterate through the array to find the next open slot in the array. In a chained hash there is actually a linked list in each slot in the array.  Each element is simply added to the list. Both types of hashes have pros and cons but I'll elaborate those in a later post.

Lists are another very basic data structure.  Despite that they are actually quite varied. Essentially a list consists of blocks of memory linked together with pointers.  How they are linked and how they are accessed determines the type of list. The first distinguishing factor is the number of links.  If there is only one link this is a singly linked list.  Singly linked lists can only be traversed in one direction, but are quite small because they only have one pointer.  Lists with both a forward and back pointer are called double linked lists.  These lists can be traversed both forward and backwards.  Also you can easily delete an element from the center of a list since you have pointers to both the last element and the next element.  Finally there are lists with more than two links.  They generally allow you to traverse your data in more than one way and are only used for specialized purposes. The second distinguishing factor is the location of the link.  If the link is stored

Arrays are one of the earliest data structures.  They are essentially just a block of memory which is accessed by offset.  Despite their simplicity there are still several broad categories each with their own sets of algorithms. Is the array a fixed size or can it grow as you add elements to it? A fixed size array is called a static array and one that can grow is called a dynamic array. Are the element all of the same type or can they be different? If they must all be the same type then the array are called homogeneous.  Otherwise it is a heterogeneous array. Finally, how many dimensions (subscripts) does the array have? For example, a 2 dimensioned array is a matrix. The number of dimensions doesn't change the structure of the array but changes the way elements are accessed. 

For our purposes I will propose 5 classes of data structures.  These being the array, list, tree, hash, and graph. Arrays Arrays are one of the most basic data structures and are characterized by direct access to every element in the structure.  It is easy to picture them as a line of numbered buckets where you can place an element into or remove an element from any bucket. Lists Lists are another very basic data structure.  In a list each node has one of more connections to other nodes.  Access to the list is only at one or both ends.  From any given element you can access any element which you have a connection to.  Here is an example of a simple list. Trees Trees are similar to lists in that each element has connections to other elements but in a tree the connections are more structured.  Each element in a tree can have children.  The number of children an element can have is an important property of a tree.  The top element in a tree is called the root.  The root in the

Like a dojo I hope this blog to be a place of instruction and hopefully study. The primary focus will be on data structures, algorithms, and programming languages.  There will be lots of programming problems thrown in and likely a few rat holes to who knows where. Like anything else improvement requires practice so I encourage you to work the problems. The first post will be an introduction to basic data structures followed by an exploration of the main branches of data structures.  Then we will implement some of these in a few languages to see the differences the programming language makes. Please feel free to comment, criticize or request and I'll see what I can do.