COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 5 years ago

#223 closed enhancement (done)

Thread safe graphs

Reported by: alpar Owned by: alpar
Priority: critical Milestone: LEMON 1.3 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

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.

Attachments (3)

4e4e2b7e8ab5.patch (4.8 KB) - added by deba 8 years ago.
Proof-of-concept
25f977576e5c.patch (4.1 KB) - added by deba 6 years ago.
18cbd451f2b7.patch (5.8 KB) - added by deba 6 years ago.

Download all attachments as: .zip

Change History (23)

comment:1 Changed 9 years ago by alpar

  • Priority changed from major to critical

comment:2 follow-up: Changed 8 years ago by deba

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.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 8 years ago by alpar

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

Changed 8 years ago by deba

Proof-of-concept

comment:4 in reply to: ↑ 3 Changed 8 years ago by deba

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.

comment:5 follow-up: Changed 8 years ago by deba

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());
  ...
}

comment:6 Changed 8 years ago by kpeter

  • Milestone changed from LEMON 1.2 release to LEMON 1.3 release

comment:7 follow-up: Changed 6 years ago by 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.
  • 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?

comment:8 in reply to: ↑ 7 Changed 6 years ago by deba

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.

comment:9 in reply to: ↑ 5 ; follow-up: Changed 6 years ago by alpar

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 version22.07 s -
Using the patch22.27 s +0.9%
Turn off pthread26.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.

comment:10 Changed 6 years ago by alpar

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?

comment:11 Changed 6 years ago by alpar

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.

Changed 6 years ago by deba

comment:12 follow-up: Changed 6 years ago by deba

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].

comment:13 in reply to: ↑ 12 ; follow-up: Changed 6 years ago by 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.

Changed 6 years ago by deba

comment:14 in reply to: ↑ 13 ; follow-up: Changed 6 years ago by deba

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.

comment:15 in reply to: ↑ 14 Changed 6 years ago by alpar

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.

comment:16 in reply to: ↑ 9 Changed 6 years ago by alpar

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 patch21.93 s -
Using the patch25 s +14%

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

comment:17 Changed 6 years ago by alpar

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.

comment:18 follow-up: Changed 6 years ago by deba

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.

comment:19 in reply to: ↑ 18 Changed 6 years ago by alpar

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.

comment:20 Changed 5 years ago by alpar

  • Resolution set to done
  • Status changed from new to closed
Note: See TracTickets for help on using tickets.