(toppers-users 3755) Re: SSPの制約タスクの待ちについて
Hiroaki TAKADA
hiro @ ertl.jp
2012年 1月 18日 (水) 01:30:45 JST
宮川様
ご教示ありがとうございます。このアルゴリズムは知りませんでした。
> 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)
>
> 固定時間だし、シフトと足し算だけなのでそれなりに速いと思います。
>
> --------------
>