OberonCore

Публикую систему Scl для BlackBox. Standard Container Library реализует объекты vectors, lists, queues, stacks, maps безо всяких дженериков. Используются метаданные BlackBox Kernel.

Мотивация:
1. "Нежелание множить сущности без необходимости" - использование одних алгоритмов (напр, сортировка, поиск) для сравниваемых элементов, а не чисел, строк и т.д.
2. "Смотрите, от чего я ради вас уклонился" - отсутствие дженериков и связанной с ними проблемной инфраструктуры.
3. "As Simple as Possible" - более простые решения более эффективны в плане быстродействия, чем переопределяющие операции решения типа reference operator[]( size_type pos ), используемые в c++ stl.

Пример - Vectors.Vector


Вектор при необходимости расширяется (в примере до size=12).
Доступ к элементам осуществляется штатным образом, а не через переопределенный оператор operator[].

Механизм работы основан на реаллокировании при необходимости MyVec.data. Используются метаданные, т.к. надо создавать указатель на массив POINTER TO ARRAY OF MyRec из базового класса.

Если библиотека контейнеров стандартная, то где именно?
Чем это лучше дженериков? Понятно, что в CP нет дженериков, но в гипотетическом плане?
Почему это более эффективно, что переопределение operator[]( size_type pos )? На первый взгляд отличия от статического метода лишь синтаксические. А тут вообще динамика.

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

В части сравнения предложенного примера с vec.data[i] супротив operator[] есть два момента:
1. operator[] имеет определенный overhead, т.к. это метод, и быстродействие доступа к элементам вектора хуже, чем доступ к элементам массива c++;
2. доступ к элементам vec.data[] - это доступ через указатель на массив с проверкой границ, что дает нам новой качество (например, защита от кибер-атак на переполнение стека);
3. как я покажу впоследствии (в библиотеке есть документ Bench-Marks.odc), во-втором случае измеренный доступ оказался быстрее.

Пример - Lists.IndexedList

Элементы List, Queue, Deque, Stack работают с указателем на массив указателей POINTER TO ARRAY OF %SearchElemPArr. Функцию NEW экономичнее вызывать для массива, чем для каждого его элемента.
Поле Keys.SString32Key означает наличие строкового ключа, по которому можно проводить сравнение. Где сравнение, там и сортировка, и бинарный поиск.

Можно делать списки, очереди и др из Ваших пользовательских структур.

Если понадобятся другие ключи, не целые и не строки, нужно добавить функцию сравнения аналогично тому, как это сделано для LongKey:

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

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

У C++ vector есть метод at() с проверками границ, что, конечно, хуже, чем если бы проверки работали при обращении через [], так как стимулирует работать без проверок, чем большинство и пользуется. Но, кстати, по методу at() подтверждаю серьёзную просадку производительности по сравнению с системами, в которых проверка границ на уровне языка и даже с Си с явной проверкой.

Теперь о сравнении с stl (mingw32, o3) в части быстродействия. Рассматривалась задача вычисления суммы значений вектора целых чисел.
Вариант 1 - Vector Iterators


Вариант 2 - Vector No Iterators


Вариант 3 - Array from Vector


Вариант 4 - SclObxBenchmarks.CLongVector(100)

Результаты сравнения:


Выводы:
Вариант реализации вектора для BlackBox лучше, чем Вариант 2 с std::vector и гораздо лучше, чем вариант 1 с использованием итераторов.
Вариант реализации вектора для BlackBox уступает Варианту 3, но это совсем не std::vector, а просто массив!

Таким образом, реализация вектора для BlackBox показывает в данном тесте на 40% выигрыш по сравнению с лучшим результатом для c++ std::vector.

Это интересно, можно выложить эти тесты? Но собирать в mingw32 не обещаю, использую GNU/Linux.

Да, конечно, прилагаю c++ тесты vector, list, map.
Тесты по векторам были навеяны статьей Веселые старты или C++ и STL: кто быстрее?.
На мой взгляд, вполне разумно и хорошо изложено. Так там stl "разогнать" не удалось, массивы и указатели - пожалуйста. Мои независимые эксперименты в части векторов показывали похожие результаты, хотя там gcc+unix.

Где взять Tb?

Еще ссылка на Scl - Standard Container Library, Component Pascal Collection, Helmut Zinn.

Для получения приемлемых временных данных в части сортировки (IndexedList) потребовалось оптимизировать функции сравнения элементов, в частности, сравнения строк. Для этого проводились измерения времени сортировки с разными функциями сравнения. Например, для 8-бит:
1. WinApi - с функцией WinApi.lstrcmpA;
2. BlackBox - с функцией Keys.SStringCompare;
3. ASM - с функцией Keys.ASStringCompare, реализованной как code на ассемблере.
Результаты для строк приведены на рисунке.

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

Теперь можно сказать и сравнении с stl в части сортировок.
В c++ код можно посмотреть в MyBench.zip/list.cpp.


В BlackBox Stl быстрая сортировка реализована по нерекурсивному алгоритму ADruS2_Sorts из Н.Вирт "Алгоритмы и структуры данных". Там есть метод "традиционной" быстрой сортировки QSort, демонстрирующий схожую динамику.

Ниже приведены времена сортировки для количества элементов 100000 300000 1000000

Вариант с BlackBox лучше на 26% для 8-бит и 3% для 16-бит

На всякий случай: Transparent Architecture использует coroutines. У меня работает на версии ВВ 1.7.1.

Пример - Maps.Map

Алгоритм осуществляет вставку в отсортированной красно-черное дерево и печатает алфавитном порядке.

Тип Maps.Multimap делает то же, но с удалением повторных вхождений.

Теперь можно сказать и сравнении с stl в части вставки в красно-черное дерево.
В c++ код можно посмотреть в MyBench.zip/map.cpp.

В BlackBox это SclObxBenchmarks.CSLongMap с аналогичным алгоритмом и вызовом map.Insert.

Ниже приведены времена вставки в красно-черное дерево для числа элементов 100000 300000 1000000 3000000

Достигнуто улучшение 41% для 8-битовых строк и 55% для 16-битовых.

Вообще говоря, результат замеров имеет мало смысла, если не проведён анализ *во что упирается* та или иная реализация. Сейчас у вас приведены какие-то цифры, но, при беглом просмотре кода складывается ощущение, что C++ и SCL программы делали совсем разные действия.

Например:

1) В C++ коде вы создаёте string, потом вызываете srnd.resize(256);
А по факту, у строки используются первые 4-5 символов.
Строки C++ могут содержать нулевые символы, поэтому операция сравнения строк вынуждена просматривать строку целиком.

Судя по BlackBox коду, сравнение в BlackBox останавливается на этом самом нулевом символе:


2) По-моему, сами ключи для теста генерируются разным образом.
В BlackBox так RandString(SHORT(ENTIER(32767*Tb.Uniform())), el.ri.name);, а в C++ так: RandString(rand(), w);
Насколько я понимаю, BlackBox вызывается с SHORT, а C++ с аргументом int.
Значит, в C++ на само построение ключей банально больше времени нужно, и сам поиск по дереву дольше, т.к. в дереве больше ключей

Поправите?
Новый замер сделаете?

И, да, раз уж используете C++11, то замер времени можно делать через



На моём macOS #include <windows.h>, по понятным причинам, не работает.

Шикарно, только нужно не забыть упомянуть, что std::list это двусвязный список (т.е. без возможности обращения по индексу, но зато с быстрой вставкой в произвольное место), а в BlackBox у вас что-то среднее между vector'ом и связным списком (вроде, есть ссылки next-prev, но обращаетесь по индексам, значит это явно не двусвязный список).
Как-никак, а BlackBox сортировка обращается к элементам по индексам. Т.е. снова сравнение яблок с фломастерами.