Pull to refresh

Comments 31

Второй вариант, это тоже реализация программы в стиле ООП, то есть с точки зрения подхода разработки они совершенно одинаковые.

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

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

Начали за здравие, а закончили очередным повторением data locality( а скорее даже нытьём ). Я уж думал будут какие-то дельные предложения

Это ж обычная и старая проблема хранения данных во внешней памяти, только перенесенная на RAM. Построчно (= по-объектно) или поколоночно (= массивами)? Или разбивать по 10К строк и их хранить поколоночно (привет orc, parquet и иже с ними)? Колонки сильно лучше жмутся и выше локальность при доступе к колонкам, ну а если поиск нужен и рандомная вставка/удаление, и нужно какое-нибудь b-дерево? Такие же трейд-оффы и здесь, поэтому от паттерна доступа к данным и нужно отталкиваться, когда по массивам распихивать внутренности объектов, когда — сами объекты, когда по спискам/хэштаблицам/деревьям.
Алгоритм компилятор не оптимизирует. Но, надо сказать, современные компиляторы могут очень многое. Агрессивные инлайн-подстановки, раскрутка/конвейеризация циклов, аффинные преобразования на вложенных циклах, удаление мертвого кода, и тд. Не стоит забывать и о процессорных оптимизациях в виде того же branch prediction.
Что-то мне подсказывает, что замена одного ArrayList на фиксированный массив даст большой буст и в «ООП»-варианте. А еще что-то подсказывает, что ускорение этой «data-driven» организации улетучится, когда будет задействовано сравнение со строками, ибо строковый буфер все равно лежит, скорее всего, в иной области памяти чем закешированный референс на инстанс объекта строки. Но мерить лень.
Замена ArrayList на просто массив не даст вообще ничего, посмотрите исходник ArrayList.
Ваша правда, согласен. По плюсовой привычке воспринял List как двусвязный нелинейный список. К тому же, все равно объекты лежат по ссылкам… А сразу представилось, что можно положить все объекты inplace в один непрерывный буфер и обойти тем самым прыжки по кэшу. Но про строки должно быть верно.

Т.е. в начале автор катил на старые негодные языки, а потом сам же и доказал, что дело в кривых ручонках самого программиста. Интересно.

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

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

TLDR: надо писать хороший код в первую очередь для людей и оптимизировать только то, что нужно оптимизировать. И всегда думать головой, что ты делаешь и зачем.

Так автор и предлагает, чтобы такими оптимизациями занимался ЯП:

Что если язык программирования предоставит нам структуру, ведущую себя как массив структур, но внутренне ведущую себя как структура массивов? Мы смогли бы программировать в обычном объектно-ориентированном стиле, удобном для людей, и при этом обеспечивать высокую производительность благодаря оптимальному использованию оборудования


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

Тогда объект будет содержать только ссылку на объект с массивами + индекс в этих массивах

Бог его знает, выстрелит или нет, но если кто-то заморочится и сделает такую оптимизацию (кажется, нечно подобное можно прямо в существующих языках и компиляторах попробовать) — будет любопытно посмотреть на бенчмарки и удобство использования
Насколько я знаю, что-то в новых языках нет единой модели вычислений, кажется, что делают некоторый MVP, а потом обсыпают фичами по запросам программистов. Теория вычислимости идёт мимо.
В моих мечтах аннотации выставлять не надо: программист или думает в традиционной процедурной парадигме, или с точки зрения data flow, одновременно получается не шибко хорошо. Data flow на текстовое представление программ ложится не шибко хорошо, значит распараллеливание должен брать на себя компилятор или VM на основе локальности данных и графа выполнения.

Примерно такое уже скоро будет в java, проект Вальгалла называется, массивы объектов вместо массивов ссылок на объекты

А я правильно понимаю, что Вальгалла - это такой реверанс в строну C#?

Похоже на то, вторая фаза Вальгаллы как раз специализация дженериков

Появляющиеся сейчас DOTS-системы в игровых движках как раз направлены на решение этой проблемы, разворачивая на этапе компиляции многочисленные экземпляры специальным образом оформленных ООП-объектов в совокупности массивов. Правда, пока пользоваться этим не очень удобно, таки да.

Статья неплохая в плане понимания работы кеша, но странно акцентируется внимание на ООП
Сам ООП абстрактен, то, что он реализуется через ссылки на куче — особенности нынешней реализации, не исключено что возможны другие.
Собственно тот же быстрый пример тоже написан на ООП, просто с учетом особенностей работы компьютера.

В копилочку DOD решений обычно еще приводят ECS — подход для игр, когда данные и методы их обработки разделены ради повышения производительности.

"Быстрый пример" написан на ООП потому что в Яве принудительное ООП.

Скорее всего, имелось ввиду, что по сути реализовали те же самые объекты, но на массивах. Поле "имена", Поле "цвета" и т.д. Т.е. Если тебе нужен доступ к полю "Имя" и "Цвет" у объекта "a", то в классическом ООП пишешь a.name a.color, в реализации на массивах names[a] colors[a]. То же ООП, но не массив структур, а структура массивов.

Авторский вариант кода всего на 60-80% производительнее выданного ООПшным компилятором. То есть компилятор всё-таки загнал данные в кэш процессора, причём того же самого уровня, что и автор "вручную" — иначе разница была бы более 3-х раз.


Похоже, что вся разница объяснима не "ловкими" манипуляциями автора с кэшем и раскладкой данных вручную, а оверхедом по занимаемой памяти ООПшными объектами.

То есть компилятор всё-таки загнал данные в кэш процессора, причём того же самого уровня, что и автор «вручную»

Компилятор этого не делает.

а оверхедом по занимаемой памяти ООПшными объектами.

Так и статья об этом. Смысл в переупорядочивании данных объекта таким образом, чтобы не читать лишнее. AOS->SOA.
Первый концепт называется AOS (Array of Structures), второй SOA (Structure of Arrays).
У каждого свои плюсы и минусы. Еще один плюс SOA это возможность работать с векторыми инструкциями процессора (SIMD).
Из крутых фич компиляторов стоило бы напомнить, что Intel Compiler умеет сам автоматически преобразовывать одно в другое в вашей программе на этапе компиляции и получать нехилый выигрыш производительности.

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

Поздравляю, автор почти изобрел базу данных. Ждём статью про индексы.

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

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

Годные шарпы уже стали шустрее пусть и кривых плюсов?
https://habr.com/ru/post/266163/ — статья не новьё, но сильно сомневаюсь, что там кардинально что-то поменялось.

А плюсы тут при чём? Там тоже всё хорошо со структурами.

Тут проблема не в структурах, а в организации данных. Плюсы не имеют право на реорганизацию данных структуры. Если разработчик не умеет, его проблемы. Плюсы это язык профессионалов((С) Б. Страуструп), которые обязаны разбираться в железе. Либо писать на других языках, которые эту работу выполнят за них.

Но если быть до конца честным, то проблема организации данных есть и на шарпах. Достаточно поизучать вопрос внедрения ECS паттерна в Unity. Ведь ECS следствие DoD, который строится на иной организации данных. И ECS реализуется на плюсах куда проще, чем на шарпах. Просто потому, что плюсы позволяют управлять организацией данных на достаточно низком уровне.

Вот ради интереса решил проверить в VS 2019 с языком C#

Количество муравьев задал 100 000 000 чтобы видно было разницу.

Если создавать List муравьев то действительно затраты на пересчет занимают 719мс.

Если использовать второй подход и создать класс колонии с тем же количеством то подсчеты занимают уже 319мс. Вроде бы и очевидно что плюс.

Но!! Если мы будем создавать не лист а массив типа Ant[] antColony с таким же размером то пересчет по первому алгоритму занимает тадаа!!! 260-280 мс.

У каждого подхода есть свои плюсы и минусы. Панацеи не существует ни при одном подходе. Если получите прирост эффективности в одном то обязательно в другом месте это выродится в костыли которые и усложнят разработку и станут превратятся в последствии в страшный кошмар для поддержки. То есть как не крути а все равно все сводится к кривизне разработчика. Какие он инструменты и механизмы выбирает и каким образом применяет.

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


Во-первых, ничего не сказано про то, что в энтерпрайзе не всегда понятно какие будут запросы к структурам данных — сегодня одни, завтра другие, поэтому средний подход ориентированный на классы в целом имху выигрывает у ориентированного на данные подхода. Особенно по другим параметрам, которые больше ценятся в энтерпрайзе чем требования к скорости — стоимость и темпы разработки.


Во-вторых, в современном энтерпрайзе никто не хранит данные о муравьях в оперативке или даже на диске. Энтерпрайз — это базы данных, а значит: экстенты и коэффициенты заполнения страниц, Б-деревья для первичных индексов, а также индексы и индексы с включёнными столбцыми и обязательно статистики для прогнозатора — и конечно же здравствуй перестроение индексов и статистик в плане обслуживания. Никто не будет хранить в памяти всё это барахло, максимум что будет храниться — десяток муравьёв из колонии, взятый как пагинация второй страницы из десяти тысяч.


Всё вышесказанное не означает, что статья — фуфло, просто мир намного более сложнее устроен. Так если поставить в табличку задержек ещё и простой select — это будет на порядок больше обращения к диску и это тоже отдельный больной вопрос. Или вопрос маппинга ООП данных на реляционные.

Размеры колонии в бенчмарке не особо репрезентативны, поэтому результата между разными размерами не видно (отклонения 61-81% в рамках погрешности измерения).

Объекты размером 24 байта в занимают 240000 байт, что влезает даже в L1 кэш (там как раз 256 Кб).
То, что ДОП тут лучше чем ООП видно, что зачем приводоить список на 100,1000 и 10000 не понятно, там разницы нет. И не будет, даже если мы вейдем за пределы кэша. Т.к. если к данным обращаются один, то в любос случае придется ходить в память.

А вот если обращаться к каждому муравью много раз, то там сразу ощутите, какая будет просадка в размере сильно больше 10000.
Sign up to leave a comment.

Articles