Быстрая проверка float range на C

а ты запустил профайлер и он показал, что это затык?

я бы доверился компилятору и отложил до момента, когда это будет необходимо.

Сомневаюсь: если я не ошибаюсь, то проверка больше-меньше в ассемблерном представлении является не более, чем вычитанием с проверкой флага. Так что в примере имеем 2 вычитания и логическую операцию, что тут можно ускорить?

А никто и не говорил что ето bottleneck, просто вопрос.

Какое, нафиг, равно?

Кстати, float — гадость та еще! Можно хорошо лопухнуться, используя их в рассчетах. Но, к сожалению, на дешевых видюшках double — слишком дорогая операция, вот и приходится выкручиваться (скажем, сначала на тысячу умножил что-то, посчитал, потом разделил).

Подумал немножко, родился такой высер:

in_range = (a - min) * (max - a) >= 0

Но это 1) медленней 2) скорее всего работает не всегда правильно, ибо я почти сплю

Кстати, float — гадость та еще! Можно хорошо лопухнуться, используя их в рассчетах. Но, к сожалению, на дешевых видюшках double — слишком дорогая операция, вот и приходится выкручиваться (скажем, сначала на тысячу умножил что-то, посчитал, потом разделил).

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

А есть ли еще быстрые способы проверки нахождения числа в диапазоне?

для одного числа есть только непереносимые говнокостыли.

Например можно проверить порядок числа(это целое число размером 1 байт), если порядок больше, то число больше (если ++, если — то наоборот). Ну очевидно, что 12345 > 546, для любых цифр. Вот только не факт, что перевод float → char будет дешевле. Также далеко не факт, что сравнение char быстрее.

А вот если чисел много, то можно что-то придумать.

Зато флоаты считаются быстрее.

float — гадость та еще!

сколько можно говорить, что у тебя руки из жопы? Освежи в памяти «приближённые вычисления».

Какое, нафиг, равно?

какая нафиг разница, < или <= ?

Но это 1) медленней

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

скорее всего работает не всегда правильно

не, правильно. Если потерь точности не будет конечно. Тут ты используешь параболу. (x-x₀)(x-x₁)==x²-x(x₀+x₁)+x₀x₁, она всегда рогами вверх, и всегда пересекает y==0 в двух точках x₀;x₁, причём между ними она всегда отрицательная(т.к. рогами вверх).

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

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

Например можно проверить порядок числа(это целое число размером 1 байт), если порядок больше, то число больше (если ++, если — то наоборот). Ну очевидно, что 12345 > 546, для любых цифр. Вот только не факт, что перевод float → char будет дешевле. Также далеко не факт, что сравнение char быстрее.

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

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

там порядок через задницу храниться. http://en.wikipedia.org/wiki/Single_precision т.ч. не получится. Если мне память не изменяет.

Ну и да, кто тебе сказал, что в amd64 вычитание float медленнее? А в x86 точно быстрее, ибо пока ты выдернешь float из FPU пройдёт куча времени.

Да вот почитал и что-то не вижу пока особой проблемы. Но настаивать не буду.

Ну и таки да, FPU вполне шустро работает. Для той же CUDA где то видел цифры, для одинарной точности int быстрее, чем float на какие-нибудь 10-20% или около того.

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

(скажем, сначала на тысячу умножил что-то,

посчитал, потом разделил)

А чем это поможет? Точность то от этого не изменится, это же не int.

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

Однако, иногда проще умножить сначала, а потом разделить. Вот, скажем, для вычисления значения [latex]\frac{a_0+b\cdot(a_1+a_2)}{c}[/latex], когда a малы, если не домножить a и c на ~1000, то ничего не получится (т.к. b в числителе практически не изменит значения в скобочках).

Порядок там (IEEE 754) хранится в старших разрядах, так что можно сравнивать битовое представление как целые числа. Только с отрицательными надо быть внимательным, там зависимость идёт обратная.

#include <stdio.h>
#include <stdlib.h>

#define LEN 100
int main() {
	int i;
	for (i = 0; i < LEN; i++) {
		float xfloat = i - LEN / 2 + rand() * 1.0 / RAND_MAX;
		int xint = *(int*)&xfloat;
		printf("%0.9f <-> %d\n", xfloat, xint);
	}
	return 0;
}

не вижу пока особой проблемы.

проблем две:

1. знак числа оторван от мантиссы. Потому отрицательные числа с тем же порядком сравниваются наоборот, а разными порядками правильно. Т.е. всё равно нужно проверять знаки, и если - -, то необходимо фильтровать порядок, и сравнивать по частям.

2. всё было-бы хорошо, если бы порядок был-бы записан as is. Но там ещё смещение есть. В аппаратной реализации это не имеет значения(всё равно числа денормализуются перед вычитанием), но без денормализации получается ерунда, если одно число много меньше(больше) другого.

Ну а главное: не факт, что это вообще будет быстрее с учётом перевода в int. Уверен, что для 80% CPU это будет медленнее.

Ну и таки да, FPU

забудь. НЕТУ никакого FPU, все юзают SSE для float'ов(начиная с третьего пня) и double(начиная с четвёртого). Если не веришь, посмотри код, который выдаёт твой компилятор.

А чем это поможет? Точность то от этого не изменится, это же не int.

это поможет от антипереполнения. См http://ru.wikipedia.org/wiki/Антипереполнение

ЗЫЖ к сожалению, не всегда это возможно.

Логика подсказывает, что даже если ты оперируешь числами порядка FLT_EPSILON, можно просто скобочками приоритет операций проставить

это логика. А вот стандарт C «радует» тем, что порядок действий между точками следования неопределён. Т.е. a*(b*c) может вычисляться как (a*b)*c. Только не путай с a*(b+c), тут компилятор может разве что считать как a*b+a*c, но вряд-ли это выгодно, если только b или c константы. Т.е. ты должен писать t=b*c; a*t;, в этом случае есть точка следования между операциями.

тут у тебя порядок почти один и тот же. Потому и работает.

Ну и да, а кто сказал, что все числа положительны?

Кстати, 0<x, если x<0 ☺

и -0>x, если x>0

ну про NaN и INF ты сам догадаешься...

НЕТУ никакого FPU, все юзают SSE для float'ов(начиная с третьего пня) и double(начиная с четвёртого)

Ребята из AMD тоже так думали.

Ребята из AMD тоже так думали.

и что там в вашем AMD случилось?

забудь. НЕТУ никакого FPU, все юзают SSE для float'ов(начиная с третьего пня) и double(начиная с четвёртого). Если не веришь, посмотри код, который выдаёт твой компилятор.

$ cat q.c
#include <stdio.h>

int main(void)
{
	float a = 3.14159;
	float b = a * 2;
	printf("%f %f\n", a, b);
	return 0;
}
$ gcc -c q.c
$ objdump -d q.o

q.o:     формат файла elf32-i386


Дизассемблирование раздела .text:

00000000 <main>:
   0:	55                   	push   %ebp
   1:	89 e5                	mov    %esp,%ebp
   3:	83 e4 f0             	and    $0xfffffff0,%esp
   6:	83 ec 30             	sub    $0x30,%esp
   9:	a1 08 00 00 00       	mov    0x8,%eax
   e:	89 44 24 2c          	mov    %eax,0x2c(%esp)
  12:	d9 44 24 2c          	flds   0x2c(%esp)
  16:	d8 c0                	fadd   %st(0),%st
  18:	d9 5c 24 28          	fstps  0x28(%esp)
  1c:	d9 44 24 28          	flds   0x28(%esp)
  20:	d9 44 24 2c          	flds   0x2c(%esp)
  24:	d9 c9                	fxch   %st(1)
  26:	dd 5c 24 0c          	fstpl  0xc(%esp)
  2a:	dd 5c 24 04          	fstpl  0x4(%esp)
  2e:	c7 04 24 00 00 00 00 	movl   $0x0,(%esp)
  35:	e8 fc ff ff ff       	call   36 <main+0x36>
  3a:	b8 00 00 00 00       	mov    $0x0,%eax
  3f:	c9                   	leave  
  40:	c3                   	ret    
$ 

Опаньки, FPU!

elf32-i386

Опаньки, FPU!

я думал x86 остался только в моём говнонетбуке образца 2009го года... Сочувствую тебе, брат некромант(некрофил?).

если серьёзно, то ТС просил «быстро». Согласись, что начиная с третьего пня «быстро» == SSE. А твой компилятор очевидно генерит код, совместимый с i80486, когда никакого SSE не было.

Это во первых. Во вторых, о чём ты говоришь, если у тебя на всю программу ОДНА операция?

Если собрался тестировать, то

1. посчитай вектор из Over9000 float'ов

2. объясни своему компилятору, что у тебя НЕ i80486.

я думал

О, урок демагогии от мастера! Из всего разнообразия надо выбрать одно и с умным видом заявить, что ничего другого не существует.

если серьёзно, то ТС просил «быстро». Согласись, что начиная с третьего пня «быстро» == SSE

объясни своему компилятору, что у тебя НЕ i80486.

Океюшки.

$ gcc -c -march=native q.c
$ objdump -d q.o

q.o:     формат файла elf64-x86-64


Дизассемблирование раздела .text:

0000000000000000 <main>:
   0:	55                   	push   %rbp
   1:	48 89 e5             	mov    %rsp,%rbp
   4:	48 83 ec 10          	sub    $0x10,%rsp
   8:	8b 05 00 00 00 00    	mov    0x0(%rip),%eax        # e <main+0xe>
   e:	89 45 fc             	mov    %eax,-0x4(%rbp)
  11:	8b 45 fc             	mov    -0x4(%rbp),%eax
  14:	c5 f9 6e d8          	vmovd  %eax,%xmm3
  18:	c5 e2 58 d3          	vaddss %xmm3,%xmm3,%xmm2
  1c:	c5 f9 7e d0          	vmovd  %xmm2,%eax
  20:	89 45 f8             	mov    %eax,-0x8(%rbp)
  23:	c5 fa 10 65 f8       	vmovss -0x8(%rbp),%xmm4
  28:	c5 f8 5a e4          	vcvtps2pd %xmm4,%xmm4
  2c:	c4 e1 f9 7e e2       	vmovq  %xmm4,%rdx
  31:	c5 fa 10 6d fc       	vmovss -0x4(%rbp),%xmm5
  36:	c5 f8 5a ed          	vcvtps2pd %xmm5,%xmm5
  3a:	c4 e1 f9 7e e8       	vmovq  %xmm5,%rax
  3f:	c4 e1 f9 6e ca       	vmovq  %rdx,%xmm1
  44:	c4 e1 f9 6e c0       	vmovq  %rax,%xmm0
  49:	bf 00 00 00 00       	mov    $0x0,%edi
  4e:	b8 02 00 00 00       	mov    $0x2,%eax
  53:	e8 00 00 00 00       	callq  58 <main+0x58>
  58:	b8 00 00 00 00       	mov    $0x0,%eax
  5d:	c9                   	leaveq 
  5e:	c3                   	retq 

Опаньки, AVX. А Главный Демагог говорил, что должно быть SSE.

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

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

Ну так-то от 0 до 50 разница минимум 5 двоичных порядков.

Про 0<x не понял.

Если не убедительно, попробуй такой код.

C INFINITY и -INFINITY тоже норм работает. И зачем сравнивать NAN?

AVX

должно быть SSE

Ну толсто же

Опаньки, AVX. А Главный Демагог говорил, что должно быть SSE.

погугли, что такое AVX пожалуйста.

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

и кому нужны «сравнения сами по себе»? А как реализовать ленивое && без ветвления?

a*(b*c) может вычисляться как (a*b)*c.

Щито?! А «a*(b+c)» может вычисляться как «a*b + a*c»? Ведь порядок действий не определен, и по-твоему выходит, что компилятор может свободно приводить выражения от одного вида к другому. Бред же.

Ну так-то от 0 до 50 разница минимум 5 двоичных порядков.

5 единиц это немного.

Про 0<x не понял.

а, ну да, тут я не прав.

Если не убедительно

ладно, убедил. Осталось решить что делать с отрицательными, и доказать, что это действительно быстрее.

И зачем сравнивать NAN?

потому что должно получится NaN.

PS: всё равно это говнокод.

что такое AVX

Не юли. Если SSE отличается от FPU, то и AVX отличается от SSE.

Щито?! А «a*(b+c)» может вычисляться как «a*b + a*c»? Ведь порядок действий не определен, и по-твоему выходит, что компилятор может свободно приводить выражения от одного вида к другому.

Увы, это стандарт. Сам наступал на эти грабли. Компилятор _может_ тасовать выражение между точками следования как угодно. И ему насрать на наше мнение. Да, это в принципе ни на что не зависит, кроме потери точности и говнокода с побочными эффектами.

Не юли. Если SSE отличается от FPU, то и AVX отличается от SSE.

ладно, ты опять победил. http://lurkmore.so/images/e/e1/Arguing.retarded.jpg

и кому нужны «сравнения сами по себе»?

Во-первых, есть CMOVxx, а во-вторых есть задачи, когда простого сравнения достаточно.

А как реализовать ленивое && без ветвления?

Не нужно. © buddhist

ладно, ты опять победил

Ура!

В твоем примере компилятор может вычислять a, b, и c в любом порядке (если они сами по себе являются выражениями или вызовами функций), но не может менять порядок операций в выражении a*(b*c). Более того, даже если убрать скобки и оставить только a*b*c, порядок выполнения операторов все равно будет жестко определен стандартом (в данном случае это (a*b) * c).
Перечитай стандарт еще раз, только на этот раз внимательно.

А как реализовать ленивое && без ветвления?

Не нужно.

в первом посте зачем-то нужно.

Перечитай стандарт еще раз, только на этот раз внимательно.

в каком конкретно месте это сказано? Если ты утверждаешь «определено», так и ткни меня туда носом.

В твоем примере компилятор может вычислять a, b, и c в любом порядке (если они сами по себе являются выражениями или вызовами функций), но не может менять порядок операций в выражении a*(b*c).

о да. В каком порядке делать ::operator++(int) компилятор значит может решать, а вот ::operator*(int) почему-то не может. А какая разница?

А как реализовать ленивое && без ветвления?

Не нужно.

в первом посте зачем-то нужно.

И где там написано, что оператор && должен быть ленивым? Там только про скорость.

::operator++(int)

На Си. Ага. Ты неиссякаем на перлы.

Ну толсто же

Можно вот это пояснить?

Блин, сколько в последнее время развелось самоуверенных недоучек.

Chapter 5: Expressions
Except where noted, the order of evaluation of operands of individual operators and subexpressions of individual expressions, and the order in which side effects take place, is unspecified.

Речь идет о порядке вычисления под-выражений и операндов, а не о перестановке операторов в одном выражении. Дальше по тексту:

The multiplicative operators *, /, and % group left-to-right.

Это значит, что в выражении a*b/c первым будет вычислено a*b, после чего результат будет разделен на c.
Ну и там в этой главе много чего еще про то, как считается выражение и что в каком порядке происходит.

Иди, почитай уже стандарт.

И где там написано, что оператор && должен быть ленивым?

а он не ленивый разве?

На Си.

опять придираешься?