Однако ни в 2009-м году, ни в 2010-м игра так и не вышла, хотя на всевозможных выставках у нее непременно были стенды, где поначалу крутились ролики, а под конец 2010-го уже стали давать поиграть в один из эпизодов. Выглядело все довольно симпатично, но скучновато. Дата выхода игры упорно замалчивалась и стала известной лишь в конце сентября 2011-го. Правда, назвав ее, разработчики снова чуть-чуть наврали, и вместо 3 ноября новый Postal вышел 23-го, а в Steam появился и вовсе 21 декабря. У меня конец года получился крайне насыщенным, поэтому премьеру, каюсь, пропустил. И все же за разнообразными хлопотами не покидала мысль – почему же никто из знакомых в соцсетях ни словом не обмолвился о выходе почти легендарного долгостроя? Почему не дают ссылки на обзоры и не рапортуют о набегах на магазины? Неужели игра так и не вышла?

Но вот новогодние праздники закончились, за ними пронеслась и CES, и я наконец-то решил попробовать Postal III. Правда, в Steam его почему-то найти не удалось, и по прямой ссылке из пресс-релиза меня просто выбрасывало на главную страницу. Ну да ладно, обойдемся архаичными DVD. Ставлю игру, активирую, запускаю и понимаю - почему молчат соцсети. Видимо, они оказались шокированы не меньше моего.

Напомню, Postal III делали без малого шесть лет. Если верить пресс-релизу, за это время «у пятерых разработчиков родились дети, двое человек, причастных к проекту, и одна собака отправились в лучший мир, дата релиза проекта переносилась раз 9. Студия TrashMasters сменила три офиса, 4 сотрудников проводили работать в заграничные компании. За годы разработки было выпито 69 800 литров кофе, 56 700 литров чая, 138 900 литров пива. Подсчитать количество более крепкого алкоголя не представляется возможным в силу провалов в памяти сотрудников». Жаль, что не уточняется – на каком этапе от издателей в ужасе убежала совесть. Потому что большей лажи я и припомнить не могу. На фоне Postal III многострадальный Duke Nukem Forever выглядит вполне приличной игрой.

В Postal III ужасно практически все. Графика – на уровне худших образцов года эдак 2006-го (поддержка только DirectX 9 в конце 2011-го, каково?). Сюжет по разнообразию уступает даже любовным романам в мягкой обложке, которые давно пишутся специально натасканными текстогенераторами. Играть в новый Postal просто дико неудобно – действительно разнообразное оружие интегрировано в геймплей из рук вон плохо, и применять его по назначению порой невозможно. Наконец, стабильность работы отсутствует: игра вылетает по поводу и без, иногда даже слегка «подвешивая» компьютер. Ну и, конечно, «потрясает» дизайн. Авторы игры явно пытались замаскировать уродливые меню под эдакий хитрый панк-стиль, где все нарочито небрежно и кривовато. Но нет: игра ДЕЙСТВИТЕЛЬНО сляпана на коленке, и ни под какой мусорный дизайн не замаскировать полное отсутствие последнего.

Полное ощущение, что Postal III забросили и похоронили еще года три назад, а потом, вдохновившись примером несчастного кадавра Duke Nukem, решили быстренько соорудить нечто из имеющихся набросков и запустить ЭТО в продажу. Народ, конечно, будет плеваться, но сотню-другую тысяч копий продать непременно успеем, пока раскушают. Всё деньги…

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

Мне же остается надеяться, что в лапы подобных раздолбаев не попадет бренд Full Throttle.

P.S. И угадайте – почему я на этот раз даже не вспомнил о поддержке многоядерных процессоров?

Итак, 1 декабря 2010 года в посте «Единство непохожих» было сказано следующее:

«В мае будущего года один из крупнейших производителей мобильных компьютеров выпустит ультралегкую модель бизнес-класса с двумя процессорами, один из которых будет построен на архитектуре x86, а другой на ARM. Разумеется, работать они будут под разными операционными системами. Насколько могу судить по имеющимся на данный момент данным, общими у них будут только батарея, клавиатура, тачпад и дисплей. Ну и, конечно, разъемы, вроде Ethernet, D-Sub и прочих.

По задумке Крупнейшего Производителя, основное время пользователь будет проводить на x86 (скорее всего, семейства Sandy Bridge) под Windows. Но где-нибудь вдали от розетки, когда скорость и, не побоюсь этого слова, эффективность работы уступают по важности автономности, можно будет одним движением специального рычажка переключиться на ARM, отправив x86 в глубокий сон. Переключение будет быстрым, потому что вторая операционная система в этот момент не загружается с нуля, а просыпается. В параллельной реальности останутся примерно те же возможности, но с ограничениями, накладываемыми аппаратными и программными факторами. К слову, с операционной системы для платформы ARM Производитель еще не определился. Среди вариантов рассматривается и MeeGo, хотя ARM, скажем так, не совсем целевая платформа для данной ОС».

Как мы уже знаем,ничего такого в мае случилось. И до конца 2011 года тоже. И только пятого января 2012-го Lenovo решилась на анонс ThinkPad X1 Hybrid. Действительно, на материнской плате – рядом с традиционными процессорами семейства Core - обнаружился двухъядерный CPU Qualcomm, а работать ARM-режим будет под управлением операционной системы на ядре Android. Обещают, что в этом режиме ноутбук проживет от батареи вдвое дольше.

Кажется, я догадываюсь – почему анонс перенесли почти на год. Как уже писал в том самом пророческом посте, имеющиеся на тот момент ARM-решения были попросту непригодны для использования в мобильных компьютерах. Нет, поставить какую-нибудь Linux-систему и покрутить на презентации видео – это запросто. А вот работать – просто никак. Об этом я тоже рассказывал в посте, опираясь на результаты собственного изучения очень раннего прототипа такого ноутбука. Но за год наконец-то появились довольно быстрые двухъядерные ARM-CPU и, что еще важнее, Android научился их худо-бедно использовать. Значит можно от сэмплов перейти к серийному производству, не опасаясь отпугнуть людей, готовых выложить за ThinkPad X1 Hybrid $1599 (без учета налогов за минимальную конфигурацию).

В продаже эта модель появится во втором квартале, а значит в ней, скорее всего, будут использоваться новые процессоры Intel семейства Ivy Bridge. Что же, посмотрим – удастся ли ARM обставить их вдвое по времени автономной работы. 22-нанометровый техпроцесс, конфигурируемый TDP да таинственный Low Power Mode могут запросто подсократить разрыв.

Не подскажете, кстати, верный способ выиграть $1600? Судя по фильмам, сделать это в Вегасе совсем несложно, но все же интересует мнение людей с системным мышлением

Ремонтники, к которым я отнес маленького страдальца, бились над ним неделю, но в итоге сказали, что придется менять материнскую плату целиком, а это стоит 6000 рублей, и привезут ее в лучшем случае через месяц (напоминаю, дело было прямо перед Новым годом, когда логистические цепочки уже пришли в праздничное состояние). Пораскинув мозгами, принял волевое решение продать почивший в бозе агрегат на запчасти, а супруге купить новый. Заодно и решается проблема выбора новогоднего подарка.

Разумеется, первым порывом было осчастливить ее ультрабуком, однако габариты продаваемых сейчас моделей показались слишком внушительными. Ничего не поделаешь, привык человек к 12 дюймам или меньше, и все тут. Моделей с 12-дюймовой (или, точнее, 11.6-дюймовой) матрицей продается немало, однако стоят они довольно дорого. А немногочисленные дешевые модели страшновато брать в руки: создается полное ощущение, что тончайший пластик крошится под пальцами. Настроился было основательно потратиться, но тут случилось небольшое чудо. В одной дружественной фирме, которой я пожаловался на свою беду, мне предложили новенький Sony VAIO TZ1 по цене хорошего нетбука.

Знающие читатели сейчас насторожились: «Как это новенький? Это ж модель какого-то совсем лохматого года!». Так и есть: данный экземпляр был изготовлен в Японии аж в июле 2007-го. Потом крупную партию VAIO TZ1 купила одна богатая российская компания для выдачи особо ценным сотрудникам, но то ли не переборщили с количеством, то ли сотрудники ценные успели разбежаться, но в результате несколько ноутбуков так и не покинули склад. В конце 2011-го состоялась масштабная инвентаризация, по итогам которой «старье» было решено продать по демпинговым ценам, а вместо него купить что-нибудь поновее. И вот один представитель этой небольшой партии раритетов добрался до моих знакомых.

Честно скажу, я долго не размышлял – решил брать. Даже если супруге не понравится, такой ноутбук всегда можно продать ценителям древностей, коих среди моих корреспондентов немало. Просто я был на презентации этой модели в далеком 2007-м, и хорошо помню свой восхищение от нее, переходящее в экстаз. Двухъядерный процессор Intel Core 2 Duo U7500 с частотой 1.06 ГГц, 2 гигабайта ОЗУ, тончайший 1.8-дюймовый 100-гигабайтный жесткий диск Toshiba со скоростью вращения шпинделя 4200 об./мин., батарея емкостью 5800 мАч, обеспечивающая до семи часов непрерывной работы… И все это при весе 1.19 кг в СНАРЯЖЕННОМ состоянии, то есть вместе с батареей. Венчал великолепие встроенный DVD-RW с очень приличными характеристиками и качественный экран с только появившейся тогда в ноутбуках LED-подсветкой.

Я понимаю, что сейчас такая конфигурация особых восторгов не вызывает. Но в далеком 2007-м еще не было нетбуков, ультрабуков и MacBook Air, и VAIO TZ был настоящим прорывом в индустрии. Поэтому никто даже особенно не роптал по поводу его цены – около $3000 в Штатах и хорошо за 100 000 рублей в России.

И вот, четыре с половиной года спустя, этот маленький шедевр у меня в руках. Честно говоря, опасался за сохранность батареи, но она оказалась живой и здоровой. Несмотря на то, что на TZ установлена операционная система Windows Vista Business, способная укротить и более серьезные системы, работает он на удивление резво. Настолько, что я даже не стал затевать переустановку. Правда, без малого двое суток (!) ушло на скачивание и инсталляцию всех патчей и сервис-паков, вышедших для Vista за четыре года, и еще пара часов на зачистку совершенно бесполезного предустановленного софта, но я не ропщу, нет. Наоборот, ощущение, словно прокатился на машине времени, потому что я уж и забыл – какой… необычной Vista была изначально.

Процессор Core 2 Duo U7500 выполнен по, страшно вспомнить, 65-нанометровой технологии и имеет TDP 14 Вт. Согласно встроенной пузомерке Windows, его рейтинг составляет 4.3 единицы – показатель не рекордный, но вполне приемлемый. Для интернет-серфинга и кинопросмотров хватит еще надолго. А карбоновый корпус не даст ноутбуку стать жертвой дорожных неурядиц.

Четыре с половиной года по меркам нашей индустрии – срок огромный. Какие там 65 нанометров, какой еще чипсет 945PM с его простенькой графикой, кому нужен этот оптический привод, ради которого инженерам приходилось творить настоящие чудеса? И все же вещь, когда-то сделанная на твердую пятерку, продолжает радовать и спустя многие годы. Конечно, лично для меня лучшим выбором стал бы один из ультрабуков, хотя и тут бы пришлось немного поколебаться…

И вот интересно – а как будут восприниматься нынешние топовые версии ультрабуков через четыре года с хвостиком? Смогут ли они порадовать девушку на фоне гораздо более совершенных наследников, или заинтересуют только собирателей IT-старины?
Я пометил этот вопрос в своем календаре. Время до ответа пролетит незаметно

А пока – с Новым годом! Пусть важное сбудется.

Не все йогурты одинаково полезны.

Преамбула:
При написании шаблонных параметров обычно принято использовать ключевое слово class, чтобы подчеркнуть, что шаблонный параметр является классом (структурой). Стандарт C++ говорит следующее [п.14.1.2]:

There is no semantic difference between class and typename in a template-parameter.

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

Амбула:
Намедни необходимо было написать шаблонный класс, параметризованный другим шаблонным классом. Было написано:

template <template  <typename T> typename Cl >

Вот тут и возникла проблема - компилятор VC++ 2010 гордо рапортовал об ошибке:

error C2988: unrecognizable template declaration/definition

Компилятор Intel C++ Compiler 12.0 и также возвращал сообщение об ошибке:

error : expected "class"
template <template <typename T> typename Cl >
                                ^

После повторного чтения стандарта, была выяснена причина. Если подробнее рассмотреть синтаксис шаблонных параметров, то можно заметить, что для параметризации шаблонных параметров можно использовать только ключевое слово class [п.14.1.1]:

template < template-parameter-list > class ...[opt] identifier[opt]
template < template-parameter-list > class identifier[opt] = id-expression

Вобщем, проблема локализована и после корректировки исходного кода до:

template <template  <typename T> class Cl >

компиляция проходит успешно в VC++ 2010 и Intel C++ 12.0.

Мораль:
Не всегда ключевые слова typename и class являются синонимами. При объявлении шаблонного параметра другого шаблонного параметра необходимо использовать только ключевое слово class, вместо typename.
И... проглядывайте стандарт C++;)

В качестве пиксельной матрицы возьмем массив 32-битных целых, рассматривая его как ARGB-плоскость. 4 байта на тексель не сильно экономят память , но избавляют от необходимости следить за выравниваем при заполнении буфера. Альфа-канал использоваться не будет.

После заполнения его каким-либо способом (зависит от библиотеки распараллеливания), загружаем данные в память видеокарты вызовом glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA...), а затем отрисовываем одним блоком GL_QUADS на весь экран (выводим прямоугольник).

Вариант с glDrawPixels и так не советуют к использованию, так еще и по результатам эксперимента применение данной функции приводит к падению скорости отрисовки на порядок. Не пойдет. А применение VBO (Vertex Buffer Objects) в данном случае не обосновано - у нас всего 4 вершины и одна текстура.

На выбор OpenGL+GLUT прежде всего повлияло желание собрать и запустить приложение как под Linux, так и под Windows и сравнить результаты на одинаковом "железе".

Распараллеливание будем выполнять, разделив текстуру на горизонтальные блоки по числу используемых потоков/ядер. В SLI/CrossFire конфигурациях видеокарт используется подобный режим Split Frame/Scissor (изображение взято с википедии):

Заменим видеокарты на процессорные ядра - и получим вариант распараллеливания.

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

typedef struct {
    double x1, y1,
           x2, y2;
} Bounds;

typedef unsigned char byte;

typedef struct {
    int  width,     // ширина в пикселях
         height,    // высота в пикселях
         size;      // размер в пикселях == width*height
    byte *buff;     // кусок памяти с пиксельными данными
} Buffer;

Само множество на комплексной плоскости находится в пределах (-2,-1) x (1,1), так что можно начать с вывода с запасом (-2,-1.5) x (1,1.5) - вариант квадратной области.

Текстура хранится также квадратная, размерами 2^n (текстуры размерами не кратными степени 2 будут работать далеко не на всех видеокартах). Размер текстуры (T), равно как и предельное число итераций проверки сходимости (n) выражают общую сложность построения как O(T^2*n).

При распараллеливании каждому из потоков на вход нужно подать ограничивающий объем в координатах комплексной плоскости, а также две V-координаты текстуры (высота/ось Y), обозначающие первую и последнюю строки, в которых следует отобразить результаты.

Сразу картинку возможного вывода:

Итого имеем:

// координаты "окна" в комплексной плоскости
Bounds screen;

// текущие координаты центра "окна" в комплексной плоскости
double cX=0, cY=0;

// размер клиентской области окна в системе
int window_width  = 800,
    window_height = 800;

// текущий шаг приближения
int STEP = 0;

// предел числа итераций проверки сходимости
int ITERS = MIN_ITERS;

Собственно рендер фрактала в текстуру выполняется обычным распараллеленым циклом:

void fractal() {
    int parts = omp_get_max_threads();
    if ( parts <= 0 ) parts = 1;

    omp_set_dynamic( 0 );
    omp_set_num_threads( parts );

    int p, y=0, dy;
    double sy = (screen.y2-screen.y1) / parts;
    dy = buffer.height / parts;

    #pragma omp parallel for firstprivate(y) ordered
    for ( p=0; p<parts; ++p ) {
        Bounds bounds;
        bounds.x1 = screen.x1;
        bounds.x2 = screen.x2;

        bounds.y1 = screen.y1 + p*sy;
        bounds.y2 = bounds.y1 + sy;

        y = p*dy;

        //fractal_block( bounds, y, y+dy-1, (p+1)*6 );
        fractal_block( bounds, y, y+dy-1, 3 );
    }
}

Т.к. координата верхней строки каждого блока (y) используется внутри тела цикла, при этом меняясь, то ее следует передавать через firstprivate.

Функция fractal_block принимает координаты окна комплексной плоскости (bounds), верхнюю и нижнюю границы в текстуре (y, y+dy-1) и множитель "яркости" (о нем ниже):

void fractal_block( Bounds block, int y1, int y2, int f ) {
    int *ptr = (int*)( buffer.buff + y1*buffer.width*4 );

    double x, y, sx, sy, z, zi;

    x = block.x1;
    y = block.y1;
    // приращения по комплексным осям между соседними текселями текстуры
    sx = (block.x2 - block.x1) / buffer.width;
    sy = (block.y2 - block.y1) / (y2-y1+1);

    int width = buffer.width;

    // раскидываю значение множителя по трем младшим байтам
    f = f%256;
    f = (f<<16) | (f<<8) | f;

    for ( ; y1<=y2; ++y1 ) {
        int _x;
        for ( _x=0; _x<width; ++_x ) {
            z = zi = 0.0;
            int steps = 0;
            for ( ; steps<ITERS; ++steps ) {
                double tmp = (z*z) - (zi*zi) + x;
                zi = 2*z*zi + y;
                z = tmp;

                if ( z*z + zi*zi > 4.0 ) break;
            }

            *ptr++ = f * steps2RGBA( steps<ITERS ? steps : 0 );

            x += sx;
        }

        y += sy;
        x  = block.x1;
    }
}

Что же дает "множитель яркости" f? Благодаря ему можно визуально разделять блоки, которые рассчитывались разными ядрами. Достаточно использовать при генерации значение, зависящее от номера текущего блока/ядра, например так: fractal_block( bounds, y, y+dy-1, (p+1)*6 );

При этом будет наблюдаться картина вроде такой:

Хорошо заметны 5 блоков, из которых состыкована текстура.

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

Реализация выполнена с подстройкой предела сходимости с целью снять ненужную нагрузку (на общем плане что 50 итераций, что 100 - визуально не заметно, а нагрузка ощущается). Соотвественно идет подстройка предела при масштабировании (также ее можно менять кнопками Up/Down).

Непосредственно по распараллеливанию. На машине с Core i5 750 в 2 потока отрисовка дает честный двухкратный прирост, на 4х потоках прирост порядка 3.5 раз. На приближении 2^40 и пределе итераций в 250 время работы 4х ядер 1.01сек против 3.64сек на одном. Была бы машина с иксами с большим числом ядер - было бы конечно интересней. Не раз встречал мнение, что распараллеливание особо проявляется не менее, чем на 8ми ядрах. Если у кого есть возможность и желание - запустите, интересен коэффициент прироста скорости в сравнении с одним и двумя ядрами.

Приближение 2^40 выбрано с целью предотвращения величин ошибок округления, влияющих на результат. Примерно на 42-43 итерации приближения размер окна в комплексной плоскости становится менее 6.82e-13 и начинают проявляться ошибки округления (underflow):

В итоге получаем достаточно неплохой результат ценой практически одной только строчки pragma

На очереди ArBB, TBB и что еще подвернется.

И еще немного картинок:

Исходники (tar.gz)

И всех с Наступающим!

Итак, вам и вашим гостям (думаю, понятно, что каждый из гостей символизирует один поток в многопоточной программе) надо как можно быстрее съесть (или иным образом употребить) огромный багет, или колбасу, или ведро портвейна. Давайте вначале введём некоторые базовые понятия:

Общий объём работы – весь багет.

Гранулярность – размер куска багета, которым не нужно делиться. Сразу становится понятно, что такое крупногранулярное и мелкогранулярное разбиение, правда? :) Если гранулярность слишком мелкая, разделить кусок с другом дольше, чем съесть его самому.

Задача – любое действие, выполняемое участниками. Собственно, в процессе поедания багета две принципиально разных задачи – “разделить кусок на части” и “съесть кусок” (сразу вспоминается “а чего тут сложного, наливай да пей!”). Но, конечно, никто не может помешать вам отвлекаться на телевизор, кофе и иные непродуктивные “задачи”.

Принципы использования потоков:

Параллельный регион OpenMP (team-and-barrier): купивший багет резервирует стол на фиксированное количество человек. В некоторых компаниях (читай: реализациях) принято начинать есть только когда все друзья соберутся вместе; в других начинать можно сразу, как придёте. Но заканчивать обязательно всем вместе: все ждут последнего, даже если он вообще не явился.

Пул потоков: купивший багет разделяет его на куски, которые выкладывает на стол, вывешивает табличку “Багет на халяву!” и ждёт, пока друзья и шапошные знакомые не съедят всё до крошки. Кроме него, никто ничего не ждёт; если со стола взять нечего, можно сразу перейти за соседний.

Пул потоков TBB: то же самое, но владелец багета начинает есть куски сам. Если никто не придёт, он и один всё съест

Принципы распределения задач:

Общий пул задач: в середине стола стоит тарелка, на которой лежит багет, туда же кладутся его “свободные” куски. Тянуться до тарелки далековато, а брать и класть нескольким лицам одновременно обычно не разрешается.

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

Захват работы (work stealing): рядом с каждым гостем своя тарелка, с которой он берёт и на которую кладёт куски. Если своя тарелка опустела, можно взять кусок с любой другой; обычно никто не стесняется, хоть до чужих тарелок тянуться и дальше.

Принципы деления работы:

Статическое деление (например, #pragma omp for schedule(static)): владелец ведра портвейна режет его на куски заданного размера (гранулярности) и по кругу раскладывает на тарелки всем гостям; в некоторых компаниях гости сами берут куски  с общей тарелки (но при этом только "свои"!). С чужих тарелок есть нельзя. Напомню, что в команде OpenMP при этом все ждут последнего. Подход очень хорошо работает, если все начинают одновременно и едят с одинаковой скоростью, а в багете не попадается инородных предметов

Динамическое деление (#pragma omp for schedule(dynamic)): багет лежит на середине стола; каждый, у кого нет еды, отрезает себе кусок заданного размера и ест. Нож (как и остаток багета) только один. Этот подход предпочтительнее статического деления, если багет пропечён неравномерно или кто-то опаздывает к столу.

Динамическое деление в tbb::parallel_do: владелец багета отрезает себе кусок на 4 порции, остаток багета кладёт на свою тарелку. Туда же кладутся три из четырёх порций, а четвёртая отправляется в рот. Гости хватают куски, где найдут; захвативший большой остаток багета повторяет процедуру деления на своей тарелке.

Рекурсивное деление (например, cilk_for или tbb::parallel_for плюс simple_partitioner): любой кусок багета больше заданного размера режется примерно напополам, половины кладутся на тарелку (в TBB – на свою, но можно и на общую). У каждого есть свой нож; в крайнем случае, можно и руками разломить

Рекурсивное деление с динамическим выбором гранулярности (tbb::parallel_for плюс auto_partitioner): Деление напополам прекращается, когда на каждого из едоков приходится по 2-4 куска. Однако, кусок, схваченный с чужой тарелки, снова делится, минимум дважды (то есть, в итоге, начетверо). Начиная с TBB 4.0, хозяин тарелки, с которой утащили кусок, замечает это и оставшиеся куски будет делить помельче.

-----

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

В предыдущем посте я немного рассказал об одном из возможных решений - динамической генерации кода. Это реализовано в Intel Array Building Blocks. У этого подхода свои плюсы и минусы. К плюсам следует отнести универсальность и гибкость, к минусам внутреннюю сложность и значительные накладные расходы (ведь сначала код надо сгенерировать).

Вопрос: какие еще существуют решения для оптимизации кода под различные платформы? Попытаемся разобраться в способе, который называется диспетчеризацией (Dispatching).

Для начала уточним задачу: код должен быть оптимизирован не под все железо, а только под определенный набор. Это нормально, ведь продукты поддерживают ограниченное число процессоров. Преемлемым решением для остальных процессоров выглядит запуск неоптимизированного кода на них. Кроме того, не всегда имеет смысл оптимизировать код под каждый процессор. Многие могут быть объединены в классы эквивалентности. Например, много процессоров поддерживают одинаковый набор SIMD инструкций.

Исходя из того, что простое лучше, чем сложное, можно сделать несколько вариантов кода, каждый из которых функционально идентичен остальным, но оптимизирован под свой набор процессоров. Очевиден и основной недостаток: на каждом CPU необходимо выбрать, какой процесс запустить или какую библиотеку вызвать. Этот минус можно обойти, если использовать дополнительный модуль. Он вызывается в run-time, автоматически определяет тип процессора и предлагает выбрать ветку кода, которая подойдет под текущее "железо" наилучшим образом. Этот модуль называется диспетчером (Dispatcher).

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

Существуют различные реализации диспетчеров. По одной из них (в библиотеке Intel IPP) диспетчер идентифицирует CPU один раз - во время инициализации библиотеки, после чего задает набор внутренних переменных. В соответствии с этим набором библиотечные вызовы из приложения перенаправляются в соответствующие внутренние функции библиотеки. Например, при запуске приложения на Core 2 Duo в 32-битной операционной системе вызов функции ippsCopy_8u() перенаправляется на p8_ippsCopy_8u() - одну из множества реализаций функциональности ippsCopy_8u(), имеющихся в библиотеке.

К недостаткам такой системы следует отнести громоздкость. Размер библиотеки увеличивается вместе с ростом поддерживаемого железа. Рост размеров библиотеки означает и рост объемов приложений, которые ее используют. Справедливости ради стоит сказать, что есть способы борьбы и против этого эффекта.

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

Но время шло. Планшетов становилось все больше, функциональность их расширялась, а многочисленные портативные клавиатуры практически решили проблему удобства набора текста. Да и цены потихоньку снизились. В результате планшетные ПК стали действительно хороши для использования в дороге: включаются быстро, живут от батареи прилично (уж точно – не меньше нетбука), габаритами обладают весьма скромными… А вот нетбуки – в большинстве своем – словно застыли в развитии. Появление двухъядерных «атомов» позволило довести производительность до приемлемого уровня, однако держатели веб-сайтов как-то слишком резко рванули украшать свои детища, и в результате даже топовый Atom N570 начинал захлебываться при веб-серфинге, не говоря уж о моделях попроще. Перестали влезать странички и в разрешение 1024х600, и если мобильные версии браузеров в «таблетках» кое-как упихивали сайты в это разрешение, то их «просто компьютерные» аналоги просто предлагали заняться скроллингом. Ну и другие программы для больших компьютеров порой вели себя невежливо. Чего стоит хотя бы невозможность сконвертировать фотографии в Photoshop из RAW в JPEG просто потому, что окно конвертера не влезает в разрешение 1024х600?

И все же мне казалось, что нетбуки и планшеты слишком разные, и не получится у них влиять на продажи друг друга. Но вот зашел на днях к своему товарищу, который держит несколько магазинов на одном из столичных компьютерных рынков. Смотрю на витрины и чувствую какую-то дисгармонию. Товара много, но что-то в нем не так… Ах ты ж елки-палки! Там, где еще с полгода назад стояло десятка два разноцветных нетбуков, расположились планшетные компьютеры. А сами нетбуки исчезли.

Из расспросов выяснилось, что в последние месяцы нетбуки брать практически перестали, а вот планшетники, что называется, «раскушали». Да и маржа на последних пока держится довольно высокая. Также приятным бонусом стали размеры упаковки: там, где вчера на складе стоял один нетбук, теперь умещается два устройства Apple, Samsung и других производителей. А иногда и все три. Обнаружился и еще один занятный феномен: вместо нетбуков люди предпочитают покупать портативные ноутбуки прошлого, а то и позапрошлого поколений. Разумеется, уже побывавшие в употреблении, но в приличном состоянии. По цене получается сравнимо с новым нетбуком, а по скорости и общему комфорту работы – получше. Уловив тренд, мой товарищ заполнил все витрины подержанными рабочими лошадками (или, наверное, правильнее назвать их пони. Интересно, откуда они берутся в таком количестве?). Спрос не ажиотажный, но по сравнению с нетбуками – отличный. Была пара случаев, когда человек сразу покупал и планшет, и ноутбук.

Разумеется, магазины моего товарища – не показатель. Я поспрашивал своих знакомых, живущих за пределами Москвы, и они в один голос отвечают, что, мол, нетбуков в магазинах много, и берут их в полный рост, особенно перед Новым годом. Только кажется мне, что тенденция к уходу нетбуков с массового рынка в нишевый проявилась в достаточной мере. Это, наверное, хороший повод поплотнее присмотреться к планшетным ПК, которых уже наделали немало, да еще грядущий CES непременно подбросит не один десяток. Ну и, судя по всему, рынок с распростертыми объятиями примет ультрабуки – быстрые, похорошевшие и подешевевшие. На той же CES мы узнаем о новых процессорах для них, а также о ряде приятных усовершенствований. Я уже записался на профильный круглый стол в Вегасе, а также, возможно, удастся взять интервью у очень посвященного человека из Intel.

Хороших вам праздников, коллеги! Надеюсь, до новых встреч в новом году – с новыми силами. И в полном составе

В качестве альтернативы можно использовать целочисленные операции, основанные на работе не с одним значением внутри интервала, а с текущими границами. Если арифметический кодер работает в пределах интервала [0,1), то интервальный кодер начинает с интервала [0,N), где N - произвольный верхний предел, от которого и зависит максимальный размер обрабатываемого блока. Логично брать N, основываясь на аппаратных возможностях архитектуры, например 2^32.

Каждый обрабатываемый символ сужает интервал, приводя его в итоге к [x,x+1), что является предельным значением точности и размера обрабатываемого блока. Подинтервалы, в которые сужается исходный [0,1), как и в случае с арифметическим кодированием берутся исходя из вероятности появления данных символов во входном потоке. Учет вероятностей позволяет оптимально использовать выделенный интервал, предоставляя "чаще используемым" символам больший диапазон значений.

Эксперимента ради, попробуйте разделить интервал [0,20) на 10 частей, а потом на столько же частей интервал [0,5), сохраняя при этом целочисленную точность. И почувствуйте разницу

Рассмотрим пример сжатия строки "abraha#" (сократил "abrahadabra") с вероятностями:

Символ "#" является служебным терминальным и нужен на случай, если после сжатия в потоке вывода не передается исходная длина строки. В таком случае появление данного символа при декодировании будет служить сигналом завершения работы (аналогично EOF, EOL, etc).

В качестве максимального значения возьмем N=100.000.000 (100 миллионов).
Преобразуем вероятности появления символов в отрезки на интервале [0,N):

• a = 40% = 0.4 => 0.4*N - верхняя граница интервала
• b = 20% = 0.2 => 0.2+0.4 = 0.6*N - верхняя граница интервала, а нижняя - 0.4*N
• ...

Получаем:

[     0,  0.4*N)

[ 0.4*N,  0.6*N)

[ 0.6*N,  0.7*N)

[ 0.7*N, 0.95*N)

[0.95*N,      N)

Кодирование строки по шагам:

В результате имеем интервал [22,110,400 ... 22,112,000). Любое значение из этого интервала даст нам результат кодирования.
Для выбора оптимального значения можно выбрать то, в котором будем максимальное число нулевых младших бит среди всех возможных. Если имеем интервал [f,t), то искомой величиной будет:

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

Если брать просто среднее значение интервала, то в качестве ответа будет 22,111,200. Если взять оптимальное значение, то получим 22,111,232. Для сравнения, их бинарное представление:

22,111,200 = 1010100010110001111100000
22,111,232 = 1010100010110010000000000

Декодирование выполняется еще более похоже на арифметическое кодирование:

1. имея значение cur из текущего интервала [f,t), получаем соответствующий символ c;
2. нормализуем интервал до [0,N), получая новое значение new по формуле:
   
3. повторяем шаги 1 и 2 до встречи терминального символа, либо до достижения исходной длины строки (если известно).

Декодирование строки по шагам:

Ну и пример реализации на Python:

#!/usr/bin/env python
#-*- coding: utf8 -*-

from math import floor, log, ceil

class Arithmetic:

    def __init__(self, freqs_tuples, MAX):
        # верхняя граница интервала
        self.max = MAX
        # подготовка словаря с интервалами вероятностей символов
        self.__freqs2dict( freqs_tuples )

    def encode(self, s):
        u"""
            Кодирование строки s на основе вероятностей в self.freqs
            Возвращает число из итогового диапазона
        """
        # начинает с полного интервала [0,1)
        (f, t) = (0, self.max)
        for c in s:
            # координаты нового интервала
            (cf, ct) = self.freqs[c]
            # длина базового интервала
            t_f = t-f
            # Получение нового интервала.
            # Важно: т.к. в вычислении фигурирует f, то его
            # изменение выполняется только после вычисления t.
            # Т.е. не надо менять строки местами : )
            t = int( floor( ct*t_f / self.max + f ) )
            f = int( floor( cf*t_f / self.max + f ) )
        return self.__optimize( f, t )

    def decode(self, i):
        u"""
            Декодирование числа в строку на основе вероятностей в self.freqs
        """
        res = []
        c = None
        while c != '#':
            c = self.__find_interval( i )
            res.append( c )
            (f,t) = self.freqs[c]
            i = int( ( i-f ) * self.max / ( t-f ) )
        return ''.join(res)

    def __freqs2dict(self, freqs_tuples):
        u"""
            Преобразование кортежа вероятностей символов строки в
              словарь интервалов с учетом self.max
        """
        self.freqs = {}
        left = 0
        for (k,v) in freqs:
            self.freqs[k] = ( int(left*self.max), int((left+v)*self.max) )
            left += v

    def __optimize(self, f, t):
        u"""
            Подбор числа из диапазона [f, t) такого, чтобы в нем
            было максимально возможное на интервале число нулевых младших бит
        """
        #return int( (t-f)/2 + f )
        f = int(f)
        t = int(t)
        x = f ^ t
        if not x: return f

        xl = int( ceil( log(x, 2) ) )
        if not xl: return f

        mask_and = ~((1<<xl)-1)
        mask_or  = 1<<(xl-1)

        r = (f & mask_and) | mask_or

        return r

    def __find_interval(self, v):
        u"""
            Ищем интервал, которому принадлежит значение v
        """
        for ( c, (cf, ct) ) in self.freqs.items():
            if v>=cf and v<ct:
                return c

freqs = ( ('a',0.4), ('b',0.2), ('h',0.1), ('r',0.25), ('#',0.05) )
src = 'abraha#'
MAX = 100000000

coder = Arithmetic( freqs, MAX )

print 'SOURCE:  ', src

enc = coder.encode( src )
print 'ENCODED: ', enc

dec = coder.decode( enc )
print 'DECODED: ', dec

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

Процесс декодирования восстанавливает последовательность в том же порядке в каком она кодировалась. Определим множество нормализованных кодов (нормализация на целый интервал):

Естественно предположить, что рекурсия, применяемая для кодирования, действует и в обратную сторону. Начиная с исходного кода алгоритм шаг за шагом находит закодированный символ:

Если до этого момента понятно так и не стало, то нас спасет только пример.

Следуя примеру из предыдущей заметки, входная последовательность символов: a2a1a0a0a1a3. Распределение вероятностей: p = [0.2, 0.5, 0.2, 0.1]. Код: 0.74267578125.

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