Почему бы нам просто не хранить всю динамическую c память в массивах?

Question

В C / C ++, когда вы выделяете динамическую c память, ОС дает вам непредсказуемый адрес для некоторой отдаленной области памяти. Если вы выделяете много динамической c памяти и вам нужно перемещаться между ней (например, связанными списками, деревьями), то вам придется тратить время на ожидание, пока ЦП свяжется с ОЗУ, потому что, скорее всего, часть память, которую вы хотели, не была близка к той части памяти, которая была у вас.

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

Поскольку это был C ++, он был быстрым, конечно, но со временем и памятью, на которых он тестировался, у меня была просто нормальная производительность.

Итак, я решил попробовать реализовать замены указателей, которые на самом деле были бы индексами векторов stati c, и функцию для увеличения вектора, когда требовался новый объект, и стек «удаленные» индексы, которые можно использовать повторно. Таким образом, все было бы близко друг к другу в памяти, и разыменования с меньшей вероятностью приводили к ошибкам кэша. Кроме того, поскольку я знал, что дерево не будет тестироваться в масштабе гигабайт данных, я мог ограничить эти индексы 32-битными значениями, значительно сократив объем памяти древовидной структуры.

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

Мой вопрос: если преимущества кэширования настолько велики, зачем нам вообще напрямую использовать new и delete? ? Почему бы просто не вставить все в векторах, по одному для каждого типа?

Answer 1

Вы используете стандартные распределители, когда они «достаточно хороши» для того, что вам нужно сделать. Разница между программой, которая работает в 10 мс, и той, которая работает в 100 мс, может быть в 10 раз, но на практике это различие не имеет смысла. Оба запускаются «мгновенно».

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

---

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

В большинстве реализаций стандартных библиотек для new / malloc используется распределитель пула, который является некоторым обобщением пула объектов, который вы используете. реализовал. При первом запросе некоторой памяти они выделяют большой кусок памяти из ОС, а затем раздают фрагменты этого пула по запросу, отслеживая, какие фрагменты используются, а какие доступны для последующего (повторного) использования. Когда пул закончится, они получат еще один кусок памяти из ОС и начнут раздавать его.

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

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

Answer 2

Почему бы нам просто не сохранить всю динамическую c память в массивах?

Если честно, мы сохраняем большинство динамических c память в массивах.

Но иногда массив не может достигнуть такой же асимптотической c сложности, как структура на основе узлов, и в таком случае может быть выгодно не использовать массив.

Почему мы вообще не можем использовать new и delete?

Чрезвычайно редко нужно использовать new и delete напрямую.

Answer 3

Чтобы добавить к очень хорошему ответу Майлза:

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

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

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

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

Знаете ли вы, что операторы new и delete могут быть перегружены в C ++? Посмотрите, это откроет для вас целый новый мир. Таким образом, вы можете написать свой распределитель памяти пула таким образом, чтобы код уровня приложения выполнял то, что кажется совершенно нормальным (или почти совершенно нормальным) использованием new и delete, и вы можете перехватить это использование за кулисами и перенаправить его на свой пользовательский распределитель памяти. Я делал это в прошлом, очень интересно, если не сказать больше.