(Большинство) реализаций C++ предоставляют по крайней мере 8, 16, 32 и 64-битные знаковые и беззнаковые целочисленные типы. Существуют потенциально неудобные неявные преобразования, споры о неопределенном поведении при переполнении (некоторые считают, что это перебор, другие — что недобор), но по большей части эти языковые конструкции хорошо справляются с поставленными задачами. В новых языках, таких как Rust, этот замысел скопирован, но исправлены проблемы с преобразованиями и поведение при переполнении.
Тем не менее, я считаю, что здесь есть место для инноваций. Позвольте мне рассказать о трех новых семействах целочисленных типов, которые я хотел бы увидеть в C++.
Де-факто представление знаковых целых чисел на современном аппаратном уровне решается как дополнительный код (two’s complement). У положительных значений старший бит равен нулю, а у отрицательных — единице. Чтобы получить абсолютное значение отрицательного числа, инвертируйте все биты и прибавьте единицу.
Например, для 8-битного целого числа 42 — это 0b0'0101010: знаковый бит нулевой, остальные представляют 42 в двоичном формате. С другой стороны, -42 — это 0b1'1010110: если инвертировать все биты, то получится 0b0'0101001, прибавить единицу и снова 0b0'0101010, то есть, получится 42. Важно отметить, что 0b1'1111111 равно -1, а более глубокие отрицательные значения доходят до 0b1'0000000, что равно -128.
Заметили что-то интересное в последнем значении? Если вы выполните преобразование, то при инвертировании получите 0b0'1111111, а прибавление единицы приведет к 0b1'0000000 — переполнение в знаковом бите.
Это означает, что абсолютное выражение наименьшего значения больше абсолютного выражения наибольшего значения 0b0'1111111 или 127; отрицательных значений больше, чем положительных, потому что положительная половина, где бит знака не установлен, также содержит число ноль.
Мне очень не нравится эта асимметрия — она приводит к проблемным побочным явлениям во всех видах целочисленных API.
Для начала, abs(x) для целых чисел x не является тотальной функцией: abs(INT_MIN) не представима. Аналогично, x * (-1) тоже не является тотальной функцией: INT_MIN * (-1) переполняется. Еще забавнее становится в случае с делением: конечно, x / y не может переполниться, так как деление уменьшает значение, верно? Неверно, INT_MIN / (-1) переполняется (и выдает ошибку деления на ноль (!) на x86). Более того, INT_MIN % (-1) также приводит к неопределенному поведению.
Итак, вот чего я хочу: знаковое целое число, где INT_MIN == -INT_MAX, полученное путем перемещения минимального значения на единицу вверх.
Во-первых, вы не теряете ничего полезного: Я бы сказал, что дополнительное отрицательное число не имеет значения в большинстве случаев. В конце концов, если бы у вас было лишнее число, разве не логичнее было бы иметь дополнительное положительное число вместо отрицательного?
Во-вторых, вы восстанавливаете симметрию. Все операции, упомянутые выше, теперь симметричны и не могут переполняться. Так они становятся гораздо понятнее.
В-третьих, вы получаете неиспользуемый битовый паттерн 0b1'0000000, старый INT_MIN, который вы можете интерпретировать как угодно. Хотя в принципе вы можете превратить его в какой-нибудь отрицательный ноль для дополнительной симметрии, пожалуйста, не делайте этого (вместо этого просто используйте дополнение единицы или знак величины). Вместо этого мы должны скопировать другую функцию, относящуюся к арифметике с плавающей запятой: not-a-number («не число») или NaN. Назовем её INT_NAN = 0b1'0000000.
Как и NaN с плавающей запятой, INT_NAN не является допустимым целочисленным значением. В идеальном мире оно также было бы липким битом, так что INT_NAN ¤ x == INT_NAN, но для эффективной работы с ним требуется аппаратная поддержка. Вместо этого, давайте просто скажем, что арифметика на INT_NAN – это неопределенное поведение; тогда программа очистки, работая в режиме отладки, может проверить это, вставляя тестовые утверждения.
Почему я хочу INT_NAN и, таким образом, добавляю дополнительное предусловие ко всей целочисленной арифметике?
Потому что мне очень нравятся контрольные значения.
Например, с INT_NAN можно иметь sizeof(std::optional) == int. Вместо того, чтобы хранить дополнительное логическое число для отслеживания, существует ли опция, мы можем просто хранить INT_NAN. Аналогично, закрытая хэш-таблица должна каким-то образом различать пустые и непустые записи. Наличие контрольного значения позволяет обойтись без дополнительных метаданных.
Теперь вам может не понравиться, что мы решили работать с контрольным значением. Что если вы хотите хранить INT_NAN в std::optional?
Ну, INT_NAN — это не число, так почему вы хотите хранить его в int? Только если вам нужно какое-то самостоятельное значение. Это похоже на контейнер NaN для значений с плавающей запятой — вы теряете возможность хранить (большинство) NaN, но повышаете эффективность хранения. Однако, в отличие от арифметики с плавающей точкой, где, например, 0/0 может привести к NaN, в моей модели ни одна арифметическая операция над целыми числами не может привести к INT_NAN, поскольку переполнение является неопределенным поведением. Поэтому вам действительно нужно избавиться от операций присваивания INT_NAN, чтобы ввести в код целочисленные NaN.
Вам может не понравиться, что я предлагаю арифметику на INT_NAN сделать неопределенным поведением, если вы в прошлом попадали под агрессивную оптимизацию компилятора. Однако НП в стандарте само по себе не является чем-то плохим; НП буквально означает, что в стандарте не предъявляется никаких требований к поведению, что обеспечивает максимальную свободу компилятору. Можно исходить из того, что такого не происходит, выстраивая оптимизацию соответствующим образом, но также можно вставлять отладочные утверждения (либо отлавливающие все, либо обеспечивающие жесткие проверки с ложными отрицаниями), либо задать компилятору четко определенное поведение. Большинство распространённых компиляторов по умолчанию выбирают первую интерпретацию, но, например, я сейчас работаю над интерпретатором языка C, где компилятор будет выдавать панику во всех случаях неопределённого поведения.
Использование беззнаковых целочисленных типов в C++ — дело, мягко говоря, спорное. «За» такой подход возможность выразить в системе типов тот факт, что некоторая сущность не может быть отрицательной. Аргументом «против» является тот факт, что вычитание легко приводит к возникновению больших значений из-за целочисленного переполнения при нуле.
Сделаю отступление и отмечу, что это не «целочисленное переполнение через нижнюю границу». — это не выход. Преодоление минимального значения целого числа — это все равно целочисленное переполнение. Антипереполнение происходит, когда у вас есть число, которое слишком близко к нулю, чтобы быть представленным в виде плавающей точки.
Будучи сторонником беззнаковых целочисленных типов, я не могу возразить против неудобного переполнения при вычитании. Да, оно может вызывать всевозможные неприятные ошибки, начиная от переполнения буфера и заканчивая ошибками «out of memory». Переход на знаковые целые целесообразен, поскольку сильно отрицательное значение очевидно вскрывает факт ошибки. Также с такой позиции выступают многие, кто использует знаковое значение на все случаи жизни. Стыдно так делать, поскольку так вы теряете возможность выражать что-либо в системе типов.
Поскольку во многих ситуациях дополнительный бит памяти, очевидно, не нужен, я хотел бы иметь нечто, что логически является 63-битным беззнаковым целым числом, а не 64-битным. В ассемблере такая сущность представляется так же, как 64-битное знаковое целое число. Однако, если в ней когда-либо сохранится отрицательное значение, это будет неопределенным поведением. Всё точно как с булевым значением: логически это один бит, но физически он представлен как байт.
Представляется, что это равноценно знаковому целому числу с более многочисленными вариантами НП, так стоит ли этим заниматься?
Во-первых, по сравнению с int, такая сущность автоматически поставляется с предварительным условием, что число не может быть отрицательным. Во-вторых, в режиме отладки требуется меньше проверок на переполнение. Поскольку у нас широкий диапазон недопустимых значений, мы можем просто проверять значение всякий раз, когда выполняем операцию сохранения, а не после каждой арифметической операции. Конечно, программа может переполниться в промежуточном выражении, тогда затем можно отменить переполнение в последующих арифметических операциях, но это хороший компромисс между производительностью и безопасностью.
Опять же, подобная слабая отладочная проверка была бы невозможна, если бы стандарт требовал завершения программы при переполнении.
Фактически, эти беззнаковые целочисленные типы на практике в точности эквивалентны соответствующим знаковым целочисленным типам с гарантией, что число неотрицательно, когда это необходимо. Этот аспект просто встроен в систему типов и реализуется компилятором, программисту не требуется прописывать такое предусловие.
Недавно я работал над компилятором для языка, в котором различаются целочисленные типы со знаком, беззнаковые целочисленные типы и битовые целочисленные типы. Первые два семейства поддерживают только арифметические операции, и только последнее поддерживает битовые операции. Сначала я был настроен скептически, но потом мне очень понравилось это различие.
Мне всегда казалось странным, что мы относимся к целочисленному типу как к числу и выполняем над ним арифметические действия, одновременно изменяя отдельные разряды. Когда вы занимаетесь математикой, вам редко приходится оперировать отдельными цифрами! Это особенно верно для знаковых целых чисел, где знаковый бит всё портит и приводит к определенному или неопределенному поведению при операциях сдвига.
Конечно, разделение этих двух операций делает написание таких оптимизаций, как shift вместо division или bitwise and вместо modulo, более назойливым, а некоторые причудливые битовые уловки требуют больше приведений. Но, в то же время, так становится очевиднее, что именно происходит: мы начинаем рассматривать целое число как последовательность битов. Так приобретается некоторый выигрыш в производительности, но это требуется дополнительно документировать.
Когда я упомянул оптимизацию сдвига, я не имел в виду замену x / 2 на x >> 1 — это сделает компилятор. Я говорю о таких вещах, как hash % hash_table_size, где hash_table_size всегда является степенью двойки, но компилятор не может этого знать.
В то время как мы решаем эту задачу: почему мы зарезервировали так много токенов для битовых операций? Как часто нам действительно нужны |, & или ~, и стоит ли затрачивать на них целый символ, который не может быть использован ни для чего другого? Не говоря уже о том, что они имеют неправильный приоритет в C, и сами по себе не очень полезны: вам часто нужны is_bit_set(x, n), extract_bits(x, low, high) или другие операции более высокого уровня, реализованные поверх битовых операций. Я бы хотел, чтобы эти операции были переданы (встроенным) функциям стандартной библиотеки, чтобы мы могли повторно использовать операторы для чего-то другого, например, для конвейеров.
В последнее время появляется много новых языков, смежных с C++, и я бы хотел увидеть на этих языках ряд экспериментов в такой фундаментальной области, как работа с целочисленными типами.
Симметричные знаковые целые числа упрощают работу со многими фундаментальными API, а 63-битный беззнаковый size_t может сочетать лучшее из знакового и беззнакового при работе с контейнерами. Конечно, нам пока не обойтись без настоящих беззнаковых типоа в ситуациях, когда требуется дополнительный бит. Но, поскольку он удваивает диапазон, я думаю, что было бы неплохо отказаться от настоящего INT_MIN, кроме как для взаимодействия с C. Различные битовые векторы могут повысить выразительность кода, но требуемые при этом преобразования также могут доставить немало головной боли. Я бы все же хотел, чтобы кто-нибудь попробовал такие эксперименты.
Тем не менее, я считаю, что здесь есть место для инноваций. Позвольте мне рассказать о трех новых семействах целочисленных типов, которые я хотел бы увидеть в C++.
Симметричные знаковые целые числа
Де-факто представление знаковых целых чисел на современном аппаратном уровне решается как дополнительный код (two’s complement). У положительных значений старший бит равен нулю, а у отрицательных — единице. Чтобы получить абсолютное значение отрицательного числа, инвертируйте все биты и прибавьте единицу.
Например, для 8-битного целого числа 42 — это 0b0'0101010: знаковый бит нулевой, остальные представляют 42 в двоичном формате. С другой стороны, -42 — это 0b1'1010110: если инвертировать все биты, то получится 0b0'0101001, прибавить единицу и снова 0b0'0101010, то есть, получится 42. Важно отметить, что 0b1'1111111 равно -1, а более глубокие отрицательные значения доходят до 0b1'0000000, что равно -128.
Заметили что-то интересное в последнем значении? Если вы выполните преобразование, то при инвертировании получите 0b0'1111111, а прибавление единицы приведет к 0b1'0000000 — переполнение в знаковом бите.
Это означает, что абсолютное выражение наименьшего значения больше абсолютного выражения наибольшего значения 0b0'1111111 или 127; отрицательных значений больше, чем положительных, потому что положительная половина, где бит знака не установлен, также содержит число ноль.
Мне очень не нравится эта асимметрия — она приводит к проблемным побочным явлениям во всех видах целочисленных API.
Для начала, abs(x) для целых чисел x не является тотальной функцией: abs(INT_MIN) не представима. Аналогично, x * (-1) тоже не является тотальной функцией: INT_MIN * (-1) переполняется. Еще забавнее становится в случае с делением: конечно, x / y не может переполниться, так как деление уменьшает значение, верно? Неверно, INT_MIN / (-1) переполняется (и выдает ошибку деления на ноль (!) на x86). Более того, INT_MIN % (-1) также приводит к неопределенному поведению.
Итак, вот чего я хочу: знаковое целое число, где INT_MIN == -INT_MAX, полученное путем перемещения минимального значения на единицу вверх.
Во-первых, вы не теряете ничего полезного: Я бы сказал, что дополнительное отрицательное число не имеет значения в большинстве случаев. В конце концов, если бы у вас было лишнее число, разве не логичнее было бы иметь дополнительное положительное число вместо отрицательного?
Во-вторых, вы восстанавливаете симметрию. Все операции, упомянутые выше, теперь симметричны и не могут переполняться. Так они становятся гораздо понятнее.
В-третьих, вы получаете неиспользуемый битовый паттерн 0b1'0000000, старый INT_MIN, который вы можете интерпретировать как угодно. Хотя в принципе вы можете превратить его в какой-нибудь отрицательный ноль для дополнительной симметрии, пожалуйста, не делайте этого (вместо этого просто используйте дополнение единицы или знак величины). Вместо этого мы должны скопировать другую функцию, относящуюся к арифметике с плавающей запятой: not-a-number («не число») или NaN. Назовем её INT_NAN = 0b1'0000000.
Как и NaN с плавающей запятой, INT_NAN не является допустимым целочисленным значением. В идеальном мире оно также было бы липким битом, так что INT_NAN ¤ x == INT_NAN, но для эффективной работы с ним требуется аппаратная поддержка. Вместо этого, давайте просто скажем, что арифметика на INT_NAN – это неопределенное поведение; тогда программа очистки, работая в режиме отладки, может проверить это, вставляя тестовые утверждения.
Почему я хочу INT_NAN и, таким образом, добавляю дополнительное предусловие ко всей целочисленной арифметике?
Потому что мне очень нравятся контрольные значения.
Например, с INT_NAN можно иметь sizeof(std::optional) == int. Вместо того, чтобы хранить дополнительное логическое число для отслеживания, существует ли опция, мы можем просто хранить INT_NAN. Аналогично, закрытая хэш-таблица должна каким-то образом различать пустые и непустые записи. Наличие контрольного значения позволяет обойтись без дополнительных метаданных.
Теперь вам может не понравиться, что мы решили работать с контрольным значением. Что если вы хотите хранить INT_NAN в std::optional?
Ну, INT_NAN — это не число, так почему вы хотите хранить его в int? Только если вам нужно какое-то самостоятельное значение. Это похоже на контейнер NaN для значений с плавающей запятой — вы теряете возможность хранить (большинство) NaN, но повышаете эффективность хранения. Однако, в отличие от арифметики с плавающей точкой, где, например, 0/0 может привести к NaN, в моей модели ни одна арифметическая операция над целыми числами не может привести к INT_NAN, поскольку переполнение является неопределенным поведением. Поэтому вам действительно нужно избавиться от операций присваивания INT_NAN, чтобы ввести в код целочисленные NaN.
Вам может не понравиться, что я предлагаю арифметику на INT_NAN сделать неопределенным поведением, если вы в прошлом попадали под агрессивную оптимизацию компилятора. Однако НП в стандарте само по себе не является чем-то плохим; НП буквально означает, что в стандарте не предъявляется никаких требований к поведению, что обеспечивает максимальную свободу компилятору. Можно исходить из того, что такого не происходит, выстраивая оптимизацию соответствующим образом, но также можно вставлять отладочные утверждения (либо отлавливающие все, либо обеспечивающие жесткие проверки с ложными отрицаниями), либо задать компилятору четко определенное поведение. Большинство распространённых компиляторов по умолчанию выбирают первую интерпретацию, но, например, я сейчас работаю над интерпретатором языка C, где компилятор будет выдавать панику во всех случаях неопределённого поведения.
Беззнаковые целые числа без одного бита
Использование беззнаковых целочисленных типов в C++ — дело, мягко говоря, спорное. «За» такой подход возможность выразить в системе типов тот факт, что некоторая сущность не может быть отрицательной. Аргументом «против» является тот факт, что вычитание легко приводит к возникновению больших значений из-за целочисленного переполнения при нуле.
Сделаю отступление и отмечу, что это не «целочисленное переполнение через нижнюю границу». — это не выход. Преодоление минимального значения целого числа — это все равно целочисленное переполнение. Антипереполнение происходит, когда у вас есть число, которое слишком близко к нулю, чтобы быть представленным в виде плавающей точки.
Будучи сторонником беззнаковых целочисленных типов, я не могу возразить против неудобного переполнения при вычитании. Да, оно может вызывать всевозможные неприятные ошибки, начиная от переполнения буфера и заканчивая ошибками «out of memory». Переход на знаковые целые целесообразен, поскольку сильно отрицательное значение очевидно вскрывает факт ошибки. Также с такой позиции выступают многие, кто использует знаковое значение на все случаи жизни. Стыдно так делать, поскольку так вы теряете возможность выражать что-либо в системе типов.
Поскольку во многих ситуациях дополнительный бит памяти, очевидно, не нужен, я хотел бы иметь нечто, что логически является 63-битным беззнаковым целым числом, а не 64-битным. В ассемблере такая сущность представляется так же, как 64-битное знаковое целое число. Однако, если в ней когда-либо сохранится отрицательное значение, это будет неопределенным поведением. Всё точно как с булевым значением: логически это один бит, но физически он представлен как байт.
Представляется, что это равноценно знаковому целому числу с более многочисленными вариантами НП, так стоит ли этим заниматься?
Во-первых, по сравнению с int, такая сущность автоматически поставляется с предварительным условием, что число не может быть отрицательным. Во-вторых, в режиме отладки требуется меньше проверок на переполнение. Поскольку у нас широкий диапазон недопустимых значений, мы можем просто проверять значение всякий раз, когда выполняем операцию сохранения, а не после каждой арифметической операции. Конечно, программа может переполниться в промежуточном выражении, тогда затем можно отменить переполнение в последующих арифметических операциях, но это хороший компромисс между производительностью и безопасностью.
Опять же, подобная слабая отладочная проверка была бы невозможна, если бы стандарт требовал завершения программы при переполнении.
Фактически, эти беззнаковые целочисленные типы на практике в точности эквивалентны соответствующим знаковым целочисленным типам с гарантией, что число неотрицательно, когда это необходимо. Этот аспект просто встроен в систему типов и реализуется компилятором, программисту не требуется прописывать такое предусловие.
Различные битовые векторы в сравнении с целочисленным типом
Недавно я работал над компилятором для языка, в котором различаются целочисленные типы со знаком, беззнаковые целочисленные типы и битовые целочисленные типы. Первые два семейства поддерживают только арифметические операции, и только последнее поддерживает битовые операции. Сначала я был настроен скептически, но потом мне очень понравилось это различие.
Мне всегда казалось странным, что мы относимся к целочисленному типу как к числу и выполняем над ним арифметические действия, одновременно изменяя отдельные разряды. Когда вы занимаетесь математикой, вам редко приходится оперировать отдельными цифрами! Это особенно верно для знаковых целых чисел, где знаковый бит всё портит и приводит к определенному или неопределенному поведению при операциях сдвига.
Конечно, разделение этих двух операций делает написание таких оптимизаций, как shift вместо division или bitwise and вместо modulo, более назойливым, а некоторые причудливые битовые уловки требуют больше приведений. Но, в то же время, так становится очевиднее, что именно происходит: мы начинаем рассматривать целое число как последовательность битов. Так приобретается некоторый выигрыш в производительности, но это требуется дополнительно документировать.
Когда я упомянул оптимизацию сдвига, я не имел в виду замену x / 2 на x >> 1 — это сделает компилятор. Я говорю о таких вещах, как hash % hash_table_size, где hash_table_size всегда является степенью двойки, но компилятор не может этого знать.
В то время как мы решаем эту задачу: почему мы зарезервировали так много токенов для битовых операций? Как часто нам действительно нужны |, & или ~, и стоит ли затрачивать на них целый символ, который не может быть использован ни для чего другого? Не говоря уже о том, что они имеют неправильный приоритет в C, и сами по себе не очень полезны: вам часто нужны is_bit_set(x, n), extract_bits(x, low, high) или другие операции более высокого уровня, реализованные поверх битовых операций. Я бы хотел, чтобы эти операции были переданы (встроенным) функциям стандартной библиотеки, чтобы мы могли повторно использовать операторы для чего-то другого, например, для конвейеров.
Заключение
В последнее время появляется много новых языков, смежных с C++, и я бы хотел увидеть на этих языках ряд экспериментов в такой фундаментальной области, как работа с целочисленными типами.
Симметричные знаковые целые числа упрощают работу со многими фундаментальными API, а 63-битный беззнаковый size_t может сочетать лучшее из знакового и беззнакового при работе с контейнерами. Конечно, нам пока не обойтись без настоящих беззнаковых типоа в ситуациях, когда требуется дополнительный бит. Но, поскольку он удваивает диапазон, я думаю, что было бы неплохо отказаться от настоящего INT_MIN, кроме как для взаимодействия с C. Различные битовые векторы могут повысить выразительность кода, но требуемые при этом преобразования также могут доставить немало головной боли. Я бы все же хотел, чтобы кто-нибудь попробовал такие эксперименты.
