Pull to refresh
38
Karma
0
Rating
Роман Кашицын @roman_kashitsyn

Пользователь

BPF для самых маленьких, часть нулевая: classic BPF

Network technologies *C *Development for Linux *
Sandbox

Berkeley Packet Filters (BPF) — это технология ядра Linux, которая не сходит с первых полос англоязычных технических изданий вот уже несколько лет подряд. Конференции забиты докладами про использование и разработку BPF. David Miller, мантейнер сетевой подсистемы Linux, называет свой доклад на Linux Plumbers 2018 «This talk is not about XDP» (XDP – это один из вариантов использования BPF). Brendan Gregg читает доклады под названием Linux BPF Superpowers. Toke Høiland-Jørgensen смеется, что ядро это теперь microkernel. Thomas Graf рекламирует идею о том, что BPF — это javascript для ядра.


На Хабре до сих пор нет систематического описания BPF, и поэтому я в серии статей постараюсь рассказать про историю технологии, описать архитектуру и средства разработки, очертить области применения и практики использования BPF. В этой, нулевой, статье цикла рассказывается история и архитектура классического BPF, а также раскрываются тайны принципов работы tcpdump, seccomp, strace, и многое другое.


Разработка BPF контролируется сетевым сообществом Linux, основные существующие применения BPF связаны с сетями и поэтому, с позволения @eucariot, я назвал серию "BPF для самых маленьких", в честь великой серии "Сети для самых маленьких".

Читать дальше →
Total votes 62: ↑62 and ↓0 +62
Views 34K
Comments 5

Ты только посмотри! 20 фильмов о науке и ученых

Человек наук corporate blog Mathematics *Popular science Science fiction Brain
Команда конференции Mieloconf подготовила подборку классных фильмов о науке и ученых для долгих новогодних каникул.

Про свои любимые фильмы рассказали: AI-евангелист ABBYY, автор подкаста «Проветримся» Иван Ямщиков, физик-ядерщик Дмитрий Горчаков, руководитель инфраструктурной команды в «Контуре» Алексей Кирпичников и программист Павел Аргентов.


Читать дальше →
Total votes 42: ↑39 and ↓3 +36
Views 53K
Comments 42

Советские мечты о будущем

Madrobots corporate blog Science fiction


Помните очаровательного котика, которые чихал в заставке советского мультфильма? Мы помним, и нашли его — вместе с ворохом другой рисованной фантастики. В детстве она пугала и обескураживала, поскольку поднимала серьезные, взрослые темы. Настала пора пересмотреть старые мультфильмы, чтобы узнать, о каком будущем мечтали в той стране.
Total votes 138: ↑136 and ↓2 +134
Views 89K
Comments 144

Sir Markdown. Лекция Яндекса

Яндекс corporate blog Perfect code *GitHub *Language localisation *Technical Writing *
При разработке документации мы руководствуемся не только стандартами, но и удобством её использования. Стандарты определяют состав и форму документации, а формат строится исходя из удобства. Разработчик Сергей Бочаров рассказывает о пути Markdown-документа и о проблемах, которые приходится решать в обмен на простоту использования этого формата.


У меня иногда складывается впечатление, что не он служит для нас, а мы служим для этого формата. Поэтому — сэр Markdown.

Total votes 70: ↑67 and ↓3 +64
Views 24K
Comments 20

Чтение на выходных: 17 независимых блогов по математике, алгоритмам и языкам программирования

CloudMTS corporate blog Programming *Algorithms *Mathematics *Professional literature *
Сегодня мы подготовили очередную [наш IaaS-дайджест и материалы по структурированию кода] подборку полезных источников. На этот раз мы решили изучить тематическую ветку на Hacker News и рассказали о блогах, которые могут хорошо дополнить чтение «Хабра».

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

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

Читать дальше →
Total votes 25: ↑21 and ↓4 +17
Views 57K
Comments 1

20 лет Яндексу. Лекция Ильи Сегаловича — человека, который придумал это слово

Яндекс corporate blog Search engines *Yandex API *Industrial Programming *
Ровно 20 лет назад — 23 сентября 1997 года — в интернете появился Яндекс. Аркадий Волож, Илья Сегалович, Елена Колмановская представили на выставке Softool поисковую систему Yandex.ru. Открывали её, перерезав ленточку перед компьютером — потому что не понимали, как надо открывать сайты в интернете.

Тогда он состоял из 5 тысяч сайтов, на которых было размещено около 4 гигабайт текста. Люди подходили к демонстрационному компьютеру, пробовали задавать запросы и получали ответы. На тот момент Яндекс учитывал морфологию русского языка, расстояние между словами и умел ранжировать документы.


Это одна из последних лекций, которую прочитал iseg, сооснователь и первый технический директор Яндекса Илья Сегалович. Она посвящена истории Яндекса с того момента, как Илья и Аркадий Волож сели в школе за одну парту. Качество записи лекции не настолько хорошее, насколько бы нам хотелось, но содержание — бесценно.

Total votes 91: ↑87 and ↓4 +83
Views 24K
Comments 16

Доступно о криптографии на эллиптических кривых

Cryptography *Algorithms *Mathematics *
Translation
image


Тем, кто знаком с криптографией с открытым ключом, наверно известны аббревиатуры ECC, ECDH и ECDSA. Первая — это сокращение от Elliptic Curve Cryptography (криптография на эллиптических кривых), остальные — это названия основанных на ней алгоритмов.

Сегодня криптосистемы на эллиптических кривых используются в TLS, PGP и SSH, важнейших технологиях, на которых базируются современный веб и мир ИТ. Я уже не говорю о Bitcoin и других криптовалютах.

До того, как ECC стала популярной, почти все алгоритмы с открытым ключом основывались на RSA, DSA и DH, альтернативных криптосистемах на основе модулярной арифметики. RSA и компания по-прежнему популярны, и часто используются вместе с ECC. Однако несмотря на то, что магия, лежащая в фундаменте RSA и подобных ей алгоритмов легко объяснима и понятна многим, а грубые реализации пишутся довольно просто, основы ECC всё ещё являются для большинства людей загадкой.

В этой серии статей я познакомлю вас с основами мира криптографии на эллиптических кривых. Моя цель — не создание полного и подробного руководства по ECC (в Интернете полно информации по этой теме), а простой обзор ECC и объяснение того, почему её считают безопасной. Я не буду тратить время на долгие математические доказательства или скучные подробности реализации. Также я представлю полезные примеры с визуальными интерактивными инструментами и скриптами.
Читать дальше →
Total votes 127: ↑125 and ↓2 +123
Views 183K
Comments 65

Three Futamura Projections и не только

Abnormal programming *
Привет, хабрачеловек. Сегодня я расскажу тебе про некоторые фундаментальные вещи в computer science: частичные вычисления, три проекции Футамуры и суперкомпиляцию.
 
 

1. Сразу к коду


-- функция, которая возводит x в степень y (неотрицательную)
power x y =
    case y of
        0 → 1
        1 → x
        _ → x * (power x (y - 1))


Читать дальше →
Total votes 126: ↑117 and ↓9 +108
Views 8.8K
Comments 76

Коды Рида-Соломона. Часть 1 — теория простым языком

YADRO corporate blog Algorithms *
Добрый день! Меня зовут Максим, в YADRO, кроме всего прочего, я занимаюсь разработкой подсистемы, отвечающей за надежное хранение данных. Готовлю небольшой цикл статей про коды Рида-Соломона — теоретическую основу, практическую реализацию, применяемые на практике программные и аппаратные оптимизации. На Хабре и в остальной сети есть хорошие статьи по вопросам этой области — но по ним сложно разобраться, если ты новичок в теме. В этой статье я попытаюсь дать понятное введение в коды Рида-Соломона, а в следующих выпусках напишу, как все это запрограммировать.



Читать дальше →
Total votes 50: ↑50 and ↓0 +50
Views 47K
Comments 31

Сколько технологий нужно Яндексу, чтобы поиск находил свежие документы почти моментально

Яндекс corporate blog Search engines *Machine learning *

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




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


1. Почему свежесть?


Интерес к любому событию в течение нескольких дней угасает практически до нуля, если, конечно, это событие не получает какого-либо дальнейшего развития. Мы проводили исследование, из которого и родилось это утверждение: оказывается, в среднем 73% пользователей интересуется событием непосредственно в день, когда оно произошло, и только 3% читателей приходит на ресурсы спустя трое суток и более после публикации. С момента проведения этого исследования прошло уже много лет, но в целом ситуация не изменилась. И даже статьи на habrahabr.ru получают наибольшее количество поисковых переходов в первые несколько суток своего существования.

Читать дальше →
Total votes 72: ↑66 and ↓6 +60
Views 23K
Comments 20

M* — алгоритм поиска кратчайшего пути, через весь мир, на смартфоне

2ГИС corporate blog System Analysis and Design *Algorithms *C *Geoinformation services *


При поиске кратчайшего пути на графах большого размера плохо работает традиционная оценка стоимости т.к. данные заведомо не помещаются в памяти и общая стоимость больше зависит от числа обращений к диску нежели от числа просмотренных рёбер. А число дисковых операций — весьма субъективный фактор, зависимый от сложно формализуемой пригодности графа к хранению на диске в форме удобной для конкретного алгоритма. Кроме того, очень важным становится компактность — количество информации в расчете на ребро и вершину.

Под катом представлена обобщенная эвристика к алгоритму A*, полезная именно в свете практической пригодности на больших графах при ограниченных ресурсах, например, на мобилке.
Читать дальше →
Total votes 110: ↑109 and ↓1 +108
Views 43K
Comments 48

Haskell: об одном методе реализации функций с переменным числом параметров

Entertaining tasks Haskell *Functional Programming *
Tutorial

– А видела ты Черепаху «Как бы»?
– Нет, – сказала Алиса. – Я даже не знаю, кто это такой.
– Как же, – сказала Королева. – Это то, из чего делают «Как бы черепаший суп».

                  Льюис Кэрролл, 
                           «Алиса в Стране чудес»

— Судя по твоим речам, ты хорошо знаешь Фангорн? — спросил в ответ Арагорн.
— Какое там! — отозвался старик. — На это ста жизней не хватит. Но я сюда иной раз захаживаю.

                 Джон Р. Р. Толкиен, 
                          «Властелин Колец» — к слову о моём знании Haskell ;)


Homines dum docent, discunt. (Объясни другим — сам поймёшь.)
                 народная латинская поговорка


Все знают, что любая функция Haskell по своей сути является функцией одного параметра. Функции «как бы» нескольких параметров просто принимая первый аргумент, возвращают другую функцию, принимающую второй аргумент (исходной функции) и обратно возвращающую функцию и т.д. до финальной функции, которая уже возвращает значение не функционального типа (каррирование).

Казалось бы о каком переменном числе параметров может идти речь при таком раскладе? Однако поразмыслив, посмотрев исходники printf или просто почитав wiki.haskell становится очевидным, что как раз ФП даёт ключ к достаточно красивому, хотя и несколько «казуистическому» решению этой задачи.

В настоящей публикации я рассмотрю один из способов реализации такого механизма на простых примерах, а также предложу некоторое обобщённое решение на базе Template Haskell, для превращения семейства обычных функций с последним параметром типа список в функцию с «как бы с переменным числом параметром» (далее по тексту просто «с переменным числом параметром»).
Читать дальше →
Total votes 24: ↑24 and ↓0 +24
Views 6K
Comments 4

От моноидов к алгебрам де Моргана. Строим абстракции на Haskell

Haskell *Mathematics *Functional Programming *
Sandbox

Что общего у нормального распределения, конечных автоматов, хеш-таблиц, произвольных предикатов, строк, выпуклых оболочек, афинных преобразований, файлов конфигураций и стилей CSS? А что объединяет целые числа, типы в Haskell, произвольные графы, альтернативные функторы, матрицы, регулярные выражения и статистические выборки? Наконец, можно ли как-то связать между собой булеву алгебру, электрические цепи, прямоугольные таблицы, теплоизоляцию труб или зданий и изображения на плоскости? На эти вопросы есть два важных ответа: 1) со всеми этими объектами работают программисты, 2) эти объекты имеют сходную алгебраическую структуру: первые являются моноидами, вторые — полукольцами, третьи — алгебрами де Моргана.

Читать дальше →
Total votes 35: ↑34 and ↓1 +33
Views 12K
Comments 12

Синтез изображений с помощью глубоких нейросетей. Лекция в Яндексе

Яндекс corporate blog Entertaining tasks Algorithms *Image processing *
Пусть в блоге Яндекса на Хабрахабре эта неделя пройдет под знаком нейронных сетей. Как мы видим, нейросети сейчас начинают использоваться в очень многих областях, включая поиск. Кажется, что «модно» искать для них новые сферы применения, а в тех сферах, где они работают уже какое-то время, процессы не такие интересные.

Однако события в мире синтеза визуальных образов доказывают обратное. Да, компании еще несколько лет назад начали использовать нейросети для операций с изображениями — но это был не конец пути, а его начало. Недавно руководитель группы компьютерного зрения «Сколтеха» и большой друг Яндекса и ШАДа Виктор Лемпицкий рассказал о нескольких новых способах применения сетей к изображениям. Поскольку сегодняшняя лекция — про картинки, то она очень наглядная.


Под катом — расшифровка и большинство слайдов.

Total votes 87: ↑84 and ↓3 +81
Views 45K
Comments 10

Тензорные разложения и их применения. Лекция в Яндексе

Яндекс corporate blog Abnormal programming *Algorithms *Mathematics *
Предыдущая лекция с Data Fest была посвящена алгоритмам, необходимым для построения нового вида поиска. Сегодняшний доклад тоже в некотором смысле про разные алгоритмы, а точнее про математику, лежащую в основе множества из них. О матричных разложениях зрителям рассказал доктор наук и руководитель группы вычислительных методов «Сколтеха» Иван Оселедец.


Под катом — расшифровка и большинство слайдов.

Total votes 49: ↑48 and ↓1 +47
Views 30K
Comments 6

Как посчитать перестановки. Лекция в Яндексе

Яндекс corporate blog Abnormal programming *Algorithms *Mathematics *
Некоторое время назад в московский офис Яндекса приезжал Игорь Пак — ученый с множеством научных работ, выпускник мехмата МГУ и аспирантуры Гарварда. Сейчас Игорь работает в Калифорнийском университете. Его лекция в Яндексе была посвящена различным классам последовательностей и перестановкам. В том числе прямо по ходу лекции он представил выкладки, опровергающие гипотезу Нунана и Зайлбергера — одну из ключевых в области перестановок.



Под катом — подробная текстовая расшифровка и большинство слайдов.
Total votes 57: ↑57 and ↓0 +57
Views 25K
Comments 12

Анатомия KD-Деревьев

C++ *Algorithms *
Sandbox
image

Эта статья полностью посвящена KD-Деревьям: я описываю тонкости построения KD-Деревьев, тонкости реализации функций поиска 'ближнего' в KD-Дереве, а также возможные 'подводные камни', которые возникают в процессе решения тех или иных подзадач алгоритма. Дабы не запутывать читателя терминологией(плоскость, гипер-плоскость и т.п), да и вообще для удобства, полагается что основное действо разворачивается в трехмерном пространстве. Однако же, где нужно я отмечаю, что мы работаем в пространстве другой размерности. По моему мнению статья будет полезна как программистам, так и всем тем, кто заинтересован в изучении алгоритмов: кто-то найдет для себя что-то новое, а кто-то просто повторит материал и возможно, в комментариях дополнит статью. В любом случае, прошу всех под кат.
Читать дальше →
Total votes 32: ↑32 and ↓0 +32
Views 38K
Comments 11

Аналитическое вычисление производных на шаблонах C++

Abnormal programming *C++ *
Тут на днях писали про аналитическое нахождение производных, что напомнило мне об одной моей маленькой библиотечке на C++, которая делает почти то же, но во время компиляции.


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

using Formula_t = decltype (k * (_1 - r0) / (_1 + r0) * (g0 / (alpha0 - logr0 / Num<300>) - _1));    // сама формула
const auto residual = Formula_t::Eval (datapoint) - knownValue;    // регрессионный остаток

// производные по параметрам:
const auto dg0 = VarDerivative_t<Formula_t, decltype (g0)>::Eval (datapoint);
const auto dalpha0 = VarDerivative_t<Formula_t, decltype (alpha0)>::Eval (datapoint);
const auto dk = VarDerivative_t<Formula_t, decltype (k)>::Eval (datapoint);

Вместо крокодилов, которые получатся, если брать частные производные функции на картинке вначале (вернее, некоторого её упрощённого варианта, но он выглядит не так страшно).

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

Под катом — небольшое описание, как оно там всё работает.
Читать дальше →
Total votes 80: ↑77 and ↓3 +74
Views 20K
Comments 28

С днём рождения, Эдсгер Вибе Дейкстраǃ

Edison corporate blog Programming *Algorithms *History of IT Biography of geeks
«Пусть тахорги в страхе воют,
Издавая визг и писк!
Ведь на них идет войною
Структуральнейший лингвист!»


image

  • Очень жесткий правдоруб.
  • Мог бы стать физиком-теоретиком (как Ричард Фейнман, который тоже родился 11 мая), но выбрал несуществующую на тот момент профессию — программист.
  • Носит имя алгоритма поиска кратчайшего пути. Алгоритм был создан при решении железячной задачи «О нахождении оптимального пути передачи электрического тока всем существенным элементам цепи, минимизируя при этом расход меди».
  • Непримиримый враг goto.
  • Инициатор мема Considered harmful. «GOTO Statement Considered Harmful», "„GOTO Considered Harmful“ Considered Harmful", «„«GOTO Considered Harmful» Considered Harmful“ Considered Harmful?»
  • Автор концепции семафора.
  • Разработчик операционной системы THE (Technische Hogeschool Eindhoven).
  • Стоял у истоков структурного программирования и распределенных вычислений.
  • Не написал ни одной статьи на компьютере.

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

Под катом несколько цитат Дейкстры, пара сокращенных эссе и список статей на русском языке.

Читать дальше →
Total votes 47: ↑45 and ↓2 +43
Views 22K
Comments 13

Почему в MIT больше не изучают SICP

Programming *
На днях широкое внимание привлекло состоявшееся в начале года на митапе NYC Lisp выступление Джеральда Джей Сассмана, — одного из авторов великого и могучего SICP, а также крестного отца Scheme. Всему виной — ответ на вопрос, почему в MIT прекратили преподавать ставший легендарным курс 6.001, построенный на основе книги Сассмана и Абельсона «Структура и интерпретация компьютерных программ» (вопрос задан на 59 минуте).



Сассман назвал две причины; впрочем, сразу замечу, что в первой из них нет ничего особенного. К 1997 году Абельсон и Сассман уже устали рассказывать практически одно и то же с 80-ых, поэтому решили оставить преподавание и предложили главе кафедры самостоятельно решить, как поступить с самим курсом. Здесь удивляться действительно нечему — что угодно может осточертерть, если заниматься им достаточно долго.

Впрочем, вторая причина гораздо серьезнее. По мнению Сассмана, они с Абельсоном осознали, что учебный план SICP больше не в силах подготовить инженеров к тому, что представляет собой «инжиниринг» сегодня. В 80-ых и 90-ых инженеры строили сложные системы, комбинируя простые и хорошо изученные «части». Целью SICP было предоставить язык абстракций для рассуждений о таких системах.
Читать дальше →
Total votes 38: ↑36 and ↓2 +34
Views 85K
Comments 37

Information

Rating
Does not participate
Location
Zürich, Zürich, Швейцария
Date of birth
Registered
Activity