Path: csiph.com!news.swapon.de!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: An experimental max_n for int's... Date: Sun, 30 Aug 2020 03:35:02 -0700 Organization: A noiseless patient Spider Lines: 117 Message-ID: <86sgc48lrd.fsf@linuxsc.com> References: <86wo1h8we4.fsf@linuxsc.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="86d1f293bb165c9de9f8ef74e73a1f76"; logging-data="12626"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/EpFwHOwLNoVQgOul2a9MCLG54WvgGWGs=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:Gxybrtpb3xzXIPc5K+anBdsYdHU= sha1:3Bzv06t+dAaz6ZrR5ucticNaeBg= Xref: csiph.com comp.lang.c:154195 "Chris M. Thomasson" writes: > On 8/29/2020 5:33 AM, Tim Rentsch wrote: > >> "Chris M. Thomasson" writes: >> >>> What do you think of this [int array maximum function] >>> [code] >>> Is there a better way to write this? >> >> I would be inclined to write something more like this: >> >> #include >> #include >> >> static int >> maximum( int *v, size_t n, int r ){ >> return n == 0 ? r : maximum( v+1, n-1, r < *v ? *v : r ); >> } >> >> int >> max_n_int( int *p, size_t n ){ >> return maximum( p, n, INT_MIN ); >> } >> >> The INT_MIN is there to handle the degenerate case of arrays >> with no elements. > > I like the idea of using INT_MIN for the degenerate case. However, > your maximum is recursive. Can it blow the stack apart if feed with > a large enough array? Oh, excellent question. I'm glad you asked. Here is the generated code under gcc -O2 (white space editing only). Note the lack of any function call instructions: .globl max_n_int .type max_n_int, @function max_n_int: .LFB1: .cfi_startproc testq %rsi, %rsi movl $-2147483648, %eax je .L1 .p2align 4,,10 .p2align 3 .L3: movl (%rdi), %edx cmpl %edx, %eax cmovl %edx, %eax addq $4, %rdi subq $1, %rsi jne .L3 .L1: rep ret .cfi_endproc .LFE1: .size max_n_int, .-max_n_int Here is the generated code under clang -O1 (again white space editing only). Again there are no function calls: .globl max_n_int # -- Begin function max_n_int .p2align 4, 0x90 .type max_n_int,@function max_n_int: # @max_n_int .cfi_startproc # %bb.0: movl $-2147483648, %edx # imm = 0x80000000 jmp maximum # TAILCALL .Lfunc_end0: .size max_n_int, .Lfunc_end0-max_n_int .cfi_endproc # -- End function .p2align 4, 0x90 # -- Begin function maximum .type maximum,@function maximum: # @maximum .cfi_startproc # %bb.0: testq %rsi, %rsi je .LBB1_2 .p2align 4, 0x90 .LBB1_1: # =>This Inner Loop Header: Depth=1 movl (%rdi), %eax addq $4, %rdi cmpl %edx, %eax cmovgel %eax, %edx addq $-1, %rsi jne .LBB1_1 .LBB1_2: movl %edx, %eax retq .Lfunc_end1: .size maximum, .Lfunc_end1-maximum .cfi_endproc # -- End function I write small recursive functions like this all the time. My experience is that compilers are almost always smart enough to turn tail-call recursion into loops, like what was done in the two compilations shown above. Of course it is possible, if a naive compiler is used or if optimization settings are too low, that the tail-call optimization won't happen, and truly recursive object code will be the result. Usually though that doesn't happen. If we are being careful -- and we should be -- the lack of actual recursion in the object code should be verified; after all, we don't want any nasty surprises. But this isn't hard to do. It's a fairly simple matter to write a program in the scripting language of your choice (I used awk) that can scan code in this format and report cases of recursive calls in the object code. Having the tool in hand, making use of tail calls and tail recursion can be done with confidence. I recommend developing an ability to write simple functions like this using a recursive, tail-call-optimizable, style. Once you get the knack I think you will find it quite empowering.