当面C#と.NETな記録

■[VisualStudio] VisualStudio2010は2010年春？

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

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

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

ツイートする

■[C#] .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() ) );
    }
}

つづく

ツイートする

■[C#] .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 メンバー
• 並列プログラミングのデータ構造体
• チュートリアル: Parallel アプリケーションをデバッグ

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

Parallel Tasks

見方がよくわからないｗ

ツイートする

■[C#] .NET4.0 の Parallel メモ

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

• http://blogs.msdn.com/pfxteam/archive/2009/03/04/9457880.aspx
  • ConcurrentBag<T> : スレッドセーフってどういうこと？ロックしないで複数のスレッドから同時に Add できる？
  • System.Lazy<T>, System.LazyVariable<T>, System.Threading.LazyInitializer, System.Threading.ThreadLocal<T>
  • http://msdn.microsoft.com/ja-jp/library/system.collections.concurrent(VS.100).aspx

• http://msdn.microsoft.com/ja-jp/library/system.threading.spinlock(VS.100).aspx
  • SpinLock 追加

• http://blogs.msdn.com/pfxteam/archive/2009/03/27/9514938.aspx
  • Task Parallel Library (TPL) は今や mscorlib.dll に。いつのまにか using System.Threading; で使えるようになってる。
  • 昔、Parallel.アグリゲート だったのがいつのまにか Parallel.For<> になってた。最後のくっつけるところではやっぱりロックがいるんだね。ロックにさよならできるかと思ってたのに甘かった。
  • http://msdn.microsoft.com/ja-jp/library/dd321836(VS.100).aspx

• http://msdn.microsoft.com/ja-jp/library/system.threading.barrier(VS.100).aspx
  • バリアって何だ？(追記:メモリバリア。havanaclubさん、ありがとうございます)

• http://blogs.msdn.com/pfxteam/archive/2008/07/23/8768673.aspx
  • 継続？

追記:

• Lock-freeとWait-freeアルゴリズム
• InfoQ Parallel-Programming
• MSDNmagazine October 2008 並列特集？

ツイートする

■[C#] De Bruijn sequence を列挙するコード

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

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

ツイートする

■[C#] 一番右端の立っているビット位置を求める「ものすごい」コードのていねいな説明

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

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で無理ですね。おしまい。

ツイートする

■[C#] 一番右端の立っているビット位置を求める「ものすごい」コード

一番右端の立っているビット位置(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;
}

意味わかりますか？ｗ

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だけ追加すればおｋ。
これだけだと順番がバラバラなので、テーブルと組み合わせる。
(中略)
ビット溢れによるマスクなども組み合わせているが。

そして、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 の値によって何ビット左シフトするか変わるので、ｙ の値によって上位 6bit のビットパターンが変わります)。最後に 58bit (58=64-6) 右シフトして上位 6bit のビットパターンを下位に移動し(下位 bit をマスク)、テーブルを引きます。このとき符号付き整数を使うと符号拡張されてしまい、さらに下位 6bit の AND を取る必要がありますが ulong を使うことでこの手間を回避しています。

参考リンク

• http://slashdot.jp/~Tellur52/journal/448479
• http://slashdot.jp/~tarosuke/journal/448442
• http://slashdot.jp/~tarosuke/journal/448489 (数列の求め方？)

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

• http://www.0xe3.com/text/ntz/ComputingTrailingZerosHOWTO.html
• http://www-graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup (bit黒魔術がいっぱい)
• http://citeseer.ist.psu.edu/leiserson98using.html (これが最初の論文かな？)
• http://chessprogramming.wikispaces.com/De+Bruijn+sequence (数学に興味がある方はこちらを見ると楽しいかも)

おまけ。この問題を解く 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 は機械語にすると何命令実行することになるとか論じてる本ですｗ 分岐や割り算をできるだけ避けるような、そういう世界。

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

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

ツイートする