Почему некоторые сравнения с плавающей запятой в четыре раза медленнее других?

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

Например:

>>> import timeit
>>> timeit.timeit("562949953420000.7 < 562949953421000") # run 1 million times
0.5387085462592742

Но если число с плавающей точкой или целое число становится меньше или больше на определенную величину, сравнение выполняется намного быстрее:

>>> timeit.timeit("562949953420000.7 < 562949953422000") # integer increased by 1000
0.1481498428446173
>>> timeit.timeit("562949953423001.8 < 562949953421000") # float increased by 3001.1
0.1459577925548956

Изменение оператора сравнения (например, использование ==или >вместо) не влияет на время заметным образом.

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

Очевидно, что сравнение этих значений более чем достаточно для большинства случаев использования. Мне просто любопытно, почему Python, похоже, больше борется с одними парами значений, чем с другими.

python performance floating-point cpython python-internals Алекс Райли
источник

Это то же самое в 2.7 и 3.x?

thefourtheye

Приведенные выше временные интервалы взяты из Python 3.4 - на моем компьютере с Linux под управлением 2.7 было подобное расхождение во временных параметрах (между 3 и 4 с небольшим раз медленнее).

Алекс Райли

Спасибо за интересную статью. Мне любопытно, что вдохновило вопрос - вы просто сравнивали случайное время или за этим стоит какая-то история?

Veedrac

@Veedrac: Спасибо. В этом нет ничего особенного: я рассеянно удивлялся, как быстро сравнивались числа с плавающей запятой и целые числа, рассчитывал несколько значений и замечал небольшие различия. Затем я понял, что понятия не имею, как Python смог точно сравнить числа с плавающей точкой и большие целые числа. Я потратил некоторое время, пытаясь понять источник и узнал, что является худшим случаем.

Алекс Райли

@ YvesDaoust: не те конкретные значения, нет (это было бы невероятной удачей!). Я пробовал различные пары значений и заметил меньшие различия во времени (например, сравнивая число с плавающей запятой с одинаковыми целыми числами и очень большие целые числа). Я узнал о случае 2 ^ 49 только после просмотра источника, чтобы понять, как работает сравнение. Я выбрал значения в вопросе, потому что они представили тему наиболее убедительным образом.

Алекс Райли

Комментарий в исходном коде Python для объектов с плавающей точкой подтверждает, что:

Сравнение в значительной степени кошмар

Это особенно верно при сравнении числа с плавающей точкой с целым числом, потому что, в отличие от чисел с плавающей точкой, целые числа в Python могут быть произвольно большими и всегда точными. Попытка привести целое число к числу с плавающей точкой может потерять точность и сделать сравнение неточным. Попытка привести число с плавающей точкой к целому числу также не сработает, потому что любая дробная часть будет потеряна.

Чтобы обойти эту проблему, Python выполняет серию проверок, возвращая результат, если одна из проверок прошла успешно. Он сравнивает знаки двух значений, затем, является ли целое число «слишком большим», чтобы быть с плавающей точкой, затем сравнивает показатель степени с плавающей точкой с длиной целого числа. Если все эти проверки не пройдены, необходимо создать два новых объекта Python для сравнения, чтобы получить результат.

При сравнении числа с плавающей точкой vс целым числом / длинным wв худшем случае это:

vи wимеют одинаковый знак (как положительный, так и отрицательный),
целое число wимеет достаточно мало битов, чтобы его можно было хранить в size_tтипе (обычно 32 или 64 бита),
целое число wимеет не менее 49 бит,
показатель числа с плавающей запятой vравен числу битов в w.

И это именно то, что мы имеем для значений в вопросе:

>>> import math
>>> math.frexp(562949953420000.7) # gives the float's (significand, exponent) pair
(0.9999999999976706, 49)
>>> (562949953421000).bit_length()
49

Мы видим, что 49 - это и показатель степени с плавающей точкой, и количество бит в целом числе. Оба числа являются положительными, и поэтому четыре критерия выше выполнены.

Выбор одного из значений, чтобы быть большим (или меньшим), может изменить число битов целого числа или значение показателя степени, и поэтому Python может определить результат сравнения без выполнения дорогостоящей финальной проверки.

Это специфично для реализации языка CPython.

Сравнение более подробно

float_richcompareФункция обрабатывает сравнение между двумя значениями vи w.

Ниже приведено пошаговое описание проверок, которые выполняет функция. Комментарии в источнике Python на самом деле очень полезны при попытке понять, что делает функция, поэтому я оставил их там, где это уместно. Я также суммировал эти проверки в списке внизу ответа.

Основная идея состоит в том, чтобы сопоставить объекты Питона vи wдва соответствующих двойников C, iи j, которые затем можно легко сравнить , чтобы дать правильный результат. И Python 2, и Python 3 используют для этого одни и те же идеи (первый только обрабатывает intи longпечатает отдельно).

Первое, что нужно сделать, это проверить, что vэто определенно число с плавающей точкой Python, и отобразить его на C double i. Затем функция проверяет, wявляется ли также число с плавающей запятой, и сопоставляет его с двойным Си j. Это лучший вариант для функции, поскольку все остальные проверки могут быть пропущены. Функция также проверяет, vесть ли infили nan:

static PyObject*
float_richcompare(PyObject *v, PyObject *w, int op)
{
    double i, j;
    int r = 0;
    assert(PyFloat_Check(v));       
    i = PyFloat_AS_DOUBLE(v);       

    if (PyFloat_Check(w))           
        j = PyFloat_AS_DOUBLE(w);   

    else if (!Py_IS_FINITE(i)) {
        if (PyLong_Check(w))
            j = 0.0;
        else
            goto Unimplemented;
    }

Теперь мы знаем, что если wэти проверки не пройдены, это не Python. Теперь функция проверяет, является ли она целым числом Python. Если это так, самый простой тест - извлечь знак vи знак w(вернуть, 0если ноль, -1если отрицательный, 1если положительный). Если знаки отличаются, это вся информация, необходимая для возврата результата сравнения:

    else if (PyLong_Check(w)) {
        int vsign = i == 0.0 ? 0 : i < 0.0 ? -1 : 1;
        int wsign = _PyLong_Sign(w);
        size_t nbits;
        int exponent;

        if (vsign != wsign) {
            /* Magnitudes are irrelevant -- the signs alone
             * determine the outcome.
             */
            i = (double)vsign;
            j = (double)wsign;
            goto Compare;
        }
    }

Если эта проверка не удалась, то vи wесть такой же знак.

Следующая проверка подсчитывает количество бит в целом числе w. Если в нем слишком много битов, его нельзя удерживать в виде числа с плавающей точкой, поэтому оно должно быть больше по величине, чем число с плавающей точкой v:

    nbits = _PyLong_NumBits(w);
    if (nbits == (size_t)-1 && PyErr_Occurred()) {
        /* This long is so large that size_t isn't big enough
         * to hold the # of bits.  Replace with little doubles
         * that give the same outcome -- w is so large that
         * its magnitude must exceed the magnitude of any
         * finite float.
         */
        PyErr_Clear();
        i = (double)vsign;
        assert(wsign != 0);
        j = wsign * 2.0;
        goto Compare;
    }

С другой стороны, если целое число wимеет 48 или меньше битов, оно может безопасно превратиться в двойное число Си jи сравнить:

    if (nbits <= 48) {
        j = PyLong_AsDouble(w);
        /* It's impossible that <= 48 bits overflowed. */
        assert(j != -1.0 || ! PyErr_Occurred());
        goto Compare;
    }

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

    if (nbits <= 48) {
        /* "Multiply both sides" by -1; this also swaps the
         * comparator.
         */
        i = -i;
        op = _Py_SwappedOp[op];
    }

Теперь функция смотрит на показатель степени с плавающей точкой. Напомним, что число с плавающей запятой можно записать (игнорируя знак) как значение и ^{показатель степени} * 2 и что значение и представляет число от 0,5 до 1:

    (void) frexp(i, &exponent);
    if (exponent < 0 || (size_t)exponent < nbits) {
        i = 1.0;
        j = 2.0;
        goto Compare;
    }

Это проверяет две вещи. Если показатель меньше 0, то число с плавающей точкой меньше 1 (и поэтому меньше по величине, чем любое целое число). Или, если показатель степени меньше числа битов, wто мы имеем это, v < |w|поскольку значение и ^{показатель степени} * 2 меньше 2 ^нбит .

Если эти две проверки не пройдены, функция проверяет, больше ли показатель степени, чем число бит в w. Это показывает , что мантисса * 2 ^{экспонента} больше 2 ^Nbits и так v > |w|:

    if ((size_t)exponent > nbits) {
        i = 2.0;
        j = 1.0;
        goto Compare;
    }

Если эта проверка не удалась, мы знаем, что показатель числа с плавающей запятой vравен числу битов в целом числе w.

Единственный способ сравнить два значения сейчас - это построить два новых числа Python из vи w. Идея состоит в том, чтобы отбросить дробную часть v, удвоить целую часть, а затем добавить одну. wтакже удваивается, и эти два новых объекта Python можно сравнить, чтобы получить правильное возвращаемое значение. Используя пример с небольшими значениями, 4.65 < 4будет определено сравнение (2*4)+1 == 9 < 8 == (2*4)(возвращает false).

    {
        double fracpart;
        double intpart;
        PyObject *result = NULL;
        PyObject *one = NULL;
        PyObject *vv = NULL;
        PyObject *ww = w;

        // snip

        fracpart = modf(i, &intpart); // split i (the double that v mapped to)
        vv = PyLong_FromDouble(intpart);

        // snip

        if (fracpart != 0.0) {
            /* Shift left, and or a 1 bit into vv
             * to represent the lost fraction.
             */
            PyObject *temp;

            one = PyLong_FromLong(1);

            temp = PyNumber_Lshift(ww, one); // left-shift doubles an integer
            ww = temp;

            temp = PyNumber_Lshift(vv, one);
            vv = temp;

            temp = PyNumber_Or(vv, one); // a doubled integer is even, so this adds 1
            vv = temp;
        }
        // snip
    }
}

Для краткости я пропустил дополнительную проверку ошибок и отслеживание мусора, которую должен выполнять Python при создании этих новых объектов. Излишне говорить, что это добавляет дополнительные издержки и объясняет, почему значения, выделенные в вопросе, сравниваются значительно медленнее, чем другие.

Вот сводка проверок, которые выполняются функцией сравнения.

Позвольте vбыть плавающим и бросить его как C двойник. Теперь, если wэто тоже поплавок:

Проверьте, wесть ли nanили inf. Если это так, обрабатывайте этот особый случай отдельно в зависимости от типа w.
Если нет, то сравните vи wнепосредственно по их представлениям, так как C удваивается.

Если wцелое число:

Извлечь признаки vи w. Если они разные, то мы знаем vи wразличны, и это является большей ценностью.
( Знаки одинаковые. ) Проверьте, wне слишком ли много битов, чтобы быть плавающей точкой (больше, чем size_t). Если это так, wимеет большую величину, чем v.
Проверьте, wимеет ли 48 бит или меньше. Если это так, он может быть безопасно приведен к двойному символу C, не теряя своей точности и по сравнению с v.
( wимеет более 48 бит. Теперь мы будем рассматривать его wкак положительное целое число, изменив опцию сравнения соответствующим образом. )
Рассмотрим показатель поплавка v. Если показатель отрицателен, то vменьше 1и, следовательно, меньше, чем любое положительное целое число. Иначе, если показатель степени меньше числа битов в wнем, он должен быть меньше, чем w.
Если показатель степени vбольше, чем число битов в, wто vбольше, чем w.
( Показатель степени равен числу бит в w. )
Финальная проверка. Разбить vна целые и дробные части. Удвойте целую часть и добавьте 1, чтобы компенсировать дробную часть. Теперь удвойте целое число w. Вместо этого сравните эти два новых целых числа, чтобы получить результат.

Алекс Райли
источник

Хорошо сделанные разработчики Python - большинство языковых реализаций просто решило бы проблему, сказав, что сравнения с плавающей запятой / целочисленные значения не точны.

user253751

Почему некоторые сравнения с плавающей запятой в четыре раза медленнее других?

Ответы:

Сравнение более подробно