classes (C++) vs. structs(C): multithreading on graph objects (e.g. DFS)

[kenneth.bull]

Hi,

Can someone with knowledge of C++ and threads help me?
------------
In C with structs and external functions that acts on the structs (C style of OOP/ADT programming), it was fairly easy to do multithreaded operations on things like graphs.

E.g.,

you have a some heirachy of structs to represent the graph
you have init, modify, etc. functions that are external from the struct definition

and you have operations like DFS, BFS that are also external, so inside these functions you can define stack based storage (like for "visited" flags) that saved state required to do these operations

so it these operations can be made "reentrant" or threadsafe
so you can have more than 1 thread doing a DFS search on the same graph object, for example.

---
But now in C++, if we move these operations inside the struct/class, they become tied to every objects (e.g., graph object).

So if one thread is doing somegraph.dfs( ), how can another thread also do it?
How to make it threadsafe when we include the operations inside the structs/class?

Thanks so much! (I am just learning C++ and coming from C)

 

[David Brown]

Hi,

Can someone with knowledge of C++ and threads help me? ------------
In C with structs and external functions that acts on the structs (C
style of OOP/ADT programming), it was fairly easy to do multithreaded
operations on things like graphs.

E.g.,

you have a some heirachy of structs to represent the graph you have
init, modify, etc. functions that are external from the struct
definition

and you have operations like DFS, BFS that are also external, so
inside these functions you can define stack based storage (like for
"visited" flags) that saved state required to do these operations

so it these operations can be made "reentrant" or threadsafe so you
can have more than 1 thread doing a DFS search on the same graph
object, for example.

--- But now in C++, if we move these operations inside the
struct/class, they become tied to every objects (e.g., graph
object).

So if one thread is doing somegraph.dfs( ), how can another thread
also do it? How to make it threadsafe when we include the operations
inside the structs/class?

Thanks so much! (I am just learning C++ and coming from C)

The C++ code:

class A { int x; void f(void); };
A a;
a.f();

is pretty much equivalent to the C code:

struct A { int x; };
void f(struct A * const this);
struct A a;
f(&a);


When you call a member function for a class object, the call happens in
the context of the calling function - not in some sort of class context
or thread.

 

[Öö Tiib]

Can someone with knowledge of C++ and threads help me?
------------
In C with structs and external functions that acts on the structs (C style of OOP/ADT programming), it was fairly easy to do multithreaded operations on things like graphs.

E.g.,

you have a some heirachy of structs to represent the graph
you have init, modify, etc. functions that are external from the struct definition

and you have operations like DFS, BFS that are also external, so inside these functions you can
define stack based storage (like for "visited" flags) that saved state required to do these operations

so it these operations can be made "reentrant" or threadsafe
so you can have more than 1 thread doing a DFS search on the same graph object, for example.

Indeed. You only have to make sure that none of the threads does write that graph
when some other thread is reading it. How you achieve that in C code?

You perhaps overestimate the extent of extension that C++ has taken with member
functions. Member functions gain access to private and protected members of class,
otherwise they are very similar to external functions. Most of it is only syntax sugar.
The graph pointer parameter of C is now that 'this' in graph member function of
C++. Access to member 'this->somemember' may be (and idiomatically is)
shortened to just 'somemember' inside member function.

The functions can still have their local, automatic storage duration data (that is not
related to other calls) and so can be reentrant.

So if one thread is doing somegraph.dfs( ), how can another thread also do it?
How to make it threadsafe when we include the operations inside the structs/class?

Thanks so much! (I am just learning C++ and coming from C)

For most synchronisation we use either standard C++ thread support
library (with its mutexes,locks,futures,atomics and condition variables) or some
other (platform/framework) synchronisation library. It all works pretty well
in C++ thanks to RAII. My impression is that it is lot more painful in other
languages that use exceptions (like C# or Java).

 

[Jorgen Grahn]

Hi,

Can someone with knowledge of C++ and threads help me?

[snip because I can't be bothered to wrap the very long lines]

So if one thread is doing somegraph.dfs( ), how can another
thread also do it?
How to make it threadsafe when we include the operations inside
the structs/class?

The traditional C++ way of walking a data structure is by iterators.
These are (normally) separate objects, so you don't store any "cursor"
state in the data structure itself. Anything else would be
problematic, not only for multithreading. Imagine walking two
structures to generate matching pairs of elements or something

void print_pairs(std:stream&, const Graph& a, const Graph& b);

Would not work for print_pairs(os, foo, foo) if walking the graph
modified a hidden cursor inside it.

/Jorgen