OberonCore
https://forum.oberoncore.ru/

Standard Container Library
https://forum.oberoncore.ru/viewtopic.php?f=47&t=6234
Страница 1 из 6

Автор:  Дмитрий Дагаев [ Суббота, 10 Март, 2018 10:21 ]
Заголовок сообщения:  Standard Container Library

Публикую систему 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.

Вложения:
scl.txt [143.26 КБ]
Скачиваний: 675

Автор:  Дмитрий Дагаев [ Суббота, 10 Март, 2018 10:40 ]
Заголовок сообщения:  Re: Standard Container Library

Пример - Vectors.Vector
Код:
MyRec = RECORD
   i1: INTEGER;
END;
MyVec = RECORD (Vectors.Vector)
   data*: POINTER TO ARRAY OF MyRec;
END;

Код:
vec.Init(10);
Log.String("Pointer Initial Size,Capacity="); Log.Int(vec.size); Log.Int(vec.capacity); Log.Ln;
mr.i1 := 109; vec.Set(9, mr);
mr.i1 := 110; vec.Set(10, mr);
mr.i1 := 111; vec.Set(11, mr);
Log.String("Pointer To Vector Size,Capacity="); Log.Int(vec.size); Log.Int(vec.capacity); Log.Ln;
FOR j := 0 TO vec.size-1 DO
   Log.Int(j); Log.String(" ="); Log.Int(vec.data[j].i1); Log.Ln;
END;

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

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

Автор:  Comdiv [ Суббота, 10 Март, 2018 14:54 ]
Заголовок сообщения:  Re: Standard Container Library

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

Автор:  Дмитрий Дагаев [ Суббота, 10 Март, 2018 15:27 ]
Заголовок сообщения:  Re: Standard Container Library

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

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

Автор:  Дмитрий Дагаев [ Суббота, 10 Март, 2018 15:52 ]
Заголовок сообщения:  Re: Standard Container Library

Пример - Lists.IndexedList
Код:
SearchElem = RECORD (Lists.Elem)
   ri-: Keys.SString32Key;
   i1: INTEGER;
END;
SearchElemPArr = POINTER TO ARRAY OF SearchElem;
MySearchList = RECORD (Lists.IndexedList)
   data*: POINTER TO ARRAY OF SearchElemPArr;
END;

Элементы List, Queue, Deque, Stack работают с указателем на массив указателей POINTER TO ARRAY OF %SearchElemPArr. Функцию NEW экономичнее вызывать для массива, чем для каждого его элемента.
Поле Keys.SString32Key означает наличие строкового ключа, по которому можно проводить сравнение. Где сравнение, там и сортировка, и бинарный поиск.
Код:
li.Init(params);
el.ri.name := "orange"; el.i1 := 2; li.PushBack(el);
el.ri.name := "red"; el.i1 := 1; li.PushFront(el);
el.ri.name := "yellow"; el.i1 := 3; li.Insert(Lists.iterNil, el);
el.ri.name := "green"; el.i1 := 4; li.PushBack(el);
el.ri.name := "lightblue"; el.i1 := 5; li.PushBack(el);
el.ri.name := "blue"; el.i1 := 6; li.PushBack(el);
li.Sort;
el.ri.name := "lightblue";
found := li.Find(el, it);
Log.String("lightblue Find="); Log.Bool(found); Log.Int(it.r);  Log.Int(it.c); Log.Char(' ');

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

Если понадобятся другие ключи, не целые и не строки, нужно добавить функцию сравнения аналогично тому, как это сделано для LongKey:
Код:
PROCEDURE LongCompare (VAR n1: LONGINT; VAR n2: LONGINT): INTEGER;
BEGIN
   RETURN SHORT(n1-n2)
END LongCompare;
PROCEDURE (VAR ri: LongKey) GetComparator* (VAR compare: Base.Comparator);
BEGIN
   SYSTEM.PUT(SYSTEM.ADR(compare), SYSTEM.ADR(LongCompare));
END GetComparator;

Автор:  Comdiv [ Суббота, 10 Март, 2018 17:25 ]
Заголовок сообщения:  Re: Standard Container Library

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

Цитата:
1. operator[] имеет определенный overhead, т.к. это метод, и быстродействие доступа к элементам вектора хуже, чем доступ к элементам массива c++;
Тогда понятно. Но это статический метод на уровне заголовочных файлов, что подразумевает возможность эффективного встраивания без паразитического кода. На моём опыте использования vector на высоких настройках оптимизации показывал скорость, идентичную работе с массивами.

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

Автор:  Дмитрий Дагаев [ Суббота, 10 Март, 2018 20:18 ]
Заголовок сообщения:  Re: Standard Container Library

Теперь о сравнении с stl (mingw32, o3) в части быстродействия. Рассматривалась задача вычисления суммы значений вектора целых чисел.
Вариант 1 - Vector Iterators
Код:
vector<int> vec;
auto end = vec.end(); int sum = 0;
for(auto i = vec.begin(); i != end; ++i)
   sum += *i;


Вариант 2 - Vector No Iterators
Код:
int sum = 0;
for(int i = 0; i < COUNT; ++i)
   sum += vec[i];


Вариант 3 - Array from Vector
Код:
int sum = 0;
int *array = &vec[0];
for(int i = 0; i < COUNT; ++i) {
   sum += array[i];
};


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

Результаты сравнения:
Вложение:
C_BB_Vectors.png
C_BB_Vectors.png [ 11.56 КБ | Просмотров: 3112 ]


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

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

Автор:  Comdiv [ Суббота, 10 Март, 2018 20:30 ]
Заголовок сообщения:  Re: Standard Container Library

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

Автор:  Дмитрий Дагаев [ Суббота, 10 Март, 2018 21:09 ]
Заголовок сообщения:  Re: Standard Container Library

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

Вложения:
MyBench.zip [2.56 КБ]
Скачиваний: 96

Автор:  Comdiv [ Суббота, 10 Март, 2018 22:25 ]
Заголовок сообщения:  Re: Standard Container Library

Где взять Tb?

Автор:  Дмитрий Дагаев [ Суббота, 10 Март, 2018 22:29 ]
Заголовок сообщения:  Re: Standard Container Library

Comdiv писал(а):
Где взять Tb?

Transparent Architecture - communication SW for distributed systems.

Автор:  Дмитрий Дагаев [ Суббота, 10 Март, 2018 22:33 ]
Заголовок сообщения:  Re: Standard Container Library

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

Автор:  Дмитрий Дагаев [ Воскресенье, 11 Март, 2018 10:34 ]
Заголовок сообщения:  Re: Standard Container Library

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

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

Автор:  Дмитрий Дагаев [ Воскресенье, 11 Март, 2018 10:48 ]
Заголовок сообщения:  Re: Standard Container Library

Теперь можно сказать и сравнении с stl в части сортировок.
В c++ код можно посмотреть в MyBench.zip/list.cpp.
Код:
list<string> sli;
...
sli.sort();


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

Ниже приведены времена сортировки для количества элементов 100000 300000 1000000
Вложение:
C_BB_Lists.png
C_BB_Lists.png [ 18.91 КБ | Просмотров: 3070 ]

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

Автор:  arlean1 [ Воскресенье, 11 Март, 2018 14:20 ]
Заголовок сообщения:  Re: Standard Container Library

Дмитрий Дагаев писал(а):


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

Автор:  Дмитрий Дагаев [ Понедельник, 12 Март, 2018 11:42 ]
Заголовок сообщения:  Re: Standard Container Library

Пример - Maps.Map
Код:
Elem = RECORD (Maps.Elem)
   ri-: Keys.String32Key;
   i1: INTEGER;
END;
ElemPArr = POINTER TO ARRAY OF Elem;
MyMap = RECORD (Maps.Map)
   data*: POINTER TO ARRAY OF ElemPArr;
END;

Алгоритм осуществляет вставку в отсортированной красно-черное дерево и печатает алфавитном порядке.
Код:
map.Init(Maps.defaults);
el.i1 := 11; el.ri.name := "eleven"; map.Insert(el);
el.i1 := 12; el.ri.name := "twelve"; map.Insert(el);
el.i1 := 13; el.ri.name := "thirteen"; map.Insert(el);
el.i1 := 14; el.ri.name := "fourteen"; map.Insert(el);
Log.String("Map rows"); Log.Bool(map.data # NIL); Log.Int(LEN(map.data)); Log.Int(map.size);
Log.Int(map.capacity);
Log.String(" cols"); Log.Bool(map.data[0] # NIL); Log.Int(LEN(map.data[0])); Log.Ln;
map.First(it);
WHILE it.r >= 0 DO
   Log.String("map["); Log.String(map.data[it.r][it.c].ri.name); Log.String("]=");
   Log.Int(map.data[it.r][it.c].i1); Log.Ln;
   map.Next(it);
END;

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

Автор:  Дмитрий Дагаев [ Понедельник, 12 Март, 2018 11:55 ]
Заголовок сообщения:  Re: Standard Container Library

Теперь можно сказать и сравнении с stl в части вставки в красно-черное дерево.
В c++ код можно посмотреть в MyBench.zip/map.cpp.
Код:
void RandSString(int irand, string &srnd)
{
   const int CM = 50, NC = 200, NMAX = NC+CM;
   srnd.resize(256);
   int j = 0;
   while (irand != 0) {
      srnd[j] = (char)(irand % NC + CM);
      ++j;
      irand = irand / NC;
   }
}
while (j < maxlen) {
   RandSString(rand(), s);
   smap[s] = j;
   ++j;
}

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

Ниже приведены времена вставки в красно-черное дерево для числа элементов 100000 300000 1000000 3000000
Вложение:
C_BB_Maps.png
C_BB_Maps.png [ 19.6 КБ | Просмотров: 3012 ]

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

Автор:  Владимир Ситников [ Понедельник, 12 Март, 2018 12:57 ]
Заголовок сообщения:  Re: Standard Container Library

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


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

Например:

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

Судя по BlackBox коду, сравнение в BlackBox останавливается на этом самом нулевом символе:
Код:
   (* ========== Short String Key implementation ========== *)
   PROCEDURE SStringCompare (s1, s2: SString256KeyUPtr): INTEGER;
      VAR j, rc: INTEGER;
   BEGIN
      j := -1;
      REPEAT
         INC(j);
         rc := ORD(s1.name[j]) - ORD(s2.name[j]);
      UNTIL (rc # 0) OR (s1.name[j] = 0X);
      RETURN rc
   END SStringCompare;


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

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

Автор:  Владимир Ситников [ Понедельник, 12 Март, 2018 12:59 ]
Заголовок сообщения:  Re: Standard Container Library

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

Код:
auto start_time = chrono::high_resolution_clock::now();
...
auto end_time = chrono::high_resolution_clock::now();
std::cout << name << " t=" << chrono::duration_cast<chrono::microseconds>(end_time - start_time).count() << " us";


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

Автор:  Владимир Ситников [ Понедельник, 12 Март, 2018 13:29 ]
Заголовок сообщения:  Re: Standard Container Library

Дмитрий Дагаев писал(а):
Теперь можно сказать и сравнении с stl в части сортировок.
В c++ код можно посмотреть в MyBench.zip/list.cpp.
Код:
list<string> sli;
...
sli.sort();


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


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

Страница 1 из 6 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/