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

[Hiroaki TAKADA]

宮川様

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

趣味の領域かもしれませんが、「assert(bitmap != 0U)」が入っているので
問題ないと考えています。

ダミー領域を入れる手もありますが、ダミーデータが返された場合に、この
関数を呼んだ側で動作保証できないので。

高田広章
名古屋大学

(12/01/18 7:52), Miyagawa wrote:
> 高田先生
> 
> 　　バグってましたね。恥ずかしい。
> 　　ちゃんとテストしないで書くと駄目ですね。
> 
> 　　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)
>>>
>>> 固定時間だし、シフトと足し算だけなのでそれなりに速いと思います。
>>>
>>> --------------
>>>
>>
>>
>