Qt Container Efficiencies

Ever stumble onto something completely obvious? You know, it's there looking you in the face every day but you don't even think about it? Take for example Qt containers with operator[]:

QStringList myEntries(fillupContainerSomewhere());
for(int i=0; i<myEntries.size(); ++i)
{
     if (myEntries[i] == "Hello") 
    {
        // Do something.
    }
}

What's wrong with this seemingly innocuous code (other than using .size(), that's obvious). We are filling up a Qt Container called QStringList with some entries, iterating through and checking against another string. This is about as basic as it gets.

To know the answer one has to know a little about Qt-style containers. They are pretty optimized for copying. Like everything in Qt, they are implemented in terms of a d-pointer (or pimpl idiom or handle idiom). Qt is smart about their containers and copying the containers. Say we do the following:

QStringList myEntries(fillupContainerSomewhere());
QStringList copyOfMyEntries(myEntries);
QStringList copy2OfMyEntries(myEntries);

Qt is smart- it only keeps the contents of 1 list in memory under the hood. They can do this by copying the d-pointer around so that multiple QStringList objects point at the same data. There is a caveat- what if one of the QStringList's is modified? The conservative and correct approach to this problem is that the contents MUST be completely copied and changed. If we didn't, what happens when:

QStringList myEntries(fillupContainerSomewhere());
QStringList copyOfMyEntries(myEntries);
QStringList copy2OfMyEntries(myEntries);

copyOfMyEntries.removeAt(4);

If we didn't force copyOfMyEntries to copy then modify all of the QStringList objects would be modified! That was definitely not the author's intent. The QStringList::operator[] returns an l-value (and if you remember, l-value means it can be modified!). Even if you are only using operator[] to read the value it will assume a write is about to take place forcing QStringList to make a deep copy! Ouch! 

The lesson here is that if you are only reading a value from a QStringList it should be done using the QStringList::at method instead- this returns an r-value and does not cause a deep copy to occur. [1] The second link in the references is good, we use it at work a lot! [2]

Keep in mind that this behavior for containers is NOT the same as the standard containers! The operator[] in a standard container (std::vector) means that if an out of bounds situation occurs it will simply fail whereas using "at" will cause an exception to be thrown. C++11 has added "at" to standard map. It appears to have the same side effect that if an element that does not exist is accessed it will throw an "out_of_range" exception. [3] 

The moral of the story, standard containers do not behave like Qt containers. The main moral is that when using Qt containers, use "at" method to read.

REFERENCES

[1] - https://qt-project.org/doc/qt-4.8/implicit-sharing.html#overview

[2] - http://www.slideshare.net/PassoK/qt-and-qml-performance-tips-tricks-for-qt-47

[3] - http://www.cplusplus.com/reference/map/map/at/

Boost.Build (Part 3)

This entry is about how to link in an external library using bjam AND a little start into using boost asynchronous IO. I'm not going to cover asio programs because I feel that the blog in the references already covers this extremely well. The entries I'll be making aim to tackle troubleshooting and filling in information where it appears to be missing.

The tutorial in [1] breaks the programs down really well. However there were no instructions on how to build the programs! You won't find a libboost_asio* on your system because that's not what it relies on. The command I used to compile the example using g++ 4.7 was:

g++ main.cpp -L/usr/boost -lboost_system -pthread

That was the absolute minimum to get the test program to build. Please see the developer's blog in [1] for the small example- it's the equivalent of a "Hello World".

Using bjam it's as simple as:

lib boostsystem
    :
    : <file>/usr/lib/libboost_system.so.1.46.1
    ;

exe sampleProgram : main.cpp .//boostsytem :
   <threading>multi ;

I'm still a little confused about the syntax of a Jamroot, so I looked it up [2]. To break things down line by line:

lib boostsystem

This line specifies that we have a library that we are describing "lib" (this is known as a rule-name) and its identifier is "boostsystem". The identifier could have been anything but since I'm linking together an ASIO program boostsystem is very descriptive.

:

The items after the first colon in a specification are the "sources" or input files. Since an existing library doesn't really have source inputs its contents will be empty.

: <file>/usr/lib/libboost_system.so.1.46.1

The contents after the second colon are the requirements. I'm not sure what the file tag does in this case- but it probably reads that the file must exist in order for the specification to be met.

;

Simply the termination of the specification.

exe sampleProgram : main.cpp .//boostsystem :

This line specifies that we are describing an executable program "exe" and that it is called "sampleProgram". Notice that the first colon is on the same line and that the first area specifies inputs as main.cpp (the source file) and .//boostsystem (which is the library we specified first!). The sources are terminated with a colon.

<threading>multi ;

Remember how in the manual command line execution I specified -pthread? Adding this argument to the build does that for you. This is a cool way to do it especially if you are working across different platforms where the threading platform differs (Windows vs. Linux vs. BSD's). Simply invoke bjam in the same directory and you're all done! Your first ASIO program is now built.


REFERENCES

[1] - http://www.gamedev.net/blog/950/entry-2249317-a-guide-to-getting-started-with-boostasio/

[2] - http://docs.huihoo.com/boost/1-33-1/doc/html/bbv2/advanced/jamfiles.html

Arduino Tools (avr-g++)

Introduction 

I'm becoming more and more curious about Arduino. I bought a board a long time ago and it is currently being used as a dust-collection mechanism. The first time it was powered on, I was disappointed that the only thing I could program in appeared to be watered down C (and my passion is C++). It's been a couple of years and in that time some research was done. As it turns out, there is a compiler to build Arduino applications!

Obtaining avr-g++ 

The first step was to get the compiler and toolchain. This worked rather nicely on Ubuntu:

> sudo apt-get install arduino

I came back to the command line and typed:

> avr-

And pressed Tab for completion. As it turns out, the installation of the Arduino module installed the avr-g++ toolchain. That g++ at the end makes me feel warm and fuzzy, kind of like when I see a terminal on the desktop with vim. Now we're getting somewhere! 

Ubuntu's package management system does something kind of funny with what it pulls down. The header files for the Arduino are located in: /usr/lib/avr/include/avr. That's unusual; why would header files be found in /usr/lib? That's besides the point. The first example [1] of a program written for avr used a header file called "wiring.h" - there is no wiring.h in the files downloaded. Keep in mind that the project shown in that example was built using eclipse. I'm going straight command line so this will not do. 

Obtaining Makefile's for Arduino Projects

I'm not the best one to talk to about Makefile's for Arduino. I can tell you that they will save you an enormous amount of time and frustration. As of this blog post, there are a number of makefile's out there to choose from. The one I'm using is "edam's Arduino makefile" [4]. It was not difficult to use, especially if you are already familiar with the Linux command line tool "make".

Obtaining and Using Arduino-specific Libraries

Getting the compiler is only half the battle. The other half is obtaining the Arduino-specific libraries that are useful when building "sketches". I'm including this as part of the article because it's good to know what their software is doing. Also the Makefile provided above also uses the Arduino-specific libraries. [5]

The Arduino library is separated into 5 different subdirectories: app, build, core, hardware, and libraries. Because this is a C++ blog, I won't trouble you with the silliness in any other directory but hardware- because that's where the C++ gold is. Navigate to:

Arduino/hardware/arduino/cores/arduino/

Here is the link on github where you can look at all of the source code for the library [6]. Looking specifically at Arduino.h, you can see it defines the stubs for setup() and loop() (around lines 117-118). If you look at the boilerplate code in main.cpp you'll see how it mostly comes together:

// Obviously this is going to include a lot of the hardware-
// specific internals, most of these will be macro'd out depending
// on the architecture of the board you selected (in my case ATmega328).
#include <Arduino.h>

int main(void)
{
    // Initialization of hardware.
    init();

   // USB Connectivity (if any).
#if defined(USBCON)
    USBDevice.attach();
#endif

    // Calling the stup() method we would write ourselves!
    setup();

    for(;;) {
        loop();
    }
}

That's the gist of the boilerplate code. When the Makefile runs, it will build your "sketch" code (C++ code that is only setup() and loop()) AND the boilerplate code and all of the code in this library. It's all linked together statically because we only deploy one hex file to the device at a time.

Hardware

After doing some research, I found out that the board I'm using is an ATmega328 [2]. This is useful because we need to know the architecture to pass into the avr-g++ compiler in order for it to enable the correct macros. The main header file to use is actually "avr/io.h".

When you plug your board in via USB there is a check you should do to make sure everything is connected and that is:

1) Connect the board via USB.

2) Check to make sure the board is powered by check the LED's on the board.

3) cd /dev

4) ls

Check the output for a device called ttyACM0. If that device exists you're good to go! 

Output Binaries

When you eventually do build the program for Arduino it should be a file with a .hex extension. This tripped me up originally because avr-g++ can produce a.out files if not given an output filename. The question you might have is, "How in the hell do I get this onto my device?" Great question. You want to use a program called avrdude. For my specific hardware here is the command I used to upload my hex file to the Arduino (USE THIS AT YOUR OWN RISK, I TAKE NO RESPONSIBILITY...EVER):

sudo avrdude -P /dev/ttyACM0 -c avrisp -p m328p -v -e -U flash:w:blink.hex -U lock:w:0x0F:m -F

The reason why this was executed with super user permissions was the access to the hardware. A more experienced linux professional could probably get this to work without the permissions but for the sake of this article I won't cover that. A lot of this I pulled from external sites so it's a little magical to me. The gist is that avrdude uses the device ttyACM0 and uses the programmer avrisp (-c avrisp) for the ATmega328 (-p m328p) and uploads my hex file (blink.hex) to the hardware. PLEASE NOTE: A couple of the sites I visited warned me about the force flag (-F) and why it shouldn't be used. I wouldn't do this unless you 1) don't care about your hardware, 2) understand fully what it is doing. I fall into the first group.

REFERENCES 

[1] - http://andybrown.me.uk/wk/2010/10/24/your-first-avr-project-in-eclipse/

[2] - http://arduino.cc/en/Main/arduinoBoardUno

[3] - http://www.nongnu.org/avr-libc/user-manual/using_tools.html

[4] - http://ed.am/dev/make/arduino-mk

[5] - http://arduino.cc/en/main/software

[6] - https://github.com/arduino/Arduino/tree/master/hardware/arduino/cores/arduino

Custom New + Delete (Part 1)

The motivation behind wanting to learn this is:

1) Better understand how operator new works.
2) Build up towards custom allocation for fast pimpl's.
3) It's pretty cool.

For my first test of trying to understand how the custom new/delete worked, I implemented a small program. My preliminary search for custom new/delete didn't turn up a simple example, so here it is:


#include <iostream>
#include <string>

struct S
{
S() : value(13), message("Hello World!") { }
int value;
std::string message;

void* operator new(size_t i) 
{
std::cout << "CALLING CUSTOM NEW!" << std::endl;
return new char[i];
}

void operator delete (void* ptr)
{
std::cout << "CALLING CUSTOM DELETER!" << std::endl;
delete[] reinterpret_cast<char*>(ptr);
}
};


int main(int argc, char** argv)
{
    for(;;)
    {
S* s = new S();
std::cout << "s.value = " 
                  << s->value 
                  << ", s.message = " 
                  << s->message 
                  << std::endl;
delete s;
    }
}

Doesn't get much simpler. The points of understanding for this are:

1) operator new DOES NOT invoke the constructor! It merely allocates the memory that is later filled by the constructor. 

2) Always have a corresponding operator delete.

It's really that simple. I ran this program and watched the memory consumption using top. It didn't seem to budge so that made me feel good. 

Overloading (NOT) Partial Specialization

I haven't put up an entry the past few days because of the confusion I've had about overloading vs. partial specialization. There are a few things I'm absolutely sure of (because a book tells me so):


1) Templates can overload [1].

2) There is no such thing as partial specialization for a template function [1].


For point #1, it simply means that if you have a plain old function (no template parameters) and you also have a templatized function with the same name and template parameters, the templatized function can be used to overload. I like the example I found on the IBM page [2]. The example was:

template<class T> void f(T x, T y) { cout << "Template" << endl; }
void f(int w, int z) { cout << "Non-template" << endl; }

That is a nice simple example of how the function template overload works. We all know that this works and works really well.

Point #2 is where I had the most trouble. I pounded this statement into my head for the past four days; not only that this was also instilled in me from numerous C++ lectures. For me, the statement is better rewritten: "There is no such thing as partial specialation for a template function, there are only overloads." Think about it- you can overload functions with template parameters. Therefore the following is another example of simple template overloading:

template <typename T> 

void func(T t) { cout << "template <typename T> void func(T t)" << endl; }

template <typename T> 

void func(T* t) { cout << "template <typename T> void func(T* t)" << endl; }

These are both just overloaded functions. Two unique overloaded functions! Things were fine in my head until I saw the Dimov/Abrahams example (rewritten in terms of above):

// 1 

template <typename T> 

void func(T t) { cout << "template <typename T> void func(T t)" << endl; }

// 2

template <typename T> 

void func(T* t) { cout << "template <typename T> void func(T* t)" << endl; }

// 3

template <>

void func<int>(int* i) { cout << "template <int>(int* i)" << endl; }

// 4

template <>

void func<int*>(int* i) { cout << "template <int*>(int* i)" << endl; } 
int main(int argc, char**argv) 
{
    int value = 12345;
    func(&value);
}
  

Everyone knows when they see code like this and are asked, "Which overload is called?" that it's a trap. I would have said that the fourth would handle it- and I'd be wrong. The question becomes, why is #3 chosen and not #4? Moreover, say you have the following code (omitting #3:

// 1 

template <typename T> 

void func(T t) { cout << "template <typename T> void func(T t)" << endl; }

// 2

template <typename T> 

void func(T* t) { cout << "template <typename T> void func(T* t)" << endl; }

// 4

template <>

void func<int*>(int* i) { cout << "template <int*>(int* i)" << endl; } 
int main(int argc, char**argv) 
{
    int value = 12345;
    func(&value);
}

Surprisingly now, #2 is called! After studying for a bit, I came across what should be a bullet fact:

3) Overload resolution selects only a single, best-fit primary template.

Here is why function #4 is never called: it is an explicit specialization of function #1, NOT FUNCTION #2! Function #3 is a specialization of Function #2. Try the example above out and take out function #1:

// 2

template <typename T> 

void func(T* t) { cout << "template <typename T> void func(T* t)" << endl; }

// 3

template <>

void func<int>(int* i) { cout << "template <int>(int* i)" << endl; }

// 4

template <>

void func<int*>(int* i) { cout << "template <int*>(int* i)" << endl; } 
int main(int argc, char**argv) 
{
    int value = 12345;
    func(&value);
}

This WILL NOT COMPILE. The specialization for #4 requires that a primary template already exists. Function #3 can exist because its primary template is Function #2.  That is the key to understanding the Dimov/Abrahams problem, what specialization is tied to what primary template. Understand that first and the whole thing comes together.

Once it's understood the tie in between the primary and specialized templates we can now determine which primary template the compiler will choose to handle the overload. Given a choice between:

// 1 

template <typename T> 

void func(T t) { cout << "template <typename T> void func(T t)" << endl; }

// 2

template <typename T> 

void func(T* t) { cout << "template <typename T> void func(T* t)" << endl; }

and the input to func being an int*, the compiler will clearly pick option #2. The compiler then checks to see if option #2 has any specializations and if any of those fit. Since option #2's overloads were:

// 3

template <>

void func<int>(int* i) { cout << "template <int>(int* i)" << endl; }

It will pick #3 as the function used! Beautiful in how much sense it makes. If Option #3 isn't available, it would default back to the primary template which is Option #2. 

So in conclusion, the rules for understanding template function overloading are:

1) Templates can overload [1].

2) There is no such thing as partial specialization for a template function.

3) Overload resolution selects only a single, best-fit primary template.

4) Explicit specializations are chosen only if they fit the singly chosen best-fit primary template only, specializations applied to any other primary template are ignored.

 

REFERENCES

[1] - Exceptional C++ Style, Herb Sutter. Item #7: Why Not Specialize Function Templates?

[2] - http://publib.boulder.ibm.com/infocenter/comphelp/v7v91/index.jsp?topic=%2Fcom.ibm.vacpp7a.doc%2Flanguage%2Fref%2Fclrc16overl_fn_templates.htm

std::stringstream vs. scanf

Back in the olden days C-Programmers would use a facility called scanf to read in values from some sort of string (char array) data. The more modern and usable facility is to use std::stringstream. I like to focus on efficiency over everything else- so if that's not your bag I would suggest skipping this entry.

The inspiration for this blog entry came from "Exceptional C++ Style" by Herb Sutter, Item #2. I would strongly advise you to check it out if you want more detailed explanations about what I'm writing about. There's a cool chart in the article that shows the trade-off's between stringstream, boost::lexical_cast, and scanf. The claims made in the book are that scanf is more efficient because of the lack of one memory allocation call. This blog entry investigates this claim.

To understand each, let's write a typical program including both styles:

// Ahh, these make me feel good!
#include <iostream>
#include <sstream>
#include <string>
// Yikes, this makes me feel sick.
#include <cstdio>

enum { BUFFER_SIZE = 100 };

int main(int argc, char** argv)
{
    std::string input("Hello World!");
 
    std::string cpp_contents;
    std::stringstream ss;
    ss << input;
    ss >> cpp_contents;
     char c_contents[BUFFER_SIZE];
    sscanf( input.c_str(), "%s", c_contents);

    std::cout << "CPP Contents: " << cpp_contents << std::endl;
    std::cout << "C Contents: " << c_contents << std::endl;
}

So obviously this is skewing in terms of efficiency. But is there anything that can be done to improve the C++ side? Let's go line by line for the analysis:

std::input("Hello World!");

This line is not what we want to focus on. I used a string here, but we could easily replace it with a null terminated character buffer. In both cpp/c land we are taking its contents (.c_str()) and using that input.

std::string cpp_contents;
std::stringstream ss;

These two lines are just setup so far. Obviously the creation of the stringstream is a unique object so it's going to cost something. Also the cpp_contents are what we are going to read into.

ss << input;
ss >> cpp_contents;

So to fake things out we'll stream input into the string stream to populate it then stream a single string into cpp_contents. Thus far the overhead is the creation of two objects (cpp_contents, ss) and streaming in to populate the stringstream then streaming out to get the single string.

char c_contents[BUFFER_SIZE];
sscanf(input.c_str(), "%s", c_contents);

The analysis at this point doesn't seem fair because it's obvious that sscanf is more efficient because there is only a character buffer created. Character buffers make me cringe because they are fragile, prone to buffer overruns, and require more maintenance. sscanf does a very efficient job of filling a buffer. Can we make the C++ better?

The first thing I thought of was replacing the string cpp_contents with a character buffer. This is a stupid idea because all we would be doing is trading one object for another instead of getting rid of an object altogether.

The second thing I thought about was directly populating the stringstream. The stringstream object has a second constructor that takes a string! Therefore we can eliminate that first stream to populate the object. But our tally still stands at 2 objects and one operation for the C++ implementation, 1 object and 1 operation for the C implementation. How sad.

As a final test, I'm taking my two implementations and racing them:

#include <iostream>
#include <sstream>
#include <string>
#include <cstdio>

enum { BUFFER_SIZE = 100, MAX = 700000 };

//#define CPP_IMPLEMENTATION
#define C_IMPLEMENTATION

int main(int argc, char** argv)
{
    std::string input("Hello World!");

#if defined CPP_IMPLEMENTATION
    for(unsigned long i=0; i<MAX; ++i)
    {
        char cpp_contents[BUFFER_SIZE];
        std::stringstream ss(input);
        ss >> cpp_contents;
    }
#endif

#if defined C_IMPLEMENTATION

    for(unsigned long i=0; i<MAX; ++i)
    {
        char c_contents[BUFFER_SIZE];
        sscanf(input.c_str(), "%s", c_contents);   
    }

#endif

}
 
What I found:

CPP_IMPLEMENTATION
    real     0m0.547s
    user     0m0.544s
    sys      0m0.000s

C_IMPLEMENTATION
    real     0m0.062s
    user     0m0.056s
    sys      0m0.004s

There it is. If you are coding for safety, use C++'s modern standard string stream. However if you are focusing your endeavours on efficiency then seriously consider using a function from the scanf family. It's faster because of the obvious: no need for an extra object allocation.

Exception Neutral vs. Exception Safe

The last entry I made was all about throw specifiers. Now I want to cover exception safety vs. exception neutral; the two main "degrees" of exception safety guarantees. The book Exceptional C++ has a (pardon the expression) exceptional explanation of these two levels- but not enough clarification in the examples. I thought I'd take the time to present some code examples that illustrate exception safe and exception neutral guarantees. 

Exception Neutrality

From what I understand (and I'll cite this), all exception neutrality is means that if you aren't handling an exception allow the exception to propagate [2]. So the following example would NOT be exception neutral:

void exceptionNonNeutral()

{

    try 

    {

         functionThatCouldThrow();

    }

    catch(...)

    {

        // Eat all exceptions thrown!

    }

}

I used to be a fan of eating all exceptions and throwing them away- however this doesn't allow exceptions to be handled by callers further down the stack. It can hide problems that may exist in functionThatCouldThrow(). To make this function exception neutral, might I suggest an extra throw?

void exceptionNeutral()

{

    try 

    {

         functionThatCouldThrow();

    }

    catch(...)

    {

        // Adding this line allows us to re-throw whatever was

        // thrown earlier. This is the key for exception 

        // neutrality.

        throw;

    }

}

The funny thing is that if you never added a try-catch block (i.e. no exceptions) you are automatically exception neutral because the exception would unwind the stack. It's only when you start catching exceptions that you need to worry about being neutral to exceptions that aren't understood by your function.

Exception Safe

This one is a bit harder to determine (and this is where Sutter scared me in Exceptional C++). Any function could throw an exception- which should make developers paranoid. This is also why writing exception safe code is so difficult as every single function could throw something and we have no idea what that might be! The only thing we can do as sane rational people is take care of our own code and safeguard it in case an exception is thrown.

The following is not exception safe:

#include <iostream>

#include <stdexcept>

struct A

{

    A(bool throwSomething) 

    { 

        if (throwSomething)

        {

            throw std::runtime_error("Exception!");

        }

    }

    int magicNumber() const { return 13; }

};

static A* internalObject = 0;

void reset()

{

     delete internalObject;

     internalObject = new A(true);

}

int getMagicNumber()

{

    return (0 != internalObject ? internalObject->magicNumber() : 0);

}

Let's cover what is going on. I've created a structure A which may or may not throw based on the bool passed in. The purpose is to illustrate exception safety- in the real world this could be a call to new that throws, etc. For the sake of simplicity, we'll keep it simple. 

The function reset() is not exception safe because it leaves the program in an inconsistent state. In a normal situation, getMagicNumber() would return a number with no incidents whether or not reset() was called. If getMagicNumber() calls without a valid internalObject it will return 0. However, if internalObject is non-zero and points at memory it will return the contents of the magicNumber() method.

Here's what can go wrong and why we should all be paranoid, if during reset() we invoke the constructor for A and it throws then the internalObject has already been deleted. That's really bad! The internalObject was destroyed, yet the internalObject pointer value is still non-zero. Then our user calls getMagicNumber() which  states that yes, internalObject is non-zero (but pointing at destroyed memory) and therefore we're going to call magicNumber() on that garbage memory. 

Exception safety means we have to keep the state of the program intact. Therefore we could do the following to fix this program:

#include <iostream>

#include <stdexcept>

struct A

{

    A(bool throwSomething) 

    { 

        if (throwSomething)

        {

            throw std::runtime_error("Exception!");

        }

    }

    int magicNumber() const { return 13; }

};

static A* internalObject = 0;

void reset()

{

    // Store a pointer to the old object.

    A* old = internalObject;

    // Attempt to create a new A object, if this throws

    // then internalObject is never set.

    internalObject = new A(true);

    // Delete the old object.

    delete old;

}

int getMagicNumber()

{

    return (0 != internalObject ? internalObject->magicNumber() : 0);

}

So here's the moral of the story, to make functions exception safe sometimes it's just a matter of ordering. In the fix above all that was done is to move the delete to the end. Delete operations should always be non-throwing [3]- that's the rule in C++. There's another operation that should also be non-throwing and that is "swap". A non-throwing swap is a good foundation to insuring exception safe code. The fix above is very close to using a swap operation. 

[1] - http://www.gotw.ca/gotw/008.htm

[2] - http://gcc.gnu.org/onlinedocs/libstdc++/manual/using_exceptions.html

[3] - Exceptional C++, Item 16 - Herb Sutter

Exception Specifiers

In the past few years I've gotten away from using exceptions. There are a lot of reasons why- but I blame Sutter. His book "Exceptional C++" scared me for life from using exceptions. That was a few years ago so I figured it was time to face my fears about exceptions and given them another try. The first topic I want to explore is throw specifiers. 

While doing some research on the internet I found the following article from 2002 about throw specifiers [1]. The first thing read was specifying that a function does not throw anything, for example:

void doSomething() throw()

{

    // BLAH

}

This tells users that the doSomething() function shouldn't be throwing any exceptions. However, exceptions can still be thrown from doSomething() but the compiler won't do what you expect! For example, say you did the following:

void doSomething() throw()

{

    throw std::runtime_error("Exception!");

}

And then you called it- what ends up happening with g++ 4.7 is that the runtime_error gets thrown and the program crashes with: 

terminate called after throwing an instance of 'std::runtime_error'

  what(): Exception!

Aborted (coredumped)

Okay, so throw specifiers can specify that no exceptions should be thrown from a function but yet the functions can still be thrown? What kind of backwards feature is this? There's more to the confusion, try catching the exception in this form using this program:

#include <iostream>

#include <stdexcept>

void doSomething() throw()

{

    throw std::runtime_error("Exception!");

}

int main(int argc, char** argv)

{

    try 

    {

        doSomething();

    }

    catch(...)

    {

        std::cout << "CAUGHT IT!" << std::endl;

    }

}

The ellipses (...) in the catch is a catch-all. Any exceptions thrown will be caught and discarded in this program. Here's the unusual part: when a throw specification is added and an exception is thrown that is NOT specified it appears as though the program will not allow a catch in any form and it becomes an automatic crash/terminate! That's really confusing- but it's a case of exceptions behaving the way exceptions should and NOT how the programmer expects.

I guess this is just one of the strange quirks I find scary about using exceptions. To allow a runtime exception to escape you can modify the doSomething throw specification to look like:

#include <iostream>

#include <stdexcept>

void doSomething() throw(std::runtime_error)

{

    throw std::runtime_error("Exception!");

}

int main(int argc, char** argv)

{

    try 

    {

        doSomething();

    }

    catch(std::runtime_error const& err)

    {

        std::cout << "CAUGHT IT!" << std::endl;

    }

}

I also modified the catch to catch a specific exception- and notice it's done by reference. The rule of thumb is to "throw by value, catch by reference" [2]. 

REFERENCES

[1] - http://www.gotw.ca/publications/mill22.htm

[2] - Effective C++, Scott Meyers. Item 13

vim plugin

Recently for no good reason I decided to build a vim plugin. Being a C++ enthusiast the target will obviously be some sort of compiled binary plugin. Scripting vim is kind of tricky- this article is going to go from start to finish in how to build the vim plugin stub. Hopefully it will help someone else since the documentation on the world wide internets can be skimpy when dealing with this topic; the reason it's skimpy is that it just works.

The first step is to write a small program that's in a library:

#include <iostream>
#include <dlfcn.h>

extern "C" 
{

const int libexp95plugin_load(const char* libname)
{
    return (long) dlopen(libname, RTLD_LAZY);
}

const char* libexp95plugin_call(const char* context)
{
    std::cout << "HELLO WORLD!" << std::endl;
    return "Hello";
}

}

Step by step:

#include <iostream>

extern "C"
{

I see this all the time in code- this tells the compiler that the function names included should have 'C' linkage. This allows any other base program (such as vim) a universal way to load this library and also know how to call it.

const char* libexp95plugin_call(const char* context)
{
    std::cout << "HELLO WORLD!" << std::endl;
    return "Hello";
}

}

The final portion of the code is self explanatory. To build this library (I put the code above into a file called exp95.cpp), I use a tool called premake4. Honestly, you could just as easily use straight command line to do it too, but premake4 is easier to read:

solution "exp95"
configurations { "Debug", "Release" }

project "exp95plugin"
kind "SharedLib"
language "C++"
files { "exp95.cpp" }
buildoptions { "-fPIC" }
linkoptions { "-fPIC" }


That's all. The -fPIC flag is the most important since it enables Placement Independent Code. After the plugin is build (inside of libexp95plugin.so), to the following:

> cd ~
> cd .vim
> vim exp95.vim

Inside of exp95.vim add the following:

function! Exp95Function()
    call libcall( "absolute-path-to-libexp95plugin.so", "libexp95plugin_call", "SOMETHING")
endfunction

command Exp95 call Exp95Function()

That's all! I got hung up for awhile because I didn't use the "call" keyword in front of libcall. The lesson there is that if you are not storing the return value from a function call in vim, you must use the call keyword in front. Otherwise you'd get the error:

E492: Not an editor command: ^Ilibcall( ... )

Yeah, not so good. To invoke your new command, all you have to do is fire up vim and execute. From within vim:

:Exp95

Your hello message should pop right up!

std::map insert, stuff I should have already known

Spot the error in the code:

typedef std::map<std::string, CacheEntry*> CacheMap;

typedef CacheMap::iterator CacheIterator;

void doSomething(CacheMap& cacheMap, std::string const& id)

{

    CacheIterator iter = cacheMap.find(id);

    if (iter != cacheMap.end())

    {

        CacheEntry* originalEntry = iter->second;

        CacheEntry* switchedCacheEntry = convertEntry(iter->second);

        delete originalEntry;

        cacheMap.insert(std::make_pair(id, switchedCacheEntry));

    }

}

There are actually a few errors in this code snippet if you are taking into account exception safety. The first error regarding exception safety is performing a delete before keeping the state of the map intact. In C++, destructors can never throw exceptions; therefore deleting the originalEntry is not a big deal. BUT what if the delete succeeds and then the cacheMap.insert throws? The cacheMap is left in an errant state because the entry in the map points at a deleted object. That's not good. The remedy for that error is simple, rearrange the order of the insertion and deletion. There is still another exception safety problem with this in that the switchedCacheEntry object will be dangling but that could be fixed by other means.

The big error that I uncovered when writing code like this was the use of std::map::insert. To me insert means that the element being inserted overwrites the contents in the map; but this is NOT THE CASE [1]. 

"Because element keys in a map are unique, the insertion operation checks whether each inserted element has a key equivalent to the one of an element already in the container, and if so, the element is not inserted, returning an iterator to this existing element (if the function returns a value)."

So there it is. In this case, it will be more efficient to just overwrite the entry in the map rather than attempt an insert. Using an insert in this case will cause us to keep the original entry object in the map instead of our switchedCacheEntry. 

REFERENCES

[1] - http://www.cplusplus.com/reference/map/map/insert/

Why I Don't Like Qt Open Source Projects (typically)

I'm porting a version of the QtCreator libraries from using qmake to premake4. Long long ago I did the same thing with QtCreator 2.5.0 and it turned my love for qmake into pure hatred. Before I had started that project I was firmly in the qmake camp because of it's simple syntax and portability with Qt projects. Then I started having to read other developer's pro files. Maybe I'll dig into qmake's more bizarre features after this blogpost; but what is really grinding my gears about Qt Open source projects right now is the private implementation mechanism they use.

Full disclaimer: private implementations are great. I love the pattern because it allows us to do lazy evaluation, fast swapping, binary compatibility, etc. It's a necessary implementation technique. With that being said, the way that Qt Open source projects do it is RIDICULOUS. Here's an example from the utils library from QtCreator:

#ifndef TIPS_H
#define TIPS_H

...

namespace Utils {
class TipContent;
}

#ifndef Q_MOC_RUN
namespace Utils {
namespace Internal {
#endif

class QTipLabel : public QLabel
{
    Q_OBJECT
...
};

#endif

Then inside of the cpp file:

#include "tips.h"
...

namespace Utils {
namespace Internal {

QTipLabel::QTipLabel() {
...
}

#include "moc_tips.cpp"

} // namespace Internal
} // namespace Utils

Okay, I've seen this pattern before with Qt projects where we will perform a moc-step and then include the resulting moc file at the bottom. I actually think it's a neat idea, most of the time the files have a .moc extension (meaning that the moc app was run on a cpp file). That's not the case here.

What this code is doing is running moc on tips.h, which will process QTipLabel. Because the namespace declarations for Utils and Internal are inside of Q_MOC_RUN, they are not going to be processed in the moc generated code. In other words, if you look at moc_tips.cpp there will be no mention of Utils/Internal. That allows us to nicely include it at the end of the cpp file.

Why go to this much trouble?! I understand wanting to be efficient and using the tools you have but don't twist the use of the tools (moc) to fit these really specific cases. Developers probably would say, "Well it works, so why care?" The reason you want to care and SHOULD care is that this is now the bar that new developers have to rise above to start contributing to your code base. It's code like this that kills projects and causes wasted time in understanding and refactoring. Just use something simple and consistent.

That's the end of my rant about Qt open source for today. Join my rant tomorrow when I continue to not take my meds...

Qt 5 for Android (Fail in MinGW)

I am very interested in running Qt 5 on Android. Qt/QML is THE platform for developing awesome user interfaces in less time than it takes to eat a delicious grilled dinner. When Digia/Qt Open Source announced that it would target Android I fired up the grill. But I was disappointed; even though there is a wiki page that has full instructions on how to set up Qt Creator to build Android apps, there are a copious amount of steps to do the setup! Having fallen victim to these in the past (either they are out of date, don't give enough info, etc.)- I figured I would write about my experiences in following the easy steps online.

The easy steps are found at:

http://qt-project.org/wiki/Qt5ForAndroidBuilding

I will give you background about myself: I am familiar with C++ and have a great love for it. I don't know a thing about developing for mobile/embedded platforms. This will be a challenge for me as I'm unfamiliar with the technical mumbo jumbo. I guess this makes me the perfect guinea pig to do this installation. A word of note before beginning, please take note of the system you are on; in particular know whether you have a 64 bit system vs. 32 bit. I'm doing this installation on a 32-bit system. Let's start!

0) I'm adding a step 0. All of the steps use tools other than what you may already have. The list of tools I've found so far includes:

• Perl: I used Active Perl v. 5.16.3, seems to work so far.
• 7-Zip: Used this to unzip the NDK when you get it.
• Git command line (when installing, make sure you add git to the DOS command line).
• mingw compiler, with the compiler in the path.
• The Java Development Kit (I'll talk more about this later).

After you are done installing all of these tools, make sure they all work on the command line. Open it up and try invoking each program (perl, git, and javac). 7-Zip can be used via a context menu (right click).

1) Android SDK. I downloaded this from http://developer.android.com/sdk/index.html. When I double clicked and installed I selected package 4.0 (that's what my ASUS Transformer can handle). This seemed easy enough so I'm still feeling good about this whole thing.

2) Android NDK. They say you have two options: use the official from Google or use the custom NDK provided in the link. Obviously they prefer the latter. http://code.google.com/p/mingw-and-ndk/downloads/list . This is where I get a little skiddish. There are a lot of choices you can make- so the best advice I can give is to try and match your platform the best you can. In my case, I chose android-ndk-r8e-ma-windows-x86.7z because I want the android NDK for Windows x86. It was the closest match.

3) Qt Creator 2.7.1. Now I didn't build this one- I downloaded the binary. http://qt-project.org/downloads/#qt-creator . 

4) I cloned Qt 5 using the instructions on the main site:

git clone git://gitorious.org/qt/qt5.git qt5

cd qt5

perl init-repository

Surprisingly, the last command is what seems to be taking forever. This will do a bunch of checkouts into your system using git. In fact, it's taking so long I'm going to go to sleep.

5) I attempted to perform a configure call using:

./configure -developer-build -xplatform android-g++ -nomake tests -nomake examples -android-ndk <path/to/ndk> -android-sdk <path/to/sdk> -android-ndk-host windows-x86 -skip qttranslations -skip qtwebkit -skip qtserialport -skip qtwebkit-examples

This didn't work because it did not understand the option "android-ndk-host". At this point, my confidence was shot. I knew the rest of the steps wouldn't work no matter what. There are two issues I have with this configure step: 1) android-ndk-host isn't a recognized flag (the biggest problem) and 2) Where is the documentation for android-ndk-host? Is the argument if you are windows win32-x86 or windows-x86 or does it require the compiler? Some consistency across the platform names would help make this a smoother build process but I digress.

After taking out the -android-ndk-host windows-x86, it seemed to start working. At the very least configuration "succeeded".I chalked it up to, "Maybe the Qt development team removed the android-ndk-host flag, maybe I'm going to be okay!" No.

6) To build this thing, I had to use mingw32-make. This is essentially a cross compilation build and the tools for mingw32 are fine. It uses one of the compilers in the ndk toolchain to actually do the build. The next problem I've run into is that this will not build with mingw32 on Windows- It fails with:

Cannot find -lQtCore5

A valid error. I searched through the directory and I did locate libQtCore5.so. When you get errors like this you know they are coming from some sort of build script error where it isn't putting the library in the correct place. Low and behold I got this error when running mingw32-make:

process_begin: CreateProcess(NULL, move, libQtCore.so.5.1 "..\..\lib ", ...) failed.

Instead of trying to troubleshoot the build scripts on a platform that is fighting me the entire way, I think I'm going to jump over to Linux. It looks like the build is much more "stable" there. Sorry if it sounds like I am complaining about the Qt build; but I think that these are all perfectly valid flaws in the build process. I think the biggest flaw is lack of documentation about what the variables in configure do. 

There Must Be Some Use For...

There's lots of obscure features in C++. One of which is "pointers to Class Members". I remember looking at some high performance code once that used this bizarre feature- I wondered about why this would be preferable. I'm not stating that this is a fair test but it definitely opens room for interpretation on what could be faster:

main1.cpp:

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

enum
{
    SAMPLE_SIZE = 65536
};

class A
{
    public:
        A() : description(), id(rand() % 32767) { }

        std::string description;
        int id;

};


std::ostream& operator<<(std::ostream& out, A const& a)
{
    out << "A(" << a.id << ")";
    return out;
}


int main(int argc, char** argv)
{
    std::vector<A> elements;
    elements.reserve(SAMPLE_SIZE);
    for(size_t i=0; i<SAMPLE_SIZE; ++i)
    {
        elements.push_back(A());
    }

    std::ostream_iterator<A> iter(std::cout, "\n");
    std::copy( elements.begin(), elements.end(), iter);   
}

And I'm going to compare against:

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

enum
{
    SAMPLE_SIZE = 65536
};

class A
{
    public:
        A() : description(), id(rand() % 32767) { }

        std::string description;
        int id;

};


std::ostream& operator<<(std::ostream& out, A const& a)
{
    out << "A(" << a.id << ")";
    return out;
}


int main(int argc, char** argv)
{
    std::vector<A> elements;
    elements.reserve(SAMPLE_SIZE);
    for(size_t i=0; i<SAMPLE_SIZE; ++i)
    {
        elements.push_back(A());
    }

    int A::*idPtr;
    idPtr = &A::id; // Just a numeric value.

    for(size_t i=0; i<SAMPLE_SIZE; ++i)
    {
        std::cout << "A(" << elements[i].*idPtr << ")\n";
    }   
}

The obvious difference is how we are iterating over the container. In main2.cpp I'm using the pointer to class member to access the value whereas the first program uses iterators to perform the outputs. Both solutions are probably acceptable- but I'm seeing better results for main2.cpp! At first I kept the sample size low (under 32767 numbers). For lower number of computations the numbers were identical. Once I upped the sample size to a higher number I've started to see a discrepancy.

The result:

main1: 
real         0m0.021s
user         0m.016s
sys          0m0.000s

main2:

real         0m0.019s
user         0m0.016s
sys          0m0.000s

Like I disclosed before, I'm not sure if this is a fair test. Commentary would be nice on this post. The compiler used was gcc 4.7 on Ubuntu running in a virtual machine. I may consider researching this topic further to see if the performance improvements are consistent.

The Amazing Shared Pointer

Quick entry tonight since I'm bogged down with work for actual work.

Did you know you could add a custom deleter to a shared pointer in boost? Try the following:

#include <boost/shared_ptr.hpp>
#include <iostream>

void doSomething(int* i)
{
    std::cout << "DOING SOMETHING" << std::endl;
}

int main(int argc, char** argv)
{
    boost::shared_ptr<int> blah(new int, &doSomething);
}

Obviously the second argument to the shared pointer can be any sort of functor (provided that operator() takes whatever the shared pointer type is).

Like I said, short and lame tonight.

Direct vs. Copy Initialization (Part 1)

#include "a_func.h"
#include <iostream>

int main(int argc, char** argv)
{
	std::cout << "Case 1 A a1;\n";
	A a1;

	std::cout << "\nCase 2: A a2 = A();\n";
	A a2 = A();

	std::cout << "\nCase 3: A a3(a2);\n"; 	
	A a3(a2);

	std::cout << "\nCase 4: A a4; a4 = a3;\n";
	A a4;
	a4 = a3;

	std::cout << "\nCase 5: A getA() { return A(); } A a5 = getA();\n"; 
	A a5 = getA();

	std::cout << "\nCase 6: A getA2() { A a; return a; } A a6 = getA2();\n";
	A a6 = getA2();

	std::cout << "\nCase 7: A getA() { return A(); } A a7; a7 = getA();\n";
	A a7;
	a7 = getA();

	std::cout << "\nCase 8: A getA2() { A a; return a; } A a8; a8 = getA2();\n";
	A a8;
	a8 = getA2();

	std::cout << "\nCLEANUP!\n";
}


/**

RESULTS


Case 1 A a1;
    A()

Case 2: A a2 = A();
    A()

Case 3: A a3(a2);
    A(A const&)

Case 4: A a4; a4 = a3;
    A()
    A& operator=(A const&)

Case 5: A getA() { return A(); } A a5 = getA();
    A()

Case 6: A getA2() { A a; return a; } A a6 = getA2();
    A()

Case 7: A getA() { return A(); } A a7; a7 = getA();
    A()
    A()
    A& operator=(A const&)
    ~A()

Case 8: A getA2() { A a; return a; } A a8; a8 = getA2();
    A()
    A()
    A& operator=(A const&)
    ~A()

CLEANUP!
    ~A()
    ~A()
    ~A()
    ~A()
    ~A()
    ~A()
    ~A()
    ~A()

ANALYSIS:

Trying to clear up DIRECT vs. COPY initialization. It appears 
that DIRECT INITIALIZATION requires NO CONVERSION. The 
"constructor is available and is an exact match" [1]. The object
is initialized using a single constructor [2].

COPY INITIALIZATION is a little more difficult to understand.
It seems to consist of a series of "conversions". It looks
for ways to do the construction [1]. 

Case 1: It's obvious what's going on here, we construct an 
        object of A using the default constructor. It is 
        destroyed at the end of the scope of main. DIRECT.

Case 2: This one surprised me- only because I've been 
        mistaken a lot. Due to the RETURN VALUE OPTIMIZATION,
        we avoid the cost of a copy constructor and an 
        assignment operator. 

Case 3: This is a simple copy constructor object. Definitely
        is a DIRECT INITIALIZATION.

Case 4: We cannot use the RETURN VALUE OPTIMIZATION in this
        case because we are not using COPY INITIALIZATION. 
        We construct an object using DIRECT INITIALIZATION
        first, then we are forced to use the assignment
        operator.

Case 5, 6: This one surprised me. Only 1 constructor for A fires?
           The compiler must be doing something interesting 
           under the hood. This is copy.

Case 7: This makes sense, we invoke constructor a7 once. Then
        we create another A when calling getA(), finally it 
        uses the copy constructor to initialize. This is COPY
        INITIALIZATION.

case 8: We create a8 with a default constructor, then call getA2
        which creates another object of class A. Finally it uses
        the copy constructor- this is a chain of constructors
        and conversions so I think it is COPY.

It looks like Herb Sutter has some pretty interesting 
articles. Going to go over them a bit more because there is 
a lot more nuance to this than I originally thought. (This
post was supposed to be short!).

REFERENCES

[1] - http://stackoverflow/questions/1051379/is-there-a-difference-between-copy-initialization-and-direct-initialization

[2] - http://www.gotw.ca/gotw/036.htm

*/