Help in this programm in C

[ballpointpenthief]

By the time you are at 5 or 6 levels of indentation, you need to
refactor the code. Very rarely is it appropriate to be that
deeply nested. The only time I've ever seen a situation where
it is appropriate to be that deeply nested is in VHDL, where
your first line of actual code is generally indented 3 or 4 levels.
I've never seen a case where it's appropriate in C.

This is from the first ever serious exercise I did. It was a sudoku
solver.

for (int i=0; i<3; i++) // Set up 'box' matrix
for (int j=0; j<3; j++)
for (int k=0; k<3; k++)
for (int l=0; l<3; l++)
for (int m=0; m<9; m++)
if (init->state[(3*i)+k][(3*j)+l] == m+1)
init->box[(3*i)+j][m] = 0;

I think this is intended as an example of code that
requires deep indentation.

Yes, that's right.

I think it's actually a great
example of code that needs to be re-designed. One
idea that immediately springs to mind is:

struct value *v;
for (v=start; v<end; v++)
v->box[v->val] = 0;

where v iterates over all the entries in the game grid.

I don't think my programme needs to be redesigned. I don't understand
how you can infer that from what I posted.

Given the current board (.state), we need a way of knowing where each
number can go.
(.poss), so we can put it into a solving function (which, is what the
..low variable is for).

struct sud {
int state[9][9];
_Bool row[9][9];
_Bool col[9][9];
_Bool box[9][9];
_Bool ava[9][9];
_Bool poss[9][9][9];
int nposs[9][9];
int low;
} ;

void init(struct sud *init) // Compute matrices
{
for (int i=0; i<9; i++) // Set up row and column matrices
for (int j=0; j<9; j++)
{
init->row[j] = 1;
init->col[j] = 1;
init->box[j] = 1;
if (!init->state[j])
init->ava[j] = 1;
else
init->ava[j] = 0;
for (int k=0; k<9; k++)
{
if (init->state[k] == j+1)
init->row[j] = 0;
if (init->state[k] == j+1)
init->col[j] = 0;
}
}
for (int i=0; i<3; i++) // Set up box matrix
for (int j=0; j<3; j++)
for (int k=0; k<3; k++)
for (int l=0; l<3; l++)
for (int m=0; m<9; m++)
if (init->state[(3*i)+k][(3*j)+l] == m+1)
init->box[(3*i)+j][m] = 0;

for (int i=0; i<9; i++) // multiply elements from each previous 9x9
mats & obtain 9x9x9
for (int j=0; j<9; j++)
for (int k=0; k<9; k++)
init->poss[j][k] = init->row[j] * init->col[k] *
init->box[((k-(k%3))/3) + (j-(j%3))] * init->ava[j][k];

init->low = 10;
for (int i=0; i<9; i++) // Set up number of possibilities matrix
for (int j=0; j<9; j++)
{
int count=0;
for (int k=0; k<9; k++)
if (init->poss[k][j])
count++;
init->nposs[j] = count;
if ((init->low > count) && (count))
init->low = count;
}
if (init->low == 10)
init->low = 0;
}

 

[Mark McIntyre]

Mark McIntyre wrote, in regard to tab vs. space indentation:


By the time you are at 5 or 6 levels of indentation, you need to
refactor the code.

Sometimes. Sometimes not.

Very rarely is it appropriate to be that deeply nested.

I disagree with such sweeping statements.

The only time I've ever seen a situation where
it is appropriate to be that deeply nested is in VHDL, where
your first line of actual code is generally indented 3 or 4 levels.
I've never seen a case where it's appropriate in C.

Then you've less experience than me.

A "large
complex program" absolutely must be broken down into
simple manageable components. Modularity really is a
good idea.

Sure, but this has nothing to do with the level of indentation, and
has its downside too (eg increasing execution time due to stack setup
/ parameter preparation etc) . Working with large multidimensional
arrays might be an example.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Mark McIntyre]

struct value *v;
for (v=start; v<end; v++)
v->box[v->val] = 0;

where v iterates over all the entries in the game grid.

a) how?
b) with what cost at runtime?

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Ian Collins]

Sometimes. Sometimes not.




I disagree with such sweeping statements.




Then you've less experience than me.




Sure, but this has nothing to do with the level of indentation, and
has its downside too (eg increasing execution time due to stack setup
/ parameter preparation etc) . Working with large multidimensional
arrays might be an example.

The cost is often small, if the extracted function is short, it is a
likely candidate for inlining. If it is long, the call overhead (as a
percentage) is low.

 

[Bill Pursell]

struct value *v;
for (v=start; v<end; v++)
v->box[v->val] = 0;

where v iterates over all the entries in the game grid.

a) how?

Via addition.

b) with what cost at runtime?

Practically none. You either set up your memory
so that all of the structures representing a cell in
the grid are contiguous and iterate over them with
a simple for loop, or if for some reason you can't
make them contiguous, you establish an array
of pointers into the data structure that you can
iterate over. I am pretty sure that the difference
is going to be completely negligible, but I would
bet that

for (v = start; v< end; v++)
do_something(v);

will be more efficient than

for (i=0; i<3; i++)
for (j=0;j<3;j++)
for(k=0;k<3;k++)
for(l=0;l<3;l++)
do_something(i,j,k,l);

And it is certainly easier to read. It would be
even cleaner to understand:

iterate_over_grid(do_something);

 

[Bill Pursell]

Bill Pursell wrote:
By the time you are at 5 or 6 levels of indentation, you need to
refactor the code. Very rarely is it appropriate to be that
deeply nested. The only time I've ever seen a situation where
it is appropriate to be that deeply nested is in VHDL, where
your first line of actual code is generally indented 3 or 4 levels.
I've never seen a case where it's appropriate in C.

This is from the first ever serious exercise I did. It was a sudoku
solver.

for (int i=0; i<3; i++) // Set up 'box' matrix
for (int j=0; j<3; j++)
for (int k=0; k<3; k++)
for (int l=0; l<3; l++)
for (int m=0; m<9; m++)
if (init->state[(3*i)+k][(3*j)+l] == m+1)
init->box[(3*i)+j][m] = 0;

I think this is intended as an example of code that
requires deep indentation.

Yes, that's right.

I think it's actually a great
example of code that needs to be re-designed. One
idea that immediately springs to mind is:

struct value *v;
for (v=start; v<end; v++)
v->box[v->val] = 0;

where v iterates over all the entries in the game grid.

I don't think my programme needs to be redesigned. I don't understand
how you can infer that from what I posted.

I'm simply stating that the code snippet you posted was
obfuscated. You are using a bunch of nested for loops
for the purpose of iterating over your data structure. I'm
arguing that it would be cleaner to write it as
a single loop. If the program as currently designed
does not allow that iteration, then I think some extra
work should be put into the data structures. Sudoku
has a concept of squares and grids and rows and columns
(I'm not a Sudoku fan, so I don't know if they have
technical names in the game.) All I see in the code
is indexes i,j,k,l,m. I think you're iterating over the
rows, or over the columns, or over the cells, but it's
not entirely clear. It would be better to make calls
like:

iterate_over_rows(do_something);
or
iterate_over_all_cells(do_something);

where do_something is a function pointer that will
act on each row or each cell. It makes understanding
the code easier, and it reduces the problem of
excessive indentation.

 

[Flash Gordon]

Richard Heathfield wrote:
jaysome said:

On Fri, 07 Jul 2006 09:10:14 +0000, Richard Heathfield

<snip>
What other Standard C functions would be good candidates for the
"-function" option?

Just gets(). But I'd flag a few others as being "experts-only"
functions, which you should not use in "real" code unless you know
/exactly/ what you're doing:

<snip>
From <stdlib.h>

[...] calloc, malloc, realloc, free, [...]

Let's get this straight: you shouldn't dynamically allocate memory in
C unless you're an expert?

It is extremely easy to get wrong.

I see you did not address this point.

Oh, let's get *that* straight too: obviously it's actually very *easy*
to write code if you can't use more than, say, 42 memory units exactly
-- or tell people such code can't be written.

You haven;t kept up with the embedded world, have you. There are pretty
powerful embedded systems with lots of memory. I know of one embedded
system which was upgraded to 1MB of RAM in the days when 640K was still
considered plenty for a desktop PC (it may even have been done before
you could get a desktop PC with 640K of RAM, since it was done before I
came across the project). Don't assume you know what goes on in all
parts of the embedded industry.

For many applications that's simply not good enough, though. You'll want
a program that can scale to core without having to recompile it.

I never said it was good enough for all or even the majority of C
programs, and certainly did not say it was the case for all desktop or
server applications! I only stated that there were plenty of
applications where dynamic memory allocation is not needed.

If you want a program that has to utilize those 42 units of memory to
the best of its ability, it's not unthinkable that you'll end up
implementing (pseudo-)dynamic memory allocation yourself.

I've had to do that *exactly* once. That was on a project where they had
selected completely the wrong HW for the job a long time before I became
involved. I was just brought on to pick up the pieces and try to at
least get *something* out the door.

The key point being "if you have a static board size". And for Life,
that's indeed not a significant restriction.

There are plenty of other applications where it is not a significant
restriction. As well as plenty where it is. Did you know that a commonly
used text editor has a fixed maximum size of text document it can
process? A limit that is orders of magnitude smaller than the amount of
free memory on the PC I am currently using?

This I do not dispute.

So why do you say that limiting the use of dynamic memory allocation to
experts would limit the use of C to experts?

But the latter class is a minority,

I don't know whether it is a minority or not, but it is an *extremely*
large class. I had several years of programming for a living before I
came across a situation at work where using dynamic allocation was the
simplest solution.

> and the former a distinct nuisance.
I cannot recount the number of times a program (quite likely written in
C) used a "reasonable" static size and refused my input.

I never said that it was always appropriate.

> The programmer
responsible would probably shug their shoulders, increase the #define'd
constants a bit and recompile. Problem solved! For now.

When an application really does need dynamic memory allocation because
there is no reasonable static size (which is more often the case when
writting SW for others than when writing it for oneself and *not*
distribution it as source) then you want it written by someone
sufficiently expert that they will get the dynamic memory allocation
right, and some otherwise good programmers don't have the experience to
do this.

Personally, I would want there to be an expert programmer involved in
*all* of the complex software that I use, unfortunately I'm not
convinced that this is the case.

 

[Mark McIntyre]

struct value *v;
for (v=start; v<end; v++)
v->box[v->val] = 0;

where v iterates over all the entries in the game grid.

a) how?

Via addition.

I was thinking more of you showing us how this works, rather than a
vague comment. I'd have said arithmetic myself.

Practically none.

Mhm, and you've tested this in all possible cases?

iterate over. I am pretty sure that the difference
is going to be completely negligible, but I would
bet that

for (v = start; v< end; v++)
do_something(v);

will be more efficient than

for (i=0; i<3; i++)
for (j=0;j<3;j++)
for(k=0;k<3;k++)
for(l=0;l<3;l++)
do_something(i,j,k,l);

And I'm willing to bet that its quite impossible to predict which will
be more efficient, and that it will depend on

a) compiler flags
b) operating system
c) memory layout and access rules
d) object type and structure
e) CPU structure, pipelines, branch methodology etc
f) number and size of registers
e) other things, too tedious to enumerate

This is rather like the old chestnut about the guy who insisted on
unrolling all his loops, and couldn't work out why they ran slower on
a Convex.

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Mark McIntyre]

The cost is often small, if the extracted function is short, it is a
likely candidate for inlining. If it is long, the call overhead (as a
percentage) is low.

But not if the function is called many many times.

This is a real world situation I've been in. Some pricing calcs ran
significantly slower after we refactored the code along the lines
discussed here. We eventually realised that a specific set of
functions were called repeatedly in tight loops. By manually inlining
the code, we more than doubled performance, at the expense of more
complex code and some repetition.

The code now has comment blocks to warn people NOT to refactor it
again. I fully expect it to happen anyway. :-(
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Andrew Poelstra]

Andrew Poelstra napsal(a):

why? where?

They display inconsistantly; on Usenet they often don't display, and they
have different widths on different editors. If you want 8 spaces, that's
fine, but you should use spaces instead of tabs.

I don't think so, that's all.

You're entitled to your opinion, and I have no right to try and change that;
there's no right or wrong when it comes to style.

It seemed, that you want him to mix 2 and 4 cols indentation...

No, I wanted him to use 2 /or/ 4 cols indentation. Sorry if I didn't
make that clear enough.

 

[Skarmander]

Skarmander wrote:
Richard Heathfield wrote:
jaysome said:

On Fri, 07 Jul 2006 09:10:14 +0000, Richard Heathfield

<snip>
What other Standard C functions would be good candidates for the
"-function" option?

Just gets(). But I'd flag a few others as being "experts-only"
functions, which you should not use in "real" code unless you know
/exactly/ what you're doing:

<snip>
From <stdlib.h>

[...] calloc, malloc, realloc, free, [...]

Let's get this straight: you shouldn't dynamically allocate memory
in C unless you're an expert?

It is extremely easy to get wrong.

I see you did not address this point.

Sure I did, in this statement:

I don't think anybody's arguing that it's not a big source of mistakes. Then
again, plenty of common tasks in C are big sources of mistakes, as the
lengthy FAQ illustrates.

You haven;t kept up with the embedded world, have you. There are pretty
powerful embedded systems with lots of memory. I know of one embedded
system which was upgraded to 1MB of RAM in the days when 640K was still
considered plenty for a desktop PC (it may even have been done before
you could get a desktop PC with 640K of RAM, since it was done before I
came across the project). Don't assume you know what goes on in all
parts of the embedded industry.

I have no idea why this is relevant to my statement, but you are probably
misled by my "42 memory units". I deliberately used a magic number and
didn't specify what those units were. The idea that assuming a specific
amount of memory makes things easier holds whether you're talking 42 bytes
or 42 megabytes. (Of course, there's a huge practical difference.)

I never said it was good enough for all or even the majority of C
programs, and certainly did not say it was the case for all desktop or
server applications! I only stated that there were plenty of
applications where dynamic memory allocation is not needed.

And my point is that as long as such programs are *not* the majority,
dynamic memory allocation is something that belongs in the arsenal of every
C programmer. We'll return to this later.

There are plenty of other applications where it is not a significant
restriction. As well as plenty where it is. Did you know that a commonly
used text editor has a fixed maximum size of text document it can
process? A limit that is orders of magnitude smaller than the amount of
free memory on the PC I am currently using?

Well, I know that the Notepad that came with Windows 3.x, 95, 98 and
presumably ME was limited to 64K, a holdover from the segmented memory era.
Ironically, the DOS-based EDIT.COM that came with Windows 9x did not have
this limitation.

Of course, that version of Notepad is restricted to the point of being
inappropriate for anything more ambitious than a grocery list, so the size
limit is just the finishing touch.

So why do you say that limiting the use of dynamic memory allocation to
experts would limit the use of C to experts?

I don't. I think it *should* limit the use of C to experts (at least for
applications programming -- but outside of applications programming there
are other things that require expert attention, so it probably evens out). I
don't really think it's acceptable for a C programmer to say "well, I
program C very well, but I can't really handle dynamic memory allocation".
If you said you had no idea how to use longjmp(), I could sympathize, but
dynamic memory allocation? No.

This is just me being a snob. In reality C is a tool, and it will be used
with various levels of competence. As long as the job gets done, you won't
hear anyone comment about how competently a tool was used. In the case of
static memory sllocation, you won't hear people comment until the job
instances get bigger.

I'm sure plenty of C users can write plenty of useful programs that do not
dynamically allocate memory. I'm also pretty sure most of the programs run
don't or shouldn't fall in this category.

I don't know whether it is a minority or not, but it is an *extremely*
large class. I had several years of programming for a living before I
came across a situation at work where using dynamic allocation was the
simplest solution.

Dynamic allocation is almost never the *simplest* solution in C.

The simplest solution is often the most appropriate one because simplicity
cuts development and maintenance costs -- but for general applications, when
the simplest solution involves no dynamic memory allocation, it will often
be *too* simple.

I never said that it was always appropriate.

My argument is that even were it is appropriate, it tends to become
inappropriate sooner than later.

When an application really does need dynamic memory allocation because
there is no reasonable static size (which is more often the case when
writting SW for others than when writing it for oneself and *not*
distribution it as source) then you want it written by someone
sufficiently expert that they will get the dynamic memory allocation
right, and some otherwise good programmers don't have the experience to
do this.

If dynamic memory allocations is for experts, then please let C be for
experts, so I don't have to cope with exactly this attitude anymore. (Note:
snobbery.)

"Well I thought a maximum of 12,564 sprockets would be reasonable enough,
but no worries if it's not, you just go to arbitrarylimits.h and increase
the third #define from the top to 47. Recompile and reinstall and you're all
set. That wasn't so hard, was it?"

Like you said, I'm sure there are a good many situations where this will
work. But it definitely does not work in general, and software tends to
evolve in the "more general" direction.

S.

 

[Bill Pursell]

On 8 Jul 2006 06:09:31 -0700, in comp.lang.c , "Bill Pursell"

struct value *v;
for (v=start; v<end; v++)
v->box[v->val] = 0;

where v iterates over all the entries in the game grid.

a) how?

Via addition.

I was thinking more of you showing us how this works, rather than a
vague comment. I'd have said arithmetic myself.

Below is some code that more or less does what I'm thinking
of.

Mhm, and you've tested this in all possible cases?

Of course not.

And I'm willing to bet that its quite impossible to predict which will
be more efficient, and that it will depend on

a) compiler flags
b) operating system
c) memory layout and access rules
d) object type and structure
e) CPU structure, pipelines, branch methodology etc
f) number and size of registers
e) other things, too tedious to enumerate

I agree whole-heartedly. I'm not in anyway suggesting that
this is a performance benefit. (Well, okay, I did somewhat suggest
that, but it was really just to deflect the counter argument that
my method may cost in performance. It might, but if the difference
matters then a new compiler is probably warranted.) I'm
coming at this strictly from a maintenance and aesthetic perspective.
Here's a sample of the type of code I am picturing. In my experience
(which is limited), I find this type of structure extremely useful.
There
are cases where a sufficiently complex data structure may make
it impractical to store multiple different accesses into the
data, but I find multiple nested loops of indices and computing
things from them to be generally difficult to understand and
fairly brittle.


#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define NUM_CELLS 81
#define NUM_ROWS 9
#define NUM_COLS 9
#define NUM_BOX 9

/* All the command line arguments. */
struct args {
FILE *in;
};

typedef enum {
top,
right,
left,
bottom
} edge;

/*
* Information about a cell in the game grid.
*/
struct cell {
int index;
int row;
int column;
int box;
int value;
enum {fixed, variable} type;
struct cell *above;
struct cell *right;
struct cell *left;
struct cell *below;
};

void parse_args(struct args *a, int argc, char *const*argv);
void read_initial_values(struct cell *c, FILE *in);
void initialize_grid(struct cell *, struct cell
*row[NUM_ROWS][NUM_COLS],
struct cell *col[NUM_COLS][NUM_ROWS], struct cell **);
int compute_box(int i);
int at_edge(int index, edge which);

int
main(int argc, char **argv)
{
struct cell grid[NUM_CELLS];
struct args a;
struct cell *row[NUM_ROWS][NUM_COLS];
struct cell *col[NUM_COLS][NUM_ROWS];
struct cell *box[NUM_BOX];
struct cell *this;
const struct cell *end=grid+NUM_CELLS;

parse_args(&a, argc, argv);
initialize_grid(grid, row, col, box);
read_initial_values(grid, a.in);

/* print the grid. */
for (this = grid; this < end; this++)
printf("%d%s", this->value, this->right ? " ":"\n");

/* print column 5. */
printf("\n column 5:\n");
for (this = col[5][0]; this; this=this->below)
printf("%d%s", this->value, this->below? " ":"\n");

/* print row 3. */
printf("\n row 3:\n");
for (this = row[3][0]; this; this=this->right)
printf("%d%s", this->value, this->right? " ":"\n");


return EXIT_SUCCESS;
}

/*
* initialize_grid()
*
* Set up the indices in all of the cells.
*/
void
initialize_grid(struct cell *g, struct cell *row[NUM_ROWS][NUM_COLS],
struct cell *col[NUM_COLS][NUM_ROWS], struct cell **box)
{
int i;
int row_idx;
int col_idx;

row_idx = col_idx = 0;
for (i=0; i< NUM_CELLS; i++) {
g.index = 0;
g.row = row_idx;
g.column = col_idx;
g.box = compute_box(i);
g.value = 0;
g.type = variable;
g.above = at_edge(i,top) ? NULL : g+i-NUM_COLS;
g.right = at_edge(i,right) ? NULL : g+i+1;
g.left = at_edge(i,left) ? NULL : g+i-1;
g.below = at_edge(i,bottom)? NULL : g+i+NUM_COLS;
row[row_idx][col_idx] = g+i;
col[col_idx][row_idx] = g+i;
box[compute_box(i)] = g+i;
if (col_idx == NUM_COLS - 1)
row_idx++;
col_idx = (col_idx + 1) % NUM_COLS;

}
assert(row_idx == NUM_ROWS);
assert(col_idx == 0);
}

/*
* at_edge()
*
* return true if the given index
* is at the given edge of the grid.
*/
int /* this is a boolean value */
at_edge(int index, edge which)
{
int ret;
switch(which) {
case top : ret = index < NUM_COLS; break;
case right : ret = index % NUM_COLS == (NUM_COLS-1); break;
case left : ret = index % NUM_COLS == 0; break;
case bottom: ret = index >= (NUM_COLS*(NUM_ROWS-1)); break;
}
return ret;
}

/*
* compute_box() TODO
*
* Compute the index of the box that
* contains cell i.
*/
int
compute_box(int i)
{
return 0;
}

/*
* parse_args()
*
* parse the command line arguments.
*/
void
parse_args(struct args *a, int argc, char *const*argv)
{
a->in = stdin;
}

/*
* read_initial_values()
*
* read the input stream to determine the
* initial fixed values in the game grid.
* TODO
*/
void
read_initial_values(struct cell *grid, FILE *in)
{
/* Insert some toy values for testing purposes. */
grid[14].value = 5;
grid[14].type = fixed;

grid[34].value = 7;
grid[34].type = fixed;
}


Note: the above code was cut/pasted into a web interface, and
a few lines were modified by hand after the paste. Apologies
for any errors.

 

[Bill Pursell]

They display inconsistantly; on Usenet they often don't display, and they
have different widths on different editors. If you want 8 spaces, that's
fine, but you should use spaces instead of tabs.

The second point you make (that tabstops have different widths in
different
editors) is not a point against tabs. It simply demonstrates that
people
need to learn their editor. Editors do not randomly select a
tabstop setting (at least, no editor that I'm aware of. Wouldn't
that be fun, though?). If your editor is displaying tabstops on
a column width that you don't like, it is because of the configuration.
If you don't know how to change the configuration, you shouldn't
be using that editor. (or you should learn how to configure it)

 

[Flash Gordon]

Flash Gordon wrote:
Skarmander wrote:
Richard Heathfield wrote:
jaysome said:

On Fri, 07 Jul 2006 09:10:14 +0000, Richard Heathfield

<snip>
What other Standard C functions would be good candidates for the
"-function" option?

Just gets(). But I'd flag a few others as being "experts-only"
functions, which you should not use in "real" code unless you know
/exactly/ what you're doing:

<snip>
From <stdlib.h>

[...] calloc, malloc, realloc, free, [...]

Let's get this straight: you shouldn't dynamically allocate memory
in C unless you're an expert?

It is extremely easy to get wrong.

I see you did not address this point.

Sure I did, in this statement:

It would have been more obvious had you put that statement by the comment.

I don't think anybody's arguing that it's not a big source of mistakes.
Then again, plenty of common tasks in C are big sources of mistakes, as
the lengthy FAQ illustrates.
Indeed.

I have no idea why this is relevant to my statement, but you are
probably misled by my "42 memory units". I deliberately used a magic
number and didn't specify what those units were. The idea that assuming
a specific amount of memory makes things easier holds whether you're
talking 42 bytes or 42 megabytes. (Of course, there's a huge practical
difference.)

Ah, but on this embedded system the assumption of X units was broken
because it was found not to be sufficient so they increased the memory
to what was then an extremely large amount.

And my point is that as long as such programs are *not* the majority,
dynamic memory allocation is something that belongs in the arsenal of
every C programmer. We'll return to this later.

Where do you get your statistics? I know I have far more embedded
processors in my house than PCs (and I have more PCs than most people)
and it is entirely possibly I regularly use more programs on embedded
processors than I use on PCs. I have no easy way to find out whether
those embedded programs use dynamic memory allocation or not.

Well, I know that the Notepad that came with Windows 3.x, 95, 98 and
presumably ME was limited to 64K, a holdover from the segmented memory
era. Ironically, the DOS-based EDIT.COM that came with Windows 9x did
not have this limitation.

It is still in XP and I believe unchanged.

Of course, that version of Notepad is restricted to the point of being
inappropriate for anything more ambitious than a grocery list, so the
size limit is just the finishing touch.

I find it very useful when I want to be able to quickly take note. It
starts instantly and does exactly what I tell it to. I don't use it for
editing code though.

I don't. I think it *should* limit the use of C to experts (at least for
applications programming

Even for programs that have absolutely no need of dynamic memory? I've
already pointed out that there are plenty of them whether or not they
are the majority.

> -- but outside of applications programming
there are other things that require expert attention, so it probably
evens out). I don't really think it's acceptable for a C programmer to
say "well, I program C very well, but I can't really handle dynamic
memory allocation". If you said you had no idea how to use longjmp(), I
could sympathize, but dynamic memory allocation? No.

So now you are restricting your requirement to just the range of
programming tasks you know use dynamic memory allocation?

This is just me being a snob. In reality C is a tool, and it will be
used with various levels of competence. As long as the job gets done,
you won't hear anyone comment about how competently a tool was used. In
the case of static memory sllocation, you won't hear people comment
until the job instances get bigger.

There are plenty of situations where there is some other limit that
prevents the job getting bigger.

I'm sure plenty of C users can write plenty of useful programs that do
not dynamically allocate memory.

And for such programs it does not matter whether the author has learnt
dynamic memory allocation or not yet. So restricting dynamic memory
allocation to experts does *not* restrict C to experts for those programs.

> I'm also pretty sure most of the
programs run don't or shouldn't fall in this category.

I know for a fact from personal experience that it is possible to spend
years programming professionally on use programs, so whether they are
the majority or not there are plenty of them. BTW, I *did* know how to
manage dynamic memory allocation, I just did not need it.

Dynamic allocation is almost never the *simplest* solution in C.

Well, it has been the simplest solution for me in a number of instances
where I had no way of knowing in advance how much memory would be required.

The simplest solution is often the most appropriate one because
simplicity cuts development and maintenance costs -- but for general
applications, when the simplest solution involves no dynamic memory
allocation, it will often be *too* simple.

If it does not solve the problem due to being too simple then it fails
to be the simplest solution because it is not a solution. If you are
going to allow things which don't solve the problem then the "simplest
solution" is
int main(void)
{
return 0;
}

My argument is that even were it is appropriate, it tends to become
inappropriate sooner than later.

If a program lasts the entire lifetime of the kit it is designed to
support without such things having to be changed (say, 20 years), I'm
happy. The next piece of kit will require changes to the supporting
software in any case.

If dynamic memory allocations is for experts, then please let C be for
experts, so I don't have to cope with exactly this attitude anymore.
(Note: snobbery.)

I disagree. I've worked on C projects with people who have not yet
finished their degrees and are not yet expert programmers, let alone
expert C programmers, and it was no problem at all. You just have an
expert programmer reviewing their work and assisting them as necessary.
The same applies *whatever* language is being used.

"Well I thought a maximum of 12,564 sprockets would be reasonable
enough, but no worries if it's not, you just go to arbitrarylimits.h and
increase the third #define from the top to 47. Recompile and reinstall
and you're all set. That wasn't so hard, was it?"

The hardware can only cope with 12564 sprockets, a static array of 12564
sprockets is not an unreasonable amount of memory, OK I'll use a fixed size.

Oh, we are producing a new piece of hardware that can cope with more?
And you have all these other extra requirements? OK, we will spend the
extra 5 minutes on top of the 6 man-months to implement the other
requirements so as to increase the array size. Why did we limit it so we
now have to waste that 5 minutes? Well, it saved us a day of development
time and we will have to go through a *lot* of 5 minutes before we hit
the point where we've lots on that saving. Anyway, 5 minutes on top of
that 6 man-months is hardly significant, is it?

Like you said, I'm sure there are a good many situations where this will
work. But it definitely does not work in general, and software tends to
evolve in the "more general" direction.

Just as not using dynamic memory allocation does not work in general
(i.e. there are a significant set or problems where it is appropriate),
so *using* dynamic memory allocation does not work in general (i.e.
there are a significant set of problems where it is inappropriate).

There are programs I've written where the only way I could have used
dynamic memory allocation would have been something like:

{
T *p = malloc(SOME_CONSTANT);
if (p == NULL)
/* we are really in the shit now */
else {
/* do stuff */
free(p);
}
}

Personally I found
{
T p[SOME_CONSTANT];
/* do stuff */
}
to be a far simpler solution.

I will admit that some of these projects where only a few man-years of
software development, so only small programs. Oh, and the only way to
increase the amount of data that the program would be required to handle
would be to replace some hardware where one circuit board alone cost
9000UKP (18 layer double sided), I don't know how much on top of that
was spent on components, now how much the other hardware that would
require replacing cost.

 

[Mark McIntyre]

I agree whole-heartedly. I'm not in anyway suggesting that
this is a performance benefit. (Well, okay, I did somewhat suggest
that,

Er, no ,you very clearly stated it! See above retained context.

but it was really just to deflect the counter argument that
my method may cost in performance. It might, but if the difference
matters then a new compiler is probably warranted.)

Thats silly - there are many cases where refactoring code seems
counterintuitive to the simplistic approach that you've advocated.
Such instances do not mean that you have to buy new toolsets.

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Bill Pursell]

Er, no ,you very clearly stated it! See above retained context.

You snipped an important part of the context. I wrote:
"I am pretty sure that the difference
is going to be completely negligible, but I would
bet that ..."

I was trying to point out that performance is not my
primary concern here, and that the performance difference
should be insignificant.

Thats silly - there are many cases where refactoring code seems
counterintuitive to the simplistic approach that you've advocated.
Such instances do not mean that you have to buy new toolsets.

I don't understand that. Which simplistic approach do you think I am
advocating? I'm trying to say that when I see code that looks like:
for (i=0; i < N; i++)
for (j=0; j < M; j++)
for (k=0;k< P; k++)
for (l=0;l<Q; l++)
/* some code that computes an address based on i,j,k, and l*/

I find that it is usually easier to precompute the desired
addresses and build an array to iterate through linearly. I'm
acknowledging that this is not always possible, but
it has been in all cases that I've seen.

You made a point else-thread about refactoring code
to reduce such loops causing substantial performance
loss, but I suspect such losses were attributable to
other concerns than simply the overhead of the functions
used to eliminate the loop. When I refactor code to
eliminate such loops, I do a performance check. If
I come accross a case such as you described, I will
undoubtedly spend some time trying to understand
what other design issues are leading to the problem,
and I will stubbornly refuse to admit that I need to keep
the nested loops for several days. And when I see
a comment that tells me someone else tried to refactor
and it led to a performance loss...well, it depends, but
I suspect that I'll not believe it and duplicate all your
work.

 

[Mark McIntyre]

I don't understand that. Which simplistic approach do you think I am
advocating?

The one you outlined in your post, ie unrolling the inner loops. This
is by absolutely no means guaranteed to be efficient, nor even
possible.

I'm trying to say that when I see code that looks like:
for (i=0; i < N; i++)
for (j=0; j < M; j++)
for (k=0;k< P; k++)
for (l=0;l<Q; l++)

I find that it is usually easier to precompute the desired
addresses and build an array to iterate through linearly.

And when N, M, P and Q all depend on the contents of the loops? Or
when you're on pipelined / vector hardware which can execute multiple
passes at once? You've just made your code massively less efficient

I'm
acknowledging that this is not always possible, but
it has been in all cases that I've seen.

As I said earlier, there are many many reasons which mean this may not
work and may not be efficient code. A general principle of
optimisation is not to do it till you know you need to.

You made a point else-thread about refactoring code
to reduce such loops causing substantial performance
loss, but I suspect such losses were attributable to
other concerns than simply the overhead of the functions
used to eliminate the loop.

No. surprisingly enough we were not all complete idiots and we did
check.

and I will stubbornly refuse to admit that I need to keep
the nested loops for several days.

Admirable, but risky. Not wise to rule out anything.

And when I see
a comment that tells me someone else tried to refactor
and it led to a performance loss...well, it depends, but
I suspect that I'll not believe it and duplicate all your
work.

Yeah, which is roughly the point at which I'd be reviewing your future
with the team. :-(
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Bill Pursell]

And when N, M, P and Q all depend on the contents of the loops? Or
when you're on pipelined / vector hardware which can execute multiple
passes at once? You've just made your code massively less efficient

That is an excellent point.

As I said earlier, there are many many reasons which mean this may not
work and may not be efficient code. A general principle of
optimisation is not to do it till you know you need to.

My first two rules of optimization:
1) don't do it
2) don't do it yet.

No. surprisingly enough we were not all complete idiots and we did
check.

I didn't actually intend to imply that you're an idiot, and I do
apologize that it reads that way.

 

[Andrew Poelstra]

The second point you make (that tabstops have different widths in
different
editors) is not a point against tabs. It simply demonstrates that
people
need to learn their editor. Editors do not randomly select a
tabstop setting (at least, no editor that I'm aware of. Wouldn't
that be fun, though?). If your editor is displaying tabstops on
a column width that you don't like, it is because of the configuration.
If you don't know how to change the configuration, you shouldn't
be using that editor. (or you should learn how to configure it)

And then every time you read code written by someone with a different
tab width setting, you should reconfigure your editor?

That only applies to people who use tabs to align things, like so:
int main (int argc,
TAB;TAB; char *argv[])

which would become
int main (int argc,
TAB____;TAB____; char *argv[])

on an 8-spaced editor (assuming the original was 4).

However, with spaces you never have problems.

 

[Bill Pursell]

And then every time you read code written by someone with a different
tab width setting, you should reconfigure your editor?

No. The person who wrote the code should write it so
that things align properly regardless of the tabstop setting.
This is not difficult to do, and is only hampered by dogmatic
assertions that one must use only spaces. However,
if the author of the code failed to indent properly, you don't
reconfigure the editor, you merely reconfigure the session.
It is hardly difficult to type
:set ts=4

I don't know what is involved in changing the tabstop in
other editors, but I gather it is extremely difficult, given
that the great majority of persons I encounter don't know
how to do it.