Почему pmr :: string так медленно в этих тестах?

Question

Испытание примера в Раздел 5.9.2 Класс monotonic_buffer_resource следующей статьи о Полиморфных Ресурсах Памяти Пабло Халперна:

Номер документа: N3816
Дата: 2013-10-13
Автор: Пабло Халперн
phalpern@halpernwightsoftware.com
Полиморфные ресурсы памяти - r1
(Изначально N3525 - Полиморфные распределители)

В статье утверждается, что:

Класс monotonic_buffer_resource предназначен для очень быстрого выделения памяти в ситуациях, когда память используется для создания нескольких объектов, а затем освобождается все сразу, когда эти объекты выходят из области видимости.

и это:

Особенно хорошим использованием для monotonic_buffer_resource является предоставление памяти для локальной переменной типа контейнера или строки.Например, следующий код объединяет две строки, ищет слово «hello» в объединенной строке, а затем отбрасывает объединенную строку после того, как слово найдено или не найдено.Ожидается, что длина конкатенированной строки будет не более 80 байт, поэтому код оптимизирован для этих коротких строк с использованием небольшого monotonic_buffer_resource [...]

Я протестировал пример, используя библиотека бенчмарков Google и boost.container 1.69 полиморфные ресурсы , скомпилированные и связанные с выпусками двоичных файлов с g ++ - 8 на виртуальной машине Ubuntu 18.04 LTS hyper-v со следующим кодом:

// overload using pmr::string
static bool find_hello(const boost::container::pmr::string& s1, const boost::container::pmr::string& s2)
{
    using namespace boost::container;

    char buffer[80];
    pmr::monotonic_buffer_resource m(buffer, 80);
    pmr::string s(&m);
    s.reserve(s1.length() + s2.length());
    s += s1;
    s += s2;
    return s.find("hello") != pmr::string::npos;
}

// overload using std::string
static bool find_hello(const std::string& s1, const std::string& s2)
{
    std::string s{};
    s.reserve(s1.length() + s2.length());
    s += s1;
    s += s2;
    return s.find("hello") != std::string::npos;
}

static void allocator_local_string(::benchmark::State& state)
{
    CLEAR_CACHE(2 << 12);

    using namespace boost::container;
    pmr::string s1(35, 'c'), s2(37, 'd');

    for (auto _ : state)
    {
        ::benchmark::DoNotOptimize(find_hello(s1, s2));
    }
}

// pmr::string with monotonic buffer resource benchmark registration
BENCHMARK(allocator_local_string)->Repetitions(5);

static void allocator_global_string(::benchmark::State& state)
{
    CLEAR_CACHE(2 << 12);

    std::string s1(35, 'c'), s2(37, 'd');

    for (auto _ : state) 
    {
        ::benchmark::DoNotOptimize(find_hello(s1, s2));
    }
}

// std::string using std::allocator and global allocator benchmark registration
BENCHMARK(allocator_global_string)->Repetitions(5);

Вот результаты:

Как тест производительности pmr :: string такой медленный по сравнению с std :: string?

Я предполагаю, что std :: string std :: allocator должен использовать «new» при резервном вызове и впоследствии создавать каждый символ при вызове:

s += s1; 
s += s2

Сравнение с pmr ::Строка, использующая полиморфный распределитель, который содержит monotonic_buffer_resource, резервирование памяти должно сводиться к простой арифметике указателей, не требуя «new», так как буфера char должно быть достаточно.Впоследствии он будет конструировать каждый символ как std :: string.

Таким образом, учитывая, что единственными отличающимися операциями между версией pmr :: string для find_hello и версией find_hello для std :: string является вызов резервной памяти, где pmr :: string использует распределение стека и std:: строка с использованием распределения кучи:

• Мой тест неверен?
• Является ли моя интерпретация того, как распределение должно происходить неправильно?
• Почему тест pmr :: stringпримерно в 5 раз медленнее, чем эталонный тест std :: string?

Answer 1

Есть комбинация вещей, которая делает повышение pmr::basic_string медленнее:

1. Строительство pmr::monotonic_buffer_resource имеет определенную стоимость (17 наносекунд здесь).
2. pmr::basic_string::reserve резервирует больше, чем требуется.В этом случае он резервирует 96 байтов, что больше, чем у вас есть 80 байтов.
3. Резервирование в pmr::basic_string не является бесплатным, даже когда буфер достаточно большой (дополнительные 8 наносекунд здесь).
4. Конкатенация строк является дорогостоящей (дополнительные 64 нс здесь).
5. pmr::basic_string::find имеет неоптимальную реализацию.Это реальная цена за плохую скорость.В GCC std::basic_string::find использует __builtin_memchr, чтобы найти первый символ, который может совпасть, какое повышение делает все это в одном большом цикле.По-видимому, это основная стоимость, и что делает boost работать медленнее, чем std.

Итак, после увеличения буфера и сравнения boost::container::string с boost::container::pmr::string версия pmr становится немного медленнее (293нс против 276 нс).Это потому, что new и delete на самом деле довольно быстры для таких микропроцессоров и работают быстрее, чем сложное оборудование pmr (всего 17 нс для строительства).Фактически, по умолчанию Linux / gcc new / delete повторно использует один и тот же указатель.Эта оптимизация имеет очень простую и быструю реализацию, которая также прекрасно работает с кешем процессора.

В качестве доказательства попробуйте это (без оптимизации):

for (int i=0 ; i < 10 ; ++i)
{
  char * ptr = new char[96];
  std::cout << (void*) ptr << '\n';
  delete[] ptr;
}

Это снова и снова печатает один и тот же указатель.

Теория такова, что в реальной программегде new / delete не ведут себя так хорошо и не могут повторно использовать один и тот же блок снова и снова, тогда new / delete значительно замедляет выполнение, и локальность кэша становится довольно плохой.В таком случае буфер pmr + того стоит.

Вывод: реализация строки boost pmr медленнее, чем строка gcc.Механизм pmr немного дороже, чем стандартный и простой сценарий new / delete.