Content inspiration: Thoughts on midtail recursion in Swift [4] — Thuyen’s Corner.

Like the comment and hope it gets better and better with your help

Author: @ios growth refers to north, this article was first published in the public number iOS growth refers to north, welcome to the correction

Please contact me if there is a need to reprint, remember to contact oh!!

This is the sixth day of my participation in Gwen Challenge

What is recursion and what is tail recursion \ call

Recursive invocation is a common technique used in the development process to implement calls to functions themselves.

People often use recursion for two reasons:

  • Make code shorter and more concise
  • Node traversal of high-level structures (trees, graphs)

When we call the function itself at the end of a function, it is called tail recursion, and when we call other functions, it is called tail call [1].

Our function call will form a call record in memory, also called call frame [2], which stores the information of the call location and internal variables. These call frames form the Call stack during nested calls.

Tail Call optimization (TCO), which is used in most languages, keeps only the call record of the inner function. If all functions are called by Tail, then it is possible to make only one call record per execution. This will save a lot of memory. This is the meaning of tail-call optimization [3].

Recursion is very memory intensive because you need to hold hundreds or thousands of call records at the same time, which is prone to stack overflow errors. For tail recursion, however, stack overflow errors never occur because there is only one call record.

Some functional programming languages write this into the language specification, so does this optimization exist in iOS? What does this optimization do?

We are going to focus on Swift, right? Trust me, this problem is presented similarly in Objective-C.

Tail recursion crashes in Debug mode

Consider the following code: what happens in default Debug mode?

func sumPrefix(_ n: Int._ acc: Int) -> Int {
  if n = = 0 { return acc }
  return sumPrefix(n - 1, acc + n)
}

_ = sumPrefix(1000000.0)
Copy the code

A regular operation that computes the sum from 0 to 1000000.

When we run the current project, eh? collapsed

An EXC_BAD_ACCESS error occurred. This error occurs when a message is sent to freed memory or when an attempt is made to access a memory segment that has been freed — a segmentation fault.

Note that we are talking about the default Debug mode, which means that relevant compilation optimizations are not enabled

But when we add the same compilation optimizations as in Release mode, the code works fine!

Swift tail call optimization

Let’s compare how the same code behaves with tuning turned on.

Converting the code to assembly, what is the phenomenon of the current function call when the configuration item is -onone (some redactions for article)

_main:
	.cfi_startproc
	...
	callq	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	...
	.cfi_endproc

	.private_extern	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.globl	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.p2align	4, 0x90
main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register %rbp
	subq	$80, %rsp
	xorl	%eax, %eax
	leaq	-8(%rbp), %rcx
	...
	callq	_memset
	...
	callq	_memset
	...
	cmpq	$0, %rcx
	jne	LBB1_2
	...
	jmp	LBB1_5
LBB1_2:
	...
	callq	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	movq	%rax, -56(%rbp)
LBB1_5:
	movq	-56(%rbp), %rax
	addq	$80, %rsp
	popq	%rbp
	retq
LBB1_6:
	ud2
LBB1_7:
	ud2
	.cfi_endproc
Copy the code

Here a number of _memset function calls, in the process of running clear memory initialization operation. And when n! = 0 call jne LBB1_2, execute LBB1_2 method, callq main.sumprefix (swift.int, swift.int) -> swift.int.

As we run the function, we keep creating new stack space, which eventually overflows the stack and causes a crash.

Optimize for Speed[O] when we use the -o enabled Release environment :(untrimmed)

_main:
	movl	$1000000, %eax
	xorl	%ecx, %ecx
	.p2align	4, 0x90
	
	.private_extern	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.globl	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.p2align	4, 0x90
main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int:
	pushq	%rbp
	movq	%rsp, %rbp
	movq	%rsi, %rax
	testq	%rdi, %rdi
	je	LBB1_5
	movq	%rdi, %rcx
	.p2align	4, 0x90
LBB1_2:
	decq	%rcx
	jo	LBB1_6
	addq	%rdi, %rax
	jo	LBB1_7
	movq	%rcx, %rdi
	testq	%rcx, %rcx
	jne	LBB1_2
LBB1_5:
	popq	%rbp
	retq
LBB1_6:
	## InlineAsm Start
	## InlineAsm End
	ud2
LBB1_7:
	## InlineAsm Start
	## InlineAsm End
	ud2
Copy the code

The comparison found:

  • After starting optimization, there is no callq _memset

  • Callq main.sumPrefix(swift.int, swift.int) -> swift.int

Tail-recursion/call optimization can reuse stack space and reuse stack frames without requesting stack space, increasing efficiency and ensuring security.

Note that we didn’t find the sumPrefix call in the main function when we turned it on, because the -o that is Optimize for Speed[O] is another optimization point that the compiler will Optimize inline.

Inline optimization

Inline optimization, that is, some methods expand it directly into function body code to reduce the application of function stack frames for faster performance.

MJ said in his Swift class that recursive calls do not perform inline optimization. From the assembly code obtained so far, tail-recursive/call optimization is performed inline optimization.

We turn off the inlining optimization of the current function and use @inline(never) to mark the function to never be inlined.

@inline(never)
func sumPrefix(_ n: Int._ acc: Int) -> Int {
  if n = = 0 { return acc }
  return sumPrefix(n - 1, acc + n)
}
Copy the code

Then we -o export the compilation for analysis :(undeleted)

_main:
	pushq	%rbp
	movq	%rsp, %rbp
	movl	$1000000, %edi
	xorl	%esi, %esi
	callq	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	xorl	%eax, %eax
	popq	%rbp
	retq

	.private_extern	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.globl	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.p2align	4, 0x90
main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int:
	pushq	%rbp
	movq	%rsp, %rbp
	movq	%rsi, %rax
	testq	%rdi, %rdi
	je	LBB1_5
	movq	%rdi, %rcx
	.p2align	4, 0x90
LBB1_2:
	decq	%rcx
	jo	LBB1_6
	addq	%rdi, %rax
	jo	LBB1_7
	movq	%rcx, %rdi
	testq	%rcx, %rcx
	jne	LBB1_2
LBB1_5:
	popq	%rbp
	retq
LBB1_6:
	## InlineAsm Start
	## InlineAsm End
	ud2
LBB1_7:
	## InlineAsm Start
	## InlineAsm End
	ud2

	.section	__TEXT,__swift5_entry,regular,no_dead_strip
	.p2align	2
l_entry_point:
Copy the code

Callq main.sumprefix (swift.int, swift.int) -> swift.int, the body of the method call remains unchanged before the inlining is turned off.

Tail recursion/call optimization implementation principle: When the last step of function A is to call its own function A (or call other functions B), the position information and internal variables of the current function A are no longer used, and the stack frame of function A is directly handed over to function A (B).

conclusion

When using recursive/nested calls in Debug mode, once the call is too deep, it is possible to overflow the stack and cause a crash. Because maximum depth is not guaranteed, it can cause your build/debug to crash in some cases.

Our example here refers to tail recursion/invocation, which is probably more in line with common invocation logic, and you need to carefully consider whether your code causes too deep a call and whether using recursion is optimal.

In addition to implementing tail recursion/call optimization, Xcode’s compilation optimization for Swift performs inline optimization for recursive functions.

More and more

For Objective-C, the same crashes occur:

- (NSInteger)sumPrefix:(NSInteger)n acc:(NSInteger)acc {
    if (n == 0) {
        return acc;
    }
    return [self sumPrefix:n - 1 acc: acc + n];
}
Copy the code

You can explore it in a similar way.

The resources

Tail call: zh.wikipedia.org/wiki/ tail call

Call stack: zh.wikipedia.org/wiki/ Call stack

Tail call optimization: www.ruanyifeng.com/blog/2015/0…

Thinking about Swift in tail recursion: trinhngocthuyen. Making. IO/posts/tech /…

If you have any questions, please comment directly, and feel free to express anything wrong with the article. If you wish, you can spread the word by sharing this article.

Thank you for reading this! 🚀