8
\$\begingroup\$

I want to parse a CSV file and store the data using the istream >> operator but I am running into big performance issues.

Here is the current version:

#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <iostream>

template <class T>
class   CSV
{

    std::vector<std::vector<T>> _data;
    size_t _width;
    size_t _height;

public:

    CSV(const std::string& filepath)
    {
        std::ifstream file(filepath);
        if (!file)
            throw std::exception();

        for (std::string line; std::getline(file, line);)
        {
            std::stringstream ss1(line);
            std::vector<T> row;

            for (std::string field; std::getline(ss1, field, ',');)
            {
                std::stringstream ss2(field);
                T item;

                ss2 >> item;
                row.push_back(item);
            }
            _data.push_back(row);
        }
        _height = _data.size();
        if (!_height)
            throw std::exception();
        _width = _data[0].size();

        for (auto& row : _data)
            if (row.size() != _width)
                throw std::exception();
    }

    size_t  Width(void)
    {
        return _width;
    }
    size_t  Height(void)
    {
        return _height;
    }

    const std::vector<std::vector<T>>   &Data(void)
    {
        return _data;
    }
};

It works but it's slow because I start by making a copy of each line in the file. I then make a copy of that line inside of a stringstream. I then parse each field in that line and make a copy of it. I then make a copy of that inside another stringstream, and finally I extract the data from the stringstream.

Basically there is too much copying, but I honestly don't know how to avoid it with stringstreams. I know there are other ways to parse things that are not stringstreams but then I miss out on using the >> operator and the point of making a templated CSV parser.


For an idea of its speed I have an 80MB file and it takes 11 seconds to parse using CSV<int>. I also have -03 turned on and am using clang++.

\$\endgroup\$
  • \$\begingroup\$ Are you sure its text copying that is your problem. I would bet its more likely to be memory management of the vector. Do you have a link to your 80 MB file. \$\endgroup\$ – Martin York Jul 6 '18 at 15:17
11
\$\begingroup\$
#include <iostream>

You don't seem to need this include.

size_t _width;
size_t _height;

These should both be std::size_t.

CSV(const std::string& filepath)

Single argument constructors should almost always be explicit.

if (!file)
    throw std::exception();

What you want to throw here is std::runtime_error or something derived from it, not std::exception.

for (std::string line; std::getline(file, line);)
{
    std::stringstream ss1(line);
    std::vector<T> row;

    for (std::string field; std::getline(ss1, field, ',');)
    {
        std::stringstream ss2(field);
        T item;

        ss2 >> item;
        row.push_back(item);
    }
    _data.push_back(row);
}

Alright, let's get into the meat of this.

for (std::string line; std::getline(file, line);)

There's really nothing you can do to improve the outer for loop prologue. One would hope line's memory would get reused, so there will be allocations only until the longest line is read. You could pull line out of the for prologue and reserve() a reasonable size for it to potentially eliminate all allocations in the loop, but then you'd have to know in advance how much to allocate, which doesn't seem generally likely.

std::stringstream ss1(line);

Here is where you can start making gains. The purpose of ss1 is just to split line by commas. That doesn't seem necessary. You can drop ss1, and change the inner for loop to:

std::string field;
for (auto p = line.cbegin(); get_field(p, line.cend(), field); )

Then you could write a get_field() function (maybe private and static in the class) something like:

template <typename ForwardIterator>
auto get_field(ForwardIterator& next, ForwardIterator last, std::string& field) -> bool
{
    if (next == last)
        return false;

    if (*next == ',')
        ++next;

    // This just gets everything up to the next comma, as your
    // current code does... but you could modify it to handle
    // escaped or quoted values.
    auto const first = next;
    next = std::find(next, last, ',');
    field.assign(first, next);

    return true;
}

Taking field (and first) by non-const reference is generally bad practice, but for an internal implementation function, it's okay - especially given that you're gunning for speed gains.

On top of this, you can move field outside of even the outer for loop - again, generally bad practice, but you're gunning for speed not beauty.

Here's another optimization opportunity. Currently you don't bother to check for row size until after everything's read. Instead, what you can do is start with _width as zero, and then at the end of the loop, set it to row.size(). Then right after you create row, you can do row.reserve(_width);. That will (hopefully) prevent the push_back()s in the inner loop from triggering allocations.

Now the inner loop is:

{
    std::stringstream ss2(field);
    T item;

    ss2 >> item;
    row.push_back(item);
}

There's not much you can do to improve this for efficiency, except that the last line should be row.push_back(std::move(item));. What you should do, though, is check that the formatting worked.

And of course, after the loop, you should move the row into _data, not copy it.

So the modified loop might look something like:

std::string field; // outside the loop so we can continually reuse the memory
for (std::string line; std::getline(file, line);)
{
    std::vector<T> row;
    row.reserve(_width); // reserve what we think the width is going to be, to prevent allocations when doing push_back()

    for (auto p = line.cbegin(); get_field(p, line.cend(), field);)
    {
        std::stringstream ss{field};

        T item;
        if (!(ss >> item))
            throw std::runtime_error{"invalid field"};

        row.push_back(std::move(item));
    }

    _width = std::max(_width, row.size()); // get a better estimate of the width
    // Note that you could actually do a check here to make sure the
    // width stays consistent, and fail early if not rather than
    // waiting until the whole file has been read before failing.

    _data.push_back(std::move(row));
}

That is about the best I can think of, performance-wise, for the main loop.

if (!_height)
    throw std::exception();

Again, you should throw std::runtime_error, not std::exception. std::exception should only be used as base class.

_width = _data[0].size();

If you get the width in the loop as I suggested, you don't need this line.

for (auto& row : _data)
    if (row.size() != _width)
        throw std::exception();

This could be done with an algorithm:

if (!std::all(_data.cbegin(), _data.cend(), [_width](auto&& row) { return row.size() == _width; }))
    throw std::runtime_error{"different widths"};

On to the other functions....

size_t  Width(void)
{
    return _width;
}

You don't need to declare void to specify an empty argument list; that's archaic C stuff.

This function, and Height() as well, can be both const and noexcept, and should be at least const.

const std::vector<std::vector<T>>   &Data(void)
{
    return _data;
}

It is standard practice in C++ to keep pointer and reference modifiers with the type. In other words const std::vector<std::vector<T>>& Data(), not const std::vector<std::vector<T>> &Data().

This function should also be both const and noexcept.

Summary

  • Try to use as much information from previous iterators to make subsequent iterators more efficient. For example, once you know the width of a row, use that to preallocate the row vector.
  • Moving allocating variables (like strings) that get reused repeatedly out of the loop may allow you to reuse the memory, and avoid allocations.
  • Move whenever possible, rather than copying.
  • You don't need to create a string stream just to split on commas.
  • std::exception is a base class, not a general use exception class. Use std::logic_error or std::runtime_error or derived classes as appropriate.
\$\endgroup\$
7
\$\begingroup\$

Since @indi gave a thorough review of the code, I'll present alternative solution.

Locales

Locales are set of rules and constants that dictate how I/O is handled. For example, one can interpret a comma as whitespace character, or space as non-whitespace character. In essence, it is a set of rules.

Benefits

There won't be any need for the class at all, as it will just change behavior of the stream, i.e. any existing code for the stream will work almost as is. The solutions that scale in terms of problems they solve are the ones that can be incorparated or integrated into existing code.

Drawbacks

If one needs previous behavior after they're done dealing with csv, user will need to save locale of the stream before imbuing the csv rules, and then restoring the old locale after the csv operations are done. Doing mixed mode operations are probably gonna be very slow.

Code

Courtesy of this answer:

struct csv_classification : std::ctype<char> {
    csv_classification() : ctype(make_table()) { }
private:
    static mask* make_table() {
        const mask* classic = classic_table();
        static std::vector<mask> v(classic, classic + table_size);
        v[','] |= space;
        v[' '] &= ~space;
        return &v[0];
    }
};

Then you can just

stream.imbue(std::locale(stream.getloc(), new csv_classification));
//use as simple stream
\$\endgroup\$
4
\$\begingroup\$

For proper field handling, you may want to look at RFC4180 - Common Format and MIME Type for Comma-Separated Values (CSV) Files if you plan to make a generalized CSV reader.

field_1,"field, two","""field""_3" CRLF
^^^^^^^ ^^^^^^^^^^^^ ^^^^^^^^^^^^^ ^^^^
 field     field         field     optional for last record

If you want to reduce the number of allocations, consider writing a range-view that lazily scans each field from C++ ranges/containers or even memory-mapped files.

\$\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.