Posts Tagged ‘Programming’

C++ Cookbooks

Posted: March 13, 2011 in Programming Recipes
Tags: ,

Some people wonder how to start studying C++ in a professional way. I’m not a C++ guru but I love it and I’d like to improve my skills. With the purpose of doing it, I’ve studied a bunch of books and I’ve read some articles about C++ programming and designing. Anyhow, you can study all the books in the world but you must program and write your own applications, otherwise you’ll just know the theory!

I keep on studying books and articles but I strive to develop full applications in my free time. Currently, I’ve set up a small team of mad guys (like me) and we are going to create a videogame. This is a hard challenge but we want to get it.

Ok, I stop talking about me, I promise. Let’s talk about C++ and what you can do when you are at the beginning.

The first thing to do is being aware of your programming skills. If you want to have a very complete start (if you have time), I’ll recommend you “Programming from the Ground Up”. It begins with Assembly and goes on dealing with C. If you read it, you’ll get acquainted with programming from the low-level – Alas, thing forgotten by the most part of modern programmers.

To have a quick start with C++, read Accelerated C++, by Andrew Koenig and Barbara E. Moo. This is one of the best introductory book about C++, covering basic concepts, STL, exceptions, OO programming, good practices, etc. It is really fast, giving you the chance to begin writing programs immediately. Reading it, you’ll be aware of the primary memory issues, operators overloading and their related troubles, inheritance, etc.

Next, you’re ready to toughen your proficiency studying Meyers’ books:

  • Effective C++
  • More Effective C++
  • Effective STL

Overall, in these books you’ll find more than 130 ways (items) to improve your programs and designs. Tips, tricks, idioms, patterns and other recipes you won’t be able to live without!

At this point, you should have an intermediate understanding of C++. Bear in mind you must get your hands dirty and write your own programs. Keep on hand the reference of the C++ Language Library (for example, this).

I think of this game like a sport team (say, a Volleyball team) trains before the beginning of the championship: during the first months, the players train their body, their mind and their skills (as you’ve read Koening’s and Meyers’ books); next they are ready to start playing some matches (as you start writing you’re own applications). During the championship the team keeps on training, but this time it should focus on its flaws or specific matches (for example, getting ready for the match against the leading team). Thus, you can keep on studying books, maybe focusing on your weaknesses and particular troubles you’re handling.

Do not forget Stroustrup‘s (the father of C++) books such as The C ++ Programming Language (the Bible of C++) and The Design and Evolution of C++. In addition to these, you can read:

  • Efficient C++: Performance Programming Techniques, by Dov Bulka and David Mayhew;
  • Josuttis’ The C++ Standard Library – A Tutorial and Reference;
  • Exceptional C++ and More Exceptional C++, by Herb Sutter;
  • Scientific and Engineering C++, by John J. Barton and Lee R. Nackman;
  • C++ Template Metaprogramming: concepts, tools, and techniques from boost and beyond, by David Abrahams and Aleksey Gurtovoy;

Keep in mind to search the Web for topics your books don’t cover. If you’re developing a new program, you should be fast and reliable and, perhaps, you don’t have time to study entire books. Never forget my advice: write your own programs! While writing a program, if you get aware that all you have done is wrong, then you’ve learned something new!

Programming Recipes

Posted: March 9, 2011 in Programming Recipes
Tags:

Hi again! When I wrote the first post of “Optimization Pills”, I didn’t realize that I’d made a terrible mistake…I had not created a “Programmig” section! Here it is! In this category I’m going to show you some “programming recipes”.

What is a “programming recipe”? – you grumbled.

I employ this expression to talk of a bunch of programming stuff: tips, tricks, books, idioms, etc. All of these things are valued when you write an application.

Suppose you’re cooking and you’d like to amaze your guests, serving some tasty dishes. Which are your possibilities?

Sure, you can think up something special, using several ingredients and precious spices. This takes time and requires creativity. But you tumble to have no time, the dinner begins in three hours and you’ve just sliced the bread!

Another choice is using a recipe, which describes all you need, including the cooking time and some comments (if you are lucky, you’ll find other intersting information like the benefit you’ll get). You just have to look for the recipes you consider appropriate (bear in mind what your guests like, if someone is allergic to some ingredients, etc) and mix the ingredients. Yum, my mouth waters!

The last choice (I write down) lies in cooking ready meals! If you’d like not to be discovered, assure none of your guests eat the same at home! This choice is really fast and safe (unless you’re not even able to heat up some pasta!).

Ok, I hope the comparison is quite clear, despite it is rough: the dinner is your application, guests (and their “preferences”) are the requirements and dishes are the “components” of your program. This components are linked in some way (generally so are the dishes in a “special” dinner). Ready meals refer to libraries or something available you can employ. Cooking a dish is the same as solving a problem in your application.

How to cook? Or rather, how to program?

Tips and tricks are excellent companions, don’t ever forget them. They are like advices your mum gives you, such as “use the bicarbonate to clean the fruits”. They can refer to either specific or general situations.

Idioms are low-level (standard) techniques to solve problems (generally simple tasks) using a programming language. Knowing the idioms associated with a programming language and how to use them is an important part of gaining fluency in that language. Think of an idiom as an action you do frequently, like “boiling the water” or “browning the onions”.

Read books to gain more knowledge of programming. A book can talk about tips and tricks, idioms, patterns, etc. In this context, a book may reference other books in which you’ll find advanced or related topics.

A library can make life easier for you, but at times it’s unuseful or unfitting. For example, you need high performance and the library “ABC” is too modular to run quickly. Sometimes the most effective way to use a library is to realize that other approaches are superior.

A programming recipe is anything useful to solve a programming issue and it includes lots of things, as you’ve just read! But keep in mind: you won’t find a recipe or a library to solve all your problems. You’ll have to use your brain and creativity, looking for new ingredients, pots, spices, etc. Your best friend is your experience, maybe enhanced by all the recipes you know!

Optimization Pills

Posted: February 10, 2011 in Optimization Pills
Tags: , ,

In this category, I’ll talk about optimization issues (especially in C++), trying to be pragmatic. What I’m going to show I’ve learned on my own, only a little part comes from the university. When you are there, it is not important to achieve good performance, then don’t get angry if you hear something like “efficiency is beyond this class” or “the DBMS will deal with optimization“.

That’s ok if efficiency does not matter to your application, if you’re developing another Java webapp with some cool functionalities and you don’t even know what a cache is and why the CPU has some registers.
The bad news is that if you deal with real-time systems, graphics, scientific computing, etc, you can’t waste time. You can’t afford it! You need your code to be more efficient, you need some tricks and best practices. Next, if you become capable, then you’ll be able to work out your own tricks. But keep in mind: you should know all about the CPU, the memory and other useful stuffs.

If you wanna step into the light, begin reading this paper: What every programmer should know about memory.

Furthermore, you can study on High performance computing, by K. Dowd and C. Severance (published by O’Reilly in 1998), Computer Systems A Programmer’s Perspective by R.E. Briant, D. O’Hallaron (published by Prentice-Hall in 2003). These are only a couple of titles. Search the Web for more resources.

Some applications require you to perform a job as soon as possible, meeting some external constraints about memory, time and quality.

No “Java.optimize” import or magic buttons to push here. Get ready to write code that is already optimized and if you can’t, try at least to optimize it next.

Let’s start with a simple question, I have these two C codes for matrix-matrix multiplication:

for(j=0;j<nn;j++){
	for(k=0;k<nn;k++){
		for(i=0;i<nn;i++){
		   c[i][j]=c[i][j]+a[i][k]*b[k][j];
		}
	}
}
for(i=0;i<nn;i++){
	for(k=0;k<nn;k++){
		for(j=0;j<nn;j++){
		   c[i][j]=c[i][j]+a[i][k]*b[k][j];
		}
	}
}

I wonder if it exists an ideal order for accessing the elements, if the answer is yes, I wonder if it depends on the language. I give you two page-refresh time to think about it! If you’re able to answer these questions, you’re able to figure out what the fastest code is.

I’ve made some tests using an Intel Core Duo 2.0 GHz, employing gcc 4.0.1. The matrices are 1024*1024:

loop order i,k,j : 2.29”

loop order j,k,i : 32.2” !

What’s the matter? I’m afraid it’s the fault of the cache. Let’s use cachegrind (a tool of valgrind) to simulate the cache. This is the j,k,i loop:

and this is the i,k,j loop:

Yes, it depends on the cache misusing. That’s because in C a matrix is stored by rows (because a matrix is a vector of vectors) and this is also a dependency on the language:

If you make the most of the cache, you can avail of the Principle of Locality: temporal locality refers to the reuse of specific data and/or resources within relatively small time durations. Spatial locality refers to the use of data elements within relatively close storage locations. In this context, the stride is the distance between two subsequently accessed elements. If you have unit stride, I have good news for you because you’re caching well.

This is a rough list of the data flow when your CPU has to read something:

1. Looking for the data;

2. L1 Cache look up (about 1-5 cycles);

3. L2 Cache look up (about 20 cycles);

4. Reading from the RAM;

5. Copying from the RAM to L2 cache (more than 100 cycles);

6. Copying from L2 cache to L1 cache;

7. Copying to the registers.

If you find the data in the L1 cache then you’ll jump to 7, saving a lot of time!

There exists a programming field called cache-friendly programming, focusing on the good using of the cache for achieving excellent results with high performance. This style of programming often leads to a bad code readability or other modifiability issues, then choose your battles and keep in mind your requirements.

I hope I’ll have time to write about cache-friendly programming (with cache blocking, padding, and other techinques), pipelined computing, out of order execution and how to take advantage of inner parallelism, with some tricks like loop unrolling, strength reduction, loop merging, loop splitting, function inlining, etc.