Наше серверное приложение делает много целочисленных тестов в горячем пути выполнения кода, в настоящее время мы используем следующую функцию:
inline int IsInteger(double n)
{
return n-floor(n) < 1e-8
}
Эта функция является очень горячей в нашей рабочей нагрузке, таким образом, я хочу, чтобы она была максимально быстро. Я также хочу устранить вызов библиотеки "пола", если я могу. Какие-либо предложения?
Некоторое время назад я запустил кучу таймингов на наиболее эффективном способе преобразования с плавающей точкой в целые числа и записал их. Я также использовал тайминговую технику округления .
Короткая история для вас заключается в следующем: преобразование из плавающего в int или использование взломов union вряд ли будет улучшением из-за опасностей, связанных с процессором, называемым load-hit-store -- , если только поплавки не поступают из оперативной памяти, а не из регистра.
Поскольку это свойство, абс(floor(x)-eps), вероятно, является самым быстрым решением. Но так как все это очень чувствительно к конкретной архитектуре вашего процессора -- в зависимости от очень чувствительных вещей, таких как глубина трубопровода и переадресация хранилища -- вам нужно будет время различных решений, чтобы найти одно из них, которое действительно оптимально.
Если вы действительно хотите получить хакерство, см. IEEE 754 спецификацию. Числа с плавающей точкой реализованы в виде знака и экспоненты. Я не знаю точно, как это сделать, но вы, вероятно, могли бы сделать что-нибудь вроде:
union {
float f;
unsigned int i;
}
Это дало бы вам побитовый доступ как к значению, так и к экспоненте. Тогда ты сможешь проложить себе путь.
Вот пара ответов:
#include <stdint.h>
#include <stdio.h>
#include <math.h>
int IsInteger1(double n)
{
union
{
uint64_t i;
double d;
} u;
u.d = n;
int exponent = ((u.i >> 52) & 0x7FF) - 1023;
uint64_t mantissa = (u.i & 0x000FFFFFFFFFFFFFllu);
return n == 0.0 ||
exponent >= 52 ||
(exponent >= 0 && (mantissa << (12 + exponent)) == 0);
}
int IsInteger2(double n)
{
return n - (double)(int)n == 0.0;
}
int IsInteger3(double n)
{
return n - floor(n) == 0.0;
}
И тестовый жгут:
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
int IsInteger1(double);
int IsInteger2(double);
int IsInteger3(double);
#define TIMEIT(expr, N) \
gettimeofday(&start, NULL); \
for(i = 0; i < N; i++) \
{ \
expr; \
} \
gettimeofday(&end, NULL); \
printf("%s: %f\n", #expr, (end.tv_sec - start.tv_sec) + 0.000001 * (end.tv_usec - start.tv_usec))
int main(int argc, char **argv)
{
const int N = 100000000;
struct timeval start, end;
int i;
double d = strtod(argv[1], NULL);
printf("d=%lf %d %d %d\n", d, IsInteger(d), IsInteger2(d), IsInteger3(d));
TIMEIT((void)0, N);
TIMEIT(IsInteger1(d), N);
TIMEIT(IsInteger2(d), N);
TIMEIT(IsInteger3(d), N);
return 0;
}
Скомпилируйте как:
gcc isinteger.c -O3 -c -o isinteger.o
gcc main.c isinteger.o -o isinteger
Мои результаты на Intel Core Duo:
$ ./isinteger 12345
d=12345.000000 1 1 1
(void)0: 0.357215
IsInteger1(d): 2.017716
IsInteger2(d): 1.158590
IsInteger3(d): 2.746216
Вывод: небольшое отклонение не так быстро, как я мог догадаться. Вероятно, именно лишние ветки его и убивают, несмотря на то, что это позволяет избежать операций с плавающей точкой. В наши дни FPU достаточно быстры, что делает -двойное
-к-int
преобразование или floor
действительно не так уж медленно.
Другая альтернатива:
inline int IsInteger(double n)
{
double dummy;
return modf(n, &dummy) == 0.0;
}
Если double
s на вашей машине соответствуют IEEE-754, это объединение описывает компоновку double.
union
{
double d;
struct
{
int sign :1
int exponent :11
int mantissa :52
};
} double_breakdown;
Это скажет вам, представляет ли двойник целое число.
Отказ от ответственности 1: Я говорю целое число , а не int
, поскольку дубль может представлять числа, которые являются целыми числами, но величины которых слишком велики, чтобы хранить их в int
.
Отказ от ответственности 2: Дубль будет держать максимально близкое к любому вещественному число, которое он может иметь. Таким образом, это может вернуть только то, образуют ли цифры , представленные , целое число. Крайне большие двойники, например, всегда являются целыми числами, так как они не имеют достаточно значащих цифр, чтобы представить какое-либо дробное значение.
bool is_integer( double d )
{
const int exponent_offset = 1023;
const int mantissa_bits = 52;
double_breakdown *db = &d;
// See if exponent is too large to hold a decimal value.
if ( db->exponent >= exponent_offset + mantissa_bits )
return true; // d can't represent non-integers
// See if exponent is too small to hold a magnitude greater than 1.0.
if ( db->exponent <= exponent_offset )
return false; // d can't represent integers
// Return whether any mantissa bits below the decimal point are set.
return ( db->mantissa << db->exponent - exponent_offset == 0 );
}