《一个奇怪的函数参数定义及解答》一文 http://blog.chinaunix.net/article.php?articleId=37822&blogId=5727 中提到 unsigned int str_len(s)
register char *s;
{
register char *t; t = s;
for (;;) {
if (!*t) return t - s; ++t;
if (!*t) return t - s; ++t;
if (!*t) return t - s; ++t;
if (!*t) return t - s; ++t;
}
} 在循环中为何使用四次if (!*t) return t - s; ++t;的问题，我想我关于“可能是流水线”的解释颇有问题，看看comp.lang.c关于此的讨论：
http://groups.google.com/group/comp.lang.c/browse_thread/thread/55936de0a54b279b/b2326ffb85ce03f4?hl=en#b2326ffb85ce03f4
 | In article <3mlogiF176so...@individual.net>,
"Jan Richter" <vincent00...@yahoo.de> wrote:
 Reply
> Hi there,
> the Code below shows DJBs own implementation of strlen (str_len):
> unsigned int str_len(char *s)
> {
> register char *t;
> t = s;
> for (;;) {
> if (!*t) return t - s; ++t;
> if (!*t) return t - s; ++t;
> if (!*t) return t - s; ++t;
> if (!*t) return t - s; ++t;
> }
> }
> I understand the code so far, but I have a question about the loops.
> To me, it seems he used loop unrolling (aka duff's device) to optimize
> the code while it is executed.
Loop unrolling != Duff's device.
Duff's device is a combination of loop unrolling + completely perverted
usage of a switch statement, which is likely to prevent the compiler
from optimising the code
> But why did he use four loops? When
> the function is invoked, he didn't know how big "s" is. Or am I wrong here?
> I always thought, to unroll a loop I need to know how often the loop is
> used.
As you can see, knowing how often a loop will be executed is not
necessary. However, before you unroll a loop by hand, you should check
whether the compiler can do loop unrolling itself, which is likely to
produce more efficient code.
|
|
Reply
Keith Thompson wrote:
> "Jan Richter" <vincent00...@yahoo.de> writes:
> > the Code below shows DJBs own implementation of strlen (str_len):
> > unsigned int str_len(char *s)
> > {
> > register char *t;
> > t = s;
> > for (;;) {
> > if (!*t) return t - s; ++t;
> > if (!*t) return t - s; ++t;
> > if (!*t) return t - s; ++t;
> > if (!*t) return t - s; ++t;
> > }
> > }
> The idea of loop unrolling is that it avoids the overhead of a test on
> each iteration,
That's supposed to be the idea,
but the above code has one test per increment
just like a naive portable implementation.
size_t str_len(const char *s)
{
size_t n = 0;
while (s[n] != '') {
++n;
}
return n;
}
--
pete
|
|
pete <pfil...@mindspring.com> wrote:
> Keith Thompson wrote:
>> "Jan Richter" <vincent00...@yahoo.de> writes:
>> > the Code below shows DJBs own implementation of strlen (str_len):
>> > unsigned int str_len(char *s)
>> > {
>> > register char *t;
>> > t = s;
>> > for (;;) {
>> > if (!*t) return t - s; ++t;
>> > if (!*t) return t - s; ++t;
>> > if (!*t) return t - s; ++t;
>> > if (!*t) return t - s; ++t;
>> > }
>> > }
>> The idea of loop unrolling is that it avoids the overhead of a test on
>> each iteration,
> That's supposed to be the idea,
> but the above code has one test per increment
> just like a naive portable implementation.
> size_t str_len(const char *s)
> {
> size_t n = 0;
> while (s[n] != '') {
> ++n;
> }
> return n;
> }
IANAAP (I am not an assembly programmer) so I don't know how the code
typically translates, but it seems to me that it does provide some benefit
- it reduces by 75%[1] the number of jump statements executed (to return
from the end to the start of the loop).
[1] When the number of iterations is not a multiple of 4 this is only
approximate.
--
http://members.dodo.com.au/~netocrat
Reply |
| Christian Bau wrote
(in article
<christian.bau-6BC92C.22422219082...@slb-newsm1.svr.pol.co.uk>):
> In article <3mlogiF176so...@individual.net>,
> "Jan Richter" <vincent00...@yahoo.de> wrote:
>> Hi there,
>> the Code below shows DJBs own implementation of strlen (str_len):
>> unsigned int str_len(char *s)
>> {
>> register char *t;
>> t = s;
>> for (;;) {
>> if (!*t) return t - s; ++t;
>> if (!*t) return t - s; ++t;
>> if (!*t) return t - s; ++t;
>> if (!*t) return t - s; ++t;
>> }
>> }
>> I understand the code so far, but I have a question about the loops.
>> To me, it seems he used loop unrolling (aka duff's device) to optimize
>> the code while it is executed.
> Loop unrolling != Duff's device.
> Duff's device is a combination of loop unrolling + completely perverted
> usage of a switch statement, which is likely to prevent the compiler
> from optimising the code
It's suddenly being discussed again, probably as a result of an
article in DDJ (Doctor Dobb's Journal) about it in the August
issue. Ralf Holly proposed using it in macro form for generic
loop unrolling, which probably makes people misunderstand its
original purpose.
He proposed something like
#define DUFF_DEVICE_8(macroCount, macroAction) \
do { \
size_t duffcount = (macroCount); \
size_t dufftimes = (duffcount + 7) >>3u; \
switch(duffcount & 7) { \
case 0: do { macroAction; \
case 7: macroAction; \
case 6: macroAction; \
case 5: macroAction; \
case 4: macroAction; \
case 3: macroAction; \
case 2: macroAction; \
case 1: macroAction; \
} while (--dufftimes > 0); \
} \
} while (0)
Of course, the caller has to know not to call with a 0
countvalue or it will execute 8 times instead.
Probably not all that practical in general use, but you might
find somewhere, (after profiling) where it makes some sense.
--
Randy Howard (2reply remove FOOBAR)
Reply |
|
pete <pfil...@mindspring.com> writes:
> Keith Thompson wrote:
[...]
>> The idea of loop unrolling is that it avoids the overhead of a test on
>> each iteration,
> That's supposed to be the idea,
> but the above code has one test per increment
> just like a naive portable implementation.
Yes, as I said in the portion of the article that you snipped.
--
Keith Thompson (The_Other_Keith) k...@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Reply |
| In article <de4pqe$i1...@chessie.cirr.com> Christopher Benson-Manica <a...@nospam.cyberspace.org> writes:
> Giannis Papadopoulos <ipapa...@inf.uth.gr> wrote:
>
> > No benefit... Maybe it is written for a compiler that does not know how
> > to unroll loops...
>
> Probably; an implementation simple-minded enough to trust the
> programmer when he uses the "register" storage class specifier
> probably could use some help unrolling a loop. The VAX compiler for
> which Duff originally wrote his device was (presumably) such an
> implementation.
Make that probably and presumably to "certainly". Loop unrolling was pretty
unheard of before the 80s. It came only in general use in the 80s when more
pipe-lined processors appeared (and it made most sense on those). General
compilers doing loop unrolling only appeared in the early 90s (if I remember
right). Even CDC Fortran compilers of the 70s and early 80s did not do
loop unrolling, while it made perfect sense on the CDC Cybers.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Reply |
|
In article <lnacjdk46z....@nuthaus.mib.org> Keith Thompson <k...@mib.org> writes:
...
> The idea of loop unrolling is that it avoids the overhead of a test on
> each iteration, falling through from one statement to the next and
> performing the test and branch only once every 4 elements.
No. It all has to do with pipelining processors, and the *instruction*
cache. It also has effect on systems where a backward branch is much
more expensive than a forward branch.
> The number
> of times a loop is to be unrolled is a tradeoff between speed and code
> size -- and if it's unrolled too much (say, 1024 times), the code size
> itself can make it run slower due to cache issues. This is all
> *extremely* system-specific, which is why the whole thing is best left
> to the compiler.
Indeed. But I think the code dates from a time when compilers did not do
loop unrolling.
> I'd be surprised to see the above code performing better than strlen()
> on any modern implementation, particularly since an implementation is
> free to implement strlen() using whatever non-portable tricks it likes
> to squeeze out the last clock cycle.
Again, indeed. There are extremely easy, and efficient, techniques to
determine (on a 64 bit system) whether any of 8 consecutive 8-bit entities
is zero.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Reply |
|
In article <0001HW.BF2BCBB9008348F7F0386...@news.verizon.net>, Randy Howard <randyhow...@FOOverizonBAR.net> writes:
> It's suddenly being discussed again, probably as a result of an
> article in DDJ (Doctor Dobb's Journal) about it in the August
> issue. Ralf Holly proposed using it in macro form for generic
> loop unrolling, which probably makes people misunderstand its
> original purpose.
> He proposed something like
> #define DUFF_DEVICE_8(macroCount, macroAction) \
> do { \
> size_t duffcount = (macroCount); \
> size_t dufftimes = (duffcount + 7) >>3u; \
> switch(duffcount & 7) { \
> case 0: do { macroAction; \
> case 7: macroAction; \
> case 6: macroAction; \
> case 5: macroAction; \
> case 4: macroAction; \
> case 3: macroAction; \
> case 2: macroAction; \
> case 1: macroAction; \
> } while (--dufftimes > 0); \
> } \
> } while (0)
> Of course, the caller has to know not to call with a 0
> countvalue or it will execute 8 times instead.
Unless I'm missing something, that's easily fixed with a
if (!duffcount) break;
before the switch. (Testing duffcount avoids using macroCount,
which might have side effects, twice, of course.)
A worse problem would be using it with a negative count; hopefully
the compiler would provide a useful diagnostic for the conversion
between a signed value and a size_t when duffcount is initialized,
but that's a QoI issue. (Also, I know far too many C programmers
who routinely ignore such diagnostics, partly because their code is
full of them. I suppose that's a QoP issue.)
> Probably not all that practical in general use, but you might
> find somewhere, (after profiling) where it makes some sense.
Agreed. I have found cases where relatively recent commercial
implementations don't unroll even simple loops where unrolling has a
significant benefit. Of course, if the loop isn't in a performance-
critical path, it doesn't matter anyway.
--
Michael Wojcik michael.woj...@microfocus.com
We are subdued to what we work in. (E M Forster)
![]()
|
|
