2005年09月13日

Duff's device

プログラマー、もしくはソフトウェアエンジニアにしか分からない話。

ここ数日、プログラミング上の一般的なトピックについて話し合う機会があった。いにしえのCの世界で、短い回数のループ処理に時間がかかりすぎる場合、どうすれば高速化できるか？gotoはどういうときに善で、どういう使い方が悪か？swich文の中でのcase文のフォールスルーはあったほうがいいか、ないほうがいいか？などなど。

まさかこの話を全てカバーするコードがあるとは思いもよらなかった。しかもかなり有名らしい。初出は２０年も前か…。

ちなみに、上の質問の答え（の一例）は、ループ内の処理をベタに繰り返し書いてしまって、ループを外すか、ループ回数を減らす（例えば４回同じ処理を繰り返し書いて、ループ回数を1/4にする）。多重ループの中から一気に抜けるためのgotoは悪いとは言い切れないが、ループ外からループ内に飛んでくるgotoはほぼ確実に悪い（という説がある）。フォールスルーについては、賛否両論。否定派が優勢か。

そして、以下のコードが Duff's device. 元々ループ処理が遅かったのでループ回数を1/8にして高速化しようとし、でもそうすると処理回数を８で割った「あまりの回数文の処理」がめんどくさくなるので、何とか上手く出来ないかとやってみたらこうなったらしい。もちろんコンパイル出来るし、きちんと動作する。本人による説明つきのページはこちら。

send(to, from, count)
register short *to, *from;
register count;
{
  register n=(count+7)/8;
    switch(count%8){
      case 0: do{ *to = *from++;
      case 7:     *to = *from++;
      case 6:     *to = *from++;
      case 5:     *to = *from++;
      case 4:     *to = *from++;
      case 3:     *to = *from++;
      case 2:     *to = *from++;
      case 1:     *to = *from++;
              } while(--n>0);
  }
}

すげえ。でも考えてみると確かに、caseは殆どラベルと一緒だし、do-while内にラベルがあるのも、switchブロックの中にループがあるのもなんら違法ではない。ちなみに、*to に ++ がついていないのは間違いではない。メモリコピーをしているわけではなく、ＩＯレジスタに書き込んでいるらしい。

検索してみると色々なページで色々な説明と共に紹介されている。Cはデフォルトではcase文のフォールスルーをサポートしているが、それについてのDuffのコメントがなかなか良い。

“This code forms some sort of argument in that debate, but I'm not sure whether it's for or against.”

Trackback on "Duff's device"

以下1件のトラックバックはこのページのエントリー"Duff's device"を参照しています。

このエントリーのトラックバックURL: 

» Duff's Device

  • 2005年09月15日 00:28
  • from Cagylogic

非常に珍しい書き方をしたCのコードを見た。その名もDuff's Device。... [続きを読む]

Comment on "Duff's device"

I’d have to acquiesce with you here. Which is not something I typically do! I really like reading a post that will make people think. Also, thanks for allowing me to speak my mind!

I’ve been searching for a little for any high-quality stories and weblog posts on this kind of area . After sufing in Bing, I at last stumbled upon your blog. After studying this essay, I knew I have discovered just what I need. Thnx!

Hi, a fantastic blog post dude. Thank you But I’m experiencing trouble with your RSS . Don't know why Fail to subscribe. Does anyone having similar RSS trouble? Anybody who can assist please reply. Thanks!

I’ve lately began a blog, the knowledge you present on this website has helped me tremendously. Thank you for all of your time & work.

i know i’m a little off topic, but i just wanted to say i love the layout of your blog. i’m new to the blogegine platform, so any suggestions on getting my blog looking nice would be appreciated.

Actually like your websites particulars! Undoubtedly a beautiful offer of data that is extremely helpful. Keep it up to carry publishing and that i’m gonna proceed studying by means of! Cheers.

I’ve not too long ago started a weblog, the data you provide on this web site has helped me tremendously. Thank you for all of your time & work.

I’m still learning from you, but I’m improving myself. I certainly love reading all the pieces that is written on your blog.Maintain the tales coming. I loved it!

hey all, I was just checkin’ out this weblog and I actually admire the basis of the article, and don't have anything to do, so if anybody would like to to have an engrossing convo about it, please contact me on AIM, my identify is heather smith

I’ll be back as soon as once again inside the possibility to examine out your blogposts down the road.

Congratulations on possessing actually certainly one of some of the sophisticated blogs Ive arrive throughout in a while! Its simply amazing how a lot you’ll have the ability to think about away from a factor principally simply because of how visually gorgeous it is. Youve place collectively a fantastic weblog site space –nice graphics, motion pictures, layout. That is certainly a should-see website!

I do know this isn’t precisely on subject, but i've a web page using the same program as effectively and i am getting troubles with my comments displaying. is there a setting i am missing? it’s doable chances are you'll assist me out? thanx.

I know this isn’t exactly on subject, but i've a website using the identical program as nicely and i am getting troubles with my feedback displaying. is there a setting i'm missing? it’s doable you might help me out? thanx.

I¡¯m delighted that I've observed this weblog. Lastly anything not a junk, which we undergo incredibly frequently. The web site is lovingly serviced and stored up to date. So it must be, thank you for sharing this with us.

You ought to essentially take into consideration engaged on growing this blog into a major authority on this market. You evidently have a grasp handle of the subjects everyone seems to be searching for on this website in any case and you possibly can certainly even earn a buck or two off of some advertisements. I would explore following latest matters and elevating the amount of write ups you put up and I guarantee you’d begin seeing some wonderful targeted site visitors in the close to future. Only a thought, good luck in no matter you do!

It is unrealistic for this to expect a psychic to always have the correct answers. However, in fairness if they’re not able to discover what lies ahead for you, they should be honest and explain they can’t see anything.

With the news of the current stressexamination on Healthcare Organisations in Europe due out soon it has to be a worrying time for the markets. Let’s hope we’re not headed for another collapse again.

Highly rated post. I study one thing completely new on completely different blogs everyday. Deciding on one . stimulating to read the paper content from other writers and study a bit of something from their website. I’d like to apply sure of this content material on my weblog you’re mind. Natually I’ll give a hyperlink here we're at your web-site. Respect your sharing.

This wireless gadget is usually utilized with Wi-Fi, as nicely a