Simple conditional loop

[darleybarreto]

Hi folks, I have a question about ifs inside for loops. Suppose I have this function:

function c_cheating(high)
	total = 0
	high *= 2
	for i in 4:4:high
		total += i
	end
	total
end

Giving

@btime c_cheating(1_000_000)
# 1.811 ns (0 allocations: 0 bytes)
# 500001000000

And

function c_loop(high)
	total = 0
	for i in 1:high
        if i%2==0
            total += i*2
        end
	end
	total
end

Giving

@btime c_loop(1_000_000)
# 192.674 μs (0 allocations: 0 bytes)
# 500001000000

Also

@btime sum(4:4:(1_000_000*2))
# 0.022 ns (0 allocations: 0 bytes)
# 500001000000

How could I improve the last for loop, or something using generators as the later? I tried using Iterators.filter, but it was slower than c_loop.

[baggepinnen]

I think the compiler has been too smart for the two fast benchmarks and have performed the computation at compile time/ replaced the loop with the answer. Timings on the order of 1ns or less should be taken with a large grain of salt.

[lungben]

You can check with @code_llvm or @code_native the generated assembly code to see if the compiler “cheated”.
In general 200 microseconds for 1M loop iterations is not too bad (if the compiler is not able to optimize the loop away), it is still more than 1 loop iteration per CPU cycle.

[darleybarreto]

I don’t quite understand what’s happening here, but this is the output:

@code_native c_cheating(1_000_000)

	.text
; ┌ @ In[1]:3 within `c_cheating'
; │┌ @ In[1]:1 within `*'
	pushq	%rbx
; │└
; │┌ @ int.jl:87 within `*'
	leaq	(%rdi,%rdi), %rdx
; │└
; │ @ In[1]:4 within `c_cheating'
; │┌ @ range.jl:22 within `Colon'
; ││┌ @ range.jl:24 within `_colon'
; │││┌ @ range.jl:256 within `StepRange' @ range.jl:205
	movabsq	$steprange_last, %rax
	movl	$4, %ebx
	movl	$4, %edi
	movl	$4, %esi
	callq	*%rax
; │└└└
; │┌ @ range.jl:620 within `iterate'
; ││┌ @ range.jl:501 within `isempty'
; │││┌ @ bool.jl:40 within `&'
	cmpq	$4, %rax
; │└└└
	jl	L71
; │ @ In[1]:5 within `c_cheating'
	negq	%rax
	xorl	%ecx, %ecx
	nopl	(%rax,%rax)
; │┌ @ int.jl:86 within `+'
L48:
	addq	%rbx, %rcx
; │└
; │┌ @ range.jl:624 within `iterate'
; ││┌ @ promotion.jl:398 within `=='
	leaq	(%rax,%rbx), %rdx
	addq	$4, %rdx
; ││└
	addq	$4, %rbx
; ││┌ @ promotion.jl:398 within `=='
	cmpq	$4, %rdx
; │└└
	jne	L48
	jmp	L73
L71:
	xorl	%ecx, %ecx
; │ @ In[1]:7 within `c_cheating'
L73:
	movq	%rcx, %rax
	popq	%rbx
	retq
	nop
; └

@code_native sum(4:4:(1_000_000*2))

	.text
; ┌ @ range.jl:1022 within `sum'
	pushq	%rbx
	movq	%rdi, %rbx
; │ @ range.jl:1023 within `sum'
	movabsq	$length, %rax
	callq	*%rax
	movq	(%rbx), %rcx
; │ @ range.jl:1025 within `sum'
; │┌ @ int.jl:87 within `*'
	imulq	%rax, %rcx
; │└
; │┌ @ int.jl:85 within `-'
	leaq	-1(%rax), %rdx
; │└
	testb	$1, %al
	jne	L45
; │┌ @ int.jl:461 within `>>' @ int.jl:454
	sarq	%rax
; │└
; │┌ @ int.jl:87 within `*'
	imulq	%rdx, %rax
	imulq	8(%rbx), %rax
; │└
	jmp	L60
; │┌ @ int.jl:461 within `>>' @ int.jl:454
L45:
	sarq	%rdx
; │└
; │┌ @ int.jl:87 within `*'
	imulq	%rax, %rdx
	imulq	8(%rbx), %rdx
	movq	%rdx, %rax
; │└
; │┌ @ int.jl:86 within `+'
L60:
	addq	%rcx, %rax
; │└
	popq	%rbx
	retq
	nopw	%cs:(%rax,%rax)
	nopl	(%rax,%rax)
; └

And for

@code_native c_loop(1_000_000)

is just too big to place here.

[jishnub]

In general for nanosecond timings, it is better to profile it using a setup code like this:

julia> @btime c_cheating(x) setup=(x=1_000_000)
  443.892 μs (0 allocations: 0 bytes)
500001000000

Compared with

julia> @btime c_loop(1_000_000)
  284.405 μs (0 allocations: 0 bytes)
500001000000