Комментарии 57
В таком случае не очень понятно зачем брать интерфейс именно vector в качестве отправной точки и менять семантику, называя вектором то, что в мире плюсов вектором не является.
Возможно, что для тренировки пользователей библиотеки и их способности вчитываться в документацию.
Вот тоже сразу бросилось в глаза. Доклад интересный, но может сложиться ложное впечатление "меняем стандартный вектор на иммутабельное творение автора, и здравствуй безопасная многопоточность".
У меня почему-то не возникло с этим проблем, потому что логика была такая: вам нужен вектор с дешевым копированием, вот он immer::vector. То есть интерфейс в виде методов именно от ветктора, однако под капотом другая структура данных. Вроде как посмотрев доклад я бы и не ожидал drop-in replacement для std::vector.
Интерфейс от вектора предполагает, что он ведет себя как вектор. И то, что автор начинает с листов, потом сравнивает с вектором, но ограничивает требования только работой с итераторами тоже вносит путаницу.
Плюс комментраии типа «игнорируйте строгую математическую сложность» — тоже не радуют.
В плюсах std::vector является тем чем вы считаете оно является, immer::vector не обязан быть таким же. В том что его назвали vector есть логика, это не ассоциативный неупорядоченный контейнер с random access доступом — т.е. математично это вполне вектор. Возможно есть более удачное имя, если есть идеи я думаю всегда предложить его автору через issue на github. Возможно еще придется придумать название для immer::map и immer::set.
В плюсах std::vector является тем чем вы считаете оно является, immer::vector не обязан быть таким же. В том что его назвали vector есть логика, это не ассоциативный неупорядоченный контейнер с random access доступом — т.е. математично это вполне вектор.
В плюсах то что Вы называете «вектором» называется std::deque.
А std::vector гарантирует что данные лежат в памяти последовательно и это существенно используется.
storing the data in contiguous chunks of 2BL elements. By default, when sizeof(T) == sizeof(void*) then B=BL=5, such that data would be stored in contiguous chunks of 32 elements.
Судя по всему immer::vector в с++ называется deque.
Думаю потому что затраты времени на операции у него ближе к вектору, чем к списку.
Flux приехал в мир C++?
P.S. в чём такие красивые диаграмки рисуют?
Если не нужен интероп с С и прочими частями, которые ожидают последовательного размещения в памяти — то, конечно, подробные реализации контейнеров — отличный вариант упростить жизнь и себе, и компилятору.
Ну и у плюсов(как экосистем) есть проблема с поддержанием обратной совместимости с условным "стандартом 98 года", потому довольно тяжело идут нововведения, особенно в такие фундаментальные сущности как std:: vector, что, снова, позволяет Rust и подобным быть намного более гибкими.
то до курка просто не дотянешься
Нет, если продолжать аналогию, то там просто предохранитель стоит. Кроме того всем на входе зачитали технику безопасности и табличку unsafe поставили.
до курка просто не дотянешься
Нет, просто на курок кто-то от души плюнул, поэтому первый раз или два ты инстинктивно отдёрнешь палец. Потом, правда, быстро привыкнешь лезть в это в скафандре.
Rust в плане иммутабильности вроде бы ничем особым от C++ не отличается, или я чего-то не понимаю. Вектор в расте такой же как вектор в плюсах, мутабельные данные, используйте .clone() чтобы это было иммутабельно. В C++ автор этого доклада сделал библиотеку immer которая типа должна поддерживать иммутабельность эффективнее чем .clone(). В расте вроде тоже можно найти библиотеку которая делает аналогичную структуру данных.
В Rust совершенно другая концепция — проверка корректности совместного доступа к памяти на уровне компилятора.
Иммутабельные данные — это скорее про Haskell.
Так там по-умолчанию все данные подразумеваются иммутабельными если явно не указано обратного. Так что оно by design использует эту концепцию.
Концепция автора немного в другом. Раст не даст вам создать две мутабельные ссылки на вектор, например, так что вам нужно будет решать эту проблему: например вы думать как безопасно расшарить эти данные чтобы вас borrow checker не ругал (через interior mutability с рантайм костами, например) или вы будете использовать .clone(). В обоих случаях получается как в плюсах или геморно (но безопаснее чем в плюсах) или медленно. У раст есть свой crate для immutable data structures, который насколько я понимаю решает аналогичную проблему (https://docs.rs/im/14.2.0/im/). Т.е. автор предлагает использовать подход с меньшим геморроем и более оптимальный чем обычный .clone()
Ну вот давайте сравним. Одна и та же операция set.
C++: https://sinusoid.es/immer/containers.html#_CPPv2NK5immer6vector3setE9size_type10value_type
Rust: https://docs.rs/im/14.2.0/im/struct.Vector.html#method.set
В C++ надо обязательно писать так: v = v.set(index, value)
В Rust можно написать так: v.set(index, value), а освободившееся возвращаемое значение используется чтобы вернуть прошлое значение ячейки.
Почему такое различие в API? Потому что Rust может проверить, что других ссылок на v не осталось, а C++ — нет.
Я так понимаю, функциональность этого Vector из im для раста и обсуждаемого "вектора" из C++ все ж не эквивалентна. Насколько я понимаю, то, что делает вектор из im — это реализует implicit sharing для хранимых данных а-ля Qt, с lazy cloning. Это не то же самое, что иммутабельность самого вектора, что обеспечивает обсуждаемый в статье "вектор" из C++. Продемонстрированная вами разница в API обусловлена главным образом этим. То есть если этот вектор из im поместить в контейнер с interior mutability, то ожидать, что он не будет меняться, нельзя. Но я так понимаю, что это нормально, так как изначально цель его создания была совсем другая.
Почему такое различие в API? Потому что Rust может проверить, что других ссылок на v не осталось, а C++ — нет.
Вы предполагаете что immer добавили immutable API из-за ограничений (точнее отсутствия оных) C++, я думаю что может да, а может и нет. Я думаю что у функционального стиля могут быть свои фишки.
У вашего замечания мне кажется есть зерно, но по моему немного в другой плоскости, с чем то с чем я дискутировал комментариями выше.
В rust ничего не мешает взять и написать let mut, мутабельность там в принципе возможна, и, конечно, активно используется. Корректность совместного доступа обеспечивается компилятором с помощью borrow checker'а.
Рассматриваемые же структуры данных вообще не требуют писать let mut при их использовании. Они изначально потокобезопасны, без всяких borrow checker'ов. За счёт несколько меньшей производительности, да (но не таких тормозов, как если бы каждый раз копировался весь массив).
В терминах обсуждаемой библиотеки, в Rust нет необходимости разделять иммутабельные структуры и их transients: обе сущности спокойно живут под одним и тем же именем. И возможность так делать даёт именно что borrow checker.
мутабельность там в принципе возможна
Скажем, в плюсах даже с его иммутабельными данными почти наверняка возможна магия
#include <iostream>
#include <vector>
int main()
{
unsigned n;
std::cin >> n;
using Vec = std::vector<unsigned>;
const Vec vec;
// vec.push(n); // так - ошибка компиляции
const auto* cvecptr = &vec;
auto vecptr = const_cast<Vec*>(cvecptr);
for (unsigned i = 0; i < n; ++i) {
vecptr->push_back(n);// а так - нормально
}
std::cout << vec.size() <<std::endl;
return 0;
}
В расте такое разве что с unsafe провернуть возможно, если не вовсе только со внешними байндингами к тем же плюсам.
Как вариант иммутабельных структур наверное можно привести кучку gc-арен на расте, которые выделяются лениво раз и больше не меняются.
За счёт несколько меньшей производительности
Ржавый Arc тоже не бесплатный, но в сравнении с оверхедом плюсов наверняка дешевле. Ну, и ниже сбросили там ржавую вариацию списков и и всяких деревьев. Ваша точка зрения понятна.
Вы хотели сказать: такая магия возможна, но это UB. Компилируется и выполняется. В данном примере даже корректно (на определённом компиляторе при определённых флагах и т.д).
Согласен по сути, уточнил бы что код с UB не соответствует стандарту C++, а потому не является репрезентативным примером.
Проблема этого определения в том, что код на C++ визуально неотличим от кода с UB. Помимо этого можно заметить, что количество серьёзных программ, написанных на C++ пренебрежимо мало.
Не хватает сравнений производительности с std::vector и с std::vector с мьютексами в реальных случаях.
На scala эти ваши иммутабельные структуры данных (не только Vector) заметно проигрывают мутабельным по скорости. Мне не понравилось.
Я пришёл к решению использовать мутабельные структуры, но оставлять их изменения лишь в месте, где структура создаётся, например. При совместном многопоточном доступе просто используется только чтение, но не запись, тех же мутабельных структур данных, иногда через иммутабельные адаптеры. Обмен между потоками реализуется какой-либо передачей сообщений, да хоть через Future, а не изменением состояния.
Подход rust'а с проверкой доступа при компиляции, опять же, менее затратен в рантайме (вообще не затратен).
Интересно, есть ли более-менее реальные примеры, где полная иммутабельность структур данных оправдана?
Как я понял посыл в том чтобы упростить код программы. Автор по сути говорит, смотрите, если вы будете использовать данные by value, вы сможете вот так упростить код вашей программы. А если вас расстраивает что вы будете копировать большие коллекции, то вот вам оптимизация в виде immer.
Если сложность работы с mutable типами вас не очень парит, то и смысла видимо нет. Я смотрел доклад какое-то время назад и мне концепция показалась интересной чтобы попробовать где-нибудь.
Что нашел по ссылке с github-а
public.sinusoid.es/misc/immer/reports
Не хватает сравнений производительности с std::vector и с std::vector с мьютексами в реальных случаях.
Автор просто взял похожее название (по-моему зря) — сравнивать с std::vector смысла никакого нет, конечно же std::vector будет производительней.
Интересно, есть ли более-менее реальные примеры, где полная иммутабельность структур данных оправдана?
Базы данных, например. Изоляция транзакций и всё такое.
Обычно это решается так:
1) Один поток (который thread) на игровую логику и рендер (и похожие задачи, где надо всегда знать все состояние мира), что медленно, особенно на процессорах с низкой тактовой частотой, но большим количеством ядер.
2) Двойная/тройная буферизация всего состояния мира (во всяких контер-страйках это не проблема, т.к. там постоянно меняются только переменные позиций игроков, что есть всего несколько килобайт.
3) Всяческие замысловатые синхронизации с блокировками, что есть сложно для реализации и более подвержено багам, чем остальные варианты.
Так майнкрафты как-то так и пользуются данными. На джаве вероятно это несколько сложнее было реализовано из-за сборки мусора, а во всяких портах и клонах такое цветет и пахнет (Veloren, например).
3d сканер строящий модель поверхности
Неужели у вас получилось иммутабельные структуры использовать так же быстро, как и мутабельные? Я пробовал в т.ч. и на всяких алгоритмах триангуляции — иммутабельные структуры были медленнее на полпорядка-порядок.
Ну просто так подставить иммутабельную структуру вместо мутабельной и получить ускорение действительно не получится, будет в разы медленее :)
Я делал ровно наоборот — подставлял мутабельную взамен иммутабельной и получал ускорение.
Но если изначально проектировать систему под иммутабельность данных
Это как? В неком алгоритме мне нужна функциональность таблицы. В scala тогда были иммутабельные и мутабельные treemap и мутабельный hashmap (позднее появился и иммутабельный hashmap). Пишем код на иммутабельных treemap — он явно тормозит, задействуем (мутабельный) hashmap — становится получше. Мутабельный TreeMap несколько быстрее, чем иммутабельный. Конечно, эксперимент не слишком чистый (hashmap вместо treemap всё-таки), но и mutable.Buffer вместо Vector как-то слишком быстр. Наверно, мои случаи как раз не те, в которых можно иммутабельность задействовать без потерь.
Но, в конце концов, на текущем железе нет ничего проще, чем выполнить команду mov, архитектура железа располагает к мутабельности, но не иммутабельности.
Конечно, эксперимент не слишком чистый (hashmap вместо treemap всё-таки),
Ну дык у Вас есть и «чистая» версия: Мутабельный TreeMap несколько быстрее, чем иммутабельный
У нас одна из основных структур данных, к слову — иммутабельный hashmap. Отлично работает.
v1 = v0.push_back(threadId);
или
v1 = v0.set(0, threadId);
не «поломают» контейнер, будучи вызванными из нескольких потоков? Я вроде бы понимаю, что мы в разные потоки передаем условно разные «копии» одних и тех же данных. Но вроде как clone или move без изменений не меняют ничего в памяти. Просто это выглядит так, будто остался один шаг до реализации software transaction memory
Симпатичные блок-схемы, через какую программу такие возможно создать?
Сверхсовременные иммутабельные структуры данных