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

Groups > comp.lang.c > #147976 > unrolled thread

OT: improve this simple algorithm?

Back to article view | Back to comp.lang.c

Contents

  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

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

#148258

On Wed, 13 Nov 2019 23:57:47 -0500, DFS <nospam@dfs.com> wrote:

<snip>

>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++) {

That sizeof expression evaluates to 9.  

>     if(seq[i + 1] - seq[i] > 1) {

The above statement causes undefined behavior when i is 8.

>       if( seq[i + 1] - (seq[i] + 1) >= 1) {

Ditto.  

On the other hand, this statement serves no purpose.  When the first
if is true, this one must be true also.  Consider - 

When the first if is true:
   seq[i] contains the value n
   seq[i+1] - n  > 1 implies that seq[i+1] contains the value n+k
  n+k - n is simply k and k > 1 means k >= 2

The second if evaluates n+k - (n+1) which is simply k-1 and since 
k >= 2 then k-1 >= 1.

>         printf("[%d,%d] ", seq[i] + 1, seq[i + 1] - 1);
>       }
>     }		
>   }
>
>}
>================================================================
>

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#148259

On 2019-11-14, DFS <nospam@dfs.com> wrote:
> 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);
>        }
>      }		
>    }
> }

1) The #include <stdlib.h> is not necessary.

2) In the last iteration of the for loop,
   where i equals sizeof seq / sizeof seq[0],
   seq[i+1] accesses the seq array outside its bounds.

3) The tests

     seq[i+1] - seq[i] > 1

   and

     seq[i+1] - (seq[i] + 1) >= 1

   are effectively the same, so one of them is redundant.

4) The output is not terminated with an end-of-line character.

5) main() promises to return an int but it doesn't do so.

All in all, I'd be tempted to re-write your program as:

  #include <stdio.h>

  int main(void)
  {
    int seq[] = {1, 2, 4, 5, 7, 8, 12, 1300, 10000};

    for (size_t i = 0; i + 1 < sizeof seq / sizeof seq[0]; ++i)
    {
      if (seq[i + 1] - seq[i] > 1)
      {
        printf("[%d,%d] ", seq[i] + 1, seq[i + 1] - 1);
      }		
    }
    putchar('\n');
    return 0;
  }

[toc] | [prev] | [next] | [standalone]

#148264

On Thursday, 14 November 2019 07:53:32 UTC, Ike Naar  wrote:
> On 2019-11-14, DFS <nospam@dfs.com> wrote:
> > 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);
> >        }
> >      }		
> >    }
> > }
> 
> ---- <snip> ----
> 
> 5) main() promises to return an int but it doesn't do so.

Yes it does - it returns zero (it just doesn't do so explicitly):

[In all standards since C99]
5.1.2.2.3 Program termination
...
reaching the } that terminates the main function returns a value of 0.
...

> ---- <snip> ----

[toc] | [prev] | [next] | [standalone]

#148260

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.

[toc] | [prev] | [next] | [standalone]

#148266

On 14/11/2019 09:01, David Brown wrote:
> On 14/11/2019 05:57, DFS wrote:

>>    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) {

> 	tcc seq.c -Wall -o seq
> 
> No output - tcc is happy, and can't help you any more.

> 	gcc -Wall -Wextra seq.c -o seq -Wno-sign-compare
> 
> No warnings now.  gcc has done all it can.

So tcc and gcc (with -Wextra and -Wno-sign-compare) are BOTH happy.

gcc only becomes unhappy when you throw in even more options (how do you 
know when you've done enough?). And that includes turning on the optimiser.

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

> There we go.  gcc has found your bug.

Except it might be interspersed with 1000 other warnings, most of which 
are irrelevant. Note this won't work when the array bound is a variable, 
as it usually is.


> 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

I get 'cannot find -lubsan', on Windows.

It worked on Linux. However, when I put the code inside a function where 
the length of seq is a parameter, then it didn't detect the bounds error.

> 
> ./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.

I just ran the OP's algorithm through my script language. There it found 
the error (out of bounds access) without having to specify dozens of 
options first. And it worked when the code was inside a function.

So that is another approach: develop and test an algorithm with a 
'softer' language first, then code it in C with the bugs already ironed out.

Now, you don't really need a super-duper compiler. Not until you need 
fast production code.

[toc] | [prev] | [next] | [standalone]

#148267

On 14/11/2019 12:27, Bart wrote:
> On 14/11/2019 09:01, David Brown wrote:
>> On 14/11/2019 05:57, DFS wrote:
> 
>>>    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) {
> 
>>     tcc seq.c -Wall -o seq
>>
>> No output - tcc is happy, and can't help you any more.
> 
>>     gcc -Wall -Wextra seq.c -o seq -Wno-sign-compare
>>
>> No warnings now.  gcc has done all it can.
> 
> So tcc and gcc (with -Wextra and -Wno-sign-compare) are BOTH happy.
> 
> gcc only becomes unhappy when you throw in even more options (how do you
> know when you've done enough?). And that includes turning on the optimiser.

Of course.

This isn't very difficult.  It is unfamiliar to some people, especially
relative beginners, which is why I am explaining it to DFS and anyone
else who wants to benefit from useful tools to help their development.
You have shown that you would far rather whine, moan, and criticise than
actually /learn/ anything - and certainly you have no interest in using
good and helpful tools.  It would make a lot more sense for you to
simply stay out of such conversations.  (Unless, of course, you /do/
want to learn - in which case I would be happy to help and give you
pointers.)

> 
>> gcc -Wall -Wextra seq.c -o seq -Wno-sign-compare -O2
> 
>> There we go.  gcc has found your bug.
> 
> Except it might be interspersed with 1000 other warnings, most of which
> are irrelevant. Note this won't work when the array bound is a variable,
> as it usually is.
> 

Please, show me a listing of the 1000 other warnings here.  You can't do it?

I am recommending that DFS - and any other C developer, except those
determined to write problematic code - make use of tools with good
static analysis from day 1.  If you want to write tens of thousands of
lines of code and /then/ try compiling it, that's your problem.  Other
people find it far more sensible to compile regularly underway, so that
they are not overwhelmed by problems, so that they can fix issues early,
and so that they will not repeat the same mistakes.  And as I show here,
using a good tool, in the right way, makes the development process easier.

> 
>> 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
> 
> I get 'cannot find -lubsan', on Windows.
> 

I don't care.  I really don't.  You are outstanding at failing to get
anything gcc or clang related to work - it is entirely intentional and
the result of years of studied effort.

> It worked on Linux. However, when I put the code inside a function where
> the length of seq is a parameter, then it didn't detect the bounds error.
> 
>>
>> ./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.
> 
> I just ran the OP's algorithm through my script language. There it found
> the error (out of bounds access) without having to specify dozens of
> options first. And it worked when the code was inside a function.
> 
> So that is another approach: develop and test an algorithm with a
> 'softer' language first, then code it in C with the bugs already ironed
> out.

Of course you can work in another language.  Another approach is to
write the code in a more convenient language in the first place, and
/not/ re-write it in C.  Another approach is not to bother with the
program at all, since it doesn't do anything particularly useful.

But the guy is learning C.  So I am showing some useful tools, and how
to use them, for programming in C.

> 
> Now, you don't really need a super-duper compiler. Not until you need
> fast production code.

Oh, bollocks.

[toc] | [prev] | [next] | [standalone]

#148269

On 14/11/2019 11:46, David Brown wrote:

> But the guy is learning C.  So I am showing some useful tools, and how
> to use them, for programming in C.

Then you're teaching how to be reliant on tools rather than learn how to 
code, test and debug manually.

(Let me guess: you drive an automatic car and use a satnav?)

Here there is the pattern of 'i' iterating over all elements of an 
array, but there is an access to element i+1 in the loop. That should 
ring alarm bells.

None of the gcc options you suggested would automatically pick that up 
when the array size is only known via a variable. Actually, your 
suggestions could gave a false sense of security when they uncover 
apparently nothing amiss.

This is where real debugging starts.

[toc] | [prev] | [next] | [standalone]

#148273

On 14/11/2019 13:01, Bart wrote:
> On 14/11/2019 11:46, David Brown wrote:
> 
>> But the guy is learning C.  So I am showing some useful tools, and how
>> to use them, for programming in C.
> 
> Then you're teaching how to be reliant on tools rather than learn how to
> code, test and debug manually.

Unless you are writing your programs on pencil and paper, you are using
tools.  And learning to use the right tools in the right way is part of
the job.

> 
> (Let me guess: you drive an automatic car and use a satnav?)

No, I drive an old wreck with manual gears.  But I /do/ expect the
automatic airbag and seat belts to work when I need them.  And I do make
use of the features it has.

And I use a satnav when I don't know the way.  What do /you/ recommend?
 Trial and error?  Dirk Gently's navigation technique of spotting a car
that looks like it knows where it is going, and following it?

> 
> Here there is the pattern of 'i' iterating over all elements of an
> array, but there is an access to element i+1 in the loop. That should
> ring alarm bells.

Of course it should - for someone who is familiar with C programming.
The suggestions I have made will help him spot such problems until he
gets the feel of handling them without thinking.  And then they will
/still/ help when he makes occasional mistakes or typos like the rest of us.

> 
> None of the gcc options you suggested would automatically pick that up
> when the array size is only known via a variable. Actually, your
> suggestions could gave a false sense of security when they uncover
> apparently nothing amiss.
> 
> This is where real debugging starts.

Where did I give the impression that using a good tool would replace
thinking, or debugging, or testing, or writing carefully, or learning
the language?  The tool is an /aid/.  Use it as such.

[toc] | [prev] | [next] | [standalone]

#147979

On Tue, 12 Nov 2019 15:55:21 -0500, DFS <nospam@dfs.com> wrote:

>You clc guys are masters at this stuff.
>
>Goal: Find all the open intervals in an ordered set of numbers
>
>nbrs  = [1, 2, 4, 5, 7, 12, 1300, 10000]
>opens = [(3, 3), (6, 6), (8, 11), (13, 1299), (1301, 9999)]
>
>I think 'open intervals' is the right terminology.
>
>My simple algorithm:
>
>if nbrs is contiguous then exit
>else
>   for i in range(nbrs)
>     if nbrs[i+1] - nbrs[i] > 1 then
>       startinterval =  nbrs[i] + 1
>       if nbrs[i+1] - startinterval >= 1 then
>         endinterval = nbrs[i+1] - 1
>
>
>
>==============================================
>#include <stdio.h>
>#include <stdlib.h>
>#include <string.h>
>
>int main(void) {
>
>   int i = 0, x = 0;
>   int nums[] = {1, 2, 4, 5, 7, 12, 1300, 10000};
>   //int nums[] = {3,4,5,7,8};  //sequential, for testing
>   int lenNums = sizeof(nums)/sizeof(nums[0]);
>   int start = nums[0];
>   int end   = nums[lenNums-1];
>   char *interval = "";

interval points to a string literal that consists of the single
character \0.

>   char *intervals[sizeof(char*) * lenNums];

Not many compilers support VLAs.

Most would allocate a dynamic array.  Some would define an array with
an arbitrary size based on the maximum number of elements expected.

>   //check for no open intervals
>   if((end-start)==(lenNums-1)) {
>     printf("Number set is sequential from %d to %d\n",start,end);
>     exit(0);
>   }	
>	
>   //find open intervals
>   x = 0;
>   for(i=0;i<lenNums;i++) {

What is this fetish you have for eye tests?

>     if(nums[i+1]-nums[i] > 1) {
>       start = nums[i]+1;
>       if(nums[i+1]-start >= 1) {
>         end = nums[i+1]-1;
>         //end of algorithm
>
>         sprintf(interval,"(%d,%d)",start,end);

interval still points to the string literal.  You are not allowed to
modify a string literal.  This causes undefined behavior.

>         intervals[x] = interval;    //assignment seems to work

Bar addressed this.

>         printf("%s ",intervals[x]);
>         x++;
>
>       }
>     }		
>   }
>
>printf("\n\n");
>
>//Why do the following not work, given that the
>//assignment and printf() in the loop above seems to?

They do work; they just don't do what you expect.

Run the code under a debugger and look at the values in intervals[i].

>printf("Interval 1 = %s\n",intervals[0]);
>printf("Interval 2 = %s\n",intervals[1]);
>printf("Interval 3 = %s\n",intervals[2]);
>printf("Interval 4 = %s\n",intervals[3]);
>printf("Interval 5 = %s\n",intervals[4]);
>printf("\n");
>for(i=0;i<x;i++) {
>   printf("%s ",intervals[i]);
>}  	
>
>
>printf("\nDone");
>exit(0);		
>}
>==============================================

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#147980

Barry Schwarz <schwarzb@delq.com> writes:
[...]
> Not many compilers support VLAs.
[...]

Is that true?  Visual Studio doesn't, but in my experience most
(other?)  modern C compilers do.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#147981

On 14/11/2019 15:28, Bart wrote:
> On 14/11/2019 13:21, David Brown wrote:
>> On 14/11/2019 13:28, Bart wrote:
> 
>>>
>>> I don't think it's me failing to understand the issues. You have to
>>> write a function that operates on a string like this:
>>>
>>>    int stringop(char* s, int length) {
>>>    }
>>>
>>
>> I'm sorry, I am a programmer.  If someone asks me to write a function
>> with unlimited sizes, or "as fast as possible", I reject it as poorly
>> specified.  (Or I give them a better specification - my job often
>> involves writing requirement specifications because the customer doesn't
>> really understand what is needed.)
> 
> 'length' may relate to the size of a file; or a string representing a 
> bignun; or the size of the output of a code generator. Something that 
> can easily be into 7 or 8 figures without there being anything amiss.
> 

And there you are getting a little bit better specified.

> I don't call that poorly specified. Let's say the task is to remove 
> spaces from a read-only string then pass that new string on to another 
> function. So you need a temporary local copy.


That is not close to a specification.

> 
> It's a general purpose function that can be used for those longer 
> strings, or equally for very short strings; why impose a restriction? 
> The only one is available memory.
> 
> I have anyway limited the size to 2**31-2.
> 
> You're refusing to answer the question, so I'm tell you: using VLAs as 
> the primary data structure is unsuitable here.

If you are specifying lengths up to 2**31 - 2, then I agree, VLA's will 
not be suitable.

If you are specifying lengths up to 1 K, which would be more than 
adequate for, say, names and addresses, then a VLA would be fine.

When you don't say what you want, you can't expect to get it.

> 
> You can use a VLA combined with heap, but equally you can use a fixed 
> local array combined with heap.

As a general rule, you should not use a VLA unless you would be equally 
safe and correct with a fixed length array on the stack.  i.e., you 
don't declare "int a[n]" unless you know "n > 0" and "n < N" where "N" 
is a compile-time fixed quantity that you would be happy using as a size 
of array on the stack.  And then you use "int a[n]" as a VLA because it 
is more efficient than using "int a[N]".

VLA's are not a vital technology.  They don't make a huge difference to 
code speed or convenience.  And usually you could use a fixed size 
array.  But when you have data that could be up to, say, 4K long but is 
more likely to be under 20 bytes, it is a lot more efficient in memory 
and cache to use a VLA than a fixed size array of 4K.

There is one other major point where VLA's are useful - when you have a 
size that is a fixed size at compile time, but is not a constant integer 
expression.  If you write "const int n = 12;", you can't declare a 
normal C array "int a[n];".  You /can/ do it with VLAs.  You can expect 
the compiler to generate exactly the same code as for "int a[12];", but 
the legalities of C say it is a VLA and not a normal array.  (In C++, it 
would be a normal array.)

> 
> However a VLA has extra issues: on Windows where gcc uses a function to 
> allocate stack frames which are either over 4KB, or which might be over 
> 4KB (eg. a VLA of size n, even if n is small), that can make things slower.
> 

That is an issue on Windows whenever you use stack frames bigger than 
4K.  It doesn't matter if you use a VLA or a normal array, or an 
alloca() call, or a thousand local "int" variables.  And it doesn't 
depend on the compiler.

> To conditionally use a VLA, when the size if small, has its own problems 
> where the VLA is defined inside a block; you can't use it outside the 
> block. And it might not be enough to stop the __chkstk() call.
> 
> A solution involving a local array can be done like this:
> 
>      char buffer[2048];
>      char *t;
> 
>      if (length<sizeof(buffer)
>          t=buffer;
>      else
>          t=malloc(length+1);
> 
> The downside is that every invocation will involve using 2KB of stack, 
> but that is only an issue when heavily recursive. We know that here, 
> that is unlikely.

An obvious solution would be to use another function:

static void usebuffer(char * p, size_t n) {
	...
}

void dosomething(size_t length) {
	const size_t max_local = 2048;
	if (length < max_local) {
		char buffer[length + 1];
		usebuffer(buffer, length);
	} else {
		char * t = malloc(length + 1);
		usebuffer(t, length);
		free(t);
	}
}

(Leave it to the compiler to figure out if usebuffer should be inlined, 
or a separate function.)

[toc] | [prev] | [next] | [standalone]

#147986

On 14/11/2019 16:08, David Brown wrote:
> On 14/11/2019 15:28, Bart wrote:

>> 'length' may relate to the size of a file; or a string representing a 
>> bignun; or the size of the output of a code generator. Something that 
>> can easily be into 7 or 8 figures without there being anything amiss.
>>
> 
> And there you are getting a little bit better specified.

It's a function that takes a string. How specific do you want it to be 
regarding the possible lengths of string?

How long a string does strlen() take?

[toc] | [prev] | [next] | [standalone]

#147996

On 14/11/2019 16:08, David Brown wrote:
> On 14/11/2019 15:28, Bart wrote:

>> However a VLA has extra issues: on Windows where gcc uses a function 
>> to allocate stack frames which are either over 4KB, or which might be 
>> over 4KB (eg. a VLA of size n, even if n is small), that can make 
>> things slower.
>>
> 
> That is an issue on Windows whenever you use stack frames bigger than 
> 4K.  It doesn't matter if you use a VLA or a normal array, or an 
> alloca() call, or a thousand local "int" variables.

That's misleading. A normal array of 3K bytes won't need special 
handling such as calling __chkstk. But a VLA of 3K bytes /will/ need it 
if the compiler doesn't know that it is only 3K bytes (or just 3 bytes).

>  And it doesn't 
> depend on the compiler.

Yes it does. My 'bcc' doesn't use anything like '__chkstk()' even for 
large stack frames. (But it requires the stack to be preallocated or 
whatever the term is for the stack pages to be already committed and 
reserved; probably the same approach is used on Linux.)

I can't speak for other Windows compilers, except that I have seen such 
a call for gcc, tcc and lccwin.

[toc] | [prev] | [next] | [standalone]

#147983

On 15/11/2019 00:53, David Brown wrote:
> On 14/11/2019 11:42, Bart wrote:
>>
>> It's completely obvious that VLAs can be far more dangerous than malloc
>> calls. Yet you are trying to brush the problems under the carpet.
>>
> 
> It is obvious that you are failing to understand the issue.  I'm not
> sure if it is because you are failing to apply even a modicum of thought
> to the process, or just trolling.

A betting man would take a punt on the latter.

-- 
Ian.

[toc] | [prev] | [next] | [standalone]

#147990

On 14/11/2019 14:38, Bonita Montero wrote:
>> However a VLA has extra issues: on Windows where gcc uses a function 
>> to allocate stack frames which are either over 4KB, or which might be 
>> over 4KB (eg. a VLA of size n, even if n is small), that can make 
>> things slower.
> 
> I've benchmarked alloca(), and VLAs would have a similar performance
> -impact. an alloca() takes about 13 clock-cycles including the __chkstk
> on my Ryzen. That should be unbeatable by malloc().

malloc isn't the only choice.

You can use your own small-object allocator which can be very fast with 
smaller sizes. (One advantage here is that the allocation can persist 
beyond the function life-time if necessary.)

Or use your own FILO stack-like-allocator, but now using your own stack 
that can be any size you like, and overflow can be checked (and if 
overflowing, could even be extended).

[toc] | [prev] | [next] | [standalone]

#147997

> Or use your own FILO stack-like-allocator, but now using your own stack 
> that can be any size you like, and overflow can be checked (and if 
> overflowing, could even be extended).

If the lifetime of content that would be otherwise allocated on such
an additional stack would be the same as the pointer on on the stack
of a function and the size isn't too large you better stick with VLAs
or alloca().
And an issue with your stack is, that when there is an overlow-exten-
sion, all pointers to your stack become invalid.

[toc] | [prev] | [next] | [standalone]

#148002

On 14/11/2019 19:16, Bonita Montero wrote:
>> Or use your own FILO stack-like-allocator, but now using your own 
>> stack that can be any size you like, and overflow can be checked (and 
>> if overflowing, could even be extended).
> 
> If the lifetime of content that would be otherwise allocated on such
> an additional stack would be the same as the pointer on on the stack
> of a function and the size isn't too large you better stick with VLAs
> or alloca().

I like to write code that can work across languages, and VLAs are not 
always available. (Nor even in C when using my own compiler.)

> And an issue with your stack is, that when there is an overlow-exten-
> sion, all pointers to your stack become invalid.


Yes, if the software stack can extend, then it might need to become 
fragmented. This is makes it a little more fiddly, but the details are 
hidden behind the function calls used to allocate and deallocate.

For most calls, the top-of-stack should be within one memory pool, 
rather than at either end, and it can still be efficient.

[toc] | [prev] | [next] | [standalone]

#148016

>> If the lifetime of content that would be otherwise allocated on such
>> an additional stack would be the same as the pointer on on the stack
>> of a function and the size isn't too large you better stick with VLAs
>> or alloca().

> I like to write code that can work across languages, and VLAs are not 
> always available. (Nor even in C when using my own compiler.)

That usually doesn't depend what you like.
You simply know which platforms you target.

>> And an issue with your stack is, that when there is an overlow-exten-
>> sion, all pointers to your stack become invalid.

> Yes, if the software stack can extend, then it might need to become 
> fragmented. This is makes it a little more fiddly, but the details
> are  hidden behind the function calls used to allocate and deallocate.

Stack fragmented ... LOL.

[toc] | [prev] | [next] | [standalone]

#147991

David Brown <david.brown@hesbynett.no> writes:
[...]
> 	gcc -Wvla
>
> warns if a VLA is used.
>
> And
> 	gcc -Wvla-larger-than=10000
>
> warns if a VLA is bigger than 10000 bytes (or might be bigger than
> that).  It is useful to have optimisation enabled to let the compiler
> work out bounds more accurately.

Note that the latter option might not warn about some VLAs if gcc has
optimized them into ordinary arrays.  (The gcc documentation covers
this.)

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#148001

On 14/11/2019 19:15, Keith Thompson wrote:
> David Brown <david.brown@hesbynett.no> writes:
> [...]
>> 	gcc -Wvla
>>
>> warns if a VLA is used.
>>
>> And
>> 	gcc -Wvla-larger-than=10000
>>
>> warns if a VLA is bigger than 10000 bytes (or might be bigger than
>> that).  It is useful to have optimisation enabled to let the compiler
>> work out bounds more accurately.
> 
> Note that the latter option might not warn about some VLAs if gcc has
> optimized them into ordinary arrays.  (The gcc documentation covers
> this.)
> 

Yes, though that should only be the case if gcc knows the VLA is going 
to be quite small, or if it knows the size is fixed (in which case you 
might know it too).  If you want to be more general, 
"-Wstack-usage=10000" can be a better option.

(There are also tools for generating stack usage information, which can 
be combined with tools for call graph and code flow analysis, which can 
be helpful in estimating bounds on total stack usage of a program. 
These things are rarely used on hosted systems, however, but are 
sometimes useful in embedded development.)

[toc] | [prev] | [next] | [standalone]

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

Back to top | Article view | comp.lang.c

csiph-web