Я пытался оптимизировать собственный алгоритм, который сортирует векторы строковых кодов на основе внутренних критериев индексации. Длина кодов варьируется от 1 до 32 символов. Алгоритм выполнил std :: swap, чтобы переместить строку в новое место.
std::vector<std::string> temp_container(sorting_size+1,"");
for(auto &index_seed : all_seeds)
{
for(int i=sorting_size;i>=0;--i)
{
size_t index = // new index based on seed
std::swap(temp_container[index],original[i]);
}
original.swap(temp_container);
}
std :: swap перегружен в std :: string и должен выполнить перемещение в базовой строке, но профилирование кажетсячтобы показать, что подкачка выполняет копирование, а не перемещение, отчет от perf показывает
- 56.95% std::swap<char, std::char_traits<char>, std::allocator<char> > ▒
- 51.14% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::swap ▒
- 17.71% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_is_local ▒
- 8.77% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_local_data ▒
- 7.49% std::pointer_traits<char const*>::pointer_to ▒
- 4.41% std::addressof<char const> ▒
1.83% std::__addressof<char const> ▒
0.94% std::__addressof<char const> ▒
3.48% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_data ▒
2.12% std::pointer_traits<char const*>::pointer_to ▒
+ 4.99% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_set_length ▒
+ 3.76% __gnu_cxx::__alloc_traits<std::allocator<char>, char>::_S_on_swap ▒
3.62% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::length ▒
3.10% std::char_traits<char>::copy ▒
3.09% __memmove_avx_unaligned_erms ▒
2.59% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_local_data ▒
1.48% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_length ▒
1.01% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_get_allocator ▒
0.58% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_data ▒
1.21% std::char_traits<char>::copy ▒
0.90% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_set_length ▒
0.90% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::length ▒
0.70% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_is_local ▒
0.69% __gnu_cxx::__alloc_traits<std::allocator<char>, char>::_S_on_swap ▒
0.67% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_get_allocator ▒
0.53% std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_length
Я пытался использовать метод свопирования std :: string и форсировать перемещение, т.е.
// tried this
temp_container[index].swap(original[i]);
// and this
temp_container[index] = std::move(original[i]);
Но они не делали различий, сравнительный анализ последовательно показывает, что алгоритм использует более 2 сек для сортировки приблизительно 400 тыс. Строк кода.
Изменение векторов для использования string_views изначально дало гораздо лучшие результаты
std::vector<std::string_view> temp_container(sorting_size+1,"");
for(auto &index_seed : all_seeds)
{
for(int i=sorting_size;i>=0;--i)
{
size_t index = // new index based on seed
// original is now also vector of string_view
std::swap(temp_container[index],original[i]);
}
original.swap(temp_container);
}
Сравнительный анализ показывает, что версия string_view выполняет такую же сортировку менее чем за 1 сек.
Однако, когда я пытаюсь скомпилировать алгоритм с оптимизацией -O {1,2 или 3}, версия string_view работает в два раза медленнее, чем std ::строковая версия.
Проверка отсутствия кэша
perf stat -e task-clock,cycles,instructions,cache-references,cache-misses ./CodeSortingAlgo
для неоптимизированной версии std :: string:
2,756.98 msec task-clock # 1.147 CPUs utilized
8,024,349,488 cycles # 2.911 GHz
13,979,212,612 instructions # 1.74 insn per cycle
3,560,486 cache-references # 1.291 M/sec
1,881,425 cache-misses # 52.842 % of all cache refs
2.404464923 seconds time elapsed
2.734367000 seconds user
0.024020000 seconds sys
и для версии string_view:
1,266.53 msec task-clock # 1.354 CPUs utilized
3,586,135,363 cycles # 2.831 GHz
4,780,766,035 instructions # 1.33 insn per cycle
7,747,467 cache-references # 6.117 M/sec
6,172,017 cache-misses # 79.665 % of all cache refs
0.935125202 seconds time elapsed
1.243645000 seconds user
0.023916000 seconds sys
Запуск того же самого для версии алгоритма, скомпилированного с -O2 std :: string version:
281.92 msec task-clock # 1.214 CPUs utilized
794,130,273 cycles # 2.817 GHz
1,166,108,846 instructions # 1.47 insn per cycle
18,772,676 cache-references # 66.589 M/sec
3,797,519 cache-misses # 20.229 % of all cache refs
0.232186807 seconds time elapsed
0.258991000 seconds user
0.023906000 seconds sys
string_view version
393.30 msec task-clock # 1.137 CPUs utilized
1,124,532,667 cycles # 2.859 GHz
609,130,643 instructions # 0.54 insn per cycle
12,675,992 cache-references # 32.230 M/sec
6,753,795 cache-misses # 53.280 % of all cache refs
0.345989809 seconds time elapsed
0.366555000 seconds user
0.027590000 seconds sys
Почему копирование std :: swap и std :: string :: swap, а не перемещение, я что-то упустил? Я неправильно прочитал отчет о производительности?
Почему производительность std :: string_view в кеше такая плохая? Это потому, что вместо замены len и ptr, следующего за ptr, а затем подкачки?
Почему оптимизатор не может оптимизировать версию string_view до того же уровня, что и версия string.
compiler isgcc версия 8.3.0