Need help with threading optimization

Question

0.00/5 (No votes)

See more:

I have a program that starts with a list of objects of a specific class. The first object is assigned to a local variable and then removed from the list. Work is performed on this local variable which may result in a new list of objects of the same class. if a list is returned then the objects are inserted back into the original list sorted based on a property of the class. The process is repeated until there are no more objects in the list.

The code is based on a branch and bound approach to finding the optimal solution to a problem. Each answer receives a score which is the Result property. The lower the score the better. The answers with the best score are chosen to be iterated on producing new answers, each with their own score, which are placed back into the list. Once certain criteria are met, an answer is considered final and is no longer worked on. Once an answer is final it is checked against the current best answer (if any) and becomes the best answer if it has a better score. The way the scoring algorithm work makes it impossible for an answer to produce an answer with a lower score, thus once a best answer is found any answers in the list with a higher score cannot produce a better answer and can be removed from the list.

VB

Dim MainList as new List(of B)
Populate(MainList ) ' Populates MainList 
Dim Best as B = Nothing

Do
  Dim Current as B = MainList(0)
  MainList.RemoveAt(0)
  Dim SubList as list(of B)=PerformWork(Current) ' Function that preforms the work
  if Sublist.Count > 0 then
    If Sublist(0).IsFinal then ' Note that only 1 item will be returned if IsFinal is true
      If Best Is Nothing OrElse Best.Result > SubList(0).Result then
        Best=Sublist(0)
        Remove(Best.Result) ' Removes all items in MainList that have a Result > Best.Result
      End if
    Else
      Insert(SubList) ' Sub that inserts all the items in SubList into MainList
    End if
  end if
Loop While MainList.Count > 0

My goal is to parallelize this process by taking the first n number of objects and starting a thread for each which will return the list of objects. As each thread returns, the returned list of objects will be inserted into the list and the current first object will be passed to a new thread.

Every example I have seen will just loop through the entire list and create a new thread for each object. Since I only want to focus on the best objects and this will change as the program runs, I do not think this is the best approach. I could just loop through the first 4 items, and keep that going, but I plan on using multiple computers and each would have to have the software tuned specifically for it. Is there any way to have the framework determine the best number of threads?

What I have tried:

Nothing code wise so far, just looked at a lot of articles that are not much help.

Posted 12-Jul-17 10:22am

Beachhouse13

Updated 14-Jul-17 8:29am

v2

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Richard Deeming · Answer 1 · 2017-07-14T07:00:00

I don't think the sorting makes any sense. If you're processing the list in parallel, the items can be processed in any order.

The List(Of T) class is not a good choice. It's not thread-safe, and removing items from the start of the list is an expensive operation. I'd suggest using the ConcurrentQueue(Of T)[^] class instead.

You'll need an extension method to get a "consuming" enumerator, that removes items from the queue as they're processed:

VB.NET

Module CollectionExtensions
    <Extension()> 
    Public Iterator Function GetConsumingEnumerator(Of T)(ByVal source As IProducerConsumerCollection(Of T)) As IEnumerable(Of T)
        Dim item As T
        While source.TryTake(item)
            Yield item
        End While
    End Function
End Module

You can then use the AsParallel[^] extension method to consume the list in parallel:

VB.NET

Dim best As B = Nothing
Dim initialList As New List(Of B)
Populate(initialList)

Dim mainList As New ConcurrentQueue(Of B)(initialList)
While Not mainList.IsEmpty
    Dim newItems As IEnumerable(Of List(Of B)) = mainList _
        .GetConsumingEnumerator() _
        .AsParallel() _
        .Where(Function (current) best Is Nothing OrElse current.Result <= best.Result) _
        .Select(Function (current) PerformWork(current)) _
        .Where(Function (newList) newList.Count > 0)
        
    For Each newList As List(Of B) In newItems
        If newList(0).IsFinal Then
            If best Is Nothing OrElse best.Result > newList(0).Result Then
                best = newList(0)
            End If
        Else
            For Each item As B In newList
                mainList.Enqueue(item)
            Next
        End If
    Next
End While

NB: You have a mistake in your current code:

If Best IsNot Nothing OrElse Best.Result > SubList(0).Result then

If Best is Nothing, you'll get a NullReferenceException on that line.