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

[Hiroaki TAKADA]

宮川様

ご教示ありがとうございます。このアルゴリズムは知りませんでした。

>    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)
> 
> 固定時間だし、シフトと足し算だけなのでそれなりに速いと思います。
> 
> --------------
>