Bizarrely slow method

Question

I have a method in my project which when placed into its own program takes mere seconds to run, when run inside the project where it belongs it takes 5 minutes. I have NO idea why. I have tried profiling, taking bits out, changing this and that. I'm stumped.

It populates a vector of integers to be used by another class, but this class is not currently being instantiated. I have checked as much as I can and it does seem as if there really is nothing else happening but the method magically taking longer in one project than it does in another.

The method is run at startup and takes about 5 minutes, or about 3 seconds if run on its own. What could be causing this? Strange project settings? Multithreading stuff that I'm unaware of? (as far as I know there is none in my project anyway unless it's done automatically).

There is a link to the project here. If anyone could solve this for me I would be so grateful, and as soon as I can will start a bounty for this.

The method is called PopulatePathVectors and runs in Level.cpp. Commenting out the call to the method (in the level constructor) means the program starts up in seconds. The only other class that uses the lists it generates is Agent, but currently none are being instantiated.

EDIT - As requested, here is the code. Although keep in mind that my question is not 'why is the code slow?' but 'why is it fast in one place and slow in my project?'

//parses the text path vector into the engine
void Level::PopulatePathVectors(string pathTable)
{
    // Read the file line by line.
    ifstream myFile(pathTable);

        for (unsigned int i = 0; i < nodes.size(); i++)
        {
            pathLookupVectors.push_back(vector<vector<int>>());

            for (unsigned int j = 0; j < nodes.size(); j++)
            {
                string line;

                if (getline(myFile, line)) //enter if a line is read successfully
                {
                    stringstream ss(line);
                    istream_iterator<int> begin(ss), end;
                    pathLookupVectors[i].push_back(vector<int>(begin, end));
                }
            }
        }
}

EDIT - I understand that the code is not the best it could be, but that isn't the point here. It runs quickly on it's own - about 3 seconds and that's fine for me. The problem I'm tying to solve is why it takes so much longer inside the project.

EDIT - I commented out all of the game code apart from the main game loop. I placed the method into the initialize section of the code which is run once on start up. Apart from a few methods setting up a window it's now pretty much the same as the program with ONLY the method in, only it STILL takes about 5 minutes to run. Now I know it has nothing to do with dependencies on the pathLookupVectors. Also, I know it's not a memory thing where the computer starts writing to the hard drive because while the slow program is chugging away running the method, I can open another instance of VS and run the single method program at the same time which completes in seconds. I realise that the problem might be some basic settings, but I'm not experienced so apologies if this does disappointingly end up being the reason why. I still don't have a clue why it's taking so much longer.

It would be great if this didn't take so long in debug mode as it means waiting 5 minutes every time I make a change. There MUST be a reason why this is being so slow here. These are the other included headers in the cut down project:

#include <d3d10.h>
#include <d3dx10.h>
#include "direct3D.h"
#include "game.h"
#include "Mesh.h"
#include "Camera.h"
#include "Level.h"

#include <vector>

using namespace std;

EDIT - this is a much smaller self contained project with only a tiny bit of code where the problem still happens.

this is also a very small project with the same code where it runs very fast.

Answer 1

I ran this code in MSVC10 (same compiler you are using) and duplicated your results with the projects you provided. However I was unable to profile with this compiler due to using the express version.

I ran this code in the MSVC9 compiler, and it ran 5 times faster! I also profiled it, and got these results:

Initialize (97.43%)
    std::vector::_Assign (29.82%) 
        std::vector::erase (12.86%)
            std::vector::_Make_iter (3.71%)
            std::_Vector_const_iterator (3.14%)
        std::_Iterator_base (3.71%)
        std::~_Ranit (3.64%)
    std::getline (27.74%)
        std::basic_string::append (12.16%)
            std::basic_string::_Grow (3.66%)
            std::basic_string::_Eos (3.43%)
        std::basic_streambuf::snextc (5.61%)
    std::operator<<(std::string) (13.04%)
        std::basic_streambuf::sputc(5.84%)
    std::vector::push_back (11.84%)
        std::_Uninit_move::?? (3.32%)
    std::basic_istream::operator>>(int) (7.77%)
        std::num_get::get (4.6%)
            std::num_get::do_get (4.55%)

The "fast" version got these results: (scaled to match other times):

Initialize (97.42%)
    std::_Uninit_copy (31.72%)
        std::_Construct (18.58%)
        std::_Vector_const_iterator::operator++ (6.34%)
        std::_Vector_const_iterator::operator!= (3.62%)
    std::getline (25.37%)
        std::getline (13.14%)
        std::basic_ios::widen (12.23%)
    std::_Construct (18.58%)
        std::vector::vector (14.05%)
    std::_Destroy (14.95%)
        std::vector::~vector (11.33%)
    std::vector::_Tidy (23.46%)
        std::_Destroy (19.89%)
            std::vector::~vector (12.23%)
        [ntdll.dll] (3.62%)

After studying these results and considering Michael Price's comments many times, it dawned on me to make sure the input files were the same size. When this dawned on me, I realized the profile for the "fast" version, does not show std::operator<<(std::string) or std::vector::push_back at all, which seems suspicious. I checked the MethodTest project, and found that it did not have a WepTestLevelPathTable.txt, causing the getline to fail, and the entire function to do almost nothing at all, except allocate a bunch of empty vectors. When I copied the WepTestLevelPathTable.txt to the MethodTest project, it is exactly the same speed as the "slow" verison. Case solved. Use a smaller file for debug builds.

Answer 2

Here're a few methods I believe could slow down the start-up process:

1. Level::GenerateGridNodes():

   void Level::GenerateGridNodes()
   {
       int gridHeight = gridSize;
       int gridWidth = gridSize;
   
       // ADD THIS STATEMENT:
       nodes.reserve(gridHeight*gridWidth);
   
       for (int h = 2; h <= gridHeight; h++)
       {
           for (int w = 2; w <= gridWidth; w++)
           {
               nodes.push_back(Node(D3DXVECTOR3((float)w, (float)h, 0)));
           }
       }
   }//end GenerateGridNodes()
   

2. Level::CullInvalidNodes(): For std::vectors, use remove-erase idiom to make erasing elements faster. You also need to re-think of how this function should work because it seems to have lots of redudant erasing and adding of nodes. Would it make sense in the code that instead of erasing you could simply assign the value you push_back() right after deletion to the value you're erasing? So instead of v.erase(itr) followed by v.push_back(new_element), you could simply do *itr = new_element;? DISCLAIMER: I haven't looked at actually what the functions does. Honestly, I don't have the time for that. I'm just pointing you to a possiblity.

3. In Level::LinkNodes():

   void Level::LinkNodes()
   {
       //generates a vector for every node
       // ADD THIS BEFORE THE FOR LOOP
       nodeAdjacencyVectors.reserve(nodes.size());
       for (unsigned int i = 0; ....)
       //... Rest of the code
   }//end LinkNodes()
   

In short, you still have got room for a lot of improvement. I believe the main hog is the Level class functions. You should have another look through it and probably rethink how each function should be implemented. Especially those invoked within the constructor of Level class.

Answer 3

It contained a loop withing a loop, each inner loop reads each line of an over 30MB data file. Of course it's going to be slow. I would say it's slow by design.