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

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

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

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

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

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

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

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

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

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

Як RPA-платформа допомогла SkyUр автоматизувати оплату рахунків