Why inst your code 100% bug free, did you even test it?

In computer science there is a well known theory about testing and the intractability of obtaining 100% certain proof of bug free code. To summarize it "Testing can never prove that software is free of all bugs"

Explaining that it is impossible to do to the Layman and beings of lower standing such as high paid wild eyed, foaming members of upper management in tailored suits who think that they require a megaphone to be heard. Can be an entertaining experience..

Come to think of that have you ever had the experience of a ticked of manager screaming at you and all you can think about is how much he looks like 2 year old child having a tantrum in a store while the parent quietly ignores them and continues to shop... So you sit like the adult, waiting, counting the mans heart rate by the huge pulsing vain in his forehead.. Wondering the whole time if your going to need the AED from down the hall or not....

By now his rampage is pushing that last of the oxygen out of his system and he is starting to turn that deep shade of purple and you know that he has to take a breath soon so you get ready and as he sucks in that life giving air you shoot off "Oh.. i sent you an email about that 2 weeks back boss.. you did read it right?"

And then it suddenly dawns on him that the unread mails from you between his playboy subscription renewal and the face-book update messages might have been important... As the oxygen rushes back into his system his face turns a sudden bright red your are left eternally wondering if he actually blushed or if it was just his flesh re-oxygenating...

Ahh give the man a break. The truth is he doesn't understand crud...he knows it... we know it.

His high paid job is all about making promises about stuff that he doesnt fully understand, talking about the work that you are doing and listening to you dribble on about the big O complexity of the search functions... And try as he might to listen to you all he can think about is that hot blond from last weekend... So now he is pissed because he thinks you deliberately lead him to the cliff edge that he just fell off and he is trying to swim back up through the air like wile-e coyte...

The reality of the situation is that this is neither good for you or him. So re-educating the boss is the best course.. the way i seem to have had the most success explaining the inability of testing to find all bug is by a coin flip game.

Consider software to be a set of coins (2 or more). The running of software is a coin toss. And bugs are when all the coins show heads. SO testing the idea of tossing the coins until you get all heads and find a bug.

Now with this in mind, walk him through a "trivial piece of software" ie a game with 2 coins. Explain to himvthat the chance of finding a bug is 1/4 so it will take about 4 tries to find it. Yes i know "4 tries" is not really accurate but kept it simple alot of people don't get or care about the mathematical background to the average.

Then expand "a 3 coin piece of software" which has a 1/8th of a chance to find a bug and therefore it will take 8 tries to find a bug. Make certian to pound home that fact that the size of the program causes an exponential growth in the cost and time of testing.

Then you hit him with that fact that your program is really something that is thousands of coins big and it would be somewhat far out of his budget to have it all tested so that it is truly 100% bug free. And there you have the seed of knowledge.. at least until the boss drinks his next set of neurons into oblivion..

Later on you you can take this metaphor a bit further by explaining that
* directed testing is like weighting the coins to come out to a point that you think has bugs
* coverage and expensive coverage tools all are about recording outcomes of the coin toss so that we can tell what % of all the possible results we have seen and take a guess at when to really stop testing.
* etc etc...

C++11 lockless queues

I have been messing around with the new c++11 threading in order to write a post on it... as per usual i ended up side tracked on something else.. while coding it i got thinking about the lockless vs lock implementations. Basically lockless implementations require you to design to very hard restrictions. They are "write mastering" and "obstruction free updating"

Write-Mastering
Write Mastering is where a data variable is updated by a single thread. Its often surprising how easy this is to do. Eg for a Queue the head is mastered from the producer side and the tail is mastered from the consumer side. (this is the example below)

Obstruction-freedom
When write mastering is not possible an obstruction-free check can be used This technique doesn't explicitly lock a data structure but instead uses a pair of "consistency markers" that are updated the sequance of read, update check 1, copy, copy update, (reread)check, write back copy(or rollback), update check 2.

To fully explain it: When an update is planed the first consistency marker is compared to the second. If they dont match enter a spin lock until they do. If/When they match the structure is free for an update. The first marker is scrambled and written to something new. The update proceeds on a copy and once its done the markers are rechecked to see if they are still scrambled as the thread choose. If both markers are cleared then nothing else changed them so then the update writes back the data copy and then updates the secondary marker to match the first. If the compare fails then the updated copy is tossed and the process starts again.

Lockless designs tend to be big cpu and memory wasters when they get into the lockless spins or are constantly clashing over updating shared structures. As a result the system running them should be balanced, tuned and as large as possible so that there is always data ready to be processed in each thread with as few conflicts as possible. You can get a taste of how cpu intensive they are by running the following example and watching your CPU hit the roof.

//complie with 
//g++ -std=c++11 lockless_queue.cpp -o lockless_queue.exe
#include <stdint.h>
#include <thread>
#include <iostream>

class LocklessQueueSys
{
  enum { size=1000};

public:
  LocklessQueueSys() :
    head(0),
    tail(0)
  {}
  
  void producer()
  {
    uint32_t count= 0;
    while(1)
      {
 while(((head+1)%size)== tail); //spin lock
 msg[head] = count++;
 head = (head + 1) % size;
      }
  }
  
  void consumer()
  {
    uint32_t expect=0;
    while(1)
      {
 while(head == tail); //spin lock
 if(expect != msg[tail])
    std::cout << "Error:" << expect  <<  "\n";
 if(expect%10000000 == 0)
    std::cout << "check:" << expect  <<  "\n";
 expect=msg[tail]+1;
 tail = (tail + 1) % size;
      }
  }
private:
  int32_t msg[size];
  int32_t head;
  int32_t  tail;
};

int main()
{
  //Use a member function in a thread
  LocklessQueueSys x;
  std::thread tpro(&LocklessQueueSys::producer, &x);
  std::thread tcon(&LocklessQueueSys::consumer, &x);
  
  tpro.join();
  tcon.join(); 
}

C++11 Delegating Constructors.

Another much needed improvement to c++ is the problem of code reuse in constructors. Often you where forced to create an "init" function and call that from the body of the constructor. What this means is that you are effectively default constructing the member variables of the object and then re-initializing them to setup them uin p the common "init" function.

The new standard fixes this by allowing Delegating Constructors. Basically one constructor can now call another one from the same class in its place.

Heres an example:

//compile with  g++ -std=c++11 $< -o $@
#include <iostream>

class DelgateConstructor
{
  std::string str_;

public:
  DelgateConstructor(char* s) : 
    str_(s)
  {
    std::cout << "Working...\n";
  } 

  DelgateConstructor() :
    DelgateConstructor("Here we are") 
  {
    std::cout << str_ << "\n";
  }
};

int main()
{
  DelgateConstructor whatever;
}

This results in this output:

Working...
Here we are

fixing a lost ubuntu unity dash

Gahh... blue screen of death was a blessing.. unix systems really can get themselves in all kinds of crazy twists. I have been trying out that various media center software for ubuntu lately... Its bad worst and just plain ugly.. Mythtv, freevo ... nothing just works nicely they have trouble doing the basic of playing an avi from a hard disk, or booting up with out destroying the monitor settings if the TV is powered down... out of all of it the one that works the best is vlc... surprise surprise.. Im on the vague of setting up a web server hacking some php together that talks to a telnet interfaced vlc deamon that boots up at start up... and calling it a day...

Anyway back to the point.. playing with this stuff tends to brick your box real quick. basically the lot of them are too invasive and over bloated with addtional power features while neglecting the basics... On several of my trials i lost the unity dash and menu-bars here is how i was restoring it.

Punch ctrl+alt+f1 if you cant get a terminal(might be safer to do it here anyway) then run

unity --reset
sudo restart lightdm

Punch ctrl+alt+f7 to jump back to the GUI interface and watch/check the restart..

May take 1 or 2 tries and its a little slow and sometimes get stuck doing the --reset.

c++11 lambda

c++11 lambdas

Lambdas are an excellent and long awaited addition to the c++ language. Lambdas where simply not possible before but the Boost lib offered a rather passable set of macros that let you get away in-lining a kin of lambda. (basically it was a series of functional objects)

The lambda syntax however makes my skin itch a bit. It is yea another reuse of the bracket characters - [](){} - and one that is potentially lowering the readability of the code and introducing coding errors as a result. I would have preferred something a bit more clear and obvious.

Firstly the basic lambda syntax is [capture](parameters)->return-type {body}. This is often short handed the most basic form when people blog and type about it which is []() { .... }


The first [] pair forms a "capture". The capture is run one time at and in the context of the lambdas creation(ie the point where you put the code). There several convenient shortcuts that grab the various variables from the current context automatically. Consider these to be members (and constructor params) of the resulting lambda object.

The next () pair forms the "parameters" these are the same as the parameters of a function definition. This resembles the operator(...) function call of a functional object or the parameter list of a function pointer. Note that these ARE surprisingly optional, but generally they are not left out.

The difference between capture and parameters is rather subtle (or obvious depending on your point of view or experience with it to date). It can at can seem like overkill or just outright fluff when you are constantly using lambdas in the local context. However the key point to realize is that if you pass the resulting lambda out of the current context without executing it then the "capture" has already completed for the context that you made it in and passed it out of. As a result the parameters in the capture must still be IN CONTEXT at the point of the Lambdas actual execution (or the capture was made by value). Parameters on the other hand are filled in when the Lambda is actually executed.

The -> forms the return type. It is optional and often left out. However it can become quite important when templates are used with lambdas otherwise the compiler can get terribly confused with which of the specializations are supposed to be put in place. I assume this is just be a problem with the maturity level of the current gen of c++11 compilers.

And of course the {} forms the body of the code. The same scoping rules apply here as if you coded the object as a completely separate member function of a functional object. So keep in mind that you can not reach outside to variables that where not passed in through the capture or params.

Ok an example: The little known summing of numbers.. zzZZZ.. ha wadaimiss...

// comile with 
//  g++  -std=c++11 lambda.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

void examplePassByValue(int* start, int* end)
{
  int stuff[]={1,2,3,4,5,6,7,8,9};
  int sum = 0; 
  std::for_each(stuff, stuff+(sizeof(stuff)/sizeof(int)), [sum] (int v) 
    {
      std::cout << v << "\n";
    // This is passed by const value (os its BAD.. if you try to modify it.. )
    //sum += v;
    });
}

void examplePassByRef(int* start, int* end)
{
  int sum = 0; 
  std::for_each(start, end, [&sum] (int v )
  {
    std::cout << v << "\n";
    sum += v;
  });
  std::cout << " sum is : "<< sum << "\n";
}

void examplePassByRefImplicatScoped(int* start, int* end)
{
  return;

  // pass by ref of the entire implicat scope
  int sum = 0; 

  std::for_each(start, end, [&] (int v) 
  {
    std::cout << v << "\n";
    sum += v;
  });
  std::cout << " sum is : "<< sum << "\n";
}

// and now the fun...
template <class T>
void filterTo(T* start,
       T* end,
       std::function<bool (const T&)> filter,
       std::function<void (const T&)> action
       )
{ 
  std::for_each(start, end, [=] (T v) { if ( filter( v ) ) action( v ); });
}

void exampleStdFunctionLambdaNoClosure(int* start, int* end)
{
  //lambda compiling to a function pointer compatible with std:function
  std::function<bool (const int&)> filter
    = [](const int& v)->bool { return v%2; };
  std::function<void (const int&)> action
    = [](const int& v)->void { std::cout << "filt odd: " << v << "\n"; };

  filterTo(start, end,
    filter, action);
}

void exampleLambdaNoFunctionTemplateWeakness(int* start, int* end)
{
//  //This is the same as above and should work however the curent 
//  // compiler is  very poor at solving this.. so it dies
//  filterTo(start, end,
//    [](const int& v)->bool { return v%1; },
//    [](const int& v)->void { std::cout << v << "\n"; });
}

void exampleStdFunctionLambdaClosure(int* start, int* end)
{
  //evil: lambda closure is creates a class object not a function pointer
  // this can still wrap up in the std::function 
  int sum = 0;
  std::function<bool (const int&)> filter
    = [](const int& v)->bool { return v%2; };
  std::function<void (const int&)> action
    = [&sum](const int& v)->void {  sum += v; std::cout << "run sum:" << sum << "\n"; };

  //lambda compiling to a function pointer compatible with std:function
  filterTo(start, end,
    filter, action);

  std::cout << "Tot sum:" << sum << std::endl;
}

int main()
{
  int stuff[]={1,2,3,4,5,6,7,8,9};
  int* end = stuff + (sizeof(stuff)/sizeof(int)); //warning this is pointer arithmetic
 
  //suming examples
  examplePassByValue(stuff, end);
  examplePassByRef(stuff, end);
  examplePassByRefImplicatScoped(stuff, end);

  //find all odds..
  exampleStdFunctionLambdaNoClosure(stuff, end);
  exampleStdFunctionLambdaClosure(stuff, end);
  
  return 0;
}

Since this is a bit of a mess to run here is the make to build and run it (set BASE) to match your mingw 4.7 install path

BASE=/c/tools/mingw47
export PATH:=${BASE}/i686-w64-mingw32/lib:${BASE}/bin:${PATH}

all: run

lambda.exe: lambda.cpp
 g++ -std=c++11 lambda.cpp -o lambda.exe

run: lambda.exe
 lambda.exe

Refer: http://www.cprogramming.com/c++11/c++11-lambda-closures.html

c++11 - mingw 4.7 install and msys setup notes

The new c++11 standard adds lots of new syntactic sugar to play with.

http://gcc.gnu.org/gcc-4.7/cxx0x_status.html


Unfortunately you'll need to get the 4.7 release directly... the automatic installer still wont download then for you.

http://code.google.com/p/mingw-builds/downloads/detail?name=i686-mingw32-gcc-4.7.0-release-c%2Cc%2B%2B%2Cfortran-sjlj.zip&can=2&q=


Once down loaded unzip in to your desired location (mine is c:\tools\...)

Then you will need to help the system locate the compiler, linker and libs (runtime dlls) for usage as well so you should run the following on a prompt before running your compliation and built .exes.

export PATH="/c/tools/tmp2/mingw/i686-w64-mingw32/lib:$PATH"
export PATH="/c/tools/tmp2/mingw/bin:$PATH"

boost 1.49 in windows 7 using mingw

Before you start. This is for(although its has worked on other systems)

mingw gcc version 4.6.2
boost verison: 1.49
OS: Windows 7 home.

This is basically the same as before in my prior post /2011/02/boost-in-vista-using-mingw-and-cmdexe.html

First get the newer version of boost from here http://sourceforge.net/projects/boost/files/boost/1.49.0/boost_1_49_0.zip/download?use_mirror=jaist


Dont bother downloading one of the ones with a build version of bjam it wont work. You will need to build it.

Setup gcc as in one of my prior posts.

Make certain that gcc is available on cmd.exe by running a fresh cmd.exe and executing:

gcc -v

You must double that this is not just a temp change to the %PATH% env variable by some script. It has to be set from windows GUI control directly to work reliably.
If gcc failed you can add it to the PATH with the following command sequence.

• windows key+e
  
• select "my computer"
  
• right click it and select "properties"
  
• 3rd tab -> click buttom "variables" button
  
• add (or edit the existing) PATH entry and set its value [installed_dir]/mingw/bin;[installed_dir]/mingw/lib (where instal_dir is the pathto your mingw install
  

Next Build bjam: For help refer to: building bjam for 1.49. Note that I use the directory c:\tools as my install area for all programs that need to avoid the windows UAE etc idiocy.. Unziped the files into the desired location Then build the bjam.exe in cmd.exe by executing :

cd C:\tools\boost_1_49_0\tools\build\v2\engine
build.bat mingw

Once built copy C:\tools\boost_1_49_0\tools\build\v2\engine\bin.ntx86\b*.exe into C:\tools\MinGW\bin (This isnt needed but makes it easy later, since you likely have it in your %PATH% already.) Next build the boost libs also in cmd.exe by excuting:

cd C:\tools\boost_1_49_0
bjam toolset=gcc --build-type=complete stage

Refer: http://www.boost.org/doc/libs/1_49_0/more/getting_started/unix-variants.html Wait for the build system to grind it out. This time around there are very few build problems. I guess alot of things have been fixed since the 1.47 version. You should then build a few boost test programs(in cmd or msys) with:

g++ -I"c:\tools\boost_1_49_0" -L"c:\tools\boost_1_49_0\stage\lib" -static boost_lamba_test.cpp -o a.exe
g++ -I"c:\tools\boost_1_49_0" -L"c:\tools\boost_1_49_0\stage\lib" -static boost_regex_test.cpp -lboost_regex-mgw46-1_49 -o b.exe

The test programs are from here:

Lamba test: http://www.boost.org/doc/libs/1_45_0/more/getting_started/windows.html#build-a-simple-program-using-boost

Regex test: http://www.boost.org/doc/libs/1_45_0/more/getting_started/windows.html#link-your-program-to-a-boost-library

Keep in mind the order of the source and libs files is important in mingw http://www.mingw.org/wiki/Specify_the_libraries_for_the_linker_to_use