Array of structures vs Structure of arrays

по какому искать надо, по тому и суй. хоть так сделай.

struct User
{
  int id;
  int something;
  float zhopa;
};


struct Users
{
  std::unordered_map <int, std::shared_ptr <User> > by_ids;
  std::unordered_map <int, std::shared_ptr <User> > by_something;
  std::unordered_map <float, std::shared_ptr <User> > by_zhopa;
};

:)

structure of arrays - локальность данных лучше

По идее - наоборот, а вообще всё исходит из того, как эти данные читать. Если последовательно по id, money, и тд - то да, если по юзерам - но нет.

спасибо! мне важно, чтобы программа не вылетала при больших количествах id.

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

как? как может опухнуть то чего нет?

мне важно, чтобы программа не вылетала при больших количествах id.

«Больших» — это сколько? Есть вариант хранить записи в СУБД, чтобы снять ограничения по оперативной памяти и обеспечить надежную работу с диском (так называемый acid).

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

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

тоньше! ок?!

ну не на столько большие... что бы использовать СУБД.
на/с диска планируется запись/чтение уже готовых структур.
каждому id соответсутсвует:

5 vector<double> // size 4096
3 vector<double> // size 100-1000
1 vector<vector<double>> 4096x100
и всякая мелочь.

есле id ~100 -> crash.
пока не отследил, когда вылетает.
или при «overflow» of id, или при передаче этой структуры в основной поток через connect.
для GUI используется Qt.

если упрощать.

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

ну и вообще как хранилища данных по пружине - тексты -> иерархии-> даги->сети произвольные->наборы кортежей (чьё упрощение таблица) и как менеджить таблица

ставший общераспротраннёный подход таблица это набор записей/кортежей

или таблица(а точнее гиперкуб :) ) это упорядоченные наборы координат на различных осях

Грубо говоря, удаление/добавление элементов в вектор делает все ранее взятые указатели/ссылки/итераторы на элементы этого вектора недействительными. Может быть, в этом проблема?

http://users.ece.utexas.edu/~adnan/pike.html

сразу выделяю(создаю) X id c нулевыми значениями, тоесть проблем с память не должно быть [так бы вылетало сразу].
у меня нет remove. есть только add(который перезаписывает нули реальными значениями или добавляет id в конец).
с remove (или сдвигами) и двойными векторами такую схему бы не использовал.
+ я вообще сделал «вброс» сюда, что бы узнать, так вообще нормально[правильно] создавать[представлять] структуру[класс].
спасибо за внимание!

Какое решение лучше, зависит от задачи, которую ты решаешь.

добавляет id в конец

push_back ?

в консоле push_back().//ранее
в GUI(Qt) append().//последнне время
но они на crash нe влияют, так как используются очень редко.
в основном перепись нулей при add.
p.s. бывают случаи crash при добавление через push_back? (интересно на будущее)

push_back() может приводить к переносу всех хранимых элементов в новый участок памяти, и следовательно делать все ранее взятые указатели/ссылки/итераторы на элементы этого вектора недействительными. Подробнее тут: http://stackoverflow.com/questions/6438086/iterator-invalidation-rules

С Qt-шными контейнерами не знаком, комментировать не берусь.

но они на crash нe влияют, так как используются очень редко.

Как раз при «id ~100» ? ;)

Мне просто очень интересно как мыслят люди програмируюшие на c++, какие решения они предпочитают и как это аргументируют.

Кто тебе сказал, что они мыслят?

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

SELECT User.FirstName, User.LastName FROM User WHERE User.RegistrationDate > 2014-02-26

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

Это уже давно пора понять, что когда балаболке задаёшь конкретный вопрос, аля «Реальные юзкейсы» - она тот час же пропадает. Совпадение - не думаю.

бывают случаи crash при добавление через push_back? (интересно на будущее)

Хм. Crash происходит не из-за push_back как такового, а из-за того, что вектор ведет себя совсем не так, как думает о нём автор программы. Ну то есть автор программы не учитывает свойств того же push_back, и в результате его программа имеет серьезные изъяны (вплоть до того, что крэшится).

в основном говорю программе: посчитай ... для id от 1 до 50(зарезервивованые add) [нули] --> посмотрел на результаты.
и вот когда id от 1 до 120 (например). crash
редко --> неее... давай еще немного --> тоесть 51-60. (через add как push_back в vector).
как то так...

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

Типичное проявление того, о чём я неоднократно говорил. Блаболка всегда уклоняется от конкретных вопросов и конкретных ответов. Балаболка всегда юлит и не отвечает прямо.

Задам ещё раз свой вопрос. Где основание твоего высера? Кукаретинг вида «это итак понятно», «я так сказал» и прочие куллстори - мне не интересны. Не можешь - иди кукарекай с соседями по парте.

В чём твоя проблема? Не фортануло с «делать»? Ну придерись к пунктуации на худой конец. Зачем же так явно сразу на дно?

учитывает свойств того же push_back

Это не свойство push_back, а свойство аллокатора.

reserve(total_free_ram) так же в помощь.

Нормальная тачка и нормальный аллокатор так же решают эту проблему. Хотя не на нормальной тачке дефолтный аллокатор итак не работает, поэтому только аллокатор.

Crash происходит не из-за push_back как такового.

согласен, что как его(soft) написать так оно и будет работать. а правильность написания зависит от знаний автора.
пока у меня только два «постоянных» crash. приходится обходить.
вот появилась идея (пока писал). --> если id больше 100. считать и добавлять по 50... может все будет ок.

Это не свойство push_back, а свойство аллокатора.

Обоснуй. Вот тебе для затравки:

23.2.4.3 - vector modifiers

void push_back(const T& x);
void push_back(T&& x);
.....
-3- Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

Жду от тебя сслыку на Стандарт, где указано, что в зависимости от свойств аллокатора «all the iterators and references before the insertion point remain valid» даже если «reallocation happens».

приходится обходить.

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

включал както valgrind. вместо 10 сек для одного id 5 минут(оr less) расчет едет...(может изза valgrind или Debug-mode)
умножаем на 100... и не факт что краш сработает.
хотя можно поиграться... посчитать один id... и записать его over 100 раз...
будем испытывать!

вместо 10 сек для одного id

Ох. Что там так долго считается?

Это маленькая часть...

reallocation
If no reallocation happens, all the iterators and references before the insertion point remain valid.
If no reallocation happens
all the iterators and references before the insertion point remain valid.

Тут написано, что если нет реалокации, то всё работает. Значит рушит ссылки реалокация, а не push_back().

Жду от тебя сслыку на Стандарт, где указано, что в зависимости от свойств аллокатора «all the iterators and references before the insertion point remain valid» даже если «reallocation happens».

Причём тут стандарт? Стандарт описывает аллокатор, который тут и подразумевается - дефолтный аллокатор.

Сам по себе push_pack() никак ссылки не рушит - это следует из стандарта. Т.е. я целиком и полностью прав.

Далее уже идёт второе моё утверждение про то, что этого можно избежать - это так же следует из стандарта:

Рушит их аллокатор. Если же моя реализация аллокатора гарантирует сохранение ссылок после реаллокация, либо вообще её отсутствие, то у меня всё работает и стандарт тут не при делах.

Давай ещё раз, а то вдруг слишком сложно. Нарушение ссылок - это свойство аллокатора. Причём свойство дефолтного аллокатора, описываемого стандартом. При этом стандарт позволяет не использовать этот аллокатор. Т.е. все ремарки, которые следуют из дефолтного аллокатора не имеют силы, когда дефолтный аллокатор не является обязательным, а поведение его наследовать стандарт не требует.

Все эти ремарки к аллокатору как таковому отношения не имеют. Поэтому валидности ссылок после реаллокации ничего не мешает.

А за жалкие попытки съехать с «Это не свойство push_back, а свойство аллокатора» на «all the iterators and references before the insertion point remain valid» даже если «reallocation happens».» в приличном обществе выставляют за дверь. В следующий раз за такую херню я просто буду констатировать твой обсёр, а не потакать тебе в твоём юлеже.

начни с питона или если нет оснований_к_фобии паскаля/фортрана -

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

Я к тому, чтобы на время тестирования заменить настоящие расчеты упрощенными. Например, уменьшить размеры массивов, по которым у тебя длительные циклы бегают.

Во втором варианте возникнут большие проблемы, если ты захочешь отсортировать готовый список юзеров по какому-либо критерию

Аноним/Царь(?) я с в̶а̶с̶ тебя «тащусь» :)

если valgrind тормозит, используй address sanitizer

Тут написано, что если нет реалокации, то всё работает. Значит рушит ссылки реалокация, а не push_back().

Вовсе на значит.

Причём тут стандарт? Стандарт описывает аллокатор, который тут и подразумевается - дефолтный аллокатор.

Стандарт описывает stl.

Рушит их аллокатор.

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

Нарушение ссылок - это свойство аллокатора.

Это твои фантазии, в стандарте такого не написано.

почему? я же могу написать итератор который будет показывать сразу на весь срез by index?

и передать его в std::sort например

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

спасибо за вопрос.

http://users.ece.utexas.edu/~adnan/pike.html

номер поскажешь?

я гдето писал о «обмазывании памятью»?
извините, не осилил весь текст.
фобий нет. использую матлаб. когда там все работает [медленно], переношу на плюсы. почему не фортран etc? у меня нет конкретного ответа, что было под рукой... тем и пользуюсь.

structure of arrays - локальность данных лучше

По идее - наоборот, а вообще всё исходит из того, как эти данные читать. Если последовательно по id, money, и тд - то да, если по юзерам - но нет.

интел имеет возразить

Keeping separate arrays for each structure-field keeps memory accesses contiguous when vectorization is performed over structure instances. AOS structures require gathers and scatters, which can impact both SIMD efficiency as well as introduce extra bandwidth and latency for memory accesses.

Although it may seem more logical to organize data in Array of Strutures (AoS), this organization makes it extremely difficult to access the memory for reads (gather) and writes (scatter). This prevents many optimizations by the compiler, most notably it often prevents efficient vectorization.

не все сразу. и это (~10 секунд) уже достаточно.
на самом деле сейчас менее 10. но больше 3-4.
+ если будет не антипаттерн, до 1 секунды всеравно не опустится.
я же не буду писать о каждой выигранной секунде. округлил и порядок.
главное вместо 10 секунд не пиcать 10 минут.

Ну вот, для SIMD таки да. Спасибо за ссылку

Совсем балабол поплыл.

Вовсе на значит.

Тут чёрным по белом написано:

If no reallocation happens, all the iterators and references before the insertion point remain valid.

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

Т.е. типичное враньё.

Стандарт описывает stl.

Стандарт не определяет операцию «реалокация», поэтому естественно за неё считает то, чем она и является в любой имплементации.

Там не сказано, кто их рушит.

Сказано - реалокация. Чётко и ясно.

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

Не может. Конпелятор ничего не может делать с памятью, потому что память аллокатора.

Стандарт никак не определяет ни понятие «реалокации» ни когда она происходит. Определяется только одно - откуда берётся память, а память берётся из аллокатора.

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

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

В целом типичное поведение нулей. Нихрена не знаешь? Кукарекай про конпелятор про который нуль так же не знает ничего.

Это твои фантазии, в стандарте такого не написано.

В стандарте не написано ничего этому противоречащего. Вернее всё, что написано косвенно это подтверждает.

Сказано - реалокация. Чётко и ясно.

У тебя явные проблемы с восприятием текста.

Стандарт не определяет операцию «реалокация»

Вот-вот. Вместо этого стандарт определяет, *когда* реаллокация происходит: «Causes reallocation if the new size is greater than the old capacity». И определяет, что можно полагаться на валидность ссылок/итераторов *если* реаллокации не было. Как ты отсюда высосал свюю бредятину про свойства аллокатора — остаётся загадкой.

обратите внимание, там таки говорится про:

The SOA form does come at the cost of reducing locality between accesses to multiple fields of the original structure instance (thus increasing TLB (Translation Look-aside Buffer) pressure for example).

но предлагается в таком случае использовать Array-Of-Structure-Of-Arrays (AOSOA)

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

Не согласен.

Насколько я вижу у тебя там:

vec a[100500], b[100500], c[100500];//

for (int i = 0; i < V.size(); ++i) {//так для каждой из 100500 "пар" abc?
	if(i > 1) V[i] = f(V.at(i-2), V.at(i-1),a,b,c);
	else 	  V[i] = i;
}

Выкати свою f() которую ты считаешь и данные на которых бенчишь и результаты вычислений. Я попробую в меньше секунды.

Я б тоже хотел посмотреть на f()

Конпелятор ничего не может делать с памятью, потому что память аллокатора.

Компилятор, основываясь на формально выведенных из стандарта заключениях, применяет достаточно агрессивные оптимизации. Вот тебе живой пример: https://lwn.net/Articles/342330/

Из dereference указателя компилятор делает вывод что указатель валиден, и опускает провернку на null.

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

Разумеется первый. Второй - тонкое извращение нужное только ради cache locality на проходах по отдельным характеристикам пользователей (поиск или аналитика) - о нём думать нужно ТОЛЬКО когда точно знаешь что в этом боттлнек, и я даже в этом случае реализовал бы его параллельно основному контейнеру с пользователями, только для нужных полей и использованием более подходящих структур данных чем вектора.