Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Клуб программистов > Свободное общение
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 01.08.2018, 11:08   #11
eduard-fe
 
Аватар для eduard-fe
 
Регистрация: 23.07.2018
Сообщений: 8
По умолчанию

To: kvitaliy

Пока подготовил файл только под линукс (отключал зависимости от личных библиотек, дополнял разными вариантами подготовки файлов данных, их просмотра и сравнения).

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

Сейчас я пишу код для автоматической настройки параметров, а потом и проверю его на рабочей мощной машинке и слабенькой домашней. Тогда и вышлю версию для виндоус. Ранее высылать действительно нет смысла.

Цитата:
Сообщение от rrrFer Посмотреть сообщение
У меня есть.
Я уже обещал другому человеку.

Цитата:
Сообщение от rrrFer Посмотреть сообщение
Если у вас не SSD диск - то значительную часть этих 4 секунд будет именно файл считываться и записываться. Операции с диском медленные же.
Время загрузки бинарного файла заданного размера с обычного диска 0.18 с, повторной загрузки 0.05 с, что намного меньше времени сортировки 3.7 с. Медленная загрузка характерна для текстового файла, но и там замедление обусловлено не диском, а конвертацией из строкового представления данных в машинное.

Цитата:
Сообщение от rrrFer Посмотреть сообщение
Мало того, мы тут замечали, что вижуал студия распараллеливает автоматически (по крайней мере векторизует) и в документации нашли, что по умолчанию автоматический векторизатор включен )). Отсюда - код может начать работать в несколько раз быстрее если написан так, что компилятор обнаружит возможность распараллеливания. И это может случаться или не случаться внезапно )). В G++ вроде как распараллеливание включается на -O3.
Проверил, у меня -O2.

Цитата:
Сообщение от WorldMaster Посмотреть сообщение
Интересно бы на код посмотреть. Конечно может быть там и правда что-то выдающееся но странно что за все время развития информационных технологий никто не придумал подобное. Вроде великие умы занимались этой задачей ..
Я не претендую на новый алгоритм, это лишь реализация давно известного, которая лишь немного лучше подстраивается под "рваную" (L1, L2, L3) архитектуру.

Цитата:
Сообщение от WorldMaster Посмотреть сообщение
Вы говорите что код не покажете. А каким образом вы предлагаете оценить его качественность так сказать. Все равно нужно когда то показать код. А то окажется что у вас там метод дихотомии просто распаралеленн на несколько потоков.
Говорить о параллельной версии будем, когда она станет достаточно шустрой, пока она сырая.

Код автоматической настройки под процессор готов. На i7 настраивается даже лучше, чем руками. Версия для Win7 готова, жду ответа от kvitaliy.

Чтоб добавить что-то к своему сообщению, используйте кнопку "Правка", а не пишите несколько сообщений подряд.
Sincerely yours,
I am utterly indifferent to you.

Последний раз редактировалось Вадим Мошев; 03.08.2018 в 17:05.
eduard-fe вне форума Ответить с цитированием
Старый 07.08.2018, 12:59   #12
eduard-fe
 
Аватар для eduard-fe
 
Регистрация: 23.07.2018
Сообщений: 8
По умолчанию

Исправил ошибку генерации случайных данных, указанную by kvitaliy (ранее использовал rand(), а у него диапазон чисел в пределах 65 тысяч). На данных в диапазоне [-2 млрд ..+2 млрд] скорость сортировки меньше (см. ниже).

Выкладываю также результаты по параллельной сортировке.

Код:
sequental
                    std::sort  std::stable_sort        sort                  ratio
--------------------------------------------------------------------------------
'10^8'             7.891279       7.969707       3.859269    2.04x       2.06x
'10^8(dup)'     5.772722       7.397444       1.878287    3.07x       3.93x

parallel
                     std::sort    std::stable_sort      sort 
--------------------------------------------------------------------------------
'10^8'            1.833703       2.045609       1.228664     1.49x       1.66x
'10^8(dup)'    1.299971       1.653642       0.802673     1.61x       2.06x
Файл '10^8(dup)' содержит 100 млн чисел многие из которых совпадают друг с другом (10000 уникальных чисел, каждое из которых дублировано 1000 раз). Подобные наборы данных используются для проверки эффективности стабильной сортировки, где дублирование замедляет работу.

Параллельная сортировка для стандартных методов сделана как описано в https://stackoverflow.com/questions/...mented-already (2-й ответ, через omp).
Sincerely yours,
I am utterly indifferent to you.

Последний раз редактировалось eduard-fe; 08.08.2018 в 07:37. Причина: исправлены данные по параллельной сортировке
eduard-fe вне форума Ответить с цитированием
Старый 09.08.2018, 10:32   #13
eduard-fe
 
Аватар для eduard-fe
 
Регистрация: 23.07.2018
Сообщений: 8
По умолчанию

(Не разрешает редактировать старый пост, потому добавил новый.)

Выполнил параллелизацию своего алгоритма полностью (нет только векторизации), он еще добавил в скорости в 1.5 раза.

Код:
(было)
                     std::sort    std::stable_sort      sort 
--------------------------------------------------------------------------------
'10^8'            1.833703       2.045609       1.228664     1.49x       1.66x
'10^8(dup)'    1.299971       1.653642       0.802673     1.61x       2.06x

(стало)
--------------------------------------------------------------------------------
'10^8'            1.636701       1.772416       0.897163     1.82х       1.97х
'10^8(dup)'    1.172392       1.598781       0.573806     2.04х       2.78х
и при подстройке параметров алгоритма под параллельное выполнение:
Код:
(стало)
--------------------------------------------------------------------------------
'10^8'            1.634384       1.777608       0.812924     2.01х       2.18х
'10^8(dup)'    1.171181       1.611976       0.469431     2.49х       3.43х
Sincerely yours,
I am utterly indifferent to you.

Последний раз редактировалось eduard-fe; 09.08.2018 в 11:52. Причина: добавление данных
eduard-fe вне форума Ответить с цитированием
Старый 15.08.2018, 09:34   #14
Ципихович Эндрю
Старожил
 
Регистрация: 24.01.2011
Сообщений: 3,034
По умолчанию

до сих пор не озвучена цена
выложите пример для теста для винды, спс
Ципихович Эндрю вне форума Ответить с цитированием
Старый 15.08.2018, 17:16   #15
сфинкс
Форумчанин
 
Аватар для сфинкс
 
Регистрация: 17.06.2012
Сообщений: 953
По умолчанию

фипс
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
сфинкс вне форума Ответить с цитированием
Старый 17.08.2018, 09:17   #16
eduard-fe
 
Аватар для eduard-fe
 
Регистрация: 23.07.2018
Сообщений: 8
По умолчанию

Цитата:
Сообщение от Ципихович Эндрю Посмотреть сообщение
до сих пор не озвучена цена
Функция запуска для произвольного вида данных выглядит как
Код:
template< class ExecutionPolicy, class RandomIt, class Compare >
void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );
то есть требует открытия кода. Защита от копирования невозможна, потому связываться с физлицами, скорее всего, я пока не буду, либо это будут специализированные lib (какие нужны? пишите). С юрлицами общаться буду через договор оказания услуг. Здесь с ценой легко определиться (стандартная ставка senior developer * days).

Цитата:
Сообщение от Ципихович Эндрю Посмотреть сообщение
выложите пример для теста для винды, спс
Выкладываю тест для Win7. Запуск без параметров - хелп с описанием режимов работы (создать и просмотреть файлы данных, настроить параметры под процессор, сортировать, сравнить с std::sort & std::stable_sort).

Тест
1) сортирует данные загруженные с диска,
2) работа только с int
3) размер файла строго ограничен (N=10^8) (для других размеров создавать и смотреть данные можно, но сортировать нельзя)
4) версия последовательная
5) без настройки параметров алгоритма производительность будет сравнима с std::sort
6) настройка в версии упрощенная (требуется указать размеры L1,L2,L3 кэшей данных, обычно для L1 размер кэша данных вдвое меньше полного размера кэша)

Кстати, просьба для всех, кто скачал и НАСТРОИЛ перед сортировкой алгоритм, выложить результаты сравнения или прислать их мне в личку (+вывод настройки +имя процессора). Мне интересно, что происходит на других процессорах.
Вложения
Тип файла: zip Release.zip (182.5 Кб, 8 просмотров)
Sincerely yours,
I am utterly indifferent to you.
eduard-fe вне форума Ответить с цитированием
Старый 17.08.2018, 13:15   #17
kvitaliy
Участник клуба
 
Регистрация: 17.05.2011
Сообщений: 1,660
По умолчанию

Тестирование приложения по сортировке проводилось на компьютере под управлением win7 x64. Компьютер оборудован офисным процессором i3-2120, 3.30 GHz. Сортировался файл с 10 000 000 значений типа Int
1. Запуск БЕЗ Подстройки под процессор показал среднее время сортировки из 10 запусков 0.819000 сек., что соответствует стандартной сортировке методом stable_sort.
2 Запуск с НАСТРОЙКОЙ на конкретный процессор. Для запуска были использованы сл. параметры: L1 = 128 L2 = 512 L3 = 3000
Среднее время сортировки из 10 запусков 0.40020 сек., что лучше предыдущего замера в 2 раза.

В общем, кому критично время сортировки, для уменьшения таковой примерно в 2 раза, можно порекомендовать испытать данный алгоритм. Алгоритм не использует многоядерность процессора, при работе загрузка соответствует одному ядру (2х ядерная система 50% загрузки).
kvitaliy вне форума Ответить с цитированием
Старый 04.09.2018, 21:00   #18
сфинкс
Форумчанин
 
Аватар для сфинкс
 
Регистрация: 17.06.2012
Сообщений: 953
По умолчанию

как 2-й скачавший программу сообщаю:
не понятно что делает программа

стартовал и не увидев ничего и нигде
стёр непонятную программу
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
сфинкс вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как адаптировать вкладки под свои нужды !!! 333_org_ua JavaScript, Ajax 0 05.12.2010 16:04
Помогите выбрать лицензию для ХР под описанные нужды. bset111 Windows 8 15.12.2009 22:38