Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #154195

Re: An experimental max_n for int's...

Show key headers only | View raw

"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:

> On 8/29/2020 5:33 AM, Tim Rentsch wrote:
>
>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> 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 <limits.h>
>>      #include <stddef.h>
>>
>>      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.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-29 00:11 -0700
  Re: An experimental max_n for int's... Bonita Montero <Bonita.Montero@gmail.com> - 2020-08-29 10:59 +0200
    Re: An experimental max_n for int's... gazelle@shell.xmission.com (Kenny McCormack) - 2020-08-29 10:18 +0000
      Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-30 00:04 -0700
    Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-30 00:06 -0700
  Re: An experimental max_n for int's... Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-08-29 03:43 -0700
  Re: An experimental max_n for int's... Bart <bc@freeuk.com> - 2020-08-29 12:06 +0100
    Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-29 18:08 -0700
  Re: An experimental max_n for int's... Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-08-29 05:33 -0700
    Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-29 18:01 -0700
      Re: An experimental max_n for int's... Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-08-30 03:35 -0700
        Re: An experimental max_n for int's... Bart <bc@freeuk.com> - 2020-08-30 12:12 +0100
          Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-30 20:33 -0700
            Re: An experimental max_n for int's... James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-08-31 07:50 -0400
              Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-31 17:46 -0700
                Re: An experimental max_n for int's... Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-01 02:32 +0100
                Re: An experimental max_n for int's... Richard Damon <Richard@Damon-Family.org> - 2020-09-01 07:27 -0400
                Re: An experimental max_n for int's... Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-01 13:36 +0100
                Re: An experimental max_n for int's... James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-09-01 10:21 -0400
                Re: An experimental max_n for int's... Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-01 15:57 +0100
                Re: An experimental max_n for int's... Richard Damon <Richard@Damon-Family.org> - 2020-09-01 21:45 -0400
                Re: An experimental max_n for int's... David Brown <david.brown@hesbynett.no> - 2020-09-01 14:39 +0200
                Re: An experimental max_n for int's... James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-09-01 10:28 -0400
          Re: An experimental max_n for int's... Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-09-07 08:28 -0700
        Re: An experimental max_n for int's... antispam@math.uni.wroc.pl - 2020-08-30 12:37 +0000
          Re: An experimental max_n for int's... Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-09-07 08:18 -0700
  Re: An experimental max_n for int's... DFS <nospam@dfs.com> - 2020-08-29 13:43 -0400
    Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-29 18:00 -0700

csiph-web