почему GCC __builtin_prefetch не улучшает производительность?

Я пишу программу для анализа графа социальной сети. Это означает, что программе требуется много случайных обращений к памяти. Мне кажется, prefetch должен помочь. Вот небольшой фрагмент кода чтения значений от соседей вершины.

for (size_t i = 0; i < v.get_num_edges(); i++) {
    unsigned int id = v.neighbors[i];
    res += neigh_vals[id];
}

Я преобразовываю приведенный выше код в приведенный ниже и предварительно выбираю значения соседей вершины.

int *neigh_vals = new int[num_vertices];

for (size_t i = 0; i < v.get_num_edges(); i += 128) {
    size_t this_end = std::min(v.get_num_edges(), i + 128);
    for (size_t j = i; j < this_end; j++) {
        unsigned int id = v.neighbors[j];
        __builtin_prefetch(&neigh_vals[id], 0, 2);
    }
    for (size_t j = i; j < this_end; j++) {
        unsigned int id = v.neighbors[j];
        res += neigh_vals[id];
    }
}

В этом коде C++ я не переопределял никаких операторов.

К сожалению, код на самом деле не улучшает производительность. Интересно, почему. По-видимому, аппаратная предварительная выборка в этом случае не работает, потому что аппаратное обеспечение не может предсказать расположение памяти.

Интересно, вызвано ли это оптимизацией GCC. Когда я компилирую код, я включаю -O3. Я действительно надеюсь, что предварительная выборка может еще больше повысить производительность, даже если -O3 включен. В этом случае оптимизация -O3 объединяет две петли? Может ли -O3 включить предварительную выборку в этом случае по умолчанию?

Я использую gcc версии 4.6.3, и программа работает на Intel Xeon E5-4620.

Спасибо, да


gcc c performance prefetch
person Da Zheng    schedule 23.03.2015    source источник
comment
Что делает get_neighbor? Какой тип neigh_vals? Что такое vertex_id_t? Что такое v? Пожалуйста, отредактируйте свой вопрос, чтобы улучшить его.   -  person Basile Starynkevitch    schedule 23.03.2015
comment
См. также этот ответ на связанный вопрос   -  person Basile Starynkevitch    schedule 23.03.2015
comment
Похоже, вы выполняете предварительную выборку в одном цикле и надеетесь, что данные все еще будут доступны в следующем цикле. Это вряд ли поможет и, вероятно, навредит.   -  person Retired Ninja    schedule 23.03.2015
comment
И какая версия gcc, какой процессор? Вам нужно отредактировать свой вопрос, чтобы улучшить его.   -  person Basile Starynkevitch    schedule 23.03.2015
comment
В сторону: является ли v.get_num_edges() инвариантным на протяжении всего цикла for? Похоже, вы можете назначить его переменной, а не вызывать ее каждый раз в начале цикла.   -  person Andy Lester    schedule 23.03.2015

Ответы (1)


arrow_upward
7
arrow_downward

Да, некоторые последние версии GCC (например, 4.9 в марте 2015 г.) могут выдавать некоторые PREFETCH инструкции при оптимизации. с -O3 (даже без явного __builtin_prefetch)

Мы не знаем, что делает get_neighbor и какие бывают типы v и neigh_val.

И предварительная выборка не всегда выгодна. Добавление явного __builtin_prefetch может замедлить ваш код. Вам нужно измерить.

Как прокомментировал Ninja на пенсии, предварительная выборка в одном цикле и надежда на то, что данные будут кэшированы в следующем цикле (ниже в вашем исходный код) неверен.

Возможно, вы могли бы попробовать вместо этого

for (size_t i = 0; i < v.get_num_edges(); i++) {
  fg::vertex_id_t id = v.get_neighbor(i);
  __builtin_prefetch (neigh_val[v.get_neighbor(i+4)]);
  res += neigh_vals[id];
}

Вы можете эмпирически заменить 4 любой подходящей константой, которая лучше всего подходит.

Но я предполагаю, что __builtin_prefetch выше бесполезно (поскольку компилятор, вероятно, может добавить его сам) и может повредить (или даже привести к сбою программы, когда вычисление ее аргумента дает неопределенное поведение, например, если v.get_neighbor(i+4) не определено; однако предварительная выборка адрес за пределами вашего адресного пространства не повредит, но может замедлить вашу программу). Пожалуйста, сравните.

См. этот ответ на соответствующий вопрос.

Обратите внимание, что в C++ все [], get_neighbor могут быть перегружены и становятся очень сложными операциями, так что мы не можем догадаться!

И бывают случаи, когда аппаратное обеспечение ограничивает производительность, какие бы __builtin_prefetch вы ни добавляли (и их добавление может ухудшить производительность).

Кстати, вы можете передать -O3 -mtune=native -fdump-tree-ssa -S -fverbose-asm, чтобы лучше понять, что делает компилятор (и заглянуть внутрь сгенерированных файлов дампа и файлов ассемблера); также случается, что -O3 производит немного более медленный код, чем то, что дает -O2.

Вы можете рассмотреть явную многопоточность, OpenMP, OpenCL если у вас есть время тратить на оптимизацию. Помните, что преждевременная оптимизация — это зло. Вы тестировали, вы профилировали все ваше приложение?

person Basile Starynkevitch    schedule 23.03.2015
comment
Просто для ясности: «или даже сбой программы» не означает, что предварительная выборка генерирует ошибки, если адрес недействителен, но само выражение адреса должно быть действительным. - person Jon Purdy; 23.03.2015