Given a (double) linked list of objects (C ++), I have an operation that I would like to use multithread for each object. The cost of the operation is not the same for each object. A linked list is the preferred repository for this set of objects for various reasons. The first element in each object is a pointer to the next object; the second element is the previous object in the list.
I solved the problem by building an array of nodes and applying OpenMP. This provided decent work. Then I switched to my own streaming routines (based on Windows primitives) and using InterlockedIncrement () (acting by index into an array), I can achieve higher overall CPU usage and speed up pass-through input. Essentially, threads work through frog-hopping along elements.
My next optimization approach is to try to eliminate the creation / reuse of an array of elements in my linked list. However, I would like to continue this leap-frog approach and somehow use some non-existent procedure, which could be called "InterlockedCompareDereference" - for atomic comparison with NULL (end of list) and conditionally dereference and store, returning dereference value.
I do not think that InterlockedCompareExchangePointer () will work, since I cannot atomically dereference a pointer and call this Interlocked () method. I did some reading, while others offer critical sections or spin locks. Critical sections are important here. I am tempted to try spin locks, but I thought I was asking this question first and asking what other people were doing. I'm not sure that the InterlockedCompareExchangePointer () method itself can be used, for example, as a spin-lock. Then you should also consider the semantics of getting / releasing / fencing ...
Ideas? Thank!
source
share