LINUX.ORG.RU

Rust и двусвязный список

 , двусвязный список,


4

2

Хорошую тему тут затронули

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

http://contain-rs.github.io/linked-list/src/linked_list/lib.rs.html#11-1388

Или не лучшее? Растаманы и растафобы, собирайтесь на великую битву!

А вот, кстати, ещё про списки:

https://rust-unofficial.github.io/too-many-lists/

★★★★★

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

А зачем map дублировать во втором кэше?

Не надо его дублировать. Мы всё ещё LRU обсуждаем? Так вот, по определению там какой-то индекс будет. Может btree-based, может hashtable-based, может что-то ещё, но он будет. И чтобы он нормально работал Вам просто жизненно необходима стабильность итераторов «очереди». В отрыве эти 2 сущности смысла обсуждать нет. Я то уж было думал что у Вас имеется решение сильно оптимальнее двусвязного списка для «очереди», хотя бы в каких-то аспектах (компактность, referential locality etc).

Все равно без map можно обойтись.

Имхо - нельзя. Как Вы собрались обрабатывать запросы от клиента на уже вытесненный элемент? Как Вы собрались обрабатывать запросы на тоже самое от нескольких клиентов?

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

хорошая идея с точки зрения микро-бенчмарка

Я возможно банальность сейчас скажу: но все эти «бенчи» яйца выеденного не стоят если они не сняты под нагрузкой в проде. Из того что я пока видел в этом треде - всё сказанное - это исключительно теоретические измышления и фантазии. Понятно, что с Вашей точки зрения я «попИсать вышел». Но, тем не менее, рискну Вам дать дружеский совет - займитесь сбором реальной статистики а не результатов синтетических тестов. Это даст вам основу для educated decisions (и тогда Вам станет более менее понятно куда двигаться дальше). Мои 2 копейки…

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

яйца выеденного не стоят если они не сняты под нагрузкой в проде.

Специально сейчаc глянул: в моей «базёнке» на самом «интересном» instance cache hit ratio чуть больше 99% на уровнях до 5го (глубина дерева), и на 6ом (последний) - чуть больше чем за 50%. 500k запросов за день (на этом конкретном instance). Мне кажется - не так плохо :) А Вы - «Крылья, ноги….»

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

Но, тем не менее, рискну Вам дать дружеский совет - займитесь сбором реальной статистики а не результатов синтетических тестов.

Не понимаю, зачем ты мне этого говоришь. Раскроешь мысль?)

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

Раскроешь мысль?)

Я вот это вот:

и хорошая идея с точки зрения микро-бенчмарка

неправильно проинтерпретировал - я на них вообще не смотрю последнее время.

Меняя тему: в ваших краях не часто, но бываю - куда стучаться в случае чего?

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

Мигрировал на Ubuntu 22.04 с 20-ки, пришлось выпилить Python из Мемории. Достали грабли с environments. Каждый раз, когда обновляю vcpkg, что-то отваливается. На удивление, всё прошло идеально. Заменил jinja2 на inja и доволен.

До кучи, потестил на разных компиляторах. Я Gcc давно не пробовал, так как на нем и собирает долго, и сообщения об ошибках у него отличались особой нечитаемостью, да и крэшился он через версию. Пользую clang на постоянной основе.

Так вот, gcc-10/11/12 на Мемории крэшатся. Так что не только для тебя мой код труден. Даже компиляторы не выдерживают.

Сейчас поеду в отпуск, потом попробую запилить им багрепорт.

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

Я Gcc давно не пробовал, так как на нем и собирает долго, и сообщения об ошибках у него отличались особой нечитаемостью, да и крэшился он через версию. ... Так вот, gcc-10/11/12 на Мемории крэшатся.

Присоединяюсь к камушку в огород gcc. Потому что неправильная модель разработки.

Так что не только для тебя мой код труден. Даже компиляторы не выдерживают.

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

Кстати, вот как я переписал твою attach, которую «все равно потом выбросят»:

void attach(EntryT* entry)
{
  switch(entry->queue_kind)
  {
    case A1i : shift_and_insert< A1i, A1o       >(entry); break;
    case A1o : shift_and_insert< A1o, BlackHole >(entry); break;
    case Am  : shift_and_insert<  Am, BlackHole >(entry); break;
    default  : THROW(__LINE__)                          ; break;
  }
}

Весь класс уменьшился на 40...60 строк.

--------------------------------------------------------------------

И я категорически не согласен с твоей мыслью что потенциальные контрибьютеры «избалованы». Нет, это авторы проектов не уделяют внимания документированию и рассказу своей модели. У авторов, правда, есть некоторые слабые оправдания, но это не повод делать выводы о потенциальных контрибьютерах.

(Чуть вбок: что касается модели мемории, то она мне интересна.)

Я думаю имеет смысл сделать пост на ЛОРе на тему избалованности и моделей.

a--
()
Последнее исправление: a-- (всего исправлений: 3)
Ответ на: комментарий от bugfixer

Так вот, по определению там какой-то индекс будет. Может btree-based, может hashtable-based, может что-то ещё, но он будет.

Нет, вовсе не обязательно.

Есть вариант кэша на слабых указателях (и он я думаю будет шустрее в end-to-end бенче (клиент кэша + сам кэш)).

А совсем полноценный дизайн кэша должен предоставлять и map (который ты назвал индекс), и слабые указатели.

a--
()
Последнее исправление: a-- (всего исправлений: 4)
Ответ на: комментарий от bugfixer

Я то уж было думал что у Вас имеется решение сильно оптимальнее двусвязного списка для «очереди», хотя бы в каких-то аспектах (компактность, referential locality etc).

Не сказать что прямо «решение», но мысли или идеи оптимизации — есть (да, за счет чанков, а вот тут вчера пришли еще мысли для многопоточного случая).

Но тут обнаружилось, что даже сама модель кэша у меня / у вас еще далека от оптимальной.

a--
()
Последнее исправление: a-- (всего исправлений: 4)
Ответ на: комментарий от a--

И я категорически не согласен с твоей мыслью что потенциальные контрибьютеры «избалованы».

Я про пользователей, а не контрибьюторов. Софта сейчас объективно избыток, пользователи предпочитают просто ждать, когда им всё принесут. В С++ные проекты дополнительно еще и высокий порог вхождения, а TMP – так и вообще что-то заоблачное. А если еще и структуры данных… По большому счету, сейчас контрибьюторам надо платить (так или иначе). Иначе процессы неустойчивы.

Насчет «всё равно потом выбросят», есть понятие технического долга. С ним всё нормально, если есть процесс его «выплаты». В Мемории он есть.

Твой attach() – красивый.

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

Твой attach() – красивый.

Код может быть либо красивый, либо умный Там все же имеются недоделки — в том смысле, что push_back лучше вынести, так как shift инкапсулирует твою модель владения (или что там у тебя с eviction_fn_)

Вот примерные 2 варианта, мне кажется 2-й все же получше выглядит в рамках С++. А в рамках resyntaxed C++ можно было бы написать еще лучше.

void attach(EntryT* entry)
{
  switch(entry->queue_kind)
  {
    case A1i : queue< A1i >.move_excess_into< A1o       >.push_back(*entry); break;
    case A1o : queue< A1o >.move_excess_into< BlackHole >.push_back(*entry); break;
    case Am  : queue<  Am >.move_excess_into< BlackHole >.push_back(*entry); break;
    default  : THROW(__LINE__)                                             ; break;
  }
}
void attach(EntryT* entry)
{
  switch(entry->queue_kind)
  {
    case A1i : shift_queue< A1i, A1o       >.push_back(*entry); break;
    case A1o : shift_queue< A1o, BlackHole >.push_back(*entry); break;
    case Am  : shift_queue<  Am, BlackHole >.push_back(*entry); break;
    default  : THROW(__LINE__)                                ; break;
  }
}
a--
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.