bobvan (11/10/82)
The responses to my C debugging puzzle have finally started to slow down. As promised, this note contains a correct solution, commentary on the wisdom of such coding practices, commentary on the appropriateness of such puzzles, and a list of those who got the first puzzle right. Once more, let me apologize for hastily posting the original puzzle with an (unintended) error. Many people spotted the obvious error, reported it, and stopped there -- missing the benefit of the exercise. Repeated here is the puzzle the way it should have read: #define XSIZE 10 #define YSIZE 10 int array2d[XSIZE][YSIZE]; int *ip; for (ip=&array2d[0][0]; ip<&array2d[XSIZE][YSIZE]; ip++) *ip = 0; Can you see the bug in the above fragment? The for statement should read: for (ip = &array2d[0][0]; ip <= &array2d[XSIZE-1][YSIZE-1]; ip++) There were two problems, even with the "fixed" version above. The "bug" is that the original for loop stops only after it has cleared well past the end of array2d. While it is true that "&array[SIZE]" is the address of one element beyond the end of "array", "&array2d[XSIZE][YSIZE]" is NOT the address of one element beyond the end of "array2d". Instead it is the address of one element beyond the end of one COLUMN beyond the end of "array2d". The x subscript in array2d only goes up to XSIZE-1, hence "&array2d[XSIZE][0]" is already past the end of array2d. The other problem with the fixed example is that many C compilers (PCC included) will produce warning messages about V6 anachronisms because "=&" may have been intended as a V6 C version of "&=". A space between the tokens fixes this in the debugged version. In either case, all V7 compilers produce the intended code. Thanks to those who pointed this out. Many people correctly pointed out that it would have been even more efficient to leave the increment part of the for statement empty and change the assignment to "*ip++ = 0". I didn't make this optimization in the puzzle to retain conformity with the cannonical code that uses indexing. --- Several responses discouraged making such optimizations in the first place. One even flamed at me for not providing a strong disclaimer with the puzzle discouraging the use of such techniques. I guess I didn't make it clear enough that I feel like a fool for getting bitten by my lust for tight code. Many pointed out that the function of the optimized version is not as clear is the function of the original version. I agree. The decision of when to sacrifice readability for performance is routinely made by many programmers. It is not a decision that should be taken lightly. It is certainly true that using such techniques can lead to conceptual errors and that they should be used with great care. I think it important to point out that my error was not due to lack of knowledge but rather to an inappropriate generalization -- that "I've done it a million times" feeling of false security we all get sometimes. In posting the puzzle, I hoped that others could learn from my mistake. I hope that these paragraphs have made that amply clear. One response claimed that the optimization was of dubious value because there are machines where indexing is faster than pointer incrementing. I believe that this is possible but can't think of any machines that behave this way (a 3B20 perhaps?). If you know of such machines, please tell me and I'll summarize. Another response claimed that such code is not portable. I also believe that this is possible, but strongly doubt it. I can't see anything in the code that is outside the language semantics given in K&R. If you know of machines where this won't work, please tell me. I have it running on an 8080, an 11/23 and a VAX. I also received several responses that contained incorrect statements about the way two dimensional arrays behave in C. Apparently this area is not as well understood as I had first thought. --- Most of the responses I received had no comment about the appropriateness of such puzzles on the net. Only one complained that the first was too easy. There were probably others who thought it too easy to even bother responding. Sorry, but I don't have any harder ones right now. Four responses strongly encouraged me to continue, and I got the one flame mentioned above. In light of the clarification and cautions above, I will post another article with two more puzzles of a different type. --- Finaly, a (probably incomplete) list of those who correctly identified the "running of the end of the array bug". This list is in order of arrival at my machine which gives an unfair advantage to my immediate neighbors. ittvax!swatt Alan S. Watt houxt!vjja Jim Allen eagle!jerry Jerry Schwarz rabbit!ark ? microsof!hanss Hans S. raven!jpl John P. Linderman utah-gr!thomas =Spencer sii!mem Mark E. Mallettt pur-ee!ecn-pa.bruner John Bruner pur-ee!Physics:crl Charles LaBrec sdcsvax!laman Mike Laman watcgl!dmmartindale Dave Martindale uicsovax!hamilton Wayne Hamilton duke!dennis ? eagle!karn Phil Karn hssg40!peachey Darwyn Peachey rabbit!ss Sharad Singhal psuvax!sibley Dave Sibley iwlc7!dfz Dave Ziffer I probably shouldn't create such a "contest" atmosphere -- "grading" your responses is hard work! Bob Van Valzah (...!decvax!ittvax!tpdcvax!bobvan)