LINUX.ORG.RU

структура из массивов с минимумом накладных расходов

 , ,


1

1

Издалека начну. Есть некий хитрый контейнер, который обходится итератором. Элементы контейнера - структура определенная юзером. В структуре может быть несколько полей (в идеале разных POD-типов, но можно ограничиться пока одним).

Теперь самое сложное - в разных элементах некоторых полей может вообще не быть, может быть просто поле типа T, а может быть небольшой массив (одномерный или двумерный), и это будет меняться в runtime. При этом накладные расходы на хранение всего этого безобразия должны быть минимальны, то есть решение вида

struct E{
  std::vector<T> a;
  std::vector<T> b;
  std::vector<T> c;
  ...
};

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

Нужно:

  1. Понять как это вообще можно сделать.

  2. Хороший интерфейс для доступа ко всему этому.

  3. Хороший интерфейс для задания структуры пользователем.

  4. Желательно, но не необязательно - прикрутить к этому какую то интроспекцию, то есть что бы хранились типы полей и имена полей (как массив строк и sizeof-ов).


Пока что придумалось такое - в структуре заводится

std::vector<char> data; // тут лежат все данные
uint8_t sz[N][2];       // размеры полей как массивов
uint16_t off[N];        // смещения различных полей в data

где Т - число полей (в итоге расход 4 байта на поле - с этим как то можно жить) и для каждого поля name делаются функции

T& name(int i=0, j=0);
void resize_name(int szi, int szj, T defval=T());

и то и то делается макросами, то есть для юзера задание структуры выглядит как

struct E{
CELL_TABLE(10); // задаем N
ADD_FIELD(0, double, a); // номер поля, тип, имя
ADD_FIELD(1, float, b);
...
};

а доступ выглядит как

I->a() ... I->b(1) ... I->c(0,2) ...

если индекс вышел за пределы массива генерируется ошибка.

Вопросы:

  1. какие тут подводные камни, что можно улучшить?

  2. как это вообще называется (лучше назвать)?

  3. как к этому малой кровью прикрутить интроспекцию? То есть я хочу иметь возможность в runtime снаружи узнать все типы полей, имена полей, размеры типов полей.

cast @KennyMinigun , @hobbit;-)

★★★★

Последнее исправление: AntonI (всего исправлений: 1)

для представления данных я бы взял какой-нибудь sqlite (+ json?) и снаружи определил бы методы их чтения и формирования.

olelookoe ★★★
()
Ответ на: комментарий от olelookoe

Нет, спасибо - не пройдет по производительности.

Да и тащить это все в проект не вижу смысла.

AntonI ★★★★
() автор топика
Последнее исправление: AntonI (всего исправлений: 1)

Для индикации наличия полей можно использовать битовые строки. В общем случае твоя задача не решается если не известны максимальные размеры объектов в том числе и массивов, а в противном случае кажется достаточно просто делать placement new над чем-то типа boost::variant на буферах максимального размера.

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

Ещё вот интересно, что ты подразумеваешь, под локальностью данных. То, что поля будут в одном буфере размещены, её достижению никак не поможет, на однопроцессорных системах так точно, а не неоднопроцессорных это можно решить с помощью аллокаторов и thread pinning.

pon4ik ★★★★★
()

Можно сделать структуру с разреженными векторами, например sparsetable из google sparsehash

annulen ★★★★★
()
Ответ на: комментарий от pon4ik

Для индикации наличия полей можно использовать битовые строки.

Можно, но это никак не поможет с размерами массива, а если размер массива хранить то битовая строка уже ненужна. Хотя конечно размеры массива для поля можно не хранить если поля нет, это сэкономит 4 байта… но усложнит код, думаю что 4 байта на поле я переживу.

В общем случае твоя задача не решается если не известны максимальные размеры объектов в том числе и массивов

Максимальные размеры по контейнеру или максимально допустимые? В исходном посте заложено ограничение 256х256, этого должно хватить.

placement new над чем-то типа boost::variant на буферах максимального размера.

Я таких слов не знаю но погуглю, спасибо.

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

Почему? Можно считать, что данные структуры небольшие и влезают в кэш. Если они будут размазаны по нескольким буферам, то локальность точно будет хуже. Очевидно один элемент всегда обрабатывается одним тредом.

AntonI ★★★★
() автор топика
Ответ на: комментарий от annulen

Эмм… да, как альтерантивная реализация если обход контейнера последовательный это тоже будет хорошо и интересно. Спасибо!

AntonI ★★★★
() автор топика

культурные люди делают хранение обьектов с переменным числом полей, значений и типов на списках. а не на массивах. массивы хороши только в одном случае - нужно компактное представление для маломеняющихся(по количеству записей) данных, идеально - число записей не меняется. как только данные начинают меняться активно(записи удаляются/добавляются) преставление в виде массива только тормозит.

alysnix ★★★
()
Ответ на: комментарий от alysnix
  1. если произвольный доступ производится чаще чем изменение (в моем случае на несколько порядков) то вектор лучше списка.

  2. Стандартный вопрос на собеседовании - что быстрее, 1000 вызовов std::list::push_back или 1000 вызовов std::vector::push_back ?

ЗЫ на самом деле список лучше вектора в двух случаях - активная вставка/удаление из середины с сохранением порядка следования объектов или если нужно что бы адрес объекта был неизменен. В остальных случаях вектор как правило лучше.

AntonI ★★★★
() автор топика
Последнее исправление: AntonI (всего исправлений: 2)
Ответ на: комментарий от AntonI

Почему? Можно считать, что данные структуры небольшие и влезают в кэш. Если они будут размазаны по нескольким буферам, то локальность точно будет хуже. Очевидно один элемент всегда обрабатывается одним тредом.

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

Да расположение их в одной странице памяти всех целиком, или хотя бы выравнивание по размеру страницы позволит сэкономить несколько кэш линий на этапе загрузки, но это такое себе преимущество. Вот если буфера находятся на разных numa нодах, тут да, могут быть не очень приятные последствия, но о5 же только на этапе загрузки в кэш.

Как делают обычно - горячие поля + указатель на остальные кладут в одну структуру, остальные в другую структуру. Так вот структура массивов - содержит именно hot части, объектов которые будут обрабатываться на одной итерации цикла. Как их подобрать и разложить - без очень пристального взгляда на сам цикл не придумать.

pon4ik ★★★★★
()
Ответ на: комментарий от AntonI

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

alysnix ★★★
()
Ответ на: комментарий от alysnix

Спасибо, кэп, ответ правильный;-) ТОлько вот стандартные аллокаторы в std устроены так, что вектор в этом случае будет гораааздо быстрее (поскольку аллоцирование - это долго). Это к вопросу о «культурных людях», данных данных с переменным числом элементом и массивах - можете считать меня некультурным но я в таких случаях таки обычно использую вектора…

AntonI ★★★★
() автор топика
Последнее исправление: AntonI (всего исправлений: 1)
Ответ на: комментарий от AntonI

Согласен он, лол. А надо то тебе чего? Не пойму почему ты в заголовке говоришь про локальность данных, а подразумеваешь экономию памяти. Но при этом в начале упоминаешь SoA, потом сам же от него отказываешься. Каша какая-то.

Тут надо либо труселя скидывать, либо крестик надевать.

pon4ik ★★★★★
()
Ответ на: комментарий от pon4ik

Если бы я четко знал что мне надо, я бы не спрашивал на ЛОРе а сделал то, что мне надо;-)

Вариант когда во всех элементах есть запас памяти на все поля не прокатывает однозначно. Что бы точно понять насколько будет важна локальность и пр. нужно будет делать профилирование, код пока не написан и тут можно только гадать.

Сейчас хотелось бы выбрать хотя бы такой интерфейс, что бы если мы через год уперлись в медленный доступ к памяти можно было поменять контейнер не переписывая все остальное, например на разреженные вектора как предлагал @annulen или еще на что то.

AntonI ★★★★
() автор топика
Ответ на: комментарий от AntonI

ну тут надо смотреть что там за «стандартные аллокаторы». поскольку это все на куче лежит, а если старый буфер заполнился, классикой(при простой реализации вектора) является захват буфера на удвоенное число элементов, переписывание туда данных из старого буфера(при этом все ссылки на старые элементы становятся невалидными), и записывание нового элемента. плюс есть уже запас на N новых. массив это по сути сжатый список. когда линки элементов выбросили, но сами элементы расположили в памяти последовательно. плюс в том, что произошло сжатие, поскольку линков уже нет, и можно обращаться по индексу. минус в том, что такое последовательное расположение надо поддерживать.

alysnix ★★★
()

Извиняй, если не совсем по теме…

Элементы контейнера - структура определенная юзером.

Но вот я при этих словах уже насторожился. :) Либо ты пишешь какого-то универсального убийцу 1С, либо пытаешься исправить чьи-то косяки проектирования (когда структуры не проработаны, и кто-то надеется, что пользователи сами всё поправят).

то есть для юзера задание структуры выглядит как

Ага. То есть «юзеры» — это не совсем юзеры, а всё-таки прикладные программисты, а ты им библиотеку делаешь? Если так, то я задам следующий вопрос: это для какого-то конкретного проекта, или ты собираешься эту библиотеку распространять как универсальную?

Я к чему клоню: если ты хочешь, чтобы что-то было мегауниверсальным, да ещё и быстро работало — так обычно не бывает. То есть да, всё, что ты написал, работать будет (только имей в виду, что макросы — вещь коварная и не прощают ошибок). Но вот насколько оно оправдано…

hobbit ★★★★★
()
Ответ на: комментарий от hobbit

Это для XFEM. Я отбивался как мог, но те кто пишут сами методы (расчет матриц жесткости и пр.) сказали «нам именно это надо!». То есть там и правда все вот так вот дышит и меняется…

Да, мелькнула мыль - я такого никогда не делал, а вдруг это еще где то понадобится? Я даже знаю где, для хранения и визуализации данных расчетов. Поэтому вопросы про интроспекцию…

А так то да, похоже на СУВТ;-(

AntonI ★★★★
() автор топика
Последнее исправление: AntonI (всего исправлений: 1)

вообще для подобной пурги(хранение произвольных структурированных данных) я сделал кастомный json, его парсер и генератор, плюс внутреннее представление на двусвязных списках. можно произвольно хранить структуры(списки именованных полей с данными), массивы(неименованные поля с данными), плюс скалярные типы - integer, boolean, string. если добаыть блобы, будет вообще типа субд. вот вам и нужно мастерить нечто такое. json придумали не просто так

alysnix ★★★
()
Ответ на: комментарий от AntonI

Ты можешь сделать какую-нибудь обёртку над tuple, которая будет определять состав «полей» (сам кортеж будет являться аналогом твоей структуры), а эту обёртку уже хранить в векторе. Тогда ты получишь, что требуется. Вроде

XMs ★★★★★
()
Ответ на: комментарий от pon4ik

placement new над чем-то типа boost::variant

Как по мне так сразу в глаза бросается что нужно использовать sumtype, даже удивлен, что только один человек предложил это. А вот насчет необходимости placement new я бы задумался. Если пользовательская структура имеет деструктор, то его нужно вызвать будет вручную. Как по мне в этом случае будет проще работать с типизированными данными, а не с буферов и банально использовать присвоение - там компилятор сам сделает что нужно и код будет проще.

yetanother ★★
()
Ответ на: комментарий от AntonI

Преждевременные оптимизации - зло. Вдвойне зло их применение повсеместно вместо хотя бы потенциально-узкого места.

SoA - не про контейнер как таковой, а про механизм доступа к полям и представление дескриптора объекта.

В случае AoS - дескриптором объекта является this, а ссылки на поля объекта есть смещения относительно this. Итерация по контейнеру с произвольным доступом достигается путём прибавления к указателю на текущий объект смещения последнего поля плюс его размер.

В случае SoA - дескриптором объекта, является его номер, в множестве объектов. А ссылка на поле является номером массива плюс дескриптор объекта. Хранение объектов в контейнере - невозможно, только их дескрипторов.

Пока объекты позволяют менять своё внутреннее состояние только через интерфейсные функции - интерфейсы самих объектов не придётся менять, т.е. бизнесс логика останется не затронутой, а способ доступа к полям - всегда можно инкапсулировать в этих методах, в случае перехода на SoA всегда можно сделать их force inline например. Но вот как спроектировать интерфейс описания классов что бы подходил под разные подходы - это задача не тривиальная, и трудозатраты на неё могут занять больше чем внушительная часть твоего проекта, особенно, если цель это zero cost этой абстракции.

pon4ik ★★★★★
()
Ответ на: комментарий от XMs

Не, я не понимаю. Если я сделал tuple, я выделил данные под ВСЕ поля, причем КАЖДОЕ поле это одна ячейка а не массив. Дальше что? Никакой оберткой это не вылечить…

Вариант с AoS тут на первый взгляд кажется более Ъ. Но то что мне придумалось (блоб по которому лазят свои функции) на первый взгляд проще, там вообще два макроса на один экран и все…

AntonI ★★★★
() автор топика
Ответ на: комментарий от hobbit

Но вот я при этих словах уже насторожился. :) Либо ты пишешь какого-то универсального убийцу 1С, либо пытаешься исправить чьи-то косяки проектирования (когда структуры не проработаны, и кто-то надеется, что пользователи сами всё поправят).

Либо реализует бинарный протокол определяющейся схемой, аля SBE например. Когда с сети приходит тип сообщения, его нужно сматчить со структурой, а потом, аккуратно расположить пакет в буфере который выделяется один раз на всё про всё, при том так, что бы доступ к отдельным полям был эффективен (т.е. не просто описать смещения к сырым данным в пакете).

pon4ik ★★★★★
()
Ответ на: комментарий от pon4ik

Либо реализует бинарный протокол определяющейся схемой, аля SBE например.

А можете накидать ключевых слов по этой теме для «погуглить»? У меня вырисовывается потребность в нечто похожем.

yetanother ★★
()
Ответ на: комментарий от pon4ik

Блин, вот вроде я все это знаю, но часть знаю как мутно (спинным мозгом), а что бы вот так все вместе четко сформировать сходу - так вообще не могу:-(

Сухой остаток (как я понял) - сделать как нить (условно пристойно) через интерфейсы что бы работало, а потом посмотреть и подумать/попрофилировать. В общем я тему создавал что бы обсудить - получилось, спасибо большое, проблема решена:-)

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

AntonI ★★★★
() автор топика
Ответ на: комментарий от hobbit

пытаешься исправить чьи-то косяки проектирования

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

Непонятно только, стоит ли все эти варианты собирать и под них заморачиваться, или оставить 2D массив как самое простое и универсальное решение?

AntonI ★★★★
() автор топика
Ответ на: комментарий от yetanother

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

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

pon4ik ★★★★★
()
Ответ на: комментарий от AntonI

интерфейс сначала напиши, потом будешь думать как представить внутри. что надо - добавить/удалить поле по имени, элемент по индексу, добавить/удалить запись(что вообщем-то тоже поле), взять число элементов в структурном обьекте, взять тип обьекта, удалить обьект и проч. также неясны требования по производительности и числу обьектов. одно дело когда их миллион, другое - не ограничено вообще.

alysnix ★★★
()
Ответ на: комментарий от alysnix

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

alysnix ★★★
()
Ответ на: комментарий от alysnix

Интерфейс я уже написал (см исходный пост), мне бы таки хотелось что бы он был реализуем при различных вариантах подкапотного устройства. Вроде можно сделать…

AntonI ★★★★
() автор топика
Ответ на: комментарий от AntonI

с маркдауном пока не разобрался пока так: CELL_TABLE(10); // задаем N ADD_FIELD(0, double, a); // номер поля, тип, имя ADD_FIELD(1, float, b);

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

ps: как тут вообще пост редактировать, я новичок тут

alysnix ★★★
()
Ответ на: комментарий от AntonI

А я поинтересоваться сугубо в целях

повышения образованности: как эта вся штука связана с XFEM? Что за такой произвольный набор полей?

Это пространственная сетка (ну или не сетка, если оно FEM) и в ней свойства материала записаны? Что за дополнительные массивы? Его какие-нибудь физические характеристики при фазовых переходах? Тогда их может быть конечное число (штуки 4) да и поди их можно вынести в отдельный массив или функцию.

Или все сложно-сложно?

sshestov
()
Ответ на: комментарий от alysnix

Можно в профиле установить дефолтом разметку lorcode или таки прочитать про маркдаун (там все просто, ссылка на хелп внизу, там же где кнопки «Опубликовать сообщение»).

Нет, это не реляционная БД. Совсем.

AntonI ★★★★
() автор топика
Ответ на: А я поинтересоваться сугубо в целях от sshestov

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

В зависимости от порядка аппроксимации на каждое поле может требоваться несколько значений (первая размерность массива).

В зависимости от схемы могут требоваться значения с нескольких слоев по времени (вторая размерность массива).

Сетка состоит из узлов, ячее, граней - некоторые поля ассоциированы с узлами, некоторые с ячейками, некоторые с гранями, некоторые есть и там и там (и там).

Ну и вишенкой на торте extended - некоторые поля в некоторых ячейках могут быть сильно раздуты (больше степеней свободы). Скажем моделируем распространение трещины, там где где трещины нет все просто (нет), там где трещина есть все сложно (совсем-совсем).

ЗЫ свойства материала на этом фоне ерунда, решается индексацией - слава Б-гу сетка конформная и нет никакого подсеточного сглаживания и пр. фигатени.

AntonI ★★★★
() автор топика
Последнее исправление: AntonI (всего исправлений: 1)
Ответ на: комментарий от AntonI

тогда зачем писать sell_table(10), add_field(…);

у меня для жисона сделано просто классы

Value = число, строка, null, Object, Array //значение

Pair = имя -> Value //именованное значение

Object = { Pair } //список именованных значений, возможно пустой

Array = {Value} //список просто значений, возможно пустой

вот на таких классах можно навернуть любую кухню с произвольно структрированными данными. типов тут всего пять. структуризация обеспечивается наличием Object, Array(что есть тип), можно еще свои добавить.

alysnix ★★★
()
Ответ на: комментарий от AntonI

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

alysnix ★★★
()
Ответ на: комментарий от AntonI

В зависимости от схемы могут требоваться значения с нескольких слове по времени (вторая размерность массива).

Т.е. получается вы в одном снапшоте сразу историю по времени тащите?

Сетка состоит из узлов, ячее, граней - некоторые поля ассоциированы с узлами, некоторые с ячейками, некоторые с гранями, некоторые есть и там и там (и там).

Все-равно вариаций в каждой точке весьма конечное число.

Ну и вишенкой на торте extended - некоторые поля в некоторых ячейках могут быть сильно раздуты (больше степеней свободы). Скажем моделируем распространение трещины, там где где трещины нет все просто (нет), там где трещина есть все сложно (совсем-совсем).

Наверное это стоило это рассказать в самом начале. А то по первому описанию граждане стали решать придумывать как строить БД или чего еще :)

sshestov
()
Ответ на: комментарий от sshestov

Т.е. получается вы в одном снапшоте сразу историю по времени тащите?

Нет, мы решаем например вместе уравнения упругости и уравнения фильтрации.

Все-равно вариаций в каждой точке весьма конечное число.

Да, не спорю. Но тащить шаблон с параметризацией по десяткам типов - плохая идея.

Наверное это стоило это рассказать в самом начале

Там стоит тэг с++, ИМНО этого достаточно:-) Объяснить что такое xfem стороннему человеку сложно, я и сам то до конца не понимаю…

AntonI ★★★★
() автор топика
Ответ на: комментарий от AntonI

если есть много много однородных данных, но иногда встречаются совсем неоднородные, то можно использовать вариант с расширением, типа - пусть надо хранить миллирад пар чисел, но там иногда встречается нечто большое(вот типа «трещины»). тогда надо хранить {тип поля, нечто}. нечто - union{struct{int,int}; *ExtendedData}; то есть по типу поля оно интерпретируется либо как стандартная пара чисел, либо как указатель ExtendedData, что хранится например в своем массиве. То есть наиболее массовые данные хранятся напрямую, нестадартные редкие в своих массивах или списках, и адресуются по указателю или ссылке. нестандартных данных может быть много разных, они по тегу определяются.

alysnix ★★★
()
Ответ на: комментарий от alysnix

Можно. Но здесь это неудобно, потому что исходно есть как минимум три типа элементов.

AntonI ★★★★
() автор топика

Ни Си, ни C++ не позволят решить эту задачу красиво для произвольных структур. И уж тем более так как в предполагаемом интерфейсе в посте.

Сдается мне что в реальности тут ни подобная premature optimization, ни даже вообще C++ в принципе, и не нужны.

lovesan ★★
()
Ответ на: комментарий от lovesan

Спасибо, Ваше мнение очень ценно для всех присутствующих, продолжайте держать в курсе.

O STL, С++, лиспе и пр. ништяках троллят там ===>

AntonI ★★★★
() автор топика
Ответ на: комментарий от lovesan

Я бы конечно спросил, что Вы знаете о критериях для кода в области в которой я работаю, но не буду - ответ как бы и так очевиден…

AntonI ★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.