«Если вы пашете поле, что вы предпочтете: двух сильных быков или 1024 курицы?»
— Сеймур Крэй


Сеймур Крэй, отец «суперкомпьютеров», создатель индустрии суперкомпьютеров, инженер-электронщик и математик.

Ачивки Сеймура Крэя:

• 1958 — За год собрал прототип 6-битного суперкомпьютера из бракованных транзисторов.
• 1960 — Первая машина на германиевых транзисторах вместо ламп (CDC 1604).
• 1963 — Обошел IBM в 3 раза по производительности и на 40% по цене (CDC 6600).
• 1971 — Чтобы не увольнять 4 инженеров отказался от своей зарплаты.
• 1975 — Первый коммерчески успешный векторный суперкомпьютер. Применение архитектуры команд «регистр-регистр» (Cray-1).
• Дизайн суперкомпьютера в виде дивана (Cray-1).
• 1988 — 500 MHz (Cray 3).
• Нашел замену кремнию — арсенид галлия (GaAs) — в шесть раз быстрее кремниевых микросхем.
• 1994 — 1 GHz (Cray-4).
• Чтобы не отвлекаться на посещение Белого Дома и встречу с Президентом США, он отказался от чести быть удостоенным Национальной медалью США в области технологий и инноваций.
• Выкопал собственный противоядерный Vault13 c запасом топлива и воды на 4 года.

С днем рождения, Сеймур Крэй!

Данная статья в некотором роды выжимка того, что Вы могли бы узнать просмотрев разные видео ролики господина Шипилева, Елизарова, Смирнова. Собственно мы даже собрали для Вас плейлист если Вы захотите пойти «the hard way». В статье я лишь попробую Вам передать некоторые основные мысли/идеи, которые при желании Вы сможете намного более глубоко изучить в первоисточниках.

Итак, давайте теперь перейдем к собственно сабжу. Еще лет пять назад можно было не сильно «парясь» выдавать на-гора однопоточные программы, которые с трудом запускались на топовом железе и знать, что через год-два этот кусочек “программки” (простите за аллегорию) начнет работать нормально. Сегодня подобный «бесплатный обед» закончился.


На картинке четко видно, что количество транзисторов все еще растет, но с точки зрения частот мы практически достигли потолка. «Кривизну» рук разработчиков уже трудно компенсировать тем, что через год железо станет работать в два раза быстрее. Хотя не все так печально, процессоры пока еще растут, только с точки зрения количество ядер. Как следствие, для того чтобы «программка», написанная криворуким орком, смогла хоть как-то нормально работать на новом железе, нужно чтобы она нормально работала в многопроцессорной среде. А производительность была напрямую связана с количеством ядер на железе. Вот собственно от том, а что же такое «нормально работала многопроцессорной среде» мы и поговорим далее.

Атака на башни Всемирного Торгового Центра 11 сентября 2001 года унесла жизни 658 сотрудников финансовой компании Cantor Fitzgerald. Ее директор Говард Лутник, потерявший в тот день родного брата, столкнулся с невиданной ранее проблемой. И дело было даже не в том, что серверы компании, включая резервные, также были погребены под обломками. Информация частично была доступна, но она была закрыта за сотнями учетных записей погибших коллег. На помощь были привлечены специалисты из компании Microsoft, они задействовали мощные серверы для максимально быстрого брутфорса — от доступа к данным зависело существование компании, и надо было успеть к первому открытию торгов после атак. Ускорить взлом могли персональные данные погибших. Лутнику пришлось обзванивать родственников и, в самый неподходящий момент, задавать им серию вопросов: день свадьбы, название колледжа или университета, имя собаки.

Это краткий пересказ, пожалуй, самой грустной статьи о паролях за всю их историю, опубликованной в 2014 году в New York Times. История дает две главные характеристики парольной защиты: она создает кучу проблем, и, во многих случаях, все равно не работает. Пароли — настолько плохая концепция защиты, что их уже не раз хоронили и СМИ, и специалисты по безопасности, и научные исследователи. Но воз и ныне там, пароль по-прежнему остается главным методом отделения публичного от приватного, и такую ситуацию, после похорон-то, вполне можно официально считать цифровым зомби-апокалипсисом.

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

Статей про double-checked locking на Хабре было столько, что казалось бы ещё одна — и Хабр лопнет. Вот только по Java неплохие публикации: Реализация Singleton в JAVA, Правильный Singleton в Java, А как же всё-таки работает многопоточность? Часть II: memory ordering или вот замечательный пост от TheShade (слава web-archive!). В наши дни, наверно, каждый Java-разработчик слышал, что если используешь DCL, будь добр объявить переменную volatile. Найти сегодня в коде известных опенсорсных проектов DCL без volatile довольно трудно, но оказалось, что проблемы ещё не полностью решены. Поэтому я добавлю небольшую заметку по теме с примерами из реальных проектов.

Иногда складывается ощущение, что программисты не включают мозги и не пытаются понять, как что работает, а просто следуют простым и понятным правилам вроде «объяви переменную volatile, используй DCL, и всё будет хорошо». К сожалению, такой подход в программировании не всегда работает.

Вышла недавно статья на Хабре о том, как можно самому создать на функциональном языке такие структуры как Очередь (первый зашёл, первый вышел) и Дек (напоминает двусторонний стек — первый зашёл, первый вышел с обоих концов). Посмотрел я на этот код и понял, что он жутко неэффективен — сложность порядка O(n). Быстро сообразить, как создать структуры с O(1) у меня не вышло, поэтому я открыл код библиотечной реализации. Но там была не лёгкая и понятная реализация, а <много кода>. Это было описание пальчиковых деревьев, необходимость и элегантность которых для этой структуры данных хорошо раскрывается текущей статьёй.

Пальчиковые деревья

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

Статья будет состоять из 3-х частей:

Пальчиковые деревья (Часть 1. Представление)
Пальчиковые деревья (часть 2. Операции)
Пальчиковые деревья (Часть 3. Применение)

Разрабатывая структуру данных

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



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

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

— Для чего нужны монады?
— Для того, чтобы отделить чистые вычисления от побочных эффектов.
(из сетевых дискуссий о языке Haskell)

Шерлок Холмс и доктор Ватсон летят на воздушном шаре. Попадают в густой туман и теряют ориентацию. Тут небольшой просвет — и они видят на земле человека.
— Уважаемый, не подскажете ли, где мы находимся?
— В корзине воздушного шара, сэр.
Тут их относит дальше и они опять ничего не видят.
— Это был математик, – говорит Холмс.
— Но почему?
— Его ответ совершенно точен, но при этом абсолютно бесполезен.
(анекдот)

Когда древние египтяне хотели написать, что они насчитали 5 рыб, они рисовали 5 фигурок рыб. Когда они хотели написать, что насчитали 70 людей, они рисовали 70 фигурок людей. Когда они хотели написать, что насчитали в стаде 300 овец, они… — ну, в общем, вы поняли. Так и мучились древние египтяне, пока самый умный и ленивый из них не увидел нечто общее во всех этих записях, и не отделил понятие количества того, что мы подсчитываем, от свойств того, что мы подсчитываем. А потом другой умный ленивый египтянин заменил множество палочек, которыми люди обозначали количество, на значительно меньшее количество знаков, короткой комбинацией которых можно было заменить огромное количество палочек.

То, что сделали эти умные ленивые египтяне, называется абстракцией. Они подметили нечто общее, что свойственно всем записям о количестве чего-либо, и отделили это общее от частных свойств подсчитываемых предметов. Если вы понимаете смысл этой абстракции, которую мы сегодня называем числами, и то, насколько она облегчила жизнь людям, то вам не составит труда понять и абстракции языка Haskell — все эти непонятные, на первый взгляд, функторы, моноиды, аппликативные функторы и монады. Несмотря на их пугающие названия, пришедшие к нам из математической теории категорий, понять их не сложнее, чем абстракцию под названием «числа». Для их понимания совершенно не требуется знать ни теорию категорий, ни даже математику в объёме средней школы (арифметики вполне достаточно). И объяснить их тоже можно, не прибегая к пугающим многих математическим понятиям. А смысл абстракций языка Haskell точно такой же, как и у чисел — они значительно облегчают программистам жизнь (и вы пока даже не представляете, насколько!).

От автора: перевод статьи «Функциональное программирование непопулярно, потому что оно странное» вызвал бурное обсуждение. В нескольких комментариях весьма справедливо замечалось, что при обсуждении недостатков функционального программирования хорошо бы опираться на современные и развитые функциональные языки (в оригинальной статье примеры были на шаблонах C++) и что Хаскель, например, последние пять лет широко используется в индустрии. В связи с этим я хотел бы обратить внимание на две очень предметные статьи из другого блога (от автора книги F# for Scientists): (i) "Недостатки чистого функционального программирования" и (ii) "Почему Хаскель так мало используется в индустрии". Перевод первой из них я как раз и хотел бы представить ниже.

1. На чистых функциональных языках не существует эффективного неупорядоченного словаря и множества

Это седьмая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре:

• Теория категорий для программистов: предисловие
• Категория: суть композиции
• Типы и функции
• Категории, большие и малые
• Категории Клейсли
• Произведения и копроизведения
• Простые алгебраические типы данных

Функторы

За понятием функтора стоит очень простая, но мощная идея (как бы заезжено это ни прозвучало). Просто теория категорий полна простых и мощных идей. Функтор есть отображение между категориями. Пусть даны две категории C и D, а функтор F отображает объекты из C в объекты из D — это функция над объектами. Если a — это объект из C, то будем обозначать его образ из D как F a (без скобок). Но ведь категория — это не только объекты, но еще и соединяющие их морфизмы. Функтор также отображает и морфизмы — это функция над морфизмами. Но морфизмы отображаются не как попало, а так, чтобы сохранять связи. А именно, если морфизм f из C связывает объект a с объектом b,

f :: a -> b

то образ f в D, F f, связывает образ a с образом b:

F f :: F a -> F b

(Надеемся, что такая смесь математических обозначений и синтаксиса Haskell понятна читателю. Мы не будем писать скобки, применяя функторы к объектам или морфизмам.)

Теоретические основы императивного программирования были заложены ещё в 30-х годах XX века Аланом Тьюрингом и Джоном фон Нейманом. Теория, положенная в основу функционального подхода, формировалась в 20-х и 30-х годах. В числе разработчиков математических основ функционального программирования — Мозес Шёнфинкель (Германия и Россия) и Хаскелл Карри (Англия), а также Алонзо Чёрч (США). Шёнфинкель и Карри заложили основы комбинаторной логики, а Чёрч является создателем лямбда-исчисления.

Функциональное программирование как раз основано на идеях из комбинаторной логики и лямбда-исчисления.

Но теория так и оставалась теорией, пока в начале 50-х прошлого века Джон МакКарти не разработал язык Lisp (1958), который стал первым почти функциональным языком программирования. На протяжении многих лет у Lisp не было конкурентов. Позднее появились функциональные языки программирования APL (1964), ISWIM (1966) и FP (1977), которые не получили столь широкого распространения.

Со временем Lisp перестал удовлетворять некоторым требованиям разработчиков программ, особенно с ростом объема и сложности программного кода.

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

Тип — это коллекция возможных значений. Целое число может обладать значениями 0, 1, 2, 3 и так далее. Булево может быть истиной или ложью. Можно придумать свой тип, например, тип "ДайПять", в котором возможны значения "дай" и "5", и больше ничего. Это не строка и не число, это новый, отдельный тип.

Статически типизированные языки ограничивают типы переменных: язык программирования может знать, например, что x — это Integer. В этом случае программисту запрещается делать x = true, это будет некорректный код. Компилятор откажется компилировать его, так что мы не сможем даже запустить такой код. Другой статически типизированный язык может обладать другими выразительными возможностями, и никакая из популярных систем типов не способна выразить наш тип ДайПять (но многие могут выразить другие, более изощренные идеи).

Динамически типизированные языки помечают значения типами: язык знает, что 1 это integer, 2 это integer, но он не может знать, что переменная x всегда содержит integer.

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

Как устроена MySQL-репликация

Андрей Аксенов (Sphinx), shodan

Мой доклад предназначен для тех людей, которые знают слово «репликация», даже знают, что в MySQL она есть, и, возможно, один раз ее настроили, 15 минут потратили и забыли. Больше про нее они не знают ничего.

Мы немного пройдемся по теории, попытаемся объяснить, как это все работает внутри, а после этого вы с утроенными силами сможете сами нырнуть в документацию.

Что такое репликация, в принципе? Это копирование изменений. У нас есть одна копия БД, мы хотим с какой-то целью еще одну копию.

Репликация бывает разных видов. Разные оси сравнения:

• степень синхронизации изменений (sync, async, semisync);
• количество серверов записи (M/S, M/M);
• формат изменений (statement-based (SBR), row-based (RBR), mixed);
• теоретически, модель передачи изменений (push, pull).

В ресторане заиграла почти забытая песня. Вы слушали её в далёком прошлом. Сколько трогательных воспоминаний способны вызвать аккорды и слова… Вы отчаянно хотите послушать эту песню снова, но вот её название напрочь вылетело из головы! Как быть? К счастью, в нашем фантастическом высокотехнологичном мире есть ответ на этот вопрос.

У вас в кармане лежит смартфон, на котором установлена программа для распознавания музыкальных произведений. Эта программа – ваш спаситель. Для того чтобы узнать название песни, не придётся ходить из угла в угол в попытках выудить из собственной памяти заветную строчку. И ведь не факт, что это получится. Программа, если дать ей «послушать» музыку, тут же сообщит название композиции. После этого можно будет слушать милые сердцу звуки снова и снова. До тех пор, пока они не станут с вами единым целым, или – до тех пор, пока вам всё это не надоест.

Мобильные технологии и невероятный прогресс в области обработки звука дают разработчикам алгоритмов возможность создавать приложения для распознавания музыкальных произведений. Одно из самых популярных решений такого рода называется Shazam. Если дать ему 20 секунд звучания, неважно, будет ли это кусок вступления, припева или часть основного мотива, Shazam создаст сигнатурный код, сверится с базой данных и воспользуется собственным алгоритмом распознавания музыки для того, чтобы выдать название произведения.

Как же всё это работает?

Эта поучительная история повествует о том, как важно развивать навыки гугления, и о том, как я боролся с ежечасным полным Garbage collection.

Краткое описание проблемы

После того, как мы мигрировали в продакшене один из компонентов системы (единственный, работающий на Tomcat) на новую версию томката, неожиданно саппорт запаниковал, увидев в логах полуторасекундные запуски GC.

Последние два года вся страна пристально следит за курсом доллара. Новостные выпуски пестрят громкими репортажами о долларе. Все говорят о долларе. А что, если мы на фоне горячего интереса, разберемся с тем, как формируется цена доллара, посмотрим кто и как торгует валютой?! Все результаты, представленные в данной статье, получены на основе официальных торговых данных full orders log (полный журнал заявок), купленные на Московской Бирже. Мы покажем реальные торги изнутри. Параллельно, познакомимся со стандартными методами анализа рынка. Такая аналитика стоит не малых денег и её могут позволить ограниченное число «компаний».

Инструментом для анализа данных будет Java. Анализируемый биржевой инструмент — USDRUB_TOM. Наша задача вытащить любопытные детали из имеющихся данных и попробовать сделать определенные выводы.

Недавний перевод статьи «Пора заменить Python как язык для обучения» спровоцировал большую дискуссию. Очевидно, что программисты считают эту тему очень важной. К сожалению, большинство споров были об императивных языках, и мало кто предлагал функциональные языки в качестве инструмента обучения программированию.

Мы в Хекслете недавно запустили новую версию, ключевой особенностью которой стали практические упражнения по программированию в браузере. В связи с этим мы стали получать еще больше писем от начинающих программистов с вопросами вроде «с чего начать». С одной стороны, они хотят выложить бета-версию приложения в app store через неделю. С другой стороны, мы понимаем, что за такой короткий срок, наверное, можно научиться кодить приложения, но нельзя научиться программировать. И сложно решить, что лучше: как можно быстрее научить созданию простых приложений без реального понимания программирования, алгоритмов и их вычислительной сложности, а потом начать знакомство с этими важными темами, или начать «с начала», и органично придти к созданию приложений и продуктов после освоения фундамента.

В 2001 году, Эдсгер Дейкстра написал письмо экономическому совету университета Техаса. В нем знаменитый ученый призывает членов совета задуматься о смене языка программирования для вводного курса. К сожалению, язык был заменен на Java. Примерно в то же время MIT сменили язык курса «Структура и интерпретация компьютерных программ» с функционального Scheme (диалекта LISP) на Python.

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

Членам Экономического Совета

Я пишу вам по поводу слуха о замене языка во вводном курсе по программированию с функционального языка Haskell на императивный язык Java. Я считаю, что Совет должен взять на себя ответственность, чтобы решение не было принято на неправильном уровне.

Задача

За минимальное время написать HTTP сервер, который после запуска сможет корректно ответить браузеру и отдать простую HTML страничку (минимальное время, чтобы кода было мало, чтобы новичку вникать было проще).
У меня это заняло около 15 минут. Сервер вроде справляется с поставленной задачей.

Суть примера — показать что такое Socket, ServerSocket, InputStream, OutputStream, и Thread.

Опять на собеседованиях по Java спрашивают про hashCode и equals? А кто из собеседующих сам ответит на вопрос, как вычисляется Object.hashCode() и System.identityHashCode()? Насколько дорог вызов этих методов? Как их можно ускорить в HotSpot JVM? Держу пари, едва ли кто даст правильный ответ. Разве что, кто прочитает эту статью.

Привет, %habrausername%. Я хочу сыграть с тобой в игру.

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

От предыдущего разработчика осталась кучка кода и домашние тапочки. Ты осторожно кладёшь тапочки в мусорную корзину и начинаешь рефакторинг.

Этот код ужасен. Во-первых, нет никого, кто мог бы сказать, зачем этот код писался. Во-вторых, нет никакой документации. Нет даже комментариев, не говоря уже о юнит-тестах. В-третьих, код не структурирован, а имена классов и методов ни о чём не говорят. И, наконец, работать это должно начать не сегодня, и даже не вчера, а внезапно.
Ну как, %habrausername%, пробежал холодок по спине?

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

Все языки

«Есть два подхода к программированию. Первый — сделать программу настолько простой, чтобы в ней очевидно не было ошибок. А второй — сделать её настолько сложной, чтобы в ней не было очевидных ошибок.»
Tony Hoare. Профессор, занимался реализацией Алгол 60, сейчас исследователь в Microsoft Research.

Algol 60 (позже повлиявший на C)

«Я не мог устоять перед искушением добавить в язык нулевой указатель (null), просто потому, что его так легко было реализовать. Это привело к бессчётному множеству ошибок, уязвимостей и сбоев, которые нанесли ущерб, наверное, в миллиард долларов за последние сорок лет.»
Tony Hoare.

Привет, уважаемые хабровчане!

Это корпоративный блог МТС. Здесь наши специалисты, отвечающие за связь и технологии, будут писать обо всем самом интересном. Начнем с директора Департамента эксплуатации конвергентных сетей и сервисов МТС Андрея Серегина. Итак, слово Андрею Вячеславовичу.



Доброго времени суток! Наконец-то у меня дошли руки до текста для Хабра.

Хочу поделиться своим опытом с профессиональной и интересующейся публикой. 4 года назад мы в МТС первыми в стране открыли Единый Центр оперативного управления мобильной сетью, который расположился в Краснодаре. В ноябре прошлого года мы официально открыли Единый Центр управления фиксированной сетью в Нижнем Новгороде. Таким образом, мы завершили централизацию мониторинга и управления всеми сетями – мобильной и фиксированной. И это первый в России опыт централизации такого масштаба среди телеком-операторов.