Category: it

satyr

wtf

Рассматриваю кусок кода на гитхабе:

    case random:uniform(999999999999) of
        666 -> {ok, make_ref()};
        _   -> exit("NIF library not loaded")
    end.

Не, я всё понимаю, что управление в эту функцию попасть не может, если nif нормально подгрузился. Но в чём прикол с рандомным успехом? :) Там же всё дальше в таком духе.
satyr

Весёлые приключения одной аллокации

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

Про сам перформанс мб в другой раз, а пока я бы поделился некоторыми наблюдениями насчёт собственно языка.

Я уже говорил, что вижу в Rust достаточно большой потенциал. И тут даже дело не в том, что за ним стоит мозилла, и что он динамично развивается, и что там дружелюбное (до приторности) коммьюнити, и что разработчики (пользуясь бета-статусом релиза) смело тащат в язык разные модные конструкции из других языков и всячески экспериментируют с ними. Этого добра (в той или иной степени) полно и в других подобных хипстерских языках из т.н. "практической ниши", типа Go, Scala, D, какой-нибудь Nim и тд. Но, в отличие от них, мне кажется, что Rust выстрелит.

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

  • Ownership -- это, грубо говоря, RAII на стероидах.
  • Borrowing + lifetimes -- это концепция "безопасных" указателей, при этом в транслированном коде это обычные сишные указатели, а вся безопасность исключительно в compile-time.

Идея с ownership-ом, при этом, оказалась настолько удачной, что спустя некоторое время начали всплывать различные приятные, но при этом халявные бонусы, вроде дружелюбной многопоточности, которая при этом не завязана на immutable-state, как в других языках (более подробно можно ознакомиться в Fearless Concurrency).

И, что ещё любопытно, благодаря ownership-у, масштабный проект на Rust, потенциально, должен иметь заметно более высокую производительность, нежели на C++ или Java (включая их производные). Дело в том, что сложные абстракции в этих языка (а таковыми все крупные приложения обязательно постепенно обрастают) требуют множество аллокаций/деаллокаций и копирования. Если язык при этом поощряет активное использование неизменяемого состояния, то копирований и аллокаций будет ещё больше (да, компиляторы, конечно, пытаются оптимизировать эти места по-максимуму, но, в среднем, тенденция сохраняется). За всё это нужно расплачиваться либо паузами GC, либо пониженной производительностью C++ приложения (при массированной нагрузке на аллокатор можно получить фрагментацию памяти).

В идиоматической программе на Rust физических аллокаций и копирований заметно меньше, за счёт того, что, благодаря ownership-y, жизненный цикл объектов получается достаточно длинным. Я попробую сейчас продемонстрировать это на примере одной аллокации из моей флешмобной реализации бенчмарка.

Итак, познакомимся с хорошо знакомым всем объектом "строка". Предположим, её зовут Зинаида, и впервые она рождается в функции read_line_loop в этом куске кода:

            let mut line = String::new();
            match try!(reader.read_line(&mut line)) {
                0 => return Ok(()),
                _ => manager.feed_workload(line),
            }

В отличие от языков со сборкой мусора, здесь у нас всё детерминировано: я могу точно сказать, что первый malloc будет вызван в String::new(), и затем, в методе read_line, скорее всего, будет выполнен realloc. Далее Зинаида, а равно как и всевозможные права на неё отдаются в метод Manager::feed_workload(), после чего в рассматриваемом куске кода мы про неё забываем. Это называется "ownership transferring". Всё, далее вызовов free здесь в радиусе функции нигде сгенерировано не будет, а Зинаида будет прибита где-то в feed_workload, вместе со своими аллокациями в куче.

Идём дальше, в метод Manager::feed_workload().

impl Manager {
    // ... some code
    fn feed_workload(&mut self, line: String) {
        // ... some code
        self.pool.slave_mut(ready_slave_idx).tx.send(Command::Workload(line)).unwrap();
        // ... some more code
    }

Зинаида (переменная "line") оборачивается в алгебраический тип Command::Workload, формируя тем самым новый объект. Физически, никаких дополнительных аллокаций и деаллокаций кучи здесь не происходит: выделяется небольшой объект на стеке, и присваиваются несколько переменных (указатели внутри объекта Vec, который является составной частью String). Зинаида всё ещё жива, хотя теперь она является частью другого объекта, вот такого типа:

enum Command {
    Workload(String),
    Terminate,
}

Далее, все права на Зинаиду (в составе объекта Workload) полностью передаются в метод send объекта типа mpsc::Sender<Command>. Деаллокаций всё ещё нет, содержимое строки, вычитанное из stdin лежит без изменений в регионе памяти, который всё ещё валиден и доступен по старому указателю.

Пропустив некоторое количество магии, которое происходит в кишках mpsc, мы переходим к следующему месту, где мы встречаемся с Зинаидой. Это функция slave_loop, результат Receiver::recv:
        match rx.recv() {
            Ok(Command::Workload(line)) => {
                match SlaveTask::parse(&line) {
                    Ok(task) => {
                        // some code skipped
                    },
                    Err(error) => {
                        tx.send(TaskResult::Error(line, error)).unwrap();
                        // some code skipped
                    },
                }
            },
            Ok(Command::Terminate) | Err(..) =>
                break,
        }

Тут уже ситуация любопытней. Сначала следует осознать, что вот это место, где мы щас находимся, на минутку, контекст другого треда. Ок, ладно. Итак, Зинаида возвращается нам нетронутой в составе объекта Workload, который деструктурируется в первой ветви паттерн-матчинга. Собственно, Зинаида в этом блоке теперь доступна под биндингом "line", тип которого String (не ссылка, а именно что ownership). Дальше происходит вот что:

  • Сначала, мы "одалживаем" Зинаиду методу SlaveTask::parse (это borrowing), то есть, по выходу из этой функции она всё ещё наша.
  • Если парсинг завершён успешно, Зинаида будет, наконец, уничтожена на выходе из блока ветви Ok. Здесь произойдёт долгожданный вызов free.
  • Если же мы попали в ветвь Err, то мучения Зинаиды на этом не заканчиваются. Она снова оборачивается в тип TaskResult::Error (это снова, напоминаю, zero copy), и права на неё передаются в send.

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

    fn recv_any(&mut self) -> (usize, TaskResult) {

Здесь мы получаем её в составе TaskResult::Error из recv и возвращаем во втором элементе тупла (это ownership transfer). Далее:

    fn poll(&mut self) -> TaskResult {

Ничего интересного, передаём власть над результатом выше по стеку.

fn read_line_loop(manager: &mut Manager) -> Result<(), io::Error> {
    // code skipped
    loop {
        // code skipped
        process_result(manager.poll());

Получаем из одного места и сразу отдаём в process_result. Зинаида всё ещё путешествует в составе TaskResult::Error.

fn process_result(result: TaskResult) {
    match result {
        // code skipped
        TaskResult::Error(input, error) => { 
            let _ = writeln!(&mut io::stderr(), "Input data: [ {} ], error: {:?}", input.trim_right_matches(|c: char| c.is_whitespace()), error); 
        },

Зинаида прилетает в параметре result, в ветви паттерн-матчинга он деструктурируется, и Зинаида оказывается в биндинге input. Это ownership, поэтому, после того, как мы даём временно попользоваться нашей Зинаидой функции печати, нам её необходимо прибить. Та-дам, это второе место в программе, где для нашего объекта вызывается free.

А теперь можно проскроллить экран наверх и посмотреть, сколько всего пережила Зинаида (а, соответственно, и аллоцированный регион памяти в куче), прежде чем оказаться напечатаной на экран в составе рапорта об ошибке. Имеет смысл обратить внимание, что объект дважды переходил границу потоков операционной системы. Мало того, у нас в наличии ситуация, когда строка аллоцируется в одном потоке, а освобождается в другом (в Си это считается страшным грехом). Вдобавок, у нас есть ситуация, когда один поток аллоцирует объект, которым пользуется другой поток, затем снова первый, и освобождает его. Учитывая то, что физически это тупо указатель на память (тоесть, вообще, самое низкоуровневое и производительное, что может быть), полагаю, очень редкие программисты Си/С++ смогут с первого раза написать эквивалентную программу, в которой не возникнет ситуаций "free after use" или "segmentation fault".

И да, при этом в нашей программе нет мусорщика, и все аллокации/деаллокации детерменированы.

Короче, в качестве итога. Концепция Ownership в Rust, на мой взгляд, настолько удачная (и, при этом, достаточно простая для понимания), что язык просто обязан забрать нишу C++. Ну, по крайней мере, я в это верю :)
satyr

\1083\1099\1090\1076\1099\1073\1088

Поучаствовал вчера в ежемесячном микро-развлекалове, выступив, внезапно, с хаскелем.

Код мой там, конечно, получился лолшто, но мне простительно. Но вернёмся лучше к срачу про юникод :) Как там это было: "В 2014 году говорить об юникоде!" ©.

Prelude> putStrLn "привет, я юникод"
привет, я юникод
Prelude> putStrLn $ show "привет, я юникод"
"\1087\1088\1080\1074\1077\1090, \1103 \1102\1085\1080\1082\1086\1076"
Prelude> "привет, я юникод"
"\1087\1088\1080\1074\1077\1090, \1103 \1102\1085\1080\1082\1086\1076"
satyr

Rust и иже с ним

Как это было у классиков: "Джва года ждал такой язык, суть токова...". На самом деле, я тут, вместе с остальным прогрессивным человечеством, активно обнюхиваю Rust, поддавшись мощной PR-компании. Есть даже какие-то мысли, но писать, как обычно, лень (или, как это щас модно называть: "У меня прокрастинация").

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

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

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

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

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

На этом уровне (владеющие указатели) руст перестаёт быть си-совместим, и становится самостоятельным языком. Утверждается, что скомпилировавшаяся программа на этом языке никогда не упадёт в segfault, а в многопоточной среде будут отсутствовать гонки. Тем не менее, всегда можно свободно перемещаться между уровнями с помощью unsafe-"мостика". Очевидно, что при "спуске" в "си" компилятор теряет возможность отслеживать корректность использования памяти, но, следует понимать, что для rust unsafe не является чем-то постыдным, навроде goto в с++ -- это просто механизм пометок тех мест, где пользователь самостоятельно, своими потными ладошками лезет в память. При этом гарантия (memory-) корректности остального кода сохраняется, и при случившемся сегфолте круг подозреваемых сужается до отмеченных тегом "unsafe" мест.

Собственно, идея и сама база Rust на этом заканчиваются. Всё остальное, что накручивается разработчиками сверху -- это какие-то парадигмы, инструменты и подходы, по-мелочи (или целиком) потасканные из других языков. Так как руст создаётся с нуля, и релиза пока что нет, авторы имеют право волочь всё, что покажется им интересным и многообещающим, но (!) только, если это не идёт вразрез с базой Rust.

Поэтому, например, в руст принесены HM вывод типов, алгебраические типы и тайпклассы из хаскеля (в русте они называются traits), разлапистый паттерн-матчинг, куча функциональщины, но нет (и не должно бы быть), например, исключений, и GC. Кое с чем там, в принципе, приходится мириться: например, два вида строк или запредельная сложность возврата замыканий из функций -- это всё тоже должно быть очевидно, почему так. С чем-то мириться получается не очень: например, из-за обработки ошибок через возврат Option/Result-ов (аналог Maybe/Either) разрастаются деревья match-ей. Но надо понимать, что это всё, на самом деле, шелуха, и она ещё, к тому же, может сто раз измениться к релизу.

Лично я для себя рассматриваю руст как потенциальную замену С++ в тех областях, где нужно много двигать байтики, дёргать системное апи, или как glue между несколькими сишными библиотеками (в отличие от многих других языков, тут не будет маршаллинга/сериализации). Опять же, большой плюс в том, что есть возможность делать .so-шки с сишным апи, которые потом можно линковать через ffi куда угодно, хоть к CL, хоть к эрлангу, хоть к чёрту лысому. Короче, вроде как многообещающе.
satyr

Рандомные мысли про эрланг

Решил тут пару месяцев назад попробовать сделать один рабочий проект на эрланге. С одной стороны, вроде как предметная область уж очень ровно ложилась под OTP (по моим представлениям), с другой -- вроде как вокруг сплошные success story, поэтому интересно было поближе посмотреть на сабж. Вроде как всё получилось, и получилось неплохо, поэтому имеет смысл сдампить все мои мысли по этому поводу в бложик, пока не забылось.

Про собственно язык. Осваивается за несколько часов, если есть какой-то минимальный бекграунд из лиспа/руби и окамла/хаскеля, и за несколько дней, если нету (надо осознать атомы, базовое фп, паттерн матчинг и неизменяемый стейт). Первый proof-of-concept проекта у меня был готов через, буквально, неделю (при том, что с эрлангом до этого момента я дела никогда не имел).

Про "let it crash". В целом, идея "да пропади оно всё пропадом" в паре с вотчдогом каким-то особым откровением не является: вещь достаточно интуитивная, я много раз такое видел, и сам так делал. Например, простейший бинарь с perror + exit или неотлавливаемыми исключениями уже можно считать таким примером: на "хуяк-хуяк, и в продакшне" он запускается под monit-ом, или просто тупо внутри цикла: "while true; do ...; sleep 3; done". Криво, но (в лучших традициях эрланга) такие демоны спокойно переживают разнообразные мигания сети, рестарты баз и временные отгнивания используемых сервисов.

"Эрланг для бедных" (с zeromq, "let it crash", и псевдо-супервайзером) я, также, достаточно часто использую и многопоточных приложениях на CL, если нужна логика сложнее банального workers pool'а. Идея там какая-то такая: входная точка потока представляет собой бесконечный цикл, обёрнутый вокруг handler-case, в основной секции которого zmq_socket+zmq_connect и рабочее тело потока, а в секции с перехватом исключения ругань в лог и задержка. В итоге любая ошибка в рабочем теле заставляет ребутнуться весь поток, с освобождением и перезахватом всех необходимых ресурсов и обнулением стейта. Да, ну и общение с потоком исключительно сообщениями, конечно, иначе весь смысл теряется.

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

Итого, стиль программирования на эрланге получается достаточно самобытен: потоки дешёвые, изолированные от всего, общение только через message passing, никакие ошибки обрабатывать не надо. Для программиста это означает реализацию только happy day scenario, что в паре с паттерн-матчингом превращает программу в какое-то подобие простыни ассертов:

flush_to_temp_file( TempDirectory, Entries ) ->
    ok = filelib:ensure_dir( TempDirectory ),
    { ok, Fd } = file:open( TempDirectory ++ "/flush.tmp", [ append, binary, delayed_write ] ),
    ok = lists:foreach( fun( Entry ) ->
                                ok = file:write( Fd, Entry ),
                                ok = io:nl( Fd )
                        end, 
                        Entries ),
    ok = file:close( Fd ).

Потоки можно свободно спавнить по любому поводу: через них в эрланге можно делать всё, что в обычных языках делается через мультиплексирование, КА, колбеки, call/cc и тп. Результатом выполнения потока может быть только успех: в любой исключительной ситуации потомок похоронит своего родителя (если он порождён через spawn_link, конечно), а родитель будет отрестарчен надзирателем.

Собственно, сама модель "let it crash", дерева супервайзеров и пачки других шаблонных схем, является частью Open Telecom Platform, в рамках которой всячески рекомендуется оставаться, разрабатывая что-то на эрланге. Причём, выход за эти рамки крайне просто отследить: типа, вроде программируешь, всё как по маслу -- красиво, стройно, и тут внезапно хуяк, какие-то костыли, что-то не стыкуется и резко нарастает внутренее раздражение. Самое время переосмыслить логику -- где-то мы вылезли за рамки OTP :) В этом плане эрланг сильно выигрывает у того же КЛ: там ничего не подозреваешь до самого конца -- всё красиво и стройно вплоть до последнего момента, когда пора уже просто выкидывать весь код в помойку, и начинать заново. С другой стороны, очевидно, что не все проекты на свете ровно ложатся в парадигму OTP, и здесь моё мнение таково, что такие проекты просто не стоит даже начинать делать на эрланге, всё равно ничего хорошего не получится, одни страдания.

Теперь про впечатления от собственно разработки.

Из хорошего: очень похоже на CL :) Тот же репл по C-z, та же мгновенная компиляция по C-c C-k, что-то накодил -- сразу проверил, что "накожено" верно. То же горячее обновление кода, remote shell, те же микро-исправления "по-живому" в продакшне, красота.

Из плохого: как ни крути, это всё даже близко не лежало рядом со slime.
Файлы в репл загружать можно только целиком, в slime можно каждую форму по-отдельности. Функции нужно явно экспортить, чтобы проверить в репле. Интеграция с IDE минимальна, все эти "i()", "p()", "dbg", и тд нужно вводить непосредсвенно в репл. Средства интроспекции кода околонулевые, дебаггер только простейший, ничего подобного волшебному "break" нет. Это всё, на самом деле, достаточно странно для виртуальной машины, исполняющей байткод, особенно на фоне того, что sbcl-то транслирует в натив.

Вот, например, есть у нас проект на сервере, который как-то странно себя ведёт. Как я обычно делаю с CL? slime-connect, "(sb-thread:list-all-threads)", выбираю интересующий меня тред, slime-inspect, далее "e" и "(sb-thread:interrupt-thread * #'break)". Всё, я могу спокойно поисследовать любой стейт на любом уровне вложенности, понатыкать брекпойнтов куда мне надо с любыми условиями, да даже выполнить любой код в контексте этого треда. Далее "continue", и всё побежало дальше, как ни в чём ни бывало.

В эрланге я в этом плане существенно более ограничен. Да, я могу войти в машину через remsh и что-то там пообновлять через make:all([load]), например. Могу повтыкать на etop. Могу, с помощью какой-то матери, найти pid интересующего меня процесса и посмотреть на него через erlang:process_info или sys:get_status. Могу что-то потрейсить с помощью dbg. Но я не могу динамически влиять на программу, например, сформировав ей какой-то тестовый входной параметр и понаблюдав, как оно поведёт себя на боевых данных. Только если как-то специально пересобрав и перезагрузив исходники. И, самое главное -- это всё происходит в отдельном шелле, без привязки к IDE.

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

hwpmc howto

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

Собственно, примерно также, как и в луниксе.

Вариант 1: купить VTune (Intel его таки распространяет и для фряхи, правда, пока, unofficial).

Вариант 2: hwpmc(4) (это вместо oprofile).

Собственно, для второго варианта идея такова:

% sudo kldload hwpmc
% sudo pmcstat -S instructions -O sample.out bin/myprog
% pmcstat -R sample.out -F myprog.cg.out
% kcachegrind myprog.cg.out &

Вместо callgrind-совместимого дампа можно сделать, например, gprof-совместимый ("-g" вместо "-F"), это кому что нравится.

Вроде всё работает, всё показывает -- это хорошо.
satyr

И еще раз о задачке про ip-диапазоны.

Собственно, описание задачи и варианты её решения можно почитать здесь у nponeccop. Один из вариантов там предложен на CL лавсанчиком. Собственно, он меня немножечко возмутил, поэтому пришлось писать этот пост :)

Суть токова: это вполне себе рабочий код, но так на common lisp писать не надо :) Потому что так надо писать на си. На сях этот же код будет вдвое короче (хотя бы за счет отсутствия скобок и более лаконичного синтаксиса) и вдвое быстрее.

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

Условия нам благоприятсвуют: диапазоны грузятся один раз, а дальше только лукап. Поэтому мы попробуем решить эту задачу классическим лисповым способом: «расставить скобки вокруг спецификации и заставить её запуститься». Вот прямо так, буквально. Итак, имеем файл ranges.list такого вида:

104.72.221.173,220.57.219.35
16.65.26.150,133.42.154.151
80.241.37.220,93.109.90.13
35.165.212.97,105.166.11.16
122.143.149.115,246.17.13.31
20.44.170.80,144.105.12.169
122.132.114.84,184.165.60.95
102.111.151.45,120.152.236.26
53.252.70.24,171.51.24.110
101.103.12.180,224.55.178.136

Отлично, давайте расставим вокруг скобки, чтобы получить ranges.list.lisp:

(in-package :ip-ranges)
(gen-test-proc
  "104.72.221.173,220.57.219.35"
  "16.65.26.150,133.42.154.151"
  "80.241.37.220,93.109.90.13"
  "35.165.212.97,105.166.11.16"
  "122.143.149.115,246.17.13.31"
  "20.44.170.80,144.105.12.169"
  "122.132.114.84,184.165.60.95"
  "102.111.151.45,120.152.236.26"
  "53.252.70.24,171.51.24.110"
  "101.103.12.180,224.55.178.136"
)

Только, конечно же, не руками, а вот так:

(defun preprocess-ranges-file (filename)
  (let ((lisp-file (format nil "~a.lisp" filename)))
    (with-open-file (f-in filename)
      (with-open-file (f-out lisp-file
                             :direction :output
                             :if-exists :supersede
                             :if-does-not-exist :create
                             :external-format :ascii)
        (format f-out "(in-package :ip-ranges)~%(gen-test-proc~%")
        (iter (for range in-stream f-in using #'read-line)
              (format f-out "  \"~a\"~%" range))
        (format f-out ")~%~%")))
    lisp-file))

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

(defpackage #:ip-ranges
  (:use :cl :iterate :metatilities)
  (:shadowing-import-from :metatilities #:minimize #:finish)
  (:export #:check))

(in-package :ip-ranges)

(defun extract-values (string)
  (unless (zerop (length string))
    (multiple-value-bind (value rest-index)
        (parse-integer string :junk-allowed t)
      (if value
          (cons value (extract-values (subseq string rest-index)))
          (extract-values (subseq string 1))))))

Работать это должно так:

IP-RANGES> (extract-values "104.72.221.173,220.57.219.35")
(104 72 221 173 220 57 219 35)

Теперь надо немного пораскинуть мозгами. Вот у нас есть диапазон, заданный ip-адресами, каждый из которых представлен четырьмя октетами -- в нашем случае '(104 72 221 173) и '(220 57 219 35). Допустим, нам выдали адрес в таком же формате: ip = (list ip-0 ip-1 ip-2 ip-3); какой код должен быть в программе, которым можно проверить принадлежность этого адреса заданному диапазону? Собственно, тут даже не надо ничего делать руками (например, склеивать октеты в 32-х битный адрес и т.п.), просто тупо сгенерируем сравнение в лесенкой столбик :)

(defun ip-range (range-string)
  (let ((values (extract-values range-string))
        (vars '(ip-0 ip-1 ip-2 ip-3)))
    (assert (= (length values) 8))
    (labels ((stairs (cmp values vars)
               (if (null values)
                   t
                   `(or (,cmp ,(car vars) ,(car values))
                        (and (= ,(car vars) ,(car values))
                             ,(stairs cmp (cdr values) (cdr vars)))))))
      `(and ,(stairs '> (subseq values 0 4) vars)
            ,(stairs '< (subseq values 4 8) vars)))))

IP-RANGES> (ip-range "104.72.221.173,220.57.219.35")
(AND
 (OR (> IP-0 104)
     (AND (= IP-0 104)
          (OR (> IP-1 72)
              (AND (= IP-1 72)
                   (OR (> IP-2 221)
                       (AND (= IP-2 221)
                            (OR (> IP-3 173) (AND (= IP-3 173) T))))))))
 (OR (< IP-0 220)
     (AND (= IP-0 220)
          (OR (< IP-1 57)
              (AND (= IP-1 57)
                   (OR (< IP-2 219)
                       (AND (= IP-2 219)
                            (OR (< IP-3 35) (AND (= IP-3 35) T)))))))))

Ну а теперь у нас есть все для того, чтобы "скомпилировать спецификацию":

(defmacro gen-test-proc (&rest ranges)
  `(defun ip-check (ip-0 ip-1 ip-2 ip-3)
     (or ,@(mapcar #'ip-range ranges))))

(defun check (ip-string)
  (apply #'ip-check (extract-values ip-string)))

Вуаля:

IP-RANGES> (load (compile-file (preprocess-ranges-file #p"ranges.list")))
; compiling file "/home/swizard/devel/lisp/ip-ranges/ranges.list.lisp" (written 03 NOV 2011 11:16:02 PM):
; compiling (IN-PACKAGE :IP-RANGES)
; compiling (GEN-TEST-PROC "104.72.221.173,220.57.219.35" ...)

; /home/swizard/devel/lisp/ip-ranges/ranges.list.fasl written
; compilation finished in 0:00:00.045
T
IP-RANGES> (check "192.168.0.1")
T
IP-RANGES> (check "10.0.0.0")
NIL


Итак, еще раз, что мы сейчас сделали:
  • Расставили скобки вокруг списка ip-диапазонов.
  • Сгенерировали по описанию функцию ip-check, решающую задачу.
  • ...
  • Profit!

Красотища? Да, но пока что не особо.

  • Несмотря на константные проверки и восьмибитную сегментацию адреса, у нас получилась последовательная проверка.
  • Несмотря на автоматическую генерацию условия по диапазону, это условие генерируется какое-то кривоватое и сильно избыточное.
  • Несмотря на то, что какие-то диапазоны проверять нет смысла, так как они "поглощаются" более широкими, все равно проверяются все.
  • По условиям задачи диапазонов могут быть сотни: поэтому код надо сегментировать по функциям, чтобы не нагнуть компилятор при стратегии (optimize (speed 3))


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

О мусорщиках

Вот тут вот есть статья про то, как можно обойти gc-шный heap, чтобы победить паузы, возникающие при сборке мусора.

Надо признать, что затронутые там проблемы можно спроецировать и на SBCL. А, вдовесок, мы имеем еще пару непонятных моментов:
  1. Собственно наш мусорщик менее технологичный, нежели в JVM. Как минимум, он не параллельный и, вообще, при сборке отважно накладывает глобал-лок на весь процесс.
  2. При всех несомненных плюсах GC, мне непонятно, почему в CL нет богатых возможностей по ручному управлению памятью.

Что касается первого пунка, то я уже предлагал подумать в сторону выделенного GC, который можно будет переключать, например, глобальной переменной *current-gc*. Ну или хотя бы локальный thread-specific GC. Да, объекты, выделенные в разных кучах, не смогут ссылаться друг на друга, но в большинстве случаев это и не надо: каждая нить занята своей отдельной работой, но злобный мусорщик останавливает сразу всех, чтобы подчистить только за одной.

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

На втором пункте надо бы остановиться отдельно.

Действительно, в CL имеются богатые возможности для метапрограммирования, и нет никаких проблем безопасно и надежно прятать все ручное управление памятью поглубже. Начиная от RAII в стиле with-open-file, заканчивая декларативными eDSL, в которых можно аккуратно разметить необходимую область памяти и политику ее освобождения. Хотя, возможно, достаточно просто расширить интерфейс garbage collector'а, позволив выводить из-под его влияния выбранные объекты, которые он затем не имеет права трогать. А продолжительностью их жизни пусть управляет программист: ведь дофига же случаев, когда объекты не нужны уже сразу вне своего блока видимости.

Вообще, приглашаю подискутировать на эту тему :)
satyr

Толочь воду в ступе

Пост навеян свежим ПФП. Статья про circumflex, вот этим вот:

// Выбрать все города Швейцарии, вернуть Seq[City]:
SELECT (ci.*) FROM (ci JOIN co) WHERE (co.code LIKE ”ch”)
ORDER_BY (ci.name ASC) list

Стоило ли огород городить, если на выходе всё равно получается нечто, что
очень похоже на SQL? Выражаясь языком Lurkmore, «вы так говорите, как буд-
то SQL — это что-то плохое». Получившийся DSL является, тем не менее, кор-
ректным Scala-кодом, и может быть использован внутри Scala-программ со все-
ми возможностями языка, правильной типизацией, ...

Почему-то напомнило отважные победы thesz над типизацией проклятого SQL, да и вообще приключения любого уважающего себя аколита церкви типизации по причесыванию всякого динамического говна под строгие требования компилятора.

Давайте я организую мини-набросец :) Ведь действительно, на кой черт?

Нет, ну а как же, казалось бы -- а вот случиться мне поменять декларацию класса в моей ORM, а тут-то меня компилятор и хлопнет по рукам: мол, вот тут и тут у тебя запросы херню теперь возвращать будут, давай-ка, правь. А вот писали бы чистый SQL, схлопотали бы ужасную по своей чудовищности ошибку в рантайме, а то и вовсе segfault!

Ок, хорошо, а вот, действительно -- поменял я декларацию класса, и компилятор мне услужливо выдал ОДНУ ТЫСЯЧУ мест в моей стамегабайтной опердени, где у меня разъехались запросы с реальностью. Дальше-то что? А дальше вперед -- grep-find, replace-regexp, клавиатурные макросы, али просто сиди и правь все руками как потомственный энтерпрайз программист. Где обещанное счастье? Но это ладно, допустим, мне за это платят зарплату. А вот если у меня отдельно от кода поменяется схема БД, спасет ли меня компилятор? Конечно нет, откуда ему про это знать. Я получу свою заслуженную ошибку в рантайме.

Итак, как делать правильно.

Правильно -- это динамическая типизация и хорошее метапрограммирование (читай: lisp).

По объявлению класса мы:
  • генерируем все необходимые нам в данный момент методы с соответствующими sql-запросами
  • на этапе макроэкспанда верифицируем декларацию класса и схему таблиц в бд

Вот с этого момента начитается обещанное счастье.

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

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

(defpackage :my-orm
  (:use :cl :iterate :postmodern :metatilities)
  (:shadowing-import-from :metatilities minimize finish))

(in-package :my-orm)

(defvar *db-connection* (connect-toplevel "swizard" "swizard" "" "localhost"))

И начнем с конца:

(defclass-db city ()
  ((name :accessor name
         :col-type string)))

Вот такой вот незамысловатый объект :) Проверяем, на всякий случай, консоль psql:

swizard=# \d 
No relations found.

Чистенько! Поехали колдовать: компилируем класс C-c C-c:

; compiling (DEFCLASS-DB CITY ...)

; file: /var/tmp/tmp.zPicFJ
; in: DEFCLASS-DB CITY
;     (MY-ORM::DEFCLASS-DB MY-ORM::CITY NIL
;                          ((MY-ORM::NAME :ACCESSOR MY-ORM::NAME :COL-TYPE STRING)))
; 
; caught WARNING:
;   Postgres warning: table "city" does not exist, skipping
; 
; caught WARNING:
;   Postgres warning: sequence "city_seq" does not exist, skipping
; 
; compilation unit finished
;   caught 2 WARNING conditions

Ага!! Постгресс на что-то ругнулся, что же там произошло? Смотрим psql:

swizard=# \d
           List of relations
 Schema |   Name   |   Type   |  Owner  
--------+----------+----------+---------
 public | city     | table    | swizard
 public | city_seq | sequence | swizard
(2 rows)

swizard=# \dS city
                        Table "public.city"
 Column |  Type   |                   Modifiers                    
--------+---------+------------------------------------------------
 id     | integer | not null default nextval('city_seq'::regclass)
 name   | text    | not null

Опа, нифига себе. А мы всего-то ведь скомпилировали класс :) Проверяем магию дальше: меняем декларацию класса:

(defclass-db city ()
  ((name :accessor name
         :col-type string)
   (zip :accessor zip
        :col-type integer)))

Перекомпилируем и смотрим в базу:

swizard=# \dS city
                        Table "public.city"
 Column |  Type   |                   Modifiers                    
--------+---------+------------------------------------------------
 id     | integer | not null default nextval('city_seq'::regclass)
 name   | text    | not null
 zip    | integer | not null

Оно поменялось!! Ну и, на закуску, нам была сгенерирована парочка методов:

MY-ORM> (create-city "Moscow" 111222)
#<CITY {100548DA61}>
MY-ORM> (create-city "Saratov" 222111)
#<CITY {10054A18B1}>
MY-ORM> (mapcar #'describe (list-all-city))
#<CITY {10054BC851}>
  [standard-object]

Slots with :INSTANCE allocation:
  ID    = 1
  NAME  = "Moscow"
  ZIP   = 111222
#<CITY {10054BCBD1}>
  [standard-object]

Slots with :INSTANCE allocation:
  ID    = 2
  NAME  = "Saratov"
  ZIP   = 222111
(NIL NIL)

Ок, а где наш хваленый персистенс? А вот он:

swizard=# select * from city;
 id |  name   |  zip   
----+---------+--------
  1 | Moscow  | 111222
  2 | Saratov | 222111
(2 rows)

Ну красота же :) Ну что ж, самое время приводить код нашего волшебного defclass-db, благо это всего четыре десятка строчек:

(defmacro defclass-db (name () (&rest fields))
  (let ((field-names (sort (mapcar (compose #'string-downcase #'string #'first)
                                   (cons '(id) fields))
                           #'string<))
        (seq-name (form-symbol name '-seq)))
    (unless (and (table-exists-p name)
                 (equal field-names (sort (mapcar #'first (table-description name)) #'string<)))
      (execute (sql-compile `(:drop-table :if-exists ,name)))
      (execute (sql-compile `(:drop-sequence :if-exists ,seq-name)))
      (execute (sql-compile `(:create-sequence ,seq-name)))
      (execute
       (sql-compile
        `(:create-table ,name
                        ((id :type integer :default (:nextval ',seq-name) :primary-key)
                         ,@(iter (for field-desc in fields)
                                 (destructuring-bind (field-name &key col-type &allow-other-keys)
                                     field-desc
                                   (collect `(,field-name :type ,col-type)))))))))
    `(progn
       (defclass ,name ()
         ((id :reader oid)
          ,@(iter (for (field-name . field-args) in fields)
                  (collect `(,field-name ,@(iter (generating kv in field-args)
                                                 (for (key . value) = (cons (next kv) (next kv)))
                                                 (unless (eq key :col-type)
                                                   (collect key)
                                                   (collect value))))))))
       (defun ,(form-symbol 'create- name) (,@(mapcar #'first fields))
         (let ((obj (make-instance ',name)))
           ,@(iter (for (field-name . args) in fields)
                   (collect `(setf (slot-value obj ',field-name) ,field-name)))
           (execute (sql (:insert-into ',name :set ,@(iter (for (field-name . args) in fields)
                                                           (collect `',field-name)
                                                           (collect field-name)))))
           obj))
       (defun ,(form-symbol 'list-all- name) ()
         (iter (for (id ,@(mapcar #'first fields)) in
                    (query (:select 'id ,@(iter (for (field-name . args) in fields)
                                                (collect `',field-name)) :from ',name)))
               (collect (let ((obj (make-instance ',name)))
                          (setf (slot-value obj 'id) id)
                          ,@(iter (for (field-name . args) in fields)
                                  (collect `(setf (slot-value obj ',field-name) ,field-name)))
                          obj)))))))

Никаких монструозных фреймворков, только чистые динамические запросы и EDSL на сорок строк :) Вы еще типизируете SQL? Тогда мы идем к вам!