Va

Побеждая C двадцатью строками Haskell: пишем свой wc

Привет, Хабр.

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

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

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

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

Быстрее, чем C++; медленнее, чем PHP

Привет, Хабр.

У меня тут случайно код на хаскеле получился быстрее аналогичного кода на C++. Иногда — на 40%.

(время работы, меньше — лучше, C++ снизу)

Что самое смешное — я собирал хаскель-код через LLVM-бекенд, но при этом сравнивал с GCC. Если сравнивать с clang (что вроде как логичнее), то всё становится ещё хуже для плюсов: почему-то на этой задаче clang проигрывает GCC в пару раз, и разница становится не 40%, а этак раза три. Впрочем, одна маленькая модификация C++-кода это поменяет.

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

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

Посмотрим, как этого можно достичь?

В качестве бонуса — сравнение с некоторыми другими языками. Спойлеры:

• Nim медленнее компилятора C двадцатилетней давности.
• C# в пять раз медленнее Java, которая оказывается вполне на уровне Rust.
• Go вровень с C.
• PHP быстрее питона (что оправдывает вторую часть заголовка).

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

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

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

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

О новых стандартах C++

Сегодня у меня довольно короткий пост. Я бы его и не писал, наверное, но на Хабре в комментах довольно часто можно встретить мнение, что плюсы становятся хуже, комитет делает непонятно что непонятно зачем, и вообще верните мне мой 2007-й. А тут такой наглядный пример вдруг попался.

Почти ровно пять лет назад я писал о том, как на C++ сделать каррирование. Ну, чтобы если можно написать , то можно было бы писать и . Тогда C++14 только вышел и еле-еле поддерживался компиляторами, так что код использовал только C++11-фишки (плюс пара костылей для симуляции библиотечных функций из C++14).

А тут я что-то на этот код снова наткнулся, и мне прямо резануло глаза, насколько он многословный. Плюс ещё и календарь не так давно переворачивал и заметил, что сейчас уже 2019-й год, и можно посмотреть, как C++17 может облегчить нашу жизнь.

Посмотрим?

Игнорируем лишние аргументы функции на C++

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

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

был корректным. Или, что то же самое, чтобы можно было писать .
А если нужны только первые N аргументов, остальные тоже можно было не указывать: .

Радости и горести побед над C: делаем конфетку из прототипа wc на хаскеле

Привет, Хабр.

Итак, в прошлый раз мы эмпирически доказали, что на хаскеле можно довольно легко написать этакий игрушечный wc, который при этом существенно быстрее реализации wc из GNU Coreutils. Понятное дело, что это не совсем честное сравнение: наша программа не умеет ничего, кроме подсчёта байт, строк и слов, тогда как настоящий wc куда мощнее: он имеет ещё несколько статистик, поддерживает опции, умеет читать из stdin… Короче, у нас действительно получилась всего лишь игрушка.

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

Основная функция С-версии не влезла на 4k-экран в портретной ориентации 4-м шрифтом.

Кроме этой модуляризации мы, среди прочего:

• выразим идею, что некоторые статистики вроде подсчёта числа байт могут работать эффективнее на всём входе целиком, а другие должны смотреть на каждый байт;
• реализуем ещё больше статистик, наслаждаясь возможностью рассуждать о каждой из них в отдельности (то, что называют local reasoning);
• напишем немного тестов, наслаждаясь local reasoning’ом ещё раз;
• испытаем некоторые почти зависимо типизированные техники, успешно получив корректно работающий, но феерически тормозящий код;
• поиграем с Template Haskell;
• полюбуемся (не)предсказуемостью и (не)воспроизводимостью производительности результирующего кода.

Этот ваш хаскель (не) только для факториалов и годен

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

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

Ну и вдобавок можно легонько выпендриться более эффективным алгоритмом, чем лобовой поиск делителей для каждого числа от до .

Пора на свалку

Никогда не думал, что это случится со мной, но, похоже, я выгорел. А ещё мне стрёмно. Да, это ещё одна статья про выгорание.

Я тут на днях смотрел на свою RSS-читалку и заметил, что под тегом «C++» у меня где-то три сотни непрочитанных статей. Я не прочитал ни одной статьи по плюсам с прошлого лета, и мне офигенно. Я не написал ни строчки осмысленного кода на плюсах за последние три месяца, с тех пор, как распустили отдел, где я работал, и мне просто супер. Я позволил себе хотеть больше никогда не писать на плюсах, и у меня появились крылья.

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

Короче, да, я выгорел. И я не знаю, что делать дальше.

Тесты или типы

Перевод

Привет, Хабр. На днях я искал, как сделать что-то в Idris, и наткнулся на неплохой пост, вольный перевод которого выглядит вполне уместным. Вольности и отсебятину, где необходимо, я буду обозначать ⟦вот такими закорючками в начале и в конце⟧.

Когда стоит использовать тесты, а когда — типы? Какую информацию и какие гарантии мы получаем в обмен на наши усилия по их написанию?

Мы рассмотрим простой и немного надуманный пример, выраженный на Python, C, Haskell и Idris. Мы также увидим, что можно сказать о реализации без каких-либо дополнительных знаний о ней, в каждом из случаев.

Мы не будем учитывать разнообразные чёрные ходы, позволяющие явно нарушать гарантии языка (например, расширения C, в Haskell, небезопасные приведения типов), иначе нельзя было бы сделать вообще никаких выводов, и этот пост получился бы довольно коротким. ⟦Кроме того, у того же хаскеля есть подмножество Safe Haskell, явно и транзитивно запрещающее использование этих и ряда других трюков, могущих нарушить целостность языка.⟧

Подборки

Армейские ПесниКлассика пианиноМузыка из рекламыДетские песни из мультфильмовМузыка для аэробикиСборник песен 70х годовДля любимого человекаКлассика в современной обработкеКлубные миксы русских исполнителей3D ЗвукДальнобойщикиЗарубежный рэп для машиныТоповые Клубные ТрекиМощные БасыДискотека 2000Песни про папуХристианские ПесниЗимняя МузыкаМузыка Для МедитацииРусские Хиты 90ХГрустная МузыкаRomantic SaxophoneТанцевальный хип-хопНовогодние песниЗарубежные хиты 80 — 90Песни про покемонаРомантическая МузыкаМотивация для тренировокМузыка для сексаМузыка в машинуДля силовых тренировокПремия «Grammy 2017»

Саундтреки

Из фильма В центре вниманияИз фильма Ван ХельсингИз сериала Дневники ВампираИз фильма Скауты против зомбииз фильмов ‘Миссия невыполнима’Из фильма Голодные игры: Сойка-пересмешница. Часть 2OST ‘Свет в океане’OST «Большой и добрый великан»из фильма ‘Новогодний корпоратив’из фильма ‘Список Шиндлера’ OST ‘Перевозчик’Из фильма Книга джунглейиз сериала ‘Метод’Из фильма ТелохранительИз сериала Изменыиз фильма Мистериум. Тьма в бутылкеиз фильма ‘Пассажиры’из фильма ТишинаИз сериала Кухня. 6 сезониз фильма ‘Расплата’ Из фильма Человек-муравейиз фильма ПриглашениеИз фильма Бегущий в лабиринте 2из фильма ‘Молот’из фильма ‘Инкарнация’Из фильма Савва. Сердце воинаИз сериала Легко ли быть молодымиз сериала ‘Ольга’Из сериала Хроники ШаннарыИз фильма Самый лучший деньИз фильма Соседи. На тропе войныМузыка из сериала «Остров»Из фильма ЙоганутыеИз фильма ПреступникИз сериала СверхестественноеИз сериала Сладкая жизньИз фильма Голограмма для короляИз фильма Первый мститель: ПротивостояниеИз фильма КостиИз фильма Любовь не по размеруOST ‘Глубоководный горизонт’Из фильма Перепискаиз фильма ‘Призрачная красота’Место встречи изменить нельзяOST «Гений»из фильма ‘Красотка’Из фильма Алиса в ЗазеркальеИз фильма 1+1 (Неприкасаемые)Из фильма До встречи с тобойиз фильма ‘Скрытые фигуры’из фильма Призывиз сериала ‘Мир Дикого Запада’из игр серии ‘Bioshock’ Музыка из аниме «Темный дворецкий»из фильма ‘Американская пастораль’Из фильма Тарзан. ЛегендаИз фильма Красавица и чудовище ‘Искусственный интеллект. Доступ неограничен»Люди в черном 3’из фильма ‘Планетариум’Из фильма ПрогулкаИз сериала ЧужестранкаИз сериала Элементарноиз сериала ‘Обратная сторона Луны’Из фильма ВаркрафтИз фильма Громче, чем бомбыиз мультфильма ‘Зверопой’Из фильма БруклинИз фильма Игра на понижениеИз фильма Зачарованнаяиз фильма РазрушениеOST «Полный расколбас»OST «Свободный штат Джонса»OST И гаснет светИз сериала СолдатыИз сериала Крыша мираИз фильма Неоновый демонИз фильма Москва никогда не спитИз фильма Джейн берет ружьеИз фильма Стражи галактикииз фильма ‘Sos, дед мороз или все сбудется’OST ‘Дом странных детей Мисс Перегрин’Из игры Contact WarsИз Фильма АмелиИз фильма Иллюзия обмана 2OST Ледниковый период 5: Столкновение неизбежноИз фильма Из тьмыИз фильма Колония Дигнидадиз фильма ‘Страна чудес’Музыка из сериала ‘Цвет черёмухи’Из фильма Образцовый самец 2из фильмов про Гарри Поттера Из фильма Дивергент, глава 3: За стеной из мультфильма ‘Монстр в Париже’из мультфильма ‘Аисты’Из фильма КоробкаИз фильма СомнияИз сериала Ходячие мертвецыИз фильма ВыборИз сериала Королек — птичка певчаяДень независимости 2: ВозрождениеИз сериала Великолепный векиз фильма ‘Полтора шпиона’из фильма Светская жизньИз сериала Острые козырьки

Передаем указатели на функции-члены в C API

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

Понятно, что в качестве можно использовать свободную функцию, статическую функцию-член или вообще лямбду (2017-й год на дворе, всё-таки), но писать соответствующую конструкцию каждый раз для каждой функции руками несколько лениво, а препроцессор, как мы все, конечно, знаем — моветон.
В этом посте мы попробуем (и, что характерно, у нас это получится) написать универсальную обёртку, а заодно посмотрим, как кое-какая фишка из C++17 поможет нам ещё сократить количество избыточного кода. Никаких крышесносных шаблонов здесь не будет, решение, на мой взгляд, достаточно тривиально, но, пожалуй, им всё равно имеет смысл поделиться (и заодно лишний раз попиарить новые возможности C++17).

Can I haz? Ударим программированием на типах по дженерикам

Привет, Хабр.

В прошлый раз мы описали -паттерн, обрисовали проблемы, которые он решает, и написали несколько конкретных инстансов:

Выглядит неплохо. Какие тут могут возникнуть сложности?

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

Они позволяют нам легко писать отдельные тесты или вспомогательные утилиты, не зависящие от всего .

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

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

Если интересно, как решить эту задачу в общем виде, причём тут зависимые типы, и как всё это в итоге будет выглядеть на хаскеле — велкам под кат.

Can I haz? Рассматриваем ФП-паттерн Has

Привет, Хабр.

Сегодня мы рассмотрим такой ФП-паттерн, как -класс. Это довольно любопытная штука по нескольким причинам: во-первых, мы лишний раз убедимся, что паттерны в ФП таки есть. Во-вторых, оказывается, что реализацию этого паттерна можно поручить машине, что вылилось в довольно любопытный трюк с тайпклассами (и библиотеку на Hackage), который лишний раз демонстрирует практическую полезность расширений системы типов вне Haskell 2010 и ИМХО куда интереснее самого этого паттерна. В-третьих, повод для котиков.

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

Итак, как в хаскеле решается проблема управления некоторым глобальным окружением, доступным только для чтения, которое необходимо нескольким различным функциям? Как, например, выражается глобальная конфигурация приложения?