c++11 Variadic template

Another interesting feature of c++11 is the variadic templates. Basically these allow you to add infinite, heterogeneous parameters to your functions. However their syntax seems to force you to define them recursively. As a result they seem to be usable in 2 main ways.

1. Map: Apply an repeated operation over the entire list of objects
   
2. Reduce(or fold): Take in the list of objects and compound them into something
   

How very Hadoop. This apparent limited usability makes them a prime candidate for reduction in a forwarding function. Something that simply recurses the list of parameters and forwards them through a normaliser into a Lambda or directly into a templated function that can handle the specific Type. Here is the Normalize and Lambda approach.

#include <iostream>
#include <sstream>
#include <functional>

template <typename R, typename I>
R normalise(I i)
{
  try
    {
      R item;
      std::stringstream s;
      s << i;
      s >> item;
      return item;
    }
  catch(...)
    {}

  return R();
}

template <typename R, typename I>
R reduce(std::function<R (const R&, const R&)> action, I i)
{
  return normalise<R>(i);
}

template <typename R, typename I, typename... II>
R reduce(std::function<R (const R&, const R&)> action, I i, II... ii)
{
  return action(normalise<R>(i), reduce<R>(action, ii...));
}

template <typename R, typename I>
R map(std::function<void (const R&)> action, I i)
{
  action(normalise<R>(i));
}

template <typename R, typename I, typename... II>
void map(std::function<void (const R&)> action, I i, II... ii)
{
  action(normalise<R>(i));
  map<R>(action, ii...);
}

int main()
{ 
  std::function<int (const int&, const int&)> max
    = [](const int& a, const int& b)->int { return a>b ? a : b;  };  

  std::function<float (const float&, const float&)> min
    = [](const float& a, const float& b)->float { return a<b ? a : b;  };  

  std::function<float (const float&, const float&)> sum
    = [](const float& a, const float& b)->float { return a+b;  };  

  std::cout << "Max:" << reduce(max, "452", 3.422, 32, 0x000000ff, "543.485") << "\n";
  std::cout << "Min:" << reduce(min, "452", 3.422, 32, 0x000000ff, "543.485") << "\n";
  std::cout << "Sum:" << reduce(sum, "452", 3.422, 32, 0x000000ff, "543.485") << "\n";

  float res = 0;
  std::function<void (const float&)> accum
    = [&res](const float& a) { res += a;  };  

  map(accum, "452", 3.422, 32, 0x000000ff, "543.485");
  
  std::cout << "\n" << "Accum:" << res << "\n";

  std::stringstream ss;
  std::function<void (const float&)> stream = [&ss](const float& a) { ss << a << ",";  };

  map(stream, "452", 3.422, 32, 0x000000ff, "543.485");
  std::cout << ss.str() << "\n";
}

Tablified Traits

Here is simple c++ trait wrapper that goes around the old standard c++ array of structs lookup table. It handles the forward and reverse lookup of the trait entry via its main key and an attrib and then the access of the various attributes from the resulting row.

There are some caveats to it. The Enum id cant be sparse. and the UNKNOWN entry needs to be second last before the MAX entry marker.

#include <iostream>

template<int LAST, typename R, typename T>
R lookup(T* table, R T::*member, int key) 
{
  if (key < LAST) return table[key].*member;
  return table[LAST].*member;
}

template<int LAST, typename R, typename T>
int locate(T* table, R T::*member, R target) 
{
  int k = 0;
  while (k < LAST)
    {
      if (table[k].*member ==  target)
 return k;
      k++;
    }
  return LAST;
}

template<int LAST, typename T>
int locate(T* table, const char* T::*member, const char* target) 
{
  int k = 0;
  while (k < LAST)
    {
      if (std::string(table[k].*member) == std::string(target))
 return k;
      k++;
    }
  return LAST;
}

class TableTrait
{
public:
  enum Key
    {
      ITEM1,
      ITEM2,
      ITEM3,
      ITEM4,
      ITEM5,
      UNKNOWN, //Must be second last
      MAX      //Must be last
    };    

private:  
  struct TableEntry
  {
    Key         key;
    int         attribA;
    bool        attribB;
    const char* attribC;
  };

  static TableEntry lookup_table[MAX];

  int key_;
public:
  TableTrait(int key) :
    key_(lookup<UNKNOWN>(lookup_table, &TableEntry::key, key))
  {}

  TableTrait(const char* rev_key) :
    key_(locate<UNKNOWN>(lookup_table, &TableEntry::attribC, rev_key))
  {}

  bool        valid()   { return key_ != UNKNOWN; }
  Key         key()     { return static_cast<Key>(key_); }
  int         attribA() { return lookup<UNKNOWN>(lookup_table, &TableEntry::attribA, key_); }
  bool        attribB() { return lookup<UNKNOWN>(lookup_table, &TableEntry::attribB, key_); }
  const char* attribC() { return lookup<UNKNOWN>(lookup_table, &TableEntry::attribC, key_); }  
};

TableTrait::TableEntry TableTrait::lookup_table[TableTrait::MAX] =
{
  { ITEM1,   3, false, "ITEM1"   },
  { ITEM2,   2, true,  "ITEM2"   },
  { ITEM3,   6, false, "ITEM3"   },
  { ITEM4,   5, true,  "ITEM4"   },
  { ITEM5,   8, false, "ITEM5"   },
  { UNKNOWN, 0, false, "UNKNOWN" }
};

int main()
{
  std::cout << "lookup: " << TableTrait(TableTrait::ITEM1).attribC() << "\n";
  std::cout << "lookup: " << TableTrait(TableTrait::ITEM2).attribB() << "\n";
  std::cout << "locate: " << TableTrait("ITEM3"          ).attribA() << "\n";
  std::cout << "locate: " << TableTrait("ITEM2"          ).key()     << "\n";
  std::cout << "locate: " << TableTrait("Blah"           ).attribC() << "\n";
}

C++ Mixins and Curiously Recurring Templates

C++ Curiously Recurring and Mixin's

In large systems it is often desirable to have a policy or rule classes that handle a group of settings for particular instance of a data object. Generally the most common settings are chosen for the base class so that it becomes the "Default" policy. Other Policy's are added by over loading the various part of the Rules class to make new policies such as "DefaultWithA" and "DefaultWithB". But then someone will note the need for a "DefaultWithAandB"

At this point coders either cut and paste. Or try to break the Main rule object into sub-grouping objects "PolicyGroupA" and "PolicyGroupB" and convert the the main Rule into an interface that just aggreatates the tree of sub rules objects. This slowly crags up the rule checking with a series wrapper function calls just to get to the final cluster of rules. Furthermore its often rather difficult to divide these objects in a sane way because they have some form of relationship that caused them to be grouped at the start anyway.

Ruby provides an interesting addition to its language to handle common functionally and code grouping called a mixin. Rubys mixin is just another inheritance trick and once you realize what it is its easy to repeat it in C++. Simply put works out as a near brother of the curiously reoccurring templates. here is how it works;

#include <iostream>

class Default
{
public:
  virtual void ruleA() { std::cout << "default::ruleA\n"; }
  virtual void ruleB() { std::cout << "default::ruleB\n"; }
  virtual void ruleC() { std::cout << "default::ruleC\n"; }
};

class Impl1 : public Default
{
public:
  virtual void ruleC() { std::cout << "Impl1::ruleC\n"; }
};

template <typename T>
class MixinA : public T
{
public:
  virtual void ruleA() { std::cout << "mixin::ruleA\n"; }
};

template <typename T>
class MixinB : public T
{
public:
  virtual void ruleB() { std::cout << "mixin::ruleB\n"; }
};

class Unrelated
{
};

class DefaultWithMixinA : public MixinA<Default >
{
};


class DefaultWithMixinAandB : public MixinB< MixinA< Default > >
{
};

class Impl1WithMixinA : public MixinA<Impl1>
{
};

class UnrelatedWithMixinA : public MixinA<Unrelated>
{
};

int main()
{
  std::cout << "DefaultWithMixinA\n";
  DefaultWithMixinA d;
  d.ruleA();
  d.ruleB();
  d.ruleC();
  
  std::cout << "DefaultWithMixinAandB\n";
  DefaultWithMixinAandB ab;
  ab.ruleA();
  ab.ruleB();
  ab.ruleC();
  
  std::cout << "Impl1WithMixinA\n";
  Impl1WithMixinA i;
  i.ruleA();
  i.ruleB();
  i.ruleC();
  
  std::cout << "UnrelatedWithMixinA\n";
  UnrelatedWithMixinA u;
  u.ruleA();
}

Here is some code so that you can see the difference between this and a real curiously reoccurring template. Pay close attention to how it inherits

#include <iostream>

template <typename T>
struct CuriouslyRecurring
{
public:
  virtual void ruleA()  { std::cout << "CRP::ruleA\n"; }
};

template <typename T>
struct Mixin : public T
{
public:
  virtual void ruleA() { std::cout << "mixin::ruleA\n"; }
};

struct Default
{
public:
  virtual void ruleA() { std::cout << "default::ruleA\n"; }
};

struct DefaultWithMixin : public Mixin< Default >
{

};

struct SelfWithCRT : CuriouslyRecurring< SelfWithCRT >
{
};

// Impossible complier cant tell which ruleA to use when you call it
//struct DefaultWithCRT : public CuriouslyRecurring< DefaultWithCRT >, Default
//{
//};

// Impossible this is a MIXIN cant overload an incomplete class
//struct SelfMixin : public Mixin< SelfMixin >
//{
//};

int main()
{
  SelfWithCRT crt;  
  crt.ruleA();

  DefaultWithMixin mix;  
  mix.ruleA();

  //DefaultWithCRT dcrt;  
  //dcrt.ruleA();
}

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.