Russian Qt Forum

Добрый день

Сцена имеет N объектов, каждый из которых по меньшей мере имеет Position (3 double) и Rotation (3 double). Однако "3 double" - это всего лишь "текущее значение", параметры хранятся в виде "анимационных кривых" (animation curves). Когда юзверь двигает "ползунок" на линейке времени, текущие значения Position и Rotation вычисляются из кривых, в рез-те объект двигается и/или вращается. Анимационные кривые - в принципе обычные контейнеры, данные хранятся в виде контрольных точек сплайна и/или тупо по кадрам (номер кадра + значение).

И вот вчера юзер (с гордостью) создал 102K объектов, и подозреваю, это далеко не предел. Правда они не анимированы, но и пустые кривые (с одной точкой сплайна) - уже 100Mb. Робкие попытки анимации 20 sec (с гораздо меньшим числом объектов) - уже 2-3Gb  (дальше просто боюсь смотреть). Вылетов нет (64-bit да и 8Gb стоит, просто "хватает"), но машина уже "убита", плохо реагирует на мышь и клаву.

Очевидно нужно как-то подкачивать данные с диска. Какую схему подкачки Вы можете предложить?

Спасибо

Какие же они большие. Большие данные сегодня начинаются с 10^15 байт

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

Пы.Сы. Еще можно поиграться со сторонними аллокаторами типа jemalloc (https://github.com/jemalloc/jemalloc) , mimalloc (https://github.com/microsoft/mimalloc).

Пример: память забита такими структурами

C++ (Qt)
std::vector<std::pair<int, double>> 

Ну или second = 3 double. И что я тут "оптимизирую"? Ну разумно попытаться отсечь неиспользуемый хвост/пул вектора, но это даже не вдвое. И даже не в полтора раза. Чисто технически рез-т может быть вполне достойный. Но для юзания разница примерно "с какого этажа падать - 8-го или 9-го", итог тот же.

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

Значит надо копать в сторону https://en.wikipedia.org/wiki/Memory-mapped_file

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

Опять же - что показывает профайлер?

То что и должен - память забита animation curves (контейнеры о которых писал выше). Бесполезно выяснять "а сколько" т.к. юзер всегда может создать в 10 раз больше. Или в 100. Ему достаточно ввести число. Др словами проблема в том что расход памяти стал совершенно неконтролируемым (со всеми вытекающими).

Неясно. Подозреваю что у вас проблема в реалоокациях которым надо копировать вектор. std::deque пробовали? Она хранит данные чанками и добавление не вызывает реаллокаций миллионов элементов.

а если animation curves в какую нибудь БД скинуть, и читать оттуда только актуальные данные?

Дека - хорошая вещь, но она здесь ни при чем. И оптимизация переаллокаций тоже не имеет отношения к теме. Проблема в том что (просто-напросто) данных слишком много  :) Да, это звучит странно - а вчера что, было мало? Ну в общем да. Обычно сцена заряжается данными из файла(ов), напр obj. fbx и др. А их надо откуда-то взять, прочитать. Просто так, руками, 100K объектов не создать. Но тут появилась новая фича типа "размножить по образцу" которая позволяет юзверю легким движением руки размножить N копий. Каждая такая копия конечно юзает оригинал, но какие-то свои данные (ну хотя бы Position и Rotation) у нее есть. Вот их-то и стало безумно много.

А вообще задача очень неплохая. Речь не идет о "памяти вообще", а только о достаточно конкретных и достаточно простых контейнерах, это реально

Что значит "много"? Доступ к элементам вектора не зависит от количества данных - он делается за константу. Если вы не делаете доступ, а что-то другое, говорите, что конкретно тормозит. "количество" данных в векторе тормозить не может. Может тормозить вставка, поиск, сортировка.

Тут ты не прав. Потому как если данные в твоем векторе засвопились, то доступ к ним не будет таким же быстрым, как если бы он был в оперативе, или более того в каком нибудь из кешей проца.

после того как отмапите себе 100GB файл, пишите свой аллокатор. Все стандартные контейнеры могут работать с кастомными аллокаторами.

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

Не понимаю каким боком тут аллокатор. К оператору [] он отношения не имеет, а подгружать контейнер целиком нет смысла, напр на кадре 100 будет обращение ко всем контейнерам по индексу 100, т.е. загрузим/перемелем все. Итог - свап в минус

Ждал подобного предложения :) Никаких аргументов "почему нет" привести не могу по той причине что никогда СУБД не занимался. Ну разве что

Мальчишество конечно, но все же  :)

"На родном языке" получится велосипед, называемый "своя СУБД", который будет работать не быстрее той же sqlite, но времени на разработку своего уйдет уйма и глюков с костылями наловится куча.

Вполне возможно. Но столь же вероятна СУБД в роли "коровы на бане", и не исключено что в конце-концов не устроит скорость или что еще. Кстати, я впервые слышу что, оказывается, есть СУБД (sqlite) которые работают медленно.

Ну хорошо, попробуем более конкретно. Есть 1 миллион анимационных кривых, нужно прочитать все их значения для заданного кадра. Какое время займет это при использовании СУБД (какой - Вам виднее) ?

Или совет дан чисто их общих соображений: данных много - значит СУБД (подозреваю что так  :))

Из личного опыта, SELECT запрос выполнится за 5-15мс, примерно столько же на тупой пробег циклом по всему миллиону записей, другая сторона медали, что тупой пробег мало кому нужен, а нужна генерация структур из БД.
Если не надо по полям этих структур в БД фильтровать, то можно через memcpy хранить просто бинарку и так же через memcpy в си-шные структуры десерелизовывать. Этот способ наиболее быстрый будет.
Если все же надо десерелизовывать структуры из полей, тогда время будет тратится на доступ к нескольким полям, будет медленнее, насколько относительно первого способа, я не скажу, могу прикинуть, что на 30-50%.

Хорошо, вот анимация "по кадрам"

C++ (Qt)
template<class T> Data;
struct CustomFrame {
 int m_frame;
 Data m_data;
};
std::vector<CustomFrame> theCurve;

Аргумент T или double или тройка double (координата), др варианты здесь не интересуют. Эл-ты хранятся в векторе по возрастанию m_frame. Чтение, запись, вставка и удаление реализованы с помощью lower_bound. Вектор может содержать любое кол-во эл-тов, напр для минуты анимации 1800 (30 fps). Разные вектора необязательно имеют одинаковые кадры (m_frame), хотя часто бывает и так.

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

1) Что в БД будет "полями" и что "записями"? Если я верно понял из написанного выше, то 1 кривая = 1 запись. Тогда что с полями? Одно поле = все данные одного вектора? И для чтения всех кривых по заданному кадру нужно "прогрузить" их все, каждую целиком? Это очевидно не вариант. Выходит поля должны быть кадрами, и надо сразу их все создать. Ну не знаю, их может быть много тысяч. И что если напр всего кадров 4K, а конкретная кривая имеет только 100? Все равно хранить все 4K?

2) Этот и след вопрос скорее из люботытства. В моем (наивном) представлении БД = нечто "стабильное". Типа "пришел утром и залогинился к своей базе". Но здесь др ситуевина: юзер открывает окно, указывает число размножаемых копий и диапазон времени - все, погнали, извольте создать базу с большим кол-вом полей. Так можна?  :)

3) Какую конкретно СУБД Вы бы порекомендовали (можно "настоятельно" :)), и что Вы вообще думаете о привлечении СУБД в данном случае? Напр

а) безусловно необходимо
b) возможно
с) та ну нафиг

?

Спасибо

1. Если m_frame это некий ID кадра, тогда его можно вынести в отдельное ключевое поле, все остальное (m_data) в бинарку серелизовать.
Тогда таблица будет примерно такого плана
Соот-но m_data должна уметь серелизовывать себя, если разные типы, то в таблицу можно добавить поле с типом в integer, по которому понимать куда десерелизовывать данные.

2. Не надо большое кол-во полей создавать, нужна одна таблица, куда запихнется вся эта серелизованная бинарка, одна запись - один CustomFrame, в транзакции и пакетным запросом на диск сбросится быстро, больше будет играть роль скорость диска, чем сама СУБД.

3. Для тестов можно взять sqlite, один нюанс, у нее запись блокирующая все БД, поэтому запись и чтение распараллелить не получится.
Распараллеливание возможно на постгресе, но он накладывает обязательство иметь полноценный сервер на машине, и настройка его конфига дефолтная довольно медленная. С MySQL не работал, но по отзывам она тоже не плоха.
Что сильно не порекомендую, это микрософтовское поделие mssql server, он еще хуже sqlite при вставке себя ведет (я в разделе БД тему создавал недавно).
PS: ну и для скорости надо выбирать из БД несколькими параллельными запросами, на select СУБД доступ не блокирует.
PPS: в моем прошлом проекте скорость работы с постгресом была на уровне 80-100к структур в сек, структуры содержали от 5 до 20 полей с UUID-дом, строками, небольшой бинаркой, были join-ы по 3-4 таблицам.

Хотя... я тут подумал, не сильно то и нужна СУБД в данном случае. Можно бинарку, все эти 100500 curves для одного фрейма можно сложить просто в бинарный файл с названием, содержащим идентифиактор этого фрейма.
Вот с изменениями в середине фала, будет небольшой, но в принципе решаемый гимор.

Отрадно видеть "подумал", это бывает редко, обычно типа "я своих решений не меняю" :). Все-таки вариант с СУБД я пока не "отметаю", ну не работал с ними, так что, все когда-нибудь случается впервые.
Да, этот путь очевиден/напрашивается. Ну наверно не "по файлу на кадр", а пачку кадров, так чтобы размер был метров восемь (это уже непринципиальные детали). Ну и грузить эти апельсины бочками по мере того какой кадр запрошен. С изменениями я обычно делаю так: обновить весь фрагмент (здесь кривую) дописав его в конец файла. А старый забыть, только зафиксировать сколько байт "устарело". Когда накопится достаточно много - переписать файл.

Но не все так уж просто. Нужно вычислять позицию/смещение в загруженном из файла блоке памяти. Это легко когда все "регулярно", т.е. все кривые имеют одно и то же число тех же кадров. Да, этот случай самый популярный, но увы, не единственный. К сожалению возможно что первая кривая напр имеет кадры 0-100, вторая 10-110, третья еще какие-то.  (другие). Нужно делать "заголовок", типа curveID+offset+size. Хотелось бы эти подробности пообсуждать (ну не все же заняты русской локалью  :))

Вооот, а в БД это делается одной строчкой )))
Ну ладно, 3 командами, insert/update/delete
Ну и выборка по фрейму автоматом получится.
В общем набросать прототип, который внутри инкапсулирует работу БД, дело на 2-4 часа. Не понравится, пусть этот прототип инкапсулирует работу с файлами.

Не совсем ясно что Вы сейчас предлагаете: юзать БД или как? Что мне не нравится с БД - с "блобами" фактически мы, для того чтобы считать данные одного кадра, прогружаем ВСЕ данные (которых может быть много гектар). Это безыдейно и не может быть правдой, пусть я ничего не понимаю в БД. Правильно считывать только (малую) часть данных

Каким образом если одно поле (блоб)?

Чуть ранее я писал про индексацию таблицы по нужным параметрам (в данном случае по фрейму), т.е. будет одно или несколько полей для выборки данных по ситуации. По фрейму, или допустим понадобится упорядочить curves по какому-либо признаку, можно добавить еще поле а-ля "вес", добавить поле с информацией о типе (1 дабл или 3 дабла в в структуре хранятся) и т.д.
Не надо полностью ничего загружать, надо написать запрос типа
подставляем в параметры ("?") идентификатор фрейма, получаем данные только для конкретного фрейма.

Как говорится, "не вкурил". Собсно все сводится к тому же: а что (или какие) в этой базе "поля" и какие "записи"?
Если "frame_data" - одно поле, то и оперировать с ним придется как с одним, то есть читать/писать целиком. Может имелось ввиду такое
Где frame_data = одно, единичное значение (данной кривой для данного кадра).

Да, но если мои предположения верны, то уже со 100K объектов выходит 700К кривых, и следовательно 700К записей на кадр. И что, СУБД умеют с этим справляться? Или загнется нафиг, да еще и диск забьет?   

Вообще странный вопрос... СУБД могут петабайтами информации ворочать и не загибаются.
Файловая sqlite у меня работала с БД до 5Гб (на бОльший объем не проверял, но уверен, справится), делала join выборку с результатом в 40 лямов строк (кривой запрос + кривые данные были).
Постгрес в прошлом моем проекте работал с таблицами по 20-30 лямов строк, объем БД был 50Гб.
Текущий проект в БД пишет по 1Тб в сутки, выборки правда довольно редкие.

Так, на днях лекцию смотрел по СУБД в МФТИ https://www.youtube.com/watch?v=V1rz3hbzsdw (https://www.youtube.com/watch?v=V1rz3hbzsdw).. Может интересно будет кому..)

Хорошо, подытожу вопросы
1. Структура базы
Это тупенькая структуркв записи верная, или можно как-то получше? Собсно мне нужно читать/писать значения для кадра кривой (читать макс быстро) - и все

2. Какую конкретно СУБД брать имея ввиду что мне нужно "доставить БД из кармана" (т.е. создавать ее втихаря когда юзер нажал кнопку), и сохранить (сериализовать) ее в своем файле данных. Т.е. чтобы не требовались какие-то внешние драйвера, установка в рамках ОС и.т.п.

Спасибо

1. Проиндексировать поля, по которым будет условия в select
frame_data для расширяемости можно в BLOB, если понадобится хранить там более одного значения

2. SQLite, достаточно подложить Qt-шные драйвера рядом со своим бинарником.

Для максимально быстрого чтения, можно создать пул соединений к БД, кажое соединение будет выбирать свой кусок данных и складывать в общий вектор.
Запрос будет что то типа такого:
соответственно  %N и %M для каждого подключения будут свои.

Спасибо, буду "пробывать" (где-то через месяц-другой). Постараюсь не забыть отписаться