У меня есть код синхронизации, который я использую для измерения времени выполнения данного фрагмента кода:
struct time_data {
std::chrono::steady_clock::time_point start, end;
auto get_duration() const {
return end - start;
}
void print_data(std::ostream & out) const {
out << str();
}
std::string str() const {
static const std::locale loc{ "" };
std::stringstream ss;
ss.imbue(loc);
ss << "Start: " << std::setw(24) << std::chrono::nanoseconds{ start.time_since_epoch() }.count() << "ns\n";
ss << "End: " << std::setw(24) << std::chrono::nanoseconds{ end.time_since_epoch() }.count() << "ns\n";
ss << "Duration: " << std::setw(24) << std::chrono::nanoseconds{ get_duration() }.count() << "ns\n";
return ss.str();
}
static friend std::ostream & operator<<(std::ostream & out, const time_data & data) {
return out << data.str();
}
};
template<typename T>
time_data time_function(T && func) {
time_data data;
data.start = std::chrono::steady_clock::now();
func();
data.end = std::chrono::steady_clock::now();
return data;
}
Затем, чтобы использовать его, у меня есть следующий код, предназначенный для выполнения накопления в наборе данных, но вместо простого добавления чисел вместе он сначала обнаруживает, что Total Stopping Time применяет гипотеза Collatz и накапливает это вместо этого.
template<typename T>
T accumulation_function(T a, T b) {
T count = 0;
while (b > 1) {
if (b % 2 == 0) b /= 2;
else b = b * 3 + 1;
++count;
}
return a + count;
}
template<typename IT>
auto std_sum(IT begin, IT end) {
auto sum = (*begin - *begin);
sum = std::accumulate(begin, end, sum, accumulation_function<decltype(sum)>);
return sum;
}
template<typename IT>
auto single_thread_sum(IT begin, IT end) {
auto sum = (*begin - *begin);
IT current = begin;
while (current != end) {
sum = accumulation_function(sum, *current);
++current;
}
return sum;
}
template<typename IT, uint64_t N>
auto N_thread_smart_sum(IT begin, IT end) {
auto sum = (*begin - *begin);
std::vector<std::thread> threads;
std::array<decltype(sum), N> sums;
auto dist = std::distance(begin, end);
for (uint64_t i = 0; i < N; i++) {
threads.emplace_back([=, &sums] {
IT first = begin;
IT last = begin;
auto & tsum = sums[i];
tsum = 0;
std::advance(first, i * dist / N);
std::advance(last, (i + 1) * dist / N);
while (first != last) {
tsum = accumulation_function(tsum, *first);
++first;
}
});
}
for (std::thread & thread : threads)
thread.join();
for (const auto & s : sums) {
sum += s;
}
return sum;
}
template<typename IT>
auto two_thread_smart_sum(IT begin, IT end) {
return N_thread_smart_sum<IT, 2>(begin, end);
}
template<typename IT>
auto four_thread_smart_sum(IT begin, IT end) {
return N_thread_smart_sum<IT, 4>(begin, end);
}
template<typename IT>
auto eight_thread_smart_sum(IT begin, IT end) {
return N_thread_smart_sum<IT, 8>(begin, end);
}
template<typename IT>
auto sixteen_thread_smart_sum(IT begin, IT end) {
return N_thread_smart_sum<IT, 16>(begin, end);
}
template<typename IT>
auto thirty_two_thread_smart_sum(IT begin, IT end) {
return N_thread_smart_sum<IT, 32>(begin, end);
}
template<typename IT>
auto sixty_four_thread_smart_sum(IT begin, IT end) {
return N_thread_smart_sum<IT, 64>(begin, end);
}
И для справки: код шаблона main, который запускает все это:
int main() {
std::vector<int64_t> raw_data;
auto fill_data = time_function([&raw_data] {
constexpr uint64_t SIZE = 1'000'000'000ull;
raw_data.resize(SIZE);
std::vector<std::thread> threads;
for (int i = 0; i < 8; i++) {
threads.emplace_back([i, SIZE, &raw_data] {
uint64_t begin = i * SIZE / 8;
uint64_t end = (i + 1) * SIZE / 8;
for (uint64_t index = begin; index < end; index++) {
raw_data[index] = begin % (20 + i);
}
});
}
for (std::thread & t : threads)
t.join();
});
int64_t sum;
std::cout << std::setw(25) << "Fill Data" << std::endl;
std::cout << fill_data << std::endl;
auto std_data = time_function([&] {
sum = std_sum(raw_data.begin(), raw_data.end());
});
std::cout << std::setw(25) << "STD Sum: " << sum << std::endl;
std::cout << std_data << std::endl;
auto single_data = time_function([&] {
sum = single_thread_sum(raw_data.begin(), raw_data.end());
});
std::cout << std::setw(25) << "Single Sum: " << sum << std::endl;
std::cout << single_data << std::endl;
auto smart_2_data = time_function([&] {
sum = two_thread_smart_sum(raw_data.begin(), raw_data.end());
});
std::cout << std::setw(25) << "Two-Thread-Smart Sum: " << sum << std::endl;
std::cout << smart_2_data << std::endl;
auto smart_4_data = time_function([&] {
sum = four_thread_smart_sum(raw_data.begin(), raw_data.end());
});
std::cout << std::setw(25) << "Four-Thread-Smart Sum: " << sum << std::endl;
std::cout << smart_4_data << std::endl;
auto smart_8_data = time_function([&] {
sum = eight_thread_smart_sum(raw_data.begin(), raw_data.end());
});
std::cout << std::setw(25) << "Eight-Thread-Smart Sum: " << sum << std::endl;
std::cout << smart_8_data << std::endl;
auto smart_16_data = time_function([&] {
sum = sixteen_thread_smart_sum(raw_data.begin(), raw_data.end());
});
std::cout << std::setw(25) << "Sixteen-Thread-Smart Sum: " << sum << std::endl;
std::cout << smart_16_data << std::endl;
auto smart_32_data = time_function([&] {
sum = thirty_two_thread_smart_sum(raw_data.begin(), raw_data.end());
});
std::cout << std::setw(25) << "Thirty-Two-Thread-Smart Sum: " << sum << std::endl;
std::cout << smart_32_data << std::endl;
auto smart_64_data = time_function([&] {
sum = sixty_four_thread_smart_sum(raw_data.begin(), raw_data.end());
});
std::cout << std::setw(25) << "Sixty-Four-Thread-Smart Sum: " << sum << std::endl;
std::cout << smart_64_data << std::endl;
return 0;
}
Это вывод программы:
Fill Data
Start: 16,295,979,890,252ns
End: 16,300,523,805,484ns
Duration: 4,543,915,232ns
STD Sum: 7750000000
Start: 16,300,550,212,791ns
End: 16,313,216,607,890ns
Duration: 12,666,395,099ns
Single Sum: 7750000000
Start: 16,313,216,694,522ns
End: 16,325,774,379,684ns
Duration: 12,557,685,162ns
Two-Thread-Smart Sum: 7750000000
Start: 16,325,774,466,014ns
End: 16,334,441,032,868ns
Duration: 8,666,566,854ns
Four-Thread-Smart Sum: 7750000000
Start: 16,334,441,137,913ns
End: 16,342,188,642,721ns
Duration: 7,747,504,808ns
Eight-Thread-Smart Sum: 7750000000
Start: 16,342,188,770,706ns
End: 16,347,850,908,471ns
Duration: 5,662,137,765ns
Sixteen-Thread-Smart Sum: 7750000000
Start: 16,347,850,961,597ns
End: 16,352,187,838,584ns
Duration: 4,336,876,987ns
Thirty-Two-Thread-Smart Sum: 7750000000
Start: 16,352,187,891,710ns
End: 16,356,111,411,220ns
Duration: 3,923,519,510ns
Sixty-Four-Thread-Smart Sum: 7750000000
Start: 16,356,111,471,288ns
End: 16,359,988,028,812ns
Duration: 3,876,557,524ns
Первые несколько результатов не удивительны: мой самоналоженный код накапливания работает примерно так же, как функция std::accumulate (я видел, как оба появляются как "самые быстрые" в последовательных прогонах, подразумевая, что их реализация, вероятно, аналогична). И когда я перехожу к двум потокам и четырем потокам, код становится быстрее. Это имеет смысл, потому что я использую 4-ядерный процессор Intel.
Но результаты, выходящие за эту точку, сбивают с толку. Мой процессор имеет только 4 ядра (8, если вы считаете гиперпоточность), но даже если я извиняюсь, что Hyperthreading дает предельную производительность в 8 потоках, набирая число до 16, 32 и 64 потоков, все это дает дополнительный прирост производительности. Почему это? Как дополнительные потоки приносят дополнительный прирост производительности, когда я уже давно превысил количество потоков, которые процессор может физически выполнять одновременно?
Примечание: это не то же самое, что этот связанный вопрос, поскольку я имею дело с конкретным вариантом использования и кодом, тогда как связанный вопрос имеет дело с общими.
Я сделал корректировку кода, так что, когда потоки создаются, их приоритет устанавливается на Windows с самым высоким приоритетом. Результаты, в общем, кажутся одинаковыми.
Fill Data
Start: 18,950,798,175,057ns
End: 18,955,085,850,007ns
Duration: 4,287,674,950ns
STD Sum: 7750000000
Start: 18,955,086,975,013ns
End: 18,967,581,061,562ns
Duration: 12,494,086,549ns
Single Sum: 7750000000
Start: 18,967,581,136,724ns
End: 18,980,127,355,698ns
Duration: 12,546,218,974ns
Two-Thread-Smart Sum: 7750000000
Start: 18,980,127,426,332ns
End: 18,988,619,042,214ns
Duration: 8,491,615,882ns
Four-Thread-Smart Sum: 7750000000
Start: 18,988,619,135,487ns
End: 18,996,215,684,824ns
Duration: 7,596,549,337ns
Eight-Thread-Smart Sum: 7750000000
Start: 18,996,215,763,004ns
End: 19,002,055,977,730ns
Duration: 5,840,214,726ns
Sixteen-Thread-Smart Sum: 7750000000
Start: 19,002,056,055,608ns
End: 19,006,282,772,254ns
Duration: 4,226,716,646ns
Thirty-Two-Thread-Smart Sum: 7750000000
Start: 19,006,282,840,774ns
End: 19,010,539,676,914ns
Duration: 4,256,836,140ns
Sixty-Four-Thread-Smart Sum: 7750000000
Start: 19,010,539,758,113ns
End: 19,014,450,311,829ns
Duration: 3,910,553,716ns
Я отредактировал программу, чтобы убедиться, что переменная tsum была локальной переменной внутри лямбда, а не ссылкой на внешнюю сторону лямбда. Многопоточный код ускорился довольно значительно, но он все еще демонстрирует то же поведение.
Fill Data
Start: 21,740,931,802,656ns
End: 21,745,429,501,480ns
Duration: 4,497,698,824ns
STD Sum: 7750000000
Start: 21,745,430,637,655ns
End: 21,758,206,612,632ns
Duration: 12,775,974,977ns
Single Sum: 7750000000
Start: 21,758,206,681,153ns
End: 21,771,260,233,797ns
Duration: 13,053,552,644ns
Two-Thread-Smart Sum: 7750000000
Start: 21,771,260,287,828ns
End: 21,777,845,764,595ns
Duration: 6,585,476,767ns
Four-Thread-Smart Sum: 7750000000
Start: 21,777,845,831,002ns
End: 21,784,011,543,159ns
Duration: 6,165,712,157ns
Eight-Thread-Smart Sum: 7750000000
Start: 21,784,011,628,584ns
End: 21,788,846,061,014ns
Duration: 4,834,432,430ns
Sixteen-Thread-Smart Sum: 7750000000
Start: 21,788,846,127,422ns
End: 21,791,921,652,246ns
Duration: 3,075,524,824ns
Thirty-Two-Thread-Smart Sum: 7750000000
Start: 21,791,921,747,330ns
End: 21,794,980,832,033ns
Duration: 3,059,084,703ns
Sixty-Four-Thread-Smart Sum: 7750000000
Start: 21,794,980,901,761ns
End: 21,797,937,401,426ns
Duration: 2,956,499,665ns
Я снова повторил те же тесты, но наоборот. Результаты довольно схожи:
Fill Data
Start: 22,845,472,001,475ns
End: 22,850,746,219,215ns
Duration: 5,274,217,740ns
Sixty-Four-Thread-Smart Sum: 7750000000
Start: 22,850,747,328,223ns
End: 22,853,951,903,952ns
Duration: 3,204,575,729ns
Thirty-Two-Thread-Smart Sum: 7750000000
Start: 22,853,951,981,830ns
End: 22,857,239,237,507ns
Duration: 3,287,255,677ns
Sixteen-Thread-Smart Sum: 7750000000
Start: 22,857,239,307,839ns
End: 22,860,389,285,305ns
Duration: 3,149,977,466ns
Eight-Thread-Smart Sum: 7750000000
Start: 22,860,389,353,524ns
End: 22,864,828,560,484ns
Duration: 4,439,206,960ns
Four-Thread-Smart Sum: 7750000000
Start: 22,864,828,633,834ns
End: 22,870,640,982,096ns
Duration: 5,812,348,262ns
Two-Thread-Smart Sum: 7750000000
Start: 22,870,641,056,956ns
End: 22,877,032,284,384ns
Duration: 6,391,227,428ns
Single Sum: 7750000000
Start: 22,877,032,367,997ns
End: 22,889,501,695,960ns
Duration: 12,469,327,963ns
STD Sum: 7750000000
Start: 22,889,501,770,820ns
End: 22,902,014,633,229ns
Duration: 12,512,862,409ns
Все ваши записи tsum относятся к тем же array, которые будут занимать последовательные адреса в памяти. Это вызовет проблемы с конфликтом в кешках со всеми этими записями. Имея больше потоков, они записывают в разные строки кэша, поэтому ядра процессора тратят меньше времени на недействительность и перезагрузку строк кэша.
Попробуйте скопировать в локальную переменную tsum (а не ссылку в sums), а затем записать ее в sums[i], когда цикл завершен.
Я подозреваю, что вы видите ускорение, потому что потоки для вашего приложения представляют собой больший процент от общего количества активных потоков, запущенных в системе, что дает вам больше кусочков времени в целом. Возможно, вам захочется узнать, изменились ли цифры в лучшую сторону или хуже, когда у вас есть дополнительные программы.