Запрос запаса места в unordered контейнерах перед переаллокацией

alexander.y.k
alexander.y.k

Сейчас для определения такой ситуации либо нужно делать сравнение целого числа с float:

if( unord.size() + new_items_count >= unord.max_load_factor() * unord.bucket_count() ) {
    // slow insertion
} 
else {
    // fast insertion 
}

А так же здесь для меня до сих пор не очевидно, что нужно использовать знак сравнения ">=" (в gcc реализации в этом примере корректен именно он), по тому, что пересказ стандарта своими словами легко может сделать сравнение строгим. Так например cppreference.com, наводит именно на эти мысли:

> The container automatically increases the number of buckets if the load factor exceeds this [max_load_factor()] threshold.

Так же можно добиться результата эмулируя происходящее внутри контейнера, что должно быть снова затрагивает float'ы, и вообще говоря implementation specific, и так же не очевидна корректность происходящего для всех возможных комбинаций размера коллекции, количества вставляемых элементов и актуальных значений max_load_factor() и bucket_count().

Помимо этого, сама формулировка из стандарта: "The container automatically increases the number of buckets as necessary to keep the load factor below this [max_load_factor()] number", — не ограничивает реализации делать переаллокации в "удобное" для них время.

Далее, учитывая доминирующее положении реализации float чисел по стандарту IEEE 754, мы получаем, что если число элементов вышло за пределы 2^24 (=16'777'216), то требуется точная эмуляция поведения реализации для недежных выводов.

Я могу ошибаться, но кажется есть еще один нюанс того как x86 процессоры производят floating арифметику — они ведут флаг округления говорящий в какую сторону был округлен резултат последней операции, и в следующий раз применяют округление в другую сторону, чтобы накопление ошибок округления более-менее нивелировали друг друга в последовательных вычислениях. Если такие механизмы имеются на платформе, то собственноручно написанная техника проверки запаса может дать иной результат относительно того какой получила реализация в текущий момент.

Таким образом хотелось бы иметь гарантированно работающий механизм получения запаса на количество вставляемых элементов которое не преведет к переаллокации, что-то вроде такого:

if( unord.size() + new_items_count > unord.capacity() ) {
    // slow insert
}
else {
    // fast insert
}
4
рейтинг
3 комментария
alexander.y.k
Демонстрация проблемы (осторожно, требует 10GB RAM):

#include <iostream>
#include <unordered_set>

int main()
{
std::unordered_set< int > unord;
unsigned actual_buckets = unord.bucket_count();

for( int i = 0; i < 256*1024*1024; ++i )
{

if( unord.size() + 1 >= unord.bucket_count() * unord.max_load_factor() ) {
std::cout << "Expect rehashing on " << unord.size() + 1 << " items." << std::endl;
}

unord.insert( i );

if( actual_buckets != unord.bucket_count() ) {
std::cout << "Buckets extended from " << actual_buckets << " to " << unord.bucket_count() << std::endl;
actual_buckets = unord.bucket_count();
}

}

return 0;
}

Вывод:
...
Expect rehashing on 36473443 items.
Buckets extended from 36473443 to 74066549
Expect rehashing on 74066549 items.
Buckets extended from 74066549 to 150406843
Expect rehashing on 150406840 items.
Expect rehashing on 150406841 items.
Expect rehashing on 150406842 items.
Expect rehashing on 150406843 items.
Buckets extended from 150406843 to 305431229
...
alexander.y.k
yndx-antoshkka
alexander.y.k, может в данном примере стоит использовать rehash/reserve, чтобы избежать проблемы? Или есть случаи, где rehash/reserve не помогают?
yndx-antoshkka
alexander.y.k
yndx-antoshkka, да, это вполне возможно. Например оценивать что load_factor стал равен 90% от max_load_factor, тогда производить reserve и вставку. Единственное что смущает, что это эвристика, и она требует дополнительные усилия и внимательность чтобы сделать все правильно. Например нужно предусмотреть, что кол-во вставляемых элементов + актуальный размер коллекции будут меньше чем новый "capacity", а еще лучше меньше чем 90% этой величины. На мой взгляд для такой тривиальной операции сложность слишком высока.

Отсюда несколько выводов: 1. трудно быть абсолютно уверенным, что наша эвристика корректно себя ведет для любой тройки величин: размера коллекции, max_load_factor и числа вставляемых элементов; 2. мы никогда не используем максимально эффективно все доступное пространство; 3. мы искажаем политику роста контейнера собственной логикой, что не критично, но намекает на проблему в стандартном дизайне.

Хотелось бы видеть в С++ такой уровень инженерной дисциплины, который не опирается на подобные техники.

Замечу так же, что судя по тому, что мне удалось понять из сходных кодов GCC, они уже имеют величину, которая, c дополнительной проверкой, реализует семантику capacity(), это _M_next_rehash:
github.com/gcc-mirror/gcc/blob/e11be3ea01eaf8acd8cd86d3f9c427621b64e6b4/libstdc%2B%2B-v3/include/bits/hashtable_policy.h#L597

Но дополнительная проверка вновь зависит от float арифметики.
alexander.y.k
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).