1

The bottleneck of my c++ application is filling an std::vector< std::vector< Chunk > >. Sometimes this takes 0ms and sometimes ~16ms, it takes never something between, like 2-14ms. Why? I fill allways about 5000 elements in the vector. My code is:

Chunk struct:

struct Chunk {
    std::vector<std::pair<std::string, std::pair<int, int>>> chreatures_;
};

init:

int height_ = 100;
int width_ = 100;
const int chunksidelength_ = 10;
std::vector<std::vector<Chunk>> chunks_;
std::list<std::shared_ptr<Creature>> creatures_;

chunks_.reserve(height_ / chunksidelength_);
for (int i = 0; i < height_ / chunksidelength_; i++) {
    chunks_.emplace_back();
    chunks_[i].reserve(width_ / chunksidelength_);
    for (int j = 0; j < width_ / chunksidelength_; j++) {
        chunks_[i].emplace_back();
        chunks_[i][j].chreatures_.
                reserve(chunksidelength_ * chunksidelength_ * 3);
    }
}

filling:

long long before = (std::chrono::duration_cast<std::chrono::milliseconds>
    (std::chrono::system_clock::now().time_since_epoch())).count();

for (std::vector<Chunk>& chunks : chunks_) {
    for (Chunk& chunk : chunks) {
        chunk.chreatures_.clear();
    }
}

for (const std::shared_ptr<Creature>& creature : creatures_) {
    int x = creature->x() / chunksidelength_;
    int y = creature->y() / chunksidelength_;
    std::string image = creature->image_path();
    std::pair<int, int> position(creature->x(), creature->y());
    chunks_[y][x].chreatures_.emplace_back(std::make_pair(image, position));
}

long long after = (std::chrono::duration_cast<std::chrono::milliseconds>
    (std::chrono::system_clock::now().time_since_epoch())).count();
std::cout << after - before << std::endl;
user3561614
  • 1,024
  • 1
  • 12
  • 20
  • 4
    My first guess would always be memory allocations and context switching associated with that. Try statically allocated vector (with your own allocator) and see how it changes things. – SergeyA Mar 24 '16 at 14:34
  • @SergeyA in the creatures_ vector of a Chunk an reallocation should never happen, because for every Chunk creautres_.capacity is bigger than the count of elements inserted. Is there another place where I could look for reallocations? – user3561614 Mar 24 '16 at 14:43
  • I'm by no means an expert on this but could it possibly be some kind of register overflow or other memory type change (stack, registers, main memory etc). Maybe sometimes when you reach over a certain factor of a number of elements, you overflow enough to switch to another form of memory, or another clear and fill type operation pattern. – SolaGratia Mar 24 '16 at 14:52
  • Could you try to run the same code on multiple different computers? Just to find out whether this happens only in your particular runtime environment. – Daniel Langr Mar 24 '16 at 14:53
  • @user3561614 Are you timing an optimized build? That is important as to whether this issue is really worth pursuing. – PaulMcKenzie Mar 24 '16 at 14:55
  • 1
    You have the `std::string` part which may allocate. (and `std::string image = creature->image_path()` should probably be const ref, or then missing `std::move` for the `std::pair`). – Jarod42 Mar 24 '16 at 14:55
  • I recommend you change your data structure to `std::map >`. The `map` is a data structure optimized for accesses by key (speeding up the search). – Thomas Matthews Mar 24 '16 at 16:08

1 Answers1

1

Are you on Windows? Is the timer resolution 15.6 ms? That may mean that your code just 'executes very quickly', in 0 or 1 timer ticks.

gluk47
  • 1,812
  • 20
  • 31
  • Might be related: http://stackoverflow.com/questions/21470315/odd-behaviour-using-chronohigh-resolution-clocknow – Daniel Langr Mar 24 '16 at 15:04
  • I'm on Windows 10. My time meassurement also returns values like 2-15 for other tasks, but perhaps after allocation of new memory for std::string it takes until the next timerinterrupt, that the OS gives the program processortime. – user3561614 Mar 24 '16 at 15:23