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

Category was added automatically. Read all entries about "компьютеры".

satyr

7 + 14 == 14

Современные компьютеры, конечно, весьма загадочные звери.

Профилировал тут давеча callgrind-ом один бинарь: смотрю -- наверх всплывают две тяжёлые функции, допустим, A и B. На первую процессор тратит 14 млрд тиков, на вторую 7. Вклад всего остального, допустим, несущественен.

Казалось бы, должна ли программа стать быстрее на треть, если избавится в коде от функции B? Логика подсказывает, что да, и мало того -- под профайлером оно почти так и происходит. Но запускаешь релизную сборку -- по таймингам ускорение 2.5% вместо 33% :)

И причина древняя, и хорошо всем знакомая: функция B считает математику в тёплом и уютном кэше процессора, а A рыщет по памяти, инициализируя структуры и всячески перелинковывая их.

Короче, не очень понятно, как в таком недружелюбном мире профилировать что-то. Походу, надо сначала добиваться удовлетворительной работы программы в условиях 100%-го свопа на хард (причём, какой-нибудь старый 5400rpm), чтобы минимизировать все возможные random seek в алгоритме :)
satyr

Человеческий язык

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

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

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

Вот, например, фраза из учебника, второй урок: Chùng tôi ghi từ -- здесь нихрена нельзя сказать наверняка :) Это может быть: "Я записываю слова", "Я буду записывать слова", "Я записывал слово", "Мы (я и еще один чувак) записывали слово" -- здесь нет ни времени, ни числа, ничего полезного, кроме собственно значения лексем :) Все это добро нужно узнавать "из контекста", а поди еще объясни машине этот контекст...
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

Useless pc stuff

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

Целенаправленно продавать мне лень, а выкинуть или заныкать в шкаф жалко -- все же, хорошее рабочее железо, которое может кому-нибудь пригодится.

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

Торг, разумеется, возможен. Срок -- где-то до нового года.


Девайс 1: видеокарта Asus GeForce 7600GT 256Mb AGP. Допустим, 1000р.


Девайс 2: звуковуха Sound Blaster Live! 5.1. Хз, пусть будет 400р.


Девайс 3: SCSI плата для pci. Даже не знаю, назначайте сами цену :) Наверно, надо сразу нахаляву отдавать.


Девайс 4: материнка Gigabyte GA-8VT880 Ultra, процессор Intel P4 Prescott 3Ghz, кулер Zalman CNPS7000-Cu, оперативка DDR-400 2x512 + 2x1024. Было бы круто отдать все скопом. По-отдельности: 1600 за память, 1200 за cpu+cooler, 800 за мать. Вместе пусть будет 3500.


Разумеется, из всего этого можно собрать комп :) Достаточно добавить хард и корпус.
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, который я собираюсь туда водрузить :)