8
\$\begingroup\$

I am trying to get acquainted with C++11/14, so please tell me if the code below could be written in a more "modern" way. Or, of course, if it could be improved in any way.

The function buildInput reads the content of a file and builds a matrix with it.

std::vector<std::vector<int>> buildInput(std::string fileName) {
    auto rows = 0, cols = 0;
    auto objectsCount = 0;

    std::ifstream in(fileName);

    // Throw exceptions in case any i/o operation fails.
    in.exceptions(std::ifstream::failbit | std::ifstream::badbit);

    in >> rows >> cols >> objectsCount;
    std::vector<std::vector<int>> input(rows, std::vector<int>(cols, 0));

    for(int i = 0; i < objectsCount; ++i) {
        auto type = 0, row = 0, col = 0;
        in >> type >> row >> col;
        input[row][col] = type;
    }

    return input;
}

The function builds the input for a Sokoban game from a file. Basically, it builds a "map" (a matrix) with several types of objects placed on it.

The file has the following format:

rows_count columns_count objects_count
[object_type object_row_number object_column_number](objects_count times)

For example, for the following file content:

4 4 6
1 0 3
2 1 2
3 1 3
1 2 3
4 3 1
1 3 3

the code would build the matrix

0 0 0 1
0 0 2 3
0 0 0 1
0 4 0 1
\$\endgroup\$
8
\$\begingroup\$

I see some things that may help you improve your code.

Use the required #includes

The code uses std::vector which means that it should #include <vector>. It was not difficult to infer, but it helps reviewers if the code is complete. The full set of required includes appears to be this:

#include <iostream>
#include <fstream>
#include <vector>

Think of the user

The provided example input requires 21 numbers so that the computer can create a matrix containing just 16. There is a lot of redundancy there! It seems to me that simply having your example output be the input format would make a lot more sense and require less space, less typing and less interpretation.

Sanitize user input better

If I change the last line of the sample input to 1 9 9 it is asking the code to initialize a location that is outside the bounds of the vector and on my machine the computer segfaults and the program dies. Some bounds checking would be prudent.

Pass a stream rather than a filename

The current design is rather inflexible in that it can only use an actual file as input. I'd recommend making it more generic and accepting a std::istream & as a parameter rather than a file name.

Use a better data structure

The choice of a vector of vectors for a matrix is not a very good one because unlike a matrix, there is nothing to assure that all of the vectors are the same size. I'd recommend creating your own custom object which hides the messy details of the actual storage (it might be a std::array or a single std::vector) but could do bounds checking and retrieval using the same coordinate system. An example is shown below.

Use a friend extractor instead of a standalone function

Rather than having a separate function, it would be nicer to be able to write code something like this:

SokobanBoard board;
std::cin >> board;

Alternatively,

SokobanBoard board;
ifstream in(fileName);
in >> board;

To do this, we could write an extractor. Here's a sketch of an example:

class SokobanBoard {
public:
    SokobanBoard(std::size_t rows, std::size_t cols);
    int at(std::size_t x, std::size_t y) const;

    friend std::ostream& operator<<(std::ostream& out, const SokobanBoard &sb);
    friend std::istream& operator>>(std::istream& in, SokobanBoard &sb);
private:
    std::size_t m_height;
    std::size_t m_width;
    std::vector<int> m_board;
};

A word about addressing individual squares

A question in the comments was whether doing the mathematics (multiplication) might be longer than the addressing of a vector of vectors. On my 64-bit Linux machine using gcc 6.2.1 with -O3 optimization, I coded two different versions.

First, here is the test source code:

#include <vector>
#include <iostream>

class Test1 {
public:
    Test1(int rows, int cols) :
        vec(rows)
    {
        for (auto &row: vec) {
            row.reserve(cols);
        }
    }
    int fetch(int x, int y) const;
private:
    std::vector<std::vector<int>> vec;
};

class Test2 {
public:
    Test2(int rows, int cols) :
        height{rows},
        width{cols},
        vec(height * width)
    {}
    int fetch(int x, int y) const;
private:
    const size_t height;
    const size_t width;
    std::vector<int> vec;
};

int Test1::fetch(int x, int y) const { return vec[x][y]; }
int Test2::fetch(int x, int y) const { return vec[x+y*height]; }

int main() {
    std::size_t rows, cols;
    std::cin >> rows >> cols;
    Test1 test1(rows, cols);
    Test2 test2(rows, cols);
    std::size_t x, y;
    std::cin >> x >> y;
    int m = test1.fetch(x, y);
    int n = test2.fetch(x, y);
    std::cout << "m = " << m << ", and n = " << n << "\n";
}

Note that this is a poor program lacking all error checking, but the purpose was only to extract the assembly language for the two versions of fetch. First, this version

int Test1::fetch(int x, int y) const { return vec[x][y]; }

produced this assembly code

0000000000000000 <Test1::fetch(int, int) const>:
Test1::fetch(int, int) const():
   0:   48 63 f6                movslq %esi,%rsi
   3:   48 8b 0f                mov    (%rdi),%rcx
   6:   48 63 d2                movslq %edx,%rdx
   9:   48 8d 04 76             lea    (%rsi,%rsi,2),%rax
   d:   48 8d 04 c1             lea    (%rcx,%rax,8),%rax
  11:   48 8b 00                mov    (%rax),%rax
  14:   8b 04 90                mov    (%rax,%rdx,4),%eax
  17:   c3                      retq   

This version

int Test2::fetch(int x, int y) const { return vec[x+y*height]; }

produced this assembly code

0000000000000020 <Test2::fetch(int, int) const>:
Test2::fetch(int, int) const():
  20:   48 63 d2                movslq %edx,%rdx
  23:   48 8b 47 10             mov    0x10(%rdi),%rax
  27:   48 63 f6                movslq %esi,%rsi
  2a:   48 0f af 17             imul   (%rdi),%rdx
  2e:   48 01 d6                add    %rdx,%rsi
  31:   8b 04 b0                mov    (%rax,%rsi,4),%eax
  34:   c3                      retq   

I was not able to detect any timing differences with the testing I did, but we can see that the difference is that there are 5 memory fetches for the vector of vectors version, versus three for the multiplying version. If the structure happens to be in the cache (likely the case in my testing where I was using small dimensions), they are both about the same duration. If there is a cache miss, the multiplying version will likely be faster.

I'd always encourage you to measure it on your own machine with your own data to determine which is better for your purposes.

\$\endgroup\$
  • 1
    \$\begingroup\$ The input is a sparse matrix. It is a compact representation when "most" elements are 0 \$\endgroup\$ – Caleth Dec 20 '16 at 17:59
  • 2
    \$\begingroup\$ @Caleth Even if that's the case, it is still redundant to have the count of objects followed by that many objects. Computers can count very well -- why not have the input routine simply read entries until the end of file and omit the count? \$\endgroup\$ – Edward Dec 20 '16 at 18:04
  • \$\begingroup\$ Thank you for such a detailed answer, @Edward ! Regarding the data structure: I'm thinking that the matrix elements will be randomly accessed very often - won't computing the current location every time hurt the performance? (that x * width + y) Not sure if I could use an std::array since the size is not known when it is initialized. \$\endgroup\$ – Ioanna Dec 21 '16 at 12:41
  • 1
    \$\begingroup\$ Computing the location each time is unlikely to hurt performance, but it's best to actually measure. Create a fetch(std::size_t x, std::size_t y) routine for the custom object. Code it one way and measure; then code it the other way and measure. \$\endgroup\$ – Edward Dec 21 '16 at 13:49
  • 1
    \$\begingroup\$ Because of cache effects, it may make a difference whether you fetch them in order or randomly. Ideally, the test should match the intended usage pattern. \$\endgroup\$ – Edward Dec 21 '16 at 16:22
3
\$\begingroup\$

In addition to @Edwards excellent answer there are some things I would like to mention:

Pass by reference to const unless you need a copy

When you pass an argument to a function like here:

std::vector<std::vector<int>> buildInput(std::string fileName)

you are passing it "by value" which means that the fileName variable will be a copy of the value the caller passed in. When the type of the parameter is a complex type or managing dynamic memory (like std::string) is doing then this copy time will become non-trivial.

Unless you actually need the copy (because you're storing it somewhere or you want to modify it without affecting the caller) then you should pass all non-POD types by reference to const. Like so:

std::vector<std::vector<int>> buildInput(const std::string& fileName)

Represent 2D matrix with one vector

Conventional wisdom is that 2D and 3D (or nD for the matter) volumes should be linearised to 1D arrays by computing a 1D index from nD coordinates.

I.e. replace:

// creation
vector<vector<T>>  data;
for(int row = 0; row < height; row++){
    data.emplace_back(vector<T>(width));
} 

// access
data[x][y];

with:

// creation
vector<T> data(row*width);

// access
data(y*width + x);

The idea is that a long contiguous vector is nicer on your CPU cache, is easier to move around and has less overhead in memory usage and also contributes less to memory fragmentation.

There are also portability implications just about all software that I know of that processes images or matrices use this kind of linearisation and you should too if you want to interoperate with them.

Too see the (non) effects of this I have written a benchmark here on ideone. And I'm posting the results here:

from Ideone:

16x16 alloc speed up: 1.97028x iter speed up: 1.01526x
128x16 alloc speed up: 1.62749x iter speed up: 1.08437x
1024x16 alloc speed up: 1.96126x iter speed up: 0.818857x
8192x16 alloc speed up: 1.08617x iter speed up: 1.07597x
16x128 alloc speed up: 2.60728x iter speed up: 1.05362x
128x128 alloc speed up: 1.9301x iter speed up: 1.05701x
1024x128 alloc speed up: 1.10907x iter speed up: 1.06326x
8192x128 alloc speed up: 1.07762x iter speed up: 1.04457x
16x1024 alloc speed up: 5.71674x iter speed up: 1.0753x
128x1024 alloc speed up: 1.1498x iter speed up: 1.02847x
1024x1024 alloc speed up: 1.03182x iter speed up: 1.04656x
8192x1024 alloc speed up: 1.02505x iter speed up: 1.00829x
16x8192 alloc speed up: 2.1236x iter speed up: 1.07109x
128x8192 alloc speed up: 1.16434x iter speed up: 1.04066x
1024x8192 alloc speed up: 1.16075x iter speed up: 1.03849x
8192x8192 alloc speed up: 1.0298x iter speed up: 1.04191x
print sum to avoid the code from being removed: -2147483648

from my local gcc 6.2.0 with -O3:

16x16 alloc speed up: 7.47556x iter speed up: 1.01411x
128x16 alloc speed up: 4.34979x iter speed up: 0.964627x
1024x16 alloc speed up: 0.619431x iter speed up: 1.14025x
8192x16 alloc speed up: 1.20561x iter speed up: 0.985355x
16x128 alloc speed up: 5.25231x iter speed up: 1.0264x
128x128 alloc speed up: 0.791409x iter speed up: 1.12025x
1024x128 alloc speed up: 1.04606x iter speed up: 0.96693x
8192x128 alloc speed up: 1.35056x iter speed up: 1.00495x
16x1024 alloc speed up: 2.91901x iter speed up: 0.954083x
128x1024 alloc speed up: 1.01451x iter speed up: 1.01057x
1024x1024 alloc speed up: 1.07157x iter speed up: 0.980892x
8192x1024 alloc speed up: 1.17986x iter speed up: 0.997074x
16x8192 alloc speed up: 3.00445x iter speed up: 1.03182x
128x8192 alloc speed up: 1.327x iter speed up: 0.97198x
1024x8192 alloc speed up: 1.3206x iter speed up: 1.01225x
8192x8192 alloc speed up: 1.2715x iter speed up: 0.983423x
print sum to avoid the code from being removed: -2147483648

So from these results we can draw the conclusion that any differences between the two methods is minimal and I would say it is within measurement error because these measurements are done on an otherwise active system.

Benchmark code below for reference

#include <iostream>
#include <vector>
#include <chrono>
using namespace std;

size_t creation1_ns = 0;
size_t creation2_ns = 0;

size_t iteration1_ns = 0;
size_t iteration2_ns = 0;

double test1(size_t w, size_t h){
    auto start = chrono::steady_clock::now();
    vector<vector<double>> data;
    data.reserve(h);
    for(size_t row = 0; row < h; ++row){
        data.emplace_back(vector<double>(w));
    }
    creation1_ns += chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now() - start).count();

    start = chrono::steady_clock::now();
    for(size_t row = 0; row < h; ++row){
        for(size_t col = 0; col < w; ++col){
            data[row][col] += rand(); // Write something
        }   
    }

    double sum = 0.0;
    for(size_t row = 0; row < h; ++row){
        for(size_t col = 0; col < w; ++col){
            sum += data[row][col]; // Read something
        }   
    }
    iteration1_ns += chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now() - start).count();

    return sum;
}


double test2(size_t w, size_t h){
    auto start = chrono::steady_clock::now();
    vector<double> data(w*h);
    creation2_ns += chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now() - start).count();

    start = chrono::steady_clock::now();
    for(size_t row = 0; row < h; ++row){
        size_t offs = row*w;
        for(size_t col = 0; col < w; ++col){
            data[offs + col] += rand(); // Write something
        }   
    }

    double sum = 0.0;
    for(size_t row = 0; row < h; ++row){
        size_t offs = row*w;
        for(size_t col = 0; col < w; ++col){
            sum += data[offs + col]; // Read something
        }   
    }
    iteration2_ns += chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now() - start).count();

    return sum;
}

int main() {
    srand(2);
    const auto thoroughness = 50000.0;
    auto s = 0;

    for(int h = 16; h < 10000; h *= 8){
        for(int w = 16; w < 10000; w *= 8){
            creation1_ns = 0;
            creation2_ns = 0;
            iteration1_ns = 0;
            iteration2_ns = 0;

            auto trials = thoroughness/(w*h);

            for(int r = 0; r < trials; ++r){
                s+= test1(w, h);
                s+= test2(w, h);
            }

            cout<<w<<"x"<<h
                <<" alloc speed up: "<< (double(creation1_ns) / creation2_ns)<<"x"
                <<" iter speed up: "<< (double(iteration1_ns) / iteration2_ns)<<"x" <<endl; 
        }
    }


    cout<<"print sum to avoid the code from being removed: "<<s<<endl;
    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.