Threading nested foreach-loops?

Question

Helllo!

I'm trying to build a program that calculates the best score from a various amount of items with bruteforce. And I believe that the speed to calculate this can be improved on systems with multicore CPUs with the help of threading. Correct me if I'm wrong. But how do I achieve this?

Here's a part of my code, and it does the job well (no threading).

private double _bestScore = 0.0;

private void BruteForce()
{
  foreach (Stats head in _heads)
    foreach (Stats chest in _chests)
      foreach (Stats leg in _legs)
        foreach (Stats feet in _feets)
        {
          int stamina = head.sta + chest.sta + leg.sta + feet.sta;
          int power = head.power + chest.power + leg.power + feet.power;
          int armor = head.armor + chest.armor + leg.armor + feet.armor;
          int hit = head.hit + chest.hit + leg.hit + feet.hit;

          double total = stamina * _scaleSta + power * _scalePower + armor * _scaleArmor;

          if (total > _bestScore && hit >= 100)
          {
            _bestScore = total;

            // Store best setup for output when done with bruteforce
            _bestHead = head;
            _bestChest = chest;
            _bestLeg = leg;
            _bestFeet = feet;
          }
        }
}

So, is there anyway to improve this with threading?

Edit: Fixed typo and updated to include another stat, hit. Hit must reach 100 to be a possible part of "best score". This does so I can't check each individual slot first to try and find the best gear. Hit is a very important stat up to 100, but every point after 100 is useless. Also, this part of my code has a lot more of foreach-loops (28 instead of 4). So number of iterations are a LOT. However, each list (_heads, _chests etc) usually contains a maximum of 2 items.

Answer 1

You will probably find adding multiple threads to this will actually slow things down. Is this calculation very slow? What are your expected average counts for heads, chests, legs and feet?

You might be better off finding the highest values for each of heads, chests, etc and discarding the rest, finding the best combination of these selected ones.

Answer 2

I'm pretty sure this will do it, not having any test data or a compiler to hand makes me not 100% confident:

private void BestItems()
{
    _bestHead = GetBestItem(_heads);
    _bestChest = GetBestItem(_chests);
    _bestLeg = GetBestItem(_legs);
    _bestFeet = GetBestItem(_feets);
}


private Stats GetBestItem(List<Stats> items)
{
    double best = 0.0;
    Stats result = null;

    foreach stats item in items
    {
     double total = item.stamina * _scaleSta + item.power * _scalePower + item.armor * _scaleArmor;

     if (total > best)
     {
      result = item;
     }
    }

    return result;
}

Edit:

Steps:

1. Create a list for each slot in order of most important stat (smallest first)
2. Loop through using some kind of weighting to find the smallest values of hit that satisfy your hit rating. (yuo will need this per slot for my next step)
3. For each slot pick item with best stats that meets that slots min-hit rating.

you will need a lot of loops one after the other, but its better than 2^28 i think :p

Edit2: Again, still no compiler here... but this might work. You will end up with a bucket load of threads though...

For thread joining and waiting see here (msdn) (look at mutex, monitor, ManualResetEvent, AutoResetEvent)

private void BruteForce()
{

  var threads = new List<Thread>;
  foreach (Stats head in _heads)
    foreach (Stats chest in _chests)
      foreach (Stats leg in _legs)
        foreach (Stats feet in _feets)
        {
            if (threads.Count <= 2)


      thread worker = new thread(addressof Process, new object() {head, chest, leg, feet, ...});
      worker.start();
      threads.add(worker);
        }

    foreach (Thread t in threads)
     t.join();  //this might not be the best as it might make the main thread wait for each thread one after the other, not when all finished.  A manual/auto reset is probably better here.
}


private void Process(params...)
{

    int stamina = head.sta + chest.sta + leg.sta + feet.sta;
    int power = head.power + chest.power + leg.power + feet.power;
    int armor = head.armor + chest.armor + leg.armor + feet.armor;
    int hit = head.hit + chest.hit + leg.hit + feet.hit;

    double total = stamina * _scaleSta + power * _scalePower + armor * _scaleArmor;

    lock _bestscore
    {
     if (total > _bestScore && hit >= 100)
     {
      _bestScore = total;

      // Store best setup for output when done with bruteforce
      _bestHead = head;
      _bestChest = chest;
      _bestLeg = leg;
      _bestFeet = feet;
     }
    }
}

EDIT 4: Guess who still doesnt have a compiler near him? Something along the lines of this should make sure you only have 2 threads alive at any point.

var threads = new Dictionary<Guid, Thread>;

private void BruteForce()
{
  foreach (Stats head in _heads)
    foreach (Stats chest in _chests)
      foreach (Stats leg in _legs)
        foreach (Stats feet in _feets)
        {
            while (threads.Count >= 2) {}    //im sure thread.join or equivelent can do this instead of a nasty loop :p

            var guid = Guid.NewGuid();
            thread worker = new thread(addressof Process, new object() {guid, head, chest, leg, feet, ...});
            worker.start();
            threads.add(guid, worker);
        }

    foreach (Thread t in threads)
        t.join();  //this might not be the best as it might make the main thread wait for each thread one after the other, not when all finished.  A manual/auto reset is probably better here.
}

private void Process(params...)
{
    int stamina = head.sta + chest.sta + leg.sta + feet.sta;
    int power = head.power + chest.power + leg.power + feet.power;
    int armor = head.armor + chest.armor + leg.armor + feet.armor;
    int hit = head.hit + chest.hit + leg.hit + feet.hit;

    double total = stamina * _scaleSta + power * _scalePower + armor * _scaleArmor;

    lock _bestscore
    {
        if (total > _bestScore && hit >= 100)
        {
            _bestScore = total;

            // Store best setup for output when done with bruteforce
            _bestHead = head;
            _bestChest = chest;
            _bestLeg = leg;
            _bestFeet = feet;
        }
    }

    _threads.remove(guid)
}

Answer 3

If you want the simple way of adding multithreading, look into the Parallel Extensions for .NET. For performance reasons, you will only want to put a Parallel.For() call on the outermost loop.

Answer 4

An aproach to this problem is to unnest some of the loops and so create some work items that can be processed in parallel. Something like this:

private struct Stat
{
   int sta;
   int power;
   int armor;
   int hit;
};
private List<Stat[]> workItems = new List<Stat[]>();
private const int NUMBER_OF_CPUS = 4;

private void BruteForce()
{

    //create some work load to split into separate threads
    //we do this by unnesting the first 3 loops.
    //maybe more unnesting is needed to get some more work items
    //for thread to process
    //at least one item per thread/CPU makes sense
    foreach (Stats head in _heads)
      foreach (Stats chest in _chests)
        foreach (Stats leg in _legs)
        {
          this.workItems .Add(new Stat[3] { head, chest, leg });
        }

Next would be to split up that work items into chunks that can be processed by a single thread. You would chose a number of thread that equals the number of CPU cores. Your thread function would at least have a parameter providing, the threads work items.

The beginning of your thread function could look like:

private void Process(object param)
        {
            List<Stat[]> threadWorkitems = (List<Stat[]>)param;

            foreach (Stat workItem in threadWorkitems)
            {
                Stats head = threadWorkitems[0];
                Stats chest = threadWorkitems[1];
                Stats leg = threadWorkitems[2];

                foreach (Stats feet in _feets)
                {
                    int stamina = head.sta + chest.sta + leg.sta + feet.sta;
                    int power = head.power + chest.power + leg.power + feet.power;
                    int armor = head.armor + chest.armor + leg.armor + feet.armor;
                    int hit = head.hit + chest.hit + leg.hit + feet.hit;

                    double total = stamina * _scaleSta + power * _scalePower + armor * _scaleArmor;

                    if (total > _bestScore && hit >= 100)
                    {

What is missing in this snippet is, that you have to collect the best results of all threads and afterwards compare them to find your actual best set.

I hope this gives some hints.

Greetings