Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147987
| Subject | Re: OT: improve this simple algorithm? |
|---|---|
| Newsgroups | comp.lang.c |
| References | <C_EyF.8877$yS5.1510@fx22.iad> <87a790zn7z.fsf@bsb.me.uk> <_85zF.5075$II7.2317@fx17.iad> <qqj564$2m4$1@dont-email.me> |
| From | DFS <nospam@dfs.com> |
| Message-ID | <fxgzF.21520$1S4.4613@fx01.iad> (permalink) |
| Organization | blocknews - www.blocknews.net |
| Date | 2019-11-14 12:56 -0500 |
On 11/14/2019 4:01 AM, David Brown wrote:
> 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 a really good analysis, David. I'm embarrassed to mess up such
a tiny bit of C code - but it works anyway?
The fix is subtract 1 from the seq size:
i < (sizeof(seq) / sizeof(seq[0])) - 1
> This is getting good, but is not bug-free yet.
It's not bloat-free, either. Barry Schwarz pointed out the line before
the printf() is redundant.
if( seq[i + 1] - (seq[i] + 1) >= 1) {
The code works with or without that line.
> 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.)
ha!
> 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.
Since sizeof(seq)/sizeof(seq[0]) can only be >= 0 the compiler? decides
the result is unsigned, is that right?
Comparing int i to the (unsigned int) number of elements in the array is
somehow worth a warning? Not an egregious warning, but this is the kind
of thing that makes some people dislike C. It's like you can't write
working, reasonable code without being smacked on the back of the hand
with a ruler.
> 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.)
Or we could run screaming from C... but that execution speed is very
addicting.
> 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++) {
> ^~~
Bingo!
I've just been replaced by 3 letters in the compiler instruction.
> There we go. gcc has found your bug. It has pointed out exactly what
> is going wrong, and where.
I'm sure you know python doesn't let you get away with running past the
last element.
seq = [1, 2, 4, 5, 7, 8, 12, 13, 1300, 10000]
for i in range(len(seq)):
if (seq[i + 1] - seq[i]) > 1:
print("[%d,%d] " % (seq[i] + 1, seq[i + 1] - 1)),
$ python getintervals.py
[3,3] [6,6] [9,11] [14,1299] [1301,9999]
Traceback (most recent call last):
File "getintervals2.py", line 3, in <module>
if (seq[i + 1] - seq[i]) > 1:
IndexError: list index out of range
It's interesting that C will let you hang yourself in some ways, but is
so demanding in others.
>/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.)
If I print each [seq[i],seq[i+1]], the last 2 are:
gcc in MSYS2: [1301,9999] [10000,0]
tcc Windows : [10000,1310544] [10001,1310543]
> We also see that you should add a
> "printf("\n");" line at the end of the function.
a nit
> 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.
Yep. Perfect.
> 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.
I'll definitely look into them.
Thanks again for your in-depth assistance. I appreciate you taking the
time.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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