`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

Как изменилось финансирование ИТ-направления в вашей организации?

Best CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Андрей Зубинский

"Интуитивно" - не значит "верно"

+22
голоса

Программисты любят степени двойки. Эта любовь - уже притча во языцех. Оправдывает её двоичная природа аппаратных средств всех современных цифровых вычислительных машин (безусловно, бывают и основанные на троичной системе счисления вычислители, но кто видел хоть один такой современный вычислитель?).

 На практике же эта любовь может привести к весьма непредсказуемым последствиям.  А именно, - если требуется очень быстро обрабатывать массивы, программист интуитивно предполагает, что размер массива, выражаемый как 2^N, должен быть в каком-то смысле "лучше", чем некратный степени двойки.

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

 Дело в том, что при исполнении оперирующего массивами кода вычислителем с не полностью ассоциативной кэш-памятью (direct-mapping или set-mapped организация кэш-памяти), проявляется совершенно неинтуитивная зависимость между размером массива и… быстродействием кода.

 Неинтуитивность заключается в том, что при размерности массива, кратной степени двойки, наблюдается существенная деградация производительности - счёт ведётся не на единицы, а на большие десятки процентов. Виновник явления - частые коллизии при обращении к данным в кэш-памяти.

 Отыскалось это странное, но полезное, предупреждение, в самом неожиданном месте - в описании предпочтительных чисел в wikipedia. Эти числа интересны сами по себе - именно на их основе строятся современные шкалы номиналов резисторов и конденсаторов (и, несмотря на весьма внушительную предысторию, от этого шкалирования никто не собирается отказываться).

 Авторы соответствующего абзаца в заметке wikipedia ссылаются на опубликованную ACM статью некоей Моники Лэм. ACM - ресурс, к сожалению, небесплатный. Но разведка доложила точно - на сайте самой Моники Лэм статья доступна за просто так, разве что в посткрипте (надеюсь, это не будет главной проблемой для желающих её прочесть - статья-то ой какая не простая).

 Важно ли это всем пишущим? Наверное, - не очень. Но если речь идёт о коде для DSP (цифровых сигнальных процессоров) или для развитых микроконтроллеров, потеря производительности из-за подсказок "интуиции" может оказаться фатальной.

 Так что на всякий случай размерности массивов 2^N лучше сторониться - если не поможет, так хоть не навредит.

+22
голоса

Напечатать Отправить другу

Читайте также

 
 
IDC
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT