приведение удваивается к целым числам, чтобы набрать скорость - PullRequest
9 голосов
/ 12 мая 2010

в Redis (http://code.google.com/p/redis) есть оценки, связанные с элементами, чтобы отсортировать эти элементы. Эти оценки удваиваются, даже если многие пользователи на самом деле сортируют по целым числам (например, раз Unix).

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

  snprintf((char*)buf+1,sizeof(buf)-1,"%.17g",val);

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

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

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

double x = ... some value ...
if (x == (double)((long long)x))
    use_the_fast_integer_function((long long)x);
else
    use_the_slow_snprintf(x);

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

Поскольку я хотел убедиться, что в какой-то системе это не сломается, я присоединился к #c на freenode и получил много оскорблений;) Поэтому я сейчас пытаюсь здесь.

Есть ли стандартный способ сделать то, что я пытаюсь сделать, не выходя за пределы ANSI C? Иначе, должен ли вышеуказанный код работать во всех системах Posix, которые в настоящее время предназначены для Redis? То есть, арки, где сейчас работают Linux / Mac OS X / * BSD / Solaris?

То, что я могу добавить для того, чтобы сделать код более разумным, - это явная проверка диапазона double перед попыткой приведения вообще.

Спасибо за любую помощь.

Ответы [ 4 ]

6 голосов
/ 12 мая 2010

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

Еще одна мысль - запустить собственную функцию snprintf (). Преобразование из двойного в целое число изначально поддерживается многими модулями FPU, так что это должно быть молниеносно. Преобразовать это в строку также просто.

Всего несколько случайных идей для вас.

2 голосов
/ 12 мая 2010

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

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

1 голос
/ 12 мая 2010

Я не вижу проблем с приведениями, если x находится в диапазоне long long. Может быть, вы должны проверить функцию modf (), которая разделяет двойное на его целую и дробную часть. Затем вы можете добавить проверки против (двойного) LLONG_MIN и (двойного) LLONG_MAX для составной части, чтобы убедиться. Хотя могут быть трудности с точностью до двойной.

Но прежде чем что-то из этого делать, вы убедились, что это действительно узкое место, измеряя его производительность? И достаточно ли процент целочисленных значений, чтобы это действительно имело значение?

0 голосов
/ 13 мая 2010

Ваш тест в порядке (при условии, что к этому моменту вы уже обрабатывали бесконечности и NAN отдельно) - и это, вероятно, один из немногих случаев, когда вы действительно делаете хотите сравнить числа с плавающей точкой на равенство. Он не вызывает неопределенного поведения - даже если x находится за пределами диапазона long long, вы просто получите «результат, определенный реализацией», который в порядке здесь.

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

...