OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Понедельник, 22 Октябрь, 2018 23:28

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 96 ]  На страницу 1, 2, 3, 4, 5  След.
Автор Сообщение
 Заголовок сообщения: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 10:21 

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 277
Откуда: Москва
Публикую систему 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 КБ]
Скачиваний: 206
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 10:40 

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 277
Откуда: Москва
Пример - 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 из базового класса.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 14:54 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 15:27 

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 277
Откуда: Москва
Библиотека стандартных контейнеров, таких, как Vector, List, Map.
Чем лучше? Я не говорил, что лучше, я говорил, что на других принципах. Буду выкладывать информацию (и по эффективности тоже), что-то отвечу предметно, и Вы сможете сравнить.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 15:52 

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 277
Откуда: Москва
Пример - 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;


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 17:25 

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 20:18 

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 277
Откуда: Москва
Теперь о сравнении с 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 КБ | Просмотров: 1160 ]


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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 20:30 

Зарегистрирован: Четверг, 08 Май, 2008 19:13
Сообщения: 708
Откуда: Киев
Это интересно, можно выложить эти тесты? Но собирать в mingw32 не обещаю, использую GNU/Linux.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 21:09 

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


Вложения:
MyBench.zip [2.56 КБ]
Скачиваний: 31
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 22:25 

Зарегистрирован: Четверг, 08 Май, 2008 19:13
Сообщения: 708
Откуда: Киев
Где взять Tb?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 22:29 

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 277
Откуда: Москва
Comdiv писал(а):
Где взять Tb?

Transparent Architecture - communication SW for distributed systems.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Суббота, 10 Март, 2018 22:33 

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 277
Откуда: Москва
Еще ссылка на Scl - Standard Container Library, Component Pascal Collection, Helmut Zinn.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Воскресенье, 11 Март, 2018 10:34 

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Воскресенье, 11 Март, 2018 10:48 

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 277
Откуда: Москва
Теперь можно сказать и сравнении с 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 КБ | Просмотров: 1118 ]

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Воскресенье, 11 Март, 2018 14:20 

Зарегистрирован: Среда, 31 Январь, 2018 19:54
Сообщения: 39
Дмитрий Дагаев писал(а):


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Понедельник, 12 Март, 2018 11:42 

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 277
Откуда: Москва
Пример - 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 делает то же, но с удалением повторных вхождений.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Понедельник, 12 Март, 2018 11:55 

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 277
Откуда: Москва
Теперь можно сказать и сравнении с 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 КБ | Просмотров: 1060 ]

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Понедельник, 12 Март, 2018 12:57 

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 53
Дмитрий Дагаев писал(а):
Теперь можно сказать и сравнении с 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 13:00, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Standard Container Library
СообщениеДобавлено: Понедельник, 12 Март, 2018 12:59 

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 53
И, да, раз уж используете 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>, по понятным причинам, не работает.


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

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 53
Дмитрий Дагаев писал(а):
Теперь можно сказать и сравнении с stl в части сортировок.
В c++ код можно посмотреть в MyBench.zip/list.cpp.
Код:
list<string> sli;
...
sli.sort();


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


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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 96 ]  На страницу 1, 2, 3, 4, 5  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2018, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB