Статьи Галерея Форум Чат Файлы HowTo Ссылки Поиск
Текущее время: 15 июл 2019, 22:21




Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: 30 апр 2006, 16:57 
Неотъемлемая часть форума
Аватара пользователя

У нас с: 13.08.2004
Сообщения: 891
Откуда: Минск
Foxx, а у меня таких поисков диапазона несколько миллионов.

Aleksey Kondratenko, ОГРОМНОЕ спасибо вам за примеры кода! Я в Асме не слишком силён, но буду внимательно разбираться в представленном коде.

_________________
https://grinchik.com/


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 05 май 2006, 19:58 
Интересующийся
Аватара пользователя

У нас с: 01.12.2003
Сообщения: 67
Откуда: Минск
одним из самых быстрых методов является является "интерполяционный" метод. Думаю не секрет, что именно интерполяция всегда достигает наиболее лучших результатов:D. В этом методе используется супер навороченная формула, которую я сейчас попробую изобразить :)

d=цел.часть

(j-i)*(K-Ki)
-----------
Kj - Ki

Тут d - это расстояние первоначального сравнения. Параметры i и j - номера соответственно первого и последнего элемента отрезка. Ki и Kj - это значения элементов в i и j позициях. K- ключ. Если все элементы исходного массива являются(или достаточно близки к ним) членами арифметической прогрессии, то поиск может пройти за одно сравнение. Если Вы не нашли нужный ключ с первого раза, то исходный отрезок поиска сужается и делается следующее сравнение с ключом расположенным на новом расстоянии d.


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 11 май 2006, 06:50 
Неотъемлемая часть форума

У нас с: 12.08.2003
Сообщения: 250
"Надумал"/нашел несколько ошибок в моем предыдущем посте.

1. В одной из последних строчек кода константа 0x0001000 (двенадцатый бит) должна быть заменена на
0x00010000 (шестнадцатый бит). Нолик справа упущен.

2. Комбинация "неветвящегося" поиска и интерполяционного -- полный бред.

3. И самое главное о чем я не сказал (и не подумал :( ). В данной задаче если применять последовательный поиск можно рассчитывать на хорошее предсказание ветвлений. Последовательный поиск будет иметь два условных перехода: один на начало цикла (если еще есть диапазоны), и второй на выход при успешном попадании. Оба перехода ни разу не случайные. Первый переход будет почти всегда выполняться (а значит будет хорошо предсказываться), и второй переход будет почти всегда не выполняться (тоже хорошо). Можно смело считать, что за весь цикл мы получим максимум один неверно предсказанный переход. А это будет быстрее предложенного варианта начиная с некоторого (очень маленького (до десятка элементов, ИМО)) размера множества.

Таким образом, на мой взгляд, единственное место, где _возможно_ стоит попробовать предложенный подход -- это в дереве (арности где-то начиная с 4).

П.С. Я надеюсь, что напоминать тебе о том, что последовательный поиск не годиться для больших множеств не надо.

П.П.С. Если тема оптимизации с учетом оссобенностей современных процессоров тебе интересна, то рекоммендую почитать "Intel Architecture Reference Manual" (доступен на сайте Интеловцев (для последней версии Order Number: 245127-001)). Он довольно неплохо написан и описывает в том числе и общие для всех современных процев нюансы.


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 11 май 2006, 07:09 
Неотъемлемая часть форума

У нас с: 12.08.2003
Сообщения: 250
Упс. Снова наврал. Последний интеловский optimization manual имеет совсем другой order number. В общем ищи у них на сайте.


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 11 май 2006, 09:02 
Неотъемлемая часть форума

У нас с: 03.04.2004
Сообщения: 436
Aleksey Kondratenko, гм, есть пара вопросов. Я уже поотстал от гонки технологий, потому, может, вы поможете наверстать малую часть упущенного.
Все таки оптимизация. таки уж она имеет смысл для современных процессоров? Понимаю, что с позиции быстродействия - безусловно да, но с точки зрения стоимости затрат кодирования простых алгоритмов для простых систем (не берем realtime-системы, всякие слабые контроллеры и т. п. специфичные задачи)? Интересно ваше мнение.
ИМХО если уж и заниматься оптимизацией для машин семейства x86, то должы быть соблюдены и backward compatibilities, то есть импользование conditional mov-ов для те же первых пней невозможно. Хотел сказать, что в таком случае должен быть использован более "классический" набор команд. Потому как прирост быстродействия менее критичен и будет гораздо менее заметен при текущих вычислительных мощностях (и оптимизаторах кода), нежели на древних аппаратах.
Еще бы хотел спросить про предсказание переходов и поведение кэша при этом, но пока не знаю, как точно сформулировать свой вопрос.


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 11 май 2006, 17:43 
Неотъемлемая часть форума

У нас с: 12.08.2003
Сообщения: 250
Для большинства задач ИМО не имеет. Часто дешевле докупить железа чем платить за лишние человеко-часы. Именно поэтому все большее количество задач (оссобенно IO-bound) решают на все более высокоуровневых языках (типа Ruby). Работает в разы медленней, зато программировать значительно приятней и дешевле. Кроме того, думаю, в некоторой не сильно отдаленной перспективе можно все таки ожидать нормальных реализаций JIT для распостраненных динамических языков (Python, Ruby).
Если не free software community, то Сан (у них есть опыт в этой области) или может быть smalltalk'еровские ренегаты рано или поздно это сделают. Это ИМХО целый клондайк для исследователей и инженеров в области компиляции. Лично я большой сторонник применения в не слишком критичных задачах языков программирования (более) высокого уровня.

Однако ИМО есть области, где хотя бы можно обсуждать трату времени на хорошую оптимизацию. Это продукты массового употребления: библиотеки структур данных и алгоритмов, СУБД, OS kernel -- кирпичики самого нижнего уровня. В этих областях трата большого количества дополнительного времени может окупаться за счет массового применения результатов работы. И это ИМО более актуально для free software, нежели для проприетарщины.

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


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 11 май 2006, 18:29 
Неотъемлемая часть форума

У нас с: 12.08.2003
Сообщения: 250
Уточню. Когда я говорю о хорошей оптимизации, я не имею в виду ручное кодирование на ассемблере. На абсолютно идентичных алгоритмах значительно опередить современный компилятор очень не просто. Года два назад специально попробовал. И речь идет не о разах разницы, а о десятках процентов. Я имею в виду маленькие вариации исходного алгоритма позволяющие использовать оссобенности определенного или всех современных процессоров в целом.

Предложенный мной код демонстрирует эту идею. Алгоритм в принципе тот же -- последовательный поиск. Но реализация (вероятно, слишком агрессивно) задействует одну из возможностей современных процев -- conditional move.

Аналогично можно поступать при проектировании структур данных. Например, по всей видимости, обычный связанный список для целого ряда задач далек от опимальности. Например, когда нужно пробежаться по всем элементам списка, и для каждого элемента произвести простые действия. Такие подзадачи типичны, например, для графовых алгоритмов. Вместо него можно применять линейный массив (если задача позволяет), или модифицированный связанный список, где элементами "связанного списка" являются массивчики элементов небольшого фиксированного размера. Я читал статью с исследованиями на эту тему.

Значительного прироста можно добиться за счет векторизации. gcc пока что не очень хорошо умеет векторизовывать. Зато он предоставляет специальные compiler intrinsics для того, чтобы делать это не прибегая к ассемблеру.
Кроме того, даже хорошему в автовекторизации компилятору может пригодиться небольшая помощь от программиста в виде небольших модификаций исходного алгоритма.


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


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

Найти:
Перейти:  
[ All resources are available under GNU GPL ] [ Support ] [ Hosted by DataHata | MyCloud.by ] [ Powered by phpBB® Forum Software © phpBB Group ]

LVEE Winter LVEE Rambler's Top100