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

Groups > comp.lang.c > #148260

Re: OT: improve this simple algorithm?

From David Brown <david.brown@hesbynett.no>
Newsgroups comp.lang.c
Subject Re: OT: improve this simple algorithm?
Date 2019-11-14 10:01 +0100
Organization A noiseless patient Spider
Message-ID <qqj564$2m4$1@dont-email.me> (permalink)
References <C_EyF.8877$yS5.1510@fx22.iad> <87a790zn7z.fsf@bsb.me.uk> <_85zF.5075$II7.2317@fx17.iad>

Show all headers | View raw

On 14/11/2019 05:57, DFS wrote:
> 
> That recursion is pretty cool.
> 
> I was inspired to decrapify mine (still iterative tho):
> ================================================================
> #include <stdio.h>
> #include <stdlib.h>
> 
> int main(void) {
> 
>   int seq[] = {1, 2, 4, 5, 7, 8, 12, 1300, 10000};
> 
>   for(int i=0; i < (sizeof(seq) / sizeof(seq[0])); i++) {
>     if(seq[i + 1] - seq[i] > 1) {
>       if( seq[i + 1] - (seq[i] + 1) >= 1) {
>         printf("[%d,%d] ", seq[i] + 1, seq[i + 1] - 1);
>       }
>     }       
>   }
> 
> }
> ================================================================
> 
> 

This is getting good, but is not bug-free yet.

Let's look at how tools can help, with this program saved as "seq.c".

	tcc seq.c -Wall -o seq

No output - tcc is happy, and can't help you any more.

(But it runs in 4 ms on my machine.  Yeah!  That's more than ten times
faster than gcc, saving me 50 milliseconds!  If I do this often enough,
tcc will have saved me enough time to blink.)

	gcc -Wall -Wextra seq.c -o seq

seq.c: In function ‘main’:
seq.c:8:18: warning: comparison between signed and unsigned integer
expressions [-Wsign-compare]
   for(int i=0; i < (sizeof(seq) / sizeof(seq[0])); i++) {


gcc has found a potential problem.  It is not, in this case, a real
problem in the code.  It is fine to compare a signed type and an
unsigned type - /if/ you know the values will be valid after the integer
promotions used by C to make both sides the same type.  These integer
promotion rules are not always obvious, especially to someone new to the
language, and it is easy to make mistakes.  So many compilers can warn
you when you mix signed and unsigned types in comparisons, even though
it is a false positive in this case.

So let's disable that particular warning for now.  (Alternatively, we
could change the type of "i" to "unsigned int", or cast the sizeof
expression to an int.)

	gcc -Wall -Wextra seq.c -o seq -Wno-sign-compare

No warnings now.  gcc has done all it can.

Or has it?

Remember I told you to enable optimisation for better static analysis?

gcc -Wall -Wextra seq.c -o seq -Wno-sign-compare -O2

seq.c: In function ‘main’:
seq.c:9:11: warning: iteration 8 invokes undefined behavior
[-Waggressive-loop-optimizations]
     if(seq[i + 1] - seq[i] > 1) {
        ~~~^~~~~~~
seq.c:8:3: note: within this loop
   for(int i=0; i < (sizeof(seq) / sizeof(seq[0])); i++) {
   ^~~


There we go.  gcc has found your bug.  It has pointed out exactly what
is going wrong, and where.  /That/ is why you should use gcc (or clang,
or MSVC) for development, with warnings enabled and with optimisation
enabled.  Ignore the muppets who tell you you want a fast and simple
compiler for development, and ignore the muppets who tell you to use
"debug" builds with no optimisation.


Let us progress - we will take the blasé attitude that "it's only a
warning", and try the generated program:

./seq
[3,3] [6,6] [9,11] [13,1299] [1301,9999] [10001,32743]

We see two things here.  One is the unexpected extra interval at the
end.  This shows that something has gone wrong.  (The value it shows for
the last number will vary.)  We also see that you should add a
"printf("\n");" line at the end of the function.


So (still pretending we did not see the warning from gcc showing the
problem), we know something is wrong - but we don't know what.  That is
where sanitizers come in:

gcc -Wall -Wextra seq.c -o seq -Wno-sign-compare -O2 -fsanitize=undefined

./seq

seq.c:9:11: runtime error: index 9 out of bounds for type 'int [9]'
seq.c:9:11: runtime error: load of address 0x7ffc5116f764 with
insufficient space for an object of type 'int'
0x7ffc5116f764: note: pointer points here
  10 27 00 00 00 00 00 00  00 9a ab 7b ce 5c 60 44  a0 d9 c2 c8 07 7f 00
00  00 00 00 00 00 00 00 00

The sanitizer has spotted the problem with the out of bounds access to
the array, on line 9 of the seq.c file.  That is plenty of information
for finding and fixing the error.



Give these gcc options a shot before you fix the program.  Then use them
regularly in your development for checking your code.

Other useful sanitize options include:

	-fsanitize=address

for checking memory and pointers,

	-fsanitize=leak

for checking malloc/free leaks, and

	-fsanitize=thread

for multi-threaded stuff.

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

Thread

OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-12 15:55 -0500
  Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-12 21:20 +0000
    Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-12 23:28 -0500
      Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 10:52 +0100
        Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-13 10:16 -0500
          Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 16:53 +0100
      Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 11:18 +0000
  Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-12 23:30 +0000
    Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-15 05:12 +1300
      Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 16:34 +0000
        Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-15 10:07 +1300
          Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 22:25 +0000
            Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-15 12:02 +1300
              Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 23:27 +0000
                Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-15 19:06 +1300
                Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-15 10:45 +0000
                Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-15 13:28 +0100
                Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-15 12:58 +0000
                Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-15 15:39 +0100
                Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-15 15:04 +0000
                Re: OT: improve this simple algorithm? Richard Damon <Richard@Damon-Family.org> - 2019-11-15 12:19 -0500
                Re: OT: improve this simple algorithm? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-15 09:46 -0800
                Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-15 18:59 +0000
                Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-16 11:59 +0000
                Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-16 09:02 +1300
              Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-15 11:17 +0100
                Re: OT: improve this simple algorithm? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-15 21:38 +0000
    Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-14 11:44 -0500
      Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-14 18:11 +0000
        Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-14 13:33 -0500
          Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-15 01:49 +0000
      Re: OT: improve this simple algorithm? Barry Schwarz <schwarzb@delq.com> - 2019-11-14 10:38 -0800
    Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-14 12:56 -0500
      Re: OT: improve this simple algorithm? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-14 13:50 -0500
        Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-14 14:42 -0500
          Re: OT: improve this simple algorithm? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-14 15:25 -0500
      Re: OT: improve this simple algorithm? Barry Schwarz <schwarzb@delq.com> - 2019-11-14 11:03 -0800
        Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-14 16:08 -0500
          Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-15 11:30 +0100
            Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-15 11:17 +0000
              Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-15 17:35 -0500
                Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-15 17:39 -0500
                Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-15 23:19 +0000
                Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-15 18:53 -0500
                Re: OT: improve this simple algorithm? Richard Damon <Richard@Damon-Family.org> - 2019-11-15 19:08 -0500
                Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-16 01:30 +0000
                Re: OT: improve this simple algorithm? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-16 07:39 -0500
                Re: OT: improve this simple algorithm? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-16 07:37 -0500
          Re: OT: improve this simple algorithm? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-15 09:46 -0500
            Re: OT: improve this simple algorithm? Richard Damon <Richard@Damon-Family.org> - 2019-11-15 12:38 -0500
              Re: OT: improve this simple algorithm? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-15 23:07 +0000
              Re: OT: improve this simple algorithm? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 16:54 -0800
                Re: OT: improve this simple algorithm? Richard Damon <Richard@Damon-Family.org> - 2019-11-28 20:17 -0500
                Re: OT: improve this simple algorithm? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-29 06:08 -0800
      Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 20:45 +0100
    Re: OT: improve this simple algorithm? Keith Thompson <kst-u@mib.org> - 2019-11-14 10:10 -0800
      Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 20:19 +0100
    Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-12 23:57 -0500
      Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 10:34 +0100
    Re: OT: improve this simple algorithm? DFS <nospam@dfs.com> - 2019-11-13 23:57 -0500
      Re: OT: improve this simple algorithm? Barry Schwarz <schwarzb@delq.com> - 2019-11-13 23:00 -0800
      Re: OT: improve this simple algorithm? Ike Naar <ike@sdf.lonestar.org> - 2019-11-14 07:53 +0000
        Re: OT: improve this simple algorithm? guinness.tony@gmail.com - 2019-11-14 02:34 -0800
      Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 10:01 +0100
        Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 11:27 +0000
          Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 12:46 +0100
            Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 12:01 +0000
              Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 14:05 +0100
  Re: OT: improve this simple algorithm? Barry Schwarz <schwarzb@delq.com> - 2019-11-12 18:34 -0800
    Re: OT: improve this simple algorithm? Keith Thompson <kst-u@mib.org> - 2019-11-12 19:01 -0800
      Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 17:08 +0100
        Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 17:06 +0000
        Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 19:11 +0000
      Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-15 05:15 +1300
      Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 18:13 +0000
        Re: OT: improve this simple algorithm? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 20:16 +0100
          Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 20:03 +0000
            Re: OT: improve this simple algorithm? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-15 04:51 +0100
      Re: OT: improve this simple algorithm? Keith Thompson <kst-u@mib.org> - 2019-11-14 10:15 -0800
        Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 20:52 +0100
      Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 10:57 +0100
        Re: OT: improve this simple algorithm? Ian Collins <ian-news@hotmail.com> - 2019-11-13 23:23 +1300
        Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 11:53 +0000
          Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 14:02 +0100
            Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 13:40 +0000
              Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 17:01 +0100
                Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 16:28 +0000
                Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-13 22:49 +0100
                Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 22:38 +0000
                Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-13 23:06 +0000
                Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 10:10 +0100
                Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 10:42 +0000
                Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 12:53 +0100
                Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 12:28 +0000
                Re: OT: improve this simple algorithm? David Brown <david.brown@hesbynett.no> - 2019-11-14 14:21 +0100
                Re: OT: improve this simple algorithm? Bart <bc@freeuk.com> - 2019-11-14 14:28 +0000
                Re: OT: improve this simple algorithm? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 15:38 +0100
                Re: OT: improve this simple algorithm? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 13:37 +0100
                Re: OT: improve this simple algorithm? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-14 13:38 +0100
          Re: OT: improve this simple algorithm? Thiago Adams <thiago.adams@gmail.com> - 2019-11-13 05:21 -0800

csiph-web