Roots of Software Inefficiency

Being a GEEK ACMer or TopCoder beast (i.e design and analysis of algorithms) is about writing an efficient algorithm in the scope of 3 or 2 functions doing a very specific and limited task. However, writing a software that runs on customers’ computers is bigger than this. A typical windows commercial mid-sized software consists of a set of Executable, Services and DLLs interacting with each other to shape what is called software. The efficiency of algorithms and data structures is necessary but not sufficient: By itself, it does not guarantee good overall program efficiency. It is important to know the roots of software inefficiency if we care about writing fast one.

What are the factors that affect efficiency? Efficient C++ Performance Programming Techniques book By Dov Bulka, David Mayhew made a very good high-level categorization to these factors:

Design Efficiency This involves the program’s high-level design. To fix performance problems at that level you must understand the program’s big picture.  We are talking here about software architecture, UML diagrams, pseudo codes, algorithms, data-structures, and anything you can consider it language independent.

Code Efficiency Small-to medium-scale implementation issues fall into this category. Fixing performance in this category generally involves local modifications. For example, you do not need to look very far into a code fragment in order to lift a constant expression out of a loop and prevent redundant computations. The code fragment you need to understand is limited in scope to the loop body.

Both these 2 levels can be broken down more:

1. Design

1.1 Algorithms and Data Structures Technically speaking, every program is an algorithm in itself. Referring to “algorithms and data structures” actually refers to the well-known subset of algorithms for accessing, searching, sorting, compressing, and otherwise manipulating large collections of data. Oftentimes performance automatically is associated with the efficiency of the algorithms and data structures used in a program, as if nothing else matters which is inaccurate.

1.2 Program Decomposition This involves decomposition of the overall task into communicating subtasks, object hierarchies, functions, data, and function flow. It is the program’s high-level design and includes component design as well as inter-component communication. Few programs consist of a single component. A typical Web application interacts (via API) with a Web server, TCP sockets, and a database, at the very least.

2. Coding

2.1 Language Constructs A programming language is a tool we use to express to computers how to do a specific task. Whether you use C++, C#, Java and you care about performance, you need understand the cost of your programming language constructs so not to be shocked at run time when you program scale. C++ adds power and flexibility to its C ancestor (i.e Object Oriented capabilities). These added benefits do not come for free—some C++ language constructs may produce overhead in exchange.

2.2 System Architecture System designers invest considerable effort to present the programmer with an idealistic view of the system: infinite memory, dedicated CPU, parallel thread execution, and uniform-cost memory access. Of course, none of these is true—it just feels that way. Developing software free of system architecture considerations is also convenient. To achieve high performance, however, these architectural issues cannot be ignored since they can impact performance drastically. When it comes to performance we must bear in mind that:

• Memory is not infinite. It is the virtual memory system that makes it appear that way.
• The cost of memory access is non-uniform. There are orders of magnitude difference among cache, main memory, and disk access.
• Our program does not have a dedicated CPU. We get a time slice only once in a while.
• On a uniprocessor machine, parallel threads do not truly execute in parallel—they take turns.

If you write Windows software, you need read well about WinAPI and dig deep in Windows programming world, to understand how your host operating system – Windows in this case – will execute your program. This applies if you write software for Linux, iOS or any operating system. Good understanding of the host operating system is a must.

2.3 Libraries The choice of libraries used by an implementation can also affect performance. For starters, some libraries may perform a task faster than others. Because you typically don’t have access to the library’s source code, it is hard to tell how library calls implement their services. For example, to convert an integer to a character string, you can choose between
sprintf(string, “%d”, i); or an integer-to-ASCII function call, itoa(i, string); Which one is more efficient? Is the difference significant?

There is also the option of rolling your own version even if a particular service is already available in a library. Libraries are often designed with flexibility and reusability in mind. Often, flexibility and reusability trade off with performance. If, for some critical code fragment, you choose to put performance considerations above the other two, it might be reasonable to override a library service with your own home-grown implementation. Applications are so diverse in their specific needs, it is hard to design a library that will be the perfect solution for everybody, everywhere, all the time.

2.4 Compiler Optimizations Simply a more descriptive name than “miscellaneous,” this category includes all those small coding tricks that don’t fit in the other coding categories, such as loop unrolling, lifting constant expressions out of loops, and similar techniques for elimination of computational redundancies. Most compilers will perform many of those optimizations for you. But you cannot count on any specific compiler to perform a specific optimization.For ultimate control, you have to take coding matters into your own hands.

I remember how Visual Studio saved my team in an Image Processing performance competition in my faculty. In this competition your image processing package has to run many image processing algorithms and your package timing in each algorithm is used to rank it among the others. We optimized some of our algorithms manually, but didn’t have much time to optimize the others. I got an evil idea of enabling Visual Studio code optimization, and I was shocked by the results. The running time of many algorithms dropped down greatly and I couldn’t believe how C++ code optimization held by the compiler can be that effective.

Conclusion

1. Teach yourself how to design and analyze algorithms and practice well (i.e problem solving through ACM Online Judge and TopCoder)
2. Pick a programming language and master it (i.e read about its internals and understand the scary dark side of it).
3. Know the internals of a certain operating system on which you prefer to write your software (e.g Windows, Linux or Mac OS programming).
4. Write big multi-file, multi-module projects with real requirements.

Events and Delegates: A C++ Implementation

Hi geeks! Hope for you a good coding and debugging day, free of Access Violation and Linkage errors.

First of all, Who should read this article?

• C++ geek, who dreams of pointers, watches "Bug attack" movies, and prefers to trace the call stack all the night rather than going out with some friends.
• C# cool dude, sick of Microsoft babysitting, and willing to move to C++, and aware of the trade-offs.
• Java bean, that never heard of pointer to function concept, and wants to know how C++/C# guys suffer.
  

I have been using C# for around 2 years. I was totally fascinated by C# object oriented architecture. Events and delegates are of the most C# constructs I liked. However, there is a big trade-off here i.e using delegates in C#, it is flexibility and performance. Delegates in C# are no function to pointers rather they are implemented somehow using reflection. I was shocked when I read an article called Writing Faster Managed Code: Know what things cost, this article is talking about the cost of most common C# operations. You will be surprised when you find that in C# a function call using a delegate is slower 6 times than simply calling a function using its signature. The function call using its signature costs around 6 ns (nano second), while using delegate costs around 40 ns! If you are a normal geek then you should be shocked now. As a consequence to this shock, I don’t know how it happened, but months ago I felt that C++ is calling me. I started to code everything using C++. The geek inside me is controlling! Help me.

Coding C++ again after 1 year of pure C#ing is not easy. I was used to delegates and events heavily in my code to maintain a decoupling between classes. I couldn’t find something like: Click += new Handler(ClickHandler); The only way to achieve something near this in C++ is through function to pointers. A first attempt was done here in this article Meet Functors. The first attempt was about implementing generic delegates, but unfortunately it was over complex, and requires a lot of code to deal with. A second attempt was made, and it is about implementing Events and Delegates in C++ like those in C#. That is what this article is all about.

We are not going to explain the concept here. We will pose the code here, and any explanation required will be in the discussion.

The big goal is the line of code below, i.e approaching C# syntax as much as possible:

p_server->MessageSent += new ClientDelegate(this, &Client::MessageSentHandler);

driver.cpp

class Server; class Client; typedef Event<Server> ServerEvent; typedef Delegate<Client, Server> ClientDelegate; class Server { public: ServerEvent MessageSent; void SendMessage(char* p_msg) { MessageSent(this, p_msg); } }; class Client { static int s_id; int m_id; void MessageSentHandler(const Server* p_sender, void* p_parameter) { cout << "Client" << m_id << ": received: " << (char*)p_parameter << endl; } public: Client(Server* p_server) { m_id = ++s_id; p_server->MessageSent += new ClientDelegate(this, &Client::MessageSentHandler); } }; int Client::s_id = 0; int main() { Server server; Client client1(&server), client2(&server), client3(&server); server.SendMessage("Hello"); return 0; }

Console Output

Client1: received: Hello  Client2: received: Hello Client3: received: Hello Press any key to continue . . .

Delegate.h

template<class TSender> class BaseDelegate { public: virtual bool Equals( const BaseDelegate<TSender>* p_other) = 0; virtual void operator()( const TSender* p_sender, void* p_parameter) = 0; virtual void Call( const TSender* p_sender, void* p_parameter) = 0; }; template<class TReciever, class TSender> class Delegate : public BaseDelegate<TSender> { private: typedef void (TReciever::*PTF)(const TSender*, void* p_parameter); PTF m_ptr2Func; TReciever* m_ptr2Object; public: Delegate(TReciever* p_ptr2Object, PTF p_ptr2Func) { m_ptr2Func = p_ptr2Func; m_ptr2Object = p_ptr2Object; } bool Equals(const BaseDelegate<TSender>* p_other) { const Delegate<TReciever, TSender>* other; other = static_cast<const Delegate<TReciever, TSender>*>(p_other); assert(other != NULL); assert(m_ptr2Object != NULL); return other->m_ptr2Object == m_ptr2Object && other->m_ptr2Func == m_ptr2Func; } virtual void operator()(const TSender* p_sender, void* p_parameter) { assert(p_sender != NULL); (m_ptr2Object->*m_ptr2Func)(p_sender, p_parameter); } virtual void Call(const TSender* p_sender, void* p_parameter) { assert(p_sender != NULL); (m_ptr2Object->*m_ptr2Func)(p_sender, p_parameter); } };

Event.h

template<class TSender> class Event { list< BaseDelegate<TSender>* > m_observers; void Register( const BaseDelegate<TSender>* p_handler); void Unregister( const BaseDelegate<TSender>* p_handler); public: void operator += ( const BaseDelegate<TSender>* p_handler); void operator -= ( const BaseDelegate<TSender>* p_handler); void operator () ( const TSender* p_sender, void* p_parameter); void Call( const TSender* p_sender, void* p_parameter); ~Event(); }; template<class TSender> void Event<TSender>::operator += (const BaseDelegate<TSender>* p_handler) { Register(p_handler); } template<class TSender> void Event<TSender>::operator -= (const BaseDelegate<TSender>* p_handler) { Unregister(p_handler); } template<class TSender> void Event<TSender>::operator ()(const TSender* p_sender, void* p_parameter) { Call(p_sender, p_parameter); } template<class TSender> void Event<TSender>::Register(const BaseDelegate<TSender>* p_handler) { assert(p_handler != NULL); for(list< BaseDelegate<TSender>* >::iterator itr = m_observers.begin(); itr != m_observers.end(); itr++) { if((*itr)->Equals(p_handler)) return; } m_observers.push_back(const_cast<BaseDelegate<TSender>*>(p_handler)); } template<class TSender> void Event<TSender>::Unregister(const BaseDelegate<TSender>* p_handler) { assert(p_handler != NULL); vector< BaseDelegate<TSender>* >::iterator where; for(list< BaseDelegate<TSender>* >::iterator itr = m_observers.begin(); itr != m_observers.end(); itr++) { if((*itr)->Equals(p_handler)) { where = itr; break; } } m_observers.erase(where); } template<class TSender> void Event<TSender>::Call(const TSender* p_sender, void* p_parameter) { for(list< BaseDelegate<TSender>* >::iterator itr = m_observers.begin(); itr != m_observers.end(); itr++) { (*itr)->Call(p_sender, p_parameter); } } template<class TSender> Event<TSender>::~Event() { for(list< BaseDelegate<TSender>* >::iterator itr = m_observers.begin(); itr != m_observers.end(); itr++) { assert(*itr != NULL); delete (*itr); } }

I leave you with the code, feel it and test it. If you detect any bug please don’t hesitate to fire it here. Any questions are very welcomed.