Возможность realloc

[apolukhin]

Перенос предложения: голоса +8, -1
Aвтор идеи: h4tred

В текущем виде, если нужно увеличить размер массива, мы вынуждены сначала аллоцировать новый, после чего делать копию/перемещение существующих элементов и освобождать память. Это объяснимо и применимо для типов у которых есть нетривиальные конструкторы копирования/перемещения, но не является оптимильным для простых типов.

Примерный вид может быть таким:

new_ptr = new (old_ptr) Foo[new_size];

Сигнатура для оператора new, может быть такой:

void* operator new[] (size_t size, void *old_ptr, struct realloc_tag);

тег нужен, что бы не конфликтовать с существующей сигнатурой для placement new.

Предложенный синтаксис в текущем виде применим для placement new, но может вызывать ряд проблем:

• http://stackoverflow.com/questions/15254/can-placement-new-for-arrays-be-used-in-a-portable-way
• http://stackoverflow.com/questions/4011577/placement-new-array-alignment

Если кто-то осторожно работает с placement new для массивов, возможна поломка обратной совместимости. Что бы избежать возможно:

Добавление тега в вызов new:

    new (realloc_tag, old_ptr) Foo[new_size]​

Использовать новый специальный оператор, напрример renew

Данных механизм применим только для памяти выделенной при помощи new[].

Поддержка со стороны языка нужна, что бы можно было отличить тип элемента массива и правильно принять решение: делать realloc или вызывать new[]+move/copy+delete[].

[apolukhin]

Олег Ляттэ, 6 декабря 2016, 1:14
А чем не устраивает std::vector? Он делает по сути всё, что Вы хотите от realloc new. Плюс RAII, помогающий избежать проблем, характерных для ручной работы с памятью.

Victor Dyachenko, 6 декабря 2016, 15:42
Олег Ляттэ, а vector может расширить свою capacity без копирования уже созданных элементов в другое место? Не может. Вот как минимум для реализации такого и нужен realloc.

Victor Dyachenko, 6 декабря 2016, 15:42
Боюсь, что попытка полностью имитировать realloc() - это провальная идея, так как в общем случае объекты в C++ нельзя копировать с помощью memcpy(). Но вот возможность расширить выделеный кусок памяти, если рядом с ним есть свободное место - фича очень полезная и нужная. Тот же vector не использует move-конструктор элементов, если он не noexcept, что заметно бьёт по производительности, если кто-то написал даже тривиальный move-конструктор, но забыл его пометить noexcept. А если элементы не надо никуда двигать, то такой проблемы нет.

Не готов пока предложить конкретный интерфейс, но идея такая. Распределитель памяти должен либо возвращать указатель на расширенный блок памяти, либо просто неудачу (например nullptr), если это сделано быть не может. Вызывающий код во втором случае просто выполняет всё то же самое, что делается сейчас: выделяет новый блок и перемещает элементы туда. Написать более высокоуровневую обёртку поверх такого примитива будет несложно. И учитывая, что все системные распределители пишутся на C, реализовать им такой примитив будет несложно.

Victor Dyachenko, 6 декабря 2016, 15:54
Да, и, конечно, под это дело необходимо будет видоизменить/расширить текущий интерфейс аллокаторов, чтобы контейнеры могли явно выражать, что они хотят: новый блок памяти или расширить старый.

yndx-antoshkka, 7 декабря 2016, 12:55
Разработчик libstdc++ сейчас продумывает механизм, позволяющий делать нечто подобное http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0401r0.html.

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

Другие подходы скорее всего не будут работать на современных имплементациях malloc/new, которые как правило аллоцируют блоки одного из предопределённых размеров и просто не могут расширять проаллоцированный блок за пределы этого предопределённого размера.

Другие подходы могут так же негативно повлиять на вычислительную сложность работы с контейнером, на что комитет не пойдёт.

Victor Dyachenko, 7 декабря 2016, 13:39
Спасибо за ссылку, но она немного о другом. Возможность узнать реально выделенный размер и возможность "подрастить" выбеленный блок - это ортогональные вещи.
Основная идея в моём комменте выше - дать возможность создателям контейнера декларировать свои намерения. Если в конкретном случае расширить нельзя, то не страшно - будет просто существующее поведение. Но если запрос будет удовлетворён, то получим существенный прирост скорости и не огребём проблем с безопасностью исключений при перетаскивании существующих элементов. Сложность работы с контейнером с точки зрения удобства никак не пострадает, а вычислительная будет не хуже чем сейчас, а в некоторых случаях гораздо лучше.

P.S. Через вашу ссылку нашёл более близкое предложение: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3495.htm

yndx-antoshkka, 7 декабря 2016, 16:42
Victor Dyachenko, ваша идея требует от разработчика контейнера std::vector, при нехватке мета, пытаться увеличить размер выделенного блока на 1 элемент:

if (capacity == size) {
    if (try_realloc(size + 1)) return;

    ptr = allocate (size * 2);
    capacity = size * 2;
}

Если вы создадите вектор на 2049 char и будете постепенно вызывать push_back ещё 2047 раз, то realloc вызовется 2047 раз. Это может дать серьёзное замедление производительности.

Либо разработчик контейнера будет пытаться вызвать realloc для в два раза большего объема памяти, и realloc всегда будет возвращать новый блок.

if (capacity == size) {
    ptr = reallocate (size * 2);
    capacity = size * 2;
}

В этом случае, мы ничего не достигли, это аналогично вызовам new+move+delete. При этом придётся переместить логику new+move range+delete внутрь std::allocator_traits.

Сравните со случаем, когда аллокатор просто будет честно возвращать размер блока:

if (capacity == size) {
    ptr = allocate (size * 2);
    capacity = get_size_from_alloc(ptr);
}

Если вы создадите вектор на 2049 char и будете вызывать push_back ещё 2047 раз, то мы даже не зайдем внутрь if. Это будет ощутимо быстрее. При этом, на современных имплементациях libc, оба подхода будут выдавать абсолютно одинаковые результаты.

Более того, используя подход "вытаскиваем информацию из аллокатора" можно будет написать функцию realloc, работающую с любыми аллокаторами. А вот из функции realloc не получится сделать нечто, достающее истинный размер блока из аллокатора.

Victor Dyachenko, 7 декабря 2016, 17:36

ваша идея требует от разработчика контейнера std::vector, при нехватке мета, пытаться увеличить размер выделенного блока на 1 элемент:

Почему это? Что мешает расширить на то же значение, на которое расширяет текущая реализация? Почему именно 1?

yndx-antoshkka, 7 декабря 2016, 19:56

"Почему это? Что мешает расширить на то же значение, на которое расширяет текущая реализация?"

Вариант расширения в 2 раза рассмотрен сразу после первого примера, в том же сообщении.

Victor Dyachenko, 7 декабря 2016, 22:05

Либо разработчик контейнера будет пытаться вызвать realloc для в два раза большего объема памяти, и realloc всегда будет возвращать новый блок.

Вот тут не понял, из чего следует такое поведение?

При этом придётся переместить логику new+move range+delete внутрь std::allocator_traits.

Не нужно этого делать. Логика перемещения остаётся в контейнере!

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

Похоже, надо пример написать, чтобы меня поняли правильно.

void push_back(T v)
{
    if(size() == capacity())
    {
        size_t new_capacity = ...;
        if(extend(space_ptr_, new_capacity))
        {
            // удалось расширить
            capacity_ = new_capacity;
        }
        else
        {
            // расширить не получается выделяем новый блок; перемещаем данныеж
        }
    }
    space_ptr_[size_++] = v;
}

P.S. Ничто не мешает добавить сюда возможность аллокатору сообщать, сколько он реально выделил и использовать это значение. Это ОРТОГОНАЛЬНОЕ предложение, можно делать и то и другое.

yndx-antoshkka, 13 декабря 2016, 15:03
Victor Dyachenko, могу помочь с proposal на тему realloc, если хотите. Но у меня нехорошее чувство, что в комитете ваша идея будет воспринята в штыки.

Victor Dyachenko, 14 декабря 2016, 16:09
Спасибо, давайте попробуем. Набросал рабочий код, демонстрирующий идею + прикрутил фичу из p0401 - аллокатор может сообщать, сколько он реально выделил.

Текст лучше напишу на русском для начала (с английским у меня не очень...) Дальше, наверное, удобнее будет общаться через e-mail. На какой адрес прислать набросок?

Victor Dyachenko, 1 февраля 2017, 14:13
Опубликовал:
https://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/AeL6Q35t1j8
https://github.com/2underscores-vic/articles/blob/master/realloc4cpp/realloc4cpp.md

yndx-antoshkka, 1 февраля 2017, 15:34
мои 5 копеек:

• необходимо описать ситуацию, когда передаётся new_size меньше чем прошлый размер. Это ключевой плюс вашего предложения, т.к. предложение от Jonathan Wakely не может никак улучшиить ситуацию с shrink_to_fit(). Ваше же предложение сможет в ряде случаев выполнять shrink_to_fit() без переалллокаций и копирований.
• Приведите ссылку на http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3495.htm и приведите небольшое сравнение двух предложений
• возможно стоит добавить noexcept ?
• стоит передавать "сurrent block size as for allocator::deallocate()". Для некоторых аллокаторов это позволит быстрее делать ``resize_allocated`.

Дедлайн для новых предложений - ближайшая пятница (оффициально дедлайн 2017-02-06, но было скинуто предупреждение что дедлайн скорее всего наступит в пятницу).

Лично я бы рекомендовал не торопиться (скорее всего на ближайшем заседании обсуждать будут в основном только С++17), дождаться отклика на std-proposals и скрестить вашу идею с идеей Jonathan Wakely.

Victor Dyachenko, 1 февраля 2017, 15:55

• Есть в примере https://github.com/2underscores-vic/articles/blob/master/realloc4cpp/realloc4cpp.cpp. Стоит отдельно описать текстом?
• ОK
• noexcept, как мне кажется, тут лишний - не такая это тривиальная операция. И чем он тут кардинально поможет, как, допустим, в случае со swap или move-операциями?
• Тоже склоняюсь к этому.

Да, подождём откликов с std-proposals. Сам Jonathan Wakely добавлен список рассылки.

Еще попросил бы Вас присылать замечания по использованию английского, если что бросилось в глаза. С ним у меня туго... :-[

yndx-antoshkka, 1 февраля 2017, 21:52

• да. В код редко заглядывают в простых случаях
• noexcept позволит генерировать более компактный код - компилятор не будет генерировать код свёртки стека на случай исключения. Учитывая что метод resize_allocated скорее всего будет вызывать extern функцию, компилятору noexcept тут сильно поможет.

Дмитрий, 1 апреля 2017, 12:54
Теоретически есть 4 варианта - расширение памяти вперед, освобождение памяти спереди, расширение памяти назад и освобождение памяти сзади.
Освобождение памяти в обе стороны возможно во всех случаях и даст следующие гарантированные преимущества:

1. Возможность реализовать эффективные shrink_to_fit() и pop_front() у вектора, без переаллокации памяти.
2. Оптимизировать удаление элементов, расположенных до середины вектора. Например при удалении второго элемента из вектора в 100 элементов, достаточно сдвинуть первый элемент на вторую позицию и вернуть занимаемую первой позицией память системе, а не сдвигать 98 элементов назад, как реализовано сейчас.
   Расширение памяти возможно только если есть свободная память до/после. Но расширение даже на один элемент гораздо эффективнее переаллокации, поэтому требование увеличения размера вектора в 2 (или 1.5) раз при расширении памяти можно исключить. Если не влезает двойной размер, можно расширяется на столько, сколько возможно, даже на 1 элемент.
   Расширение памяти в обе стороны даст следующие преимущества:
3. Возможность реализовать эффективный insert(begin()) у вектора (в некоторых случаях) без переаллокации памяти. Если есть свободная память до вектора - достаточно расширить ее назад и вставить элемент.
4. Оптимизировать вставку элементов до середины вектора. Например при вставке элемента во вторую позицию вектора из 100 элементов, достаточно расширить память назад, и сдвинуть первый элемент назад, а не сдвигать 98 элементов вперед.
5. Оптимизировать вставку в конец вектора, у которого capacity() уже равна size(), но есть свободная память после блока вектора.
   Конечно, необходимо всё продумывать, добавить анализ доступного для выделения объема и т.д., но если подойти к решению данного вопроса комплексно, в общем случае производительность работы с памятью может увеличиться многократно без каких-либо телодвижений со стороны программиста.

Ватенов Артем, 24 февраля 2018, 18:10
Эта оптимизация должна дать очень значительное ускорение, и повысить энергоэффективность с++ приожений, т.к. std::vector и std::string самые используемые контейнеры. На с++ просто не бывает кода без них.
realloc обсуждают уже ни один год. Но ничего не меняется. И здесь инициатива застопорилась. В стандарт проходят куда более сложные, и менее важные вещи...
Еще вектор/строки должно ускорить приравнивание capacity() к _msize(), т.к. память выделяется блоками и capacity обычно получается меньше. Из-за этого переаллокация происходит раньше, чем фактически возможно.