Hatena::ブログ(Diary)

当面C#と.NETな記録 このページをアンテナに追加 RSSフィード

2009/7/28 (火)

[] VisualStudio2010は2010年春?  VisualStudio2010は2010年春?を含むブックマーク  VisualStudio2010は2010年春?のブックマークコメント

http://japan.cnet.com/news/biz/story/0,2000056020,20397152,00.htm

来年春登場だそうな。今年の11月ごろかなと期待してたのに。

ネタ元は Mary Jo Foley おばさんらしい。

トラックバック - http://d.hatena.ne.jp/siokoshou/20090728

2009/7/22 (水)

[] .NET4.0 の並列処理を試してみた その2 : 再帰と並行性  .NET4.0 の並列処理を試してみた その2 : 再帰と並行性を含むブックマーク  .NET4.0 の並列処理を試してみた その2 : 再帰と並行性のブックマークコメント

id:siokoshou:20090721 のつづき。前回は並列化したのに微妙に速くなっただけで、Parallel.For 使えばそれでおしまい。じゃないことがわかったところまで。今回はもっと速くします。

ここでちょっとおわびです。前回は気づいてなかったんだけど、ベータのベンチマーク結果を公表するなとEulaに書いてあったので、これからは相対的な割合だけ書きます。並列化に関してはそこが知りたいところだろうけど、しょうがないです。

本題。小さい処理のタスクを大きくまとめたら速くなったので、この路線をもっと進めてみます。このことは既に MSDN ライブラリの How to にありました。How to: Speed Up Small Loop Bodies。でも今回は再帰で繰り返す回数が実行してみないとわかんないので(こういうときに再帰はきれいに書ける)、この記事のようにはできません。

困ったのでパラレルチームの blog をぐぐってみるとありました。Recursion and Concurrency。長いのでちょっとしか読んでません。前の How to も元はパラレルチームの blog 記事みたい。

最後に載ってるコードで、木を降りていくときにある程度の深さまでは並列、その先は逐次と処理を切り替えています。これ、ハードコーディングしなくてもやってくれればいいのに!たまってるタスクの数かスレッドの状況か何かよくわからないけど、現在の状況をみて逐次か並列か、というかタスクを作るか作らないかかな?とにかく、よきにはからってほしい。

というわけでまねしてみました。B(4,2)では以下のように 3 または 4 のときが速いようです。B(3,3)のときは 5 にすると速いです。マジ自動化してほしい…。手動じゃ無理…。

ともかく、こうすると7/15の逐次コードより2倍ちょっと速くなりました!パチパチパチパチ。まー、2倍でももの足りないけど1.4倍よりはいいか。

private void SearchCore( int[] array )
{
    // 重複判定
    if ( !IsUnique( array ) ) return;

    // 完成判定
    if ( IsComplete( array ) )
    {
        Output( array );
        return;
    }

    // 次の反復へ
    if ( 3 < array.Length )
    {
        for ( int i = 0; i < this.k; i++ )
        {
            SearchCore( array.Concat( new int[] { i } ).ToArray() );
        }
    }
    else
    {
        Parallel.For( 0, this.k, i => SearchCore( array.Concat( new int[] { i } ).ToArray() ) );
    }
}

つづく

トラックバック - http://d.hatena.ne.jp/siokoshou/20090722

2009/7/21 (火)

[] .NET4.0 の並列処理を試してみた その1 : Parallel.For, ConcurrentQueue<T>  .NET4.0 の並列処理を試してみた その1 : Parallel.For, ConcurrentQueue<T>を含むブックマーク  .NET4.0 の並列処理を試してみた その1 : Parallel.For, ConcurrentQueue<T>のブックマークコメント

.NET4.0 から従来よりも抽象的で簡単に使える並列ライブラリがどさっと追加されます。おもしろそうなので VisualStudio2010 のベータ1で試してみました。

結論から書くと

  • Parallel.For すばらしい!
  • Concurrent なコレクションはロックなしで複数タスクからデータの追加ができた
  • 今回は約1.4倍しか速くならなかった。不本意。きっと次回に続く


並列?並行? Parallel? Concurrent?

ちょっと名前に混乱があるのでまずはここから。

Parallel は並列、Concurrent は並行。

結城さんのすばらしいマルチスレッドの本によると、

  • 逐次(sequential)は複数の仕事を順番に処理
  • 並列は複数の仕事を同時に処理
  • 並行は逐次・並列に対して抽象度の高い表現で、1つの仕事を「どんな順序で処理してもよい複数の作業」に分割する様子を表現した言葉
    • 作業者が一人なら並行処理できるように作業を分割しても逐次的に実行されるし、二人いれば並列に実行される

だそうです。ガッテン、ガッテン。

Java の本だけど、アトミックって何?みたいなことをきっちりわかりやすく書いてあるのでとてもオススメ。並列はしっかりした理解なしだと怖いから、もう一度ちゃんと勉強しなおしたいな。



参考資料

このあたりはまだろくにドキュメントがないし、今後も変更がありそうですが、とりあえず。

参考資料は前回のメモに書いたけど特にオススメなのが MSDN magazine OCTOBER 2008 。日本語だし、blog より詳しくまとまってます。はじめに英語 blog 読んだ自分は涙目…

最初の記事は難しすぎるのでさらっと流し読み推奨。でも書いてる人がクレイからMSに移ってきて並列処理に取り組んでるってのが、そういう時代なんだなーって感慨深い。

特に 次期バージョンの Visual Studio で強化される並列処理のサポート って記事は .NET の並列に興味がある人は必読!TPL (Task Parallel Library), PLINQ (Parallel LINQ), LazyInit<T>, ThreadStaticAttribute の問題、スレッドセーフ コレクション、C++ の PPL (Parallel Pattern Library) (TPL そっくり)、VisualStudio2010 の MultiStack ビューとタスク一覧ビュー(ベータ1では Parallel Stacks/Parallel Tasks になってる)、同時実行分析のサポートなど日本語で説明があります。英語の blog 読むよりこっちを先に読むべきでした。

もうひとつ、Windows と C++ にある、「アルゴリズムの効率は、皆さんが考えるほど簡単ではありません。シングルプロセッサ上の適切にデザインされたアルゴリズムは、複数プロセッサ上の不十分な実装よりもパフォーマンスが高い場合がよくあります。」「問題をさらに複雑にするのは、シングルプロセッサ用に最適化されたアルゴリズムは並列化が難しいことが多く、若干効率の劣るアルゴリズムの方が複数プロセッサ上で高いパフォーマンスを示す可能性があることです。」ってところはへぇへぇへぇ。

並列化すれば速くなるってわけじゃないんですね…。

また、データ競合、デッドロックなどの問題は TPL を使ってもあいかわらず「ある」そうです。まあそうだよね。

MSDN



Parallel.For と ConcurrentQueue<T> で挑戦

id:siokoshou:20090715 の De Bruijn Sequence を求めるプログラムを並列化してみました(De Bruijn Sequence がわからなくても OK)。De Bruijn Sequence B(4,2) のとき、解が20736個あります。このとき、7/15の逐次的なコードの実行時間はx86版でピー秒程度でした(自主規制w)。Output() でコンソールに出力しているところはコメントアウトして、リリース版をVisualStudioなしでエクスプローラーからダブルクリックで起動したときの時間です。

深さ優先探索で木をたどって行くバックトラックによる探索プログラムです。

逐次→並列で変えたところ

  • 並列化のため、一つの配列をひっぱりまわすのをやめ、新しい配列を作って再帰先に渡すようにした
    • プログラムは単純になったが遅くなった
    • 「シングルプロセッサ用に最適化されたアルゴリズムは並列化が難しいことが多く、若干効率の劣るアルゴリズムの方が複数プロセッサ上で高いパフォーマンスを示す可能性があることです。」これにピタリと当てはまる
  • for 文は Parallel クラスの Parallel.For() を使って並列化した
    • Parallel.For( 0, this.k, i => SearchCore( ... ) )
    • とても簡単に並列化できる。スレッドを扱うごちゃごちゃした部分がライブラリの奥にいったので、従来の(抽象度が低かった)スレッドを扱ったコードより見通しがよいコードになる
    • しかもよいハードに変えればコードはそのままでさらに並列化される。次のフリーランチはこちら。
  • ConcurrentQueue<T> を使ってロックなしでデータを追加するようにした
    • 本当にロックなしで正しく動いた。なにこれスゴイ
    • ほかの Concurrent なコレクションもロックいらずで使えた
    • このコードではデータを追加するだけで、生産者/消費者型の使い方をしてないので、どの Concurrent なコレクションでも動く
    • Concurrent なコレクションはどれを使ってもこの使い方では実行時間はほぼ同じ
    • ConcurrentLinkedList は削除予定らしい
  • タスク(分割した仕事を今後タスクと呼ぶっぽい。TPL の T)の粒度が小さすぎ(処理が少ない)、かつ、タスクを作りすぎるので、逐次的な SearchCoreSequential と SearchCore を交互に呼ぶようにしてやっと逐次版より速くなった
    • SearchCore だけを呼び続けた場合の実行時間は逐次版と同じくらい。配列のコピーで遅くなった分を取り返した程度。意味ない…
    • ぼこぼことタスクを増やすのはやはりよくないっぽい。for を Parallel.For に変えただけで速くなるってほど甘くないみたい

実行時間はx86版で約 1.4 速くなりました。実行環境は Core i7 920 実4コア 仮想8コア、メモリ6G、Windows7RC x64。ちなみにx64版はx86よりちょっと遅い…。

今回は約1.4倍速くなっただけ。これじゃあまだまだ全然なので、もっと速くできないかいろいろ試してみます。

並列化したコード。

using System;
using System.Collections.Concurrent;
using System.Diagnostics;
using System.Linq;
using System.Threading;

namespace DeBruijnSequence
{
  public class SearchDeBruijnSequenceConcurrentCollection
  {
    private readonly int k, n, max;
    //private ConcurrentBag<string> results = new ConcurrentBag<string>();
    //private ConcurrentStack<string> results = new ConcurrentStack<string>();
    //private ConcurrentDictionary<string, string> results = new ConcurrentDictionary<string, string>();
    private ConcurrentQueue<string> results = new ConcurrentQueue<string>();

    public SearchDeBruijnSequenceConcurrentCollection( int k, int n )
    {
      if ( k < 2 || 10 < k )
        throw new ArgumentOutOfRangeException( "k" );
      if ( n < 1 )
        throw new ArgumentOutOfRangeException( "n" );

      this.k = k;
      this.n = n;
      double pow = Math.Pow( k, n );
      if ( ( double ) int.MaxValue < pow )
        throw new ArgumentOutOfRangeException( "k, n" );

      this.max = ( int ) pow;
    }

    public ConcurrentQueue<string> Search()
    {
      int[] array = new int[ this.n ];
      SearchCore( array );
      return this.results;
    }

    private void SearchCore( int[] array )
    {
      // 重複判定
      if ( !IsUnique( array ) ) return;

      // 完成判定
      if ( IsComplete( array ) )
      {
        Output( array );
        return;
      }

      // 次の反復へ
      //Parallel.For( 0, this.k, i => SearchCore( array.Concat( new int[] { i } ).ToArray() ) );
      Parallel.For( 0, this.k, i => SearchCoreSequential( array.Concat( new int[] { i } ).ToArray() ) );
    }

    private void SearchCoreSequential( int[] array )
    {
      // 重複判定
      if ( !IsUnique( array ) ) return;

      // 完成判定
      if ( IsComplete( array ) )
      {
        Output( array );
        return;
      }

      // 次の反復へ
      for ( int i = 0; i < this.k; i++ )
      {
        SearchCore( array.Concat( new int[] { i } ).ToArray() );
      }
    }

    private bool IsUnique( int[] array )
    {
      if ( array.Length <= this.n ) return true;

      int pos = array.Length - this.n;
      int[] last = array.Skip( pos ).Take( this.n ).ToArray();

      for ( int i = 0; i < pos; i++ )
      {
        if ( array.Skip( i ).Take( this.n ).SequenceEqual( last ) )
          return false;
      }
      return true;
    }

    private bool IsComplete( int[] array )
    {
      if ( array.Length != this.max ) return false;

      for ( int i = 0; i < this.n - 1; i++ )
      {
        array = array.Concat( new int[] { array[ i ] } ).ToArray();
        if ( !IsUnique( array ) )
          return false;
      }
      return true;
    }

    private string Output( int[] array )
    {
      string str = string.Join( "", array.Select( m => m.ToString() ).ToArray() );
      //this.results.Add( str );
      //this.results.Push( str );
      //this.results.TryAdd( str, str );
      this.results.Enqueue( str );
      return str;
    }

    static void Main()
    {
      var searcher = new SearchDeBruijnSequenceConcurrentCollection( 4, 2 );

      var sw = Stopwatch.StartNew();
      var result = searcher.Search();
      int count = result.Count;
      sw.Stop();

      Console.WriteLine();
      Console.WriteLine( count );
      Console.WriteLine( sw.Elapsed );

      Console.ReadKey();
    }
  }
}


VisualStudio2010 の新しいデバッグ機能

Parallel Stacks

f:id:siokoshou:20090721180550j:image

Parallel Tasks

f:id:siokoshou:20090721180549j:image

見方がよくわからないw

2009/7/17 (金)

[] .NET4.0 の Parallel メモ  .NET4.0 の Parallel メモを含むブックマーク  .NET4.0 の Parallel メモのブックマークコメント

ずいぶんと気合入れて追加してきてるみたい。気になるものをメモ。あとでしっかり読……みたい。

追記:

トラックバック - http://d.hatena.ne.jp/siokoshou/20090717

2009/7/15 (水)

[] De Bruijn sequence を列挙するコード  De Bruijn sequence を列挙するコードを含むブックマーク  De Bruijn sequence を列挙するコードのブックマークコメント

いろいろとコメントをいただいているうちに De Bruijn sequence がわかってきました。初めは数学的な背景には興味がなかったんだけど、De Bruijn sequence をすべて列挙する問題が最近遊んでいるデータマイニングの頻出集合を求める問題とそっくりなことに気づいて、ちょっと練習がてらコードを書いてみました。かのダイクストラもコード書いて遊んでみたんなら自分もちょっと遊んでみようかなと。求めてどうするかは知りませんw

De Bruijn sequence の詳しい説明はこちら

http://chessprogramming.wikispaces.com/De+Bruijn+sequence

深さ優先探索をする再帰によるバックトラックの簡単なコードです。De Bruijn sequence は爆発的な勢いで解の数が増えていくので小さい数字で動かしてみてください。解の数は |B(2,5)|=2048、|B(2,6)|=67,108,864、|B(2,7)|=144,115,188,075,855,872 といった具合に増えていきます。大きい数字だとメモリが尽きるかも。B(9,1) だと |B(9,1)|=40320 だけど、B(9,2) になると |B(9,2)|=1.347e+48 にもなります…。

De Bruijn sequence B(k,n) の先頭が n 個の 0 ではじまるのは、周期的な数列なのでずらしてできる値を同じものとみなしているようです。たとえば、B(2,2) は 0011 をずらせば 0110, 1100, 1001 が見つかります。B(k,1) は単なる順列です。

using System;
using System.Collections.Generic;
using System.Linq;

namespace SearchDeBruijnSequence
{
    public class SearchDeBruijnSequence
    {
        private readonly int k, n, max;
        private List<string> results = new List<string>();

        public SearchDeBruijnSequence( int k, int n )
        {
            if ( k < 2 || 10 < k )
                throw new ArgumentOutOfRangeException( "k" );
            if ( n < 1 )
                throw new ArgumentOutOfRangeException( "n" );

            this.k = k;
            this.n = n;
            double pow = Math.Pow( k, n );
            if ( ( double ) int.MaxValue < pow )
                throw new ArgumentOutOfRangeException( "k, n" );

            this.max = ( int ) pow;
        }

        public List<string> Search()
        {
            int[] array = new int[ this.max + this.n - 1 ];
            //SearchCore( array, -1 ); // 0 始まり以外の変形も列挙したければこちら
            SearchCore( array, this.n - 1 );
            return this.results;
        }

        private void SearchCore( int[] array, int tail )
        {
            // 重複?
            if ( !IsUnique( array, tail ) )
                return;

            // 完成?
            if ( IsComplete( array, tail ) )
            {
                Output( array );
                return;
            }

            // 次の反復へ
            for ( int i = 0; i < this.k; i++ )
            {
                array[ tail + 1 ] = i;
                SearchCore( array, tail + 1 );
            }
        }

        private bool IsUnique( int[] array, int tail )
        {
            if ( tail < this.n ) return true;

            int pos = tail - this.n + 1;
            int[] last = array.Skip( pos ).Take( this.n ).ToArray();

            for ( int i = 0; i < pos; i++ )
            {
                if ( array.Skip( i ).Take( this.n ).SequenceEqual( last ) )
                    return false;
            }
            return true;
        }

        private bool IsComplete( int[] array, int tail )
        {
            if ( tail != this.max - 1 ) return false;

            for ( int i = 0; i < this.n - 1; i++ )
            {
                array[ tail + 1 + i ] = array[ i ];
                if ( !IsUnique( array, tail + 1 + i ) )
                    return false;
            }
            return true;
        }

        private void Output( int[] array )
        {
            string str = string.Join( "",
                array.Take( this.max ).Select( m => m.ToString() ).ToArray() );
            this.results.Add( str );

            if ( ( this.max <= 64 && this.k == 2 )
                || ( this.n == 1 && this.k == 8 ) )
            {
                ulong x = Convert.ToUInt64( str, this.k );
                Console.WriteLine( "{0} : {1}", str, x );
            }
            else
            {
                Console.WriteLine( str );
            }
        }


        static void Main()
        {
            var searcher = new SearchDeBruijnSequence( 2, 4 );
            var result = searcher.Search();

            Console.WriteLine();
            Console.WriteLine( result.Count );

            Console.ReadKey();
        }
    }
}

ダイクストラのコードよりわかりやすい?

解の例。

B(2,1)
01 : 1

B(2,2)
0011 : 3

B(2,3)
00010111 : 23
00011101 : 29

B(2,4)
0000100110101111 : 2479
0000100111101011 : 2539
0000101001101111 : 2671
0000101001111011 : 2683
0000101100111101 : 2877
0000101101001111 : 2895
0000101111001101 : 3021
0000101111010011 : 3027
0000110010111101 : 3261
0000110100101111 : 3375
0000110101111001 : 3449
0000110111100101 : 3557
0000111100101101 : 3885
0000111101001011 : 3915
0000111101011001 : 3929
0000111101100101 : 3941

B(3,1)
012
021

B(3,2)
001021122
001022112
001102122
001102212
001120221
001121022
001122021
001122102
001202211
001211022
001220211
001221102
002011221
002012211
002101122
002110122
002112201
002122011
002201121
002201211
002210112
002211012
002211201
002212011
トラックバック - http://d.hatena.ne.jp/siokoshou/20090715

2009/7/6 (月)

[] 一番右端の立っているビット位置を求める「ものすごい」コードのていねいな説明  一番右端の立っているビット位置を求める「ものすごい」コードのていねいな説明を含むブックマーク  一番右端の立っているビット位置を求める「ものすごい」コードのていねいな説明のブックマークコメント

id:siokoshou:20090704 のはてブのコメント見てるとわからないってコメントが結構あるので、もう一度がんばって説明してみます。まあわかったところで得はないかもしれませんw

public static int GetNumberOfTrailingZeros( long x )
{
    if ( x == 0 ) return 64;

    ulong y = ( ulong ) ( x & -x );
    int i = ( int ) ( ( y * 0x03F566ED27179461UL ) >> 58 );
    return table[ i ];
}

static int[] table;

table = new int[ 64 ];
ulong hash = 0x03F566ED27179461UL;
for ( int i = 0; i < 64; i++ )
{
    table[ hash >> 58 ] = i;
    hash <<= 1;
}

まずはTarZさんが見つけた謎の数 0x03F566ED27179461 の説明から。これを2進表現すると

0000 0011 1111 0101 0110 0110 1110 1101 0010 0111 0001 0111 1001 0100 0110 0001

です。この数は 6bit の 000000 から 111111 まですべてのビットパターンが現れる不思議な数。このような数(01の数列)を De Bruijn sequence と呼ぶそうです。はてブコメントや参照であげたリンク先ではM系列とも呼ばれているようです。M系列が何かわかりませんがw

左から 6bit を切り出してみると 000000。次に先頭 1bit を飛ばして次の 6bit を見ると 000001。今度は 2bit ずらして 6bit を見ると 000011。

図にします。長いので一部省略。すべてのパターンは TarZさんのところ参照

[0] 0000001111110......010001100001

[1] 0000001111110......010001100001

[2] 0000001111110......010001100001

[3] 0000001111110......010001100001

[4] 0000001111110......010001100001

[5] 0000001111110......010001100001

:

[60] 0000001111110......010001100001(00000)

[61] 0000001111110......010001100001(00000)

[62] 0000001111110......010001100001(00000)

[63] 0000001111110......010001100001(00000)

左の[]内の数はずらしたビット数です。

最後のほうは 6bit ないので後ろに0を補ってあげて 6bit にします。このように 1bit ずつずらしながら切り出したときに 000000 から 111111 まで、すべてのパターンが出現しています。重複もありません。この長ーいビットのどこかでスパッと切って、そこから 6bit 見ると、切る場所が違えば必ず異なるビットパターンが出てきます。逆に 6bit のビットパターンがあれば、どこから切り出した値か一意に決まります。すごい!

6bit で表現できる数の範囲は 2の6乗 = 64 なので 0〜63 です。切り出したビットパターンを10進表現にしてみると

[0] 000000 = 0
[1] 000001 = 1
[2] 000011 = 3
[3] 000111 = 7
:
[61] 001000 = 8
[62] 010000 = 16
[63] 100000 = 32

000000 から 111111 の全パターンが出現しているということは、0〜63 の 6bit で表現できるすべての数があらわれているってことです。これは「[]内の数(ずらしたビット数) 0〜63」と「ビットパターンの 0〜63」が一対一に対応する表と考えることができます。

0 … 0
1 … 1
2 … 3
3 … 7
:
61 … 8
62 … 16
63 … 32

これをテーブルに入れておきます。「table[ビットパターン]=ずらした数」として作ります。

table[0]=0, table[1]=1, table[3]=2, table[7]=3,... table[8]=61, table[16]=62, table[32]=63

こうしておくと、int n = table[ 6bit のビットパターン] として、どこから切り出したのか求めることができます。


テーブルの正体がわかったので計算のほうを見ていきます。

x & -x。これを計算すると立っている一番右端のビットだけ残して0になります。-x のように符号を反転するには「ビットを反転して+1」という操作が行われます。2の補数表現ってやつです。4bit 幅で例をあげると 1 は 0001、-1 は 1111 です。1 の符号を反転してみると 0001 のビットを反転して 1110、+1 すると 1111 で -1 になりました。逆もやってみると -1 は 1111。1111 のビットを反転すると 0000、+1 して 0001。1 になりました。

では、x & -x を 00100100 を例にやってみます。

00100100 反転すると
11011011 +1すると
11011100 最初の 00100100 と AND を取ると
00000100

反転して+1した値と元の値を比べると、立っている右端のビットだけが共通して立っているのがわかります。賢い!

これで y = x & -x は立っている右端の 1bit だけ 1 で残りのビットは 0 になりました。1bit だけ立っている数、つまり 1,2,4,8,16... 2 の n 乗の値となりました。

C# を知らない人向けに補足しておくと long は符号付き 64bit 整数、ulong は符号なし 64bit 整数、int は符号付き 32bit 整数です。

最後。( y * 0x03F566ED27179461UL ) >> 58。ここで唐突に話はかわって、2倍するって bit で考えるとどんな操作でしょう?

1 * 2 = 2 → 0001 * 2 = 0010
2 * 2 = 4 → 0010 * 2 = 0100
3 * 2 = 6 → 0011 * 2 = 0110

2 倍することは bit でみると左に 1bit シフトすることです。左シフトすると右から 0 が詰め込まれていきます。あふれたビットは捨てられます。4倍だとどうでしょう?

1 * 4 = 4 → 0001 * 4 = 0100
2 * 4 = 8 → 0010 * 4 = 1000

2bit 左シフトです。8倍は?1*8=8なので 3bit 左シフトです。

このように 2 の n 乗倍は n ビット左シフトすることに相当します。Windows の電卓ででも試してみてください。

話を戻すと、3F566ED27179461 に 2 の n 乗である y をかけるのは、左に n ビットシフトしているわけです。これにより、y の立っているビット位置によって上位 6bit に出てくるビットパターンがそれぞれ違うものになります。だんだん話が見えてきました。n ビット左にシフトしたときの結果の上位 6bit を見てみます。[]内はシフトした数 n です。

[0] 00000011... 0bit シフト

[1] 00000111... 1bit シフト

[2] 00001111... 2bit シフト

[3] 00011111... 3bit シフト

:

[61] 00100000... 61bit シフト

[62] 01000000... 62bit シフト

[63] 10000000... 63bit シフト

さっきのビットパターンが上位 6bit に出てきました。この 6bit があればテーブルから n が求められます。ついでと言ってはなんだけど、左シフトしたことで目的の 6bit より左のビットが消えました。

この 6bit より右のビットも邪魔です。なので、64bit から 6bit だけが残るように、64 - 6 = 58bit 右にシフトします。符号なし整数を使っているので、右シフトでは 1001 >> 2 = 0010 のように上位には 0 が入ります。下位 58bit は消えてしまったので、これで目的の 6bit のビットパターンだけが 0〜63 の数として得られました。

まとめると ( y * 0x03F566ED27179461UL ) >> 58 は、2 の n 乗である y をかけることで左に n ビットシフトし、その結果の上位 6bit だけを残すために右に 58bit シフトします。

これでビットパターンが得られたので、この数でテーブルを引けば何ビット左にシフトしたか、つまり右から何番目のビットが立っていたかという答えが得られます。ビットパターン 000000 が出てきたら table[0]=0 で 0bit 目(最下位)が立っていた、000111 が出てきたら table[000111=7]=3 で (0はじまりで)3bit 目が立っていた、100000 が出てきたら table[100000=32]=63 つまり一番上のビットが立っていたというわけです。

これであなたも De Bruijn sequence 初級!


おまけ。テーブル使わずに全ビットパターンが順に出てくる数列はないのかと考えてみる。

[0] 000000 = 0
[1] _000001 = 1
[2] __000010 = 2
[3] ___000011 = 3

0,1,2まではいいけど、3で無理ですね。おしまい。

Ito hisashiIto hisashi 2009/07/11 22:32 面白いプログラムをご紹介ありがとうございます!

うちのブログでも取り上げさせていただきました。
(Bloggerからはトラバが送れないのでコメントで失礼します。)

table[0]=0 を前提にすれば、魔法の数字は、この世に6つだけしかなく、

0x0218A7A392DD9ABFUL
0x02FCA8CF75A6C487UL
0x03F566ED27179461UL
0x03C953422DFAE33BUL
0x03848D96BBCC54FDUL
0x03731D7ED10B2A4FUL

です。3番目がご紹介のやつですが、他のでも同じ用途に使えます。

siokoshousiokoshou 2009/07/12 01:10 興味深いコメントありがとうございます!
http://chessprogramming.wikispaces.com/De+Bruijn+sequence
を見ると 0x022fdd63cc95386d が載ってて、これも6bitで0~63の一意の値が畳み込まれているんですが……
もしかしてこのあたりがM系列と De Bruijn sequence の違いなんでしょうか?私には難しくてよくわかりません……
この6つの値はM系列なんですか?

2009/7/4 (土)

[] 一番右端の立っているビット位置を求める「ものすごい」コード  一番右端の立っているビット位置を求める「ものすごい」コードを含むブックマーク  一番右端の立っているビット位置を求める「ものすごい」コードのブックマークコメント

一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。

この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの?ってことになるので、問題を正確にするために ntz として 64 を返すことにしたんだと思います。すぐに思いつくのがループで 1bit ずつ見ていく方法ですよね。高速化する方法はおもいつきますか?Hacker's delight ではバイナリーサーチを使ってて、見たときはスゲーと思ったんだけど、このコードの前では色あせて見えます(^^;

ちなみに環境依存してよいなら x86/x64 に bsf (VC++ なら http://msdn.microsoft.com/en-us/library/wfd9z0bb.aspx) ってのがあります。bsf では 0 のときの戻り値は未定義です。

問題の説明はここまでにして、コードの紹介です。Hacker's delight のコードより4〜5倍速く(5-13より4〜5倍、5-15より1.2〜1.3倍)、そして、イミフ加減が半端じゃない!これ一つで 64bit 値以下のすべての値に対応できます。

public static int GetNumberOfTrailingZeros( long x )
{
    if ( x == 0 ) return 64;

    ulong y = ( ulong ) ( x & -x );
    int i = ( int ) ( ( y * 0x03F566ED27179461UL ) >> 58 );
    return table[ i ];
}

table は以下のようにして求めます。

static int[] table;

table = new int[ 64 ];
ulong hash = 0x03F566ED27179461UL;
for ( int i = 0; i < 64; i++ )
{
    table[ hash >> 58 ] = i;
    hash <<= 1;
}

意味わかりますか?w

x & -x は Hacker's delight にある、立っている一番右端のビットだけ残して0にしてしまう黒魔術。使える場面が多いので覚えておくと便利です。いろんな値を入れてためしてみてください。

その後、完全ハッシュを使って数(2^n)を数(0〜63)に変換してるわけです。0のときの if 文が目障りですが、0のとき呼ばないなど don't care であれば省いてもOKです。省くと 0 のときに 0 が返ってきます。bit1 最下位ビットが立っているときも 0 なので区別できません。64bit 値の右端のビット位置をあらわすには、0の場合も含めると65通りの答えが必要で、もし65をあまり越えないコンパクトなハッシュ値を作れると if が不要になります。あってもこっちのほうが速い可能性はありますが。

このコードは 2ch のビット演算スレ0x03 の 71 と 80 で知りました。

http://pc12.2ch.net/test/read.cgi/tech/1226143920/

80 から解説の引用の引用。

周期2^p-1ビットの列があって、そこからpビットを切り出すと、オール0以外のすべてのパターンが現れる

p=3の場合のM系列は例えばこう。
0011101
↓ (周期2^3-1=7で同じパターンの繰り返し)
001110100111010011101...
上の桁から3ビットを切り出すと、
001 (1)
_011 (3)
__111 (7)
___110 (6)
____101 (5)
_____010 (2)
______100 (4)

1〜7まで全部出るだろ。これに000だけ追加すればおk。
これだけだと順番がバラバラなので、テーブルと組み合わせる。
(中略)
ビット溢れによるマスクなども組み合わせているが。

そして、TarZさんの見つけた値 0x03F566ED27179461 を使ったのが上のコードです。

http://slashdot.jp/~TarZ/journal/448559

0x03F566ED27179461 =

0000 0011 1111 0101 0110 0110 1110 1101 0010 0111 0001 0111 1001 0100 0110 0001。

以下引用。

このビット列について、6文字を切りだす作業を1文字目から順に行っていくと、以下の通りになる。
2つ目のパターンでsortしてみると、000001から111111まで、すべてのパターンが出現していることが確認できる。
さらにこれに000000を加えればすべて揃うことになる。なんと素晴らしい!

    1    000001
    2    000011
    3    000111
以下略

すごい!すごすぎる!この値はどうやって求めたんだろう?

( y * 0x03F566ED27179461UL ) >> 58 の部分についてもうちょっと書いておくと、y は 2 の n 乗の値、つまり 1, 2, 4, 8,... で掛け算することによって 0x03F566ED27179461 を左シフトすることになります。y が 1 ならシフトなし、2 なら 1bit シフト、4 なら 2bit シフトといったぐあい。これによって桁あふれを起こし、上位の桁を消します(追記。このとき y の値によって何ビット左シフトするか変わるので、y の値によって上位 6bit のビットパターンが変わります)。最後に 58bit (58=64-6) 右シフトして上位 6bit のビットパターンを下位に移動し(下位 bit をマスク)、テーブルを引きます。このとき符号付き整数を使うと符号拡張されてしまい、さらに下位 6bit の AND を取る必要がありますが ulong を使うことでこの手間を回避しています。

参考リンク

英語での解説もみつけました。

おまけ。この問題を解く IEEE754 の float を使ったハックがありますが、それの 64bit版 C# コードも書いてみました。上のコードの10倍ほど遅くなってしまいました><

禁断の unsafe 使えば速いかも?

public static int FloatHack2( long v )
{
    if ( v == 0 ) return 64;

    v = v & -v;

    if ( v == -9223372036854775808 ) return 63;

    float f = ( float ) v;
    var bits = BitConverter.GetBytes( f );
    uint n = BitConverter.ToUInt32( bits, 0 );
    int r = ( int ) ( ( n >> 23 ) - 0x7f );
    return r;
}


(7/6追記) たくさんのアクセスありがとうございます。こんなマニアックな話題なのにまさかのホットエントリー入りに驚いてますw

本当に速いの?ってはてブのコメントに答えると、環境依存してよければ x86 には bsf という機械語があって一命令でカウントできます。x64 の 64bit であれば bsfq。環境依存なしならこのコードは私の知る限り最速です。K8 では bsf よりこっちを使ったほうがよいそうです。詳しくはコメント参照。64回ループするのに比べると手元の環境では10倍程度速いです。速さにこだわっているわけは一つ前の日記あたり。もっと速いのあれば教えてください。上には上がいる!かも?

ちなみに Hacker's delight は機械語にすると何命令実行することになるとか論じてる本ですw 分岐や割り算をできるだけ避けるような、そういう世界。

はてブのわからないってコメントに答えて丁寧に説明してみました。でもわからなくてもいいと思うw

  • 編集履歴
    • 2009/7/6 ( y * 0x03F566ED27179461UL ) >> 58 の説明をちょっと直してみた。リンク1件追加。追記追加。
    • 2009/7/7 「Hacker's delight のコードより4〜5倍速く」だった部分を修正。

山田 剛@CSA山田 剛@CSA 2009/07/05 00:31 コンピュータチェスの実装用に、ビット操作を最大限に使う 'bitboard' というテクニックが広く使われていますが、ここでも、長いビット列を乗算によってハッシュアドレッシング可能な短いビット列に変換するテクニックが知られています。

http://chessprogramming.wikispaces.com/Magic+Bitboards

タテやナナメのビット列を無理やりヨコに倒しています。

この方面の黒さ加減も相当なものですが、コンピュータチェスやコンピュータ将棋くらいでしか使えないのが残念。何かのアルゴリズムに応用できないですかね…。

siokoshousiokoshou 2009/07/05 10:42 おー、bitboardってそういうものなんですね。ビット演算スレやwikipediaからリンクがあるのは気づいてたけど見てなかったです。
そして、↑のコードってそこが出所っぽいですw
http://chessprogramming.wikispaces.com/BitScan#DeBruijnMultiplation
ここに数が違うけど同じアルゴリズムのコードがありました。

このマジックナンバーのことを、オランダの数学者 Nicolaas de Bruijn にちなんで De Bruijn sequence と呼ぶそうです。
http://chessprogramming.wikispaces.com/De+Bruijn+sequence
下のほうにあるグラフを拡張していく方式でこの数列を見つけることができるっぽいですね。

プライベートナンバーが欲しい人のためのジェネレーターもあるw ○○専用 De Bruijn sequence!
http://chessprogramming.wikispaces.com/De+Bruijn+Sequence+Generator

このwikiによると、P4 や K8 の bsf はだいぶ遅いようですね。特にK8だとほかのプロセッサのリソースもブロックしてしまうから、↑のコードのほうがいいみたい。

↑のコードの32bitフレンドリーバージョンものってた。
http://chessprogramming.wikispaces.com/BitScan#MattTaylorsFoldingtrick
これもわけわかw

TarZTarZ 2009/07/07 00:50  /.Jの古い日記エントリに、はてブがいくつかついたのでびっくりしました。(んー、その2chコメントも見覚えが…確かビット演算スレ0x02のときに…)

 6ビット版のあのビット列は、試行錯誤で出したものではなくて、M系列の生成式で出したものです。

 「なぜM系列になるか?」といった数学的な裏づけになると少々こみいった話になりますが、とりあえず生成式が判れば、それをちょろっとコードを書けばビット列を得ることはできます。
 残念ながらWeb上では、生成式について詳細に解説された日本語コンテンツは少なそうです。すでにリンクを挙げられている英語コンテンツか、興味がおありでしたら信号処理などの教科書に載っていると思います。

 ゴロム定規とかM系列などは、その性質が興味深いだけでなく、思わぬところで応用できたりするのでなかなか面白いものです。

siokoshousiokoshou 2009/07/07 11:22 おぉぉTarZさん!! 6ビットの数ありがとうございます。後生大事に使わせていただきます。
2chのコメントは演算スレ0x02にあったものが0x03にコピペされてて、これ読んでようやく理解できました。それまではさっぱりわからず頭の上が???だらけでしたw
なるほどー、信号処理ですか。学生のころ苦手だったところだったり(^^;
本当におもしろい数ですね。一つの数にこれだけスゲーって盛り上がるとは思いもしませんでした。
ゴロム定規、M系列調べてみます。↑のコメントで山田さんもおっしゃってますが、ほかに応用ってどんなのがあるんでしょう?

TarZTarZ 2009/07/08 01:37  「ほかの応用」というよりは、どちらかというとM系列の本来の(?)使われ方になるのですが、コンピュータのプログラム関係では、周期の長い擬似乱数列生成が有名かと思います。ここから白色雑音生成などに利用でき、比較的軽い回路や処理で作れるので、信号処理の分野ではよく利用されます。
 私の専門ではないので詳しくは知りませんが、3G携帯電話の通信基盤(基地局〜端末)などでも使われているのではないでしょうか。

 ということで、M系列は(特に工学系の)学生さんにはおなじみの道具ではないかと思いますが、あのような応用があるとは思いもしませんでしたねえ。私も、M系列の話が出てきて初めて、昔の教科書をひっくり返したくらいでして。

http://chessprogramming.wikispaces.com/ のサイトは知らなかったので参考になります。ちょっと読んでみているところですが、De Bruijn sequenceは、M系列に最初から0を付与してある感じ。

siokoshousiokoshou 2009/07/08 14:22 > ここから白色雑音生成などに利用でき、比較的軽い回路や処理で作れるので、信号処理の分野ではよく利用されます。
なるほどー!ずいぶん前に、こんな安いチップでどうやってホワイトノイズ作ってるの?って疑問に思ったことがあったんですが、これで簡単に作れるんですね!ほほーう。
どちらかというとハードよりの応用が多いようですね。とても勉強になります。ありがとうございます。
> http://chessprogramming.wikispaces.com/ のサイト
ここ、おもしろいですよねw ちょっとはまってますw ふざけたことを大真面目に追求してるのがいい感じ!

KooniesKoonies 2009/07/08 21:24 どうも、興味深い話題ありがとうございます。
NLZについて何かないかなとずっと思っていたので参考になりました。
一応0x03F566ED27179461ULの生成コード書いてみました
http://d.hatena.ne.jp/Koonies/20090708/nlz3

siokoshousiokoshou 2009/07/09 00:15 おぉ!すばらしい。どうやらM系列は01の列で、De Bruijn sequenceは01に限らないって感じなのかな?
ダイクストラもDe Bruijn sequenceを求めるコードを書いたそうです。って記事を和田先生が書いている。二重の意味でびっくりな記事を見つけました。
http://parametron.blogspot.com/2009/04/dijkstra.html

CGI の De Bruijn sequenceジェネレーターだそうで。
http://www.hakank.org/comb/debruijn.cgi

De Bruijn sequenceのスゴイ応用w 一番下のビデオ
http://chessprogramming.wikispaces.com/De+Bruijn+sequence

KooniesKoonies 2009/07/09 00:27 M系列は触ったことがあったのでそれなりに理解できましたが
De Bruijn sequenceですか。
新しい課題ありがとうございます(笑

2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 09 | 11 | 12 |
2007 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 08 | 09 | 10 | 12 |
2009 | 01 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 07 |
2011 | 04 | 07 | 10 |
2012 | 04 | 12 |
2013 | 08 |
2014 | 03 | 08 |
2017 | 09 |
Connection: close