---559023410-1903590565-906392824=:24308
Content-Type: TEXT/PLAIN; charset=US-ASCII
On Wed, 16 Sep 1998, Jukka Tapani Santala wrote:
> work, it suddenly struck to me that I have "The Programmers PC
> Sourcebook", 2nd edition, in my bookshelf. According to this, Microsoft
This problem solved my other problem, in fat_getdirx(), which is by no
doubt one of the most wretched functions in the kernel. Among other
things, it nests up into deepening loops, the last of which is one to go
one by one thru the FAT filename's characters, doing case-transform and
other stuff and copying them to the display-name for Linux fs. These
final loops are so nested and complex that the source generated by the
optimizer is worthy of being used as an example of how to slow a Pentium
to crawl... So simplifying it has been a high priority for me for a while.
I unrolled them in one attempt, but among other things I wasn't satisfied
by the (admittedly low) increased memory image size. Not onlyt hat, but
the performance was still quite poor due to fundamental problems in the
processing. Recently, I checked the mentioned resource book, and noted
that according to it the FAT file-records names must be space-padded.
Another table told me that spaces were not allowed characters in
filenames, letting me get rid of a lot of the complex logic...
...however, trust Microsoft to change their clearly stated standards. I
quickly noticed that VFAT filenames in fact did contain spaces in middle
of the filenames. So it didn't do to simply process until the fist space.
This forced me to take little more complex approach, as demonstrated in
this patch. First, a simple reverse loop finds the section formed
completely of spaces (essentially reverse strspn), and then the actual
paydata is processed by considerably lightened version of the original
loops. The patch applies to fs/fat/dir.c
Other optimizations included here are moving 0x05 check out of the first
loop. Note: Warning! Having it in the loop as originally done is not
inefficient, but also a clear violation of the standard. 0x05 only has a
special meaning as first letter of the name, as implemented in other parts
of the kernel code. This won't cause current problems since 0x05 is
apparently not allowed in other parts of the filename. In addition, we can
now skip the second loop altogether if the space-checking tells us it's
all spaces.
Some possibility for optimization still exists even for this stretch of
code; say, for example, unrolling it. I'm currently playing around trying
to do something with the annoying case-switch code. Removing it altogether
is something that suits me (I like seeing what case the files are in the
DOS filesystem even if it's asthetically unpleasing), but I can imagine
this can cause problems with programs thinking there isn't a file by given
name etc.
Unfortunately the "boundary chars" of the letters many are also allowed
in MSDOS filenames, so a simple bit-operation for switching case isn't
usable. So my thoughts are lead towards an actual table; since I hate
wasting 256 bytes (or worse, aligned) for something like this, not to
mention the cache and alignment issues, I'm thinking of trying something
like 'if (ch&32!=ch) char=tab32[ch&31];' and do away with 32 element
table, which could still be somewhat defensible.
Another issue worth a test is whether pulling the case-translation stuff
out from the copy-loops and running them in a separate pass on the whole
ptname string would be more effective? My guess is that'd be more
effective... So, does anybody know of a reason not to do that? Is there
anywhere a basic letters-only casetable for conversion, and any reason
the aboive 32 element method would be a bad idea? Opinions on other
issues raised in this discussion?
-Donwulff
---559023410-1903590565-906392824=:24308
Content-Type: TEXT/PLAIN; charset=US-ASCII; name="spacelen.patch"
Content-Transfer-Encoding: BASE64
Content-ID: <Pine.SOL.3.90.980921184704.24308B@ankkuri.uwasa.fi>
Content-Description:
LS0tIGRpci5jMglGcmkgU2VwIDE4IDIxOjAwOjUzIDE5OTgNCisrKyBkaXIu
dwlGcmkgU2VwIDE4IDIyOjIxOjEyIDE5OTgNCkBAIC0xMjIsNyArMTIyLDcg
QEANCiAJaW50IGJvdGgpDQogew0KIAlzdHJ1Y3Qgc3VwZXJfYmxvY2sgKnNi
ID0gaW5vZGUtPmlfc2I7DQotCWludCBpbm8saSxpMixsYXN0Ow0KKwlpbnQg
aW5vLGksaTI7DQogCWNoYXIgYzsNCiAJc3RydWN0IGJ1ZmZlcl9oZWFkICpi
aDsNCiAJc3RydWN0IG1zZG9zX2Rpcl9lbnRyeSAqZGU7DQpAQCAtMjM5LDYg
KzIzOSw3IEBADQogCQkJY2hhciAqcHRuYW1lID0gYnVmbmFtZTsNCiAJCQlp
bnQgZG90b2Zmc2V0ID0gMDsNCiAJCQlpbnQgd2FzX2xvbmcgPSBpc19sb25n
Ow0KKwkJCWludCBsYXN0Ow0KIA0KIAkJCWlmIChpc19sb25nKSB7DQogCQkJ
CXVuc2lnbmVkIGNoYXIgc3VtOw0KQEAgLTI2MywyNyArMjY0LDI2IEBADQog
CQkJCWRvdG9mZnNldCA9IDE7DQogCQkJCXB0bmFtZSA9IGJ1Zm5hbWUrMTsN
CiAJCQl9DQotCQkJZm9yIChpID0gMCwgbGFzdCA9IDA7IGkgPCA4OyBpKysp
IHsNCi0JCQkJaWYgKCEoYyA9IGRlLT5uYW1lW2ldKSkgYnJlYWs7DQorCQkJ
Lyogc2VlIG5hbWVpLmMsIG1zZG9zX2Zvcm1hdF9uYW1lICovDQorCQkJaWYg
KHB0bmFtZVswXSA9PSAweDA1KSAqcHRuYW1lID0gMHhFNTsNCisJCQlsYXN0
PTg7IHdoaWxlKGxhc3QmJihkZS0+bmFtZVstLWxhc3RdPT0nICcpKTsNCisJ
CQlmb3IgKGkgPSAwOyBpIDw9IGxhc3Q7IGkrKykgew0KKwkJCQljID0gZGUt
Pm5hbWVbaV07DQogCQkJCWlmIChjID49ICdBJyAmJiBjIDw9ICdaJykgYyAr
PSAzMjsNCi0JCQkJLyogc2VlIG5hbWVpLmMsIG1zZG9zX2Zvcm1hdF9uYW1l
ICovDQotCQkJCWlmIChjID09IDB4MDUpIGMgPSAweEU1Ow0KLQkJCQlpZiAo
YyAhPSAnICcpDQotCQkJCQlsYXN0ID0gaSsxOw0KIAkJCQlwdG5hbWVbaV0g
PSBjOw0KIAkJCX0NCi0JCQlpID0gbGFzdDsNCi0JCQlwdG5hbWVbaV0gPSAn
Lic7DQotCQkJaSsrOw0KLQkJCWZvciAoaTIgPSAwOyBpMiA8IDM7IGkyKysp
IHsNCi0JCQkJaWYgKCEoYyA9IGRlLT5leHRbaTJdKSkgYnJlYWs7DQotCQkJ
CWlmIChjID49ICdBJyAmJiBjIDw9ICdaJykgYyArPSAzMjsNCi0JCQkJaWYg
KGMgIT0gJyAnKQ0KLQkJCQkJbGFzdCA9IGkrMTsNCi0JCQkJcHRuYW1lW2ld
ID0gYzsNCisJCQlsYXN0PTM7IHdoaWxlKGxhc3QmJihkZS0+ZXh0Wy0tbGFz
dF09PScgJykpOw0KKwkJCWlmKGxhc3QpIHsNCisJCQkJcHRuYW1lW2ldID0g
Jy4nOw0KIAkJCQlpKys7DQorCQkJCWZvciAoaTIgPSAwOyBpMiA8PSBsYXN0
OyBpMisrKSB7DQorCQkJCQljID0gZGUtPmV4dFtpMl07DQorCQkJCQlpZiAo
YyA+PSAnQScgJiYgYyA8PSAnWicpIGMgKz0gMzI7DQorCQkJCQlwdG5hbWVb
aV0gPSBjOw0KKwkJCQkJaSsrOw0KKwkJCQl9DQogCQkJfQ0KLQkJCWlmICgo
aSA9IGxhc3QpICE9IDApIHsNCisJCQlpZiAoaSAhPSAwKSB7DQogCQkJCWlm
ICghc3RyY21wKGRlLT5uYW1lLE1TRE9TX0RPVCkpDQogCQkJCQlpbm8gPSBp
bm9kZS0+aV9pbm87DQogCQkJCWVsc2UgaWYgKCFzdHJjbXAoZGUtPm5hbWUs
TVNET1NfRE9URE9UKSkNCg==
---559023410-1903590565-906392824=:24308--
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/