Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #148000
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: OT: improve this simple algorithm? |
| Date | 2019-11-14 20:45 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <qqkask$elg$1@dont-email.me> (permalink) |
| 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> <fxgzF.21520$1S4.4613@fx01.iad> |
On 14/11/2019 18:56, DFS wrote:
> 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?
>
Making mistakes is part of the learning process. And it was a nice
mistake for demonstrating tools to help catch such mistakes, so it was a
positive thing that you posted it.
But don't get the idea that "it worked anyway". Don't get in the habit
of thinking "it worked when I tested it, it must be correct" - bad code
can work by luck during testing, and you can be sure it will fail by
luck when used later on.
>
> The fix is subtract 1 from the seq size:
>
> i < (sizeof(seq) / sizeof(seq[0])) - 1
>
Yes. Or you can use Ben's alternative of starting from 1. Or my own
preference:
int main(void) {
const int seq[] = {1, 2, 4, 5, 7, 8, 12, 1300, 10000};
const int seqlen = sizeof(seq) / sizeof(seq[0]);
for (int i = 0; i < seqlen - 1; i++) {
if (seq[i + 1] - seq[i] > 1) {
printf("[%d, %d] ", seq[i] + 1, seq[i + 1] - 1);
}
}
printf("\n");
}
I prefer not to have overly complex expressions in the "for" controlling
expressions. Local variables are free - use them whenever they might
help clarity.
(And note, if you will, the more consistent use of spacing. I am a
strong fan of space in code. The exact details of where you have spaces
and where you don't is a matter of style and preference, but consistency
is always good.)
>
>
>> 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.
It was redundant, yes. But it wasn't the source of a bug.
>
>
>
>> 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?
No. "sizeof" gives an expression of type "size_t", which is always an
unsigned type (typically an alias for "unsigned long" or "unsigned long
long" on most systems). Thus is is of unsigned type.
So when when comparing the signed int "i" to this expression, the
compiler (following the rules of the language) will convert "i" to the
same unsigned type as "size_t" (unless size_t is smaller than an "int" -
hypothetically possible, but not at all likely). Converting a signed
value into an unsigned value could change its value. So the compiler
can give a warning here to tell you there might be something unexpected
going on.
<https://en.cppreference.com/w/c/language/conversion>
>
> 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.
>
The day you find that "(-1 > 0x80000000)" evaluates as "true" on most C
systems, you will be glad of compilers giving you such warnings.
There is no choice of implicit conversion rules that would work well in
every case and be as efficient as people want from a language like C -
the rules were picked to give the best (or least bad) results for most
cases.
>
>
>> 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.
>
C is not for everyone, nor for every programming task. It is an
excellent choice in some circumstances, but you need to know its rules
and quirks. And you need to learn to work /with/ the language and
tools, not /against/ them. That does not mean you have to like all the
rules - no one does. You just have to obey them when you use C. (And
feel free to use other languages too - no one in c.l.c. will be upset.)
>
>
>> 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.
>
C is a language that trusts the programmer - it does not add any extra
checks that you have not asked for.
>
>
>> /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]
>
This is undefined behaviour - /anything/ could happen. It is unlikely,
but you /could/ get :
[1301,9999] [10001,reformating hard drive...]
More realistically, you will get whatever happened to be in the invalid
memory at the time.
>
>> We also see that you should add a
>> "printf("\n");" line at the end of the function.
>
> a nit
>
Yes - but strive to make your programs as nice as you can. It's all
good practice.
>
>> 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.
(Skip the multi-threading stuff for now!)
>
> Thanks again for your in-depth assistance. I appreciate you taking the
> time.
I hope it helps you and others.
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