1
\$\begingroup\$

I am fairly new to C++ but ran into a bit of a performance issue. To counter this I am trying to optimize parts of my code. This part is reading a text file and storing the first two values of a line foreach line in the file. This works but I was wondering if it is possible to do it faster and cleaner. See code below:

vector<pair<double, double>> createList(string path)
{
    ifstream file (path, ios::binary);
    vector<pair<double, double>> file_lines;
    string value;
    double token;
    string delimiter = "\t";
    size_t pos = 0;
    int rowCount = 0;

    while(std::getline(file, value))
    {
        int count = 0;
        pair<double, double> values;
        while ((pos = value.find(delimiter)) != string::npos && count < 2)
        {
            token = std::stod(value.substr(0, pos));
            if(count == 0){
                values.first = token;
            }else{
                values.second = token;
            }
            value.erase(0, pos + delimiter.length());
            count++;
        }
        file_lines.push_back(values);
        rowCount++;
    }
    return file_lines
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

It looks like you're missing some crucial #include lines, and several using declarations (or a using directive - you should really avoid that).

I'd probably split the function into two parts: one that handles filesystem stuff, and one that's unit-testable, accepting a std::istream&. That looks like this (after fixing the syntax error on the return statement):

#include <istream>
#include <string>
#include <utility>
#include <vector>

auto createList(std::istream& file)
{
    std::vector<std::pair<double, double>> file_lines;
    std::string value;
    double token;
    std::string delimiter = "\t";
    std::size_t pos = 0;
    int rowCount = 0;

    while(std::getline(file, value))
    {
        int count = 0;
        std::pair<double, double> values;
        while ((pos = value.find(delimiter)) != std::string::npos && count < 2)
        {
            token = std::stod(value.substr(0, pos));
            if(count == 0){
                values.first = token;
            }else{
                values.second = token;
            }
            value.erase(0, pos + delimiter.length());
            count++;
        }
        file_lines.push_back(values);
        rowCount++;
    }
    return file_lines;
}

We can write our first test. I'll use the GoogleTest framework, but you can use whatever suits you best.

#include <gtest/gtest.h>
#include <sstream>

TEST(CreateList, Empty)
{
    std::istringstream is{""};
    EXPECT_EQ(createList(is), (std::vector<std::pair<double, double>>{}));
}

We can add some more tests, now. It's good to start with tests of invalid input:

TEST(CreateList, NonNumeric)
{
    std::istringstream is{"abcde"};
    EXPECT_EQ(createList(is), (std::vector<std::pair<double, double>>{}));
}

I had hoped that the function would ignore the invalid line, but no, it's treated as 0.0:

[ RUN      ] CreateList.NonNumeric
274028.cpp:49: Failure
Expected equality of these values:
  createList(is)
    Which is: { (0, 0) }
  (std::vector<std::pair<double, double>>{})
    Which is: {}
[  FAILED  ] CreateList.NonNumeric (0 ms)

That's probably not what we want. Consider throwing an exception when input doesn't match expectation.

We can add some tests where we expect conversions (be careful to use exact floating-point values, not ones with infinite binary representation such as 0.1). I'll use a function and a small macro to help reduce repetition.

#include <sstream>

static auto createListFromString(std::string s)
{
    std::istringstream is{s};
    return createList(is);
}

#define EXPECT_CREATELIST_EQ(str, ...) \
    static const std::vector<std::pair<double, double>> expected{__VA_ARGS__}; \
    EXPECT_EQ(createListFromString(str), expected);

TEST(CreateList, TwoValues)
{
    EXPECT_CREATELIST_EQ("1.5\t-2\t\n", {1.5, -2});
}

TEST(CreateList, TwoLines)
{
    EXPECT_CREATELIST_EQ("1.5\t-2\t\n" "-1.0\t5.5\t",
                         {1.5, -2},    {-1, 5.5});
}

With some tests in place, it's time to look at the code.

We can start by getting rid of rowCount, as it's only ever written to, and never read.

Some of the other names are confusing - I'd choose line rather than value, and value instead of token. Several of the variables can be reduced in scope, and delimiter can be a char instead of a string.

That gets us to:

auto createList(std::istream& file)
{
    std::vector<std::pair<double, double>> file_lines;
    static const char delimiter = '\t';

    std::string line;
    while(std::getline(file, line))
    {
        std::pair<double, double> values;
        std::size_t pos = 0;
        for (int count = 0;  (pos = line.find(delimiter)) != std::string::npos && count < 2; ++count)
        {
            double value = std::stod(line.substr(0, pos));
            if(count == 0){
                values.first = value;
            }else{
                values.second = value;
            }
            line.erase(0, pos + 1);
        }
        file_lines.push_back(values);
    }
    return file_lines;
}

Now we can start looking at the performance. The first thing that jumps out at me is the line.erase(0, pos + 1);. Erasing from the start of a string can be an expensive operation, as it requires moving the rest of the string forwards. This is even more wasteful second time around the loop, when we won't be using the string again. It's better to keep the string unchanged, and instead change where we look into it.

While we're doing that, we can unroll the loop which executes only twice, and has half its body conditional on the loop counter.

auto createList(std::istream& file)
{
    std::vector<std::pair<double, double>> file_lines;
    static const char delimiter = '\t';

    std::string line;
    while(std::getline(file, line))
    {
        auto first_len = line.find(delimiter);
        auto second_delim = line.find(delimiter, first_len+1);
        if (second_delim == line.npos) {
            // invalid line; ignore it
            continue;
        }
        auto second_len = second_delim - first_len;
        std::size_t end;
        double first_val = stod(line.substr(0, first_len), &end);
        if (end != first_len) {
            // junk between number and delimiter
            continue;
        }
        double second_val = stod(line.substr(first_len, second_len), &end);
        if (end != second_len) {
            // junk between number and delimiter
            continue;
        }
        file_lines.emplace_back(first_val, second_val);
    }
    return file_lines;
}

Now our main inefficiencies come down to reading entire lines when we're only interested in the beginning, and copying substrings rather than using views. We can avoid both of those by using formatted input functions (namely >>), especially if we can be sure that our lines always have at least two strings at the start. That looks like

auto createList(std::istream& file)
{
    std::vector<std::pair<double, double>> file_lines;

    file.exceptions(file.badbit);
    for (;;) {
        double first, second;
        file >> first >> second;
        if (!file) {
            if (file.eof()) {
                // done
                return file_lines;
            }
            // failure
            throw std::ios_base::failure("createList parse error");
        }
        // now skip past the rest of the line
        file_lines.emplace_back(first, second);
        if (!file.ignore(std::numeric_limits<std::streamsize>::max(), '\n')) {
            return file_lines;
        }
    }
}

Modified code

Full replacement code, with tests:

#include <filesystem>
#include <fstream>
#include <limits>
#include <string>
#include <utility>
#include <vector>

auto createList(std::istream& file)
{
    std::vector<std::pair<double, double>> file_lines;

    file.exceptions(file.badbit);
    for (;;) {
        double first, second;
        file >> first >> second;
        if (!file) {
            if (file.eof()) {
                // done
                return file_lines;
            }
            // failure
            throw std::ios_base::failure("createList parse error");
        }
        // now skip past the rest of the line
        file_lines.emplace_back(first, second);
        if (!file.ignore(std::numeric_limits<std::streamsize>::max(), '\n')) {
            return file_lines;
        }
    }
}

auto createList(std::filesystem::path path)
{
    std::ifstream is{path};
    return createList(is);
}
#include <gtest/gtest.h>
#include <sstream>

static auto createListFromString(std::string s)
{
    std::istringstream is{s};
    return createList(is);
}

#define EXPECT_CREATELIST_EQ(str, ...) \
    static const std::vector<std::pair<double, double>> expected{__VA_ARGS__}; \
    EXPECT_EQ(createListFromString(str), expected);

TEST(CreateList, Empty)
{
    EXPECT_CREATELIST_EQ("");
}

TEST(CreateList, NonNumeric)
{
    EXPECT_THROW(createListFromString("abcde"), std::ios_base::failure);
}

TEST(CreateList, TwoValues)
{
    EXPECT_CREATELIST_EQ("1.5 -2 .other stuff\n", {1.5, -2});
}

TEST(CreateList, TwoLines)
{
    EXPECT_CREATELIST_EQ("1.5\t-2\n" "-1.0\t5.5\t\n",
                         {1.5, -2},    {-1, 5.5});
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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