В чем преимущество встраивания связанного списка в структуру данных?

Question

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

Я более знаком с проектами, которые отделяют тип контейнера от типа значения (рассмотрим std::list, или же System.Collections.Generic.LinkedList). Я изо всех сил пытаюсь понять ценностное предложение встраивания семантики контейнера в тип данных - какая эффективность достигается? Это действительно все об устранении хранения указателя экземпляра узла?

Answer 1

Предположим, у вас есть итератор / указатель на узел в вашем списке. Чтобы получить данные, вы должны:

• читать указатель на данные из узла
• разыменуйте указатель, который вы только что прочитали и прочитали фактические данные

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

Другая проблема, связанная с отдельным узлом списка и его данными, заключается в том, что сам узел списка мал (обычно всего 2 или 3 указателя). В результате, накладные расходы на хранение такой небольшой структуры в памяти могут иметь значение. Вы знаете - такие операции, как new или же malloc на самом деле потребляет больше памяти, чем выделяет - система использует свои собственные древовидные структуры, чтобы отслеживать, где память свободна, а где нет.

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

Подобную стратегию можно увидеть с помощью навязчивых указателей (по сравнению с общими указателями) или std::make_shared это объединяет данные объекта и интеллектуального указателя.

---

Zett42 делает комментарий, что std::list<T> держит T вместе с данными узла. Это позволяет получить один блок памяти, как я объяснил выше, но имеет другую проблему: T не может быть полиморфным. Если у вас есть класс A и его производная B, затем node<B> не является производной от node<A>, Если вы стараетесь вставить B в std::list<A> Ваш объект будет:

• В лучшем случае вызвать ошибку компиляции (без конструктора A::A(const B&))
• В худшем случае тихо нарезать B копирование только части, представляющей A в узел.

Типичное решение, если вы хотите хранить полиморфные объекты в одном списке, это на самом деле иметь std::list<A*> вместо std::list<A>, Но тогда вы получите дополнительное косвенное объяснение, которое я объяснил выше.

Альтернативой является создание навязчивого списка (например, boost::intrusive::list), где информация об узле фактически является частью A объект. Тогда каждый узел может быть производным от A без проблем.

Answer 2

Одним большим преимуществом связанного списка Intrusive является то, что вы можете создать список ранее существовавших объектов без каких-либо новых выделений. Для этого с указателем std::list потребуется выделение памяти.

Boost имеет навязчивую реализацию списка с обоснованием использования. http://www.boost.org/doc/libs/1_63_0/doc/html/intrusive.html

Answer 3

какая эффективность достигается? Это действительно все об устранении хранения указателя экземпляра узла?

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

Answer 4

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

Например, у вас может быть набор элементов, отсортированных 3 разными способами, в соответствии с его записями в 3 разных списках. Это было бы довольно неуклюже с std::list, например.

Другое большое преимущество, на мой взгляд, как упоминает @doron, заключается в том, что для управления списком требуется 0 выделений, как только у вас есть сами объекты.

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