lkml.org 
[lkml]   [1997]   [Sep]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
SubjectKernel optimizations... (PC-arcitechture/long)
  Readprofile

Having caught a bad cold, I had a while to play around with things, so
the dice went up on Linux kernel, and I decided to take a look on what I
could optimize. First things first, though, ofcourse, so I took a look at
the readprofile-program for kernel profiling, and found out I could make
few changes there as well.

This is, by all means, a quick and dirty hack, but in concert with gdb
vmlinux and the -g compiled assembler-source of the modules it proved an
invaluable tool for finding what _really_ slowed things up in Linux... As
a fair warning, this is something that worked for me; most people won't
probably be satisfied with this.

In the process I found a slight bug in readprofile, though - in summing
the ticks it forgets the profile entry zero is used for granularity. This
makes all the addresses off by two bytes; however, this doesn't seem to
have any effect on result because all functions are null-padded or
otherwise exit without going to end. I've attached the patch to reaprofile
2.0 to the end of this mail.

uni2ascii

Next to the kernel-optimizations themselves. I'm not going to provide
patches for these, because being optimizations, I don't expect a lot of
people to agree with the way I've done them. Given quick descriptions,
though, any kernel-hacker worth their salts can repeat them. It would be
nicer if we got GCC auto-optimize these, though, but I can see trouble in
that happening.

First thing I noted was that during my conversion of several HPFS drives
to VFAT, readprofile showed that most of the kernels time was being spent
in uni2ascii. A quick look to the source gave a reason for this. Now, the
obivious optimization would be to form a complete unicode-translation
table to use, however in kernel we need to worry about optimizing space as
well, and we just don't have 64k of memory to spare for this, so...

Next thing in turn was getting the assembler source for the function in
fs/fat/dir.c. Using GCC 2.7.2.1 and equivalent libs on i486 and kernel
2.1.55, it turns out the compiler is a bit too faithful to the loop
exit-condition used : "while (*ip || ip[1]) {" translates into two
separate compares. Until such time as GCC realizes to combine these,
replacing the check with "while (*(short *)ip) {" leads to considerable
speed-up.
However, even this done the function is still unforgivably slow. Enters
something that may work in many other places of unicode-translation in
Linux kernel as well. Given that actually only two pages are defined in
the current code, further optimizations suggest itself, but with the
support for multi-page there, I went for a general solution.

In essence, knowing that most of the time there will be several characters
of the same unicode-page in line we'll predict that. Dividing the function
into two nested loops with the inner one breaking out if the page changes
letting the outer one fetch a new page gives _major_ speed-improvement in
most contexts. Unfortunately page zero seems to be used, so we need to
maintain the check for *(short *)ip in the inner loop. A shame.

The next optimization may be the most controversial, however, I believe
it was worth it, at least in my case. The code in the function behaves
very differently depending on whether uni_xlate in the driver is set or
not, and this check is done inside the loops - in this case the inner
loop - for _every_ letter in the filename. Tsk-tsk. GCC should really try
to optimize things like this out, but in this case I simply divided the
function into two different loop-constructs that are chosen between at
the start.

fat_readdirx

Okay, what next..? Well, surprising enough, fat_readdirx still pushes up
on the front... A quick look thru the new profiler-output, contrasted to
the gdb debug of vmlinux for finding the respective code, and finally
matched out from the assembler-output with debug symbols from dir.c
reveals an slightly surprising result : At least on my arcitecture the
conversions from FAT-filesystem charactersets & case to unix take major
cycles.

So, what to do..? Here the initial instinct might be right, and building
separate conversion-tables does indeed save some CPU here. However, we're
still losing about half-k of memory for the tables, which might be better
used elsewhere (For some strange reason the FAT filesystem uses different
mappings for the name and the extension).

Using the table lookups may also not be the fastest solution - and even if
it is, sharing the tables with some other similiar functions in the kernel
would provide more advantage for the memory. This is something I'll leave
for others to solve and find out.

Console

Okay, we've now made some major process in optimizing out the FAT-based
filesystems. For those who use them, the above optimizations may prove out
to be worth their weight in gold. There's no easy way to make a
subjective benchmark for them, but let's just say that in some
file-expensive activities the difference may be noticeable by eye.
Speaking of which, next we'll optimize something fairly visible ;)

A word of caution here : I have very little idea of the issues related
herein, however the changes described here worked on my system setup -
given that the video-adapter is rather old, there's good changes this
applies to most people with VGA/EGA video-card on intel-based machine.
Your mileage, however, may vary - those with more information, feel free
to butt in.

After doing some extensive work on the computer in shell-mode, I found
out that scrdown-function pressed itself on the front in readprofile -
output. This was a slight surprise to me - at least until I took a look
at the generated code. GCC does really terrible work here, but I guess
the kernel source is to blame in part for this.

First let's take a look at /usr/include/linux/selection.h which provides
many of the small parts used for building up the console access. Of
particular interest to us now are the scr_readw and scr_writew functions,
which are at the helm of the console CPU-usage. "normal VGA console
access" is what we're looking for, and the next comment pops up :

/*
* NOTE: "(long) addr < 0" tests for an Alpha kernel virtual address; this
* indicates a VC's backing store; otherwise, it's a bus memory address, for
* the VGA's screen memory, so we do the Alpha "swizzle"... :-)
*/
One wonders... if this is intended for Alpha, why aren't those bits of
code bounded out in #ifdef __alpha__ checks? Well, they aren't, and from
running for quite a while with them commented out it doesn't seem as if
leaving them out on non-alpha architectures causes any trouble. Slight
improvement, but we're not there yet...

Out next point of concern is the memcpyw() - function used extensively
for screen-scrolling. In fact, while we're at it, why not deal with
memsetw() at the same time - although there's a gotcha there, to which
I'll get promptly. But first memcpyw()... this particular function
translates into awful assembler-code; the target-address will be
maintained in the stack, and the addresses keep being "fixed" during
every loop.

So, what to do..? Personally, I could see only one thing to do to save
the day : using memcpy() function instead. The fact that this isn't done
in the code suggests there may be a reason for it, however doing so
hasn't manifested up as any negative effects on my machine at least as of
yet. I suppose some systems might have trouble with the generated 32-bit
transfers, but in that case we should have a way to instruct GCC to use
repz movsw instead.

On the negative side, GCC generates one unneccessary piece of code: at
the end of each memcpy(), the size is checked for parity, and missing
bytes are padded at the end. Because the size-operand for the memcpy()
command is already even, this is unneccessary. I guess it's not an easy
thing to optimize out for the compiler, and since it's out of the loop
it's little concern to me. Of course direct inline-assembler is one
choice, as we're dealing with non-portable code-section anyway.

Then over to the memsetw() calls. One would think that using memset()
here in the spirit of the last optimization would do, however since we
need to set both the character _and_ attribute we get into slight trouble
here - namely, a green background which I've come quite fond of
personally ;) If there's a command for setting the memory to specific
word instead of byte on GCC/lib, let me know; otherwise down to
inline-assy we go (using repz movsb is a bad choice for the CPU as well).

After applying these same changes to places in devices/char/console.c
where the memsetw and memcpyw functions are replaced by inline-code doing
the same thing - and remember to use __io_virt() on the video-pointers! -
you can, literally, see the difference. (In my case it's green - but
that's just because I'm too lazy to write the inline-assembler code for
word-fill;) In particular, after this an ls -lR on (V)FAT partition will
just fly. And sometimes you'd think that's what most people use their
computers for ;)

Comments?

Well, anything you'd have done differently..? Any major problems,
ideas..? Patches can be had by request, but as said I haven't included
them here, as I can't see a lot of people agreeing with the ways I've
chosen to go (I can already hear the shouts of "Kernel bloat", "Redundant
code!" and "Inline assembler! <grin>) but here's the mainlines at any
case. Now I just wish I could somehow optimize getphase() on the Adaptec
aha1520 SCSI-card... ;)

-Donwulff

Our cause is a secret within a secret,
a secret that only another secret can explain;
it is a secret about a secret veiled by a secret.--- readprofile.c Wed May 15 23:28:16 1996
+++ readprof.c Tue Sep 16 21:34:05 1997
@@ -35,7 +35,7 @@
/* These are the defaults */
static char defaultmap[]="/usr/src/linux/System.map";
static char defaultpro[]="/proc/profile";
-static char optstring[]="m:p:itvarV";
+static char optstring[]="m:p:itvlarV";

void usage()
{
@@ -45,6 +45,7 @@
"\t -p <pro-file> (default = \"%s\")\n"
"\t -i print only info about the sampling step\n"
"\t -v print verbose data\n"
+ "\t -l print in long format (load per point)\n"
"\t -a print all symbols, even if count is 0\n"
"\t -r reset all the counters (root only)\n"
"\t -V print version and exit\n"
@@ -77,8 +78,8 @@
unsigned int fn_add, next_add; /* current and next address */
char fn_name[S_LEN], next_name[S_LEN]; /* current and next name */
char mode[8];
-int c;
-int optAll=0, optInfo=0, optReset=0, optVerbose=0;
+int c, notyet=0, largest=0;
+int optAll=0, optInfo=0, optReset=0, optVerbose=0, optLong=0;
char mapline[S_LEN];
int maplineno=1;
int popenMap; /* flag to tell if popen() has been used */
@@ -97,6 +98,7 @@
case 'p': proFile=optarg; break;
case 'a': optAll++; break;
case 'i': optInfo++; break;
+ case 'l': optLong++; break;
case 'r': optReset++; break;
case 'v': optVerbose++; break;
case 'V': printf("%s Version %s\n",prgname,RELEASE); exit(0);
@@ -144,6 +146,9 @@
exit(0);
}

+ for(index=1; index<(len/sizeof(unsigned int)); index++) if(buf[index]>largest) largest=buf[index];
+ index=1;
+
total=0;

if (!(map=myopen(mapFile,"r",&popenMap)))
@@ -185,21 +190,40 @@
}
if (*mode!='T' && *mode!='t') break; /* only text is profiled */

- while (index < (next_add-add0)/step)
+ while (index <= (next_add-add0)/step) {
+ if (optLong) {
+ if (buf[index]) {
+ if(notyet==1)
+ printf("%08x\n", ((index-2)*step)+add0);
+ if(notyet>1) printf("======== %08x\n", notyet*step);
+ printf("%08x %4i ", ((index-1)*step)+add0, buf[index]);
+ for(notyet=0; (notyet<60)&&(notyet<(buf[index]/(largest/60)));
+ printf("*"), notyet++);
+ printf("\n");
+ notyet=0;
+ } else
+ notyet++;
+ }
this += buf[index++];
+ }
total += this;

fn_len = next_add-fn_add;
- if (fn_len && (this || optAll))
+ if (fn_len && (this || optAll || optLong))
{
+ if(notyet) printf("======== %08x\n", notyet*2);
if (optVerbose)
printf("%08x %-40s %6i %8.4f\n",
fn_add,fn_name,this,this/(double)fn_len);
+ else if (optLong)
+ printf("%08x-%08x %-40s %6i %8.4f\n",
+ fn_add,fn_add+fn_len-1,fn_name,this,this/(double)fn_len);
else
printf("%6i %-40s %8.4f\n",
this,fn_name,this/(double)fn_len);
}
fn_add=next_add; strcpy(fn_name,next_name);
+ notyet=0;
}
/* trailer */
if (optVerbose)
@@ -208,7 +232,9 @@
else
printf("%6i %-40s %8.4f\n",
total,"total",total/(double)(fn_add-add0));
-
+
+ printf("%i\n", largest);
+
popenMap ? pclose(map) : fclose(map);
exit(0);
}
\
 
 \ /
  Last update: 2005-03-22 13:40    [from the cache]
©2003-2011 Jasper Spaans