Пересмотр QList против QVector

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

QList будет автоматически сохранять "большие" объекты в качестве указателя и выделять объекты в куче, что можно считать хорошей вещью, если вы ребенок, который не знает, как объявить QVector<T*> и использовать динамическое размещение. Это не обязательно хорошо, и в некоторых случаях это только увеличит использование памяти и добавит дополнительную косвенность. IMO, всегда полезно четко указать, что вы хотите, будь то указатели или экземпляры. Даже если вам нужно выделение кучи, всегда лучше выделить ее самостоятельно и просто добавить указатель в список, чем создавать объект один раз, а затем копировать его в куче.

Qt вернет вам QList во многих местах, где это связано с накладными расходами, например, при получении дочерних элементов QObject или при поиске дочерних элементов. В этом случае нет смысла использовать контейнер, который выделяет место перед первым элементом, поскольку это список объектов, которые уже есть, а не то, к чему вы, вероятно, не будете добавляться. Мне также не очень нравится отсутствие метода resize().

Представьте ситуацию, когда у вас есть объект размером 9 байт и выравниванием по байтам в 64-битной системе. Это «слишком много» для QList, поэтому вместо этого он будет использовать 8-байтовый указатель + накладные расходы ЦП для медленного выделения кучи + накладные расходы памяти для выделения кучи. Он будет использовать в два раза больше памяти, а с дополнительным косвенным доступом он вряд ли обеспечит преимущества в производительности, как рекламируется.

Что касается того, почему QVector не может внезапно стать контейнером «по умолчанию» — вы не меняете лошадей в середине гонки — это устаревшая вещь, Qt — такой старый фреймворк, и хотя многие вещи устарели, внесение изменений в широко используемые значения по умолчанию не всегда возможны, не без нарушения большого количества кода или создания нежелательного поведения. Хорошо это или плохо, но QList, скорее всего, останется значением по умолчанию на протяжении всей Qt 5, а также, вероятно, и в следующем крупном выпуске. По той же причине Qt будет продолжать использовать «тупые» указатели в течение многих лет после того, как умные указатели стали обязательными, и все плачут о том, насколько плохи простые указатели и что их никогда не следует использовать.

При этом никто не заставляет вас использовать QList в своем дизайне. Нет причин, по которым QVector не должен быть вашим контейнером по умолчанию. Я сам нигде не использую QList, а в функциях Qt, которые возвращают QList, я просто использую их как временные для перемещения материала в QVector.

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

Последний, но тем не менее важный:

Для большинства целей подходит класс QList.

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

Для большинства целей подойдет QList.

Подводя итог:

QList PRO

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

QList минусы

• не имеет метода resize(), reserve() является тонкой ловушкой, так как он не увеличит действительный размер списка, даже если доступ к индексу работает, он попадает в категорию UB, также вы не сможете перебрать этот список
• делает дополнительную копию и выделяет кучу, когда объект больше указателя, что также может быть проблемой, если идентификация объекта имеет значение
• использует дополнительную косвенность для доступа к объектам, большим, чем указатель
• имеет накладные расходы процессорного времени и памяти из-за последних двух, а также менее удобен для кеша
• поставляется с дополнительными накладными расходами при использовании в качестве возвращаемого значения «поиск», поскольку вы вряд ли будете добавлять или даже добавлять к этому
• имеет смысл только в том случае, если доступ к индексу является обязательным, для оптимальной производительности добавления и вставки связный список может быть лучшим вариантом.

CON немного перевешивает PRO, а это означает, что, хотя в «случайном» использовании QList может быть приемлемым, вы определенно не хотите использовать его в ситуациях, когда время процессора и/или использование памяти являются критическим фактором. В общем, QList лучше всего подходит для ленивого и небрежного использования, когда вы не хотите рассматривать оптимальный контейнер для хранения для варианта использования, которым обычно будет QVector<T>, QVector<T*> или QLinkedList (и я исключаю " STL», поскольку мы говорим здесь о Qt, контейнеры Qt столь же переносимы, иногда быстрее и, безусловно, проще и чище в использовании, тогда как контейнеры std излишне многословны).

В Qt 5.7 документация была изменена по обсуждаемой здесь теме. В QVector теперь указано:

QVector должен быть вашим первым выбором по умолчанию. QVector<T> обычно обеспечивает более высокую производительность, чем QList<T>, потому что QVector<T> всегда последовательно хранит свои элементы в памяти, а QList<T> размещает свои элементы в куче, если только sizeof(T) ‹= sizeof(void*) и T не объявлены либо Q_MOVABLE_TYPE, либо Q_PRIMITIVE_TYPE с использованием Q_DECLARE_TYPEINFO.

Они ссылаются на эту статью Марка Мутца.

Итак, официальная точка зрения изменилась.

QList представляет собой массив void*.

В своей обычной работе он new размещает элементы в куче и сохраняет указатель на них в массиве void*. Подобно связному списку, это означает, что ссылки (но, в отличие от связанных списков, а не итераторов!) на элементы, содержащиеся в списке, остаются действительными при любых изменениях контейнера до тех пор, пока элемент снова не будет удален из контейнера. Отсюда и название «список». Эта структура данных называется списком-массивом и используется во многих языках программирования, где каждый объект имеет ссылочный тип (например, Java). Это очень неудобная для кэширования структура данных, как и все контейнеры на основе узлов.

Но изменение размера массива-списка может быть учтено в независимом от типа вспомогательном классе (QListData), который должен сэкономить некоторый размер исполняемого кода. В моих экспериментах почти невозможно предсказать, какой из QList, QVector или std::vector производит наименее исполняемый код.

Это был бы хороший тип данных для многих ссылочных типов Qt, таких как QString, QByteArray и т. д., которые состоят не более чем из указателя pimpl. Для этих типов QList получила важную оптимизацию: когда тип не больше указателя (обратите внимание, что это определение зависит от размера указателя платформы — 32 или 64 бита), вместо размещения объектов в куче объекты хранятся в слоты void* напрямую.

Однако это возможно только в том случае, если тип просто перемещается. Это означает, что его можно переместить в память с помощью memcpy. Перемещение здесь означает, что я беру объект, memcpy его по другому адресу и, что особенно важно, не запускаю деструктор старого объекта.

И тут дела пошли не так. Потому что, в отличие от Java, в C++ ссылкой на объект является его адрес. И хотя в исходном QList ссылки были стабильными до тех пор, пока объект снова не был удален из коллекции, при помещении их в массив void* это свойство больше не сохранялось. Это больше не «список» для всех намерений и целей.

Однако дела по-прежнему шли не так, потому что они разрешали помещать типы строго меньше void* в QList. Но код управления памятью ожидает элементы размером с указатель, поэтому QList добавляет заполнение (!). Это означает, что QList<bool> на 64-битных платформах выглядит так:

[ | | | | | | | [ | | | | | | | [ ...
[b|   padding   [b|   padding   [b...

Вместо размещения 64 логических значений в строке кэша, как это делает QVector, QList обрабатывает только 8.

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

Vector — самый простой из классов контейнеров STL и во многих случаях самый эффективный.

В Effective STL Скотта Мейера есть несколько элементов, которые начинаются с "Предпочитать std::vector вместо...".

То, что верно в целом для C++, не становится вдруг неверным только потому, что вы используете Qt.

Qt 6 исправит эту конкретную ошибку проектирования. А пока используйте QVector или std::vector.

Если размер типа элемента QList больше, чем размер указателя, QList работает лучше, чем QVector, потому что он не сохраняет объекты последовательно, а последовательно сохраняет указатели на копии кучи.

Я склонен говорить об обратном. Это будет намного хуже, когда вы будете проходить предметы. Если он сохранит его как указатели в куче, не будет ли QList намного хуже, чем QVector? Причина, по которой последовательное хранилище (все время QVector) настолько хорошо, заключается в том, что оно удобно для кеша, как только вы сохраняете указатели, вы теряете локальность данных, начинаете получать промахи кеша, и это ужасно для производительности.

Контейнер «по умолчанию» IMHO должен быть QVector (или std::vector), если вы беспокоитесь о большом перераспределении, то предварительно выделите разумную сумму, оплатите единовременную стоимость, и вы выиграете в долгосрочной перспективе.

Используйте *Vector по умолчанию, если у вас возникнут проблемы с производительностью, профилируйте и измените по мере необходимости.

Обратите внимание, что это полностью изменилось в Qt6: https://www.qt.io/blog/qlist-changes-in-qt-6

QVector и QList унифицированы, и в качестве базовой реализации используется модель QVector. Это означает, что дополнительный уровень косвенности Qt 5 QList для универсальных типов теперь отсутствует, и элементы всегда хранятся непосредственно в выделенной памяти. QList — это настоящий класс с реализацией, а QVector — просто псевдоним QList. QList в Qt 6 поддерживает оптимизированное начало. Теперь он может сжиматься при удалении элементов без использования резерва. И ограничение размера в 2 ГБ снято.

QList — это наилучший контейнер для использования в целом, как указано в документации. Если размер типа элементов ‹= размера указателя = машина и разрядность ОС = 4 или 8 байт, то объекты хранятся так же, как это делает QVector - последовательно в памяти. Если размер типа элемента QList больше, чем размер указателя, QList работает лучше, чем QVector, потому что он не сохраняет объекты последовательно, а последовательно сохраняет указатели на копии кучи. В 32-битном случае картина следующая:

sizeof( T ) <= sizeof( void* )
=====
QList< T > = [1][1][1][1][1]
                   or
             [2][2][2][2][2]
                   or
             [3][3][3][3][3]
                   or
             [4][4][4][4][4] = new T[];

sizeof( T ) > sizeof( void* )
=====
QList< T > = [4][4][4][4][4] = new T*[]; // 4 = pointer's size
              |   |  ...  |
           new T new T   new T

Если вы хотите, чтобы ваши объекты размещались в памяти последовательно независимо от размера их элементов, как это обычно бывает при программировании OpenGL, вам следует использовать QVector.

Вот подробное описание внутреннего устройства QList.

Представьте, что у нас есть класс DataType.

QVector - массив объектов, например:

// QVector<DataType> internal structure
DataType* pArray = new DataType[100];

QList — массив указателей на объекты, например:

// QList<DataType> internal structure
DataType** pPointersArray = new DataType*[100];

Поэтому прямой доступ по индексу будет быстрее для QVector:

{
// ...
cout << pArray[index]; //fast
cout << *pPointersArray[index]; //slow, need additional operation for dereferencing
// ...
}

Но обмен будет быстрее для QList, если sizeof(DataType) > sizeof(DataType*):

{
// QVector swaping
DataType copy = pArray[index];
pArray[index] = pArray[index + 1];
pArray[index + 1] = copy; // copy object

// QList swaping
DataType* pCopy = pPointersArray [index];
pPointersArray[index] = pPointersArray [index + 1];
pPointersArray[index + 1] = pCopy; // copy pointer
// ...
}

Итак, если вам нужен прямой доступ без перестановки операций между элементами (например, сортировка) или sizeof(DataType) ‹= sizeof(DataType*), лучше использовать QVector. В другом случае используйте QList.

QList ведет себя по-разному в зависимости от того, что находится внутри (см. исходный код struct MemoryLayout):

• если sizeof T == sizeof void* и T определены как Q_MOVABLE_TYPE, то QList<T> ведет себя точно так же, как QVector, то есть данные хранятся в памяти непрерывно.

• если sizeof T < sizeof void* и T определены как Q_MOVABLE_TYPE, то QList<T> дополняет каждую запись до sizeof void* и теряет совместимость макета с QVector.

• во всех остальных случаях QList<T> является связанным списком и, следовательно, в некоторой степени медленным.

Именно такое поведение делает QList<T> почти всегда плохим выбором, потому что, в зависимости от изящных деталей, QList<T> на самом деле является либо списком, либо вектором. Это плохой дизайн API и склонность к ошибкам. (Например, вы столкнетесь с ошибками, если у вас есть библиотека с общедоступным интерфейсом, которая использует QList<MyType> внутри и в своем общедоступном интерфейсе. sizeof MyType is < sizeof void*, но скажите, что вы забыли объявить MyType как Q_MOVABLE_TYPE. Позже вы захотите добавить Q_MOVABLE_TYPE. Это является бинарно несовместимым, а это означает, что теперь вам нужно перекомпилировать весь код, который использует вашу библиотеку, так как структура памяти QList<MyType> изменилась в общедоступном API. Если вы не будете осторожны, вы пропустите это и создадите ошибку. Это довольно хорошо иллюстрирует, почему QList здесь плохой выбор.)

Тем не менее, QList по-прежнему не так уж плох: он, вероятно, будет делать то, что вам нужно в большинстве случаев, но, возможно, за кулисами он будет выполнять работу не так, как вы ожидаете.

Правило большого пальца:

• Вместо QList используйте QVector<T> или QVector<T*>, так как это явно говорит о том, что вы хотите. Вы можете комбинировать это с std::unique_ptr.

• В C++11 и более поздних версиях даже считается лучшим просто использовать std::vector, так как он будет вести себя правильно в цикл for на основе диапазона. (QVector и QList могут отсоединиться и, следовательно, выполнить глубокое копирование).

Вы можете найти все эти и другие подробности в презентации Марка Мутца и в видео Оливье Гоффара.