OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Среда, 21 Август, 2019 16:27

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




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

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 72
Дмитрий Дагаев писал(а):
Теперь о сравнении с stl (mingw32, o3) в части быстродействия. Рассматривалась задача вычисления суммы значений
...
Таким образом, реализация вектора для BlackBox показывает в данном тесте на 40% выигрыш по сравнению с лучшим результатом для c++ std::vector.


Слушайте, а вы не перепутали опции -O3 и -o3?
Как-никак, регистр имеет значение. Первая указывает на уровень оптимизаций, а вторая на имя результирующего файла.

Дело в том, что GCC вообще оптимизирует в ноль ваш вариант bm_foreach_lambda.

Подтверждение:
Заходим на https://godbolt.org/
Пишем такой код:
Код:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int COUNT = 10000000;
vector<int> vec;

int RandomNumber () {
        static int s = 0;
        return (s++ % 100);
}

typedef void (*BmProc)(void);

void bm_foreach_lambda()
{
        int sum = 0;
        for_each(vec.begin(), vec.end(), [&sum](int i) {
                sum += i;
        });
}

void RunOne(BmProc prc, const char *name)
{
//        auto start_time = chrono::high_resolution_clock::now();
//      GetSystemTimeAsFileTime(&t0.ft);
        (*prc)();
//      GetSystemTimeAsFileTime(&t1.ft);
//       auto end_time = chrono::high_resolution_clock::now();
//        std::cout << name << " t=" << chrono::duration_cast<chrono::microseconds>(end_time - start_time).count() << " us" << std::endl;
}

int main ()
{
        vec.resize(COUNT);
        generate(vec.begin(), vec.end(), RandomNumber);
#ifdef BM_FOREACH_LAMBDA
        RunOne(bm_foreach_lambda, "Foreach lambda");
#endif
}


Справа в поле "Compiler options" указываем -O3

И в результате видим, что функции bm_foreach_lambda и RunOne состоят из одной инструкции. Ни о какой итерации речи там, разумеется, не идёт.
Код:
bm_foreach_lambda():
  rep ret
RunOne(void (*)(), char const*):
  jmp rdi


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

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 369
Откуда: Москва
Цитата:
Строки C++ могут содержать нулевые символы, поэтому операция сравнения строк вынуждена просматривать строку целиком

Вы в этом уверены? А документация говорит про std.size().
Цитата:
Судя по BlackBox коду

Сравнение осуществляется ассемблерной процедурой AsmStringCompare, AsmSStringCompare
Цитата:
В BlackBox так RandString(SHORT(ENTIER(32767*Tb.Uniform())), el.ri.name);, а в C++ так: RandString(rand(), w);
Насколько я понимаю, BlackBox вызывается с SHORT, а C++ с аргументом int.

ENTIER(x) возвращает тип LONGINT, SHORT(ENTIER()) - возвращает INTEGER. См. BlackBox Languare Reference

Цитата:
результат замеров имеет мало смысла, если не проведён анализ *во что упирается* та или иная реализация

В части деревьев еще раз (см. Maps.odc) отмечу структурные различия.
----------
Модуль SclMaps используется для реализации пользовательских типов со следующей функциональностью Maps и MultiMaps. Все эти типы абстрактны и являются контейнерами. Расширенный пользователем тип должен быть реализован согласно следующему шаблону:
%Elem = RECORD (Maps.Elem)
(* далее любые данные возможны *)
END;
%ElemPArr = POINTER TO ARRAY OF %Elem;
%MyList = RECORD (Lists.List)
data*: POINTER TO ARRAY OF %ElemPArr;
(* далее любые данные возможны *)
END;
Первое поле в записи должно быть определено как "exported POINTER TO ARRAY OF %ElemPArr", где . %ElemPArr представляет собой указатель на массив элементов %Elem.
----------
При добавлении элемента в дерево аллокирование памяти осуществляется для массива n_cols, это более эффективно, чем для отдельного элемента.


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

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
У меня есть предложение по названию. Оберон не проходил никаких мероприятий по стандартизации. Поэтому, слово "стандартный" может вводить в заблуждение. И "библиотека" обычно в Оберонах не используется. Как насчёт просто"классические коллекции"?


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

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 369
Откуда: Москва
Цитата:
Дело в том, что GCC вообще оптимизирует в ноль ваш вариант bm_foreach_lambda

Я не использовал gcc, если вы заметили.

И ссылался на статью, где gcc для этих целей использовано. Можете поспорить с тем автором.

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

По-существу, я реализацию списка оставляю за собой. Вставка в этот список, как полагается, O(1).

По-форме, Вам, видимо, будет интереснее вести дискуссию с людьми, больше подходящими Вам по возрасту и темпераменту. Мне - нет.


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

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 72
Дмитрий Дагаев писал(а):

Уверен.

Такой код выводит, что size для двух строк равно 256
Код:
#include <iostream>
#include <map>
#include <string>

using namespace std;


void RandString(int irand, wstring &srnd)
{
        const int CM = 50, NC = 200, NMAX = NC+CM;
        srnd.resize(256);
        int j = 0;
        while (irand != 0) {
                srnd[j] = (wchar_t)(irand % NC + CM);
                ++j;
                irand = irand / NC;
        }
}

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;
        }
}

int main()
{
        string s;
        wstring ws;
        RandSString(rand(), s);
        RandString(rand(), ws);
        cout << "s.size() = "<< s.size() << std::endl;
        cout << "ws.size() = "<< ws.size() << std::endl;
        return 0;
}


Дмитрий Дагаев писал(а):
Сравнение осуществляется ассемблерной процедурой AsmStringCompare, AsmSStringCompare

Которая тоже останавливается на 1-ом нулевом символе.


Дмитрий Дагаев писал(а):
Владимир Ситников писал(а):
В BlackBox так RandString(SHORT(ENTIER(32767*Tb.Uniform())), el.ri.name);, а в C++ так: RandString(rand(), w);

ENTIER(x) возвращает тип LONGINT, SHORT(ENTIER()) - возвращает INTEGER. См. BlackBox Languare Reference

И всё-таки, какое значение возвращает Tb.Uniform ?
Это значение от 0 до 1? Или какое?
Если от 0 до 1, тогда вся конструкция SHORT(ENTIER(32767*Tb.Uniform())) будет принимать значения от 0 до 32767, т.е. количество ключей будет меньше, чем в случае C++.
Всё-таки лучше использовать один и тот же генератор случайных чисел, чтобы сравнивать не генераторы, а непосредственно структуры данных.

Дмитрий Дагаев писал(а):
В части деревьев еще раз (см. Maps.odc) отмечу структурные различия.

А неважно что там в коде написано. Важно во что в результате скомпилируется и на что именно будет тратиться процессорное время.
В случае C++ всё время уходит в сравнение строк. Ещё бы. Приходится сравнивать по 256 символов.

А BlackBox останавливается на первом нулевом символе.


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

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 72
Дмитрий Дагаев писал(а):
Цитата:
Дело в том, что GCC вообще оптимизирует в ноль ваш вариант bm_foreach_lambda

Я не использовал gcc, если вы заметили.

А что же вы использовали?
Mingw32?
Это же и есть GCC.


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

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 369
Откуда: Москва
Valery Solovey писал(а):
У меня есть предложение по названию. Оберон не проходил никаких мероприятий по стандартизации. Поэтому, слово "стандартный" может вводить в заблуждение. И "библиотека" обычно в Оберонах не используется. Как насчёт просто"классические коллекции"?

Может быть, Вы правы. Только я уже назвал и у Цинна отослал. А стандартизация... Я в атомной отрасли работаю, и тут огромная инфраструктура: контроль качества, международные рабочие группы МАГАТЭ, органы по сертификации и проч. Кто будет стандартизацией заниматься?


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

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 72
Дмитрий Дагаев писал(а):
И ссылался на статью, где gcc для этих целей использовано. Можете поспорить с тем автором.

А зачем мне с ним спорить?

Вы сравнили C++ и BlackBox, и при этом показали код, которым проводили замеры.
Так оказалось, что это не сравнение, а просто два разных кода. Для BlackBox одно, а для C++ совсем другое.
Ну и фиг бы с ним, но вы же планомерно рисуете полученные цифры от BB и C++ на один график. И пишете утверждения в духе "BB работает быстрее". Этим вводите в заблуждение тех, кто может подумать, что "BB работает быстрее".


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

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 369
Откуда: Москва
Владимир Ситников писал(а):
Дмитрий Дагаев писал(а):
И ссылался на статью, где gcc для этих целей использовано. Можете поспорить с тем автором.

А зачем мне с ним спорить?

Вы сравнили C++ и BlackBox, и при этом показали код, которым проводили замеры.
Так оказалось, что это не сравнение, а просто два разных кода. Для BlackBox одно, а для C++ совсем другое.
Ну и фиг бы с ним, но вы же планомерно рисуете полученные цифры от BB и C++ на один график. И пишете утверждения в духе "BB работает быстрее". Этим вводите в заблуждение тех, кто может подумать, что "BB работает быстрее".


Я привожу условия и замеры, которые проводились в данных условиях. Можно с ними спорить, в части size(256) я готов с Вами согласиться. В части разного числа ключей - Вы не правы, т.к. irand % NC дает NC ключей. Могут быть другие тесты, проведенные уже не мной.

Теперь про сравнение C++ и BlackBox в плане быстродействия. Я не переходил от частного к общему, утверждая, что BB работает быстрее. Более того, всегда было (и есть) наоборот. У c++ компиляторов есть множество способов оптимизации, "разогнать" его проще. Оптимизированный компилятор Оберона это - XDS.

При разработке библиотеки было очевидно, что придется конкурировать в заведомо проигрышной ситуации, памятуя, что компилятор для BlackBox проиграет тому же gcc в плане оптимизации, да еще с учетом разных аппаратных архитектур. Это - вопрос больших компаний. Мои действия будут стандартными для свободного ПО: буду разрабатывать при наличии производственной необходимости, при наличии возможности - публиковать.


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

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 72
Дмитрий Дагаев писал(а):
Я привожу условия и замеры, которые проводились в данных условиях.

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

Дмитрий Дагаев писал(а):
Можно с ними спорить, в части size(256) я готов с Вами согласиться.

Т.е. методологическая ошибка номер раз.

Дмитрий Дагаев писал(а):
В части разного числа ключей - Вы не правы, т.к. irand % NC дает NC ключей.

Вы либо запутались, либо лукавите.

Смотрим на код:
Код:
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;
        }
}

1) Очевидно, что количество различных ключей (== количество различных строк на выходе) не может быть больше количества различных значений irand, попадающих на вход функции RandSString. Верно? Это нужно доказывать? Ну, это же чистая функция без состояния, т.е. каждому значению аргумента будет соответствовать одна фиксированная результирующая строка, и таким образом, количество результирующих строк не может превысить количество различных входных значений. Принцип Дирихле или что-то типа того.

Тут у вас вторая ошибка: в C++ используется 32bit случайное значение, а в BlackBox -- 16 bit. Я уже цитировал: Uniform возвращает значение от 0 до 1, вы его умножаете на 32767, т.е. никак не можете получить больше 32767 различных значений.

2) Легко заметить, что количество букв определяется значением irand. Если irand<200, то будет одна буква. Если irand < 200*200, то будет 2 буквы.
Кстати, в случае BlackBox, похоже, в ключе всегда одна-две буквы (т.к. аргумент не превышает 32767)
В C++ же случае irand может быть порядка 32bit, т.е. нужно 4-5 раз прокручивать irand = irand / NC, чтобы irand оказалось равно нулю.
Получается, что в C++ используются более длинные ключи, что в свою очередь, влечёт за собой более длительные операции сравнения. Ну, технически, наверное, разницы между двумя или четыремя буквами для современных процессоров нет, но всё же не стоит на ровном месте в сравнение закладывать различие.

Дмитрий Дагаев писал(а):
Теперь про сравнение C++ и BlackBox в плане быстродействия. Я не переходил от частного к общему, утверждая, что BB работает быстрее.

Я про общее и не говорил. Всё, что я тут пишу относится именно к вашему коду.
У вас "частные" случаи для BlackBox и C++ совсем разные. И, похоже, вы забыли включить -O3.


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

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 369
Откуда: Москва
Цитата:
Тут у вас вторая ошибка: в C++ используется 32bit случайное значение, а в BlackBox -- 16 bit. Я уже цитировал: Uniform возвращает значение от 0 до 1, вы его умножаете на 32767, т.е. никак не можете получить больше 32767 различных значений.

The rand function returns a pseudorandom integer in the range 0 to RAND_MAX (32767).
https://msdn.microsoft.com/en-us/library/398ax69y.aspx


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

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 72
Дмитрий Дагаев писал(а):
The rand function returns a pseudorandom integer in the range 0 to RAND_MAX (32767).
https://msdn.microsoft.com/en-us/library/398ax69y.aspx


Да в Mingw32 RAND_MAX действительно равно 32767.
Технически, RAND_MAX зависит от реализации. В Linux это 32 бита.

Получается, количество ключей совпадает, и вопрос в том, действительно ли использовалось -O3, и в 256 буквах.


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

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


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

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 72
Comdiv писал(а):
Надо бы ещё не забыть, что mingw32 gcc - это, всё-таки, далеко не то же самое, что gcc в GNU/Linux. Обычно, он ещё и основывается на сильно более старом коде, чем компиляторы, доступные в GNU/Linux.

Оно-то правда, но, если компилятор умеет C++11, то он не такой-то и старый.
На godbolt.org минимальная версия gcc, которая умеет -std=c++11 это 4.7.1, и эта версия оптимизирует "сумму массива" в пустую функцию
Ещё бы. Функция написана так, что результат сложения вообще никак не используется, и компилятор правильно понял, что функция ничего не делает. Чтобы такого не происходило нужно не просто выполнять бесполезную работу, а, например, возвращать вычисленную сумму и распечатывать её после замеров времени.


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

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 369
Откуда: Москва
Владимир Ситников писал(а):
Получается, количество ключей совпадает, и вопрос в том, действительно ли использовалось -O3, и в 256 буквах.

Я еще раз проверил и уточняю.
Оптимизация не использовалась, ни -O3, ни какая другая.
При установке длины строки числом букв изменились результаты Maps.
Вложение:
C_BB_Maps.png
C_BB_Maps.png [ 22.59 КБ | Просмотров: 1808 ]

Показывает улучшение 19% для 8-битовых строк и 10% для 16-битовых.


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

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 72
Дмитрий Дагаев писал(а):
Оптимизация не использовалась, ни -O3, ни какая другая.

Точно? А почему без оптимизаций? Зачем тогда в BlackBox на ассемблере пишете?

В документации Scl/Docu/Bench-Marks.odc вы указываете:
Цитата:
Scl Benchmarks
Several tests we performed to compare Scl with C++ Standard Template Library. Mingw32 compiler for windows was used with -std=c++11 -o3 options.

Ну и в сообщении
Дмитрий Дагаев писал(а):
Суббота, 10 Март, 2018 20:18
Теперь о сравнении с stl (mingw32, o3) в части быстродействия.

Что тут означало слово "o3" ?


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

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 369
Откуда: Москва
Точно. Документ я обновлю с оказией.


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

Зарегистрирован: Вторник, 26 Январь, 2010 09:31
Сообщения: 714
Откуда: Барнаул
А компилятор в ББ делает кое-какую оптимизацию.
Вообще в данном случае про сравнение производительности вообще не стоит говорить


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

Зарегистрирован: Вторник, 01 Март, 2011 09:34
Сообщения: 369
Откуда: Москва
Kemet писал(а):
Вообще в данном случае про сравнение производительности вообще не стоит говорить

Согласен, более того, отделить вклад Scl от вклада компилятора невозможно. Scl я как-то оптимизировал, компилятор не рассматривал. Поэтому - вот есть данные, они получены в таких-то условиях.


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

Зарегистрирован: Вторник, 27 Февраль, 2018 09:18
Сообщения: 72
Kemet писал(а):
А компилятор в ББ делает кое-какую оптимизацию.
Вообще в данном случае про сравнение производительности вообще не стоит говорить

Сравнение производительности делать стоит (чтобы убедиться, что оно не в 100500 раз медленнее простой программы на C++).
Но вот говорить "SclVectors demonstrate 40% better results against 'std::vector without iterators', especially with array bounds check as a bonus." уж точно не стоит. Равно как и говорить "более простые решения более эффективны в плане быстродействия..." тоже не стоит.


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

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


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

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


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

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