From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: ok@goanna.cs.rmit.edu.au (Richard A. O'Keefe) Subject: Re: What's the best language to start with? [was: Re: Should I learn C or Pascal?] Date: 1996/09/04 Message-ID: <50jfdb$cmu@goanna.cs.rmit.edu.au> X-Deja-AN: 178400810 references: <31FBC584.4188@ivic.qc.ca> <4vroh3$17f@goanna.cs.rmit.edu.au> <01bb9360$21d0dbe0$87ee6fce@timpent.airshields.com> <50650h$rek@goanna.cs.rmit.edu.au> <50blgc$g9f@shellx.best.com> organization: Comp Sci, RMIT, Melbourne, Australia keywords: efficient newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada nntp-posting-user: ok Date: 1996-09-04T00:00:00+00:00 List-Id: Joe Keane writes: >That's just bad code. It specifies a *quadratic* algorithm for a very >simple operation. My impression would be that the coder doesn't >understand some basic things about C programming, or they're just >inconsiderate. How hard is it to put the length in a variable? Perhaps we have different perspectives. Would a *professional* programmer produce code like that? No way! Would it be "bad" if a 3rd semester student produced it? In my view, no way! At the moment, I'm bogged down in marking. Last semester, when the students were in their 3rd semester, using C, I would have wept for joy to see code that good. This semester, now they have had another semester under their belts, and understand something about big-Oh, I would expect better code. In fact, to my joy I *am* seeing better code, much better code. But the students are writing Ada this semester, and I find that our students *do* write much better Ada than they do C. >It's a basic fact that, in the idiomatic `for' loop, the test is >evaluated every time through the loop. You have forgotten the "as if" rule. The outcome of the program must be the same AS IF the expression had been evaluated every time, but when part of an expression manifestly does not change, the compiler is under no obligation to re-evaluate it. >If the upper bound is fixed, >it's really good practice to put it in a local variable. We *agree* that a *professional* programmer, if using a language in which the _only_ for-loop is like C's (which I am not knocking; I use "do" in Lisp and Scheme all the time, and it's like C's "for" only better), would arrange it cheaply. By the way, a *professional* C programmer would not call strlen() at all in such an example. But coming from an educational perspective, I am unwilling to call *clear*, *correct* code "stupid", or even "bad". A student who is capable of writing code that _good_ is one we can help to improve. >>The ONLY strlen() optimisation that is needed here >>is one that is completely general: strlen() is a pure function and its >>argument does not change, so the strlen(s) computation can be hoisted out >>of the loop. >It's not a pure function. Whether the argument changes isn't the point; >it's a local variable and it's clear to everyone that it's not changed. In the article you quote, I explained that by "argument" I meant the NTBS that the actual parameter points to, AND IN THIS EXAMPLE THAT NTBS DOES NOT CHANGE, and that *IS* the point. >Really. I expect an optimizing compiler to do a decent job of low-level >things, such as allocating registers, selecting instructions, scheduling >instructions, and so on. If optimization is turned off, the code will >get slower, maybe two to five times, but a constant factor. >I don't expect the compiler to work miracles, to turn crap into gold. >That would include changing a quadratic algorithm to a linear one. Some >people may think that it's nifty, but i think it's just a bit disturbing >and i'd rather have compiler writers concentrate on compiling good code. Again, we have obviously have different perspectives. I have one foot in the "declarative programming" community (and if you think Haskell and Mercury are esoteric, think "SQL" which has _exactly_ the same kinds of optimisation requirements and opportunities). For example, there is a well-known transformation which routinely turns a class of algorithms with exponential cost if taken naively into implementations with polynomial cost. Do I have to explain that the strlen() optimisation is one that has been legal for Fortran compilers since the first Fortran standard? Or that strlen() is a C library function, and that the C standard very carefully allows a compiler to take advantage of special knowledge about library functions? >You can't blow off a level of indirection so easily. "Blow off" iks rather offensive language. The NTBS that the pointer pointers to does not change. True, that is "a level of indirection", but I *explained* how that can be handled. >>In the program fragment under discussion, it was not merely the pointer >>that was constant, but the NTBS itself. >I think that you misunderstand the `const' keyword. Bullshit. I said nothing about the 'const' keyword. I said that the pointer and the NTBS were *constant*. That doesn't mean they are declared "read-only". It means THEY DIDN'T CHANGE. That's all. I defy anyone to show where the pointer or the NTBS changed in my example. I didn't mention the 'const' keyword because it wasn't relevant. >>If I do >> n = strlen(s); >> /* much code that does not change s */ >> /* NOT the NTBS that s refers to */ >> m = strlen(s); >>it is necessarily the case that m and n will be the same size_t value. >I'm unclear on that comment, but if there are pointer stores in there, >the length may be changed, even if `s' isn't changed. The comment (which should have read NOR, not NOT) *says* there are no such stores. You are like someone who is told "There are no dinosaurs in this room." and replies "I'm unclear on that remark, but if there are any dinosaurs in this room, one of them is about to bite your head off." >In your example, it is possible. But it's based on a lot of assumptions >and it's not something you should depend on. You have mistaken just about everything I was trying to say. I suppose this must be my fault. I *did* say explicitly that *I* know why naive compilers generate costly code for this, and that it is not something that I would myself write. I have been using C since V6+ UNIX, and have had to live with naive C compilers for years. >In many similar examples, >the compiler *must not* remove the duplicated calls. Yes, but we aren't *talking* about similar examples. Again, you are shifting the argument to attack a position I am not stating or defending. The strlen() example is a very very specific one; it is *ONLY* in the specific case of strlen() and *ONLY* in the specific case where the NTBS is not changing that C suckers students into writing for (i = 0; i < strlen(s); i++) ... process s[i] ... All I am claiming, all I have ever claimed, is that a beginner who writes *that* code to iterative over an unchanging NTBS is not writing "stupid" or "bad" code, merely code which is _inefficient_ under _some_ C compilers (admittedly the majority of them). I refuse to call clear correct *working* *readable* code "stupid" or "bad". That doesn't mean I am going to slobber over the author with praise, or that I am not going to put a fair bit of red ink on such an assignment. It just means I'm not going to call such a student nasty names, and am going to take it as an encouraging sign that the student has learned how to do some important things _well_. -- Australian citizen since 14 August 1996. *Now* I can vote the xxxs out! Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.