company_banner
21 апреля в 14:30

Как я писал предложение к стандарту С++

Это будет история младшего разработчика из Яндекс.Паспорта о появлении предложения в стандарт С++, разработанного в соавторстве с Антоном antoshkka Полухиным. Как часто бывает в жизни, что-то новое началось с боли, а точнее — с желания её прекратить.


Жила-была библиотека у меня на поддержке. Всё у неё было хорошо: собиралась под Linux, работала, не падала. Однажды пришли люди с просьбой (требованием) собрать её под Windows. Почему бы и нет? Но с первого раза не получилось. Корнем зла оказалась рукописная криптография, которая в какой-то момент умножала два 64-битных целых числа. Для сохранения результата такого умножения потребуется число на 128 бит, и в библиотеке использовался тип __int128. Он прекрасен: имеет естественный интерфейс, поддерживается несколькими компиляторами (gcc, clang), работает без аллокации памяти, но главное — он есть.

Разработчики компилятора из Microsoft поддержку этого типа не обеспечили, аналогов не придумали — или я их не нашёл. Единственное пришедшее на ум кроссплатформенное решение — Big Numbers из OpenSSL, но оно несколько другое. В итоге конкретно эту проблему я решил «велосипедом»: нужен был только uint128_t с ограниченным набором операций. Из нескольких чужих решений собрал класс UInt128, положил его в исходники библиотеки. «Велосипед» — как раз и есть та самая боль. Задача была решена.

Вечером того же дня пошёл развеяться на мероприятие, где люди из «Рабочей Группы 21» (РГ21) рассказывали о том, как они обрабатывают напильником С++. Я послушал и написал на cpp-proposal@yandex-team.ru короткое письмо из двух предложений на тему «нужен int128 в сpp». Антон Полухин в ответ поведал о том, что разработчики стандарта хотят решить эту проблему раз и навсегда. Логично: сейчас мне потребовалось число на 128 бит, а кому-то надо работать с числами на 512 бит — и этот кто-то тоже захочет удобный инструмент.

Ещё Антон поведал, что есть два пути к решению: через ядро языка и через библиотеку. Существует мнение, и я его разделяю, что синтаксис языка и так достаточно сложен: добавить в язык конструкцию, которая обеспечит кроссплатформенную и эффективную возможность использовать числа разной точности, будет очень непросто. А вот в рамках библиотеки справиться вполне реально: шаблоны — наше всё. «Нужен работающий прототип, — сказал Антон. — И желательно с тестами». А ещё выяснилось, что тип должен быть plain old data (POD), чтобы понравиться большему количеству людей.

И я пошёл делать прототип. Название wide_int выбрал осознанно: устойчивых ассоциаций с таким названием нет, во всяком случае — распространённых. Например, big_number мог ввести в заблуждение — мол, он хранит значение в куче (heap) и никогда не переполняется. Хотелось получить тип с поведением, аналогичным поведению фундаментальных типов. Хотелось сделать тип, размер которого будет продолжать их прогрессию: 8, 16, 32, 64… 128, 256, 512 и т. д. Через какое-то время появился работающий прототип. Сделать его оказалось несложно: он должен был компилироваться и работать, но необязательно по-настоящему эффективно и быстро.

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

Критиковали немного. Например, кто-то высказал желание сделать целочисленный тип, который не переполняется. Или тип, размер которого можно задать с точностью до бита (и получить, например, размер в 719 бит!). Предложение отказаться от привязки к количеству бит, а задавать количество машинных слов, мне показалось самым странным: бизнес-логике всё равно, сколько слов в числе на какой-то платформе, — ей важно однозначно определять одни и те же числа на разных платформах. Скажем, уникальный идентификатор пользователя — беззнаковое целое число из 64 бит, а не из одного unsigned long long.

Если в двух словах, это были идеи для других типов. Критику мы выслушали, каких-то существенных замечаний не оказалось. После этого Антон опубликовал предложение к стандарту и поехал его защищать на очередное заседание комиссии.

Защита прошла успешно: наше предложение взяли в работу — другими словами, оно будет рассматриваться на заседаниях и дальше. Был высказан ряд замечаний; сейчас мы вносим нужные исправления. В частности, комиссия всё-таки попросила в wide_int оперировать количеством машинных слов. Аргументация проста: тип так или иначе будет реализован, но если использовать эти самые машинные слова, то выйдет эффективнее. У меня остаётся надежда, что удобный алиас uint128_t попадёт в стандарт — тогда я смогу выкинуть свой тип UInt128, пока его не увидел кто-то ещё. =)

Актуальную версию имплементации можно найти здесь. Ещё есть документ и небольшое обсуждение на stdcpp.ru. Всего со дня отправки первого письма на cpp-proposal@yandex-team.ru прошло около четырёх месяцев. Из них около 40 часов нерабочего времени мною было потрачено на это предложение. На момент написания статьи имплементация распухла на 1622 строки, да ещё тесты добавили 1940 строк.

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

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

В-третьих, я много нового для себя узнал о шаблонах в С++.

В-четвёртых, говорят, что это как-то усилит моё резюме… Пока не проверял, но поверю опытным коллегам на слово.

В-пятых, когда Бьярне Страуструп где-то в переписке, посвящённой обсуждению твоей работы, пишет кому-то «+1» — это весело. =) Даже если он поддерживает чью-нибудь критику.

Напоследок скажу, что про новости и мероприятия РГ21 С++ можно узнавать, подписавшись в Твиттере на канал stdcppru.
Автор: @cerevra
Яндекс
рейтинг 432,74
Как мы делаем Яндекс

Комментарии (80)

  • +6
    У меня остаётся надежда, что удобный алиас uint128_t попадёт в стандарт — тогда я смогу выкинуть свой тип UInt128, пока его не увидел кто-то ещё. =)

    А что вам мешает использовать предложенный к стандартизации шаблон прямо сейчас — вместо класса UInt128? Заодно обкатаете свое предложение в реальном проекте? ;-)

    • +1
      Имплементация делает слишком много копирований — так было проще написать код (Proof of concept). Об эффективности речи в нём нет
  • 0
    А почему не собирали тем же GCC?
    • +1
      Надо было собирать проект в Microsoft Visual Studio 2015. Это данность, с которой пришлось жить
      • +4
        1. Внести изменение в стандарт C++ легче чем перевести приложение на другой компилятор?
        2. Но даже если ваше изменение примут, оно не решает же поставленную задачу, потому что в Microsoft Visual Studio 2015 изменение никогда не появится.
        • +3

          Задача итак решена, просто не эстетично. Разговор про то, чтобы не писать велосипеды в дальнейшем.

        • +1
          1. Внести изменение в стандарт действительно в некоторых ситуациях может быть легче.
          2. В этой версии MSVS останется велосипед, в будущих появятся изменения, всем хорошо, все довольны.
          • +1
            > всем хорошо, все довольны.

            Не совсем. Негативные эффекты есть — стандарт C++ станет жирнее. А если эта фича будет добавлена в какой-нибудь популярный хедер, то ВСЕ его использующие получат пенальти на скорость компиляции, даже если им фича не нужна. Хотя фича прекрасно могла быть реализована в виде подключаемой библиотеки, без залезания в стандарт.
            • 0
              А если эта фича будет добавлена в какой-нибудь популярный хедер, то ВСЕ его использующие получат пенальти на скорость компиляции, даже если им фича не нужна

              А модули не помогут? Или с высокой вероятностью их примут и реализуют уже после этой фичи?

              • 0
                С модулями ни в чём нельзя быть уверенным
        • 0
          1. Вот есть данность: Windows и MSVC. Пусть не 2015-й, а более поздний. __uint128 в нём не появится никогда, а 128-битный тип нужен. Ваши предложения?

          2. Появится в более поздникх MSVC, а в более ранних можно скомпилировать библиотеку.
  • 0
    Если бы ребята приняли в стандарт атрибут при декларации целочисленной переменной для указания endian при ее сериализации, как это будет в стандарте для ANSI C (и уже реализовано в новых GCC), то очень много ABIшного кода можно было бы выпрямить и избежать многих ошибок.
    • +2
      Это повод для еще одного предложения: https://stdcpp.ru/proposals/new =)
      • 0

        Тут не proposal нужен, а своевременная синхронизация с последним доступным стандартом C на момент принятия нового стандарта C++

        • +1
          С++ обеспечивает не полную совместимость с C. Например, restrict отсутствует в С++. Поэтому нельзя ожидать, что всё, что появлется в С, должно быть тут же подхвачено в С++. Тем более, если речь идёт о том, что еще только будет в стандарте C. Если поискать здесь «From C», то видно, что что-то втягивается из C. И если есть острое желание что-то конкретное втянуть из C, то это нужно обсуждать отдельно
          • 0
            Например, restrict отсутствует в С++
            Как будто это хорошо, restrict как минимум позволяет компилятору проводить более сильные оптимизации, т.к есть более сильные ограничения на область памяти. Из фич C99, которых нет в стандарте меня лично бесит designated initializers, и нет initializer list не замена, т.к надо помнить порядок полей структуры, жаль что только clang поддерживает их в std=c++11
            • 0
              Это ни хорошо, ни плохо. Так есть
              • 0
                Но над этим работают! P0329R0, к примеру, будет включен в C++20. Может к концу столетия и restrict поддержат…
                • 0
                  как много раз за вашу карьеру вы использовали __restrict/__restrict__/пр. в с++ программе и это дало хоть какой-то прирост?
                  • 0
                    Я его не использовал — потому что он не входит в стандарт. Однако возможное ускорение заметно.

                    Неясно, впрочем, насколько получаемое ускорение стоит того, что можно «переборщить» и нарваться на весьма сложно отлавливаемые баги.
                    • 0
                      Однако возможное ускорение заметно.

                      возможное. Ситуаций, где restrict имеет значение, очень мало. Тем более, что c++ по стандарту считает, что указатели на разные типы не алиасятся (кроме void*/char*)
                      • +1
                        В любой числодробилке такие ситуации есть и типы там почти всегда одинаковые.
                        Так что фича то нужная… хоть и не так широко.
                        • 0
                          Я лишь пытаюсь сказать, что для 1-2х случаев в жизни можно воспользоваться и расширениями компиляторов (если надо под разные — через define, вон, с экспортом символов из библиотек всю жизнь так делают). Если бы среднестатистический программист пользовался restrict'ом часто, он бы появился в с++ намного раньше
                          • 0
                            Над proposal на restrict сейчас работают люди занимающиеся разработкой компиляторов. Там есть много сложностей связанных с алиасингом this, алиасингами членов класса (не очень понятно как это указывать с точки зрения синтаксиса).

                            Авось через лет 5 появится в стандарте.
                  • 0

                    Ну например с ним openCL компилятор, что от amd, что от altera позволяет ускорить код где-то на 5-7%.

                • 0
                  Proposal классный, если бы еще memberов с существующим default constructor можно было бы опускать то вообще бы конфетка была.
  • 0
    В частности, комиссия всё-таки попросила в wide_int оперировать количеством машинных слов

    Стандарт же вроде не определяет размер машинного слова. Как быть если надо именно int2048_t?

    • +1
      У комиссии есть планы по решению этой проблемы. Антон рассказывал об этом
  • +1
    А почему boost multiprecision не зашел? Он и сам умеет и бэкенды всякие дружит. Имею опыт использоваания, как раз из-за типа int128 для msvc. Помедленней чем нативный __int128 gcc, но для моих применений вполне.
    http://www.boost.org/doc/libs/1_64_0/libs/multiprecision/doc/html/boost_multiprecision/ref/cpp_int_ref.html
    • 0
      Он крутой, согласен. Но он не POD, поэтому не стали тащить его в стандарт.
      А в задаче не было возможности использовать boost
    • 0
      В 20 раз это помедленней? Я велосипед только из-за этого и делал.
  • +2
    Можно делать ставки, в каком году примут стандарт с этим нововведением?

    Но автор молодца — не остановился на этапе «поныть что все плохо»
    • 0
      Спасибо

      Я бы ожидал этот код в C++23. Это моё частное мнение, и оно может не совпадать с мнением Вселенной
      • +1
        Код в колонии на марсе можно будет сразу нормально писать!
  • +5

    Слониха и слонёнок помогают мыши прогнать кота. Это иллюстрация работы комитета С++.

  • 0
    Я, конечно, плохо знаю, как там дела у microsoft, но для intel-овских процессоров есть даже специальная библиотека для работы с 128 разрядными числами, которая использует SIMD(tmmintrin.h, вспомнил эту статью)(может что есть и для amd).
    Но допустим, что мы не хотим использовать ее и пишем собственную библиотеку на шаблонах wide_int. Тогда следующий вопрос к языку C: «В ассемблере уже много лет есть команда adc, которая складывает с учетом флага переноса, где она в С?»(Также еще можно поставить вопрос про SIMD и конвейерные инструкции). И количество таких вопросов огромно, когда мы начинаем копаться в возможностях С и ассемблера… И что самое важное, это полезные фичи ускоряющие процесс написания и скорость исполнения кода.
    В общем, как мне кажется, стоит подумать в стандарте о реализации ключевого слова Casm(ассемблер из С), который бы предоставлял возможность писать платформонезависимые вставки(возможно программы) на ассемблере.(хотя обычно к моим идеям относятся негативно)
    • 0
      Небольшая поправка: Конвейерные инструкции — Операции с цепочками данных(статья)
    • 0
      Есть похожая идея. Такое решение удовлетворило бы ваши потребности? Если нет, то опишите своё предложение. После его обсуждения можно будет написать предложение в стандарт.
      • 0
        Так далеко я там не смотрел…
        Мне немного непонятно, что он имеет в виду под операциями… С функции? Если да, то это не совсем то что я хочу. Если мое предложение выразить в виде фрагмента кода, то получится следующее:
        bool operator_plus(register dx, register si){
        	unsigned char flag;
        	Casm{
        		lodsl  //перенести из указателя esi данные в eax
        		adcl ax, [dx] //сложение с учетом флага переноса
        		addl dx, 4 //инкремент второго указателя(первый - автоматически)
        		stosl //положить в edi результат
        		lahf //загрузить регистр флагов в ah
        		movb flag, ax //перебросить в переменную flag
        	}
        	return flag & 1; //если в результате суммирования возникло переполнение типа возвращаем его
        }
        

        Очень похожим способом реализовывались ассемблерные вставки в TurboС30...(1992 год выпуска)(в качестве компилятора asm тогда использовался TASM). У меня даже был опыт написания драйвера мыши под него, откуда и возник мой никнейм.
        • 0
          в Сasm-е написал не совсем правильный код, но общая идея понятна.
          Синтаксис ассемблера можно выбрать из существующих или придумать свой. Но он не должен вставляться напрямую в ассемблер, а проходить процесс трансляции в компиляторе С.
          • 0
            в Сasm-е написал не совсем правильный код, но общая идея понятна.
            Не совсем.
            Синтаксис ассемблера можно выбрать из существующих или придумать свой. Но он не должен вставляться напрямую в ассемблер, а проходить процесс трансляции в компиляторе С.
            Ну если он всё равно будет проходить через «процесс трансляции», то чем вам интринзики не угодили?

            По моему вы сейчас медленно и со скрипом изобретаете GCC'шные built'ины — всякие __builtin_clz и __builtin_ctz, __builtin_popcount и __builtin_parity, __builtin_add_overflow и __builtin_sub_overflow — они как раз спроектированы так, чтобы ложиться в одну инструкцию в процессорах где они есть и эмулироваться там, где их нет…

            А предложение выше как раз и заключается в том, чтобы выбрать некоторый набор этих интринзиков и включить в стадарт… правда оно обрывается на самом интересном месте: нет списка интринзиков, процессоров и реализуемости — а это, как бы, самое сложное, могут сотни часов уйти на штудирование мануалов, чтобы приличный набор изобразить…
            • 0
              Я отталкивался от кода автора статьи и идеи для стандарта 21 года, которую также мне он прислал. Про интринзики не знал, и поэтому буду рад если вы назовете библиотеку(и) (желательно еще код реализации), где можно найти их.
              • 0
                Вообще современный С++ в сравнении с ассемблером мне все больше напоминает недо-python(CPython) в сравнении с языком С. Да, безусловно, тебе не нужно волноваться о совместимости со всем, стандартная библиотека шаблонов предоставляет высокий уровень абстракции и т.д. Но везде нужен некий баланс, и программист сам должен решать, пожертвовать ли совместимостью с кофемолкой в угоду ускорению некоторой функции на несколько десятков процентов. А когда язык не предоставляет такой свободы выбора, это меня сильно печалит(и немного раздрожает).
                • 0
                  Для CPython есть же Cython. Аналогом могли бы как раз быть стандартные интринсики.
        • +2
          А вы не думали, как Ваше предложение скомпилируется, скажем, для процессора архитектуры MIPS, где нет флагового регистра и операции AddWithCarry? Боюсь, работать не будет
          • –4
            Какую долю на рынке современных процессоров занимают процессоры данной архитектуры?
            • +4
              Это неважно. Если C++ поддерживается на какой-то платформе, то он поддерживается полностью. Это печалит, согласен
              • +1
                Тогда отстается только написать заглушки в случае, если данная команда недоступна. Впрочем, ничего нового, так и пишут низкоуровневый системный код… Но терять в скорости исполнения из-за 1-20% процентов неподдерживающих устройств это, как мне кажется, глупо.
                • +1
                  И сколько % теряется в скорости? Оно того стоит?
                  • 0
                    Сильно зависит от кода. Можешь почитать вот эту статью. Там с помощью SIMD инструкций достигается серьезное ускорение…
                    • +1
                      Проблема в том, что это ускорение может превратиться и в замедление, если использовать какую-нибудь эмуляцию NEON'а для x86 и использовать «не те» инструкции.

                      Для примера: на ARM нет инструкции tzcnt, так что вместо неё используется rbit (разворот всего 32-битного регистра на 180 градусов) и lzcnt. А теперь представьте что у вас такое — где-нибудь во внутреннем цикле… хорошо будет только производителям кулеров. Ну ещё продавцы электроэнергии порадуются…
                      • 0
                        Эмулятор на то и эмулятор… Он гарантирует правильное исполнение, но не гарантирует скорости. Об этих интструкциях, ксати, и писал человек в предложении к стандарту.
                        • +3
                          Он гарантирует правильное исполнение, но не гарантирует скорости.
                          Но если ваш Casm «гарантирует правильное исполнение, но не гарантирует скорости», то нафиг он вообще нужен?!

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

                          Куча достаточно муторной работы. А сказать «сделайте мне хорошо» — это не предложение, а так, словоблудие…
                          • –3
                            Так нет же, эмулятор должен гарантировать правильное исполнение, а не Сasm. А если компилировать под другую платформу, то получится и другой код…
                            По сути меня вполне устроят интринзики, если компилятор умеет их превращать в одну инструкцию на поддерживающих платформах и в несколько на не поддерживающих. Также я хочу знать где они хранятся.
                            Поэтому давайте закончим бессмысленную переписку… Оставьте пару ссылок на материалы по интринзикам для других интересующихся и придем к соглашению, что Casm их эквивалент в упрощенной форме…
                            Я их также изучу(код реализации) и посмотрю, какие у меня к ним появятся замечания
                            • +2
                              По сути меня вполне устроят интринзики, если компилятор умеет их превращать в одну инструкцию на поддерживающих платформах и в несколько на не поддерживающих.
                              Примерно так gcc'шные интринзики и устроены. А вот Intel'овские и ARM'овские — не так: там если процессор инструкцию не поддерживает — то и интринзик вызвать нельзя.

                              Также я хочу знать где они хранятся.
                              Что значит «где хранятся»? В исходниках компилятора и хранятся. К примеру __builtin_popcount. Вот тут в LLVM, здесь — в GCC. Я тут вот — табличка для старых процессоров.

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

                              А материалы… Википедия не устроит? Не думаю, что есть что-то более структурированное.
                    • 0
                      А при чем тут SIMD?
                      SIMD в удобных случаях компиляторы уже научились использовать.

                      Я о приросте конкретной вашей операции — сложение с переносом — прежде чем предлагать, нужно оценить выгоду, и в каких случаях она достигается.

                      Иначе это не предложение к Стандарту а просто ППР.
                      • 0
                        Я о приросте конкретной вашей операции — сложение с переносом — прежде чем предлагать, нужно оценить выгоду, и в каких случаях она достигается.
                        Сложение с переносом ещё так себе (можно выкручиваться по-разному и компиляторы это уже умеют прилично распознавать и оптимизировать).

                        А вот умножение с детектированием переполнения — это жуть: на большинстве процессоров это делается в пару команд, можно также использовать __int128 и clang/gcc сгенерят приличный код, но в «чистом» C/C++ этого никак не сделать! А количество ошибок, которые порождаются из-за этого — на миллиарды долларов, я думаю. Тут вопрос даже не просто в скорости. Просто если проверка дешевая — её будут вызывать, если дорогая — будут пытаться обойтись без неё.
                        • 0

                          Что компиляторы умеют распознавать и оптимизировать? Вот примерно такой код:


                           s.low = a.low + b.low;
                           s.hi = a.hi + b.hi + (s.low < a.low); //carry

                          никак не хочет превращаться в adc, компиляторы упорно выдают сравнение и условный переход.
                          Вот как раз умножение 64bit64bit=>128bit можно при отсутствии родного int128 записать как четыре умножения 32bit32bit=>64bit и несколько сложений, и при этом без ручного контроля переноса. Как-то так:


                          void xmul128(uint64_t &hi, uint64_t &lo, uint64_t a, uint64_t b)
                          {
                                  uint64_t x0,x1,x2,x3;
                                  const uint32_t al = (uint32_t)(a);
                                  const uint32_t ah = (uint32_t)(a >> 32);
                                  const uint32_t bl = (uint32_t)(b);
                                  const uint32_t bh = (uint32_t)(b >> 32);
                          
                                  x0 = (uint64_t)(ah) * bh; //high
                                  x1 = (uint64_t)(al) * bh; //mid1
                                  x2 = (uint64_t)(ah) * bl; //mid2
                                  x3 = (uint64_t)(al) * bl; //low
                          
                                  x2 += x3 >> 32; // no carry: max (2^32-1)^2 + 2^32-1
                          
                                  x0 += x2 >> 32;
                                  x1 += (uint32_t)(x2); // still no carry
                          
                                  hi = x0 + (x1 >> 32);
                                  lo = (x1 << 32) | (uint32_t)(x3);
                          }
                          • +2
                            Вот примерно такой код:
                             s.low = a.low + b.low;
                             s.hi = a.hi + b.hi + (s.low < a.low); //carry
                            
                            никак не хочет превращаться в adc, компиляторы упорно выдают сравнение и условный переход.
                            Это смотря какие компиляторы.

                            Полная программа
                            #include <inttypes.h>
                            
                            struct pair {
                              uint64_t low;
                              uint64_t hi;
                            };
                            
                            pair add(pair& a, pair& b) {
                             pair s;
                             s.low = a.low + b.low;
                             s.hi = a.hi + b.hi + (s.low < a.low); //carry
                             return s;
                            }

                            Сходите на godbolt и сравните. Вот что выдаёт clang:

                            add(pair&, pair&):                        # @add(pair&, pair&)
                                    movq    (%rsi), %rax
                                    movq    8(%rsi), %rdx
                                    addq    8(%rdi), %rdx
                                    addq    (%rdi), %rax
                                    adcq    $0, %rdx
                                    retq
                            


                            Вот что выдаёт gcc 4.4:
                            add(pair&, pair&):
                                    movq    (%rdi), %rax
                                    movq    8(%rsi), %rcx
                                    addq    8(%rdi), %rcx
                                    addq    (%rsi), %rax
                                    setb    %dl
                                    movzbl  %dl, %edx
                                    leaq    (%rcx,%rdx), %rdx
                                    ret
                            
                            Конечно «movzbl %dl, %edx» доставляет и setb вместо adc — не очень… но переходом нет!

                            Последние версии GCC, правда, окосели и действительно генерируют бог знает что — ну так если багрепортов нет, то никто это и не починит.

                            Вот как раз умножение 64bit64bit=>128bit можно при отсутствии родного int128 записать как четыре умножения 32bit32bit=>64bit и несколько сложений, и при этом без ручного контроля переноса.
                            Можно. Но скорость у этого будет…

                            Но я о другом. Вам приходит (снаружи) количество элементов и их размер. И вам нужно элементарно оценить размер буфера под это дело. Как? Простой контроль входных данных — а эффективно это реализовать невозможно. Бред ведь!
                            • +2
                              Последние версии GCC, правда, окосели и действительно генерируют бог знает что

                              Поигрался — gcc 6.3 при -O2 выдаёт непонятно что, а при -O1:
                              add(pair&, pair&):
                                      mov     rax, QWORD PTR [rdi]
                                      mov     rdx, QWORD PTR [rsi+8]
                                      add     rax, QWORD PTR [rsi]
                                      adc     rdx, QWORD PTR [rdi+8]
                                      ret
                              
                            • –1

                              В msvc есть _umul128(), в gcc/clang __int128. Но под 32 битные платформы всего этого нет. И там все равно надо 4 умножения, быстрее не получится.

                              • –1
                                И там все равно надо 4 умножения, быстрее не получится.
                                Не получится… что, я извиняюсь? Перемножить два 64-битных числа? Для получения младшей части, в общем-то, достаточно трёх. А для проверки на переполнение при перемножении двух 32-битных часел достаточно и одного:

                                Программа
                                #include <inttypes.h>
                                
                                bool multiply_with_overflow(uint32_t x, uint32_t y, uint32_t& result) {
                                  uint64_t extended_result = uint64_t(x) * uint64_t(y);
                                  result = extended_result;
                                  if (uint32_t(extended_result) != extended_result)
                                    return false;
                                  return true;
                                }
                                

                                Результат работы GCC
                                	.file	"test.cc"
                                	.text
                                	.p2align 4,,15
                                	.globl	_Z22multiply_with_overflowjjRj
                                	.type	_Z22multiply_with_overflowjjRj, @function
                                _Z22multiply_with_overflowjjRj:
                                .LFB4:
                                	.cfi_startproc
                                	movl	8(%esp), %eax
                                	mull	4(%esp)
                                	movl	12(%esp), %ecx
                                	testl	%edx, %edx
                                	movl	%eax, (%ecx)
                                	sete	%al
                                	ret
                                	.cfi_endproc
                                .LFE4:
                                	.size	_Z22multiply_with_overflowjjRj, .-_Z22multiply_with_overflowjjRj
                                	.ident	"GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4"
                                	.section	.note.GNU-stack,"",@progbits
                                


                                Однако, во-первых. без типа __int128 это не расширяется на 64-битные платформы, а во-вторых — код с __builtin_mul_overflow всё равно чуть-чуть эффективнее (особенно для чисел со знаком, хотя, стоит признать, на практике это чуть реже встречается).
                                • 0

                                  Не получится умножить два 64 битных числа с получением 128 бит результата, о чем собственно в самом начале было...

                • +1
                  Я вот не уверен, что вы много потеряете использовав ваш ассемблер вместо соответствующих интринзиков. Например потому уже, что в случае с интринзиками компилятор будет достаточно умным, чтобы не переносить флаги в %ah, а может просто использовать флаг переноса для следующей команды.

                  А уж при переносе на другую платформу… Практика показывает, что перенести ассемблерный код с одной платформы на другую — зачастую очень и очень дорого. Вот в вашем «псевдоассемблере»' флаги возвращаются. И что — будем считать PARITY на ARM'е? Это сожрёт весь выигрыш от эффективного «сложения с переносом»!

                  И не забудьте о том, что CARRY флаг одинаков на x86 и arm'е при сложении, но отличается при вычитании! А это, на минуточку, два самых распространённых на сегодня класса процессоров (причём arm более популярен).
                  • 0
                    Приведенный мною код ничем от интринзика для частного случая не отличается…
                    • 0
                      Отличается, ещё как отличается. Приведённых вами код оперирует операциями addl и lahf, которые, среди прочего, порождают не один, а кучу флагов. Включая, например, флаг PARITY — и как вы поддержку этого чуда на не-x86 процессорах предлагаете делать? Или если в вашем примере сделать в конце на "& 4", то всё — это уже не поддерживается?
                      • –4
                        я же сказал, что для частного случая, т.е. для процессора определенной заранее архитектуры.
                        • +2
                          Для процессора «определенной заранее архитектуры» существуют низкоуровневые языки ассемблера. И отдельные компиляторы их поддерживают в C/C++ программах. В том числе GCC позволяет это делать единообразно для всех архитектур.

                          Но тут мы, как бы, обсуждаем предложения для комитета по стандартизации. А у них всё просто: C (и C++) — языки, предназначенные для написания переносимых программ и, соответственно, ничего «для процессора определенной заранее архитектуры» в них быть не может.
            • +1
              По поводу доли на рынке: мир не ограничен x86 и десктопами. В телефонах, например, ARM. А в сетевое оборудование часто ставят MIPS. А в серверах можно и SPARC найти, правда тяжеловато. И что, на них C++ не использовать?
    • +4
      Увы, но C++-код должен компилироваться на множестве аппаратных платформ. И на многих из них нет операций типа сложения с переносом, SIMD и прочих. Поэтому сомневаюсь, что кто-то решит затащить эти операции в стандарт языка — они очень платформозависимы. А если они кому нужны на конкретной платформе, народ использует intrisincs.
      Что касается «платформонезависимых ассемблерных вставок», хотелось посмотреть, как вы себе это представляете.
      • –1
        Ну не знаю… Операция с учетом флага переноса вещь очень древняя и любой современный компьютерный процессор поддерживает ее. А если вы пишите код для другого типа устройств, то вы знаете о их конфигурации и подбираете соответсвующие команды(в крайнем случае можно проверять что доступно, как это сделано tmmintrin.h)
        Платформонезависимость ассемблера, как я уже написал выше, достигается процессом трансляции(построчный перевод нашего кода в код ассемблера) на этапе компиляции программы.
        • +2
          К сожалению я не представляю как в общем случае транслировать один ассемблер в другой. Тут проблемы начинаются с регистров. Например в AMD64 — 16 регистров общего назначения, в armv7 — тоже 16, но 32 битных, в armv8 — 31 регистр и специальный регистр из которого всегда читается 0. В ARMах все регистры общего назначения равноправны, в интелах, насколько я помню — нет. ARM не позволяет делать mov между памятью и памятью. AMD64 — позволяет. В armv7 практически любая интсрукция может быть условной, а ещё там инструкции push/pop принимают любое множество регистров (от 1 до всех 16ти). А в armv8 такой инструкции уже нет, зато есть push pair. И так далее…
          Можно очень долго перечислять разницу только между этими тремя архитектурами. А ещё есть mips, openrisc, sh, ia64, avr32, arc и т.д. А так же всякая экзотика типа DSP или машин с аппаратным стеком.
          В результате надо или разрешить в casm только подмножество общих инструкций или разрешить транслировать одну инструкцию в несколько. Но тогда можно легко вылететь за ограничение относительного JMP, например. И в большинстве случаем код транслированный из такого ассемблера будет больше и медленнее, чем код сгенерированный компилятором под целевую архитектуру.
          • 0
            А это я ещё не упоминал ABI, которых больше одной штуки практически на любой платформе. Например в armv8 регистры r0-r7 используются для передачи первых восьми параметров функции. И есть такая удобная штука как link register.
            • 0
              Ещё следует упомянуть о флагах. В x86 и amd64 поддерживается один набор флагов, в ARMv7/v8 другой, в MIPS вообще флагов нет, а целочисленное переполнение на signed сложении генерирует исключение. И семантика у операций может быть разная: например в x86 инструкция SUB устанавливает Carry Flag, если был заём. А в ARM логика противоположная, Carry Flag выставляется, если заёма не было.
          • 0

            А можно ссылку на референс, где amd64(em64t) позволяет mov память память?

            • 0
              Посмотрите документ «Intel® 64 and IA-32 Architectures Software Developer’s Manual», Volume 2, Chapter 4, раздел «4.3», описание инструкции «MOVS/MOVSB/MOVSW/MOVSD/MOVSQ—Move Data from String to String». Документ можно скачать здесь: https://software.intel.com/en-us/articles/intel-sdm
  • +1
    Хорошую вещь делаете.
    В меру свободного времени потестировал, занёс найденное в issues. Но это было очень поверхностное тестирование, далеко от того которое требуется для числовой библиотеки.
    • 0
      Большое спасибо за помощь. Все обнаруженные вами проблемы починил. Отдельное спасибо за почти 100 строк тестов =)
      Нетрудно догадаться, что фокус внимания не был нацелен на полностью корректное поведение
      Приоритеты примерно такие:
      0) полный набор методов для реализации интерфейса
      1) POD
      2) constexpr
      3) noexcept
      4) common_type
      5) корректность поведения
      6) читаемость

      Такой низкий приоритет продиктован тем, что в конечном счёте в std из этой имплементации не попадёт ничего. Главное, что примерно работающий код с заявленным интерфейсом можно написать.
      Еще раз спасибо за отклик
  • +1
    Ещё надо придумать что делать с std::abs. В лучшем случае код не скомпилируется, в худшем, компилятор приведёт к double.
    • 0
      надо предоставить перегрузки для всех мат. функций. В т.ч. abs/pow/signbit/пр., корректная работа std::complex<wide_int<...>> и пр.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка