защо 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 може да забави вашия код. Трябва да измерите.

Както коментира Retired 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