Archive for category Performance
сумасшедший алгоритм
Posted by John Lepikhin in Performance, программирование on November 16th, 2009
Уже 3-й день размышляю над алгоритмом следующей задачки.
Дано:
- Есть кластер. В кластере живёт несколько узлов. В узле живёт несколько веб-серверов. В веб-сервере живёт несколько аккаунтов. В аккаунте живёт несколько сайтов.
- Для каждого сайта известна текущая нагрузка. Соответственно, известна нагрузка для каждого из аккаунтов.
- Известно количество сайтов в каждом из аккаунтов.
- Для каждого аккаунта сказано, на скольких минимум узлах (не веб-серверах) он должен присутствовать. Пусть это будет μ.
- Для каждого аккаунта известно, какие веб-серверы обрабатывают его в данный момент.
Задача состоит в том, чтобы перераспределить аккаунты по веб-серверам так, чтобы
- Аккаунты с максимальной нагрузкой присутствовали на максимальном числе узлов. Ну и соразмерно все остальные.
- Каждый аккаунт представлен минимум на μ узлах.
- В пределах одного узла каждый аккаунт представлен лишь один раз.
- Текущая нагрузка наиболее равномерно распределена между всеми узлами (или с каким-то коэффициентом — не суть).
- Сайты максимально равномерно распределены между всеми веб-серверами, чтобы минимизировать объём памяти каждого из процессов веб-серверов.
- Сделать это всё так, чтобы изменения коснулись по возможности минимального количества веб-серверов, чтобы затем минимум их пришлось заставить перечитывать конфиг.
- Делать это каким-то хитрым алгоритмом т.к. простой перебор на потенциальные десятки тысяч сайтов может отожрать немало проца и памяти…
Понятно, что идеально соблюсти все условия не получится. Соответственно, надо либо расставить приоритеты условиям, либо ввести коэффициент максимальной допустимой погрешности решения. Решение вырастает весьма объёмным даже для простого перебора. Мне страшно представить о часе, когда надо будет искать более изящные решения.
Решение для решателя Sudoku
Posted by John Lepikhin in Blogroll, Ocaml, Performance, программирование on June 10th, 2009
Хотел вечерком размять мозг — набросать какой-нибудь особенно красивый решатель Sudoku на Ocaml. Но возникла мысль изучить вражеские аналоги. Итак, решатель Sudoku размером 800 с небольшим байт:
include Set.Make(struct type t = (int * int) * int let compare = compare end) let (@) g f x = g (f x) and id x = x and sw f x y = f y x and zip x y = (x, y) let fold9 f = let rec loop i = if i>8 then id else loop (i+1) @ f i in loop 0 let fold81 f = fold9 (fold9 @ (@) f @ zip) let mark ((i,j),x as e) : t -> t = add e @ fold9 (fun k -> remove ((i/3*3 + k/3, j/3*3 + k mod 3), x) @ remove ((i,j),k) @ remove ((i,k),x) @ remove ((k,j),x)) let search = let g p f s = fold (f @ sw mark s) (filter ((=) p @ fst) s) in fold81 g let read () = let f p = Scanf.scanf "%d " (fun x -> if x>0 then mark (p,x-1) else id) in fold81 f (fold81 (fold9 @ ((@) add @ zip)) empty) let print s () = let pr ((i,j),x) = Printf.printf "%d%c" (x+1) (if j=8 then '\n' else ' ') in iter pr s; print_newline ();; search print (read ()) ()
Вы посмотрите эту красоту, это же [почти] совершенство! А если учесть, что 272 байта — это чтение задачи с STDIN и вывод результата, размер кода сокращается до менее чем 600 байт.
ocaml-epoll
Posted by John Lepikhin in Ocaml, Performance, программирование on May 29th, 2009
Написал биндинг для работы с epoll(7). Пока бета, но на ней уже ради эксперимента написал успешно работающий маленький веб-сервер :) Скачать можно со страницы Software. epoll является аналогом select() и poll(), но с увеличением количества обрабатываемых сокетов сложность остаётся O(1), что позволяет без особых задержек обрабатывать тысячи параллельных соединений.
Nginx против oProxy: друг другу сливаем :)
Posted by John Lepikhin in Ocaml, Performance, oProxy, программирование on February 1st, 2009
Потестировал производительность проксирования HTTP трафика. Результаты местами получились весьма неожиданными.
Повторю, тестировалось именно проксирование. Известно, что при прямой отдаче и Apache, и Nginx использует ядрёный вызов sendfile(), который отдаёт содержимое файлика в сокет без лишних копирований. Это неинтересно. А вот проксирование — это совсем другое дело. В ядре пока что ещё нет прямых путей для копирования из сокета в сокет (есть полупрямой вариант splice() + pipe(), но как выяснилось он даже не на всех современных ядрах работает).
Итак…
oProxy: производительность mysql_proxy
Posted by John Lepikhin in Performance, oProxy on November 25th, 2008
Сократил оверхед до 56 МИКРОсекунд на запрос (т.е. запрос отдаётся в среднем медленнее на это время, чем если бы подсоединялись напрямую). Для сравнения, у Mysql Proxy это значение заявлено в 400 МИКРОсекунд, т.е. 7 раз больше. Но у меня практически никакого анализа пакетов не делается, только выясняю подсоединившегося пользователя и собираю статистику. Считал скриптом:
time perl -MDBI -e ‘$dsn = “DBI:mysql:database=mysql;host=127.0.0.1;port=5501″;$dbh = DBI->connect($dsn, “user”, “анунеподглядывай”);for(0..100000){$s = $dbh->selectall_arrayref(”select repeat(100000000000000000, 10)”);}’
Во время выполнения, oProxy ел около 31% CPU, MySQL 25% Perl 50%. Ещё есть куда расти.
oProxy (о прокси, about proxy)
Posted by John Lepikhin in Ocaml, Performance, программирование on November 14th, 2008
Настроение: подшофе. Первый эксбиционисткий пост, как и положено в б-сферах. Прости меня, г-поди!
Сравнение ЯП
Posted by John Lepikhin in Performance on August 9th, 2007
Любопытный сайт, сравнивающий пару десятков языков по производительности и ресурсоемкости на реальных алгоритмических задачах. Любители священных войн могут обратить внимание на производительность PHP по сравнению, например, с Perl: