(toppers-users 3756) Re: SSPの制約タスクの待ちについて

[Miyagawa]

高田先生

　　バグってましたね。恥ずかしい。
　　ちゃんとテストしないで書くと駄目ですね。

　　ASPは2回の 0チェック(バイナリサーチ)とテーブル参照ですね。
　　理解しやすくて速いコードなので断然こちらが良いですね。

　　ご指摘のように実行速度はプロセッサの種類とオプティマイズの状況で
　　変わるかも知れませんがC言語なら現状のASPコードが良いと思います。
　　アセンブラでカリカリに書くなら最適化は色々と有りそうですが難読な
　　芸術の世界に成りますね。

---話はちょっと変わりますが---

　　既にkoizumiさんが指摘しているようにbitmap_search_tableは
　　先頭にダミーを入れて -1 しないで参照するのが良いと思います。

　　元々bitmapはゼロでない事を期待したコードですから、
　　テーブル参照時に-1するのはOKなのでしょうが、
　　異常な状態だとしても0で来た時にテーブルの前を参照するコードは
　　好ましくないと感じます。


(2012/01/18 1:30), Hiroaki TAKADA wrote:
> 宮川様
> 
> ご教示ありがとうございます。このアルゴリズムは知りませんでした。
> 
>>    x = (x&  0xffff) + ( (x>>  4)&  0xffff)
> 
> ここは、0xffff → 0x0f0f ですね？（動作させて確かめました）
> 
> そこで、ASPカーネルのアルゴリズムと、どちらが速いか比較してみま
> した。その結果、0x0001〜0xffffまでを1000回ループさせて、私のマ
> シン（プロセッサは 1.8GHz Intel Core i7）で時間を計測したところ、
> 
> ASPカーネルのアルゴリズム
>  0.550u 0.000s 0:00.55 100.0%
> 
> 宮川さんが書かれているアルゴリズム
>  0.751u 0.000s 0:00.75 100.0%
> 
> ということで、この評価では、ASPカーネルのアルゴリズムに軍配が上
> がりました。とは言え、固定時間なのは魅力的ですね。あと、プロセッ
> サによっても違う結果になるとは思います。
> 
> 高田広章
> 名古屋大学
> 
> (12/01/17 11:10), Miyagawa wrote:
>> 宮川です。
>>
>> 余計な突っ込みかも知れませんが、、、
>>
>>> Inline uint_t
>>> bitmap_search(uint_t bitmap)
>>> {
>>>   uint_t n;
>>>   for(n = 0U; n<  3; n++){
>>>    if ((bitmap&  0x0fU) == 0U) {
>>>     bitmap>>= 4U;
>>>    }else{
>>>     break;
>>>    }
>>>   }
>>>   return (n*4U + bitmap_search_table[(bitmap&  0x0fU) - 1U]);
>>> }
>>
>> n<= 3 ? は置いといて、
>>
>> 良く知られた方法としては、こんな手もあります。(16bit)
>>
>>    x = (x&  (-x)) - 1
>>    x = (x&  0x5555) + ( (x>>  1)&  0x5555)
>>    x = (x&  0x3333) + ( (x>>  2)&  0x3333)
>>    x = (x&  0xffff) + ( (x>>  4)&  0xffff)
>>    x = (x&  0x00ff) + ( (x>>  8)&  0x00ff)
>>
>> 固定時間だし、シフトと足し算だけなのでそれなりに速いと思います。
>>
>> --------------
>>
> 
>