Блог

Я бы хотел использовать a std::pmr::unordered_map с a std::pmr::monotonic_buffer_resource . Они хорошо сочетаются друг с другом, потому что узлы набора стабильны, поэтому я не создаю много дыр в буферном ресурсе путем перераспределения:

  std::pmr::monotonic_buffer_resource res;
 std::pmr::unordered_set<T> set(amp;res);
  

То есть, за исключением списка корзин, который необходимо перераспределить, когда set перефразирует, поскольку он превышает max_load_factor() . Предполагая, что я не могу reserve() выбраться из этого, и я действительно забочусь о дырах в буферном ресурсе, оставленных старыми списками корзин с тех пор, как они выросли, каковы мои варианты?

Если я знаю, что unordered_set это реализовано как std::vector<std::forward_list> , как в (некоторых версиях) MSVC, тогда я должен иметь возможность использовать a scoped_allocator для предоставления разных распределителей для vector и forward_list . Но а) я не могу полагаться на то, что unordered_set я a vector<forward_list> в переносимом коде, и б) scoped_allocator Allocator monotonic_buffer_resource это while is a memory_resource , несоответствие импеданса, которое приведет к очень сложной инициализации.

Или я мог бы написать a switch_memory_resource , который делегирует другим memory_resource s в зависимости от размера запроса. Затем я мог бы использовать a monotonic_buffer_resource для запросов, соответствующих размеру узлов (которые, однако, я также не могу переносимо знать) и default_memory_resource() для всего остального. Вероятно, я мог бы сделать обоснованное предположение, что узлов не более sizeof(struct {void* next; size_t hash; T value;}) , добавить некоторый запас ошибок, умножив его на два и используя это как ограничение между двумя memory_resource s, но мне интересно, есть ли более чистый способ?

Небольшое количество конкретных типов ресурсов, которые я предложил несколько лет назад и которые были приняты в C 17, представляли собой минималистичный набор полезных распределителей. Как видно из вашего вопроса, они не обеспечивают оптимального поведения для всех обстоятельств. Не так много наборов настроек, и я сожалею об отсутствующей функциональности, но они все еще полезны для большинства случаев.

Для вашей конкретной ситуации вы говорите: «Предполагая, что я не могу reserve() выбраться из этого, и я действительно забочусь о дырах в буферном ресурсе, оставленных старыми списками корзин с тех пор, как они выросли». Я не уверен, что какой-либо общий распределитель может вам помочь. Геометрический рост списка разделов оставит пробелы в любой стратегии распределения. Вопрос в том, можно ли повторно использовать и / или минимизировать эти отверстия. Как вы указываете, только очень тщательно настроенный распределитель для конкретной ситуации сведет к минимуму эти дыры. Но, возможно, ваши предположения слишком сильны.

Рассмотрим a std::pmr::vector<int> . Это наихудший сценарий для a monotonic_buffer_resource , потому что каждое перераспределение приводит к утечке памяти. И все же даже в этом случае наихудшая потеря памяти составляет всего 50%; т. Е. Он никогда не будет использовать более чем в два раза больше памяти, чем при использовании ресурса, который идеально повторно использует блоки памяти. Конечно, 50% может быть довольно плохим, но в вашем сценарии мы говорим намного, намного меньше. Для достаточно большого набора список сегментов мал по сравнению с сегментами и самими данными, и вы можете использовать reserve его для минимизации перераспределения. Итак, мой первый совет — продолжить и использовать monotonic_buffer_resource без изменений и измерить, есть ли у вас неприемлемое использование памяти. Вторым экспериментом было бы использовать unsynchronized_pool_resource поддержанный (восходящий) monotonic_buffer_resource .

Если вы решите, что хотите создать пользовательский ресурс для этой цели, что может быть плодотворным и даже забавным, ваш подход выбора некоторого нижнего порога для перехода к монотонному распределителю, вероятно, сработает и на самом деле не потребует больших усилий. Вы также можете подумать о том, чтобы сделать его адаптивным: сохраните список последних, скажем, 4, размеров выделения. Если какой-либо размер получает более двух попаданий, предположим, что это ваш размер узла, и выделите эти узлы из монотонного ресурса, в то время как другие запросы передаются непосредственно на вышестоящий ресурс. Однако будьте осторожны, чтобы использовать такой пользовательский распределитель только тогда, когда вы знаете, что происходит. Если у вас есть std::pmr::unordered_set<std::pmr::string> , то оба подхода могут привести к тому, что многие строки будут выделены из вышестоящего ресурса и, таким образом, потеряют преимущество монотонного буфера. Как вы можете видеть, слишком скупая память для вашего списка корзин может иметь неприятные последствия в общем контексте. Вы, вероятно, обнаружите, что неизмененный monotonic_buffer_resource вариант был лучшим выбором.

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

Определение std::pmr::unordered_set

 using unordered_set = std::unordered_set<Key, Hash, Pred,
                                         std::pmr::polymorphic_allocator<Key>>
  

Что указывает на то, что он используется только для узлов.

Но короткий тест показывает, что он используется и для того, и для другого, что меня огорчает. Таким образом, единственным способом будет проверка размера выделения.

эта часть указывает, что распределитель учитывает только Key

 std::pmr::polymorphic_allocator<**Key**>
  

В старых распределителях были функции повторной привязки для преобразования в другой тип распределителя, который я не видел в pmr (он есть std::allocator_traits , см. Комментарии).

Я как раз начинал писать что-то вроде этого

   void* do_allocate(std::size_t bytes, std::size_t alignment) override {
    if (bytes == first_size)
      return first_alloc->allocate(bytes, alignment);
    return second_alloc->allocate(bytes, alignment);
  }
  

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