Comments 46
Ну и при чём тут С++? К С++ данная оптимизация не применима хотя бы в силу того, что между классом и структурой нет никакой разницы (private/public проигнорируем).
Если уж размер указателя имеет столь большой вклад в размер объекта, то эффективнее использовать собственный аллокатор и вместо указателя на объект хранить индекс этого объекта в собственном диспетчере памяти (будет 4 байта, независимо от архитектуры. Или два байта или три или полтора).
Если уж размер указателя имеет столь большой вклад в размер объекта, то эффективнее использовать собственный аллокатор и вместо указателя на объект хранить индекс этого объекта в собственном диспетчере памяти (будет 4 байта, независимо от архитектуры. Или два байта или три или полтора).
Действительно в C++ многие проблемы решаются прозрачно. Поэтому я описал C# — там многие тонкости скрыты. В С++ на практике в Поиске Пути только лишь использование массивов простых типов вместо массивов структур дало выигрыш в скорости на 0.6%. Это крохи. Но в основном я произвел это разделение для того, резервировать в памяти не 1 большой блок для 1 массива, а несколько более мелких. Слишком уж проблема с нехваткой памяти за горло взяла. Возможно это — специфический случай, но, думаю интересный.
В таком случае в определенных кейсах вы наборот замедлили, например, последовательный доступ (в C++ варианте). Не стоит оно того. Если уж хочется не один большой кусок памяти, а несколько поменьше — есть std::deque
Согласен — многое зависит от кейса. И если ресурсов много — труд программиста всегда ценнее. Возможно при нехватке ресурсов для определенного программно-аппаратного комплекса (например мобильное решение) следует обращать внимание на время доступа к памяти в тактах, попадание в кеш и т.п. Одна из конструкций, которую я использовал — специализированная хеш таблица. Там размерами и количеством блоков памяти можно управлять. При разбиении структуры мы действительно получаем фиксированное число и не можем просто упралять количеством и размерами выделяемях блоков памяти. Все действительно зависит от задачи и ситуации.
Не совсем понял как это относится к c++. Насколько я помню struct и class в с++ занимают одинаковое количество памяти.
В С++ также имеет место выравнивание в структурах и классах. Например если процессору легче взять из памяти за 1 раз 8 байт ( зависит от архитектуры ) то желательно сразу взять то, что нужно или пригодиться потом. Если класс или структура будут иметь нерелевантные данные ( потерянное место ввиду выравнивания или же соседнее ненужное вданное время поле ) или же выравнивание будет несоответствующее — у процессора уйдет больше времени на доступ к памяти. Плюс кеш. В итоге массивы простых данных работают быстрее. Хотя С++ намного более гибок и является системным языком программирования, даже выбор/создание аллокатора и хранилища требуют хорошего понимания платформы, т.е. кеша, режима доступа к памяти и т.п. Не задумываясь об этом иногда можно быстро израсходовать ресурсы системы.
Не совсем понял на что вы отвечаете? Естественно cpu возьмет из памяти сразу cache line. Естественно примитив занимает меньший объем памяти и с большой долей вероятности в кэш попадет больше значений. Только вот sizeof(struct)=sizeof(class). В c# совершенно все по другому скорее всего, т.к. class содержит кучу информации помимо данных.
Внутри структур/классов поля выравниваются. Это приводит к появлению «пустот». Если поля хранить в отдельных массивах, выравнивание внутри массивов не производится. Суммарно массивы полей занимают меньше памяти чем один массив структур. Возможно эффект небольшой, ведь компилятор оптимизирует код, но при нехватке ресурсов и определенной ситуации может быть полезен.
Т.е. в статье 2 шага. 1 — от классов к структурам. Если в С++ дизайн правильный, тут эффекта может не быть или он будет небольшой 2-я часть — разбиение массива структур на массивы их полей. Тут можно немного выиграть и на С++.
Т.е. в статье 2 шага. 1 — от классов к структурам. Если в С++ дизайн правильный, тут эффекта может не быть или он будет небольшой 2-я часть — разбиение массива структур на массивы их полей. Тут можно немного выиграть и на С++.
Вам поможет #pragma pack(push, 1)
В выравнивании и экономии памяти поможет. Но скорость доступа будет меньше чем при разбиении на массивы полей. И если не ошибаюсь меньше и при доступе к полям структуры — ведь их выравнивают для оптимизации доступа.
За счет чего, простите?
Железо. В общих словах — обращение к данным, не находящимся по кратным разрядности адресам требует дополнительных операций процессора.
А как вам поможет при этом массив?)
Не проще ли написать Struct в котором все поля будут идти в правильном порядке (без padding)?
Не проще ли написать Struct в котором все поля будут идти в правильном порядке (без padding)?
Если в определенном месте алгоритма, например каком-то цикле нужна только часть полей структуры, а не она вся, массив тут оптимальнее. Но выигрыш тут правда небольшой — у меня на С++ в релизе с оптимизацией на скорость выигрыш составил порядка 0.6% по времени. Но разбиение конечно усложняет код и это серьезный аргумент в пользу структур. Дело случая.
А так, — я как-то стараюсь создавать структуры с полями в 32 байта — не сильно напрягает, но упаковка лучше.
А так, — я как-то стараюсь создавать структуры с полями в 32 байта — не сильно напрягает, но упаковка лучше.
С чего это? Покажите методику вашего теста пожалуйста. И желательно опишите железо.
Алгоритм Поиска Пути. Тест простой — разница во времени между началом и концом вычислений для одинаковых путей. Т.е. 0.6% — не только время доступа, но и другие внутренние операции. Цифра грязная, но соответствует только одному изменению — разбиению на массивы полей.
Железо — Intel i7, 4 Gb RAM. Но тестировал в режиме x86 ( 32 бита ). Тестировал много раз, так как долго отлаживал.
Не являются ли постоянные малые положительные показания доказательством хотя бы малого, но положительного эффекта? Может я зацикливаюсь и что-то не учел?
Железо — Intel i7, 4 Gb RAM. Но тестировал в режиме x86 ( 32 бита ). Тестировал много раз, так как долго отлаживал.
Не являются ли постоянные малые положительные показания доказательством хотя бы малого, но положительного эффекта? Может я зацикливаюсь и что-то не учел?
Ну это не тест вовсе.
Давайте попробуем написать полноценный benchmark. Мне кажется там проблема, что у вас данные не влазили в cacheline. и скорее всего ваши 0.6 это просто погрешность)
Давайте попробуем написать полноценный benchmark. Мне кажется там проблема, что у вас данные не влазили в cacheline. и скорее всего ваши 0.6 это просто погрешность)
Ок. Мне самому интересно. Пока я вижу только выигрыш, так как он полностью соответствует теории. Т.е. если я только лишь улучшаю структуру данных и после этого имею выигрыш при каждом запуске, это скорее всего наведёт на мысль о взаимосвязи, ведь погрешность бы скакала и отрицательные значения компенсировали бы время в случае если ничего не улучшилось.
Но все-же более интересен другой вопрос. Если дело идет о широком использовании, надо тестировать точнее, увереннее и на разных платформах. А то уверенность что тут я выиграл не дает гарантии что на другой платформе или алгоритме не будет проигрыша. Т.е. более понять вклад в цифру разных факторов.
Но все-же более интересен другой вопрос. Если дело идет о широком использовании, надо тестировать точнее, увереннее и на разных платформах. А то уверенность что тут я выиграл не дает гарантии что на другой платформе или алгоритме не будет проигрыша. Т.е. более понять вклад в цифру разных факторов.
Если уж заговорили о выравнивании, то нужно сразу сказать и о порядке объявления данных-членов. Порой, можно существенно уменьшить размер структур, просто переупорядочив данные-члены. Если кратко, то наиболее компактным будет расположить данные от типов максимального размера к типам минимального, тогда будут минимальные затраты на выравнивание «пустыми» байтами.
Откровенно говоря не хотел усложнять статью — больше текста и сам запутаюсь. Там по ссылкам есть на эту тему касательно C#. А программисты С++ более вероятно знают проблематику. Если в записи много полей различных типов — можно поиграться. А так — хотелось просто обратить внимание на влияние выравнивания.
Потом как ни крути — доступ в случае массивов полей более благожелатален для кеша чем через структуры. Пусть в С++ выигрыш небольшой, но он есть. Т.е. я как-то эти два преимущества ( отсутствие выравнивания и доступ к однотипным данным ) вместе рассматриваю.
Потом как ни крути — доступ в случае массивов полей более благожелатален для кеша чем через структуры. Пусть в С++ выигрыш небольшой, но он есть. Т.е. я как-то эти два преимущества ( отсутствие выравнивания и доступ к однотипным данным ) вместе рассматриваю.
Говорю только за С++.
Доступ к полям «благожелательнее», чем к элементам массива. Потому что адрес поля известен статически, а адрес элемента может потребоваться вычислять в рантайме (если компилятор не оптимизирует). Выравнивание всегда можно настроить, чтобы поля были так же плотно расположены, как и в массиве. С точки зрения кэша абсолютно без разницы, будет считанно 4 элемента массива или четыре переменные, расположенные друг за другом.
А вообще, если на C# или Java или других высокоуровневых языках начинают заниматься байтоёбством, то это означает лишь то, что язык для данной задачи был выбран неудачно, либо пришло время немного переписать часть программы на другом языке.
Доступ к полям «благожелательнее», чем к элементам массива. Потому что адрес поля известен статически, а адрес элемента может потребоваться вычислять в рантайме (если компилятор не оптимизирует). Выравнивание всегда можно настроить, чтобы поля были так же плотно расположены, как и в массиве. С точки зрения кэша абсолютно без разницы, будет считанно 4 элемента массива или четыре переменные, расположенные друг за другом.
А вообще, если на C# или Java или других высокоуровневых языках начинают заниматься байтоёбством, то это означает лишь то, что язык для данной задачи был выбран неудачно, либо пришло время немного переписать часть программы на другом языке.
Тут вопрос доступа к структурам в массиве и к полям в массиве. Т.е. и там и там массив.
Откровенно говоря меня иногда С# бесит, особенно когда нужно байтокамасутрится :-) В особенности отсутствие битового представления числа… Тут уж как говорится если требуется так, то уже… Просто на вопрос — куда в C# деваются 73% памяти на 64 битной системе без заглядывания вовнутрь не обойтись.
Но история началась с части кода на С++, после изменения которого возникла нехватка памяти. Вот и пошло по цепочке. Отоптимизировал код на С++ по полной ( даже кажется это уже чистый С получился ). Потом залез в C# глазами С++ — ника. И напоролся на такое обжорство…
Откровенно говоря меня иногда С# бесит, особенно когда нужно байтокамасутрится :-) В особенности отсутствие битового представления числа… Тут уж как говорится если требуется так, то уже… Просто на вопрос — куда в C# деваются 73% памяти на 64 битной системе без заглядывания вовнутрь не обойтись.
Но история началась с части кода на С++, после изменения которого возникла нехватка памяти. Вот и пошло по цепочке. Отоптимизировал код на С++ по полной ( даже кажется это уже чистый С получился ). Потом залез в C# глазами С++ — ника. И напоролся на такое обжорство…
Вроде бы и интересно и полезно, но выводы и советы какие-то в стиле Капитана.
Эцсамое. Тут не так давно NFX-овский Heap рекламировали. Да и комментариях предложена ещё пара вариантов. Есть мнение, что вполне применимо к вашему случаю, притом позволяет не так сильно издеваться над структурами данных.
При разработке где это возможно нужно использовать структуры, а не классы.
Надо убрать слово возможно, потому, что возможно почти везде, а вот нужно не везде!
Просто передайте ваш массив на обработку в метод и посмотрите на результат.
В замене обьектов на массивы простых данных зарылась еще одна собака — векторизация и более адресный доступ к памяти.
Про векторизацию помнил, но уже капнуть глубже просто не успел. Тут тоже как понимаю возникают варианты и в каждом случае мы можем получить тот или иной эффект. Но для более простых процессоров эффект от замены должен быть ощутимей.
Я сейчас честно в ступоре. Векторизация вроде бы делается для однотипных операции, причем независимых. С трудом могу представить ситуацию, когда вам нужно ко всем полям добавить 1) Ну и собственно сборка векторов не бесплатна, не всегда это дает прирост производительности.
Дело в том, что при обращении только к части полей, например только трем полям Lengths, NodesFrom и NodesTo структуры Road в случае их расположения в отдельных массивах можно получить более оптимальное использование кеша процессора. Использование всех преимуществ кеша зависит от алгоритма доступа к данным, но в любом случае выигрыш может быть заметным.
Не понял про преимущество третьего варианта, если у вас три разных массива аллоцированы в произвольных регионах памяти, как вы получите преимущество при чтении из кеша процессора? Кеш-лайн L1, L2 — допустим 64, 128 байт, общий размер несколько мегабайт максимум. Чтение из одного кешлайна даст вам преимущество как раз при использовании массива Road, где поля одной дороги лежат друг за другом, а не разнесены по памяти.
В примере структура короткая. Если алгоритм оперирует только частью полей (на оопределенном участке), разделение дает преимущество в особенности для длинных структур и при доступе, где вероятность работы с соседними значениями велика. Например даже если рандомно обращаться только к одному или нескольким полям при их разносе в массивы вероятность обращения к физически соседним полезным данным выше (я не имею в виду расстояние, но то, позволит ли оно например вместиться в кеш). Различия могут быть как заметными так их может и не быть — зависит от алгоритма.
В Вашем случае будет явное преимущество при не-разбиении если нужна вся структура целиком и поля в ней «хорошо» выровнены.
В Вашем случае будет явное преимущество при не-разбиении если нужна вся структура целиком и поля в ней «хорошо» выровнены.
Расходы на использование структур в C# нулевые, особенно если правильно ими пользоваться. Пишем небольшой атрибут:
И вуаля:
Хотя доступ по выровненным данным все равно лучше, чем экономия 3 байт. Ну а случае особой битовой магии всегда есть LayoutKind.Explicit с ручным расставлением необходимых смещений. Энивей, всегда можно добиться необходимой оптимизации не вводя кучу магических констант и несвязанных между собой явно массивов.
[StructLayout(LayoutKind.Sequential, Pack = 1)]
public struct RoadPacked
...
И вуаля:
Хотя доступ по выровненным данным все равно лучше, чем экономия 3 байт. Ну а случае особой битовой магии всегда есть LayoutKind.Explicit с ручным расставлением необходимых смещений. Энивей, всегда можно добиться необходимой оптимизации не вводя кучу магических констант и несвязанных между собой явно массивов.
Расходы памяти в этом случае — нулевые. А вот расход времени доступа увеличивается. Вопрос возникает когда чего-то начинает резко не хватать. Вот тогда и решаем чем жертвовать. Если же место есть и процессор не перегружается — можно и не думать об оптимизации.
Единственный кейз, когда у нас массив структур, а мы постоянно из 1000 полей берем 1-2. Только это уже проблемы архитектуры, что ненужные поля засунули куда попало.
Да — 1000 полей — явный кейс. Или когда полей штук 20, берем 2,, а в массиве несколько десятков миллионов записей, Плюс вероятность доступа к соседним элементам высока.
Значит неправильно сделана структура, в которой 20 полей. Структура упаковывает единый неделимый набор данных. Если мы начинаем работать кусками структуры, то мы неправильно изначально объединили данные. Недаром в том же шарпе best practice обязывает структуры быть неизменяемыми.
Есть такая стилистическая фигура — гипербола…
Да — 1000 полей — явный кейс
Есть такая стилистическая фигура — гипербола…
Тут и кроется неудобство. Лучший дизайн может требовать рассмотрение структуры включая все поля, как одно целое. Алгоритм же в одной части может использовать 2-3 поля, в другой части другие поля. Выделить эти 2-3 поля в отделбную структуру а остальные в другую? Т.о. получим промежуточный вариант. Если так идти далее -придем к делению на примитивные данные. Деление — это уже не дизайн, а оптимизация.
Т.е. два конца палки — что упрощает работу программиста — усложняет работу железа. Лучшая практика — это для большинства случаев. Ведь си-шарп не системный язык и действительно надо делать структуры неизменяемыми. Это когда начинаешь. А деление на примитивы — частный случай оптимизации когда переписывать на С++ трудоемко, менять железо — ресурсоемко. Оптимизация, это когда логически уже работает и надо не создать, а улучшить для лучшего переваривания железом.
Т.е. два конца палки — что упрощает работу программиста — усложняет работу железа. Лучшая практика — это для большинства случаев. Ведь си-шарп не системный язык и действительно надо делать структуры неизменяемыми. Это когда начинаешь. А деление на примитивы — частный случай оптимизации когда переписывать на С++ трудоемко, менять железо — ресурсоемко. Оптимизация, это когда логически уже работает и надо не создать, а улучшить для лучшего переваривания железом.
Т.е. два конца палки — что упрощает работу программиста — усложняет работу железа.
Известное утверждение, не переставшее от этого быть ложным. За примерами ходить не надо — посмотрите на Rust, который изначально был сделан, чтобы достичь и того, и другого. Скорее нужно сказать «ускорение работы без длительного предварительного размышления над проблемой приводит в говнокоду». Тут уж я соглашусь, сколько обычно пилятся всякие ЯП — раз-два и готово, и сколько пилился раст, сколько раз пересматривалась архитектура и т.п. То есть чтобы сделать и быстро, и красиво, нужно сначала очень напряженно подумать. А обычно заморачиваться не приходится — зачем, если мы все красиво спрячем за фасадом абстракций, а во внутренности никому лезть не надо. Потом оказывается, что надо, но это уже обычно не проблема тех, кто писал, и они забивают.
Что шарп — не системный язык, я согласен, однако не согласен с тем, что на шарпе нельзя писать быстрые и эффективные приложения. Вот, Андрей DreamWalker выступал на конференкции этой весной, вдохнул в эту мою мысль новую жизнь. И вполне убедительно смог её аргументировать.
Мне так повезло, что на C# приходится решать многие задачи, для решения которых лучше бы подошел С++. Что мне очень нравится, что в C# уровень можно выбирать в широких пределах. Если надо заоптимизировать — можно глубоко залезть, даже до unsafe. А если надо еще глубже — пожалуйста, можно часть кода написать на нативном С++ и подключить как unmanaged DLL.
Касательно Rust — очень интересный подход в его развитии.
Кстати и на С++ так можно написать, что медленнее старого бейсика пойдет. Если не ошибаюсь даже просто с new/delete код на С++ можно сделать в разы медленнее чем на C#. И говнистость кода — вещь относительная. Иногда код — как бомж некрасивый, но свое дело делает четко (конечно лучше его привести и к хорошему виду). Эти вопросы наверное надо рассматривать с позиций менеджмента и дизайна.
За инфу о лекциях Андрея спасибо. Смотрю как раз запись. Тематика интересная.
Касательно Rust — очень интересный подход в его развитии.
То есть чтобы сделать и быстро, и красиво, нужно сначала очень напряженно подумать. — уже тут зарыто много труда (чтобы упростить работу железа).
Кстати и на С++ так можно написать, что медленнее старого бейсика пойдет. Если не ошибаюсь даже просто с new/delete код на С++ можно сделать в разы медленнее чем на C#. И говнистость кода — вещь относительная. Иногда код — как бомж некрасивый, но свое дело делает четко (конечно лучше его привести и к хорошему виду). Эти вопросы наверное надо рассматривать с позиций менеджмента и дизайна.
За инфу о лекциях Андрея спасибо. Смотрю как раз запись. Тематика интересная.
. — уже тут зарыто много труда (чтобы упростить работу железа).О чем и речь:)
Кстати и на С++ так можно написать, что медленнее старого бейсика пойдет. Если не ошибаюсь даже просто с new/delete код на С++ можно сделать в разы медленнее чем на C#.
Строго говоря, new в шарпе и так быстрее ибо это просто инкремент указателя на размер объекта, а не поиск свободного блока. Ибо на GC возлагается задача иметь всегда последовательный набор возрастающих свободных адресов. Так что что объект создать, что локальную структуру — требуется одно и то же мизерное количество операций. Вот delete да, будет быстрее, чем просмотр кучи и её переупорядочивание.
За инфу о лекциях Андрея спасибо. Смотрю как раз запись. Тематика интересная.
Всегда пожалуйста :)
Sign up to leave a comment.
Назад в будущее – Декапсуляция