bill@twwells.uucp (T. William Wells) (10/27/88)
Sorry I wasn't able to participate much in the discussion on efficient
coding, but between setting up my new computer, a wedding
anniversary, computer problems at work, thinking about comp.archives,
and lots of other things, I have had little or no time to write, and
certainly not about anything complex. Anyway, here goes...
It's the damnedest thing, but people whose opinions I otherwise
respect seem to have this thing about coding efficiently. They don't
like it. Worse, they discourage it.
Well, phooey.
---
I advocate training oneself to be one who codes efficient programs. I
do not mean writing code and then making it more efficient, I mean
writing it that way in the first place. One should make it a practice
to consider which coding methods are best on each architecture, so
that it is second nature to code efficiently. Efficient coding should
take its place right along with easily understood coding as something
every coder should do, as a routine part of the job.
I have heard three main counterarguments to this:
1) "The compiler ought to handle that, so you shouldn't bother with
it." What nonsense! We have to code in the real world, not the
world of make-believe and ought-to.
2) "What is more efficient on one machine may well be less efficient
on another." Well, this is a good argument for knowing a lot of
different machines and adapting one's coding style to the relevant
machines, but this is certainly not a good argument for avoiding
efficient coding. What it boils down to is an argument that a
program which is coded in ignorance of efficiency may well be
better (efficiency-wise) than one which is coded to be efficient,
albeit only for some set of architectures. Well, could be, but I
wouldn't bet on it.
3) "Efficient coding makes obscurer programs." Well, since most
efficient coding involves minor changes from the inefficient way
of doing things, changes which are mostly a matter of style rather
than of organization, this argument should really be read: "*I*
don't like to or find it hard to read that kind of program, so it
is unclear." Well, speak for yourself!
---
[I wrote about improving other people's code. I mentioned that
following certain coding practices, eliminating "fat", and doing so
throughout a program, I was often able to improve the execution time
by 25% or more.]
From: rwberry@hubcap.UUCP (Robert W Berry)
Message-ID: <3105@hubcap.UUCP>
: I've been programming for YEARS, and if it's not a professional trade
: secret, I'd love it if you would summarize your "coding practices" and
: email them or post them.
They are no real secret but I haven't really thought hard about
organizing them for presentation, so I can't just tell you about
them. However, some of the suggestions that I have seen posted have
been similar to what I do. The next time I go over someone else's
code, I'll see if I can remember to make notes. Following are some
suggestions right off the top of my head, take them with the
requisite dollop of thinking for oneself.
The first thing: understand the kinds of architectures where
efficiency matters. If you are coding a game, you can be reasonably
sure that efficiency is only of concern on relatively conventional
architectures, so make yous assumptions accordingly. If you are
coding some kinds of numerical stuff, where the greatest efficiency
ought to be obtained on an array processor, keep in mind the
characteristics of array processors when optimizing code. The more
you know about the processors that your code could have to run on,
and the better your analysis of which ones efficiency matters on, the
better will be the decisions you make on which coding practices to
adopt.
Read compiler design books. Whatever they tell you is good for the
compiler is also good for you the coder. They talk about common
subexpression elimination: when you write code, look for common
subexpressions and eliminate them. (But watch out: not all common
subexpressions should be eliminated, this too is a matter of
judgegment and experience.) They talk about strength reduction, you
look for places where strength reduction is possible. Note that
*you* can do a better job of this than the compiler can. *You* are
capable of inductions that the compiler is not. *You* can find
optimizations that are not possible to discover mechanically. This is
one reason why the argument "leave it to the compiler" is often wrong.
Along this line, look for redundant calculations: sometimes it is
cost effective to store the result of a previous calculation instead
of recomputing it. In particular avoid recalculation in the control
part of iterative statements. Many's the time that I have got
significant improvements just by turning:
for (i = 0; i < a[j]; ++i) ...
into
for (i = 0, ilast = a[j]; i < ilast; ++i) ...
or some equivalent.
Use register variables. And take a litle pain to get them right. A
technique that works enough of the time is this: break up a routine
into groups that are executed with about the same frequency.
Guessing is OK. Starting with the most frequent, count the number of
references to each automatic. If the numbers are sufficiently
different, order them by those numbers. Where they are not, use the
next most frequent group to decide the order. Repeat till you run out
of groups or variables. This is only a heuristic, but it can be done
on the fly, or with simple programming tools, and is certainly better
than not specifying register variables at all.
Avoid excess function calls. A lot of people have been brainwashed by
some modularity gurus into believing that every identifiable "whole"
should have its own function. What I have found is that this makes
the program LESS maintainable than otherwise. And, of course,
programs written this way do a lot of function calls. My own recipe
divides functions into two classes: those that control the operation
of other functions and those that do the dirty work. The control
functions should generally restrict themselves to if's and function
calls and maybe some initialization; the other functions can do
whatever is needed. If the grunge functions start to get too
complicated, start from the outside when splitting up the function:
this keeps down the number of function calls while getting the most
decomposition for your effort.
Don't use goto. Yes, oddly enough, this can make programs slower.
Many optimizers that I know of give up on any function that contains
a goto. So adding a goto may very well slow down your code.
---
From: g-rh@XAIT.XEROX.COM (Richard Harter)
Message-ID: <34112@XAIT.XEROX.COM>
: I would say that we all know what Bill is talking about
: here, except that "we" all obviously don't. Basically this is
: using hand optimization as a default in coding style. One can take
: the view that a good optimizer will do many of these things, e.g.
: use of temporaries, moving static expressions outside loops, placing
: the appropriate variables in registers, etc. One can also take the
: view that the capabilities and realities of optimizing compilers are
: less than claimed. Hand optimizing is safer across a variety of
: environments.
:
: In my experience hand optimizing in original code is less
: efficient, in the sense of code written per unit time, then writing
: code initially in a "clear" style first, and then hand optimizing
: afterwards. In short, write it in the simplest way first, get it
: working, and then improve performance.
This is not quite what I am advocating. Rather than hand-optimizing
as you code (though one should certainly do a certain amount of
this as a matter of course), I am advocating developing a mindset
where this kind of "optimizing" becomes your natural coding style.
This does mean developing more than one "natural" coding style, but
that is no more a problem than our habit of using different speech
patterns in different social situations.
As an example of what I mean, when I am coding a program that I
expect to be run on one of the "normal" machines, I don't write my
code as
for (i = 0; i < ALAST; ++i) {
... A[i];
}
and then change it to:
for (ap = A; ap < &A[ALAST]; ++ap) {
... *ap;
}
I write it this second way, as a matter of course, because I thought
about it for a while and decided that this was the appropriate way to
do it. I then trained myself into the habit of doing it this way.
Now, I don't spend *any* extra time getting the advantages of the
latter formulation. As a necessary and important side effect I also
became comfortable with such things and now treat them as no more
abnormal or incomprehensible than *ptr++.
---
From: bright@Data-IO.COM (Walter Bright)
Message-ID: <1700@dataio.Data-IO.COM>
: Here's some of the things I do:
: o Organize complicated if statements so the result of the calculation
: is known by evaluating it as little as possible. For instance,
: if (a && b && c)
: ...
: organize such that if a is easy to evaluate and usually FALSE, put
: it first.
This also generalizes to sequences of if-else statements.
: o Replace stuff like,
: if (a)
: x = b;
: else
: x = c;
: with,
: x = a ? b : c;
: Many compilers generate better code for the latter.
I have to disagree with this. About the only time that this helps is
when combining the statements gives greater scope to the optimizer.
This happens because many optimizers won't optimize across
statements. Unfortunately, this particular change, when done with
complicated expressions, can make the code much harder to read, so it
must be done with care.
: o Use the ^ operator because many times,
: a = !a;
: should really be,
: a ^= 1;
However, some machines can't do ^ very well, so take care.
: o Avoid things like,
: a %= 4;
: Replace with,
: a &= 3;
Generally true, but watch out for negative numbers. Also, dividing
positive numbers by powers of two should be done with a shift.
: o Organize control flow such that the most common cases go straight
: through, this is most important for pipelined machines.
While this is true, this tends to make the code *much* less readable,
even when you can get the optimizer to cooperate. So I don't do this
one.
: o I gag when I see things like,
: a = strlen("asdf") + 1;
: instead of,
: a = sizeof("asdf");
: The strlen case above was even printed in a magazine recently to
: 'prove' that assembler was better than C!
Gag. This is a specific example of a general case: never do at run
time that which you can get the compiler to do at compile time.
However, beware of getting the compiler to do floating point for you:
some won't, and others will do it differently in the compiler than
they would have at run time.
: o Try to improve the 'locality' of operations, i.e. move calculations
: as close as possible to the point where they are used. This helps
: most compilers to utilize registers better.
Good point. I hadn't thought of doing this. And it should often make
the reader's job easier, bringing related things closer.
: o Replace int variables with unsigned where possible. This tells the
: optimizer that the variable can never be negative, making certain
: optimizations possible.
Unfortunately, this one is likely to make the optimizer not do certain
optimizations that the compiler writer didn't think were useful for
unsigned. Sigh. Not only that, but I have discovered more bugs dealing
with unsigned things...
: o Put the most frequently accessed member of a struct first, so the
: offset is 0.
Yes. And put scalar arguments before aggregate arguments in your
functions.
: o Use char arrays instead of int arrays where possible.
Accessing characters on some systems causes a fair amount of code to
be generated. For example, on a 68000, accessing an unsigned character
to be used as an integer adds an instruction to each read. Accessing
a signed character might involve two extra instructions.
: o Adjust other
: arrays so that the size of the array elements are a power of 2.
: (Making the address calculation a simple shift.)
Be careful if you are making the arrays larger, you may make the
program slower. Demand paging systems and swapping systems both can
do you dirty when the program data is bigger.
: o Avoid bit fields, most especially signed ones.
Try: don't use them at all, they tend to be nonportable. Of course,
if you have a good compiler on a VAX...
: o Use realloc instead of malloc/free pairs. Use calloc instead of
: malloc followed by zeroing each member.
Efficient memory allocation is *much* more difficult than this, what
you really need to do is to cut down on the number of calls to malloc
and free. Of course, that usually means writing some kind of
allocation stuff yourself, never an easy task.
Realloc has to copy data, so this should be less efficient than just
doing another malloc & free.
Also, calloc is nearly useless for clearing structures that contain
pointers. It is just not portable to assume that a bit pattern of all
zeros is equivalent to a null pointer.
---
From: gwyn@smoke.ARPA (Doug Gwyn )
Message-ID: <8630@smoke.ARPA>
: > o Avoid things like,
: > a %= 4;
: > Replace with,
: > a &= 3;
:
: You're assuming a is nonnegative. Any decent compiler will
: perform such instruction replacements for you. Write whatever
: is clearest in context. To get a remainder, % is clearer.
You are assuming that the compiler can figure out that a is
nonnegative. Unless declared so, it is unlikely that a compiler will
figure this out. However, the human can. And, again, clarity is often
merely in the eye of the beholder. *I* don't have any problem
interpreting the & as a remainder operation.
: In the case that the "4" might change, parameterizing the
: first case will give correct code after it changes, while
: the second will break unless another power of two is used
: for the replacement for "4". Thus the first is SAFER.
Unless, of course, the programmer remembered to COMMENT.
: > o Combine printfs,
: > printf("aksdf aksjdhf kahdf jhdsfhj\n");
: > printf(" asdkljfhkajshdf djfh kjahsdfkja h\n");
: > Convert to,
: > printf("aksdf aksjdhf kahdf jhdsfhj\n\
: > asdkljfhkajshdf djfh kjahsdfkja h\n");
:
: Thereby introducing a bug (exercise for the student).
The spaces. Two black spots for K&R string continuation.
: The difference in time between these is negligible,
: but if you're really tweaking for efficiency puts()
: might have been better, depending on the implementation.
But I'd think of this as a *space* optimization, not a speed
optimization. And I know of several programs where just this one
optimization could save 5-10% in the program size.
: ...
: A related point is to declare local variable in blocks
: rather than all at the beginning of the function body.
I've found that this can actually make the code harder to read, by
making it difficult to find the declaration of a variable. My own
practice is to declare things in just four places: in an include file,
at the top of a source file, at the top of a function, and within a
block, but only if the whole of the block will fit in a 20 line
window.
: > o Put the most frequently accessed member of a struct first, so the
: > offset is 0.
:
: Not all architectures can access the 0 offset faster than
: the others. I knew of one that was actually slower.
But, unless one really cares about this oddball situation, one should
do it anyway.
: > o Avoid struct function parameters and return values.
:
: This is a matter of interface design. Small structs such
: as one might use to represent a complex number are not a
: problem; large structs are more quickly (though less conveniently)
: passed by reference, so long as not too many references to
: the members are made inside the function. Forcing the
: caller to allocate the structure may not be convenient.
I avoid structure passing and returning. There are still enough
compilers out there that don't handle them, or that handle them wrong
that portability considerations keep me from using them.
---
From: bright@Data-IO.COM (Walter Bright)
Message-ID: <1704@dataio.Data-IO.COM>
: Micro-efficiency gets regularly denounced. Here are some counterarguments:
: o If your commercial product is slower than the competition, you
: won't get a chance to take advantage of the maintainability/
: portability advantages because you'll be out of business.
Or if it is larger. This discussion has focused on making programs
faster, but making them smaller is also relevant. I do know that we
have lost customers because someone else offered a smaller program to
do the same job.
: o The sum of all the tweaks can make the difference (on the PC)
: between using a small memory model and the large. This gives
: a lot of leverage to seemingly minor changes.
The sum of all tweaks can make a difference on lots of machines.
Consider the Mac 32K segments, the PDP-11 64K+64K address space, the
user forced to wait for 10 seconds instead of 4 because of the 5%
slower routine which caused the scheduler to lower his priority....
: o I derive a lot of personal satisfaction from creating 'lean
: and mean' code.
This is often disregarded: good programmers get that way because they
*care*, and if they care, they will insist on doing the best they
can. And that should include these "tweaks".
---
Phew... I finally got it all answered. On to the next subject...
---
Bill
{uunet|novavax}!proxftl!twwells!billgwyn@smoke.BRL.MIL (Doug Gwyn ) (10/28/88)
In article <119@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes: >It's the damnedest thing, but people whose opinions I otherwise >respect seem to have this thing about coding efficiently. They don't >like it. Worse, they discourage it. I think it would be more accurate to say that we want to discourage excessive concern with microefficiency to the detriment of other important attributes of source code. >2) "What is more efficient on one machine may well be less efficient > on another." Well, this is a good argument for knowing a lot of > different machines and adapting one's coding style to the relevant > machines, .. Actually the force of this argument is stronger if you already appreciate the value of coding for reasonable behavior on almost any C implementation, rather than "optimum" behavior on just one. Some people really may never port their code outside the first system it's compiled for, but many of us do and we simply don't have time to fine-tune the code in each environment (unless we will personally accrue enough benefit to justify it). My own time is worth much more than any computer's. >3) "Efficient coding makes obscurer programs." Certainly going overboard with microefficiency tweaks does. > for (i = 0; i < a[j]; ++i) ... >into > for (i = 0, ilast = a[j]; i < ilast; ++i) ... In most cases, the following can be used: for (i = a[j]; --i >= 0; ) which is more efficient and clearer. (But don't write something like for (p = &a[j]; --p >= a; ) which is nonportable.) > for (i = 0; i < ALAST; ++i) { > ... A[i]; > } > > for (ap = A; ap < &A[ALAST]; ++ap) { > ... *ap; > } > >I write it this second way, as a matter of course, because I thought >about it for a while and decided that this was the appropriate way to >do it. I then trained myself into the habit of doing it this way. This makes a good example of the dangers of overconcern with such matters. There are quite a few compilers that, in many cases, will generate much better code for the first method than for the second, because they can recognize an opportunity to use vector instructions. Others will generate essentially the same code for the two methods. Unless the situation is naturally thought of as involving a pointer (for example, to a structure member of an array), it may be clearer to treat array elements as array elements. >... dividing positive numbers by powers of two should be done with a shift. No! Juggling the source code to use bit-oriented operations in an arithmetic context not only makes the code less portable and harder to maintain, it can also lead to future errors, when for example a chunk size is changed to a variable rather than a constant, or to a non-power-of-two. >Unless, of course, the programmer remembered to COMMENT. Comments don't necessarily track the code, and it is unrealistic to expect every use of the kind of tricks you advocate to be commented. Besides, the failure may very well result when code is changed somewhere far from the place of the comment. I agree that any use of a trick ought to be clearly commented, but then whenever I find myself doing that I also usually figure out a good non-tricky way to accomplish the goal and use that instead.
djones@megatest.UUCP (Dave Jones) (10/28/88)
From article <119@twwells.uucp>, by bill@twwells.uucp (T. William Wells): ... > > Phew... I finally got it all answered. On to the next subject... > Dream on.
scs@athena.mit.edu (Steve Summit) (10/28/88)
In article <119@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes: >It's the damnedest thing, but people whose opinions I otherwise >respect seem to have this thing about coding efficiently. They don't >like it. Worse, they discourage it. Some time ago I came to the conclusion that the style vs. efficiency debate is another religious war, which I usually try to stay out of. Good style and, I'll admit it, anti-efficiency is a personal crusade, though, so I can't help but respond. None of this should be taken as a personal attack against Mr. Wells, or anyone else, for that matter. His points are well taken; I simply have a different point of view, going back to first principles, as all good religious wars do. When caught between a rock and a hard place, when something's got to give, some people shrug their shoulders and sacrifice style, modularity, or portability. I am prepared to sacrifice efficiency. (Most of the time I can have my cake and eat it too, and I have any number of general techniques for doing so, which I will probably defer to a separate posting so that those who are sensibly ignoring these diatribes can still see them.) >I advocate training oneself to be one who codes efficient programs. I >do not mean writing code and then making it more efficient, I mean >writing it that way in the first place. Here I agree with at least some of the words, but not the implications. It happens that I usually write nice, efficient programs, but not by resorting to microefficiency tweaks or by sacrificing readability in any way. It is important to employ lots of common sense (and, of course, "common sense isn't"); to shy away from grotesquely inefficient algorithms; and to partition the code so that key sections can be cleanly replaced later if efficiency does prove to be an issue. It isn't important to write every last expression and statement in the most theoretically blistering way possible. >I have heard three main counterarguments to this: >1) "The compiler ought to handle that, so you shouldn't bother with > it." What nonsense! We have to code in the real world, not the > world of make-believe and ought-to. Many of the more egregious examples of source-level microefficiency tweaking are, in fact, routinely handled by today's (and even yesterday's) compilers. Consider replacing power-of-two multiplies by left shifts, a textbook example. I just booted up my pdp11 (I am not making this up), and its optimizer knows how to shift left when I multiply by two. (To be sure, not all newer compilers have been better.) >3) "Efficient coding makes obscurer programs." Well, since most > efficient coding involves minor changes from the inefficient way > of doing things, changes which are mostly a matter of style rather > than of organization... I don't know what is meant by "most efficient coding." The interpretation "the most efficient coding involves the most minor changes" is probably not the one that was intended, although I like it, because taken to its extreme it says not to make any changes at all. I cannot agree with the more likely interpretation. The minor changes, the replacements of multiplies and divides by shifts and the like, are mostly noise (both with respect to efficiency and style). The really big efficiency hacks, the ones people spend weeks and months on, do involve massive organizational changes and wholesale concessions to readability and maintainability. > ...this argument should really be read: "*I* > don't like to or find it hard to read that kind of program, so it > is unclear." The attitude of most C experts is "*I* don't have any problem reading this code; anyone else who considers himself a Real C Programmer shouldn't, either." This attitude is patronizing and wrong. To borrow a previous argument, "We have to code in the real world, not the world of make-believe." There are plenty of people out there who are still learning C, and since C has become as popular as it has and C programmers are in demand, many of them are working for real companies writing (and maintaining) real programs. A few painless concessions (like multiplying instead of shifting, or making comparisons against NULL pointers explicit) really do substantially increase the readability of code by mere mortals. (I maintain that every unnecessary translation from an encoding back to an intended meaning, no matter how intuitive to the experienced programmer, incrementally increases comprehension time, effort required, and probability of error.) >...look for redundant calculations: sometimes it is >cost effective to store the result of a previous calculation instead >of recomputing it. ...but be scrupulously careful, and comment the stored result well, because doing so is one, extremely common, "concession to maintainability." One of the all-time, number one bugs is the redundant variable whose value becomes wrong because one of the precedent variables changes, but the calculation is not repeated. If you use n squared at several different places within a longish section of nontrivial control flow, and you try to replace it with a new variable nsq which is set to n*n just once, sooner or later someone (probably you) is going to make some change to the program (either a new assignment to n, or a new wrinkle in the control flow) which results in nsq not containing the square of the current n. If you leave the explicit n*n everywhere, this error is impossible. This advice, like almost anything, must be applied on a case-by-case basis. When the control flow is straight-through and all occurrences of the common subexpression are well- localized, a temporary variable is often a good idea, not so much because it's easier to type or it might be more efficient, but because it makes it easier for the reader to prove that the identical quantity was really used in both (or all three, etc.) places. >Use register variables. And take a litle pain to get them right. A >technique that works enough of the time is this:... I'm sorry, I don't have spare time or spare brain cells for following or utilizing a technique like this. When I was a beginning C programmer, I decided not to use register variables at all in the first pass of coding, because I figured that, when I eventually got the program working, somebody was going to say that it wasn't fast enough, and if I had already blown all of my ammunition, how was I going to speed it up? Lately I throw in "register" all the time, but in some ways I respect my original attitude more. The point is, if it's the sort of program that people notice how fast it is, they would have complained even if I had used register variables since day one. I have also always felt that this is one area where the compiler really should be doing the work. Many modern compilers are very, very good at register allocation. It is true that the historically popular compilers (specifically, the Unix ones) are not, so it is good practice to put "important stuff" in registers, but don't spend a lot of time on it unless you have to. (What's "important stuff?" A ridiculously simplistic rule of thumb for using "register" in C, albeit one of the two I use, is "on any variable named 'i' or 'p'.") >Avoid excess function calls. A lot of people have been brainwashed by >some modularity gurus into believing that every identifiable "whole" >should have its own function. What I have found is that this makes >the program LESS maintainable than otherwise. Here's another religious debate: the structured programming one. Nevertheless, good modularity is the only way to keep a large program maintainable. Of particular pertinence to the theme of this article is that efficiency-critical modules, if properly isolated, can be implemented quickly and (possibly) inefficiently first, while getting the program to work correctly at all, and then transparently replaced later with a more efficient version, if and only if it is found that the quick, inefficient implementation is really too inefficient after all. If people have a bad impression of highly modular code, it is because they (or, more likely, their predecessors) have used what I call a "Ginsu knife" approach to modular decomposition, whereas the correct instrument to use is a scalpel. If you went to a lecture once on modularity but the only guideline you remember is "50 source lines," you're going to use split -50 on your monolithic source files, and not garner any of the benefits of good modularity. If, on the other hand, you learn how to modularize well, you just won't believe how easy your life (with respect to software development and maintenance, anyway) will become. There are a few applications (and, some believe, a few architectures) for which function call overhead is significant, but they are infrequent, and in general there should be absolutely no stigma attached to a function call. It's usually easy to back a function call out later, if you have to. (The normal way is with macros, but be careful lest the semantic differences between macros and functions hamper code quality.) >Rather than hand-optimizing >as you code (though one should certainly do a certain amount of >this as a matter of course), I am advocating developing a mindset >where this kind of "optimizing" becomes your natural coding style. >As an example of what I mean, when I am coding a program... >I don't write my > > for (i = 0; i < ALAST; ++i) > ... A[i]; > >and then change it to: > > for (ap = A; ap < &A[ALAST]; ++ap) > ... *ap; > >I write it this second way, as a matter of course. I am in complete agreement that there is a large class of good coding practices which is far better learned well and adopted from the beginning than applied retroactively. (I disagree that source-level microefficiency belongs in this class.) The judicious use of pointers does belong in this class, once you're comfortable with them, and as long as they're appropriate for the problem at hand. If you're not coding for a particular machine, or if it's low-frequency code, don't worry about using array notation if it makes more sense. Among other things, it may not make a speed difference, after all. Just yesterday a colleague and I were working with an FFT routine. (Interestingly enough, it was in the book "Numerical Recipes in C".) The first difficulty was the use of shifts instead of multiplies and divides. My colleague is a fine mathematician, and a competent C programmer, but "m=n>>1" just wasn't leaping off the page and saying "divide by two" for him, and he was interested in seeing how the algorithm worked. I was particularly annoyed with this particular shift, because it was in initialization code, so any savings wouldn't matter. Then I realized that there were also some shifts in inner loops, and was about to concede that the shifts in the initialization section were justifiable, for consistency's sake. Then I noticed that the "m=n>>1", which did appear in a loop, operated on a constant n which had been computed with "n=nn<<1", so if efficiency really mattered, a simple "m=nn" could have been used. (Side note on style: a variable called "nn" usually means twice "n," not the other way around.) Then I noticed an "istep=2*mmax" (also in a loop), thus demolishing any consistency argument. Shift vs. multiply is actually a side issue here. Things got interesting when I noticed that, in spite of their apparent concern with efficiency, the authors of the FFT code had used nothing but array references, even in the inner loops of the code (doubtlessly because it had been translated from Fortran). "Well," I said to myself, remembering a favorite sentence from The Elements of Programming Style, "FFT's are an area in which efficiency does matter in practice, so let's see what happens if I replace those array references with pointers." The result, to my considerable surprise, but reinforcing the point all the more, was that there was no difference (30.59 vs. 30.54 seconds for 20 512-point FFT's on a PC AT.) I know that there are machines on which a difference would have been evident. The point here is that there are also machines for which there is no difference at all, either because they can implement subscripts efficiently, or because the floating-point operations completely dominate the timing. Previous posters have noted that there are also machines for which pointers could actually be slower. >: o Replace [simple if/then with ?:] >I have to disagree with this. >statements. Unfortunately, this particular change, when done with >complicated expressions, can make the code much harder to read... Agreed. >: o Organize control flow such that the most common cases go straight >: through, this is most important for pipelined machines. >While this is true, this tends to make the code *much* less readable... Absolutely. Control flow should be determined almost entirely by readability and stylistic considerations. >: o Avoid bit fields, most especially signed ones. >Try: don't use them at all, they tend to be nonportable. This is a side question: what's so unportable about bitfields? Sure, the layout (left to right or right to left) isn't defined, but that's only a problem if you're trying to conform to external layouts, which is a "problem" with structures in general. (The solution is neither "don't use bitfields" nor "don't use structures" but "don't try to portably conform to external layouts.") The ordering could also be a problem if the code internally depended on it in some way, but this is no more or less a problem than programs which depend on byte ordering within words. Are there substantial numbers of real (not toy) C compilers that either don't implement bitfields, or that don't implement them correctly? ("Correctly" as defined by K&R and ANSI, not by some program that is trying to use them nonportably.) >: o Use realloc instead of malloc/free pairs. Use calloc instead of >: malloc followed by zeroing each member. >Efficient memory allocation is *much* more difficult than this, what >you really need to do is to cut down on the number of calls to malloc >and free. Of course, that usually means writing some kind of >allocation stuff yourself, never an easy task. Please don't avoid malloc; the alternative is generally fixed-size arrays and "lines longer than 512 characters are silently truncated." Please don't roll your own allocation routines, again unless you have to; this is the kind of low-level dirty work, hard enough to do well, that you should let the lower levels (i.e. the standard implementations of malloc) give it their best shot. >Also, calloc is nearly useless for clearing structures that contain >pointers. It is just not portable to assume that a bit pattern of all >zeros is equivalent to a null pointer. Absolutely correct. Why does calloc exist? Of what use is it? Why has ANSI legitimized it? In principle, it is equally useless for clearing structures that contain floating-point fileds. >: > o Avoid things like, >: > a %= 4; >: > Replace with, >: > a &= 3; > >: In the case that the "4" might change, parameterizing the >: first case will give correct code after it changes, while >: the second will break unless another power of two is used >: for the replacement for "4". Thus the first is SAFER. > >Unless, of course, the programmer remembered to COMMENT. If the code reads a &= 3; /* really a %= 4 */ or a &= 3; /* really a %= HASHSIZE */ and I do a global replace of 4, or re#define HASHSIZE, the comment may not help. >: Micro-efficiency gets regularly denounced. Here are some counterarguments: >: o If your commercial product is slower than the competition, you >: won't get a chance to take advantage of the maintainability/ >: portability advantages because you'll be out of business. >Or if it is larger. This discussion has focused on making programs >faster, but making them smaller is also relevant. I agree, and find code size far more frequently relevant in practice (among other things, because of the aforementioned pdp11). Remember that the classic tradeoff is between time and space, so the fancy efficiency hacks often make the code larger. On the other hand, there is a quote of Brian Kernighan's or Dennis Ritchie's (which I can't find at the moment) which points out that, counter to the tradeoff, clean, tight code is often smaller and faster. (Emphasis on clean. Of course, I advocate sneaky hacks to decrease code size as much as I advocate efficiency hacks, i.e. not at all.) I might also point out that the marketplace generally rewards the product that comes out first, so if you can compress your development schedule by using clean, straightforward design and eschewing time-consuming and bug-prone efficiency tweaking, you may come out ahead (and sew up your market share and your pocketbook by releasing a speeded up version 2 six months later). >: o The sum of all the tweaks can make the difference (on the PC) >: between using a small memory model and the large. This gives >: a lot of leverage to seemingly minor changes. >The sum of all tweaks can make a difference on lots of machines. >Consider the Mac 32K segments, the PDP-11 64K+64K address space, the >user forced to wait for 10 seconds instead of 4 because of the 5% >slower routine which caused the scheduler to lower his priority.... While these considerations are real, they should be viewed as unfortunate and temporary limitations which will be resolved, hopefully soon enough, at the root level, and not something which we resign ourselves to working around forever, and which we get so used to working around that the workarounds become part of the language, persisting well beyond their need. These are what Fred Brooks calls "accidental problems," and every programmer minute and line of code spend catering to them is not being spent on real problems. >: o I derive a lot of personal satisfaction from creating 'lean >: and mean' code. >This is often disregarded: good programmers get that way because they >*care*, and if they care, they will insist on doing the best they >can. And that should include these "tweaks". I'll third the motion, but without the tweaks. My proudest code is that which is not only small and fast and elegant and portable and modular and extensible but also patently obvious in function to the casual observer, and demonstrably correct without exhaustive analysis. That may sound like a tall order, but I think I'm fairly successful at it, and as I've implied I'll compromise on the first two (size and speed) before the rest, and the last two (obvious and demonstrably correct) are non-negotiable. * * * I'm not going to try to second-guess all of the replies I will undoubtedly get from the efficiency aficionadoes out there, but I will mention two things. I keep saying "don't do <something> unless you have to," by which I mean after actual experiments on prototype code demonstrate that there is a problem. The attitude of "don't worry about efficiency until later" is frequently denigrated as leading to unsalvageably inefficient code, because trying to patch in some efficiency later is tantamount to a rewrite. Although this can be true, the solution is to teach people good, responsible programming practices early, avoiding gratuitous and unnecessary inefficiency, without teaching them to "optimize too early." It's been said before, and I'll say it again and keep saying it: Don't Optimize Too Early. If, once the program is working correctly, it's too slow, profile it and then see about optimizing the routines that will make a difference. This absolutely does not mean that you should write throwaway code; if the prototype is a hodgepodge, you won't be able to go back in and speed it up cleanly, and you also won't be able to go back and add any features without breaking it (on the off chance that it isn't badly broken already). Responsible programming practices are just what the articles I am reacting to are trying to formulate, and all I'm trying to do is to draw the line a little more finely between what's reasonable and what's overboard. My second point, and the reason I'm taking all of this time and space replying, is that people who are learning programming (and we're all still learning programming) are much more impressionable than you might think. There's nothing wrong with this; it's actually refreshing given that it is often supposed that people stop learning at around age 20. But it does mean that if you unilaterally tell a reasonably green programmer to use pointers instead of arrays, he'll spend months having lots of frustrating problems with pointers, and likely end up hating them and the language in general. Even the most obfuscated efficiency tweaks do occasionally have a place, when speed really matters and the hardware (or whatever) isn't up to it, but these techniques tend to be discussed and advocated out of proportion to their usefulness. None of us need more excuses or encouragement to write tricky code. There are far better problems to be expending effort on. Steve Summit scs@adam.pika.mit.edu
guy@auspex.UUCP (Guy Harris) (10/28/88)
>: o Use the ^ operator because many times, >: a = !a; >: should really be, >: a ^= 1; > >However, some machines can't do ^ very well, so take care. And some code for reasons of, well, *microefficiency* may rely on the fact that any non-zero value, not just 1, is considered "true" by C; the only safe way of inverting such a boolean is with "a = !a". Too bad C doesn't have a Boolean type....
guy@auspex.UUCP (Guy Harris) (10/28/88)
>: o Use realloc instead of malloc/free pairs. Use calloc instead of >: malloc followed by zeroing each member. > >Realloc has to copy data, so this should be less efficient than just >doing another malloc & free. Err, umm, "realloc" is often used when you have e.g. an array with N filled-in elements, and you want to add some more elements; in this case, if you do another "malloc" and "free", you'll have to copy the entire array *anyway*; some "realloc" implementations may be able to avoid this if they can tell that the extra data can simply be pasted onto the end of the existing array.
knudsen@ihlpl.ATT.COM (Knudsen) (10/29/88)
In article <8775@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn ) writes: > (But don't write something like > for (p = &a[j]; --p >= a; ) > which is nonportable.) Why not portable? I know there are some weird architectures that may treat pointers strangely. But assuming that p is declared apointer to the same type as a[], don't the official semantics of C guarantee that the above code is valid? What am I missing? -- Mike Knudsen Bell Labs(AT&T) att!ihlpl!knudsen "Lawyers are like nuclear bombs and PClones. Nobody likes them, but the other guy's got one, so I better get one too."
henry@utzoo.uucp (Henry Spencer) (11/01/88)
In article <7421@ihlpl.ATT.COM> knudsen@ihlpl.ATT.COM (Knudsen) writes: >> for (p = &a[j]; --p >= a; ) >> which is nonportable.) > >Why not portable? ... It terminates by running p off the beginning of a, and comparing it to a to detect this situation. The result of running a pointer off the beginning of an array is (and always has been) undefined. On some segmented machines, this can and does cause trouble. -- The dream *IS* alive... | Henry Spencer at U of Toronto Zoology but not at NASA. |uunet!attcan!utzoo!henry henry@zoo.toronto.edu
bright@Data-IO.COM (Walter Bright) (11/01/88)
In article <7421@ihlpl.ATT.COM> knudsen@ihlpl.ATT.COM (Knudsen) writes: >In article <8775@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn ) writes: >> (But don't write something like >> for (p = &a[j]; --p >= a; ) >> which is nonportable.) >Why not portable? If a was created by a call to malloc, and (sizeof(a[0])>2), then on the 8086 in large memory model, p can NEVER be less than a! The trouble results from malloc creating a segment for a. Decrementing p past a causes a segment wrap, exactly like decrementing an unsigned variable past 0. This behavior is allowed for by ANSI C, and is the most reasonable way of doing things on the 8086.
pjs269@tijc02.UUCP (Paul Schmidt ) (11/01/88)
After working for a year to optimize a DBMS I
have some comments on writing efficient code.
"More harm has been done in the sake of
efficiency than any thing else."
When I was optimizing I found some horrendous
"efficient coding" practices that were used that
made the code either less managable, less efficient
or both.
Take, for example, my favorite:
some_function(a_variable)
short a_variable;
The coder (who was inexperienced in C) wanted
to optimize the space needed to save the parameter
passed to the function. This actually may add to
the memory and time to do conversion between short
and int.
The worst violation of coding for efficiency
was done in assembler. The person set a condition
bit inside a subroutine. After the return the bit
was used in a conditional jump. Of course, another
programmer saw the subroutine and couldn't under-
stand why there was an unneeded operation in the
subroutine and removed it.
The time spent coding a project is only about
10%. The maintenance phase lasts around 50% of a
project. If the coders write the most readable
code for the maintenance, the entire project cost
can be reduced.
But there is still a need for optimization.
This should be done after the code is written and
working. Why? Because the amount of time spent
in each code segment varies widely. There is no
reason to optimize the initialization routines if
they are only run once and are fairly fast
already.
Using prof(1) under UNIX I have always been
suprised at where the time is spent for a given
program. And using this shows which routines
need to be optimized. Using a benchmark it was
easy to see that only 10% of the routines were
run 90% of the time. Some of the results showed
obvious duplication of calculations that were
easy to eliminate. But instead of trying to
find them by hand, we let the computer show us
where they were. After changing the obvious
problems, there were many low level optimizations
that were done. Some included calculating
certain variables once and storing them as
globals while others were to make certain
variables declared as register. At one point it
became obvious that the semaphore routines
supplied by UNIX took 25-50% of the total time
to do a database retrieve. (This was solved by
making ownership of relations, and removing the
need to call the semaphore routines.) All through
the optimization process we were aware of what
was the most important code to optimize so we
could, as our boss always put it, "Get the
biggest bang for the buck."
For less experienced C programmers, try
running prof on a program and see which routines
are actually taking the most amount of time.
Prof will order the output from the most used
routine to the least and give the percentage of
time spent in each routine. I copied this prof
output from July 87, 1987, p 588, on profilers:
%time cumsecs #call ms/call name
82.7 4.77 _sqrt
4.5 5.03 999 0.26 _prime
4.3 5.28 5456 0.05 _root
2.6 5.43 _frexp
1.4 5.51 __doprnt
1.2 5.57 _write
...
This is for a program to compute prime numbers:
root(n)
int n;
{ return (int) sqrt((float) n); }
prime(n)
int n;
{ int i;
for (i = 2; i <= root(n); i++)
if (n % i == 0)
return 0;
return 1;
}
main()
{ int i, n;
n = 1000;
for (i = 2; i <= n; i++)
if (prime(i))
printf("%d\n", i);
}
It is interesting to see that the square root
calculation takes this much time for a function
and is not needed to calculate primes. It was
probably an "optimization" to make the search
for primes quicker.
In conclusion, I would like to stress that
readability for the maintenance phase should
outweigh the importance of optimizing code as
it is written. Easy to read code is easier to
maintain, and easier to optimize.
Paul Schmidt
Texas Instruments
PO Drawer 1255, MS 3517
Johnson City, TN 37605-1255
mcnc!rti!tijc02!pjs269leech@tlab1.cs.unc.edu (Jonathan Leech) (11/02/88)
In article <273@tijc02.UUCP> pjs269@tijc02.UUCP (Paul Schmidt ) writes: > Using prof(1) under UNIX I have always been suprised at where the > time is spent for a given program. And using this shows which > routines need to be optimized. Using a benchmark it was easy to see > that only 10% of the routines were run 90% of the time. There are certainly counterexamples. I have occasionally profiled the text editor I maintain. No one procedure took more than 3% of execution time. -- Jon Leech (leech@cs.unc.edu) __@/ ``It seemed to him that in addition to being beautiful she brought out all that was best in him of intellect and soul. That is to say, she let him talk oftener and longer than any girl he had ever known.'' - P. G. Wodehouse
bill@twwells.uucp (T. William Wells) (11/02/88)
In article <8775@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: : In article <119@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes: : >It's the damnedest thing, but people whose opinions I otherwise : >respect seem to have this thing about coding efficiently. They don't : >like it. Worse, they discourage it. : : I think it would be more accurate to say that we want to discourage : excessive concern with microefficiency to the detriment of other : important attributes of source code. Put that way, it is adifficult to argue the other side. Obviously, it is not good to write "efficient" code that is not understandable. I recall writing, early in my programming career, a few lines of assembly code that did a real neat (and efficient) trick. Unfortunately, this code was sufficiently tricky that when it came time to make a minor change to it, I could no longer figure out what it did! Of course, it got rewritten. This excessive "efficiency" is unarguably bad. However, anti- efficiency types (or so they appear) have taken this too far in the other direction. The kind of thing I do is mostly attention to detail; the algorithm remains the same, and the broad structure of the program remains the same. What is different are the coding details. In fact, what we are talking about is mostly a matter of "style". However, style does not exist in a vacuum; one chooses a particular style because it serves some purpose(s). Certainly, a style must be clear: this implies a consistent method of expressing algorithms coupled with an eye for laying out the code on the page. Certainly a style must be portable: this means leaving out things that don't go wherever the program might be ported. And just as certainly, a style should get the job done as efficiently as possible: this means choosing the details of how the thing is to be coded to be as likely as possible to be efficient. These goals aren't entirely consistent; that implies that a coder is going to have to make a trade-off whose details will depend on the circumstances. : >2) "What is more efficient on one machine may well be less efficient : > on another." Well, this is a good argument for knowing a lot of : > different machines and adapting one's coding style to the relevant : > machines, .. : : Actually the force of this argument is stronger if you already : appreciate the value of coding for reasonable behavior on almost : any C implementation, rather than "optimum" behavior on just one. Actually, one of the nicenesses of C programming is that reasonable behaviour is very easy to get: most C operations have a small cost. However, they do not have equal costs, and sometimes it is reasonable to make generalizations of the form: "On machines X where efficiency is of greater concern to me, doing it by method A is usually more efficient than doing it by B." When such generalizations are possible, one should take advantage of them. : Some people really may never port their code outside the first : system it's compiled for, but many of us do and we simply don't : have time to fine-tune the code in each environment (unless we : will personally accrue enough benefit to justify it). My own : time is worth much more than any computer's. Some people have their code ported damn near everywhere. For example, the spelling software I was responsible for a few years ago runs on everything from 8086's to IBM-370's. (This is not to say that there weren't portability problems: e.g., we had to write a program to preprocess character strings into \nnn so that it would run on non-ASCII machines. This was a case where clarity conflicted with portability.) However, it was not hard to figure out a reasonable set of generalizations and then apply them; after all, on which machines would it matter most how fast the program is: the micros with an impatient user waiting in front of them, or the mainframes with lots of horsepower? Of course, I coded it with efficiency on the micros as the greater concern. : >3) "Efficient coding makes obscurer programs." : : Certainly going overboard with microefficiency tweaks does. Moderation in all things, especially moderation! :-) : > for (i = 0; i < a[j]; ++i) ... : >into : > for (i = 0, ilast = a[j]; i < ilast; ++i) ... : : In most cases, the following can be used: : for (i = a[j]; --i >= 0; ) : which is more efficient and clearer. Right. And I use the latter whenever possible; however, it does not preserve the semantics of the original loop. (I just realized that I probably should have added a caveat that the transform is invalid if j is changed in the loop. This applies to both versions, though.) : (But don't write something like : for (p = &a[j]; --p >= a; ) : which is nonportable.) I'll remember! :-) Eh, Chris? : > for (i = 0; i < ALAST; ++i) { : > ... A[i]; : > } : > : > for (ap = A; ap < &A[ALAST]; ++ap) { : > ... *ap; : > } : > : >I write it this second way, as a matter of course, because I thought : >about it for a while and decided that this was the appropriate way to : >do it. I then trained myself into the habit of doing it this way. : : This makes a good example of the dangers of overconcern with such : matters. There are quite a few compilers that, in many cases, will : generate much better code for the first method than for the second, : because they can recognize an opportunity to use vector instructions. : Others will generate essentially the same code for the two methods. Why did you say this? I thought I had made it clear that I am well aware of the differences in compilers and they systems they run on. I thought I had made it clear that different situations require different choices in one's code. However, it appears that I have failed to communicate. How? Until I understand where the failure of communications is, I'll let this one drop. : Unless the situation is naturally thought of as involving a pointer : (for example, to a structure member of an array), it may be clearer : to treat array elements as array elements. "Naturally?" At least for me, a pointer into an array is neither more or less "natural" than an index into the array, I'll use either, as the situation requires. : >... dividing positive numbers by powers of two should be done with a shift. : : No! Juggling the source code to use bit-oriented operations in an : arithmetic context not only makes the code less portable and harder : to maintain, it can also lead to future errors, when for example a : chunk size is changed to a variable rather than a constant, or to a : non-power-of-two. Less portable? If a compiler doesn't take my n >> m (n >= 0, m < 16) and do the same thing as when dividing it by 2**m, the compiler is broken. Now, there might be some compilers that are broken that way, but that makes it an individual decision as to whether one panders to the frailties of those compilers. For the record, the spelling code I earlier mentioned does this in a few places and I've never heard of a problem relating to it. Harder to maintain? There is something there: if one has a number n, one has to have a second number representing log2(n); that is a cost. But that is a minor one. There is also the fact that if the number ceases to be a power of two, all references to the log have to be changed, but that is mechanical and so another minor cost. Lead to future errors? Only when done wrong. When I do it, it gets done this way: #define BLOCK_BITS 9 #define BLOCK_SIZE (1 << BLOCK_BITS) This is a clear signal (which can be reenforced by a comment) that BLOCK_SIZE is supposed to be a power of two. Changing it to a variable shouldn't cause any problems: all one needs to do is introduce two variables. If the size becomes other than a power of two, this is easily enough dealt with: it is clear that the program is depending on the existence of BLOCK_BITS; an instant's thought will tell the maintainer that he has got to do something about all references to BLOCK_BITS; such will certainly include all the >> BLOCK_BITS stuff. So, I disagree. : >Unless, of course, the programmer remembered to COMMENT. : : Comments don't necessarily track the code, Let's see: "Comments don't necessarily track the code, therefore you shouldn't do something (coding `tricks') where that tracking is important." Sounds more like an argument for more care in commenting, not an argument against coding "tricks". The failures that are possible in a system which are caused by carelessness by the users of the system are arguments for teaching the users how to better use their system, not arguments for discouraging particular uses of the system. Or even better, for improving the system (but that is a completely different can of worms. :-) : and it is unrealistic to : expect every use of the kind of tricks you advocate to be commented. Can you say "straw man"? It is not usually necessary to comment such "tricks". There is nothing about a counted-down for loop that requires a comment. There is nothing about a redundant calculation that gets eliminated that requires a comment. There are situations where a comment is desirable; however, even better is a method like the one I showed for replacing division by shifting: when the code is changed so that the trick doesn't work, one is forced to fix the places where the trick is used. --- Bill {uunet|novavax}!proxftl!twwells!bill
smryan@garth.UUCP (Steven Ryan) (11/02/88)
>>Realloc has to copy data, so this should be less efficient than just >>doing another malloc & free. > >Err, umm, "realloc" is often used when you have e.g. an array with N ERRR, UMMMM, we seem to have lost the point here. It sounds as though someone's guessing what the data structure size should be, guesses wrong, and has to increase it. If data structure size keeps getting bumped bit by bit until the problem size is finally determined, then we've got an O(n) structure which has been copied O(n/increment)=O(n) times so that the cost of creating just this structure is O(n**2) so that the overall time is quadratic, at best. This sounds more like someone's using an inappropriate data structure which is going to cost far more than any amount tweaking is going to get you. Tweaking a program gives at best linear improvement. Fixing the basic algorithm gives at least linear improvement. -------------------------------------------------------------------------------- Well, gee, how do you allocate an indefinite sized array? Glad you asked. I stuff it down a stack, each element individually handcrafted with malloc, until I've reached the end and know exactly how big it is. Then, IF I need random access, I copy it to an array. Linear time.
bill@twwells.uucp (T. William Wells) (11/02/88)
One of the things about Usenet that is very unfortunate is that mere agreement isn't worth commenting on (and wastes bandwidth). So, while some of my replies are a bit harsh, do keep in mind that there is also a lot which I agree with in that posting. In article <7700@bloom-beacon.MIT.EDU> scs@adam.pika.mit.edu (Steve Summit) writes: : In article <119@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes: : >It's the damnedest thing, but people whose opinions I otherwise : >respect seem to have this thing about coding efficiently. They don't : >like it. Worse, they discourage it. : : Some time ago I came to the conclusion that the style vs. : efficiency debate is another religious war, which I usually try : to stay out of. Good style and, I'll admit it, anti-efficiency : is a personal crusade, though, so I can't help but respond. But I think you mostly missed my point. One could approximate it with: "Efficient code IS a matter of style." Most of what I advocate is choosing a consistent style that is also reasonably efficient. While you seem to agree with this, you also directed much of your discussion to code-tweaking, a thing which I agree should be done after one has discovered a need for greater efficiency. These are two separate issues, and I wish you'd have addressed the former and not the latter. : None of this should be taken as a personal attack against Mr. : Wells, or anyone else, for that matter. His points are well : taken; I simply have a different point of view, going back to : first principles, as all good religious wars do. Perhaps we should discuss those "first principles". I had been composing an article on them,, but I decided that I didn't really have the time for it. Anyway, here are mine: 1) Programming is a *utilitarian* art. If the program doesn't do the intended job, it is a bad program. This is the overriding standard by which one judges a program. Portability ranks up here, as a program is portable because it can do the job when moved to another machine. But because portability ranks here, there is also a limit on meaningful portability: if the program isn't going to be ported then who cares if it can be ported? 2) Programs have to be read and maintained by humans. This implies modularity and a clean and consistent coding style, and for procedural programs, a structured program. This is a secondary standard. This is important because it makes it easier to fix bugs and to add to the jobs the program can do. 3) Programs should consume as little resource as possible. Programs that consume excess resources waste resources of the user, and may also impact other users of a multi-user system. In the extreme case, an inefficient program can be unusable. This too is a secondary standard. 4) Programming is a utilitarian *art*. Be that as it may, and while this may contribute to improving the program according to the other standards, this is less important than all other considerations. Esthetics is just not that important compared to efficiency or maintainability, unless it contributes to one or the other. Any real disagreement? : >I advocate training oneself to be one who codes efficient programs. I : >do not mean writing code and then making it more efficient, I mean : >writing it that way in the first place. : : Here I agree with at least some of the words, but not the : implications. It happens that I usually write nice, efficient : programs, but not by resorting to microefficiency tweaks or by : sacrificing readability in any way. It is important to employ : lots of common sense (and, of course, "common sense isn't"); to : shy away from grotesquely inefficient algorithms; and to partition : the code so that key sections can be cleanly replaced later if : efficiency does prove to be an issue. It isn't important to : write every last expression and statement in the most : theoretically blistering way possible. But who said anything about "ideal"? Not me! What I want is enough attention to detail so that the code is reasonably efficient to start with. A side benefit of this attention to detail is that one often discovers bugs in the code, thus saving later pain. : >3) "Efficient coding makes obscurer programs." Well, since most : > efficient coding involves minor changes from the inefficient way : > of doing things, changes which are mostly a matter of style rather : > than of organization... : : I don't know what is meant by "most efficient coding." The : interpretation "the most efficient coding involves the most minor : changes" is probably not the one that was intended, although I : like it, because taken to its extreme it says not to make any : changes at all. Oh dear, a semantic problem. Part of it is in the use of the verb "code" which, to me, refers to the last phase of writing a program: the transcription of what you want to do into something the computer understands. ("Writing a program" is the phase of getting the damnthing out just before "making it work".) So, to me, coding doesn't have much lattitude: it presumes that the overall structure of the program has already been decided, that the major data structures are mostly decided, etc. The other part is "changes". This is intended as a comparative, not as implying that one should actually change ones code in conformance with my idea of efficient coding. To repeat, one should write it that way in the first place. : I cannot agree with the more likely : interpretation. The minor changes, the replacements of : multiplies and divides by shifts and the like, are mostly noise : (both with respect to efficiency and style). The evidence is against you there: 10-25% improvements are not "noise". : The really big : efficiency hacks, the ones people spend weeks and months on, do : involve massive organizational changes and wholesale concessions : to readability and maintainability. I am not talking about such things, nor do I advocate doing such, except when the program isn't fast enough. : > ...this argument should really be read: "*I* : > don't like to or find it hard to read that kind of program, so it : > is unclear." : : The attitude of most C experts is "*I* don't have any problem : reading this code; anyone else who considers himself a Real C : Programmer shouldn't, either." This attitude is patronizing and : wrong. Cut the BS. While I have beliefs that could be approximated by your nasty remark, they are not the same. You apparently think that it is proper for a programmer to constrain his style to one that poorly trained programmers will have no trouble with. This kind of attitude is not useful. Rather, when we encounter a programmer who can't understand a good coding style, we should make sure that he gets taught. That is what we do where I work and so that is how I will code when working here. As for my personal stuff, I don't care that the untrained of the world can't read it. Call that patronizing if you will. I call it having high standards. : To borrow a previous argument, "We have to code in the : real world, not the world of make-believe." There are plenty of : people out there who are still learning C, So teach them right! : and since C has become : as popular as it has and C programmers are in demand, many of : them are working for real companies writing (and maintaining) : real programs. Hmmmm. Most programmers come into the real world completely unable to program. All they have is a little knowledge, and very little experience. Since they can't write programs well, we should be very careful that they don't see examples of good programs, since they might have problems reading them. That way they won't have to learn how to write such programs. :-) sort of. : >Avoid excess function calls. A lot of people have been brainwashed by : >some modularity gurus into believing that every identifiable "whole" : >should have its own function. What I have found is that this makes : >the program LESS maintainable than otherwise. : : Here's another religious debate: the structured programming one. I think you missed the point. Structured programming is essential to good procedural programming. I am saying that excessive partitioning not only makes the code less efficient but is actually contrary to the purposes for which structured programming exists. So this is a win all around. : There are a few applications (and, some believe, a few : architectures) for which function call overhead is significant, : but they are infrequent, and in general there should be : absolutely no stigma attached to a function call. My particular comment was directed at the following kind of programming: (This was a real program. Only the names have been changed....) string_diddling_function(in, out) char *in; char *out; { char temp[MAXSTRING]; /* comment 1 */ diddle_1(in, temp); /* comment 2 */ diddle_2(temp, out); /* comment 3 */ diddle_3(out, temp); /* comment 4 */ diddle_4(temp, out); } /* Each diddle had about this degree of complexity: */ diddle_1(in, out) char *in; char *out { while (*in) { if (*in == '`') { ++in; } else { *out++ = *in++; } } *out = 0; } The whole thing was unreadable! Not only that, but 40% of one program (patgen) was spent in just this set of routines. Ugh! : >: o Avoid bit fields, most especially signed ones. : >Try: don't use them at all, they tend to be nonportable. : : This is a side question: what's so unportable about bitfields? Signedness of the bit fields, for one thing. As I understand it, compiler writers have chosen to implement them as either signed or unsigned according to their own whim. Also, it used to be the case that a number of compilers either didn't implement them or did them incorrectly. It may still be. That, plus the frequent relative inefficiency of these compared to do-it-yourself bit fields, makes them undesirable. : >: o Use realloc instead of malloc/free pairs. Use calloc instead of : >: malloc followed by zeroing each member. : >Efficient memory allocation is *much* more difficult than this, what : >you really need to do is to cut down on the number of calls to malloc : >and free. Of course, that usually means writing some kind of : >allocation stuff yourself, never an easy task. : : Please don't avoid malloc; the alternative is generally : fixed-size arrays and "lines longer than 512 characters are : silently truncated." Please don't roll your own allocation : routines, again unless you have to; this is the kind of low-level : dirty work, hard enough to do well, that you should let the lower : levels (i.e. the standard implementations of malloc) give it : their best shot. My original understanding was that someone was advocating something like changing: thing1 = malloc(size1); ...finish using thing1 free(thing1); thing2 = malloc(size2); into: thing1 = malloc(size1); ...finish using thing1 thing2 = realloc(thing1, size2); I now suspect that I am the only person who read it that way, so most of what I said is irrelevant. However, what I said about rolling your own memory allocation still stands, but let me clarify this. I don't mean writing a malloc replacement, but rather an interface to malloc. One should always write such an interface, in order to handle memory allocation failures, unless one want's to check the return value of each malloc call. Here is an (untesetd) example of what I mean: typedef struct MYSTRUCT { struct MYSTRUCT *my_next; /* a general link */ char *my_field1; float *my_field2; } MYSTRUCT; MYSTRUCT *Free_mystruct; /* A list of currently unused MYSTRUCT's */ /* Everyone gets to malloc through here. It tries to malloc, but if that fails, frees whatever is on the free list(s) and then tries again. Repeated failure causes the program to exit. */ void * mymalloc(size) size_t size; { void *ptr; while (!(ptr = malloc(size))) { if (!Free_mystruct) { fprintf(stderr, "You lose: out of memory!\n"); exit(1); } while (ptr = Free_mystruct) { Free_mystruct = ((MYSTRUCT *)ptr)->my_next; free(ptr); } } return (ptr); } /* Call here whenever you want a fresh MYSTRUCT. */ MYSTRUCT * alloc_mystruct() { register MYSTRUCT *ptr; if (ptr = Free_mystruct) { Free_mystruct = ptr->my_next; } else { ptr = mymalloc(sizeof(MYSTRUCT)); } ptr->my_next = 0; ptr->my_field1 = 0; ptr->my_field2 = 0; return (ptr); } Now, I can already hear the screams of "Unclean, unclean!!!!" from those who don't like my style of coding. Let's save bandwidth and not flame, OK? : Why does calloc exist? Of what use is it? : Why has ANSI legitimized it? In principle, it is equally useless : for clearing structures that contain floating-point fileds. Oh yes. I forgot about floating point. And I suppose the reason that ANSI left it around is the number of existing programs that use it. Me, I never have and never will. : >Unless, of course, the programmer remembered to COMMENT. : : If the code reads : : a &= 3; /* really a %= 4 */ : or : a &= 3; /* really a %= HASHSIZE */ : : and I do a global replace of 4, or re#define HASHSIZE, the : comment may not help. Yes, but writing an explicit constant is bad to start off with. It should be: #define HASHSIZE 4 /* A power of two, or else! */ a &= HASHSIZE - 1; : find code size far more frequently relevant in : practice (among other things, because of the aforementioned : pdp11). Remember that the classic tradeoff is between time and : space, so the fancy efficiency hacks often make the code larger. I believe that the "classic trade off" has almost nothing to do with coding. Except when using data to replace code, faster code is usually smaller and smaller code is usually faster. This is good news for coders! : I might also point out that the marketplace generally rewards the : product that comes out first, so if you can compress your : development schedule by using clean, straightforward design and : eschewing time-consuming and bug-prone efficiency tweaking, There you go again, attacking the wrong issue. Grrrrrr. : While these considerations are real, they should be viewed as : unfortunate and temporary limitations which will be resolved, : hopefully soon enough, at the root level, and not something which : we resign ourselves to working around forever, and which we get : so used to working around that the workarounds become part of the : language, persisting well beyond their need. These are what Fred : Brooks calls "accidental problems," and every programmer minute : and line of code spend catering to them is not being spent on : real problems. Keep dreaming. It is still the case that our customers don't like our products when they consume over 64K, even though many (most?) machines have *lots* more memory. It will always be the case that there is never enough to go around. : I'm not going to try to second-guess all of the replies I will : undoubtedly get from the efficiency aficionadoes out there, but : I will mention two things. Click, whoosh!!!!! :-) : I keep saying "don't do <something> unless you have to," by which : I mean after actual experiments on prototype code demonstrate : that there is a problem. The attitude of "don't worry about : efficiency until later" is frequently denigrated as leading to : unsalvageably inefficient code, because trying to patch in some : efficiency later is tantamount to a rewrite. Although this can : be true, the solution is to teach people good, responsible : programming practices early, avoiding gratuitous and unnecessary : inefficiency, without teaching them to "optimize too early." What in *hell* do you think I am advocating? It is very frustrating to see myself being misunderstood (ignored?) so thoroughly. : Responsible programming practices are just what the articles I am : reacting to are trying to formulate, and all I'm trying to do is : to draw the line a little more finely between what's reasonable : and what's overboard. But I think you rather failed. You fairly consistently attacked efficiency tweaking, and with arguments that are mostly relevant to that discussion. But, as you said, I am advocating what you called "responsible programming", and I'd have much rather seen discussion on that subject. Instead, I get what seems to be a disagreement with my position, but what is really a disagreement with a straw man. How can I answer that? What can we learn from that? : My second point, and the reason I'm taking : all of this time and space replying, is that people who are : learning programming (and we're all still learning programming) : are much more impressionable than you might think. There's : nothing wrong with this; it's actually refreshing given that it : is often supposed that people stop learning at around age 20. : But it does mean that if you unilaterally tell a reasonably green : programmer to use pointers instead of arrays, he'll spend months : having lots of frustrating problems with pointers, and likely end : up hating them and the language in general. Did I anywhere do anything like that? I believe that I prefaced my remarks with an awful lot of "but consider your particular circumstances first". Sigh. I *hate* being misunderstood. --- Bill {uunet|novavax}!proxftl!twwells!bill
ok@quintus.uucp (Richard A. O'Keefe) (11/02/88)
In article <1709@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: [the context is realloc()] >It sounds as though someone's guessing what the data structure size should >be, guesses wrong, and has to increase it. If data structure size keeps >getting bumped bit by bit until the problem size is finally determined, >then we've got an O(n) structure which has been copied O(n/increment)=O(n) >times so that the cost of creating just this structure is O(n**2) so that >the overall time is quadratic, at best. Not so. The standard technique is to increase the size by a MULTIPLICATIVE factor, not an additive increment. The best factor is data-dependent; I tend to use 1.5 because that's what InterLisp used, 2 is pretty popular. The total cost in this case remains O(N), N being the final size.
rkl1@hound.UUCP (K.LAUX) (11/03/88)
In article <136@twwells.uucp>, bill@twwells.uucp (T. William Wells) writes: | In article <8775@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: | : In article <119@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes: | | : >... dividing positive numbers by powers of two should be done with a shift. | : | : No! Juggling the source code to use bit-oriented operations in an | : arithmetic context not only makes the code less portable and harder | : to maintain, it can also lead to future errors, when for example a | : chunk size is changed to a variable rather than a constant, or to a | : non-power-of-two. | | Less portable? | | If a compiler doesn't take my n >> m (n >= 0, m < 16) and do | the same thing as when dividing it by 2**m, the compiler is | broken. Now, there might be some compilers that are broken | that way, but that makes it an individual decision as to | whether one panders to the frailties of those compilers. For | the record, the spelling code I earlier mentioned does this in | a few places and I've never heard of a problem relating to it. | I'm suprized that noone has questioned the validity of shifting instead of dividing by (powers of) 2. What about the difference between Logical and Arithmetic shifts? If you want to divide, then divide! A lot of compilers are smart enough to implement the divide as a shift, but only where appropriate. I *did* notice the condition of dividend being positive, but now you have to *guarantee* that it will always be positive. Also, by implication, the dividend is a *signed* quantity. You can get into trouble if it gets changed to an *unsigned* quantity (like when 16K isn't enough). As for the 'compiler being broken' if it doesn't do the same thing for a shift and dividing, this is not true. In one case, you only told it to shift, the other to do a divide: they made be *equivalent*, but they certainly are not *equal*. So, please, if you *functionally* require a divide by (powers of) 2, code it as a divide and let the compiler *implement* it (maybe optimization needs to be turned on). --rkl
gwyn@smoke.BRL.MIL (Doug Gwyn ) (11/03/88)
In article <137@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes: >#define HASHSIZE 4 /* A power of two, or else! */ To continue my complaint against using bitwise operators where arithmetic is called for, let me point out that most reasonable hashing schemes work best of the hash table size is NOT a power of two. Now, if you had used arithmetic instead of bit-diddling throughout your hashing code, most likely a programmer could change HASHSIZE to some useful number like 113 and that would be all it would take to improve the hashing scheme. On the other hand, your code would force him to either use 128 (and obtain suboptimal performance), or else go through the code and try to put it back in the shape it should have had from the outset. Again, this is a case that any decent compiler would have been able to handle just as well if you had used division and remainder operators. The trickery is not only unnecessary, but (as I said previously) it gets in the way of code reliability and maintainance.
bill@twwells.uucp (T. William Wells) (11/03/88)
In article <273@tijc02.UUCP> pjs269@tijc02.UUCP (Paul Schmidt ) writes:
: When I was optimizing I found some horrendous
: "efficient coding" practices that were used that
: made the code either less managable, less efficient
: or both.
:
: Take, for example, my favorite:
:
: some_function(a_variable)
: short a_variable;
Here you are just demonstrating my point: had the programmer been
trained to write efficient code, he'd have known that, in general,
one doesn't declare short arguments (or float or char, for that
matter).
I'll repeat myself: I am not advocating optimizing one's programs, I
am advocating learning the coding techniques which generally result
in efficient code and applying them consistently.
: The coder (who was inexperienced in C) wanted
: to optimize the space needed to save the parameter
: passed to the function. This actually may add to
: the memory and time to do conversion between short
: and int.
Actually, declaring the thing short would not have been likely to
save any stack space: the caller almost always has to push an int.
(Except in ANSI C when there is a prototype, or in the unusual case
that the compiler can do inter-function optimizations.)
: The worst violation of coding for efficiency
: was done in assembler. The person set a condition
: bit inside a subroutine. After the return the bit
: was used in a conditional jump. Of course, another
: programmer saw the subroutine and couldn't under-
: stand why there was an unneeded operation in the
: subroutine and removed it.
Sounds to me like a documentation error: that returned bit is part of
the interface and should have been documented as such. Thus the error
you use as an example of bad coding for efficiency's sake is nothing
of the sort.
: The time spent coding a project is only about
: 10%. The maintenance phase lasts around 50% of a
: project. If the coders write the most readable
: code for the maintenance, the entire project cost
: can be reduced.
Here we get the same old argument, rehashed: "efficient code is
unreadable". It is not necessarily true. And in many cases, the
claim of unreadability is merely a demonstration that the reader does
not make it a practice to read that kind of code, rather than a valid
claim that the code is inherently unreadable.
I'll go even further: while there is code that is both unreadable and
efficient, the unreadability is more likely a consequence of the
programmer's inability or unwillingness to express himself properly
than a consequence of the code being written efficiently.
I'll even go so far as to say that efficiency antagonists compound
this. By setting up the false dichotomy of efficient vs. readable
code, they convince programmers that they can either write efficient
code or readable code, but not both. This merely makes people who
believe in efficiency give up the attempt to make their efficient
code readable. And, of course, their code is unreadable.
My own code is both efficient and readable. The former I know because
of testing; the latter because of feedback from people who have paid
money for it. So, I know that one can have it both ways.
: This is for a program to compute prime numbers:
:
: [code omitted, except for one line:]
: for (i = 2; i <= root(n); i++)
:
: It is interesting to see that the square root
: calculation takes this much time for a function
: and is not needed to calculate primes. It was
: probably an "optimization" to make the search
: for primes quicker.
It is more interesting to note that the simple discipline of avoiding
computing a thing more than once would have been sufficient to get
rid of most of the calls. Had the for loop been written
imax = root(n);
for (i = 2; i <= imax; i++)
two benefits would have been had. First, no time would have been
wasted waiting for or optimizing the thing. And second, the next
person who read the code wouldn't have to figure out that root(n) is
a loop invariant. (Trivial in this case, but not so in something more
complicated.)
: In conclusion, I would like to stress that
: readability for the maintenance phase should
: outweigh the importance of optimizing code as
: it is written. Easy to read code is easier to
: maintain, and easier to optimize.
Well, you said it, but you utterly failed to demonstrate it. All
that you have shown are examples of where bad programming leads to
unreadable code as well as inefficient code.
---
Bill
{uunet|novavax}!proxftl!twwells!billsmryan@garth.UUCP (Steven Ryan) (11/03/88)
>[the context is realloc()] > >Not so. The standard technique is to increase the size by a MULTIPLICATIVE >factor, not an additive increment. The best factor is data-dependent; I >tend to use 1.5 because that's what InterLisp used, 2 is pretty popular. >The total cost in this case remains O(N), N being the final size. However, this makes the space cost O(1.5**n), exponential.
seanf@sco.COM (Sean Fagan) (11/03/88)
In article <273@tijc02.UUCP> pjs269@tijc02.UUCP (Paul Schmidt ) writes: > > After working for a year to optimize a DBMS I >have some comments on writing efficient code. > Take, for example, my favorite: >some_function(a_variable) >short a_variable; > The coder (who was inexperienced in C) wanted >to optimize the space needed to save the parameter >passed to the function. This actually may add to >the memory and time to do conversion between short >and int. If I were to look at that, I would say that the coder used a short because he/she wanted to document the fact that the value was not expected to overflow a short. (is anybody following me? if so, could you explain it to me? 8-) Here's another shot:) I.e., "I don't expect the value to be larger than 32k-1 [on most 32-bit machines, for example]." It's what I would do. In the rest of the article, he only says one thing I really agree with: > But there is still a need for optimization. >This should be done after the code is written and >working. Why? Because the amount of time spent >in each code segment varies widely. Also, Paul advocates the use of prof. I agree (if anyones interested, there's a story I have about how profiling enabled someone to cut the execution time of a program from 9+ CPU hours on a Cyber [a *very* fast number cruncher] to about 2-5 minutes [on the same machine, of course]). Most programmers (in C) that I know tend to do some "microoptimizations" as they write (i.e., "a&0xf" instead of "a%16" type of thing). Afterwards, I (and they) tend to look at the program, try to understand what I wrote, and see how I can improve it (which isn't always easy). For me, this process is modified by how the compiler optimizes, and what the machine architecture I'm on dictates (I admit that I don't necessarily write portable, optimal code. Tough. 8-)). Basicly, what I'm trying to say is that not all microoptimization is bad. > Paul Schmidt > mcnc!rti!tijc02!pjs269 -- Sean Eric Fagan | "Engineering without management is *ART*" seanf@sco.UUCP | Jeff Johnson (jeffj@sco) (408) 458-1422 | Any opinions expressed are my own, not my employers'.
djones@megatest.UUCP (Dave Jones) (11/03/88)
Okay, I'll wade into the fray. But only up to my, er, toenails this time. Last time I ventured into a religious war, I was burned at the metaphorical stake, but I never converted by gum! No doubt this will have the same outcome. From article <8819@smoke.BRL.MIL>, by gwyn@smoke.BRL.MIL (Doug Gwyn ): > In article <137@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes: >>#define HASHSIZE 4 /* A power of two, or else! */ > > To continue my complaint against using bitwise operators where arithmetic > is called for, let me point out that most reasonable hashing schemes work > best of the hash table size is NOT a power of two. Perhaps most, but certainly not all. My favorite *requires* a power of two. One exception disproves the rule. But aren't we straying away from the subject? The subject is whether it is EVER okay to use >> to implement division by a power of two, not whether or not it is best, in some hypothetical case, to divide by a power of two or a by a prime number. > ... > Again, this is a case that any decent compiler would have been able to > handle just as well if you had used division and remainder operators. True enough. But what if you are programming for the new Banana 8000, and you don't have access to a "decent compiler", because there aren't any? Or, more to the point, what if the power of two you are dividing by is not a constant? I've got a hash-table package that has been working just fine, thankyewverymuch -- and fast as blazes -- in lots of applications written by lots of programmers, for about three years now. I expect it to live on indefinately. It uses a quick rehashing scheme, not chaining. It automatically doubles the size of the table when things get crowded. And yet entries can be efficiently removed on demand. It is the fastest hashing algorithm I know of. The speed of the division makes a difference. The table size is not a constant, but it's always a power of two. Has to be. I used a shift to divide by the power of two, and I'm not about to make it slower because of religious dogma. > The trickery is not only unnecessary, but (as I said previously) it gets > in the way of code reliability and maintainance. What trickery?
ok@quintus.uucp (Richard A. O'Keefe) (11/03/88)
In article <1718@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >>[the context is realloc()] >> >>Not so. The standard technique is to increase the size by a MULTIPLICATIVE >>factor, not an additive increment. The best factor is data-dependent; I >>tend to use 1.5 because that's what InterLisp used, 2 is pretty popular. >>The total cost in this case remains O(N), N being the final size. > >However, this makes the space cost O(1.5**n), exponential. No such thing. The space cost is O(N). What we're talking about here is a technique for maintaining dynamically sized data structures. Just to keep it simple: typedef <whatever> element; struct dynarray { unsigned limit; /* how many cells available */ unsigned count; /* how many in use */ element *table; /* the memory block */ }; int init_dyn_array(struct dynarray *p; unsigned initalloc) { element *table = (struct element *)malloc(initalloc * sizeof *table); if (table == NULL) return -1; p->limit = initalloc, p->count = 0, p->table = table; return 0; } element *dyn_array_elt(struct dynarray *p; int index) { return index < 0 || index >= p->count ? NULL : &(p->table[index]); } int push_dyn_array(struct dynarray *p; element new_value) { if (p->count == p->limit) { unsigned newlimit = p->limit*2; element *table = (struct element *)realloc(p->table, newcount * sizeof *table); if (table == NULL) return -1; p->limit = newlimit, p->table = table; } p->table[p->count++] = element; return 0; } These routines return -ve or NULL to indicate error. It is easy to see that if you build a flexible array by doing struct dynarray flex; if (init_dyn_array(&flex, 1)) abort(); ... for (...) { ... if (push_dyn_array(&flex, x)) abort(); ... } then the space required to hold N elements is at most 2*N*sizeof (element). This is O(N), not O(1.5**N) as Steve Ryan claims. If we assume that the cost of realloc(o,x) is at most O(x + size of o(x), it is straightforward to show that the time cost is also O(N) (basically, the latest doubling always dominates what has preceded it).
chase@Ozona.orc.olivetti.com (David Chase) (11/03/88)
In article <1709@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >It sounds as though someone's guessing what the data structure size should >be, guesses wrong, and has to increase it. If data structure size keeps >getting bumped bit by bit until the problem size is finally determined, >then we've got an O(n) structure which has been copied O(n/increment)=O(n) >times so that the cost of creating just this structure is O(n**2) so that >the overall time is quadratic, at best. First estimate is size k, too small, so we double it (etc) finally reaching size k*2^n. How many bytes have we copied? We've copied k + k * 2 + ... + k * 2^(n-1) = k * (2^n - 1). This is linear in the final size. We also did n allocations, but n is proportional to the log of the size (and bounded by 32 on most machines that I use) so we don't worry about the time spent allocating. "Efficient coding" is indeed harmful if you can't figure out the complexity of your algorithms. David
gregg@ihlpb.ATT.COM (Wonderly) (11/03/88)
From article <1709@garth.UUCP>, by smryan@garth.UUCP (Steven Ryan): >>>Realloc has to copy data, so this should be less efficient than just >>>doing another malloc & free. UMMMM, realloc() only moves things when it has to. >> >>Err, umm, "realloc" is often used when you have e.g. an array with N > > ERRR, UMMMM, we seem to have lost the point here. > > It sounds as though someone's guessing what the data structure size should > be, guesses wrong, and has to increase it. If data structure size keeps > getting bumped bit by bit until the problem size is finally determined, > then we've got an O(n) structure which has been copied O(n/increment)=O(n) > times so that the cost of creating just this structure is O(n**2) so that > the overall time is quadratic, at best. > > ..... > > Well, gee, how do you allocate an indefinite sized array? > > Glad you asked. I stuff it down a stack, each element individually > handcrafted with malloc, until I've reached the end and know exactly > how big it is. Then, IF I need random access, I copy it to an array. > Linear time. That is moving all of the data twice, but you are still doing more work than might be necessary for the simple case. The cost realloc()ing an array can be decreased by using incremental resizing where the increment is >>> 1. /* * addstr() * * Add a dynamically allocated string to a dynamically allocated array. * Input is the existing array pointer, the number of entries already * allocated, the entries used (current index) and the string to add. */ #define BIGINC 100 char **addstr (arr, acnt, cnt, str) register char **arr, *str; register int *acnt, *cnt; { register char *t; /* If space exhausted get some more. */ if (*cnt == *acnt) { /* If space allocated, realloc else malloc. */ if (!acnt) arr = (char **)realloc (arr, (*acnt += BIGINC) * sizeof (char *)); else arr = (char **)malloc ((*acnt += BIGINC) * sizeof (char *)); } /* Allocate space for the string. */ t = (char *) malloc (strlen (str) + 1); strcpy (t, str); arr[(*cnt)++] = t; return (arr); } Now, only if there are more than BIGINC entries will I have to realloc the array, and better yet, I didn't have to move the strings. And, only every BIGINC entries will I have to move the pointers... This method is extremely STRAIGHT FORWARD, and easy to understand. It does not involve lots of tricky programming to try and get around having to move the strings. -- Gregg Wonderly AT&T Bell Laboratories DOMAIN: gregg@ihlpb.att.com IH2D217 - (312) 979-2794 UUCP: att!ihlpb!gregg
ark@alice.UUCP (Andrew Koenig) (11/04/88)
In article <2730@hound.UUCP>, rkl1@hound.UUCP (K.LAUX) writes: > I'm suprized that noone has questioned the validity of shifting > instead of dividing by (powers of) 2. > > What about the difference between Logical and Arithmetic shifts? > If you want to divide, then divide! A lot of compilers are smart enough > to implement the divide as a shift, but only where appropriate. This correctly picks up a simple problem, but misses a deeper one: even if you use an arithmetic shift, shifting right one bit is still not equivalent to dividing by 2 if the dividend is negative, at least on machines that round the quotient toward zero. Example: on a 32-bit 2's complement machine, -1 is represented as 0xFFFFFFFF. Shifting right one bit arithmetically still gives 0xFFFFFFFF. Dividing -1 by 2, though, gives 0. It is true, however, that shifting an unsigned integer right is equivalent to dividing it by a power of 2. I would expect a good C compiler to recognize this equivalence and replace a division by a corresponding shift where applicable. Section 7.5 (page 90) of `C Traps and Pitfalls' has more to say about shifting and division. -- --Andrew Koenig ark@europa.att.com
bill@twwells.uucp (T. William Wells) (11/04/88)
In article <8819@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: : In article <137@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes: : >#define HASHSIZE 4 /* A power of two, or else! */ : : To continue my complaint against using bitwise operators where arithmetic : is called for, let me point out that most reasonable hashing schemes work : best of the hash table size is NOT a power of two. But there are also some that don't. : Now, if you had used : arithmetic instead of bit-diddling throughout your hashing code, most : likely a programmer could change HASHSIZE to some useful number like 113 : and that would be all it would take to improve the hashing scheme. But on quite a few of the hashing schemes that use a power of two, you *can't* change the number to anything other than a power of two. It breaks the algorithm. Actually, I almost agree with you here: if the hash method were not one where the size had to be a power of two, it would be incorrect to use bitwise operators. However, the mistake would have been in making the requirement that a tunable parameter which is not naturally restricted to a power of two be restricted to be a power of two. That mistake would then be compounded by taking advantage of the bogus restriction. (Ack, I *hate* subjunctives!) Formulated as a general principle: if an operand in a multiply or the divisor in a divide or mod (with the other operand being known to be a positive number) is one which in the problem being solved is naturally a power of two, it is reasonable to use bitwise operators to implement the operation, provided that a #define is used to define the number and (when needed) its log base 2. --- Bill {uunet|novavax}!proxftl!twwells!bill
news@rosevax.Rosemount.COM (News administrator) (11/04/88)
[profile of prime calculation] >%time cumsecs #call ms/call name > 82.7 4.77 _sqrt [in code] > for (i = 2; i <= root(n); i++) [note: root() calls sqrt()] sqrt() shouldn't dominate your profile so much after you take it out of the loop. This isn't fortran; root() is called on every iteration. True, some optimizations are maintenance pessimizations, but most C compilers can't tell when function calls can be optimized out. Thus the call for a "pure function" keyword (a function whose value is the same for the same arguments, with no side effects). > Paul Schmidt Merlyn LeRoy
desnoyer@Apple.COM (Peter Desnoyers) (11/04/88)
In article <1718@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >>[the context is realloc()] >> >>Not so. The standard technique is to increase the size by a MULTIPLICATIVE >>factor... I tend to use 1.5 ... >>The total cost in this case remains O(N), N being the final size. > >However, this makes the space cost O(1.5**n), exponential. No, max size <= 1.5N = O(N). There's a big difference between linear and exponential. Peter Desnoyers
jss@hector.UUCP (Jerry Schwarz) (11/04/88)
In article <624@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: > >What we're talking about here is a technique for maintaining dynamically >sized data structures. Just to keep it simple: It seems that way. So since this discussion has very little to do with C at this point perhaps it should be moved elsewhere. Jerry Schwarz
ps@celerity.UUCP (Patricia Shanahan) (11/04/88)
In article <8819@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >In article <137@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes: >>#define HASHSIZE 4 /* A power of two, or else! */ > >To continue my complaint against using bitwise operators where arithmetic >is called for, let me point out that most reasonable hashing schemes work >best of the hash table size is NOT a power of two. Now, if you had used >arithmetic instead of bit-diddling throughout your hashing code, most >likely a programmer could change HASHSIZE to some useful number like 113 >and that would be all it would take to improve the hashing scheme. On >the other hand, your code would force him to either use 128 (and obtain >suboptimal performance), or else go through the code and try to put it >back in the shape it should have had from the outset. >... Although I agree with most of what you are saying, it is not safe to assume that hashing schemes necessarily work better for HASHSIZE 113 than for 128. I did some experiments to select a hashing function for use in an assembler. I extracted all identifiers from several assembly language programs and measured the symbol table look up time and other statistics for each of the hash schemes that I was considering. Hashing with a prime size reduced the number of collisions. Hashing with a power of two size reduced the total time to do the symbol table management. The reason was that the extra time to do a prime division compared to a bit masking outweighed the small savings due to reduced search length. This is an empirical result, applicable only to the machine for which I was coding, and the type of mix of input strings that resulted from extracting the identifiers. I agree that micro-efficiency should not be considered during initial coding because of this type of experience. To do a good job of performance implementation for a particular machine requires a lot more work than appears on the surface. Many trade-offs require careful analysis or measurement for the actual machine. It is usually not worth doing for most functions. ps (Patricia Shanahan) uucp : ucsd!celerity!ps arpa : ucsd!celerity!ps@nosc phone: (619) 271-9940
tim@crackle.amd.com (Tim Olson) (11/04/88)
In article <8386@alice.UUCP> ark@alice.UUCP (Andrew Koenig) writes: | This correctly picks up a simple problem, but misses a deeper one: | even if you use an arithmetic shift, shifting right one bit is | still not equivalent to dividing by 2 if the dividend is negative, | at least on machines that round the quotient toward zero. | | Example: on a 32-bit 2's complement machine, -1 is represented as | 0xFFFFFFFF. Shifting right one bit arithmetically still gives | 0xFFFFFFFF. Dividing -1 by 2, though, gives 0. | | It is true, however, that shifting an unsigned integer right is | equivalent to dividing it by a power of 2. I would expect a good | C compiler to recognize this equivalence and replace a division | by a corresponding shift where applicable. A good compiler can also recognize a signed integer divided by a power of 2, and use the following trick: ;f(int a, unsigned b) ;{ ; int i, j; ; ; i = a/2; srl gr121,lr2,31 ; copy sign bit of a into lsb add gr121,gr121,lr2 ; add sign bit to a sra gr120,gr121,1 ; now we can divide by 2 (sra!) ; j = b/2; srl gr121,lr3,1 ; b is unsigned -- just shift ; return i+j; ;} -- Tim Olson Advanced Micro Devices (tim@crackle.amd.com)
ok@quintus.uucp (Richard A. O'Keefe) (11/04/88)
In article <10804@ulysses.homer.nj.att.com> jss@hector.UUCP (Jerry Schwarz) writes: >In article <624@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >>What we're talking about here is a technique for maintaining dynamically >>sized data structures. Just to keep it simple: > >It seems that way. So since this discussion has very little to do with >C at this point perhaps it should be moved elsewhere. I didn't intend to say any more about this, but I can't let "very little to do with C" stand. In any halfway decent programming language, flexible data structures should just be _there_ as part of the language, without requiring the programmer to kludge them up using unsafe operations (malloc(), free(), and realloc() are demonstrably unsafe: hacks to catch memory leaks have been discussed here several times). Given that C's claim to fame is giving you all the rope you need, and given that we have posters who evidently didn't _know_ how to maintain flexible arrays in C, I think there was some point in the discussion, and especially some point in exhibiting simple code to illustrate the technique. If we come right down to it, most of the raving that's been going on about efficiency hacks (desirable or not) was old news to Fortran programmers 10 years ago. Should that discussion be moved elsewhere? Well, I'm using my 'n' key a lot, but evidently there are people reading this group who care about it. It's their newsgroup too.
rob@raksha.eng.ohio-state.edu (Rob Carriere) (11/05/88)
In article <1718@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >>[the context is realloc()] >> >>Not so. The standard technique is to increase the size by a MULTIPLICATIVE >>factor, not an additive increment. The best factor is data-dependent; I >>tend to use 1.5 because that's what InterLisp used, 2 is pretty popular. >>The total cost in this case remains O(N), N being the final size. > >However, this makes the space cost O(1.5**n), exponential. Would someone explain where I am being dense? As far as I can see, you need to realloc ln N k = ------- ln 1.5m times, where m is the size of the initial allocation. Is this not O(ln N)? Rob Carriere
terry@wsccs.UUCP (Every system needs one) (11/05/88)
In article <7700@bloom-beacon.MIT.EDU>, scs@athena.mit.edu (Steve Summit) writes: > In article <119@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes: > >It's the damnedest thing, but people whose opinions I otherwise > >respect seem to have this thing about coding efficiently. They don't > >like it. Worse, they discourage it. Here here. > Some time ago I came to the conclusion that the style vs. > efficiency debate is another religious war, which I usually try > to stay out of. Good style and, I'll admit it, anti-efficiency > is a personal crusade, though, so I can't help but respond. Why is it that people assume good style and efficiency is mutually exclusive? This is a PC mentality. Good style is appropriate commenting, small program flow jumps (less than 2 pages, preferrably very much shorter than that), and portability. Style is often linked to which editor you use. For a UNIX environment, a good function declaration would be: type function() parameter declarations; { code code code } This allows searching for function names in a program with grep ^function *.c; it allows use of the [ and ] vi commands to jump through blocks of code; the type declarations before the function allow crosreferencing with a simple sgrep/awk combination. Unions should be avoided, as well as non-pre-aligned structures. If you must use a structure for othere than internal data representation, it should be aligned on longword boundries. if statements should look like: if( expression operator expression) rather than if (expressionoperatorexpression) which can break old compilers with either the space after the if or the runniong together of tokens such as =& and = &, =* and = *, etc. expressions where you are unsure of precedence should be paranthesized; if you are unsure of precedence, relearn your C. > I simply have a different point of view, going back to > first principles, as all good religious wars do. When caught > between a rock and a hard place, when something's got to give, > some people shrug their shoulders and sacrifice style, > modularity, or portability. I am prepared to sacrifice > efficiency. (Most of the time I can have my cake and eat it too, > and I have any number of general techniques for doing so, which I > will probably defer to a separate posting so that those who are > sensibly ignoring these diatribes can still see them.) usually, using an oblique "style standard" is what offends the portability gods, not efficiency. Being prepared to sacrafice efficiency on the alter of style is no way to maintain a market share. If it takes gross code to do something fast (code is usually called gross if it can't be understood by the reader, which is more a failing of the reader than a failing of the coder) you write gross code. The only thing to sacrifice efficiency to is the God of portability, and that's only if it isn't generally portable; if it can be made efficient and portable by two methods, ...well, that's why God invented #ifdef > >I advocate training oneself to be one who codes efficient programs. I > >do not mean writing code and then making it more efficient, I mean > >writing it that way in the first place. > > Here I agree with at least some of the words, but not the > implications. It happens that I usually write nice, efficient > programs, but not by resorting to microefficiency tweaks or by > sacrificing readability in any way. It is important to employ > lots of common sense (and, of course, "common sense isn't"); to > shy away from grotesquely inefficient algorithms; and to partition > the code so that key sections can be cleanly replaced later if > efficiency does prove to be an issue. It isn't important to > write every last expression and statement in the most > theoretically blistering way possible. Unless you are competing for a customer. Run cu for a terminal session or run uucp for a transfer and then run our stuff. Blisteringly fast means a savings in real dollars to a customer. Someone at Sun voiced this as a pro-tempe' justification for writing the SPARC compiler so it compiles benchmarks instead of code. > >I have heard three main counterarguments to this: > >1) "The compiler ought to handle that, so you shouldn't bother with > > it." What nonsense! We have to code in the real world, not the > > world of make-believe and ought-to. > > Many of the more egregious examples of source-level > microefficiency tweaking are, in fact, routinely handled by > today's (and even yesterday's) compilers. Consider replacing > power-of-two multiplies by left shifts, a textbook example. > I just booted up my pdp11 (I am not making this up), and its > optimizer knows how to shift left when I multiply by two. (To be > sure, not all newer compilers have been better.) It is sheer stupidity to depend on the supposed contents of a black box; for instance, a compiler. This generates non-portable and lazy coding practices "aw... the compiler'll make it fast..." > >3) "Efficient coding makes obscurer programs." Well, since most > > efficient coding involves minor changes from the inefficient way > > of doing things, changes which are mostly a matter of style rather > > than of organization... I disagree here; proper style is not necessarily efficiency; A program generator can do the work of 5 ordinary programmers; no code generator can replace one gifted programmer; that's why assembly language is still in use. > The really big > efficiency hacks, the ones people spend weeks and months on, do > involve massive organizational changes and wholesale concessions > to readability and maintainability. readability, yes; maintainability, not necessarily. But I submit that this loss of readability lies either in the lack of documentation (primarily in the form of appropriate/timely comments) or skill on the part of the reader. Ability to understand others code is the difference between a programmer and a person who can program. Writing code for idiots is only good if you are an idiot and can do no better, or if you are willing to hire idiots. This type of "communism of coding", where the tradeoff is always made for the less gifted programmer is what is currently threatening to move a lot of the more exciting/profitable/innovative coding offshore. A person who can program can not always read a programmers code. Tough. Hire a programmer instead of a code mechanic. This is why good programmers are worth 80K+ per year (if they are willing to work in the rigidly structured environment that entails; some intellectual freedom is worth at least 20K a year). > The attitude of most C experts is "*I* don't have any problem > reading this code; anyone else who considers himself a Real C > Programmer shouldn't, either." This attitude is patronizing and > wrong. To borrow a previous argument, "We have to code in the > real world, not the world of make-believe." There are plenty of > people out there who are still learning C, and since C has become > as popular as it has and C programmers are in demand, many of > them are working for real companies writing (and maintaining) > real programs. A beginning C programmer (say < 3 years if he isn't the type of person who stays up 3 days straight coding) can not expect to understand, let alone maintain, 65,000 lines of code, perhaps not even 8,000. To expect him or her to understand the UNIX kernel by writing it pretty is ignorance. To degrade your code (don't kid yourself; that's what it is) so that such a programmer (actually, at that point, they are "a person who can program") can understand it is marketing and technological suicide. It is the equivalent of redoing IQ tests so that 100 is average again. Saying someone is more intelligent doesn't make them so. Writing code so that someone at a lower knowledge (notice I did NOT say educational) level can understand it does not make the reader a better programmer. > A few painless concessions (like multiplying > instead of shifting, Thhhhhtp! Painless my arse. Look at the assembly with optimization turned off. An old compiler is like a new compiler without the optimization turned on. > (I maintain that every unnecessary > translation from an encoding back to an intended meaning, no > matter how intuitive to the experienced programmer, incrementally > increases comprehension time, effort required, and probability of > error.) There is some truth to this, but the key word is "unnecessary". It is also unnecessary for a computer programmer, whose first abstract concept should have been bits. If the person is a C programmer, the second an third concepts should have been Hexadecimal and Octal. Assuming that these operations haven't become automatic after experience is silly. It is equally silly to think of a programmer doing bit operations with multiplies instead of shifts! > If you leave the explicit n*n everywhere, this > error is impossible. So is speed. You have any idea how long a multiply takes on most architectures? I'll take the risk of having it blown out. If it gets blown out, I'll do another thing programmers should know how to do to deserve the name -- debug. > >Use register variables. And take a litle pain to get them right. A > >technique that works enough of the time is this:... Yes, register variables are a good idea, even if you have a fasciesticly optimizing compiler. > I'm sorry, I don't have spare time or spare brain cells for > following or utilizing a technique like this. Not to be rude, but it would do you good to deallocate some of your non-spare brain cells and realloc them to utilizing such things as register varaiables. > When I was a beginning C programmer, I decided not to use > register variables at all in the first pass of coding, because I > figured that, when I eventually got the program working, somebody > was going to say that it wasn't fast enough, and if I had already > blown all of my ammunition, how was I going to speed it up? This is at odds with your previous statement (which I agree with) of "code it right the first time". A properly written program can not be sped up without sacrificing an unacceptable degree of portability. > Lately I throw in "register" all the time, but in some ways I > respect my original attitude more. The point is, if it's the > sort of program that people notice how fast it is, they would > have complained even if I had used register variables since day > one. Bull pucky. > Here's another religious debate: the structured programming one. > Nevertheless, good modularity is the only way to keep a large > program maintainable. A correct statement. > Of particular pertinence to the theme of > this article is that efficiency-critical modules, if properly > isolated, can be implemented quickly and (possibly) inefficiently > first, while getting the program to work correctly at all, and > then transparently replaced later with a more efficient version, > if and only if it is found that the quick, inefficient > implementation is really too inefficient after all. Another way of looking at this is to rephrase it: "will my slacking off be discovered? If so, can I spend the time I should have in the first place to fix the problems I generated in slacking off?" This is slipshod and a very bad attitude. > If people have a bad impression of highly modular code, it is > because they (or, more likely, their predecessors) have used what > I call a "Ginsu knife" approach to modular decomposition, whereas > the correct instrument to use is a scalpel. If you went to a > lecture once on modularity but the only guideline you remember is > "50 source lines," you're going to use split -50 on your > monolithic source files, and not garner any of the benefits of > good modularity. If, on the other hand, you learn how to > modularize well, you just won't believe how easy your life (with > respect to software development and maintenance, anyway) will > become. Lo! Another correct statement! > There are a few applications (and, some believe, a few > architectures) for which function call overhead is significant, > but they are infrequent, and in general there should be > absolutely no stigma attached to a function call. It's usually > easy to back a function call out later, if you have to. Look at the clock-tick time on a proc call and push/pops on the 8086. > >: o Avoid bit fields, most especially signed ones. > >Try: don't use them at all, they tend to be nonportable. > > This is a side question: what's so unportable about bitfields? > Sure, the layout (left to right or right to left) isn't defined, > but that's only a problem if you're trying to conform to external > layouts, which is a "problem" with structures in general. (The > solution is neither "don't use bitfields" nor "don't use > structures" but "don't try to portably conform to external > layouts.") The ordering could also be a problem if the code > internally depended on it in some way, but this is no more or > less a problem than programs which depend on byte ordering > within words. Why use bitfields at all if they are simply internal representations? The insertion/extraction overhead far outweighs any memory advantages. If not, you should re-examine your basic data structures more closely. > Are there substantial numbers of real (not toy) C compilers that > either don't implement bitfields, or that don't implement them > correctly? ("Correctly" as defined by K&R and ANSI, not by some > program that is trying to use them nonportably.) Yes. > >: o Use realloc instead of malloc/free pairs. Use calloc instead of > >: malloc followed by zeroing each member. > >Efficient memory allocation is *much* more difficult than this, what > >you really need to do is to cut down on the number of calls to malloc > >and free. Of course, that usually means writing some kind of > >allocation stuff yourself, never an easy task. Agreed. I would add, however, that if you don't really need a calloc, using a malloc with a multiply is more efficient in that it does not have to generate a loop (or some other code) to clear the newly allocated area. > Please don't avoid malloc; the alternative is generally > fixed-size arrays and "lines longer than 512 characters are > silently truncated." Please don't roll your own allocation > routines, again unless you have to; this is the kind of low-level > dirty work, hard enough to do well, that you should let the lower > levels (i.e. the standard implementations of malloc) give it > their best shot. I can name 5 "real compilers" off the top of my head whose in-line expansion of memory allocation or whose standard library routines are broken. > >: Micro-efficiency gets regularly denounced. Here are some counterarguments: > >: o If your commercial product is slower than the competition, you > >: won't get a chance to take advantage of the maintainability/ > >: portability advantages because you'll be out of business. > >Or if it is larger. This discussion has focused on making programs > >faster, but making them smaller is also relevant. > > I agree, and find code size far more frequently relevant in > practice (among other things, because of the aforementioned > pdp11). Not to mention the Altos/Harris/SCO/MicroSoft medium-is-my-largest-model 8086 and 80186 Xenix's (Xenixi?). > I might also point out that the marketplace generally rewards the > product that comes out first, so if you can compress your > development schedule by using clean, straightforward design and > eschewing time-consuming and bug-prone efficiency tweaking, > you may come out ahead (and sew up your market share and your > pocketbook by releasing a speeded up version 2 six months later). I point at Lotus and snicke at the above paragraph. [discussion of memory model limitations] > While these considerations are real, they should be viewed as > unfortunate and temporary limitations which will be resolved, > hopefully soon enough, at the root level, and not something which > we resign ourselves to working around forever, and which we get > so used to working around that the workarounds become part of the > language, persisting well beyond their need. These are what Fred > Brooks calls "accidental problems," and every programmer minute > and line of code spend catering to them is not being spent on > real problems. Yes, but there are too many machines with these problems (unless you know something I don't about UCB coming out with new UNIX 7 and UNIX 7 compiler revisions :-). > I'll third the motion, but without the tweaks. My proudest code > is that which is not only small and fast and elegant and portable > and modular and extensible but also patently obvious in function > to the casual observer A casual observer has no place in a programming shop. > But it does mean that if you unilaterally tell a reasonably green > programmer to use pointers instead of arrays, he'll spend months > having lots of frustrating problems with pointers, and likely end > up hating them and the language in general. Or he or she will learn how to use them. I would rather have a programmer unwilling to learn something they don't know (although they'd damn well better know pointers; they're basic!) quit or be fired. Sorry to seem so hard on Steve, but the ideology embodied in his statements and statments that "the optimizer will take care of it" is so antithetical to programmerness that I had to say something. | Terry Lambert UUCP: ...{ decvax, uunet } ...utah-cs!century!terry | | @ Century Software OR: ...utah-cs!uplherc!sp7040!obie!wsccs!terry | | SLC, Utah | | These opinions are not my companies, but if you find them | | useful, send a $20.00 donation to Brisbane Australia... | | 'I have an eight user poetic liscence' - me |
bill@twwells.uucp (T. William Wells) (11/06/88)
Grrrrrrr........
In article <2730@hound.UUCP> rkl1@hound.UUCP (K.LAUX) writes:
: | : >... dividing positive numbers by powers of two should be done with a shift.
:
: I'm suprized that noone has questioned the validity of shifting
: instead of dividing by (powers of) 2.
No one has questioned it because, given the rider that *everyone* has
attached (the thing being divided being positive), it *is* valid.
: What about the difference between Logical and Arithmetic shifts?
There is none, for positive numbers.
: If you want to divide, then divide! A lot of compilers are smart enough
: to implement the divide as a shift, but only where appropriate.
And many are not. Worse, most frequently, the compiler can't
determine whether the number really is positive. In fact, only the
most advanced compilers are capable of this.
The exception to this is when the number being divided is declared
unsigned. So, the options are a cast which may or may not cause the
optimizer to do what one wants, or a shift which will.
: I *did* notice the condition of dividend being positive,
But you obviously decided to ignore the condition. Or you failed to
consider that it is a critical condition.
: but now
: you have to *guarantee* that it will always be positive.
So? If I can't determine correctly that such is true, I have much
worse problems than code which doesn't meet your approval.
: As for the 'compiler being broken' if it doesn't do the same thing
: for a shift and dividing, this is not true. In one case, you only told
: it to shift, the other to do a divide: they made be *equivalent*, but
: they certainly are not *equal*.
Go back to school. If they aren't equal, then they aren't equivalent.
If they are equivalent then the must be equal. Under appropriate
restrictions, a>>b and a/(2**b) are equal, thus equivalent.
: So, please, if you *functionally* require a divide by (powers of) 2,
: code it as a divide and let the compiler *implement* it (maybe optimization
: needs to be turned on).
So please, get your head straight, and learn to think, before
intruding your ignorance in the debates of your betters.
---
Bill
{uunet|novavax}!proxftl!twwells!billvfm6066@dsacg3.UUCP (John A. Ebersold) (11/08/88)
I have been following this for some time. My two cents... Balance all coding "tricks" against the need to produce readable and thus maintainable code. Get the code working properly first, make sure it can be read and understood by programmers less talented than yourself. Comment liberally, (the l-word and oh nooo the c-word), however do not re-state the obvious, e.g, #define EOF 0 /* ** Read until end of file (silly comment) */ while (fread != EOF) (Don't laugh, I've seen it done). Misleading comments are worse than no comments at all. If your algorithm requires five times as many lines of as the code - so be it. You may be immersed in it now, but try and remember what is going on six months from now - pity on the poor maintainer. The most important comments are those that give the BIG PICTURE, followed by those that show how the parts fit into the whole. Lastly, if it is too slow, profile it and fix the slow parts in a readable manner. Humbley (is that a word?).
knudsen@ihlpl.ATT.COM (Knudsen) (11/08/88)
In article <1630@scolex>, seanf@sco.COM (Sean Fagan) writes: > If I were to look at that, I would say that the coder used a short because > he/she wanted to document the fact that the value was not expected to > overflow a short. (is anybody following me? if so, could you explain it to > me? 8-) Here's another shot:) I.e., "I don't expect the value to be larger > than 32k-1 [on most 32-bit machines, for example]." It's what I would do. What I do for variables whose size I know is limited, but where I want to retain the efficiency of "int", is: typedef int sexy; and then declare such vars as sexy. This reminds me that these would fit perfectly well in a byte, but should be computed as int to avoid the oft-mentioned promotions to int. It's especially helpful if/when I rewrite a function in assembler, where the efficiency problem mostly goes away. If I got terrible strapped for data memory, I could change the typedef so that sexy was really char. This would expand and slow down the code, as others have noted. Some of you may have guessed I write for the 6809, whose SEX (sign extend) instruction is the mainstay of promoting bytes (chars) to 16-bit ints. Of course most of you are worried about 16-bit shorts and 32-bit ints, but the principle is the same. You may call your version "shorty" ... :-) My 6809 C compiler *is* smart enough to test chars as just one byte (no SEXing to int), so I typedef'ed "bool" to "char." BTW, a year ago there was a discussion about typedef'ing all sorts of custom types, and NEVER using the straight char/short/int/long types in your own code. I don't go this far, but I do have "byte" and "ubyte" and use "char" only for ASCII items; plus I have some custom "int" types like "index" and "time." But I use "int" for plain old loop counters and such. -- Mike Knudsen Bell Labs(AT&T) att!ihlpl!knudsen "Lawyers are like nuclear bombs and PClones. Nobody likes them, but the other guy's got one, so I better get one too."
krohn@u1100a.UUCP (Eric Krohn) (11/09/88)
In article <143@twwells.uucp> bill@twwells.UUCP (T. William Wells) writes:
]
] Formulated as a general principle: if an operand in a multiply or the
] divisor in a divide or mod (with the other operand being known to be a
] positive number) is one which in the problem being solved is
] naturally a power of two, it is reasonable to use bitwise operators to
] implement the operation, provided that a #define is used to define
] the number and (when needed) its log base 2.
Instead of #defining the log in terms of the number,
I prefer to #define the number in terms of its log base 2, as in
#define LOGSIZE 7
#define SIZE (1 << (LOGSIZE))
to insure that SIZE really is a power of 2 when I expect it to be.
For the safety conscious, you can add
#if LOGSIZE <= 0
#include "LOGSIZE must be non-negative"
#endif
#if LOGSIZE >= BITSPERWORD
#include "LOGSIZE is too large"
#endif
--
--
Eric J. Krohn
krohn@ctt.ctt.bellcore.com or {bcr,bellcore}!u1100a!krohn
Bell Communications Research, 444 Hoes Ln, Piscataway, NJ 08854dharvey@wsccs.UUCP (David Harvey) (11/09/88)
The recent postings on the net on this topic has prompted me to respond
about a teacher at our college (not necessarily reflecting the opinion
of all faculty members) who would fail me for the following code:
if( ! something) {
++j;
.
.
.
}
but would pass me with flying colors for the following:
if ( something != 0)
{
j = j + 1;
.
.
.
}
As a matter of fact, he would under no circumstances allow me to
use the '++', '--', '+=', '-=', '/=', '*=', or '%=' operators.
I would LITERALLY be failed if it were there. And yes, he feels
that Pascal is much better than C, and Modula2 better yet. In
other words, C does have philosophy of coding that emanates a
flavor of efficiency. Use it or lose it. By the way, another
teacher here loves ANSI C, and every 'enhancement' he mentions
smacks me of being Pascalish in orientation. For example, the
declaration of variables within the function parentheses will
provide the 'protection' that Pascal lovers want only if the
compiler can compile both the caller and callee at the same time.
Or the linker must be more sophisticated, using information that
is generated by the compiler. How will it be handled folks?
Either way we lose. If the compiler does it, there goes our
modular strategy of putting related functions in seperate files
from the functions that use them. But then we could always
#include C code files, which is exactly what one of the afore-
mentioned teachers required of beginning C students! But what
if I want to package a set of functions for users of equipment
I manufacture to connect to the computer and I don't want them
to have the source? Then the linker will have to do it. Will
that cost more for the compiler and linker? You bet your boots
it will! My point of view? If you want to program in Pascal,
Modula2, Ada, et al, by all means do so. But don't cram your
views that make a machine run slower down my throat! If I want
to do that I will use Lisp or Prolog where I get something back
for what I lost!
dharvey@wsccschris@mimsy.UUCP (Chris Torek) (11/10/88)
In article <23459@amdcad.AMD.COM> tim@crackle.amd.com (Tim Olson) writes: >A good compiler can also recognize a signed integer divided by a power >of 2, and use the following trick: [copy and add sign bit] It is worth noting that Sun's PCC-based compiler does something similar: f() { register i, j; ... i = j / 2; ... i = (unsigned)j / 2; ... } compiles (using the SunOS 3.5 compiler running under SunOS 3.2) to movl d6,d0 tstl d0 jge L2000000 addql #1,d0 L2000000: asrl #1,d0 movl d0,d7 (clearly not the best code in the world) and movl d6,d0 lsrl #0x1,d0 movl d0,d7 (why some constants in hex and others decimal we may never know :-) ). The optimiser transforms the latter to the more appropriate movl d6,d7 lsrl #1,d7 (yes, the 0x disappears). -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
ok@quintus.uucp (Richard A. O'Keefe) (11/11/88)
In article <764@wsccs.UUCP> terry@wsccs.UUCP (Every system needs one) writes: >if statements should look like: > > if( expression operator expression) >rather than > if (expressionoperatorexpression) > >which can break old compilers with either the space after the if or WHAT? I've used C under UNIX since version 6+, and various VM/CMS, 8086, and VMS C compilers, and I've _never_ run into one with THAT bug! The rule that I use is that "things which are similar should look similar, things which are different should look different"; if statements are not function calls, so they shouldn't look like them. Say "squodge 'if' up to the '(' and confuse the h--- out of readers because I _like_ it that way", but don't say that compilers were ever allowed to _demand_ it.
guy@auspex.UUCP (Guy Harris) (11/12/88)
>Either way we lose. "Either way" is generally used when there are two ways. There is a third way, which, although it may not catch type mismatches *all* the time, will probably catch a hell of a lot of them: put the prototypes into an #include file, and make sure the module that defines a function includes the #include file that declares that function. The compiler will complain if the prototype in the #include file does not match the prototype on the function itself. BTW, putting function declarations in an #include file is a Very Good Idea even if you don't have prototypes; without prototypes, you may not be able to declare the types of the arguments to the function, but you can declare the type of the function's return value, which is important.... >But don't cram your views that make a machine run slower down my >throat! I have yet to see any indication that adoption of stronger-type-checking notions in the dpANS will "make a machine run slower" by any significant amount. In fact, if prototypes had been there since Day 1 and had been the *only* way of declaring functions (this may perhaps have made the language too big for the PDP-11 to compile, I don't know - I'm not saying that this would necessarily have been the best thing), and if "varargs" or "stdarg" had been the only permissible way of doing variable-length-argument-list functions, calling sequences where the callee, rather than the caller, could safely have been used (since the compiler could feel reasonably confident that if a function expects N arguments of particular types, it will be passed just such a list of arguments), and it has at least been asserted that on some machines, such calling sequences are faster (e.g., the debates over the "C" and "Pascal" calling sequences on 80*86 machines). "Strong typing is for weak minds" is for weak minds.
nsw@cord.UUCP (Neil Weinstock) (11/12/88)
In article <771@wsccs.UUCP> dharvey@wsccs.UUCP writes: >The recent postings on the net on this topic has prompted me to respond >about a teacher at our college (not necessarily reflecting the opinion >of all faculty members) who would fail me for the following code: > >if( ! something) { > ++j; > ... >} > >but would pass me with flying colors for the following: > >if ( something != 0) > { > j = j + 1; > ... > } > >As a matter of fact, he would under no circumstances allow me to >use the '++', '--', '+=', '-=', '/=', '*=', or '%=' operators. I have heard this issue thrashed out before. I feel very strongly that the operators you list can *enhance* readability when used appropriately, and therefore I would assert that the teacher you refer to is extremely misguided (boy, I'm being nice). In general, when doing an increment operation or some such, I find it convenient to think of it as an operation on a variable, not as an assignment (fine shades of meaning, to be sure). C's various wonderful assignment operators reflect this naturally, and it is one of the many reasons I like C. This issue becomes important when you get big lvalue expressions: array[row*2+offset][col+loopvar] += 8; becomes array[row*2+offset][col+loopvar] = array[row*2+offset][col+loopvar] + 8; This is a contrived example, but I frequently encounter such stuff. I would assert that the first is infinitely more readable than the second. So, while the operators in question are certainly abusable, they have their place. It is difficult to imagine using C voluntarily without them, and I shudder to think of what some code would look like without them. .- -- .. --. .- .-. ..- .-.. . ... .- -- .. --. .- .-. ..- .-.. . ... | Neil Weinstock | att!cord!nsw | "I think my cerebellum just | | AT&T Bell Labs | nsw@cord.att.com | fused." - Calvin | .- -- .. --. .- .-. ..- .-.. . ... .- -- .. --. .- .-. ..- .-.. . ...
gwyn@smoke.BRL.MIL (Doug Gwyn ) (11/12/88)
In article <771@wsccs.UUCP> dharvey@wsccs.UUCP (David Harvey) writes: >... who would fail me for the following code: >if( ! something) { > ++j; >but would pass me with flying colors for the following: >if ( something != 0) > { > j = j + 1; If "something" is conceptually Boolean, then even your instructor should think !something is preferable to something==0 (note the bug fix) since his favorite languages have explicit Boolean NOT operators. On the other hand, if "something" is conceptually arithmetic, then something==0 is stylistically preferable to !something. ++ is obviously thought of as a unary increment operator, which those other langauges don't have (which is probably why your instructor is not comfortable with the idea). >declaration of variables within the function parentheses will >provide the 'protection' that Pascal lovers want only if the >compiler can compile both the caller and callee at the same time. >Or the linker must be more sophisticated, using information that >is generated by the compiler. How will it be handled folks? I see you don't understand how function prototypes work. (Perhaps this is due to your instructors also?) The compiler can (indeed, must) check function arguments and parameters against the corresponding prototype when it is in scope. Typically this occurs when a prototype declaration is supplied in an "interface" header file that is #included near the beginning of each source file that refers to things defined or declared by that header. >But then we could always #include C code files, which is exactly >what one of the afore-mentioned teachers required of beginning C >students! Obviously he has a Pascal mind-set. One of C's important features is the support for separate compilation. ANSI C's function prototypes in no way weaken this; in fact they better support it. No linker support is required beyond that required by "K&R C". ----- My advice to you as a student is to learn proper C usage from books by people like Brian Kernighan and Tom Plum. (There are other good authors of C books too, as well as scores of bad ones. I just picked a couple of the best.) Give your instructors whatever silly crap they demand and don't waste time worrying about it or trying to educate your instructors. School serves two main practical purposes: it gets you a scrap of sheepskin that helps you get a desirable job, and it potentially helps you learn how to learn under your own steam. The actual data content of your courses won't usually do you much good later in life, but general methods of gathering and evaluating information remain valid "forever".
henry@utzoo.uucp (Henry Spencer) (11/13/88)
In article <771@wsccs.UUCP> dharvey@wsccs.UUCP (David Harvey) writes: >... But what >if I want to package a set of functions for users of equipment >I manufacture to connect to the computer and I don't want them >to have the source? Then the linker will have to do it. ... Nonsense. Supply them with an include file. It doesn't contain any more information than your documentation will have to have anyway. -- Sendmail is a bug, | Henry Spencer at U of Toronto Zoology not a feature. | uunet!attcan!utzoo!henry henry@zoo.toronto.edu
mouse@mcgill-vision.UUCP (der Mouse) (11/14/88)
[ > from <137@twwells.uucp>, by bill@twwells.uucp (T. William Wells) ] [ >> from <7700@bloom-beacon.MIT.EDU>, by scs@adam.pika.mit.edu (Steve Summit) ] [ >>> from <119@twwells.uucp>, by bill@twwells.uucp (T. William Wells) ] >>> Avoid excess function calls. A lot of people have been brainwashed >>> by some modularity gurus into believing that every identifiable >>> "whole" should have its own function. >> Here's another religious debate: the structured programming one. > I think you missed the point. Structured programming is essential to > good procedural programming. The truth of this depends on what you mean by "structured programming". An unfortunately large segment seems to believe that structured programming means sticking strictly to certain rules, such as "never use a goto, ever" or "no function body larger than a page, ever" (though they never say whether terminal page or paper page, curious). And, as I am sure you are aware, blind adherence to rules cannot, in itself, produce good programs, regardless of the rules. Good programmers write good programs without needing rules; bad programmers can't write good programs even with rules. I suspect their reason for existence is that good programmers' output tends to follow them (not always, though!), so in a wonderful inversion of cause and effect, some people deduce that following the rules will make for good programs. (Using such rules as guidelines may also help nudge in-between programmers the right way.) >> There are a few applications (and, some believe, a few >> architectures) for which function call overhead is significant, On a VAX, almost all compilers (certainly all of which I am aware, except possibly for BLISS) use the CALLS/CALLG function call mechanism. This mechanism is so horribly inefficient it arguably shouldn't have existed in the first place. The VAX is certainly not more than one architecture, but it's a rather common one. (As Steve implies, this doesn't matter for the vast majority of programs. I am particularly aware of it because I have been involved in an effort to build a robot control system, which involves guaranteeing a 28-millisecond cycle time for certain parts of the code, and a CALLS - to pick just one example - is a nontrivial fraction of that.) >> Please don't avoid malloc; the alternative is generally fixed-size >> arrays and "lines longer than 512 characters are silently >> truncated." I have been guilty of going the fixed-size route on occasion, and doubtless will be in the future. Why? Because allocating requires that I know the size ahead of time. If there were some way to inquire of "the system" how much data remains to be read before the next newline....but there isn't, and probably never will be. For most programs, the user-interface flaw implied by fgets() is less painful than the time it would eat up for me to go the general route. >>> Unless, of course, the programmer remembered to COMMENT. >> If the code reads >> a &= 3; /* really a %= 4 */ >> or >> a &= 3; /* really a %= HASHSIZE */ >> and I do a global replace of 4, or re#define HASHSIZE, the comment >> may not help. > Yes, but writing an explicit constant is bad to start off with. It > should be: > #define HASHSIZE 4 /* A power of two, or else! */ > a &= HASHSIZE - 1; How about #if HASHSIZE & (HASHSIZE-1) a %= HASHSIZE; #else a &= HASHSIZE - 1; #endif Of course, I daresay there aren't that may hashing algorithms that work well for both power-of-two table sizes *and* non-power-of-two sizes. But the choice of algorithm is not the point here. der Mouse old: mcgill-vision!mouse new: mouse@larry.mcrcim.mcgill.edu
wald-david@CS.YALE.EDU (david wald) (11/16/88)
In article <771@wsccs.UUCP> dharvey@wsccs.UUCP (David Harvey) writes: >The recent postings on the net on this topic has prompted me to respond >about a teacher at our college (not necessarily reflecting the opinion >of all faculty members) who would fail me for the following code: > >if( ! something) { > ++j; > . > . > . >} > >but would pass me with flying colors for the following: > >if ( something != 0) > { > j = j + 1; > . > . > . > } > >As a matter of fact, he would under no circumstances allow me to >use the '++', '--', '+=', '-=', '/=', '*=', or '%=' operators. >I would LITERALLY be failed if it were there. Just out of curiosity: Why the hell was he teaching in C? ============================================================================ David Wald wald-david@yale.UUCP waldave@yalevm.bitnet ============================================================================
bill@twwells.uucp (T. William Wells) (11/16/88)
In article <1349@mcgill-vision.UUCP> mouse@mcgill-vision.UUCP (der Mouse) writes:
: The truth of this depends on what you mean by "structured programming".
Try this version of structured programming: the physical structure of
the program should mirror the logical structure of the program.
: An unfortunately large segment seems to believe that structured
: programming means sticking strictly to certain rules, such as "never
: use a goto, ever" or "no function body larger than a page, ever"
: (though they never say whether terminal page or paper page, curious).
: And, as I am sure you are aware, blind adherence to rules cannot, in
: itself, produce good programs, regardless of the rules. Good
: programmers write good programs without needing rules; bad programmers
: can't write good programs even with rules. I suspect their reason for
: existence is that good programmers' output tends to follow them (not
: always, though!), so in a wonderful inversion of cause and effect, some
: people deduce that following the rules will make for good programs.
: (Using such rules as guidelines may also help nudge in-between
: programmers the right way.)
All of which I heartily agree with.
: I have been guilty of going the fixed-size route on occasion, and
: doubtless will be in the future. Why? Because allocating requires
: that I know the size ahead of time. If there were some way to inquire
: of "the system" how much data remains to be read before the next
: newline....but there isn't, and probably never will be. For most
: programs, the user-interface flaw implied by fgets() is less painful
: than the time it would eat up for me to go the general route.
Write a function to handle it once and for all. Then always use the
function. This is what I'm going to start doing.
: #if HASHSIZE & (HASHSIZE-1)
: a %= HASHSIZE;
: #else
: a &= HASHSIZE - 1;
: #endif
:
: Of course, I daresay there aren't that may hashing algorithms that work
: well for both power-of-two table sizes *and* non-power-of-two sizes.
: But the choice of algorithm is not the point here.
My own feeling is that if HASHSIZE isn't known to be a power of two,
one should live with the %. The alternative is to turn one's code
into a morass of #if's. Ugh.
---
Bill
{uunet|novavax}!proxftl!twwells!billscs@athena.mit.edu (Steve Summit) (11/19/88)
Not surprisingly, I got ripped to shreds by Bill Wells and Terry
Lambert (among others) for having dared to suggest that good
style might be more important than raw efficiency and
microoptimization. (Don't worry; this won't be a line-by-line
retribution; I've got better things to do.)
The reason I opened my earlier posting by casting "efficiency vs.
style" as a religious war was to suggest that I did not expect to
convince the efficiency aficionadoes that efficiency is not as
important as they think it is, any more than I expect them to
convince me that it is. ("Efficiency aficionado" is not meant as
a pejorative term; some people simply have differing opinions
on the relative importance of things like efficiency and style.
The fact that these opinions are polarized and strongly held
makes for a fine religions war.)
There is an abominable quantity of horrible code in existence
today, and egregious amounts of time are wasted trying to fix
neverending bugs, trying to add seemingly reasonable features
which the "architecture" inexplicably prohibits, and finally
abandoning the whole mess and rewriting it from scratch. I will
be vehemently disagreed with, but I submit that most of this
unmaintainable code arises out of misplaced concerns for
"efficiency." It is true that there are a lot of miseducated
programmers out there, but their miseducation often derives from
teachers and textbook authors who constantly harp on efficiency
without teaching moderation, and from the badly-written code by
which they are surrounded and which they (the students)
inevitably emulate and go on to perpetuate.
I am not, repeat not, saying that efficiency is not important. I
am not advocating (in this article, anyway) writing deliberately
inefficient code just to make it clearer. I am saying that style
may be more important than efficiency, particularly since not all
programmers are able to "have their cake and eat it too."
Certainly we need to educate people in this direction; certainly
we need to teach them techniques for writing code that is right
the first time (where "right" is clean, clear, and not
inefficient). When assigning priorities, though, I would rather
have people learn clarity and good style first, and efficiency as
the need arises. (Among other things, the marketplace
imperatives of which we are endlessly reminded will ensure that
efficiency will not be neglected; while there are, sadly, not as
many incentives for writing clearly.) The industry is not
plagued by slow programs (compilers being tuned for the
benchmarks to the contrary notwithstanding). The industry is
plagued by software that is over schedule, over budget, buggy,
and unmaintainable.
Please: those who keep coming down like a ton of bricks (and no,
I don't take it that way; this is a religious war--I know I'm
right :-)) when it is even suggested that efficiency might not be
all-important: I am not saying that you are wrong, merely that
I'd like to shift the emphasis. (I would have more sympathy,
though, with articles which claim they agree that style is
important while continuing to trot out obfuscated C contest
candidates, if they didn't doggedly insist that x<<1 is still
better than x*2, when it has been adequately shown that the
former contributes nothing to efficiency and can only detract
from readability. Quit saying that not all compilers can do
these optimizations--to quite Kernighan and Plauger, "Those that
will not must certainly provide worse inefficiencies to worry
about.")
I forgot to recommend The Elements of Programming Style
(Kernighan and Plauger) in my previous article. If you haven't
read it already, do so; and read it again if you have. It's got
more solid, practical advice on good style on each page than
you'll see on the net in a year, and it's got a whole chapter on
efficiency, too (relegated to the back, where it belongs). Don't
let the Fortran and PL/I throw you--with a little thought all of
the issues being discussed can be seen still to be supremely
important today.
Steve Summit
scs@adam.pika.mit.edurkl1@hound.UUCP (K.LAUX) (11/22/88)
Steve very eloquently states his observations/conclusions about the state of the Software Industry. I recently read an article pointing out that there have been tremendous advances made in hardware, but relatively few in software, and that predicts a woeful shortage of Software Engineers (or whatever you would like to call them) for the future. Case in point: It is now possible to design IC's from scratch, and have them in a production run, in about 3 months, from a single workstation. So, how many programs are there now that take advantage of all (or even a lot) of the features of OS/2? Or VGA. Or 80386? I sure hope that the Software Industry has a break though like the Hardware Industry soon. At least I can be sure of steady employment :-) if not. --rkl
gwyn@smoke.BRL.MIL (Doug Gwyn ) (11/22/88)
In article <2766@hound.UUCP> rkl1@hound.UUCP (K.LAUX) writes: > So, how many programs are there now that take advantage of all (or >even a lot) of the features of OS/2? Or VGA. Or 80386? That sure is strange criteria for software!
john@frog.UUCP (John Woods) (11/22/88)
In article <8059@bloom-beacon.MIT.EDU>, scs@athena.mit.edu (Steve Summit) writes: R> I forgot to recommend The Elements of Programming Style e> (Kernighan and Plauger) in my previous article. If you haven't a> read it already, do so; and read it again if you have. It's got d> more solid, practical advice on good style on each page than > you'll see on the net in a year, and it's got a whole chapter on i> efficiency, too (relegated to the back, where it belongs). Don't t> let the Fortran and PL/I throw you--with a little thought all of !> the issues being discussed can be seen still to be supremely > important today. I would like to second this recommendation. It is also the source of my favorite quote, which happens to be on this very topic: "Presumably it was essential to get the wrong answer as fast as possible." -- John Woods, Charles River Data Systems, Framingham MA, (617) 626-1101 ...!decvax!frog!john, john@frog.UUCP, ...!mit-eddie!jfw, jfw@eddie.mit.edu Science does not remove the TERROR of the Gods!
anw@nott-cs.UUCP (11/23/88)
In article <437@auspex.UUCP> guy@auspex.UUCP (Guy Harris) writes: > >In fact, if prototypes had been there since Day 1 and had been the >*only* way of declaring functions (this may perhaps have made the >language too big for the PDP-11 to compile, I don't know - I'm not ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Naw! Let's see [PDP 11/44, V7]: $ ls -l /lib/c? -rwxrwxr-x 1 bin system 23924 May 7 1979 /lib/c0 -rwxrwxr-x 1 bin system 35282 May 16 1979 /lib/c1 -rwxrwxr-x 1 bin system 11632 Jul 11 1980 /lib/c2 $ size /lib/c? /lib/c0: 20736+3172+11552 = 35460b = 0105204b /lib/c1: 30592+4674+1206 = 36472b = 0107170b /lib/c2: 10176+1440+2430 = 14046b = 033336b Plenty of room there for expansion, even with a 64K limit! >saying that this would necessarily have been the best thing), and if >"varargs" or "stdarg" had been the only permissible way of doing >variable-length-argument-list functions, calling sequences where the >callee, rather than the caller, could safely have been used (since the >compiler could feel reasonably confident that if a function expects N >arguments of particular types, it will be passed just such a list of >arguments), and it has at least been asserted that on some machines, >such calling sequences are faster (e.g., the debates over the "C" and >"Pascal" calling sequences on 80*86 machines). Of course, the real solution to the "varargs" problem, not possible in C because of the dead hand of history, is to use extra brackets, so that every function has a fixed number of arguments: printf ("%d %c %s\n", (i, c, "hello world")); ^...arg1...^, ^.......arg2........^ Now, what language did I see that nifty idea in? [:-)] -- Andy Walker, Maths Dept., Nott'm Univ., UK. anw@maths.nott.ac.uk
guy@auspex.UUCP (Guy Harris) (11/25/88)
> Naw! Let's see [PDP 11/44, V7]: It may well be true that it can be done - I certainly won't say it's impossible, I was just considering the possibility that it wasn't in the original C language because either 1) it would have made the compiler too big or 2) DMR thought it would. At this point, I'd prefer to hear Dennis say why, when C was first created, the types of the arguments to a function was not considered part of the type of the function, or at least an answer from somebody working with him at the time. Most other answers would probably be purely speculative. > Of course, the real solution to the "varargs" problem, not possible >in C because of the dead hand of history, is to use extra brackets, so that >every function has a fixed number of arguments: > > printf ("%d %c %s\n", (i, c, "hello world")); > ^...arg1...^, ^.......arg2........^ > > Now, what language did I see that nifty idea in? [:-)] OK, so what is the data type of (i, c, "hello world") Just adding extra brackets wouldn't have been sufficient; it leaves questions such as that one....
dik@cwi.nl (Dik T. Winter) (11/25/88)
> > Of course, the real solution to the "varargs" problem, not possible > >in C because of the dead hand of history, is to use extra brackets, so that > >every function has a fixed number of arguments: > > > > printf ("%d %c %s\n", (i, c, "hello world")); > > ^...arg1...^, ^.......arg2........^ > > > > Now, what language did I see that nifty idea in? [:-)] (For those who do not know, Algol 68) > > OK, so what is the data type of > > (i, c, "hello world") > > Just adding extra brackets wouldn't have been sufficient; it leaves > questions such as that one.... It is an 'array display', i.e. the second parameter is an array whose components are a union of a lot of things. The extra brackets are required as there is (in Algol 68) a difference between: print(a, b, c) and print((a, b, c)) the first calls print with three parameters (which is illegal), the second with only one. -- dik t. winter, cwi, amsterdam, nederland INTERNET : dik@cwi.nl BITNET/EARN: dik@mcvax
peter@ficc.uu.net (Peter da Silva) (11/28/88)
In article <2766@hound.UUCP>, rkl1@hound.UUCP (K.LAUX) writes: > So, how many programs are there now that take advantage of all (or > even a lot) of the features of OS/2? Ummmm... isn't that a piece of software? > Or VGA. Or 80386? UNIX? With X-windows? -- Peter da Silva `-_-' Ferranti International Controls Corporation "Have you hugged U your wolf today?" uunet.uu.net!ficc!peter Disclaimer: My typos are my own damn business. peter@ficc.uu.net