Интрузивный список

[Igors]

Добрый день

Есть код "без всяких классов" написанный в незапамятные времена

Код

C++ (Qt)
Curve * GetNodeCurve( Node * node, int curveID )
{
 Curve * curve = GetFirstCurve(node);    
 while (curve) {
   if (GetCurveID(curve) == curveID)
    return curve;
   curve = GetNextCurve(curve);
 }
 return 0;
}

Ну ясно вставки/удаления выполняются быстро, можно лихо перебрасывать данные из одного Node в другой. "Расплата" - нет прямого доступа."По задаче" это вполне оправдано, во всяком случае было. Node имел ну сотку-другую curves максимум, а обычно десяток-другой, да и необходимость прямого доступа возникала относительно редко.

Но вот появилась новая фича которая для некоторых Node струячит поток этих curves, напр 100K и больше. Конечно код выше стал неприятно притормаживать. Отсюда вопросы

1) Как ускорить?

2) Стоит ли держаться за старый код/списки или все-таки принципиально правильно снести его нафиг и сделать "нормально"? (тогда как?).

Спасибо

[ssoft]

Добавьте индексацию этих Curve ::std::unordered_map< int, Curve*> curve_for_id;
Можно непосредственно в Node, ну или снаружи Node (в место управления самими Node).
При вставке и удалении Curve корректируйте индексацию.

[__Heaven__]

Если node владеет curve, то можно ещё попробовать std::set<Curve>. Понадобится написать transparent компоратор, который будет их укладывать и искать по curveID или обойтись std::less<> в качестве компоратора и operator< для Curve, int и для Curve, Curve

ещё можно попробовать flat_set. Индексация будет быстрее, но в нём итераторы и указатели инвалидируются при модификации а также замедлится вставка/удаление. Под капотом у него вектор.

[Igors]

Добавьте индексацию этих Curve ::std::unordered_map< int, Curve*> curve_for_id;

Если node владеет curve, то можно ещё попробовать std::set<Curve>.

Ну какой конкретно контейнер юзать - непринципиально, мне лично больше нравится QHash. Предложенные варианты вполне возможны. Но мне не нравится что утверждается (или навязывается) отношение владения. Node владеет Curve? Да, сейчас он просто хранит голову списка (Curve кстати тоже наследник Node). Но возможны курвы которыми на данный момент никто не владеет, напр при чтении из файлв/клипборды. Или вот юзер переставил что-то в UI, нужно переупорядочить список. Сначала делается типа "take"

Код

C++ (Qt)
Curve * ExtractCurvesFromList( Curve * theCurveList, // голова списка
                                               Сurve * theCurve,    // голова извлекаемых Curve
                                               bool withChildren = true ); 

Возвращается новая голова списка (меняется если theCirveList == theCurve). Потом делается

Код

C++ (Qt)
Curve * InsertCurvesInList( Curve * theCurveList,  // голова списка
                                             Сurve * theCurve,    // голова вставляемых Curve
                                             Curve * theCurveBefore = 0 ); // куда вставлять (null = в конец) 

При этом совершенно необязательно что theCurveList - тот самый что хранится в Node владельце.

Пусть интрузивность кака (std никогда ее не юзает), но она привлекает "самодостаточностью", напр код выше не требует никаких контейнеров. Может это плохо, тогда люди просто их не имели, вот и писали так? Не знаю, но я не вижу "достаточных оснований" сносить этот старый код, и неясно на что его менять

В самом деле, если хранить курвы в ассоциативном контейнере то как обеспечить ф-ционал take? Копировать конечно низзя. Придется делать контейнер указателей. И упорядоченность тоже надо поддерживать (в UI должны появляться в заданном порядке (обычно порядок создания), а не по ID). Нормальным стандартным решением будет std::list + QHash для поиска пошустрее. Ну я не вижу чем std::list так уж лучше, а пришивать рукав QHash все равно придется.

При вставке и удалении Curve корректируйте индексацию.

Это совсем непросто в достаточно большом проекте, сначала нужно как-то регламентировать вставки/удаления (сейчас поля next и prev просто public, и я сам их менял не раз (грязыми) руками)

Есть такая мысль: никто не заставляет хешировать все тотально и постоянно. Наоборот, bottleneck'ов немного (пока 2) и они хорошо видны. Один из них - чтение большого числа curves из файла. Сначала Node владелец создается с небольшим числом curves (ну там position, rotation и.т.п). Читается курва за курвой из потока. Сначала ID, такая уже есть у владельца? Да - читать в имеющуюся, нет - создать новую. Ну и вот эта проверка на 100K притормаживает. Может какой-нибудь "scoped" хеш ?

[__Heaven__]

как обеспечить ф-ционал take

Через std::set::extract обеспечивается. Делает возможным хранение объектов, а не указателей

Ну, раз нельзя упорядочивать, то видно решение от ssoft будет наиболее разумным.

поля next и prev просто public

Придётся исправлять, либо больше закапываться в местах обращения

[Авварон]

Пусть интрузивность кака (std никогда ее не юзает), но она привлекает "самодостаточностью", напр код выше не требует никаких контейнеров. Может это плохо, тогда люди просто их не имели, вот и писали так? Не знаю, но я не вижу "достаточных оснований" сносить этот старый код, и неясно на что его менять

Интрузивность тут совершенно ни при чем, просто связанный список - это очень простая структура данных, любой студент может на голых сях написать. Попробуйте написать\использовать вектор на голых сях или красно-черное дерево, вам сразу же захочется абстракций которые позволят это дерево написать один раз и хранить в нем что угодно (например, при помощи шаблонов). Но так как в си шаблонов нет, а без них вы попадаете в волшебную землю void*, приходится обходится самым простым, что можно написать - связанным списком.
В общем это всё не от хорошей жизни, сидеть и дебагать вставку нодов руками никакого удовольствия нет (хорошо если оно написано и работает, но вот эти ваши "заменить голову" уже намекают на некий бойлерплейт).
Вам нужен "обычный" вытесняющий кэш (last recently used cache, LRU cache) (только с лимитом элементов выкрученным в бесконечность), реализуется через std::list+std::unordered_map (или кутешные аналоги).
(щаз у вас правда возникнет требование вставлять в середину списка, про которое вы "забыли" упомянуть, но о5 же никакой проблемы сделать его нет, просто внешний итератор должен итерироваться по списку а не по мапе)

[Igors]

Вам нужен "обычный" вытесняющий кэш (last recently used cache, LRU cache) (только с лимитом элементов выкрученным в бесконечность), реализуется через std::list+std::unordered_map (или кутешные аналоги).

Причем тут LRU кэш Порядок следования в UI определяется заданными правилами и/или юзером, LRU здесь не поможет

(щаз у вас правда возникнет требование вставлять в середину списка, про которое вы "забыли" упомянуть, но о5 же никакой проблемы сделать его нет, просто внешний итератор должен итерироваться по списку а не по мапе)

Не понял в чем меня хотят уличить? Да, вставка/удаление обычно работают для середины списка, ну этого никто и не скрывал

..но вот эти ваши "заменить голову" уже намекают на некий бойлерплейт).

Ну да, так получается, если в Node хранить голову списка, то приходится считаться с тем что некоторые вставки/удаления могут ее изменить

В общем это всё не от хорошей жизни,

Да, это выглядит очень старомодно, архаично, наивно, примитивно и.т.п. (как хотите), хотя впрочем неизвестно какое впечатление будет производить "современный" код через четверть века. Но пока я в упор не вижу на что "современное" это поменять. Напр упоминался std::list. Тогда как, имея курву, вычеркнуть ее оттуда? Придется видимо где-то хранить (злополучный) итератор, наверно в том же хеше. На множ вставках/удалениях это заметно медленнее/затратнее чем интрузивный монстр. Ну бог с ним, это не рендер, такая скорость тоже устроит. Но выгоды-то где? Не вижу ни одной. И что делать с приведенными выше Extract/Insert ? Они вероятно будут как-то (неприятно) завязаны на контейнеры/владение. Или как ?

[Авварон]

Причем тут LRU кэш Порядок следования в UI определяется заданными правилами и/или юзером, LRU здесь не поможет

При том, что имплементация того что вам нужно 1в1 LRU cache. LRU Cache умеет:
1. быстро искать по ключу.
2. хранит порядок элементов.
3. автоматом удаляет "старые" элементы при вставке новых.

Вам нужно 1 и 2 и не нужно 3. 3 отключается выкручиванием лимита элементов в бесконечность. 1 и 2 есть "из коробки".
Не нравится название LRU cache - назовите OrderedMap (но тут возникают мысли а чем оно отличается от std::map), но на имплементацию это мало повлияет - вам всё равно придется копипастить из интернетов\писать самому, но так хотя бы вы знаете куда смотреть.
Выгоды такие что вы будете работать с контейнером где элементы хранятся по значению (ну или вы будете хранить поинтеры на курвы если вы любите извращения) и не насиловать себе мозг с ручным обновлением головы списка.

Код:

template<typename K, typename V> struct OrderedMap 
{
    using List = std::list<std::pair<K, V>>;
    using iterator = List::iterator;
    std::unordered_map<K, iterator> map;
    List data;
};

Домашнее задание - не дублировать ключ два раза.

[Igors]

При том, что имплементация того что вам нужно 1в1 LRU cache. LRU Cache умеет:
1. быстро искать по ключу.
2. хранит порядок элементов.
3. автоматом удаляет "старые" элементы при вставке новых.

Вам нужно 1 и 2 и не нужно 3. 3 отключается выкручиванием лимита элементов в бесконечность. 1 и 2 есть "из коробки".

Так он меняет порядок хранимых, при каждом обращении искомый становится "головой" списка

Код:

template<typename K, typename V> struct OrderedMap 
{
    using List = std::list<std::pair<K, V>>;
    using iterator = List::iterator;
    std::unordered_map<K, iterator> map;
    List data;
};

Домашнее задание - не дублировать ключ два раза.

А зачем в списке хранить пару? Просто "V" (сама курва или указатель на нее). Однако привязка к контейнеру все равно есть, т.е. имея курву я должен как-то достучаться до владельца (здесь OrderedMap), и выходит этого владельца я должен иметь. Напр отлинковал (take) какие-то Curves - ну и как эту "пачку" хранить? Др словами придется все делать "от владельца" - так ли уж это выгодно?

[Igors]

Ну, как всегда, все эти разговоры о "проектировании" и "архитектуре" свелись к банальному "какой готовый класс хапнуть"

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

Что касается хеша/ускорения, я пришел у выводу что делать его постоянным (и куда-то поселять) не нужно, лучше латать конкретные bottlrneck'и. Получилось примерно так

Код

C++ (Qt)
Curve * GetNodeCurve( Node * node, int curveID )
{
 auto * hash = CScopedCurveHash::instance();
 if (hash) {
   Curve * curve = hash->GetCurve(node, curveID);  // есть в хеше ?
   if (curve) return curve;
   if (hash->HasNode(node)) return 0;  // см ниже
 } 
 Curve * curve = GetFirstCurve(node);    
 while (curve) {
   if (GetCurveID(curve) == curveID) break;
   curve = GetNextCurve(curve);
 }
 if (hash)
   hash->AddCurve(node, curveID, curve); 
 return curve;
}
 

Использование

Код

C++ (Qt)
void LoadCurves( Stream & strem, Node * node )
{
 CScopedCurveHash scoped;
 scoped.AddNode(node);  // добавить все имеющиеся (на данный момент)
  ... // грузим
}

По поводу HasNode и AddNode. Если поиск по паре (Node, ID) вернул 0 что это значит? (такой вообще нет или такую еще не искали?). Ну и в ф-циях Extract/Insert хеш также корректируется.

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

Это "костыль" или нет? Лично я думаю что нет. Во всяком случае постоянное существование потенциально большого хеша проблематично. Напр объекты с большим числом curves требуют доступа по ID лишь на загрузке

[Авварон]

Код:

auto * hash = CScopedCurveHash::instance();

Потокобезопасненько