When does it make sense to use `Base.MultiplicativeInverses`

General Usage Performance
,
1

When does it make sense to use the Base.MultiplicativeInverses? I am considering storing the MultiplicativeInverse in my AbstractArray subtype which uses some index calculations based on some fields and the parent array. I thought that storing the MultiplicativeInverse of the numbers that I often divide by in my subtype would lead to a significant performance boost, but when I ran a quick benchmark I do not see any difference. Hence the question… When is it useful? What are some rules of thumb that I can abide by?

julia> un = rand(UInt64, 10_000);

julia> @btime div.($un, 56);
  6.620 μs (3 allocations: 78.20 KiB)

julia> using Base.MultiplicativeInverses

julia> @btime div.($un, $(MultiplicativeInverses.multiplicativeinverse(MultiplicativeInverses.unsigned(56))));
  6.530 μs (3 allocations: 78.20 KiB)
2

Right now you’re benchmarking with the constant 56. If it’s truly a constant, then that’ll probably always be equal or fastest (because LLVM does a similar transform on my platform!). Look ma, no divs:

julia> f(x) = div(x, 56)
f (generic function with 1 method)

julia> @code_native debuginfo=:none f(123123)
	.section	__TEXT,__text,regular,pure_instructions
	.build_version macos, 15, 0
	.globl	_julia_f_10054                  ; -- Begin function julia_f_10054
	.p2align	2
_julia_f_10054:                         ; @julia_f_10054
; Function Signature: f(Int64)
; %bb.0:                                ; %pass
	;DEBUG_VALUE: f:x <- $x0
	;DEBUG_VALUE: f:x <- $x0
	mov	x8, #18725
	movk	x8, #9362, lsl #16
	movk	x8, #37449, lsl #32
	movk	x8, #18724, lsl #48
	smulh	x8, x0, x8
	asr	x9, x8, #4
	add	x0, x9, x8, lsr #63
	ret
                                        ; -- End function
.subsections_via_symbols

You’d want to benchmark it without the constant propagation:

julia> @btime div.($un, 56); # constant!
  2.718 μs (3 allocations: 96.06 KiB)

julia> @btime div.($un, $(Ref(56))[]);
  6.267 μs (3 allocations: 96.06 KiB)

julia> @btime div.($un, $(Ref(MultiplicativeInverses.multiplicativeinverse(MultiplicativeInverses.unsigned(56))))[]);
  3.068 μs (3 allocations: 96.06 KiB)
2 Likes
3

So if I just store the size that I div with within the struct I would get the same result because llvm would propagate the constant is this correct?

4

It’d have to be a compile-time constant for Julia. If you’re storing it as a field in a struct, it’s definitely not a constant. If you store it as a type parameter, then it’d be a compile-time constant for type-stable code.

3 Likes
5

Is MultiplicativeInverses public? As far as I can see, it’s neither documented, nor exported nor marked public. So I don’t think it’s fit for consumption.

5 Likes
6

can’t even find it

7

FFTViews considered using it quite a while ago and it didn’t change since. I am not aware if it is used in base. Maybe in view / SubArray types.