Подтвердить что ты не робот

"Исправить" беззнаковое целочисленное сравнение

Таким образом, мы все знаем правила сравнения с подписью/без знака C/С++, где -1 > 2u == true, и у меня есть ситуация, когда я хочу эффективно выполнять "правильные" сравнения.

Мой вопрос, который более эффективен с учетом того, что многие архитектуры, как люди знакомы. Очевидно, что Intel и ARM имеют более высокий вес.

Дано:

int x;
unsigned int y;
if (x < y) {}

Лучше ли продвигать:

x < y  =>  (int64)x < (int64)y

или лучше выполнить 2 сравнения, то есть:

x < y  =>  (x < 0 || x < y)

Первое подразумевает расширение с нулевой протяженностью, знаком-продолжением и одну ветвь сравнения +, а последняя не требует никаких операций с расширением знака, а 2 последовательных ответвления cmp+.
Традиционная мудрость предполагает, что ветки стоят дороже, чем расширяет знак, что будет и конвейерным, но в первом случае существует разрыв между продолжениями и единственным сравнением, тогда как во втором случае я могу представить, что некоторые архитектуры могут конвейерно выполнить 2 сравнения, но затем следуют две условные ветки?

Существует еще один случай, когда значение unsigned меньше типа подписанного типа, что означает, что он может быть выполнен с единственной нулевой длиной до длины подписанного типа, а затем одно сравнение... в этом случае, предпочтительнее ли использовать версию расширения + cmp или еще предпочтительнее использовать метод сравнения 2?

Intel? РУКА? Другие? Я не уверен, есть ли здесь правильный ответ, но я хотел бы услышать, как люди берут. Низкоуровневую производительность трудно предсказать в наши дни, особенно на Intel и все чаще и чаще на ARM.

Edit:

Я должен добавить, есть одно очевидное разрешение, где типы имеют размер, равный ширине int int; в этом случае очевидно, что предпочтительным является решение с двумя сравнениями, поскольку само продвижение не может быть выполнено эффективно. Очевидно, что пример int соответствует этому условию для 32-разрядных архитектур, и вы можете перенести мысленный эксперимент на short для упражнений, применяемых к 32-разрядным платформам.

Изменить 2:

Извините, я забыл u в -1 > 2u! > _ & Л;

Изменить 3:

Я хочу изменить ситуацию, чтобы предположить, что результат сравнения является фактической ветвью, а результат НЕ возвращается как логическое. Так я бы предпочел, чтобы структура выглядела; хотя это вызывает интересную мысль о том, что существует еще один набор перестановок, когда результатом является bool vs branch.

int g;
void fun(int x, unsigned in y) { if((long long)x < (long long)y) g = 10; }
void gun(int x, unsigned in y) { if(x < 0 || x < y) g = 10; }

Это создает предполагаемую ветвь, обычно подразумеваемую, когда вы сталкиваетесь с if;)

4b9b3361

ОТВЕТЫ

Ответ 1

Хорошо, вы правильно описали ситуацию: C/С++ не имеют возможности выполнить полное сопоставление int/unsigned int с одним сравнением.

Я был бы удивлен, если продвижение к int64 было бы быстрее, чем выполнение двух сравнений. По моему опыту, компиляторы неплохо понимают, что такое подвыражение, как это, чисто (не имеет побочных эффектов) и, следовательно, нет необходимости в второй ветки. (Вы также можете явно отказаться от короткого замыкания с помощью побитового или: (x < 0) | (x < y).) Напротив, мой опыт заключается в том, что компиляторы, как правило, не делают особого оптимиза-ции для целых чисел больше, чем размер родного слова, поэтому (int64)x < (int64)y, скорее всего, действительно выполнит полное сравнение int.

В нижней строке нет никаких заклинаний, которые гарантируют получение наилучшего машинного кода на любом процессоре, но для наиболее распространенных компиляторов на наиболее распространенных процессорах я бы предположил, что форма двух сравнений будет не медленнее, чем promotion-to-int64.

РЕДАКТИРОВАТЬ: Некоторые ошибки в Godbolt подтверждают, что на ARM32 GCC ставит слишком много механизмов в подход int64. VC делает то же самое на x86. Однако с помощью x64 подход int64 на самом деле является одной инструкцией короче (поскольку продвижение и 64-битное сравнение тривиальны). Однако конвейерная обработка может привести к тому, что фактическая производительность будет идти в любом случае. https://godbolt.org/g/wyG4yC

Ответ 2

Вы должны судить об этом в каждом конкретном случае. Существует несколько причин, по которым подписанные типы будут использоваться в программе:

  • Потому что вам действительно нужно иметь отрицательные числа в вычислениях или выходе.
  • "Sloppy typing", что означает, что программист просто набирает int по всей своей программе, не задумываясь о нем.
  • Случайно подписанный. Запрограммированные на самом деле не нуждались в подписанных числах, но попали им случайно, либо с помощью неявных рекламных кампаний типа, либо с использованием целочисленных констант, таких как 0, который имеет тип int.

В случае 1), то арифметика должна выполняться со знаком арифметики. Затем вы должны преобразовать в наименьший возможный тип, который необходим для того, чтобы содержать максимальные ожидаемые значения.

Предположим, например, что значение может иметь диапазон от -10000 до 10000. Затем вам понадобится использовать 16-разрядный тип подписки для его представления. Правильный тип для использования тогда, независимо от платформы, равен int_fast16_t.

Типы int_fastn_t и uint_fastn_t требуют, чтобы тип был как минимум равным n, но компилятору разрешено выбирать более крупный тип, если он дает более быстрый код/​​лучшее выравнивание.

2) вылечивается путем изучения stdint.h и прекращением лени. Как программист, всегда нужно учитывать размер и подпись каждой отдельной переменной, объявленной в программе. Это должно быть сделано в момент объявления. Или, если вы позже получите некоторое откровение, вернитесь и измените тип.

Если вы не будете внимательно относиться к типу, вы с абсолютной уверенностью в конце концов напишите многочисленные, часто тонкие ошибки. Это особенно важно в С++, который более придирчив к правильности текста, чем C.

Когда используется "небрежная печать", фактический предполагаемый тип чаще всего является неподписанным, а не подписанным. Рассмотрим этот неряшливый пример ввода:

for(int i=0; i<n; i++)

Нет никакого смысла использовать подписанный int здесь, так почему бы вам? Скорее всего, вы повторяете массив или контейнер, а затем правильный тип - size_t.

Или, если вы знаете максимальный размер, который может содержать n, например 100, то для этого вы можете использовать наиболее подходящий тип:

for(uint_fast8_t i=0; i<100; i++)

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

Ответ 3

Учитывая конкретную настройку, которую вы представили:

int x;
unsigned int y;

и ваше явное намерение оценить, является ли значение x численно меньше, чем значение y, соблюдая знак x, я был бы склонен записать его как

if ((x < 0) || (x < y)) {}

т.е. ваш второй вариант. Он четко выражает намерение и расширяется до более широких типов, если максимальное отображаемое значение типа y не меньше, чем максимальное отображаемое значение типа x. Таким образом, если вы согласны с тем, что аргументы будут иметь такую ​​форму, вы можете даже написать это как: предотвратить ваши глаза, приверженцы С++ - макрос.

Преобразование обоих аргументов в подписанный 64-разрядный целочисленный тип не является переносимым решением, потому что нет никакой гарантии, что на самом деле это будет поощрение от int или unsigned int. Он также не расширяется для более широких типов.

Что касается относительной производительности ваших двух альтернатив, я сомневаюсь, что есть большая разница, но если это важно для вас, тогда вы захотите написать тщательный тест. Я мог представить себе портативную альтернативу, требующую еще одной машинной инструкции, чем другая, и я также могу предположить, что она требует меньше. Только если такие сравнения доминируют над производительностью вашего приложения, одна команда сделает заметную разницу так или иначе.

Конечно, это характерно для ситуации, которую вы представили. Если вы хотите обрабатывать смешанные сопоставленные/неподписанные сравнения в любом порядке, для разных типов, которые были отсортированы во время компиляции, тогда обертка на основе шаблонов может помочь вам в этом (и это вызовет вопрос об использовании макроса) но я заставляю вас конкретно задавать детали самого сравнения.

Ответ 4

Две ветки версии будут, конечно, медленнее, но на самом деле ни одна из них не является двумя ветвями... ни одной ветки... на x86.

Например, x86 gcc 7.1 для источника С++:

bool compare(int x, unsigned int y) {
    return (x < y); // "wrong" (will emit warning)
}

bool compare2(int x, unsigned int y) {
    return (x < 0 || static_cast<unsigned int>(x) < y);
}

bool compare3(int x, unsigned int y) {
    return static_cast<long long>(x) < static_cast<long long>(y);
}

Создайте эту сборку (демонстрационная версия godbolt):

compare(int, unsigned int):
        cmp     edi, esi
        setb    al
        ret

compare2(int, unsigned int):
        mov     edx, edi
        shr     edx, 31
        cmp     edi, esi
        setb    al
        or      eax, edx
        ret

compare3(int, unsigned int):
        movsx   rdi, edi
        mov     esi, esi
        cmp     rdi, rsi
        setl    al
        ret

И если вы попытаетесь использовать их внутри более сложного кода, они будут включены в 99% случаев. Без профилирования это просто догадывается, но "по кишке" я бы пошел с compare3 как "быстрее", особенно когда он был выполнен не в порядке внутри некоторого кода (что-то вроде смешного, он делает правильную 32- > 64-кампанию даже для аргумента uint, в то время как для создания кодовых звонков, которые сравниваются с некоторым беспорядком в верхнем 32b esi..., это потребует немалых усилий, но, вероятно, он избавится от него, когда он будет сконфигурирован в более сложном вычислении, где он отметил бы, что аргумент также uint64 уже расширен, поэтому compare3 тогда еще проще + короче).

... как я сказал в комментарии, я не сталкиваюсь с задачами, где мне это нужно, например, я не могу себе представить, чтобы работать над чем-то, где действительный диапазон данных неизвестен, поэтому для задачи, над которой я работаю C/С++ идеально подходит, и я точно понимаю, как это работает (что < для подписанных vs неподписанных типов хорошо определено и приводит к кратчайшему/самому быстрому коду, а также предупреждает об ошибке, чтобы сделать меня программистом, ответственным за его проверку, и в случае необходимости соответствующим образом изменить источник).

Ответ 5

Один переносимый трюк, который вы можете сделать, - проверить, можете ли вы расширить оба аргумента до intmax_t от <stdint.h>, который является самым широким интегральным типом, поддерживаемым реализацией. Вы можете проверить (sizeof(intmax_t) > sizeof(x) && sizeof(intmax_t) >= sizeof(y)) и, если да, сделать расширенное преобразование. Это работает в очень распространенном случае, когда int имеет ширину 32 бит, а long long int - 64 бит.

В С++ вы можете делать умные вещи, где у вас есть шаблон безопасного сравнения, который проверяет std::numeric_limits<T> на его аргументы. Вот одна версия. (Скомпилируйте с -Wno-sign-compare на gcc или clang!)

#include <cassert>
#include <cstdint>
#include <limits>

using std::intmax_t;
using std::uintmax_t;

template<typename T, typename U>
  inline bool safe_gt( T x, U y ) {
    constexpr auto tinfo = std::numeric_limits<T>();
    constexpr auto uinfo = std::numeric_limits<U>();
    constexpr auto maxinfo = std::numeric_limits<intmax_t>();

    static_assert(tinfo.is_integer, "");
    static_assert(uinfo.is_integer, "");

    if ( tinfo.is_signed == uinfo.is_signed )
      return x > y;
    else if ( maxinfo.max() >= tinfo.max() &&
              maxinfo.max() >= uinfo.max() )
      return static_cast<intmax_t>(x) > static_cast<intmax_t>(y);
    else if (tinfo.is_signed) // x is signed, y unsigned.
      return x > 0 && x > y;
    else // y is signed, x unsigned.
      return y < 0 || x > y;      
  }

int main()
{
  assert(-2 > 1U);
  assert(!safe_gt(-2, 1U));
  assert(safe_gt(1U, -2));
  assert(safe_gt(1UL, -2L));
  assert(safe_gt(1ULL, -2LL));
  assert(safe_gt(1ULL, -2));
}

Он может быть проинформирован о с плавающей запятой, изменив две строки.

Ответ 6

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

#include<iostream>
#include<cassert>


template<class T> auto make_unsigned(T i) -> T { return i; }

auto make_unsigned(int i) -> unsigned int {
    assert(i >= 0);
    return static_cast<unsigned int>(i);
}

auto make_unsigned(short i) -> unsigned short {
    assert(i >= 0);
    return static_cast<unsigned short>(i);
}

auto make_unsigned(long long i) -> unsigned long long {
    assert(i >= 0);
    return static_cast<unsigned long long>(i);
}

template<
        class I1,
        class I2,
        std::enable_if_t<(std::is_signed<I1>::value and std::is_signed<I2>::value)
                         or (not std::is_signed<I1>::value and not std::is_signed<I2>::value)>* = nullptr
>
bool unsigned_less(I1 i1, I2 i2) {

    return i1 < i2;
};

template<
        class I1,
        class I2,
        std::enable_if_t<std::is_signed<I1>::value and not std::is_signed<I2>::value>* = nullptr
>
bool unsigned_less(I1 i1, I2 i2) {

    return (i1 < 0) or make_unsigned(i1) < i2;
};

template<
        class I1,
        class I2,
        std::enable_if_t<not std::is_signed<I1>::value and std::is_signed<I2>::value>* = nullptr
>
bool unsigned_less(I1 i1, I2 i2) {

    return not (i2 < 0) and i1 < make_unsigned(i2);
};



int main() {

    short a = 1;
    unsigned int b = 2;

    std::cout << unsigned_less(a, b) << std::endl;

    using uint = unsigned int;
    using ushort = unsigned short;
    std::cout << unsigned_less(ushort(1), int(3)) << std::endl;

    std::cout << unsigned_less(int(-1), uint(0)) << std::endl;
    std::cout << unsigned_less(int(1), uint(0)) << std::endl;

    return 0;
}

Ответ 7

Взгляните на выражение Андрея Александрескуса на недавней конференции D в Берлине по дизайну Интроспекции.

В нем он показывает, как создать проверенный класс int во время DESIGN, и одна из особенностей, которые он придумал, - это именно то, как сравнивать подписанные и неподписанные.

В принципе вам нужно выполнить 2 сравнения

Если (signed_var < 0), то верните unsigned_var иначе продвигайте/отмените signed_var на unsigned_var, а затем сравните