Efficency

[Chris Hatton]

I realize this is not a newsgroup for the total novice or homework
questions so this will be the last post until I become more familiar
with the language.

I'm looking to optimize a piece of code that reads characters from a
text file and counts the frequency of them. If someone could point me in
the right direction that would be great. I'm not looking for any code
just a couple of links to good websites as my time is very limited at
the moment.


thanks, and apologies if this post is not appropriate.


Chris

[Ben Pfaff]

Re: Efficency

Chris Hatton <chrishatton@bl ueyonder.co.uk> writes:
[color=blue]
> I'm looking to optimize a piece of code that reads characters from a
> text file and counts the frequency of them. If someone could point me
> in the right direction that would be great. I'm not looking for any
> code just a couple of links to good websites as my time is very
> limited at the moment.[/color]

Such code, if written in any kind of sensible way, will probably
be limited by the speed that you can read data from the input
file. I doubt there's much potential for optimization.
--
int main(void){char p[]="ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwC IxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+= strchr(p,*q++)-p;if(i>=(int)si zeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Dave Vandervies]

Re: Efficency

In article <420d1976$1@nnt phost.cis.strat h.ac.uk>,
Chris Hatton <chrishatton@bl ueyonder.co.uk> wrote:[color=blue]
>I realize this is not a newsgroup for the total novice or homework
>questions so this will be the last post until I become more familiar
>with the language.[/color]

Well, it's for discussion about C. We're not here to teach you the
language or do your homework, but asking questions (even simple ones,
if they're not the ones that are so simple we've seen them INT_MAX times
already) is usually a good way to get an interesting discussion started.

[color=blue]
>I'm looking to optimize a piece of code that reads characters from a
>text file and counts the frequency of them. If someone could point me in
>the right direction that would be great. I'm not looking for any code
>just a couple of links to good websites as my time is very limited at
>the moment.[/color]

As noted already, if your code is written sensibly you shouldn't have
much optimizing left to do.

The standard library's I/O system will most likely already be reading
from the file as efficiently as possibly and buffering it for your
character-at-a-time read code, so the main loop will be doing something
like this:
--------
get character from buffer
check whether buffer needs to be refilled (it usually won't)
do stuff with character
--------
....and the "do stuff with character" part would have to be pretty
inefficient for the time taken to do this to be large enough to be
noticeable compared to the time spent refilling the buffer when that's
necessary.


The general rule is to leave the micro-optimization to the compiler,
and leave any other optimization until after it's shown to be needed.


That said, if you really want to make sure that the parts that you
can optimize yourself are as efficient as possible, it's worth noting
that characters are just small integers and that array indices are
also integers. I'll let you figure out where to go from there - if you
haven't already seen something like what I'm thinking of, it'll probably
end up being more valuable as an exercise in finding new ways to solve a
problem (and, hopefully, give you another tool to use for later problems)
than as an optimization exercise. (Be sure to show us[1] your code once
you've finished so we can point out all the problems in it. If you're
just learning the language, there WILL be a bunch.)


dave

[1] Or a local guru, if you have one. Or, better yet, both.

--
Dave Vandervies dj3vande@csclub .uwaterloo.ca
I can't pick up the phone and ask for "Farsley double one double three"
whenever I fancy a pizza. Well, I could, but I'd stay hungry.
--Peter Corlett in the scary devil monastery

[CBFalconer]

Re: Efficency

Chris Hatton wrote:[color=blue]
>
> I realize this is not a newsgroup for the total novice or homework
> questions so this will be the last post until I become more familiar
> with the language.
>
> I'm looking to optimize a piece of code that reads characters from a
> text file and counts the frequency of them. If someone could point
> me in the right direction that would be great. I'm not looking for
> any code just a couple of links to good websites as my time is very
> limited at the moment.[/color]

Without any suitable includes etc. Needs limits and stdio at
least.

/* automatically zeroed */
static unsigned long counts[UCHAR_MAX+1];
....
int ch;
FILE *f;
....
/* open files etc */
....
while (EOF != (ch = getc(f))) counts[ch]++;
....
/* display the content of counts */


--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Stan Milam]

Re: Efficency

CBFalconer wrote:
[color=blue]
> Chris Hatton wrote:
>[color=green]
>>I realize this is not a newsgroup for the total novice or homework
>>questions so this will be the last post until I become more familiar
>>with the language.
>>
>>I'm looking to optimize a piece of code that reads characters from a
>>text file and counts the frequency of them. If someone could point
>>me in the right direction that would be great. I'm not looking for
>>any code just a couple of links to good websites as my time is very
>>limited at the moment.[/color]
>
>
> Without any suitable includes etc. Needs limits and stdio at
> least.
>
> /* automatically zeroed */
> static unsigned long counts[UCHAR_MAX+1];
> ....
> int ch;
> FILE *f;
> ....
> /* open files etc */
> ....
> while (EOF != (ch = getc(f))) counts[ch]++;
> ....
> /* display the content of counts */
>
>[/color]

Damn! I knew someone would beat me to it. A question I could actually
answer, too.

--
Regards,
Stan Milam
=============== =============== =============== =============== =
Charter Member of The Society for Mediocre Guitar Playing on
Expensive Instruments, Ltd.
=============== =============== =============== =============== =

[infobahn]

Re: Efficency

Stan Milam wrote:[color=blue]
>
> CBFalconer wrote:
>[color=green]
> > Chris Hatton wrote:
> >[color=darkred]
> >>I'm looking to optimize a piece of code that reads characters from a
> >>text file and counts the frequency of them. [...][/color]
> >
> > Without any suitable includes etc. Needs limits and stdio at
> > least.
> >
> > /* automatically zeroed */
> > static unsigned long counts[UCHAR_MAX+1];
> > ....
> > int ch;
> > FILE *f;
> > ....
> > /* open files etc */
> > ....
> > while (EOF != (ch = getc(f))) counts[ch]++;
> > ....
> > /* display the content of counts */
> >
> >[/color]
>
> Damn! I knew someone would beat me to it. A question I could actually
> answer, too.[/color]

You missed the chance to crit him, too. The static array makes the
program unsuitable for functionalising ; he could easily have got
the desired zeroing behaviour using = {0}. He also forgot to point
out a few rules of optimisation, such as "don't do it", for instance.
[color=blue]
> =============== =============== =============== =============== =
> Charter Member of The Society for Mediocre Guitar Playing on
> Expensive Instruments, Ltd.
> =============== =============== =============== =============== =[/color]

Where do I sign up?

[websnarf@gmail.com]

Re: Efficency

Ben Pfaff wrote:[color=blue]
> Chris Hatton <chrishatton@bl ueyonder.co.uk> writes:[color=green]
> > I'm looking to optimize a piece of code that reads characters from
> > a text file and counts the frequency of them. If someone could
> > point me in the right direction that would be great. I'm not
> > looking for any code just a couple of links to good websites as my
> > time is very limited at the moment.[/color]
>
> Such code, if written in any kind of sensible way, will probably
> be limited by the speed that you can read data from the input
> file.[/color]

This is correct.
[color=blue]
> [...] I doubt there's much potential for optimization.[/color]

But this is not. :)

First of all there is a big difference in performance between using
character by character reading via fgets() and block reading via
fread(). Obviously use the later if possible (you can't use it on
stdin unless you are using POSIX and isatty() returns 0). Ok, second
of all, if the data itself is large enough, then having the whole thing
in memory will cause additional file activity because of memory
swapping. Even data going outside of your CPU's on-chip L1 cache will
slow things down a bit.

So this leads us to the inevitable conclusion that you should read
moderately small sized blocks (something that fits in your L1 cache,
but large enough to marginalize the overhead for calling fread() --
something like a 1K to 4K block is appropriate for just about any
existing system.) Then just do a frequency count of each character in
the block from there.

Hint: You'll *demolish* the performance of what CBFalconer posted if
you do this.

---
Paul Hsieh

http://www.pobox.com/~qed/

http://bstring.sf.net/

[CBFalconer]

Re: Efficency

websnarf@gmail. com wrote:[color=blue]
>[/color]
.... snip ...[color=blue]
>
> So this leads us to the inevitable conclusion that you should read
> moderately small sized blocks (something that fits in your L1 cache,
> but large enough to marginalize the overhead for calling fread() --
> something like a 1K to 4K block is appropriate for just about any
> existing system.) Then just do a frequency count of each character
> in the block from there.
>
> Hint: You'll *demolish* the performance of what CBFalconer posted if
> you do this.[/color]

If you are referring to the reply where I said:

"while (EOF != (ch = getc(f))) counts[ch]++;"

you might be surprised. You will note that I used getc, which may
be a macro, and may operate directly on the system buffers. It
doesn't have to be a macro, that depends on many things including
QOI. If it is, it is likely to expand (inline) to something like:

if (!(f->ix)) _fillbuff(f);
if (f->eof) return EOF;
else return f->buff[ix--];

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Thomas Matthews]

Re: Efficency

Chris Hatton wrote:[color=blue]
> I realize this is not a newsgroup for the total novice or homework
> questions so this will be the last post until I become more familiar
> with the language.
>
> I'm looking to optimize a piece of code that reads characters from a
> text file and counts the frequency of them. If someone could point me in
> the right direction that would be great. I'm not looking for any code
> just a couple of links to good websites as my time is very limited at
> the moment.
>
>
> thanks, and apologies if this post is not appropriate.
>
>
> Chris[/color]

The ultimate efficiency is to read the entire text file
into memory then process the data, place results in
a buffer, then output the buffer.

The objectives are:
1. Keep the I/O continuous.
Don't break it up.

2. Process data in memory.
In most circumstances, processing data in memory
is faster than processing directly from I/O.

3. Use processor registers.
Design your code so the compiler can maximize the
use of the processor.

4. Use other processors.
If your platform has a DMA device that can place
data from a text file into memory without burdening
the main processor, use it.

Remember these points:
1. Files have start and stop overhead, regardless of
whether they are memory mapped or external devices.

2. Not all platforms have enough extra memory to
load in the largest of text files.

3. Reduce the number of branches / jumps.
All processors love sequential data processing
more than branching to different locations.
See also: Loop Unrolling, Pipelining, Instruction
Cache

4. Beware of task / program swapping.
Swapping your task with another by the operating system
may eat up any time you save by optimizing your program.

5. *** Is this optimization necessary? ***
Don't waste your efforts on unwarranted optimization.
Missing events / interrupts because of slow code is
more important than being a little slow to process
data.

--
Thomas Matthews

C++ newsgroup welcome message:

http://www.slack.net/~shiva/welcome.txt

C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq:

http://www.comeaucomputing.com/learn/faq/

Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library

[Ben Pfaff]

Re: Efficency

websnarf@gmail. com writes:
[color=blue]
> First of all there is a big difference in performance between using
> character by character reading via fgets() and block reading via
> fread(). Obviously use the later if possible (you can't use it on
> stdin unless you are using POSIX and isatty() returns 0).[/color]

You'll have to explain your rationale here. I'm not aware of
anything in the standard that says fread() may not be used on an
interactive device.

[...][color=blue]
> So this leads us to the inevitable conclusion that you should read
> moderately small sized blocks (something that fits in your L1 cache,
> but large enough to marginalize the overhead for calling fread() --
> something like a 1K to 4K block is appropriate for just about any
> existing system.) Then just do a frequency count of each character in
> the block from there.[/color]

This is the "sensible" implementation I was referring to.
[color=blue]
> Hint: You'll *demolish* the performance of what CBFalconer posted if
> you do this.[/color]

For what it's worth I hadn't looked at CBFalconer's
implementation when I posted, so that wasn't what I was referring
to.
--
"I've been on the wagon now for more than a decade. Not a single goto
in all that time. I just don't need them any more. I don't even use
break or continue now, except on social occasions of course. And I
don't get carried away." --Richard Heathfield

[Dave Vandervies]

Re: Efficency

In article <420FA295.30505 07@sbcglobal.ne t>,
Thomas Matthews <Thomas_Matthew sSpamBotsSuck@s bcglobal.net> wrote:[color=blue]
>Chris Hatton wrote:[/color]
[color=blue][color=green]
>> I'm looking to optimize a piece of code that reads characters from a
>> text file and counts the frequency of them. If someone could point me in
>> the right direction that would be great. I'm not looking for any code
>> just a couple of links to good websites as my time is very limited at
>> the moment.[/color][/color]

[color=blue]
>The ultimate efficiency is to read the entire text file
>into memory then process the data, place results in
>a buffer, then output the buffer.
>
>The objectives are:
>1. Keep the I/O continuous.
> Don't break it up.
>
>2. Process data in memory.
> In most circumstances, processing data in memory
> is faster than processing directly from I/O.
>
>3. Use processor registers.
> Design your code so the compiler can maximize the
> use of the processor.
>
>4. Use other processors.
> If your platform has a DMA device that can place
> data from a text file into memory without burdening
> the main processor, use it.[/color]

All of these will be done to the degree that they're at all useful
by any self-respecting implementation without the programmer having
to do anything about it. (#4 should be done by the OS, #3 by any
self-respecting optimizing compiler, #1 by the stdio implementation,
and #2 comes for free given that you're pulling data out of the stdio
buffer most of the time.)

[color=blue]
>3. Reduce the number of branches / jumps.
> All processors love sequential data processing
> more than branching to different locations.
> See also: Loop Unrolling, Pipelining, Instruction
> Cache[/color]

See also: Branch prediction.
A good optimizing compiler targeting hardware that supports it should
give you a "predict taken" at the branch back up to the top of the loop
and a "predict not taken" at the branch to the fill-buffer code, which
in the common case gives you the same benefits as nice sequential code
without actually increasing the code size.



Leave the micro-optimization to the compiler - it's a lot better at it
than you are. (If it's not, it's probably time to start looking for a
better compiler.)


dave

--
Dave Vandervies dj3vande@csclub .uwaterloo.ca
It seems to me that a willingness to put up with stupid governments is
also a requirement. Why didn't you guys vote in the other guy instead?
Oh, sorry, you *did*, didn't you? --Richard Heathfield in comp.lang.c