Category: компьютеры

satyr

Порабощаем shootout, блинчеги

Продолжаем развлекаться =)

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

Выбор пал на fannkuch-redux, для которого (как и для хамелеонов) отсутствовала Lisp/SBCL-реализация. Итак,



OWNED, причем без шансов. Как видно из картинки, предыдущие лидеры там толпятся как бараны вокруг отметки в 17 секунд. Пожалуй, что для стандартного подхода к решению это предел.

Я же решил зайти с основного козыря CL: сгенерить максимально специфический для входных данных код, а потом отважно его исполнить.

(defun main (&optional force-n)
  (let* ((args (cdr sb-ext:*posix-argv*))
         (n (or force-n (if args (parse-integer (car args)) 12))))
    (multiple-value-bind (checksum max-flips-count)
        (funcall (the function (eval `(deffannkuch ,n :workers 4 :worker-chunk-size 12000))))
      (format t "~a~%Pfannkuchen(~a) = ~a~%" checksum n max-flips-count))))

Заметили там мигающий "eval"? =) Вот это оно. Между прочим, +0.35 секунд на кодогенерацию + компиляцию в рантайме.

Итак, теперь вкрадце о задаче. На вход подается число N, допустим, 4.

Этап первый: надо сгенерировать все перестановки 1 .. N чисел. Для четырех это 1234, 2134, 2314, 3214 и так далее (всего 24 перестановки — 4!). Вроде пока ок, но тут небольшая засада: последовательность генерации перестановок строго заданная (в разделе с описанием приведены данные и ссылка на алгоритм, как такую последовательность генерить).

Этап второй: берем очередную перестановку (допустим, 4132), берем первый элемент (4) и меняем порядок следования такого количества элементов в последовательности на обратный: 2314. Считаем, сколько раз надо произвести такую операцию, чтобы получить в начале единицу: 4132 -> 2314 -> 3214 -> 1234, итого 3 переворота.

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

В итоге нужно получить контрольную сумму и максимальное количество переворотов среди всех перестановок. Для N=4 максимальное количество переворотов равно четырем (последовательность "2413").

Наверно, самая наглядная реализация здесь -- это питонячья версия (решение в лоб). Всего 45 строк, но с более чем пятисоткратным отставанием по быстродействию от лидера (от меня, тоесть =)). Остальные решения пытаются применять всяческие оптимизации, и здесь наилучшего результата добился Oleg Mazurov со своей жаба-версией.

Я же решил действовать хитростью и коварством (ну как обычно). Мой стандартный алгоритм метапрограммирования выглядит так:

  1. Представить себе, как должна выглядеть максимально производительная программа, при условии фиксированных входных данных (все константы).
  2. Написать программу, которая по заданным входным данным генерирует такую "максимально производительную программу".

С хамелеонами у меня такой фокус, разумеется, не прошел: там все данные и так фиксированные, а перфоманс упирается в синхронизацию потоков. Но с "блинами" фишка сработала.

Итак, положим, у нас фиксированная N, например, 3. Как бы я написал максимально шуструю программу, печатающую все последовательности? Очевидно, вот так =)

(format t "123, 213, 231, 321, 312, 132, ")

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

(let ((tmp-0 1) (tmp-1 2) (tmp-2 3))
  (loop :repeat 3
     :do (prog1
             (let ((tmp-3 tmp-0) (tmp-4 tmp-1))
               (loop :repeat 2
                  :do (prog1
                          (let ((a tmp-3) (b tmp-4) (c tmp-2))
                            (format t "~a~a~a, " a b c)
                        (let ((first tmp-3))
                          (setf tmp-3 tmp-4
                                tmp-4 first)))))
           (let ((first tmp-0))
             (setf tmp-0 tmp-1
                   tmp-1 tmp-2
                   tmp-2 first))))))

На самом деле, стоит только прикинуть вид "максимально специфичной" для конкретных зафиксированных данных программы, как сразу становится ясен паттерн, как их генерировать. Я здесь выделил цветами RGB, соответственно, первый, второй и третий цикл в порядке их вложенности. В конце каждой итерации каждый цикл делает rotate для своих элементов, в соответствии с алгоритмом генерации перестановок. Для последнего (третьего) вложенного цикла объявление loop опущено (так как там получился бы бессмысленный ":repeat 1") и никакие элементы не сдвигаются (так как там только один, последний).

По-моему, паттерн ясен, понятен, нагляден и вообще всем хорош =) Соответственно, для перестановок N элементов мы генерим N вложенных циклов, причем каждый i-ый цикл объявляет себе (N - i) переменных, затеняя такие же родительские и наследуя остальные. Свои переменные он в конце итерации ротирует, родительские не трогает. Суммарно, например, для N=12 будет объявленно (12+11+10+9+8+7+6+5+4+3+2+12)=89 переменных.

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

FANNKUCH-REDUX> (let ((start-from 0) (total-count 24))
                  (with-permutations ((a b c d) start-from total-count)
                    (format t "~a~a~a~a, " a b c d)))
0123, 1023, 1203, 2103, 2013, 0213, 1230, 2130, 2310, 3210, 3120, 1320, 2301, ...

Реализацию можно посмотреть в коде бенчмарка, она небольшая: исходник.

Далее, что касается подсчета количества переворотов (flips). Здесь все еще элементарней: зная N, легко сгенерировать необходимый switch/case:

FANNKUCH-REDUX> (macroexpand 
                 '(with-flips-count ((a b c d) flips-count)
                   'my-code-here))
(LET ((FLIPS-COUNT 0))
  (DECLARE (TYPE FIXNUM FLIPS-COUNT))
  (UNLESS (ZEROP A)
    (LOOP (INCF FLIPS-COUNT)
          (COND ((= A 1) (WHEN (ZEROP B) (RETURN)) (ROTATEF A B))
                ((= A 2) (WHEN (ZEROP C) (RETURN)) (ROTATEF A C))
                ((= A 3) (WHEN (ZEROP D) (RETURN)) (ROTATEF A D) (ROTATEF B C)))))
  'MY-CODE-HERE)
T

Ну и все, теперь у нас в зубах достаточно инструментов, чтобы легко и припеваючи решить всю задачу для фиксированного N. Вот так, например, это будет для N=5 (я для наглядности подсветил вышеприведенные макросы):

(let ((max-flips-count 0)
      (checksum 0)
      (sign t)
      (start-from 0)
      (total-count 120))
  (with-permutations ((a b c d e) start-from total-count)
    (with-flips-count ((a b c d e) flips-count)
      (when (> flips-count max-flips-count)
        (setf max-flips-count flips-count))
      (incf checksum (if sign flips-count (- flips-count)))
      (setf sign (not sign))))
  (values checksum max-flips-count))

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

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

Хамелеончеги: возвращение

Итого, погнали по следам предыдущего поста.

  • На двухъядерном линуксе у dmitry_vk моя лисповая реализация оказалась быстрее жабьей почти на 40% (пруф)
  • У меня на ноуте (Core Duo T6600) бенчмарк отработал еще быстрее: 2.956s (напомню: на десктопе Core Quad Q6600, результат 7.4s)
  • Задачу зааппрувили на shootout, она ожидаемо неплохо выступила на x86 Core Quad и x64 Core Quad (восьмое и девятое место соответственно), но омерзительно адски слила всем на одном ядре, включая даже петон.


Выводы следующие. Как правильно было замечено здесь, Core Quad является специфическим процессором: это скорее двухпроцессорный Core Duo, чем четырехъядерный cpu. Отсюда несравненно лучшие результаты бенча на Core Duo.

Если б у меня была возможность четко приклеить нити к физическим ядрам, я бы получил суровый выигрыш, запуская первую игру на одном "процессоре", а вторую на "втором". Отсюда вопрос первый: правильно ли я понимаю, что в SBCL управлять affinity я не могу никак?

Вывод второй: запускаясь на однопроцессорной машине мне надо, во-первых, обнаружить это (вопрос: как?), а во-вторых, убрать пустой спин из ожидания, крутясь на thread-yield. Есть ли какой-нибудь универсальный способ определить однопроцессорность рантайма, помимо распарсивания /proc/cpuinfo в луниксе и sysctl в bsd?
satyr

Оптимизация: i386?

Блин, там в этом open street map еще один баг: в российском файлике russian_federation.osm (тот самый, который двухгиговый xml) обнаружился relation, который включает сам себя (бесконечная рекурсия). Ладно, надеюсь, этот конкурс от fprog.ru поможет проекту osm.

Но не суть, у меня вот какой вопрос.

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

На sbcl/amd64 я с чистой душой пользуюсь типом '(unsigned-byte 60) (какие-то биты откушены под таг), он прекрасно влезает в регистр и мгновенно считается.

А на sbcl/i386 такой тип в регистр уже не влезает, и переменная начинает бокситься, плюс вся арифметика с таким числом генерируется #GENERIC- :(

Я, честно говоря, сломал бошку, как заоптимизировать это место на i386. 1349 вон подсказывает, что из юзер-левела можно как-то определять свои типы. Наверное, что-то можно изобразить для 64-х битного числа на базе (simple-array '(unsigned-byte 8) (8))? Или это будет еще тормознее #GENERIC-операций?
satyr

MapReduce und SBCL multithreading

Это поразительно, но какой-нибудь свободной имплементации MapReduce для CL я не нашел :) В гугле триллион статей, и все они начинаются словами, мол, map и reduce -- это из лиспа, но мы сейчас все заимплементим вот-на-таком-языке.

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

Сразу настроился сделать аккуратно и по-уму, чтобы получить возможность сразу использовать в бою. Посему пошел по следующему плану:

1. Пул тредов
2. По-возможности без мьютексов, где возможно заменить блокировки на compare-and-swap.
3. Не заморачиваться портабельностью, вместо этого вылизать под sbcl.
4. Интерфейс оставить такой же, как и у mapcar.
5. Поддержать рекурсивные вызовы, чтоб не воткнулось где-нибудь на вечной блокироке.

Внезапно провозился заметно больше чем ожидал, но справился:

CL-PMAP> (pmap #'+ '(1 2 3) '(4 5 6))
(5 7 9)


Пакетик я немного облагорожу и, конечно, выложу куда-нибудь. Но прежде хочу отметить некоторые любопытные эффекты, с которыми я столкнулся в процессе экспериментирования с новой игрушкой.
Collapse )
satyr

Вопрос

Интересно, а можно подключить питание свича (стандартный такой адаптер в розетку) в бесперебойник? Там на нем входы такие же, как в компьютерные блоки питания.

Может, кто-нибудь видел в природе переходники?
satyr

Upgrade

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

А именно, докупил два гига оперативки, терабайтный хард и упс, следующих пород:

Kingston DDR 1Gb, 400MHz x 2


SATA 1TB GB WD1000FYPS SATA II 7200 rpm 16mb GREENPOWER


UPS APC Smart-750VA (SUA750I)


Терабайтный хард, это, конечно, определенный риск. Потому как, если полетит, то это будет epic fail :) Но будем надеятся, что его спасет хорошая репутация WD, бонусы модели GREENPOWER, упс и zfs, который я собираюсь туда водрузить :)
satyr

Рынок процессоров

В принципе, уже ежу понятно, что прогресс в процессорной нише остановился в росте и развивается теперь вширь. Пока Intel и AMD меряются количеством ядер -- два против четырех, как-то относительно незаметно для прессы выплыла вторая версия многообещающего процессора от Sun -- Niagara 2, в простонародье Sun UltraSpark T2. На этом фоне интел с амд выглядят просто жалко :)

UltraSpark T2 -- это уже 8 ядер, по 8 аппаратных тредов на каждом, и, самое главное -- у каждого ядра теперь свой FPU! Результаты достаточно впечатляют: по тестам sap tier2 жалкий однопроцессорный сервак Fujitsu с тактовой частотой 1.4GHz на десятом солярисе обходит большинство серверов, вооруженных 8-ми процессорными двухъядерниками =)

Вы представляете, насколько ниже у него энергопотребление? ;)

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

Вот в этом треде на рсдн товарищ Gaperton, в свое время, подробно рассказывал о преимуществах аппаратной многозадачности. Вкрадце, суть там вот в чем: самая неприятная проблема современного железа в том, что производительность памяти не поспевает за производительностью процессоров. Есть очень хорошая статья на эту тему -- What every programmer should know about memory, там очень подробно расписана ситуация. Опять же, для тех, кто не любит много читать, вкрадце идея: у сегодняшней оперативки очень высокая латентность. Поэтому достать значение из ячейки памяти примерно в 240 раз медленнее, чем из регистра, и ~ в 100 раз медленее, чем из кеша. Отсюда следствие -- когда программа обрабатывает какие-то данные, которые не помещаются в кеш, процессор тупо простаивает, ожидая, пока к нему прилетят данные.

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

Хорошо, почему же тогда общество все еще носится с интелями? Да очень просто, ниагара -- это sparc, а не x86. А всемирно любимая операционка малолетних геймеров и "экспертов" с ixbt, как известно, ни на чем больше не запускается ;)
satyr

Robots friendly

Синхронизация Palm Tungsten T5 с FreeBSD 6.2 через bluetooth.

Задача достаточно хорошо решается с помощью гугла, пока не упрешься в
один пренеприятный баг в PalmOS 5.0, которая стоит на T5. Для тех, кто
кому еще вдруг предстоит, выкладываю для индексации HOWTO.

Collapse )

Опенсурс -- великая сила =)

Ключевые слова для релевантности: Palm Tungsten T5, FreeBSD 6.2, HotSync, Bluetooth, PalmOS 5.0 bug
satyr

Denial Of Service

Пока я тут был в отпуске, рабочий быдло-exchange и девелоперский сервак активно играли в пинг-понг. На серваке в системе контроля версий у меня настроены уведомления на почту, когда кто-нибудь что-нибудь коммитит новое. А перед уходом в отпуск, я установил в своем почтовом аккаунте автоответ, типа, меня сейчас на месте нет, обращайтесь к шефу.

Уехал я, значит, в отпуск. А люди тут коммитят. На каждый коммит мне идет нотификация: "Такой-то человек проапдейтил такой-то файл". На каждую такую нотификацию ексчейндж прилежно отвечает: "I'm currently out of the office". На каждый такой ответ девелоперский сервак отвечает аутлупом, что, дескать, не могу доставить ваше сообщение, бо нет такого аккаунта. На каждый такой аутлуп ексчейнж предупреждает, что я не могу прочитать это сообщение, потому что я в отпуске... ну и так далее :) Кто из серваков победил -- не знаю.

Но это не самое смешное. Я эту историю рассказал шефу за обедом, на что он припомнил еще более смешной случай из касперской жизни.

Произошел он лет семь назад. Каждому покупателю антивируса предлагалась возможность подписаться на рассылку какой-то фигни, типа новостей. Рассылка была устроена так: на почтовом сервере был заведен адрес (допустим, subscribes@...), входящие письма на который автоматически рассылались всем подписчикам. Подписчиков было около 20 тыщ человек.

И все работало хорошо, пока в один прекрасный день кто-то злой снаружи не обнаружил этот адрес subscribes@, который, почему-то, оказался публичным. Чтобы проверить, что это за адрес, этот нехороший дядя послал туда какой-то троян или вирус.

Вирус прилежно разослался всем двадцати тысячам подписчикам :) Но не тут-то было! У многих из них стоял Антивирус Касперского, который такое письмо зарезал. Да не просто зарезал, а еще и послал на него ответ: "Мужик, в твоем письме я обнаружил Вирус, и письмо я не доставил. Будь добр, больше так не делай". К ответу он приаттачил исходное письмо с трояном.

Беда оказалась в том, что Reply-To в исходном письме указывал на subscribes@. Двадцать тысяч человек прислали на этот адрес письмо с приаттаченым письмом, в котором был приаттачен вирус. Все это добро снова разослалось им обратно, только в гораздо больших масштабах. Разумеется, доблестные Антивирусы Касперского и в этот раз обнаружили зловредного трояна, и снова предупредили отправителя об этом....

Так продолжалось не очень долго, благо почтовый сервер, обслуживающий subscribes@ при такой нагрузке лег очень быстро :) Но пользователи успели порядком удивиться, с чего вдруг касперский начал их в таких масштабах спамить троянами =)
satyr

Ministat

Глянул я в access.log и удивился. Нет, вполне закономерно, что 95% моих френдов - вендузятники (это везде так). Более того, проскочил один линуксоид. Также была пара пользователей freebsd, один из которых я, а второй был вычислен по ip: redchrom. Но самое удивительное оказалось вот что: меня читают два пользователя макос! =)

Mozilla/5.0 (Macintosh; U; PPC Mac OS X Mach-O; en-US; rv:1.7.12) Gecko/20050915 Firefox/1.0.7
Mozilla/5.0 (Macintosh; U; Intel Mac OS X; en-US; rv:1.8.0.6) Gecko/20060728 Firefox/1.5.0.6

Один из них даже тру, на ппц =))

Аннуко признавайтесь, кто? =)