6

グラフ ファイル形式用の単純なリーダーとパーサーを作成しました。問題は、それが信じられないほど遅いことです。関連するメソッドは次のとおりです。

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

なぜこんなに遅いのかを診断するために、プロファイラー (Apple Instruments) で実行しました。結果は驚くべきものでした。ロックのオーバーヘッドが原因で遅いのです。pthread_mutex_lockプログラムは、その時間の 90% 以上をとで費やしてい_pthread_cond_waitます。

楽器

ロックのオーバーヘッドがどこから来るのかわかりませんが、それを取り除く必要があります。次のステップを提案できますか？

編集: のコール スタックを展開して参照してください_pthread_con_wait。これを見ても、ロックのオーバーヘッドの原因を突き止めることはできません。

ここに画像の説明を入力

4

2 に答える 2

2

_pthread_cond_wait および pthread_mutex_lock 呼び出しの呼び出しスタックを展開して、ロック呼び出しがどこから呼び出されたかを調べます。

推測として、あなたが行っているすべての不要なヒープ割り当てにあると言えます。ヒープはスレッド セーフなリソースであり、このプラットフォームではミューテックスを介してスレッド セーフを提供できます。

于 2013-01-23T15:55:00.467 に答える
1

からデータを読み取るすべての関数は、 からの読み取りデータistreamをロックし、のロックを解除します。そのオーバーヘッドをなくすには、ではなくから直接ファイルを読み取り、 を使用してデータを解析しないでください。mutex,streambufmutexstreambufistreamstringstream

これは、代わりにgetline使用する のバージョンですstreambufistream

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;
    }
}
于 2013-01-23T17:54:14.063 に答える