Автор: д-р Майкл Скотт

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

1. Введение

У большинства людей есть любимый язык, на котором они любят программировать. Или у них может быть два или три языка по принципу «лошади за курсы». Может быть, им нравится один язык для сценариев высокого уровня, а другой — для вещей низкого уровня. Мне всегда нравились C и C++, и у меня многолетний опыт их использования. В прошлом я не мог толком комментировать соревнования, так как у меня не было с ними опыта. На некоторые я бы посмотрел свысока — Java был для людей, которые не могут разобраться с указателями, Rust — для высокопоставленных академиков. На самом деле у меня были бы всевозможные абсурдные предубеждения, но все они не основывались бы ни на каком реальном опыте.

В результате внутреннего проекта мне было поручено реализовать переносимый высокопроизводительный криптографический язык на как можно большем количестве языков. Все реализации на всех языках должны давать одинаковые выходные данные для одних и тех же входных данных. Библиотека довольно интересна и полезна сама по себе, и документирована в другом месте на этом сайте. Достаточно сказать, что он реализует симметричное шифрование, хеширование, генерацию случайных чисел, криптографию с открытым ключом (с использованием как RSA, так и эллиптических кривых) и криптографию на основе пар. Последнее является результатом криптографии на эллиптических кривых, которая представляет особый интерес для моих работодателей. Библиотека выполняет множество очень сложных целочисленных вычислений. Возможно, самый сложный расчет касается самого «спаривания». Действительно, жизнеспособность криптографии на основе пар зависит от способности быстро вычислять пары. Таким образом, производительность является большой проблемой.

2. Первые впечатления

Трудно не рассматривать развитие языков за последние 40 лет или около того как нечто иное, чем дань уважения Кернигану и Ричи и их изобретению C. Все рассмотренные здесь языки (C, Java, Swift, Javascript, Rust, C#) и Go) очень похожи на C. На самом деле разница между C и его непосредственным предшественником Fortran больше, чем между C и любым из новых языков, рассматриваемых здесь.

3. Первое препятствие

Тип целочисленной арифметики, требуемый теоретико-числовой криптографией, является довольно специализированным. Поскольку числа, используемые в криптографии (возможно, 256 бит), как правило, намного больше, чем размеры регистров (возможно, 64 бита), нам необходимо реализовать так называемую арифметику с множественной точностью. Так что в идеале одно из этих больших криптографических чисел должно быть представлено в виде массива компьютерных слов. Ясно, что чем больше размер слова процессора, тем лучше, поскольку 256-битное число более эффективно представляется и обрабатывается как четыре 64-битных «цифры», а не как восемь 32-битных цифр.

Теперь при перемножении двух 32-битных чисел результат будет 64-битным. Это прекрасно понимали Керниган и Ричи, предусмотрительно указавшие два целочисленных типа: int и long. Произведение двух целых чисел уместилось бы в длинное.

Так что на 32-битном процессоре нам нужен 64-битный тип. А на 64-битном процессоре нам нужен 128-битный тип. И тут начинаются проблемы. Невероятно, что ни один из наших «современных» компьютерных языков не поддерживает стандартный 128-битный целочисленный тип, даже несмотря на то, что 64-битные процессоры сейчас распространены повсеместно, а теперь даже вытесняют 32-битные процессоры из их ниши на рынке мобильных устройств. К счастью, разработчики популярного компилятора GCC для C и C++ увидели свет, и теперь доступен 128-битный тип. И GCC определяет свой собственный стандарт.

Это означает, что в C при разумном использовании #define и typedef мы можем мгновенно переключиться с 32-битной на 64-битную версию библиотеки. Увы, это невозможно ни в одном из других новых языков. Хорошим примером может служить Java, где тип int навсегда застрял на 32-битном уровне, а тип long — на 64-битном. В те времена, когда в моде были 32-битные процессоры, теперь это шар и цепь. Мы можем довольно неэффективно запрограммировать выход из этой проблемы, подделав псевдо128-битный тип. Но это будет медленно. Так что, похоже, мое первоначальное предубеждение в пользу C будет иметь некоторое обоснование.

4. Сделать решительный шаг

Одна вещь, которая мне была нужна, — это текстовый редактор, который мог бы работать со всеми языками и делать такие приятные вещи, как выделение ключевых слов. Я не думал, что есть один, который поддержит их всех, но он есть. Давайте послушаем это для Sublime Text!

Настоятельно рекомендуется — получить его здесь https://www.sublimetext.com/.

Когда я программировал на каждом языке, Стокгольмский синдром быстро срабатывал. Они мне действительно начали нравиться, и я начал видеть их индивидуальные преимущества. Некоторые изменения по сравнению с C казались совершенно произвольными. Точки с запятой присутствуют (Java, Javascript, C#), исчезают (Swift и Go), и когда я привык к их отсутствию, они снова появляются (Rust). А что не так со старым оператором for(i=10;i›=0;i — )? Он настолько выразительный, что с ним можно делать практически все, что угодно. Java, C#, Javascript и Go согласны, а Swift и Rust — нет. Чем же так лучше для i в (0..11).rev()? Кроме того, каждый язык имеет свое собственное предпочтительное соглашение для именования переменных и может (как Rust) довольно утомительно настаивать на том, чтобы мы придерживаемся правил дома.

Большой проблемой для меня является управление памятью. Не то чтобы у меня было много памяти для управления, на самом деле относительно немного. Поэтому я хотел бы, чтобы вся память была выделена из стека, а не из кучи. С C вы точно знаете, откуда он взялся. Как программист, я немного помешан на контроле, поэтому меня беспокоило то, что я не знал точно, что происходит под капотом с другими языками. Кажется, что Java, Go и Swift (в меньшей степени) любят использовать память Heap, в то время как Rust в этом отношении больше похож на C. Существует отношение «предоставь это мне» в отношении новых языков, с которым мне не совсем комфортно.

Мне нравится чистый синтаксис, и Swift, Javascript, Java и Go, как правило, дружелюбны в этом отношении. Rust больше похож на C, и трудно избежать избытка &s и muts. Учитывая тот же результат, я надеюсь, что каждый язык разработан таким образом, чтобы самый чистый синтаксис приводил к самому быстрому коду. Другими словами, я не хотел бороться с языком, чтобы заставить его что-то делать эффективно.

Больше всего проблем у меня было с Rust, но потом я кое-что заметил. С Rust моя отладка имела тенденцию переходить от отладки во время выполнения к отладке во время компиляции. Компилятор Rust на самом деле усложнил написание неправильного кода. На самом деле довольно впечатляюще.

Го действительно умный. Мне нравится его минимализм. И мне нравились его «улучшенные структуры», которые идеально подходили для того, что я пытался сделать. В Rust есть нечто подобное. На самом деле мне не нужна была вся мощь классов, которую мне навязывали некоторые другие языки.

Последовательность, которой я следовал, была C к Java, к C#, к Javascript, к Swift, к Rust. Это, вероятно, было довольно случайным, поскольку различия с непосредственным предшественником были достаточно небольшими. И на самом деле переход с Java на C# настолько прост, что я получил автоматический инструмент, который сделает это за меня.
Зрелость была проблемой для Swift, поскольку спецификация постоянно менялась, пока я ее писал. Надеюсь, с версией 3 все уляжется.

4.1. Как быстро?

Моя программа расчета жеребьёвки состояла из цикла, который рассчитывал 1000 пар. Для тех, кто знает о спариваниях, фактическое спаривание было рассчитано по 455-битной кривой BLS. Оптимизация компилятора была максимальной во всех случаях.

Все тайминги указаны в секундах, в основном на процессоре i3 Core Intel. Тайминги Swift приведены для Apple Mac и масштабированы для целей сравнения.

1. C (32-разрядная) — 22
2. C (64-разрядная) — 9
3. Java (32-разрядная) — 41
4. Java (псевдо 64-разрядная ) — 24
5. C# (псевдо 64-бит) — 21
6. Javascript (Google Chrome) — 390
7. Go (псевдо 64-бит) — 182
8. Swift (32-разрядная версия) — 187
9. Rust (32-разрядная версия) — 23

4.2. Обсуждение

В чем проблема с Go? Это так медленно! Хорошо, он компилируется очень быстро, но кого это волнует. Это похоже на интернет-провайдера, который может похвастаться неограниченным количеством загрузок, не говоря уже об очень ограниченной пропускной способности. И Свифт не такой быстрый. Но вы должны восхищаться производительностью JIT-компиляторов Java и C#. Очевидно, что вложенные человеко-годы окупились. Rust утверждает, что он быстрый, и это так.

Но C по-прежнему остается победителем с точки зрения производительности. Какой был моим любимым? Ну, каждый по очереди, как я его использовал, и моя последняя попытка была с Rust, так что да, сейчас мне очень нравится Rust. Но после периода охлаждения я, вероятно, вернусь к С.

Загрузить эту статью о сравнении других компьютерных языков

Эта статья впервые появилась в разделе блога на веб-сайте MIRACL 3 августа 2016 г.