as small as possible

A

Arne Demmers

Hi,

As a project of mine I have to do some C programming, which in fact isn't
the real problem. The problem it self is that I will have to write some code
that is as minimal as possible, and as fast as possible.

Are there any gidelines for this kind of thing? How do I know if my code is
possibly the smallest and fastest I could write for a certain algo?? And
where can I find thise kind of guidelines???

Many thanks in advance

Arne Demmers
 
M

Mark McIntyre

How do I know if my code is
possibly the smallest and fastest I could write for a certain algo??

There's no way to know this. Here's what to do

1) code the algo as simply and clearly as you can. DO NOT try to
outsmart the compiler, it can optimise much better than you can.

2) test it, make sure it works. No point optimizing a broken
algorithm.

3) check performance matches your requirements. You presumably have
some actual requirements to compare to, if not, go back to your boss
and ask for some.

4) then and only then, start trying to optimise. At this stage, you
may need to become an expert programmer, and to learn assembly
language.
And where can I find thise kind of guidelines???

Rules of Optimization:
Rule 1: Don't do it.
Rule 2 (for experts only): Don't do it yet.
- M.A. Jackson

"We should forget about small efficiencies, say about 97% of the time:
premature optimization is the root of all evil."
- Donald Knuth

"More computing sins are committed in the name of efficiency (without
necessarily achieving it) than for any other single reason - including
blind stupidity."
- W.A. Wulf

Mark McIntyre
 
A

Arne Demmers

4) then and only then, start trying to optimise. At this stage, you
may need to become an expert programmer, and to learn assembly
language.

So the thing your pointing at is working with in C embedde assembler code to
get it as optimal as possible, like

__asm{
some instructions (less than the C compiler had generated but does the same
thing)
}

or are you meaning sometrhing else?

thanks for your answer

Arne Demmers
 
I

Ico

Arne Demmers said:
As a project of mine I have to do some C programming, which in fact isn't
the real problem. The problem it self is that I will have to write some code
that is as minimal as possible, and as fast as possible.

My first question would be : *why* do you want to optimize ? Are you
really sure it is necassery ?
Are there any gidelines for this kind of thing? How do I know if my code is
possibly the smallest and fastest I could write for a certain algo ??

Size and speed are often contradictionary goals when optimizing, so you
will have to make choices and concessions here.

I do not know it it is possible to calculate the smallest or fasted
implementation of an algorithm. The first rule for optimizing is always:
measure! Do not optimize anything before you have actually measured it
is worth optimizing.

1. Design your algorithm. Design it with algorithms that are known to be
fast. (learn about O() notation etc)
2. Test your code and make sure it is 100% correct
3. Ask yourself it is really necassery to optimize
4. Measure where the code is spending the most of it's time
5. Optimize *only* this piece of code
6. Go back to step 2
And where can I find thise kind of guidelines???

Richard Heathfield's book 'C Unleashed' has a good chapter about
optimizing.
 
F

Flash Gordon

Arne said:
Hi,

As a project of mine I have to do some C programming, which in fact isn't
the real problem. The problem it self is that I will have to write some code
that is as minimal as possible, and as fast as possible.

It's hard to get much more minimal than the following

int main()
{
return 0;
}

Note, I know int main(void) is better style, but I decided to make the
source compatible with K&R C which did not have void.
Are there any gidelines for this kind of thing?

Yes, find the best algorithm for the job, design the software properly
(including error handling) then implement it what you have designed and
let the optimiser that comes with the compiler do its job.
> How do I know if my code is
possibly the smallest and fastest I could write for a certain algo??

That is impossible to prove in the general case. Anyway, which is more
important, the program finishing quickly or getting the correct answer?
If the program finishing quickly is more important use the program I
provide above, if not implement your chosen algorithm in an
understandable way, get it working, then see if you have performance
problems. A large amount of the advice on how to "optimize" C code is
based on what will run faster on specific implementations, and what is
fastest changes as the compiler and library and hardware are changed.
> And
where can I find thise kind of guidelines???

Rules of Optimization:
Rule 1: Don't do it.
Rule 2 (for experts only): Don't do it yet.
- M.A. Jackson

In general, algorithm questions do not belong in here, comp.programming
might be a better place.
 
I

Ico

Arne Demmers said:
So the thing your pointing at is working with in C embedde assembler code to
get it as optimal as possible, like

__asm{
some instructions (less than the C compiler had generated but does the same
thing)
}

Using assembly breaks portablity; you should ask yourself if that is
want you want.

I find that, when optimizing, it is often not even necassery to *write*
assembly yourself, but it is more important to understand the assembly
oputput of your compiler. If you can predict what a certain change in
your source will do to the resulting assembly, you can make faster or
smaller programs in C, which are still portable and run correct on other
platforms.


Ico
 
A

Arne Demmers

So what you all suggest is trial and error. Because I thought there where
some general rules like:

int counter = 0;

while(counter < something)
{
do work;
counter++;
}
OR
for(int counter = 0; counter < something; counter++)
{
do work;
}

are totaly different implemented in assembly, or is this only compiler (and
its settings offcourse) dependant?

Arne Demmers
 
I

Ico

Arne Demmers said:
So what you all suggest is trial and error. Because I thought there where
some general rules like:

int counter = 0;

while(counter < something)
{
do work;
counter++;
}
OR
for(int counter = 0; counter < something; counter++)
{
do work;
}

are totaly different implemented in assembly, or is this only compiler (and
its settings offcourse) dependant?

Yes, this is 100% compiler (and settings) dependent. The first may be
faster then the latter on your system, but it might not be on mine.

The most important thing to do when optimizing is to make sure your
algorithm's are smart. Usually it is best to leave microoptimizations
like this up to the compiler. I find it's often much better at
optimizing then I am, considering the time *I* would have to spend to
manually accomplish a similar speedup.
 
F

Flash Gordon

Arne Demmers wrote:

Please provide some context. You can't be sure that the people reading
have seen (or can remember) the article you are replying to. In this
case something as simple as:

<snip advice about optimisation>

might have been sufficient. See http://cfaj.freeshell.org/google/ for
details on how to get Google to do the right thing and other useful advice.
So what you all suggest is trial and error.

No, most of us are suggesting in the first instance *don't* try to
optimise your C, write it to be clear.

If, and only if, you have ensured you are using the best algorithm, you
have written clear code and proved it to be correct, and you have
measured it and found you really do have a problem, do you consider what
to do about optimising the code.

Having got through the above and found your really do have to do
something. What you do is measure. Then you measure some more.
Eventually you will probably find there is a small piece of code that
you need to optimise, then you look at whether it is written as clearly
and simply as possible for the compiler. Having made the code as simple
as you can and remeasured to check you still have a problem, and
remeasured some more to ensure the problem is still in the same place,
you then look at the assembler the compiler is producing and consider
your options.
> Because I thought there where
some general rules like:

int counter = 0;

while(counter < something)
{
do work;
counter++;
}
OR
for(int counter = 0; counter < something; counter++)
{
do work;
}

are totaly different implemented in assembly, or is this only compiler (and
its settings offcourse) dependant?

The general rule with something like that is write what will be clear
and maintainable. The compiler can, and generally will, do this kind of
transformation. If it doesn't do something that simple then look to see
if there is a better compiler you can use that will. After having
verified that you are telling the compiler to optimise the code, of course.
 
M

Mark McIntyre

So the thing your pointing at is working with in C embedde assembler code to
get it as optimal as possible, like

__asm{
some instructions (less than the C compiler had generated but does the same
thing)
}

Something like that. Its not a C question though is it?

And seriously, if you get to this stage in a paid job and you don't
already know how to do this or have someone showing you how to do it,
you need to consider changing jobs, you're about to fsck up royally
and get in big big trouble.

Mark McIntyre
 
M

Mark McIntyre

So what you all suggest is trial and error. Because I thought there where
some general rules like:

snip example of while vs for.

NO NO NO.

Its decades since such childish rules could be applied. Any decent C
compiler can optimise both to exactly the same code. What, you think
you're smarter than the guys over at MS / Borland / gcc / wherever who
wrote the compiler optimisation routines? Ha!

This is what I meant by not trying to outsmart the compiler. Just Dont
Do It, its worse than heroin.


Mark McIntyre
 
A

Arne Demmers

And seriously, if you get to this stage in a paid job and you don't
already know how to do this or have someone showing you how to do it,
you need to consider changing jobs, you're about to fsck up royally
and get in big big trouble.

Mark McIntyre
--

Who has ever said that I was in the possition of getting paid for what I do.
I don't think this is a nice way to answer people who don't know sh*t about
anything like this. The meaning of my initial question was in purpose of
considering to take a look at the generated assembly and see if it was
possible to make some improvements, but like most of the persons, who send a
answer, stated, I will take a glance, but only to look, because it seems
that making changes is too time consuming, as far as improvements even can
be made.

Arne
 
F

Flash Gordon

Arne said:
Who has ever said that I was in the possition of getting paid for what I do.

No one. Mark said *if*.

By the way, *please* leave in the attribution lines. You know, the
little bits that say who said what? Like "Arne Demmers wrote:" above? I
only know you are replying to Mark McIntyre because I happen to have
received both posts in the same update.
I don't think this is a nice way to answer people who don't know sh*t about
anything like this.

Mark can be abrasive sometimes, as can we all, but all he was doing this
time was giving good advice. If you are playing about for your own
personal interest that is one thing, but if you were in a paid job and
were having to look at this without either the knowledge or local advice
then you would not stand any chance of doing it. I used to program a lot
professionally in assembler and I would have major problems trying to
produce efficient assembler for a lot of modern processors, they are
just too complex.

People are trying to give good advice, and if they are vehement in there
responses it is because they have seen the messes that people make when
they try to optimise before they have the knowledge and experience to
understand what is going on, and the messes people make who *do* have
the experience that they should know.
> The meaning of my initial question was in purpose of
considering to take a look at the generated assembly and see if it was
possible to make some improvements, but like most of the persons, who send a
answer, stated, I will take a glance, but only to look, because it seems
that making changes is too time consuming, as far as improvements even can
be made.

Looking at the assembler output of an optimising compiler can be an
interesting and enlightening experience. However, in general, you need
to know both the high level language well and the assembler well to
understand what is going on and why.

I might be wrong, but you sound like you don't yet have the level of
experience to follow the assembler that a modern optimising compiler
will produce.
 
A

Arne Demmers

Flash Gordon said:
No one. Mark said *if*.

By the way, *please* leave in the attribution lines. You know, the little
bits that say who said what? Like "Arne Demmers wrote:" above? I only know
you are replying to Mark McIntyre because I happen to have received both
posts in the same update.


Mark can be abrasive sometimes, as can we all, but all he was doing this
time was giving good advice. If you are playing about for your own
personal interest that is one thing, but if you were in a paid job and
were having to look at this without either the knowledge or local advice
then you would not stand any chance of doing it. I used to program a lot
professionally in assembler and I would have major problems trying to
produce efficient assembler for a lot of modern processors, they are just
too complex.

People are trying to give good advice, and if they are vehement in there
responses it is because they have seen the messes that people make when
they try to optimise before they have the knowledge and experience to
understand what is going on, and the messes people make who *do* have the
experience that they should know.

Yes I undestand what your point is, in this case. I beleave indeed it is
horrible to recieve totally messed up code, but Mark could have mentioned
that, thats all. It was rather shocking of reading his comment, it was like
being attacked.
But if that was what you ment Mark, no offence taken.
Looking at the assembler output of an optimising compiler can be an
interesting and enlightening experience. However, in general, you need to
know both the high level language well and the assembler well to
understand what is going on and why.

I might be wrong, but you sound like you don't yet have the level of
experience to follow the assembler that a modern optimising compiler will
produce.

Its like this. In my studies we have learned some high level languages, C
being one of them, and we also studied assembler into some case studies
(ours were a SPARC and a 8051). And indeed as you mention it seems we never
had any oupling between the high level language and the low level assembler,
being the compiler. So this being the reason I indeed know nothing about
that, and ask this, for you *experts*, strange questions.
But from all of the things that are reached here I got the following, which
means I learned something valuable, that the optimalisation of C code
depends on the algo I implement, being the best one there is for a given
problem, and on the used compiler and its optimization (like gcc -O3...)
settings and that for my own sake I should trust on the optimization of the
compiler aénd stay of the assembler.

Anyone correct me if I'm wrong.
Thank for your help everyone

Arne Demmers
 
M

Mark McIntyre

Who has ever said that I was in the possition of getting paid for what I do.

Nobody. I said "if", and its a real point.
I don't think this is a nice way to answer people who don't know sh*t about
anything like this.

Well first off, I already answered you but you didn't seem to take the
hint - not even when I postpended some quotes from some Serious Dudes
in the computing world

And secondly, the above is a very nice reply. There's no insults,
swear words or concerns about your parentage, competence or
intelligence.

You may not like it, but its a serious and polite comment, I genuinely
would be concerned that if you were being paid to optimise in this
fashion, you'd shortly be either out of a job or responsible for a
disaster.
Mark McIntyre
 
G

Gordon Burditt

As a project of mine I have to do some C programming, which in fact isn't
the real problem. The problem it self is that I will have to write some code
that is as minimal as possible, and as fast as possible.

Fast, small, cheap. Pick any two.

First, decide what you want to optimize. Does RAM cost as much as ROM?
If it's a tradeoff of 2 milliseconds in an inner loop vs. 2 meg of
hash tables, which is better, fast or small? Is it better to use
1 meg of ROM (code) to save 100K of read-write tables (variables)?
Are there any gidelines for this kind of thing?

If it doesn't have to work correctly, any program can be written
with 0 bytes and execute in 0 time. And it has no hardware requirements.
How do I know if my code is
possibly the smallest and fastest I could write for a certain algo??

When you have spent an infinite amount of money on coding it.
And
where can I find thise kind of guidelines???

There are newsgroups dedicated to embedded controllers and such.
They deal with issues like this a lot.

Gordon L. Burditt
 
M

Mark McIntyre

Abusive Idiot.
*plonk*

Anyone who didn't bother to read the entire of my comment, and who
thnks the below is abusive, is no loss to me.

(original remark reappended for comparison)
And seriously, if you get to this stage in a paid job and you don't
already know how to do this or have someone showing you how to do it,
you need to consider changing jobs, you're about to fsck up royally
and get in big big trouble.
Mark McIntyre
 
M

Mark B

Mark McIntyre said:
Anyone who didn't bother to read the entire of my comment, and who
thnks the below is abusive, is no loss to me.

I'm surprised you didn't make the connection between this and your
responses to me on the 'realloc question' thread last week...
I saw the opportunity to take you out of context (as you did me)
and used it to see if it would elicit a response from you.
Nice to find that your killfile remains as empty as mine. :)

Regards,
Mark
 
M

Mark McIntyre

I'm surprised you didn't make the connection between this and your
responses to me on the 'realloc question' thread last week...

I rarely make connections between threads, it so often leads to
responding on account of something said in heat in relation to a
totally different topic.
Nice to find that your killfile remains as empty as mine. :)

Actually, it has (sfx: someone walking down long echoing corridor and
then back up) a couple of hundred entries. Most are for topics rather
than people though.
Mark McIntyre
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
474,173
Messages
2,570,937
Members
47,481
Latest member
ElviraDoug

Latest Threads

Top