середины + быстрое добавление в конец и вроде в моих бенчмарках LinkedList оказывается достаточно хорош.
Но подумал что если поэкономить аллокации то может ещё лучше будет
Сам лист нет, но вот системный аллокатор, в принципе, может иногда тут удачно такое делать
А с вектором сравнивали? А то вектор может оказаться быстрее. 😉
jemalloc умеет
с ним и сравнивал) Пока ещё пытаюсь понять как правильно бенчмаркать задачу, как приблизить бенчмарк к чему-то реальному.
Хорошо бы знать примерное соотношение и паттерны последовательности операций, и производить их на тестах примерно так же. 🙂
Ну это понятно. Проблема в том что паттерны относительно непредсказуемы и зависят от использования библиотеки) Примерное поведение понятно, но это не точно
Тогда в первую очередь тестируют рандом + граничные и краевые случаи для оценок лучшего/худшего поведения. 🤷♀️
Вы всё-таки были правы... Я всё перепутал и использовал как элемент 'большой' тип, сейчас заметил что в реальном коде используется 'маленький' (всего 24 байта). Поправил бенчмарк — стал выигрывать Vec+drain_filter или аналог. Видимо при больших размерах структур линкед лист выигрывает за счёт того что он вообще не копирует элементы, а при маленьких проигрывает из-за кэша/большего кол-ва аллокации/хз.
Если большой элемент не влезал (или едва влезал) в кеш-линию, то для вектора префетч фактически переставал работать и всё скатывалось к тому же количеству промахов, что и для списка.
Обсуждают сегодня