1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Multi-threaded Program Taking Longer To Execute

Discussion in 'Win32' started by Shard, Aug 28, 2010.

  1. Shard

    Shard New Member

    Joined:
    Aug 28, 2010
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    So I'm working on an A* algorithm and I've multi threaded it.

    But for some reason, the multi threaded version takes longer to execute.

    I'm not sure what could be cause the problem so I'm posting the relevant code below in hopes that some one can find the problem.

    Code:
    //Testing Code in Main
    std::clock_t sstart;
    double diff;
    
    for(int i = 0; i < 30; i++)
    {
            sstart = std::clock();
            aStar.SetCurrentSquare(sqr);
            diff = ( std::clock() - sstart ) / (double)CLOCKS_PER_SEC;
            cout threadID[i]);
            }
    
            WaitForMultipleObjects(9, threads, TRUE, INFINITE); 
            for(int i = 0; i < 9; i++) CloseHandle(threads[i]); //Close all handles
    }
    
    long WINAPI MTSetSquare(long mtData) //Calls AStar::SetSquare and passes in an index
    {
            ((MTData*)mtData)->aStar->SetSquare(((MTData*)mtData)->id);
            return 0;
    }  
    
    void AStar::SetSquare(int index)
    {
            if(index != 4)
            {
                    int setSqrX  = NULL;
                    int setSqrY = NULL;
                    bool exist = true;
    
                    switch(index)
                    {
                    case 0:
                            //Top Left
                            if(newCurrent->x > 0 && newCurrent->y > 0)
                            {
                                    setSqrX = newCurrent->x-1;
                                    setSqrY = newCurrent->y-1;
                            }
    
                            else exist = false;
                            break;
    
                    case 1:
                            //Top Center
                            if(newCurrent->y < newCurrent->parentGrid->resolutionOneLess)
                            {
                                    setSqrX = newCurrent->x;
                                    setSqrY = newCurrent->y+1;
                            }
    
                            else exist = false;
                            break;
    
                    case 2:
                            //Top Right
                            if(newCurrent->x < newCurrent->parentGrid->resolutionOneLess && newCurrent->y < newCurrent->parentGrid->resolutionOneLess)
                            {
                                    setSqrX = newCurrent->x+1;
                                    setSqrY = newCurrent->y+1;
                            }
                            else exist = false;
                            break;
    
                    case 3:
                            //Left
                            if(newCurrent->x > 0)
                            {
                                    setSqrX = newCurrent->x-1;
                                    setSqrY = newCurrent->y;
                            }
                            else exist = false;
                            break;
    
                    case 5:
                            //Right
                            if(newCurrent->x < newCurrent->parentGrid->resolutionOneLess)
                            {
                                    setSqrX = newCurrent->x+1;
                                    setSqrY = newCurrent->y;
                            }
    
                            else exist = false;
                            break;
    
                    case 6:
                            //Bottom Left
                            if(newCurrent->x > 0 && newCurrent->y > 0)
                            {
                                    setSqrX = newCurrent->x-1;
                                    setSqrY = newCurrent->y-1;
                            }
    
                            else exist = false;
                            break;
    
                    case 7:
                            //Bottom
                            if(newCurrent->y > 0)
                            {
                                    setSqrX = newCurrent->x;
                                    setSqrY = newCurrent->y-1;
                            }
    
                            else exist = false;
                            break;
    
                    case 8:
                            //Right
                            if(newCurrent->x < newCurrent->parentGrid->resolutionOneLess && newCurrent->y > 0)
                            {
                                    setSqrX = newCurrent->x+1;
                                    setSqrY = newCurrent->y-1;
                            }
    
                            else exist = false;
                            break;
                    }
    
    
    
                    bool good = false;
                    if(exist)
                    {
                            //Enter mutex to check if it has anything in it
                            WaitForSingleObject(squaresMutex,INFINITE);
                            if(squares.size() > 0)
                            {
                                    for(int i = 0; i < squares.size(); i++)
                                    {
                                            if(squares.at(i)->x == setSqrX && squares.at(i)->y == setSqrY) 
                                            {
                                                    //IF it does then set it and leave mutex
                                                    currentSqr.sqrs[index] = squares.at(i);
                                                    good = true;
                                                    ReleaseMutex(squaresMutex);
    
                                                    if(currentSqr.sqrs[index]->x == finderEndSqr.x && currentSqr.sqrs[index]->y == finderEndSqr.y)
                                                            InitializeSquare(*currentSqr.sqrs[index],index);
                                                    break;
                                            }
                                    }
                            }
    
                            //Leave it if it doesn't
                            else ReleaseMutex(oldSquaresMutex);
    
                            if(!good)
                            {
                                    //If not good, enter old squares mutex
                                    WaitForSingleObject(oldSquaresMutex,INFINITE);
                                    if(oldSquares.size() > 0)
                                    {
                                            //if its got stuff in it Get it and exit
                                            GridSqr *sqr = currentSqr.sqrs[index] = oldSquares.back();
                                            oldSquares.pop_back();
                                            ReleaseMutex(oldSquaresMutex);
    
                                            sqr->x = setSqrX;
                                            sqr->y = setSqrY;
                                            sqr->distCost = 0;
                                            sqr->finalCost = 0;
                                            sqr->moveCost = 0;
                                            sqr->parent = NULL;
                                            sqr->parentGrid = newCurrent->parentGrid;
                                            sqr->skip = false;
                                            sqr->closed = false;
    
                                            //Enter squares, set and exit
                                            WaitForSingleObject(squaresMutex,INFINITE);
                                            squares.push_back(currentSqr.sqrs[index]);
                                            ReleaseMutex(squaresMutex);
    
                                            //Open Mutex
                                            if(sqr->parentGrid->grid[sqr->x][sqr->y])
                                            {
                                                    InitializeSquare(*sqr,index);
    
                                                    WaitForSingleObject(openListMutex,INFINITE);
                                                    open.push_back(sqr);
                                                    ReleaseMutex(openListMutex);
                                            }
    
                                    }
    
                                    else 
                                    {
                                            //Else exit old squares mutex
                                            ReleaseMutex(oldSquaresMutex);
    
                                            GridSqr *sqr = new GridSqr;
                                            sqr->x = setSqrX;
                                            sqr->y = setSqrY;
                                            currentSqr.sqrs[index] = sqr;
                                            sqr->parentGrid = newCurrent->parentGrid;
    
                                            //Set in squares mutex and exit
                                            WaitForSingleObject(squaresMutex,INFINITE);
                                            squares.push_back(sqr);
                                            ReleaseMutex(squaresMutex);
    
                                            //Open Mutex
                                            if(sqr->parentGrid->grid[sqr->x][sqr->y])
                                            {
                                                    InitializeSquare(*sqr,index);
    
                                                    //Open open list mutex, set and exit
                                                    WaitForSingleObject(openListMutex,INFINITE);
                                                    open.push_back(sqr);
                                                    ReleaseMutex(openListMutex);
                                            }
                                    }
                            }
    
                    }
    
                    else currentSqr.sqrs[index] = NULL;
            }
    }
    
    Basically, there is a 3x3 grid, and each square in the grid gets its own thread for calculations.
    Then WaitForMultipleObjects waits until all the threads are done and then continues with the rest of the program.
     

Share This Page