How to parse CSV in C++ using Boost memory maps?

Question

I have a really huge file with 17 million records in it.

Here is a sample of the file:

Actor Movie
1,2
2,2
3,1
4,3
2,3

I would want to skip the first line and start the parsing from second line onward. I am trying to create two things.
1. Movies to actors map
vector<uint64_t> *movie_map = new vector<uint64_t>[1200000];
2. Actors to movies map
vector<uint64_t> *actor_movie_map = new vector<uint64_t>[2000000];

I purposefully did not want a HashMap since it takes some time for computing hash. I tried to use Boost library. It reads the file(~250MB) in about 3 seconds, but a lot of time is consumed while creating the maps. In fact the time is worse than normal getline() way of reading the file. Here is my implementation so far.

using CsvField = boost::string_ref;
using CsvLine  = std::vector<CsvField>;
using CsvFile  = std::vector<CsvLine>;

namespace qi = boost::spirit::qi;
struct CsvParser : qi::grammar<char const*, CsvFile()> {
    CsvParser() : CsvParser::base_type(lines)
    {
        using boost::phoenix::construct;
        using boost::phoenix::begin;
        using boost::phoenix::size;

        using namespace qi;

        field = raw [*~char_(",\r\n")] [ _val = construct<CsvField>(begin(_1), size(_1)) ];
        line  = field % ',';
        lines = line  % eol;
    }
  private:
    qi::rule<char const*, CsvField()> field;
    qi::rule<char const*, CsvLine()>  line;
    qi::rule<char const*, CsvFile()>  lines;
};

int main()
{
    srand(time(0));
    boost::iostreams::mapped_file_source csv("playedin.csv");

    CsvFile parsed;
    parsed.reserve(18*1000*1000);
    if (qi::parse(csv.data(), csv.data() + csv.size(), CsvParser(), parsed))
    {
        using boost::lexical_cast;
        for(uint64_t i=1; i < parsed.size(); i++){
        auto& line = parsed[i];
        uint64_t sample = lexical_cast<uint64_t>(line[0]);
        movie_map[lexical_cast<uint64_t>(line[1])].push_back(lexical_cast<uint64_t>(line[0]));
        actor_movie_map[lexical_cast<uint64_t>(line[0])].push_back(lexical_cast<uint64_t>(line[1]));

        }
    }
}

I do not want to use the normal way of reading file because of the large size of the file. Please suggest a way of implementing this so that the whole file reading and preparing map for 17 million records should happen in less than 2-3 seconds.I understand that the expectation is little too much, but I am sure it is possible. I am really looking at the most efficient way of doing this.

Thanks for your help!

Answer 1

• vector *movie_map = new vector[1200000];

  ✍ Never use new or delete in modern c++

• I purposefully did not want a HashMap since it takes some time for computing hash.

  Exactly how much time does calculating the hash take? I mean, chances are that a hash-map aren't the best choice here, but your reasoning is off. On may implementations std::hash<> of a 64 bit integer is a no-op (on a system where size_t is 64 bits)¹.

But The Kicker Is:

You ... read all of the data into a CsvFile first (that's a vector of vectors of string_refs...) only to then convert to a map?!

This is ridiculous. Simply skip the middle man, you don't need it!

Mind you, spirit is a parser generator. It's ridiculous in every respect to parse the text first, only to use lexical_cast on the result.

Demo

Here's a c++14 demo that cuts the middle man, using Boost Spirit X3 for good measure. I chose flat_multimap a bit randomly to make two points:

• your data structure is "like a" multi-map, perhaps even an adjacency list. What does your use-case require of it?
• there are (many) existing datastructures that have subtly varying performance characteristics

Live On Coliru

#include <boost/container/flat_map.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
#include <boost/spirit/home/x3.hpp>

using Table  = boost::container::flat_multimap<uint64_t, uint64_t>;
using Record = Table::value_type;

namespace Parsing {
    using namespace boost::spirit::x3;

    auto const ignore_header_row 
        = !uint_ >> *(char_ - eol) >> eol;

    auto const record 
        = rule<struct _rl, Record> {"record"}
        = uint_ >> ',' >> uint_ >> eol;

    auto const file 
     // = rule<struct _file, Table> {"file"}
        = omit [*ignore_header_row] >> *record >> eoi;
}

#include <iostream>

int main() {
    boost::iostreams::mapped_file_source mfs("playedin.csv");

    Table table;
    table.reserve(18*1000*1000);
    if (parse(mfs.begin(), mfs.end(), Parsing::file, table)) {
        std::cout << "Parsed " << table.size() << " records\n";
    } else {
        std::cout << "Parse failed\n";
    }
}

Prints

Parsed 5 records

Caveat In latest boost versions there is a regression in X3 attribute handling, you will want to use the fix from this answer: https://stackoverflow.com/a/48393573/85371

Benchmark + Query

Benchmarking predictably shows that inserting 17+million unsorted rows is not optimal using the flat-map approach:

• 1,000,000 unsorted rows are read in ~4m39s,
• with the input sorted it takes only 0.113s to read those same rows output screenshot

The obvious bottle neck is sorting while parsing. That's easily fixed: we don't need to sort while parsing. Just sort it after parsing:

• all 17.4 million rows are now parsed and sorted in 1.922s, or 1.284s if presorted (output screenshot again)

Benchmarked Code Listing

The final version Live On Coliru

#include <boost/container/flat_map.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
#include <boost/spirit/home/qi.hpp>

using Table  = boost::container::vector<std::pair<uint64_t, uint64_t> >;
using Record = Table::value_type;

namespace Parsing {
    using namespace boost::spirit::qi;
    using Iterator = char const*;

    static const rule<Iterator> ignore_header_row
        = !uint_ >> *(char_ - eol) >> eol;
    static const rule<Iterator, Record()> record 
        = uint_ >> ',' >> uint_ >> eol;

    static const rule<Iterator, Table()> file 
        = omit [*ignore_header_row] >> *record >> eoi;
}

Table parse_data(std::string const& fname) {
    boost::iostreams::mapped_file_source mfs(fname);

    Table table;
    table.reserve(18*1000*1000);
    if (!parse(mfs.begin(), mfs.end(), Parsing::file, table))
        throw std::runtime_error("Parse failed");

    sort(table.begin(), table.end());
    return table;
}

template <typename It> struct iterator_range {
    It b, e;
    iterator_range() = default;
    iterator_range(std::pair<It, It> p) : b(p.first), e(p.second) {}
    It begin() const { return b; }
    It end() const   { return e; }
};

struct by_actor {
    template <typename T, typename U>
    bool operator()(T const& a, U const& b) const { return actor(a) < actor(b); }
  private:
    static uint64_t actor(Record const& r) { return r.first; }
    static uint64_t actor(uint64_t i) { return i; }
};

#include <iostream>

int main(int argc, char** argv) {
    Table const& table = parse_data("playedin.csv");

    auto query = [&table](uint64_t actor) { 
        return iterator_range<Table::const_iterator>(equal_range(table.begin(), table.end(), actor, by_actor{}));
    };

    for (auto actor : std::vector<std::string>{argv+1, argv+argc}) {
        std::cout << "Actor " << actor << " played in:";
        for (auto movie : query(std::stoull(actor)))
            std::cout << " " << movie.second;
        std::cout << "\n";
    }
}

---

¹ likewise, boost's boost::hash<> defers to boost::hash_value(unsigned long long) which is documented to return val when abs(val) <= std::numeric_limits<std::size_t>::max().

Answer 2

A few thoughts:

• Lexical_cast tends to be slow.
• Memory mapping the file does not help sequential access. It might even be worse than regular reading-by-chunks.
• An array of vectors is inefficient if the vectors are small. Each vector consumes at least three pointers worth of space when it is empty. You'd be better off with a different container, like std::unordered_map.