Быстрая сортировка на AS 3.0

У большинства людей на слово «flash» появляется две главные ассоциации:

1. Надоедливые баннеры, часто непристойного содержания.
2. Меееедленно и тормозит.

И то и другое по большей части, правда, но только с поправкой «в большинстве своём». Действительно большая часть flash-контента это баннеры. Да они сильно тормозят, но виновата в этом не технология flash и не компания Adobe. Большинство тормозящих flash-приложений просто написаны так (криворукими) ленивыми программистами. Так уж повелось, что flash стал платформой для быстрой «красивой» интерактивной рекламы, но ведь это далеко не всё, на что он способен. Достаточно популярны flash-игры, которые часто содержат не только вычислительно сложную физику, но часто и не менее сложную игровую логику. Поэтому раз в сто лет появляется человек, которому нужно написать флешку, которая должна работать быстро. И вот тут и появляется проблема – flash действительно небыстрая платформа. Что делать если тормозит нормально написанный, с алгоритмической точки зрения код? Когда алгоритмы уже отточены, нужно оптимизировать код.

Предложу, наверное, самый извращённый выход из ситуации – шейдеры.



Начиная с 10 версии плеера, появились возможности использования видеокарточи как ускорителя. Вместе с этим появилась и поддержка шейдеров. Именно о них и пойдёт речь далее. На компьютерах с аппаратной поддержкой шейдеры выполняются на видеокарте, в противном случае на центральном процессоре. Даже в случае выполнения на ЦП шейдер существенно быстрее кода Action Script. Когда я всё это узнал, я был вне себя от радости, я думал, а почему бы не писать нагруженную логику в шейдере.

Если в двух словах, то пиксельный шейдер это специальная программа на специальном языке, изначально задуманная для обработки картинок. На входе у шейдера всегда есть картинка, или несколько картинок, а вернуть он должен пиксель. Шейдер вызывается для каждого пикселя результирующей картинки. Это больше всего напрягает. Единственное, что может вернуть один экземпляр шейдера – один пиксель, максимум 4 флота. Зачем это сделано понятно: шейдер можно выполнять в столько независимых потоков, сколько пикселей на итоговой картинке.

Я наивно предполагал, что во флеше адекватные шейдеры как в нейтив случае openGL или DirectX, с которыми я уже имел дело. Радость была недолгой: в флеш можно загружать только очень ограниченные по набору инструкций шейдеры. Главные обломы:

1. Нет функций – переживём подумал я, всё можно инлайнить, а рекурсия не большая потеря
2. Нет даже goto
3. И главный фейл – нет циклов. Вообще никак нельзя исполнить одну и ту же строку кода больше одного раза.

Таким образом Pixel Bender превращается в язык тривиальных эффектов. Меты почти было рухнули, но нет. Я не я, если не напишу на «этом» даже не Тьюринг-полном обрезке Pixel Bender’а что-нибудь из тривиальных алгоритмов. Первой на ум пришла идея сортировки массива. Что может быть проще? Самая простая лаба у студентов первокурсников. Эта тема весьма актуальна в флеше, так как стандартная сортировка у Array и Vector – пузырёк.

Выбор сделан, всё хорошо? Ан нет, не так всё просто – циклов-то нет. Все приспособленные для шейдеров сортировки сразу обламываются на этом пункте. Придётся придумывать свою.

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

input image4 src;
    output pixel4 dst;
 
    void
    evaluatePixel()
    {
        pixel4 cur;
        pixel1 b;
 
        float2 coord = outCoord();
        cur = sampleNearest(src, coord);
 
        if (cur.r>cur.g)
        {
            b = cur.r;
            cur.r = cur.g;
            cur.g = b;
        }
        if (cur.b<cur.g)
        {
            if (cur.b<cur.r)
            {
                b = cur.b;
                cur.b = cur.g;
                cur.g = cur.r;
                cur.r = b;
            }
            else
            {
                b = cur.g;
                cur.g = cur.b;
                cur.b = b;
            }
        }
        if (cur.a<cur.b)
        {
            if (cur.a<cur.g)
            {
                if (cur.a<cur.r)
                {
                    b = cur.a;
                    cur.a = cur.b;
                    cur.b = cur.g;
                    cur.g = cur.r;
                    cur.r = b;
                }
                else
                {
                    b = cur.a;
                    cur.a = cur.b;
                    cur.b = cur.g;
                    cur.g = b;
                }
            }
            else
            {
                b = cur.b;
                cur.b = cur.a;
                cur.a = b;
            }
        }
 
        dst = cur;
    }

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

Следующая идея была ещё проще первой. Раз уж научились сортировать по 4, то сам Бог велел реализовать сортировку слиянием. Ведь, по сути, выполнены первые её два шага. Слияние на шейдере – нереально без циклов, но почему бы не написать его на Action Script’е? Написал.

private function shaderMerge():void 
        {
            width = l * 0.025;  
            height = 10;
 
            shader.data.src.width = width;
            shader.data.src.height = height;
            shader.data.src.input = src;
 
            shaderJob = new ShaderJob(shader, dst, width, height);
            //shaderJob.addEventListener(Event.COMPLETE, shaderJobComplete);  
            shaderJob.start(true);
        }
 
        private function Merge(Size:int, p:int):void
        {
            var cur1:Number;
            var cur2:Number;
            var curNumber:int = p;
            var p1:int = p;
            var p2:int = p + Size;
            while ((p1 < p + Size) && (p2 < p + 2 * Size) && (p2 < l))
            {
                cur1 = src[p1];
                cur2 = src[p2];
                if (cur1 < cur2)
                {
                    dst[curNumber] = cur1;
                    p1++;
                }
                else
                {
                    dst[curNumber] = cur2;
                    p2++;
                }
                curNumber++;
            }
            for (var i:int = p1; i < p + Size; i++)
            {
                dst[curNumber] = src[i];
                curNumber++;
            }
            for (var j:int = p2; (j < p + 2 * Size) && (j < l); j++ )
            {
                dst[curNumber] = src[j];
                curNumber++;
            }
 
        }
 
        public function Sort():Vector.<Number>
        {
            var t1:int;
            var t2:int;
 
            t1 = getTimer();
 
            shaderMerge();
 
            t2 = getTimer();
            time = t2 - t1;
 
            buf = src;
            src = dst;
            dst = buf;
 
            var cur1:Number;
            var cur2:Number;
            var curNumber:int;
            var p1:int;
            var p2:int;
            var partSize:int;
            for (var step:int = 4; step < l; step*=2 )
            {
                if (step == 4)
                {
                    trace("4");
                }
                for (var p:int = 0; p < step*int(l/step); p += 2 * step)
                {
                    //Merge(step, p);
 
 
                    curNumber = p;
                    p1 = p;
                    p2 = p + step;
                    while ((p1 < p + step) && (p2 < p + 2 * step) && (p2 < l))
                    {
                        cur1 = src[p1];
                        cur2 = src[p2];
                        if (cur1 < cur2)
                        {
                            dst[curNumber] = cur1;
                            p1++;
                        }
                        else
                        {
                            dst[curNumber] = cur2;
                            p2++;
                        }
                        curNumber++;
                    }
                    for (var i:int = p1; i < p + step; i++)
                    {
                        dst[curNumber] = src[i];
                        curNumber++;
                    }
                    for (var j:int = p2; (j < p + 2 * step) && (j < l); j++ )
                    {
                        dst[curNumber] = src[j];
                        curNumber++;
                    }
                }
                buf = src;
                src = dst;
                dst = buf;
            }
            return src;
        }

Результаты скорости работы.
Тестирование проводилось на компьютере со следующей конфигурацией: Core 2 Duo E6600? 2GB RAM Dual Channel, Intel GMA 3100. Результаты:
standart Vector.sort: 3678
without shader: 210
with shader: 188
shader time: 5

Получилось неплохо: за счёт выполнения первых операций на шейдере получается прирост в 10% относительно сортировок слиянием написанной на чистом Action Script без шейдеров. Так же проверял на атомном нетбуке и компе с нормальной дискретной видюшкой, и там и там картина та же - шейдер даёт небольшой, но всё таки прирост. Вот уже кое-что подумал я. Надо ещё ускорится.

Ускорится ещё можно, взяв на шейдер и следующую итерацию слияния. Но тут нужно сливать по 4, то есть 8 возвращаемых элементов, а можно вернуть только 4? Решение не заставило себя долго ждать. Пусть шейдер в зависимости от пикселя выполняет одно из следующих действий:

1. Начало слияния четвёрок и получение первых четырёх элементов результирующей восьмёрки.
2. Точно такое же слияние как и в первом пункте, только пойдём с конца четвёрок и получим последние 4 элемента из результирующей восьмёрки.

Идея неплохая, но при реализации произошло страшное – кончилась мотивация. Как только опять будет свободное время, в которое захочется попинать шейдеры, обязательно напишу.

Исходники тут.