The Legend of C++: Learn me if you can

This is my forth and last year in university studying to get bachelor’s degree in software engineering. Since the first year (2009) I’ve introduced to C++ Programming Language. Since year three (fall 2011) I was teaching C++ new students as a teacher assistant. Though sometimes I feel I’ve never learned even a bit of C++ ! I never stopped studying, coding but every day I learn a new, surprising fact about the language.

"Learn Me if You Can" Poster :D

“Learn Me if You Can” Poster 😀

The last interesting feature of C++ I learned today, is called surrogate call functions. That is the simple fact:

Template arguments can be callable objects or function pointers

After a short WTF moment, I realized that the feature is extremely useful. Then I passed a little longer “Why didn’t i think of that?” moment. Finally my mind get addicted to the subject. I can’t wait to use it in my codes 🙂

template<typename FT1, typename FT2>
class callable_object {
  FT1 *f1;
  FT2 *f2;

public:
  callable_object(FT1 *_f1, FT2 *_f2):f1(_f1), f2(_f2) { }
  operator FT1*() { return f1; }
  operator FT2*() { return f2; }
};

void f(const int& i){ /* do something useful */ }
void g(const double& d){ /* do something useful */ }

int main() {
  callable_object<void(const int&), void(const double&)> c(foo, bar);
  c(10);   // ==> f
  c(10.0); // ==> g
}
Advertisements

LibAIT: A General-purpose Artificial Intelligence Toolkit

Recently I had a course on Constraint Satisfaction Problems in my university. The subject was so interesting to me. We studied basic concepts and recent works on CSPs, and also, distributed CSPs and parallel search algorithms used to solve this kind of problems. Among these staff Asynchronous Backtracking was the most interesting to me. For my final project of CSP course, My friend and I have implemented an improvement of ABT that uses polynomial space. Better improvements exists, especially Agile-ABT which we failed to implement in-time.

A Simple Constraint Satisfaction Problem

A Simple Constraint Satisfaction Problem

During research phase I was looking around to find similar projects. Then encountered Geocode project (generic constraint development environment). Its documentation says:

gecode-logo

Gecode Logo

Gecode is a toolkit for developing constraint-based systems and applications. Gecode provides a constraint solver with state-of-the-art performance while being modular and extensible. Gecode is:
open, comprehensive, efficient, documented, free, portable, parallel and tested

Well, that is a very nice set of features. The developers of project have done a great job. They pretend that gecode is most optimized and efficient infrastructure of CSP:

Gecode offers excellent performance with respect to both runtime and memory usage. It won all gold medals in all categories at the MiniZinc Challenges from 2008 to 2012: 2012, 2011, 2010, 2009, and 2008.

Unfortunately the library has some drawbacks making it useless for simple CSP staff. Most importantly, I think gecode is hard to use. In order to solve a CSP you need to inherit from a class of library, add constraint sets by hand, in code, and compile. While it’s so flexible and fast, it’s a little bit hard to use. This gives me an idea: Implement an easy-to-use, portable and efficient library for doing CSP staff.

At first glance it looks like re-inventing the wheel. Well, it’s kind of. But not exactly! The library I’m thinking of is much more simpler. It’s supposed to be fast. Most important feature that I need to include, is support for XCSP 2.1 specification. This file structure is the standard XML-based description of constraint satisfaction problems developed by International CSP Solver Competition comitee. User should be able to implement his/her own CSP solver, on the top of infrastructure layer. Infrastructure do the boring, repeated staff. Generic CSP solver should be able to read CSPs from XCSP files or streams and then convert them into a well-defined data structures, very close to formal definition of CSP. Any other solver is supposed to inherit from GCSPS. Nothing special is here. This is just matter of OOP design. I must take care to avoid making a disaster design. You know, it’s very easy in C++ to make a mess 😀

The killer feature of my (not-yet-born) library, is support for XCSP. XCSP 2.1 is very flexible. You can define constraints, relations, functions and generalized constraints in terms of XML. It supports MathML and a C-style notation with a set of functions to declare implicit constraints.

For example consider N-Queens problem. One can easily define a predicate to “implicitly” specify constraints:

<predicates nbPredicates="1">
<predicate name="P0">
  <parameters>int X0 int X1 int X2</parameters>
   <expression> 
    <functional>and(ne(X0,X1),ne(abs(sub(X0,X1)),X2))</functional>
  </expression>
</predicate>
</predicates>

And then, many constraints can refer to same predicate:

<constraints nbConstraints="66">
  <constraint name="C0" arity="2" scope="V0 V1" reference="P0">
    <parameters>V0 V1 1</parameters>
  </constraint>
  <constraint name="C1" arity="2" scope="V0 V2" reference="P0">
    <parameters>V0 V2 2</parameters>
  </constraint>
  <!-- And so on... -->
</constraints>

This makes things simpler. You don’t need to have a huge C set. I’m planning to simulate same idea in C++ code using function pointers. It’s not very easy… I will need a good XML parser and I need to implement very fast lexer/parser pair to interpret C-style notation of functional objects.

It may be fast enough to catch gecode!

Final word: I am planning to add AI-planner infrastructure (PDDL parser, etc) in far future. That’s why it’s named libAIT instead of libGCSP !

Challenge accepted 🙂

C++1y Concurrent Data Structures

Parallelism!

Parallelism and Concurrency in Modern C++

I always come across this situation: I have some program, or multiple programs running concurrently, they need to share a data. The shared data needs to be protected against read/write violation.

Well, this is known as reader/writer problem: one of traditional problems used to teach concurrency concepts in operating system courses. The well-known solution is lock-do-unlock idiom. Using threading APIs (say POSIX) that they provide mutex mechanism, this can be easily implemented using a mutex per object OR a mutex per critical area. For the first scenario, I have a better solution for object-oriented programming languages that I’m gonna describe it in this post. And also I’ll provide a possible syntax for C++.

Motivation

Suppose we have a class that it’s instances are supposed to be shared between threads. Of course all operations that modify the class should not be concurrent. Well this is not true for all possible scenarios We may want to do two independent operations, say o1 and o2, concurrently if we can make sure about safety. We can have a data structure containing two independent structures, and providing independent operations, o1 and o2, each one modifying one of internal structures. Anyway.. that’s not the common case I wanna present.

The well-known solution to reader-writer problem is to lock the critical area by mutexes. This is a bad solution. Why? First it’s inelegant. Second It lacks readability: Which mutex guards which data? Third its error-prone. What happens when you forgot an unlock? Obviously deadlocks.

This is a small example of my experience with AIT library. I was implementing Asynchronous Backtracking algorithm using a multi-agent fashion. Each agent has two threads: Message reader and Algorithm workhorse. First one reads messages from a TCP socket and stores them in a queue, second reads message from that queue and erases recently read message. Here is the code:

// Algorithm workhorse
pthread_mutex_lock(&this->messageRW);   // lock the door
P_Message x = this->messageQueue.pop(); // do the job
pthread_mutex_unlock(&this->messageRW); // get out of there
// somewhere else, in another thread
while (true) {
    P_Message message;
    solver->listener->recvMessage(message);
    pthread_mutex_lock(&(solver->messageRW));   // lock the door
    solver->messageQueue.push(message);         // do the job
    pthread_mutex_unlock(&(solver->messageRW)); // get out of there
    sem_post(&solver->messageCount);
}

That’s not the end of world. Everything works fine, though consider the fact that there are some scenarios in which you need to do the first part many many many times! Yes that’s the points. You probably don’t want to wrap each modification code in the ugly lock / unlock pairs.

Better Solution

So far, we have seen how bad mutexes are 🙂 Just kidding. They’re great. And I’m doing to present a mutex-based solution to remove lock / unlock pairs.

Suppose C++ has a keyword concurrent. This keywords comes before a complex type and magic begins. All non-const accessors and modifiers, in fact every single method or operator implemented in the class/structure, becomes wrapped in the lock/unlock pairs. For example, consider the std::queue class. We want to suppose that it’s safe to read head of the queue and append a new item to its tail at the same time (well I mean in two threads.) But it’s obviously not safe to append enqueue two items. In my very own solution, all I need to do is just put the keyword concurrent before declaration of std::queue.

concurrent std::queue<protocols::csp::abt::P_Message> messageQueue;

This keyword makes compiler to generate a code which in every non-const method of std::queue is wrapped in a lock / unlock pair. Consider following method which is implemented somewhere in stdlib.

std::queue::push_back(const T& item){
    // some of stdlib secret codes
}

Happens to be

std::queue::push_back(const T& item){
    // this->mutex->lock()
    // some of stdlib secret codes
    // this->mutex->unlock()
}

This way I can tell the compiler to call which function. In fact to generate the code tha calls which function. But before this, I need to tell the complier, which classes are supposed to be used concurrently. So I can use same keyword before class definition. Adding that keyword, causes compiler to generate binary code for two versions of each non-const operation:

// somewhere in stdlib accessed by #include <queue>
namespace std{
template <typename T>
concurrent class queue{
    // class definition
}

In the worst case, making a class concurrent, almost doubles size of generated binary. On the other hand there exist some design scenarios in which programmer don’t want to make a non-const operation thread-safe. One may need to have a partially concurrency-enabled class. For this two reason, it’s better to provide ability to declare concurrency status of each method separately. Again, using the same magic keyword: concurrent.

Of course there are ambiguities within this proposal. This post describes main idea. I’m gonna submit the detailed proposal to the C++ WG comitee, SG1, tomorrow.