Intrusive or non intrusive

views:

answers:

+2 Q:

Intrusive or non intrusive

I am writing a multi threaded server app that requires stability and high performance. I'm looking at using Boost for some data structures I need.

Is an intrusive data structure better or worse for something that should be thread safe and needs fast access, insertion, etc:::: ?

+2 A:

Intrusive data structures are not inherently better or worse than non-intrusive data structures.

The best choice is not to share data between threads. If threads do need to share data, the second best choice is a read-only data structure, which consequently needs no synchronization.

Shared data structures are a communication path between threads. As such you need to think carefully about whether having a directly-shared data structure is the best means of communication. What do you need of the data structure? Would a message queue suffice? Do you need concurrent access to the same data, or do different threads access distinct parts of the data structure?

There is nothing about intrusive data structures that makes them any better or worse than the alternatives for multi-threaded use in general.

Anthony Williams 2010-09-29 08:50:31

Intrusive data structures are inherently different, and any intrusive data structure can be turned into a non-intrusive one. Intrusive stuctures are faster (no extra pointer dereference needed) and require less memory (no extra blocks needed for nodes). The biggest problem with them is that they require each list to have its own field within the structure (from a C perspective).

wj32 2010-09-29 09:03:42

@wj32 Details such as you describe very much depend on the implementation of the intrusive and non-intrusive data structures being compared. The only defining property of an intrusive data structure is that the data-structure management info associated with each data item is in the data item itself (and is thus user-visible), and that the data items are allocated by the user. This does not imply anything about speed or memory requirements.

Anthony Williams 2010-09-29 09:25:10

The very fact that information for each node is embedded in the structures themselves makes intrusive data structures faster. What intrusive data structure needs to allocate memory more times (if at all) than a non-intrusive data structure of the same type? I do not know how things work in C++, but I can tell you that in C, it is fairly obvious that an intrusive doubly-linked list, for example, is *much* faster than a non-intrusive one.

wj32 2010-09-29 10:39:11

@wj32: I agree that embedding the data in the node can have fewer indirections and memory allocations than storing a pointer-to-data in the node. That doesn't make it intrusive. A common implementation for `std::list<>` embeds the data in the nodes, but no-one would call it intrusive, as the user doesn't need to know about the internal data structure. You couldn't have a `list<int>` if it was intrusive, as an `int` has nowhere to store the information.

Anthony Williams 2010-09-29 12:06:51

It seems that you think of intrusive-ness as a matter of abstraction. I think of it as direct/indirect with regards to pointers.

wj32 2010-09-30 00:10:43

ansaurus

tags:

views:

answers:

Intrusive or non intrusive

related questions