Жила-была библиотека у меня на поддержке. Всё у неё было хорошо: собиралась под 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.
Комментарии (81)
jaiprakash
21.04.2017 16:13А почему не собирали тем же GCC?
cerevra
21.04.2017 16:15+1Надо было собирать проект в Microsoft Visual Studio 2015. Это данность, с которой пришлось жить
slonopotamus
21.04.2017 20:36+41. Внести изменение в стандарт C++ легче чем перевести приложение на другой компилятор?
2. Но даже если ваше изменение примут, оно не решает же поставленную задачу, потому что в Microsoft Visual Studio 2015 изменение никогда не появится.
Foxeed
21.04.2017 20:44+3Задача итак решена, просто не эстетично. Разговор про то, чтобы не писать велосипеды в дальнейшем.
PashaPodolsky
21.04.2017 21:44+11. Внести изменение в стандарт действительно в некоторых ситуациях может быть легче.
2. В этой версии MSVS останется велосипед, в будущих появятся изменения, всем хорошо, все довольны.slonopotamus
24.04.2017 14:14+2> всем хорошо, все довольны.
Не совсем. Негативные эффекты есть — стандарт C++ станет жирнее. А если эта фича будет добавлена в какой-нибудь популярный хедер, то ВСЕ его использующие получат пенальти на скорость компиляции, даже если им фича не нужна. Хотя фича прекрасно могла быть реализована в виде подключаемой библиотеки, без залезания в стандарт.Azoh
24.04.2017 15:19А если эта фича будет добавлена в какой-нибудь популярный хедер, то ВСЕ его использующие получат пенальти на скорость компиляции, даже если им фича не нужна
А модули не помогут? Или с высокой вероятностью их примут и реализуют уже после этой фичи?
vladon
24.04.2017 13:231. Вот есть данность: Windows и MSVC. Пусть не 2015-й, а более поздний. __uint128 в нём не появится никогда, а 128-битный тип нужен. Ваши предложения?
2. Появится в более поздникх MSVC, а в более ранних можно скомпилировать библиотеку.
f1inx
21.04.2017 16:23Если бы ребята приняли в стандарт атрибут при декларации целочисленной переменной для указания endian при ее сериализации, как это будет в стандарте для ANSI C (и уже реализовано в новых GCC), то очень много ABIшного кода можно было бы выпрямить и избежать многих ошибок.
cerevra
21.04.2017 16:37+2Это повод для еще одного предложения: https://stdcpp.ru/proposals/new =)
Kobalt_x
22.04.2017 11:33Тут не proposal нужен, а своевременная синхронизация с последним доступным стандартом C на момент принятия нового стандарта C++
cerevra
22.04.2017 12:08+1С++ обеспечивает не полную совместимость с C. Например, restrict отсутствует в С++. Поэтому нельзя ожидать, что всё, что появлется в С, должно быть тут же подхвачено в С++. Тем более, если речь идёт о том, что еще только будет в стандарте C. Если поискать здесь «From C», то видно, что что-то втягивается из C. И если есть острое желание что-то конкретное втянуть из C, то это нужно обсуждать отдельно
Kobalt_x
22.04.2017 16:04Например, restrict отсутствует в С++
Как будто это хорошо, restrict как минимум позволяет компилятору проводить более сильные оптимизации, т.к есть более сильные ограничения на область памяти. Из фич C99, которых нет в стандарте меня лично бесит designated initializers, и нет initializer list не замена, т.к надо помнить порядок полей структуры, жаль что только clang поддерживает их в std=c++11cerevra
22.04.2017 18:48Это ни хорошо, ни плохо. Так есть
khim
22.04.2017 20:06Но над этим работают! P0329R0, к примеру, будет включен в C++20. Может к концу столетия и
restrictподдержат…
Antervis
22.04.2017 21:17как много раз за вашу карьеру вы использовали __restrict/__restrict__/пр. в с++ программе и это дало хоть какой-то прирост?
khim
22.04.2017 21:36Я его не использовал — потому что он не входит в стандарт. Однако возможное ускорение заметно.
Неясно, впрочем, насколько получаемое ускорение стоит того, что можно «переборщить» и нарваться на весьма сложно отлавливаемые баги.Antervis
23.04.2017 07:48Однако возможное ускорение заметно.
возможное. Ситуаций, где restrict имеет значение, очень мало. Тем более, что c++ по стандарту считает, что указатели на разные типы не алиасятся (кроме void*/char*)splav_asv
23.04.2017 09:03+1В любой числодробилке такие ситуации есть и типы там почти всегда одинаковые.
Так что фича то нужная… хоть и не так широко.Antervis
23.04.2017 09:51Я лишь пытаюсь сказать, что для 1-2х случаев в жизни можно воспользоваться и расширениями компиляторов (если надо под разные — через define, вон, с экспортом символов из библиотек всю жизнь так делают). Если бы среднестатистический программист пользовался restrict'ом часто, он бы появился в с++ намного раньше
antoshkka
23.04.2017 12:02Над proposal на restrict сейчас работают люди занимающиеся разработкой компиляторов. Там есть много сложностей связанных с алиасингом this, алиасингами членов класса (не очень понятно как это указывать с точки зрения синтаксиса).
Авось через лет 5 появится в стандарте.
Kobalt_x
23.04.2017 10:00Ну например с ним openCL компилятор, что от amd, что от altera позволяет ускорить код где-то на 5-7%.
Kobalt_x
23.04.2017 10:18Proposal классный, если бы еще memberов с существующим default constructor можно было бы опускать то вообще бы конфетка была.
Antervis
21.04.2017 16:24В частности, комиссия всё-таки попросила в wide_int оперировать количеством машинных слов
Стандарт же вроде не определяет размер машинного слова. Как быть если надо именно int2048_t?
ilynxy
21.04.2017 20:09+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.htmlcerevra
21.04.2017 21:12Он крутой, согласен. Но он не POD, поэтому не стали тащить его в стандарт.
А в задаче не было возможности использовать boost
Siemargl
21.04.2017 20:29+2Можно делать ставки, в каком году примут стандарт с этим нововведением?
Но автор молодца — не остановился на этапе «поныть что все плохо»
Barafu
21.04.2017 20:35+5Слониха и слонёнок помогают мыши прогнать кота. Это иллюстрация работы комитета С++.
int33h
21.04.2017 21:12Я, конечно, плохо знаю, как там дела у microsoft, но для intel-овских процессоров есть даже специальная библиотека для работы с 128 разрядными числами, которая использует SIMD(tmmintrin.h, вспомнил эту статью)(может что есть и для amd).
Но допустим, что мы не хотим использовать ее и пишем собственную библиотеку на шаблонах wide_int. Тогда следующий вопрос к языку C: «В ассемблере уже много лет есть команда adc, которая складывает с учетом флага переноса, где она в С?»(Также еще можно поставить вопрос про SIMD и конвейерные инструкции). И количество таких вопросов огромно, когда мы начинаем копаться в возможностях С и ассемблера… И что самое важное, это полезные фичи ускоряющие процесс написания и скорость исполнения кода.
В общем, как мне кажется, стоит подумать в стандарте о реализации ключевого слова Casm(ассемблер из С), который бы предоставлял возможность писать платформонезависимые вставки(возможно программы) на ассемблере.(хотя обычно к моим идеям относятся негативно)cerevra
21.04.2017 21:42Есть похожая идея. Такое решение удовлетворило бы ваши потребности? Если нет, то опишите своё предложение. После его обсуждения можно будет написать предложение в стандарт.
int33h
21.04.2017 22:32Так далеко я там не смотрел…
Мне немного непонятно, что он имеет в виду под операциями… С функции? Если да, то это не совсем то что я хочу. Если мое предложение выразить в виде фрагмента кода, то получится следующее:
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). У меня даже был опыт написания драйвера мыши под него, откуда и возник мой никнейм.int33h
21.04.2017 22:40в Сasm-е написал не совсем правильный код, но общая идея понятна.
Синтаксис ассемблера можно выбрать из существующих или придумать свой. Но он не должен вставляться напрямую в ассемблер, а проходить процесс трансляции в компиляторе С.khim
22.04.2017 01:11в Сasm-е написал не совсем правильный код, но общая идея понятна.
Не совсем.
Синтаксис ассемблера можно выбрать из существующих или придумать свой. Но он не должен вставляться напрямую в ассемблер, а проходить процесс трансляции в компиляторе С.
Ну если он всё равно будет проходить через «процесс трансляции», то чем вам интринзики не угодили?
По моему вы сейчас медленно и со скрипом изобретаете GCC'шные built'ины — всякие __builtin_clz и __builtin_ctz, __builtin_popcount и __builtin_parity, __builtin_add_overflow и __builtin_sub_overflow — они как раз спроектированы так, чтобы ложиться в одну инструкцию в процессорах где они есть и эмулироваться там, где их нет…
А предложение выше как раз и заключается в том, чтобы выбрать некоторый набор этих интринзиков и включить в стадарт… правда оно обрывается на самом интересном месте: нет списка интринзиков, процессоров и реализуемости — а это, как бы, самое сложное, могут сотни часов уйти на штудирование мануалов, чтобы приличный набор изобразить…int33h
22.04.2017 03:38Я отталкивался от кода автора статьи и идеи для стандарта 21 года, которую также мне он прислал. Про интринзики не знал, и поэтому буду рад если вы назовете библиотеку(и) (желательно еще код реализации), где можно найти их.
int33h
22.04.2017 04:09Вообще современный С++ в сравнении с ассемблером мне все больше напоминает недо-python(CPython) в сравнении с языком С. Да, безусловно, тебе не нужно волноваться о совместимости со всем, стандартная библиотека шаблонов предоставляет высокий уровень абстракции и т.д. Но везде нужен некий баланс, и программист сам должен решать, пожертвовать ли совместимостью с кофемолкой в угоду ускорению некоторой функции на несколько десятков процентов. А когда язык не предоставляет такой свободы выбора, это меня сильно печалит(и немного раздрожает).
splav_asv
22.04.2017 08:24Для CPython есть же Cython. Аналогом могли бы как раз быть стандартные интринсики.
marsianin
21.04.2017 22:47+2А вы не думали, как Ваше предложение скомпилируется, скажем, для процессора архитектуры MIPS, где нет флагового регистра и операции AddWithCarry? Боюсь, работать не будет
int33h
21.04.2017 22:52-4Какую долю на рынке современных процессоров занимают процессоры данной архитектуры?
cerevra
21.04.2017 22:56+4Это неважно. Если C++ поддерживается на какой-то платформе, то он поддерживается полностью. Это печалит, согласен
int33h
21.04.2017 23:05+1Тогда отстается только написать заглушки в случае, если данная команда недоступна. Впрочем, ничего нового, так и пишут низкоуровневый системный код… Но терять в скорости исполнения из-за 1-20% процентов неподдерживающих устройств это, как мне кажется, глупо.
Siemargl
21.04.2017 23:49+1И сколько % теряется в скорости? Оно того стоит?
int33h
22.04.2017 00:32Сильно зависит от кода. Можешь почитать вот эту статью. Там с помощью SIMD инструкций достигается серьезное ускорение…
khim
22.04.2017 00:44+1Проблема в том, что это ускорение может превратиться и в замедление, если использовать какую-нибудь эмуляцию NEON'а для x86 и использовать «не те» инструкции.
Для примера: на ARM нет инструкции tzcnt, так что вместо неё используется rbit (разворот всего 32-битного регистра на 180 градусов) и lzcnt. А теперь представьте что у вас такое — где-нибудь во внутреннем цикле… хорошо будет только производителям кулеров. Ну ещё продавцы электроэнергии порадуются…int33h
22.04.2017 03:43Эмулятор на то и эмулятор… Он гарантирует правильное исполнение, но не гарантирует скорости. Об этих интструкциях, ксати, и писал человек в предложении к стандарту.
khim
22.04.2017 14:00+3Он гарантирует правильное исполнение, но не гарантирует скорости.
Но если ваш Casm «гарантирует правильное исполнение, но не гарантирует скорости», то нафиг он вообще нужен?!
Об этих интструкциях, ксати, и писал человек в предложении к стандарту.
Угу — только без статистики. Так как эти интринцики уже есть, то разумное предложение включало бы в себя список интринзиков, которые используются какими-нибудь распространённые библиотеками, далее — разбивка по процессорам (тут есть, тут нет, тут можно табличку приспособить).
Куча достаточно муторной работы. А сказать «сделайте мне хорошо» — это не предложение, а так, словоблудие…int33h
22.04.2017 14:30-3Так нет же, эмулятор должен гарантировать правильное исполнение, а не Сasm. А если компилировать под другую платформу, то получится и другой код…
По сути меня вполне устроят интринзики, если компилятор умеет их превращать в одну инструкцию на поддерживающих платформах и в несколько на не поддерживающих. Также я хочу знать где они хранятся.
Поэтому давайте закончим бессмысленную переписку… Оставьте пару ссылок на материалы по интринзикам для других интересующихся и придем к соглашению, что Casm их эквивалент в упрощенной форме…
Я их также изучу(код реализации) и посмотрю, какие у меня к ним появятся замечанияkhim
22.04.2017 19:34+2По сути меня вполне устроят интринзики, если компилятор умеет их превращать в одну инструкцию на поддерживающих платформах и в несколько на не поддерживающих.
Примерно так gcc'шные интринзики и устроены. А вот Intel'овские и ARM'овские — не так: там если процессор инструкцию не поддерживает — то и интринзик вызвать нельзя.
Также я хочу знать где они хранятся.
Что значит «где хранятся»? В исходниках компилятора и хранятся. К примеру__builtin_popcount. Вот тут в LLVM, здесь — в GCC. Я тут вот — табличка для старых процессоров.
Оставьте пару ссылок на материалы по интринзикам для других интересующихся и придем к соглашению, что Casm их эквивалент в упрощенной форме…
Casm — это их эквивалент в усложнённой форме. В случае с интринзиками — никто, кроме компилятора, не знает, что это не функции, никаких расширений в язык добавлять не нужно и ничего нигде особо обрабатывать не нужно. Если очень приспичит — можно реализовать их в виде просто библиотеки (пример — NEON'овские интринзики для x86). А что такое ваш Casm, и как его, в принципе, использовать — я думаю вы и сами не понимаете…
А материалы… Википедия не устроит? Не думаю, что есть что-то более структурированное.
Siemargl
22.04.2017 09:44А при чем тут SIMD?
SIMD в удобных случаях компиляторы уже научились использовать.
Я о приросте конкретной вашей операции — сложение с переносом — прежде чем предлагать, нужно оценить выгоду, и в каких случаях она достигается.
Иначе это не предложение к Стандарту а просто ППР.khim
22.04.2017 14:07Я о приросте конкретной вашей операции — сложение с переносом — прежде чем предлагать, нужно оценить выгоду, и в каких случаях она достигается.
Сложение с переносом ещё так себе (можно выкручиваться по-разному и компиляторы это уже умеют прилично распознавать и оптимизировать).
А вот умножение с детектированием переполнения — это жуть: на большинстве процессоров это делается в пару команд, можно также использовать __int128 и clang/gcc сгенерят приличный код, но в «чистом» C/C++ этого никак не сделать! А количество ошибок, которые порождаются из-за этого — на миллиарды долларов, я думаю. Тут вопрос даже не просто в скорости. Просто если проверка дешевая — её будут вызывать, если дорогая — будут пытаться обойтись без неё.
paluke
22.04.2017 22:26Что компиляторы умеют распознавать и оптимизировать? Вот примерно такой код:
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); }khim
22.04.2017 23:53+2Вот примерно такой код:
Это смотря какие компиляторы.
никак не хочет превращаться в adc, компиляторы упорно выдают сравнение и условный переход.s.low = a.low + b.low; s.hi = a.hi + b.hi + (s.low < a.low); //carry
Полная программа#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; }UZERE
23.04.2017 01:34+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
paluke
23.04.2017 06:38-1В msvc есть _umul128(), в gcc/clang __int128. Но под 32 битные платформы всего этого нет. И там все равно надо 4 умножения, быстрее не получится.
khim
23.04.2017 10:08-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; }paluke
23.04.2017 15:37Не получится умножить два 64 битных числа с получением 128 бит результата, о чем собственно в самом начале было...
khim
22.04.2017 00:36+1Я вот не уверен, что вы много потеряете использовав ваш ассемблер вместо соответствующих интринзиков. Например потому уже, что в случае с интринзиками компилятор будет достаточно умным, чтобы не переносить флаги в %ah, а может просто использовать флаг переноса для следующей команды.
А уж при переносе на другую платформу… Практика показывает, что перенести ассемблерный код с одной платформы на другую — зачастую очень и очень дорого. Вот в вашем «псевдоассемблере»' флаги возвращаются. И что — будем считать PARITY на ARM'е? Это сожрёт весь выигрыш от эффективного «сложения с переносом»!
И не забудьте о том, что CARRY флаг одинаков на x86 и arm'е при сложении, но отличается при вычитании! А это, на минуточку, два самых распространённых на сегодня класса процессоров (причём arm более популярен).int33h
22.04.2017 03:50Приведенный мною код ничем от интринзика для частного случая не отличается…
khim
22.04.2017 13:53Отличается, ещё как отличается. Приведённых вами код оперирует операциями addl и lahf, которые, среди прочего, порождают не один, а кучу флагов. Включая, например, флаг PARITY — и как вы поддержку этого чуда на не-x86 процессорах предлагаете делать? Или если в вашем примере сделать в конце на "& 4", то всё — это уже не поддерживается?
int33h
22.04.2017 14:17-4я же сказал, что для частного случая, т.е. для процессора определенной заранее архитектуры.
khim
22.04.2017 19:42+2Для процессора «определенной заранее архитектуры» существуют низкоуровневые языки ассемблера. И отдельные компиляторы их поддерживают в C/C++ программах. В том числе GCC позволяет это делать единообразно для всех архитектур.
Но тут мы, как бы, обсуждаем предложения для комитета по стандартизации. А у них всё просто: C (и C++) — языки, предназначенные для написания переносимых программ и, соответственно, ничего «для процессора определенной заранее архитектуры» в них быть не может.
marsianin
22.04.2017 07:30+1По поводу доли на рынке: мир не ограничен x86 и десктопами. В телефонах, например, ARM. А в сетевое оборудование часто ставят MIPS. А в серверах можно и SPARC найти, правда тяжеловато. И что, на них C++ не использовать?
marsianin
21.04.2017 22:38+4Увы, но C++-код должен компилироваться на множестве аппаратных платформ. И на многих из них нет операций типа сложения с переносом, SIMD и прочих. Поэтому сомневаюсь, что кто-то решит затащить эти операции в стандарт языка — они очень платформозависимы. А если они кому нужны на конкретной платформе, народ использует intrisincs.
Что касается «платформонезависимых ассемблерных вставок», хотелось посмотреть, как вы себе это представляете.int33h
21.04.2017 22:50-1Ну не знаю… Операция с учетом флага переноса вещь очень древняя и любой современный компьютерный процессор поддерживает ее. А если вы пишите код для другого типа устройств, то вы знаете о их конфигурации и подбираете соответсвующие команды(в крайнем случае можно проверять что доступно, как это сделано tmmintrin.h)
Платформонезависимость ассемблера, как я уже написал выше, достигается процессом трансляции(построчный перевод нашего кода в код ассемблера) на этапе компиляции программы.lorc
21.04.2017 23:06+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, например. И в большинстве случаем код транслированный из такого ассемблера будет больше и медленнее, чем код сгенерированный компилятором под целевую архитектуру.lorc
21.04.2017 23:10А это я ещё не упоминал ABI, которых больше одной штуки практически на любой платформе. Например в armv8 регистры r0-r7 используются для передачи первых восьми параметров функции. И есть такая удобная штука как link register.
marsianin
22.04.2017 07:25Ещё следует упомянуть о флагах. В x86 и amd64 поддерживается один набор флагов, в ARMv7/v8 другой, в MIPS вообще флагов нет, а целочисленное переполнение на signed сложении генерирует исключение. И семантика у операций может быть разная: например в x86 инструкция SUB устанавливает Carry Flag, если был заём. А в ARM логика противоположная, Carry Flag выставляется, если заёма не было.
Kobalt_x
23.04.2017 09:56А можно ссылку на референс, где amd64(em64t) позволяет mov память память?
marsianin
23.04.2017 12:12Посмотрите документ «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
Imp5
23.04.2017 19:07+1Хорошую вещь делаете.
В меру свободного времени потестировал, занёс найденное в issues. Но это было очень поверхностное тестирование, далеко от того которое требуется для числовой библиотеки.cerevra
23.04.2017 20:48Большое спасибо за помощь. Все обнаруженные вами проблемы починил. Отдельное спасибо за почти 100 строк тестов =)
Нетрудно догадаться, что фокус внимания не был нацелен на полностью корректное поведение
Приоритеты примерно такие:
0) полный набор методов для реализации интерфейса
1) POD
2) constexpr
3) noexcept
4) common_type
5) корректность поведения
6) читаемость
Такой низкий приоритет продиктован тем, что в конечном счёте в std из этой имплементации не попадёт ничего. Главное, что примерно работающий код с заявленным интерфейсом можно написать.
Еще раз спасибо за отклик
k06a
25.04.2017 10:22Я тут
пару лет назад(огого) 7 лет назад делал похожую штуку:
https://github.com/k06a/boolib/blob/master/boolib/util/Intx2.h
Насколько я помню только с делением возникли серьезные проблемы.
lpre
А что вам мешает использовать предложенный к стандартизации шаблон прямо сейчас — вместо класса UInt128? Заодно обкатаете свое предложение в реальном проекте? ;-)
cerevra
Имплементация делает слишком много копирований — так было проще написать код (Proof of concept). Об эффективности речи в нём нет