Comparison to infinity when checking if a point is above a line

Question

I have a function that is being called in a tight loop. I've profiled my code and this is where my largest bottleneck is. The function is fairly simple: it checks if a point in (x,y) form is above a line in (slope, intercept) form.

The problem is, it also has to deal with the case where the slope is positive infinity, and the intercept gives the x-intercept. In this case, the function should return True if the point is to the right of the line.

Here's the function written out how it was when I noticed the bottleneck:

def point_over(point, line):
    """Return true if the point is above the line.
    """
    slope, intercept = line
    if slope != float("inf"):
        return point[0] * slope + intercept < point[1]
    else:
        return point[0] > intercept

On my machine, this is how fast it runs:

>>> timeit("point_over((2.412412,3.123213), (-1.1234,9.1234))", 
           "from __main__ import point_over", number = 1000000)
1.116534522825532

Since this function is being called a lot, I've inlined it to avoid the function call overhead. The inlined version is fairly simple:

point[0] * line[0] + line[1] < point[1] if line[0] != float('inf') else point[0] > line[1]

And performs similarly in timeit:

>>> timeit("point[0] * line[0] + line[1] < point[1] if line[0] != float('inf') else point[0] > line[1]", 
           "point, line = ((2.412412,3.123213), (-1.1234,9.1234))", number = 1000000)
0.9410096389594945

However, this one line of code is still hogging the largest proportion of execution time in my code, even after being inlined.

Why does the comparison to float('inf') take longer than a number of calculations as well as a comparison? Is there any way to make this faster?

As an example of what I'm claiming, here are the speeds of two parts of my ternary statement separated and timed:

>>> timeit("line[0] != float('inf')", 
           "point, line = ((2.412412,3.123213), (-1.1234,9.1234))", number = 1000000)
0.528602410095175
>>> timeit("point[0] * line[0] + line[1] < point[1]", 
           "point, line = ((2.412412,3.123213), (-1.1234,9.1234))", number = 1000000)
0.48756339706397966

My primary question is why it takes so long to do the comparison to infinity. Secondary is any tips on how to speed these up. Ideally there exists some magical (even if incredibly hacky) way to half the execution time of this line, without dropping down to C. Otherwise, tell me I need to drop down to C.

Answer 1

It would be faster to use the math.isinf() function:

>>> from math import e, pi, isinf
>>> s = [0, float('inf'), e, pi]
>>> map(isinf, s)
[False, True, False, False]

The reason your current check is taking so long is due to how much work it has to do:

>>> from dis import dis

>>> def my_isinf(f):
        return f == float('Inf')

>>> dis(my_isinf)
  2           0 LOAD_FAST                0 (f)
              3 LOAD_GLOBAL              0 (float)
              6 LOAD_CONST               1 ('Inf')
              9 CALL_FUNCTION            1
             12 COMPARE_OP               2 (==)
             15 RETURN_VALUE 

There is a global load which involves a dictionary lookup. There is a two-arguments function call. The Float constructor has to parse the string and then allocate (and refcount) a new float object in memory. Then the comparison step dispatches its work to float.__eq__ which returns a boolean value which is then the fed to the if-statement.

Answer 2

Others have mentioned math.isinf(). But this'll probably be faster since it avoids a name lookup and a function call:

def point_over(point, line, infinity=float("inf")):
    slope, intercept = line
    if slope == infinity:
        return point[0] > intercept
    return point[0] * slope + intercept < point[1]

Basically, instead of evaluating float("inf") each time the function is called, you evaluate it once at function definition time and store it in a local variable, by declaring it as an argument default. (Local variables are faster to access than globals.)

Answer 3

The slow part of if slope != float("inf") is no doubt converting the string to a float. It would be simpler to just use if not math.isinf(slope) instead. Of course, you must import math for that to work.

Answer 4

It'll be even faster (by avoiding function calls altogether) if you cache the value of float("inf") in a variable:

>>> def floatcall():
...     return 1.0 == float("inf")
... 
>>> def mathcall():
...     return math.isinf(1.0)
... 
>>> inf = float("inf")
>>> def nocall():
...     return 1.0 == inf
... 
>>> timeit.timeit("floatcall()", "from __main__ import floatcall", number=1000000)
0.37178993225097656
>>> timeit.timeit("mathcall()", "import math; from __main__ import math call", number=1000000)
0.22630906105041504
>>> timeit.timeit("nocall()", "from __main__ import inf, nocall", number=1000000)
0.17772412300109863