Why does locking slow down this sequential file parser?

Question

I wrote a simple reader and parser for the image file format. The problem is that it is incredibly slow. Here are the relevant methods:

Graph METISGraphReader::read(std::string path) { METISParser parser(path); std::pair<int64_t, int64_t> header = parser.getHeader(); int64_t n = header.first; int64_t m = header.second; Graph G(n); node u = 0; while (parser.hasNext()) { u += 1; std::vector<node> adjacencies = parser.getNext(); for (node v : adjacencies) { if (! G.hasEdge(u, v)) { G.insertEdge(u, v); } } } return G; } std::vector<node> METISParser::getNext() { std::string line; bool comment = false; do { comment = false; std::getline(this->graphFile, line); // check for comment line starting with '%' if (line[0] == '%') { comment = true; TRACE("comment line found"); } else { return parseLine(line); } } while (comment); } static std::vector<node> parseLine(std::string line) { std::stringstream stream(line); std::string token; char delim = ' '; std::vector<node> adjacencies; // split string and push adjacent nodes while (std::getline(stream, token, delim)) { node v = atoi(token.c_str()); adjacencies.push_back(v); } return adjacencies; } 

To diagnose why this is so slow, I ran it in the profiler (Apple Instruments). The results were unexpected: it is slow due to overhead blocking. The program spends more than 90% of its time on pthread_mutex_lock and _pthread_cond_wait .

I have no idea where the blocking overhead comes from, but I need to get rid of it. Can you suggest the following steps?

EDIT: see call stack extended for _pthread_con_wait . I cannot understand the source of the lock by looking at this:

Answer 1

Expand the call stack to the _pthread_cond_wait and pthread_mutex_lock calls to find out where the lock calls were called from.

As I assume, I'm going to say this in all the unnecessary heap allocations you make. A heap is a resource protected by a thread, and on this platform, thread safety can be ensured through mutexes.

Answer 2

All functions that read data from istream will block mutex, read data with streambuf and unlock mutex . To eliminate this overhead, read the file directly from streambuf instead of istream and do not use stringstream to analyze the data.

Here is the getline version that uses streambuf instead of istream

 bool fastGetline(streambuf* sb, std::string& t) { t.clear(); for(;;) { int c = sb->sbumpc(); switch (c) { case '\n': return true; case '\r': if(sb->sgetc() == '\n') sb->sbumpc(); return true; case EOF: return !t.empty(); default: t += (char)c; } }