Perché il blocco rallenta questo parser di file sequenziali?

Question

Ho scritto un semplice lettore e parser per un formato di file grafico. Il problema è che è incredibilmente lento. Questi sono i metodi rilevanti:

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; 
} 

Per diagnosticare perché è così lento, mi sono imbattuto in un profiler (Apple Instruments). I risultati sono stati sorprendenti: è lento a causa del blocco del sovraccarico. Il programma spende oltre il 90% del suo tempo in pthread_mutex_lock e _pthread_cond_wait.

io ho idea di dove l'overhead di blocco proviene, ma ho bisogno di sbarazzarsi di esso. Puoi suggerire i prossimi passi?

MODIFICA: vedere lo stack di chiamate espanso per _pthread_con_wait. Io non riesco a capire la fonte del sovraccarico di bloccaggio, cercando in questo modo:

Answer 1

Espandere lo stack di chiamate sulla _pthread_cond_wait e pthread_mutex_lock chiamate a scoprire dove le chiamate di blocco sono invocati da.

Come ipotesi, ho intenzione di dire che è in tutte le allocazioni di heap non necessarie che stai facendo. L'heap è una risorsa thread-safe e su questa piattaforma la sicurezza del thread potrebbe essere fornita tramite mutex.

Answer 2

Tutte le funzioni che leggono i dati da un istream bloccano i dati di lettura mutex, da un streambuf e sbloccano lo mutex. Per eliminare l'overhead, leggere il file direttamente da streambuf anziché da istream e non utilizzare stringstream per analizzare i dati.

Ecco una versione di getline che utilizza streambuf invece di 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; 
    } 
}