Thread safe graphs

[Alpar Juttner]

We should agree what kind of thread safety is required from the LEMON.

For example, we probably want to ensure that the parallelism is safe as far as it is not modifies a graph simultaneously. The only problem is with maps, for creating a new map should not be considered as graph modification. A partial solution could be some kind of static map implementation (see #224). To make the dynamic maps thread safe, we must face with the following problems.

Map allocations/deallocations::

As far as I see, this can be made thread-safe simply by using a mutex on there operations.

Adding/deleting new edges::

This is a much more difficult question. We must carefully declare what kind of thread safety we want to provide here.

Anyway, the implementation of static maps (#224) and its usage in the lemon core tools would solve the most important multithread requirement, namely the possibility of running more built-in algorithms on the same graph in parallel.

[Balazs Dezso]

I have another approach for solving the multithread problems of graphs.

We can define an abstract class Lock, which has two methods lock() and unlock(). The user can create concrete implementations of this class.

In addition there should be an abstract class LockFactory, which has one method create() which just gives back a dynamically created object of a concrete implemntation of Lock and three static member functions setDefaultFactory(), defaultFactory() and createDefault(), which can be used to set and get the default factory, and the create() method of the default factory can be called directly.

The default factory is empty initially (null pointer), but it can be set to own implementation. When a graph is created, it creates a lock for itself (if the default factory is not null). When it modifies its map list, it can use mutual exclusion for concurrent modifications.

In the library, we can provide some factories, for example for pthread, windows threads, common c++ threads, but all of them are optional, and switched off in default behavior.

[Alpar Juttner]

I can't understand how e.g. ListGraph? would get an instance of the this class.

[Balazs Dezso]

Proof-of-concept

[Balazs Dezso]

Replying to alpar:

I can't understand how e.g. ListGraph? would get an instance of the this class.

The patch [4e4e2b7e8ab5] is an example how can be implemented my idea. Some additional work needs, for example additional lockers, automake and cmake integration, better place for the files.

[Balazs Dezso]

And I forget that, but if the user want to defend the maps in an application, then he have to add a line at beginning of the main:

int main() {
  ThreadFactory::setDefaultFactory(new PThreadFactory());
  ...
}

[Alpar Juttner]

Now I think I got the idea.

Two questions:

• Do we want to restrict this approach to locks? If not, we should use the name ThreadFactory instead of LockFactory, in order to reserve the possibility of implementing other threading primitives at later time.
• Do we want to use this solely for Map allocation? How expensive operation a mutex lock is (compared to e.g. a virtual function call). I believe the overhead of a virtual function call is negligible in case of a Map creation anyway, but what about other possible use cases?

[Balazs Dezso]

Replying to alpar:

Now I think I got the idea.

Two questions:

• Do we want to restrict this approach to locks? If not, we should use the name ThreadFactory instead of LockFactory, in order to reserve the possibility of implementing other threading primitives at later time.

In my opinion, if we want to implement parallel algorithms, then we should not wrap a library (at least not with virtual functions).

• Do we want to use this solely for Map allocation? How expensive operation a mutex lock is (compared to e.g. a virtual function call). I believe the overhead of a virtual function call is negligible in case of a Map creation anyway, but what about other possible use cases?

I think, if the thread is not blocked on the lock, then the locking is pretty cheap (For example, one Compare-And-Swap operation.). So virtual functions can have overhead.

I would like to take another look on this problem, maybe a lock free list implementation could also be a solution (​http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms). However, the double linked list implementations are not from the trivial lock free data structures.

[Alpar Juttner]

I made the following quick experiment with deba's proof-of concept​.

  Graph g;
  std::queue<Map *> queue;

  Timer tf;
  Timer ti;

  for(int i=0;i<lag;i++)
    queue.push(new Map(g));

  logTime("lag",ti);

  ti.restart();
  
  for(int i=0;i<repeat;i++)
    {
      queue.push(new Map(g));
      delete queue.front();
      queue.pop();
    }
  
  logTime("alldeall",ti);
  logTime("full",tf);

I run this with lag=100 and repeat=100000000 using

1. the current hg main version, [b1744d7bdb47],
2. the same version augmented with the above patch, but switching off thread safety (i.e. using the default setting)
3. like 2. using PThreadLockFactory.

They were all compiled in Release mode (i.e. using -O3). The running time results are the following.

Current version	22.07 s	-
Using the patch	22.27 s	+0.9%
Turn off pthread	26.39 s	+20%

To sum up, running time penalty of using this patch is negligible, but actually using it causes considerable slow down. However, this is a very extreme situation (the graph is empty and we did nothing else but map allocation). In a real algorithm these operations probably take only a very small fraction of the total running time.

[Alpar Juttner]

Another question: It is possible that _observers.insert() fails (throws an exception) withing th lock()/unlock() closure of attach()? If yes, then what will happen in that case?

[Alpar Juttner]

Let us decide - do we this solution to be a general purpose locking/threading tool or just a specific one supporting the thread safe graph map allocation only.

In the latter case, let us choose a more specific name.

[Balazs Dezso]

I uploaded another patch for providing thread-safe map construction and destruction:

• It uses cmake to check the threading support on the current system
• The pthread and win32 threads are supported currently (the latter is tested with mingw on linux and with wine).
• It is moved to bits, and it does not have user facing interface.
• Automake is not supported yet.

The patch is [25f977576e5c].

[Alpar Juttner]

Replying to deba:

I uploaded another patch for providing thread-safe map construction and destruction:

I'm afraid lemon/bits/lock.h is missing from the patch. Could you please add it, as well.

[Balazs Dezso]

Replying to alpar:

Replying to deba:

I uploaded another patch for providing thread-safe map construction and destruction:

I'm afraid lemon/bits/lock.h is missing from the patch. Could you please add it, as well.

You are right, the updated changeset is there with [18cbd451f2b7] hash.

[Alpar Juttner]

Replying to deba:

You are right, the updated changeset is there with [18cbd451f2b7] hash.

Thanks. I prefer the new version compared to the previous one. The previous version made it impossible to use LEMON as a header only lib. I'm glad the see this limitation having gone away.

The only limitation I see right now is that it is difficult (impossible?) for the user to choose the locking library. I don't think it is really an issue in practice.

So, I pushed the changeset (with changed commit log) as [43a91b33f374] to the main branch.

I still keep the ticket open, for I plan to tweak the CMAKE config a bit. Besides, I would like to see some more elaborate performance evaluations.

[Alpar Juttner]

I've run again the same test as described in my comment with the latest version of the patch. Here comes the result:

Last version before the patch	21.93 s	-
Using the patch	25 s	+14%

The 14% overhead is quite significant, but remember this is a very extreme situation.

[Alpar Juttner]

Changeset [48e17328c155] implements a CMAKE variable called LEMON_THREADING determining the threading library to be used. The current choices are Pthread, Win32 and None. It defaults to a sensible value, but that can be overwritten, e.g.

cmake -DLEMON_THREADING=None ..

switches off the locking mechanism even if a threading library is available on the system.

[Balazs Dezso]

Currently, the feature is implemented only for cmake.

Can we state that the automake build system is deprecated? We might want to add a ticket to the issue tracker to port missing features to cmake, and remove the automake build system.

[Alpar Juttner]

Replying to deba:

Currently, the feature is implemented only for cmake.

Can we state that the automake build system is deprecated?

Yes, it will be deprecated with release 1.3.

We might want to add a ticket to the issue tracker to port missing features to cmake, and remove the automake build system.

I did it just a couple of minutes before your comment, see #434. If you see any more missing feature, add them to that ticket.