Why is fld(a, b) so much slower than floor(a / b)?

General Usage
1

I am using mod in a hot loop and I wondered why it is taking so much time.
When I implemented mod myself with

mod_fast(a, b) = a - b * floor(a / b)

I found out it was a lot faster:

julia> @btime mod_fast($(Ref(1232.23))[], 1023)
  2.298 ns (0 allocations: 0 bytes)
209.23000000000002
julia> @btime mod($(Ref(1232.23))[], 1023)
  8.325 ns (0 allocations: 0 bytes)
209.23000000000002

The documentation says that fld is used instead of floor. And this is indeed makes a lot of difference:

julia> @btime floor($(Ref(1232.23))[] / 1023)
  1.888 ns (0 allocations: 0 bytes)
1.0
julia> @btime fld($(Ref(1232.23))[], 1023)
  8.911 ns (0 allocations: 0 bytes)
1.0

So what is the exact difference?
Is it save to use my mod function?

1 Like
2

You can follow whats going on with which:

julia> which(fld,(Float64,Int))
fld(x::Real, y::Real) in Base at promotion.jl:355

which is:

fld(x::Real, y::Real) = fld(promote(x,y)...)

You get:

julia> which(fld,(Float64,Float64))
fld(x::T, y::T) where T<:Real in Base at operators.jl:701

which is:

fld(x::T, y::T) where {T<:Real} = convert(T,round((x-mod(x,y))/y))

On the other hand:

julia> which(floor,(Float64,))
floor(x::Real) in Base at floatfuncs.jl:152

which is just:

floor(x::Real; kwargs...) = round(x, RoundDown; kwargs...)

I am not sure it this is enough to explain the differences in performance.

3

Edit: Never mind, my reading skills are too limited.

fld does integer division. This tends to be slower than floating point division these days.

For your use case it may very well be, but not for the full range of the arguments.

julia> mod(typemax(Int), typemax(Int) - 1)
1

julia> mod_fast(typemax(Int), typemax(Int) - 1)
0.0
5 Likes
4

To answer the actually asked question, i.e. the floating point case.

What happens exactly can be traced down the call chain as already shown. The difference mostly boils down to attention to rounding and cancellation issues.

That depends on how sensitive your code is to getting a result out of range.

julia> mod_fast(prevfloat(12.3), 1.23)
-1.7763568394002505e-15

julia> mod(prevfloat(12.3), 1.23)
1.229999999999999
2 Likes
5

It seems, defining your own mod function is not a bad idea, e.g. using the built-in function can give strange results:

julia> div(-7,3)
-2

julia> mod(-7,3)
2
6

What is strange about those results and what results did you expect?

7

I would expect that mod(-7,3) results in -1 but I know that this is implementation specific (or if you want depends on the mathematical definition).

-7 / 3 = -3 remainder 2

So “strange” is bad wording, lets say it may be surprising, depending on what you expect.
In this sense it is not wrong to implement it the way one wants to have it.

8

I think it is the documented behavior: from ?mod (emphasis is mine),

The reduction of x modulo y, or equivalently, the remainder of x after floored division by y, i.e. x -
y*fld(x,y) if computed without intermediate rounding.

The result will have the same sign as y, and magnitude less than abs(y) (with some exceptions, see note below).

But maybe the wording is a bit indirect — please consider making a small PR to this docstring with the example above.

9

Note that Julia agrees with C and Python. Java disagrees, and is arguably wrong since it means that fld in Java rounds to 0 instead of -Inf, which is very annoying for some purposes.

10

There are three questions here:

  1. whether the documented behavior is correct (it is),

  2. whether it could be explained a bit better (yes, and people stumbling into it are in the best position to do so),

  3. is it violating some common consensus or expectation (like 1 + 3 returning 9).

(3) is much harder to argue here as different languages have apparently different semantics. In any case, it cannot be changed before 2.0 as it would be breaking, and it is unlikely that people would want to break this, but you can always open an issue about it.

11

mathematical definition of reminder also agrees with mod (not saying math people always have the most convenient definition for programming purpose), just that in no way is this strange

If a and d are integers, with d non-zero, it can be proven that there exist unique integers q and r , such that a = qd + r and 0 ≤ r < |d| . The number q is called the quotient , while r is called the remainder .

1 Like
12

I believe you should think of modular arithmetic as something that always wraps around into the same range (0 to something). Here, it is illustrated with a clock: Modular arithmetic - Wikipedia It would be strange to not coerce time to fall into the 12-to-12 (or even better, 0-24) range.

As far as I understand, the difference in sign behaviour is exactly what distinguishes mod from rem.

1 Like