読者です 読者をやめる 読者になる 読者になる

け日記

SIerから転職したWebアプリエンジニアが最近のIT技術キャッチアップに四苦八苦するブログ

C# Regexクラスのインスタンスメソッドと静的メソッドの性能比較

大量のURL文字列を正規表現パターンとマッチングして分類するバッチ処理C#で開発していたところ、実装が進んで分類を増やすと、唐突に割に合わない処理時間となってしまったことがありました。 原因としては正規表現のマッチング方法が非効率的だったためでした。

今回はRegexクラスの静的メソッドを使ったマッチングとインスタンスメソッドを使ったマッチングで性能比較してみます。

C#での正規表現

C#正規表現ではRegexクラス(System.Text.RegularExpressions)が一般的に使われますが、マッチングにおいてはいくつかのアプローチが提供されています。

特にインスタンス化の方法はパフォーマンスに大きな影響を与えることがあり、MSDNでも言及されています。 https://msdn.microsoft.com/ja-jp/library/gg578045(v=vs.110).aspx

マッチング方法は主に2つあります。

Regex静的メソッドを使う

例えば、文字列inputで4桁の数字をマッチングする場合はこんな感じです。

using System.Text.RegularExpressions;

Regex.Match(input, "[0-9]{4}");

メソッドの呼び出しによって正規表現パターン("[0-9]{4}“)がオペレーションコードへ変換されるのですが、この変換結果はキャッシュされるようになっています。 キャッシュされるパターン数はRegex.CacheSizeプロパティで指定できます(デフォルトで15)。

冒頭の事象は、分類が増えたことによってキャッシュする変換済みの正規表現パターンが増え、キャッシュミスが頻発したことによってパフォーマンスが劣化したためでした。

Regexインスタンスメソッドを使う

Regexクラスを正規表現パターンを引数としてインスタンス化する方法もあります。

using System.Text.RegularExpressions;

var regex = new Regex("[0-9]{4}");
regex.Match(input);

インスタンス化することで正規表現パターンから変換されたオペレーションコードをキャッシュにかかわらず持たせることができます。 冒頭の事象では、分類が限られていたということもあり、インスタンス化することで解決しました。

さらにオペレーションコードからMSILまでコンパイルするオプション(RegexOptions.Compiled)も用意されており、繰り返しマッチングする場合はコンパイルしたほうが高速とのことです。

var regex = new Regex("[0-9]{4}", RegexOptions.Compiled);

パフォーマンス比較

手軽なのは静的メソッドを使う方法ですが、何度も同じ正規表現文字列を使う場合にはインスタンスメソッドを使うことがパフォーマンスの面で推奨されています。
1,000,000件のGuid文字列から"[0-9]{4}“をマッチングするコードを4パターンで実装し、実行時間を比較してみました。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text.RegularExpressions;

namespace ConsoleApplication
{
    public class Program
    {
        public static void Main(string[] args)
        {
            long staticMethodTotal = 0;
            long staticMethodNoCacheTotal = 0;
            long instanceMethodTotal = 0;
            long instanceMethodCompiledTotal = 0;

            Console.WriteLine(Regex.CacheSize);

            // 10回平均を求める
            for (var try_num = 0; try_num < 10; try_num++) 
            {
                // 1,000,000個のGUID文字列からなるリストを生成
                var list = new List<string>();
                for (int i = 0; i < 1000000; i++)
                {
                    list.Add(new Guid().ToString());
                }

                var sw = new Stopwatch();

                // パターン1. Regex静的メソッドを使う(キャッシュ有り)
                Regex.CacheSize = 1;
                sw.Start();
                UseStaticMethod(list);
                sw.Stop();
                staticMethodTotal += sw.ElapsedMilliseconds;

                // パターン2. Regex静的メソッドを使う(キャッシュ無し)
                Regex.CacheSize = 0; // キャッシュ数を0にして無効化
                sw.Reset();
                sw.Start();
                UseStaticMethod(list);
                sw.Stop();
                staticMethodNoCacheTotal += sw.ElapsedMilliseconds;

                // パターン3. Regexインスタンスメソッドを使う(コンパイルオプション無効)
                sw.Reset();
                sw.Start();
                UseInstanceMethod(list);
                sw.Stop();
                instanceMethodTotal += sw.ElapsedMilliseconds;

                // パターン4. Regexインスタンスメソッドを使う(コンパイルオプション有効)
                sw.Reset();
                sw.Start();
                UseInstanceMethod(list, true);
                sw.Stop();
                instanceMethodCompiledTotal += sw.ElapsedMilliseconds;
            }

            Console.WriteLine(staticMethodTotal / 10.0);
            Console.WriteLine(staticMethodNoCacheTotal / 10.0);
            Console.WriteLine(instanceMethodTotal / 10.0);
            Console.WriteLine(instanceMethodCompiledTotal / 10.0);
        }

        private static List<bool> UseStaticMethod(List<string> list)
        {
            var result = new List<bool>();

            foreach (var guid in list)
            {
                result.Add(Regex.IsMatch(guid, "[0-9]{4}"));
            }

            return result;
        }

        private static List<bool> UseInstanceMethod(List<string> list, bool compiled = false)
        {
            var regex = compiled ? 
                        new Regex("[0-9]{4}", RegexOptions.Compiled) : 
                        new Regex("[0-9]{4}");

            var result = new List<bool>();

            foreach (var guid in list)
            {
                result.Add(regex.IsMatch(guid));
            }

            return result;
        }
    }
}

結果は結果は以下の通りでした。

  • キャッシュの有無(パターン1.と2.の比較)は強力で、約7倍の性能差となって現れました
    • 暗黙的にキャッシュされるので、少し正規表現パターンを増やしただけなのに性能がガクッと落ちた際はキャッシュミスを疑ってみるのはありです
  • インスタンスメソッドの方が高速(パターン1.と3.の比較)になりましたが、感覚的にはそこまで大きな差がない印象です
    • 純粋にインスタンスの生成コストの差のようで、キャッシュさえ効いていればどっちでも良いですね
  • コンパイル有無(パターン3.と4.の比較)については定説と逆転してしまいました(謎です。。。)
実行時間[ms]
パターン1. Regex静的メソッドを使う(キャッシュ有り) 472
パターン2. Regex静的メソッドを使う(キャッシュ無し) 3329
パターン3. Regexインスタンスメソッドを使う(コンパイルオプション無効) 258
パターン4. Regexインスタンスメソッドを使う(コンパイルオプション有効) 266

今回は単純な正規表現パターンで比較しましたが、バックトラッキングなどを使ってもっと複雑になってくると、より顕著に性能差が広がると思われます。

Dictionaryのキーに複数の値を使う

Dictionaryのキーに複数の値を使う方法について、考察してみます。

Dictionaryのキーに複数の値を使う方法

Dictionaryのキーに複数の変数値を使いたい場合(例えば、クラス名と出席番号をキーとして氏名を値とする、など)にいくつかの方法が考えられますが、以下3つに分類されるかと思います。

  1. キーの値を連結するなどして1つのキーを作成する
var className = "Aクラス";
var number = 1;
var name = "荒岩 一味";

var students = new Dictionary<string, string>();
students.Add(className + number, name);
Console.WriteLine(students[className + number]);
  1. Dictionaryを値とするDictionaryを作成する(Dictionary<TKey1, Dictionary<TKey2, TValue>>)
var students = new Dictionary<string, Dictionary<int, string>>();
students.Add(className, new Dictionary<int, string>{ { number, name } });
Console.WriteLine(students[className][number]);
  1. Tupleをキーとする(Dictionary<Tuple<TKey1, TKey2>, TValue>)
var students = new Dictionary<Tuple<string, int>, string>();
students.Add(new Tuple<string, int>(className, number), name);
Console.WriteLine(students[new Tuple<string, int>(className, number)]);

1.は気軽に実装できるのですが、キーの型が異なる場合に型変換を行う必要があったり、結合した結果キーが重複する場合("クラス1"と"23"、"クラス12"と"3"は結合するといずれも"クラス123"となる)を考慮しないといけないなど、使えるケースは限定的です。

実際の開発ではキーの型と同一性が保証される2.か3.を採用することが多いかと思います。

で、どっちを使うかですが、実装レベルではキーを1つにまとめられるTupleを使う3.の方法の方が素直だと思います。 2.の方法では、値(TValue)を追加・参照するたびに、上位のDictionaryのキー(TKey1)の有無を常にチェックする必要があるのも面倒です。

性能は状況により異なりそうですが、2.の方が分は良さそうです。

  • 追加・参照のたびにTupleを生成する必要がある
  • TKey1が値の数に比べて少ない場合は、メモリ効率が良い(TKey1が集約されるため)

性能比較

それぞれの方法でDictionaryに値を追加・参照するコードを使って、両者の性能を比較してみます。

firstKeyPatternは上位のDictionaryのキー(TKey1)、secondKeyPatternは下位のDictionaryのキー(TKey2)のパターン数です。 例えば、firstKeyPatternが2、secondKeyPatternが3の場合、キーは("0", 0)、("0", 1)、("0", 2)、("1", 0)、("1", 1)、("1", 2)の6パターンとなります。

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var firstKeyPattern = 1;
            var secondKeyPattern = 1000000;

            var sw = new Stopwatch();
            var name = "荒岩 一味";

            sw.Start();
            var firstDictionary = new Dictionary<string, Dictionary<int, string>>();
            for (int i = 0; i < firstKeyPattern; i++)
            {
                var secondDictionary = new Dictionary<int, string>();
                for (int j = 0; j < secondKeyPattern; j++)
                {
                    secondDictionary.Add(j, name);
                }
                firstDictionary.Add(i.ToString(), secondDictionary);
            }
            sw.Stop();
            Console.WriteLine("2.(Add): " + sw.ElapsedMilliseconds);
            sw.Reset();

            sw.Start();
            var list = new List<string>();
            for (int i = 0; i < firstKeyPattern; i++)
            {
                if (firstDictionary.ContainsKey(i.ToString()))
                {
                    for (int j = 0; j < secondKeyPattern; j++)
                    {
                        if (firstDictionary[i.ToString()].ContainsKey(j))
                        {
                            list.Add(firstDictionary[i.ToString()][j]);
                        }
                    }
                }
            }
            sw.Stop();
            Console.WriteLine("2.(Get): " + sw.ElapsedMilliseconds);
            sw.Reset();

            sw.Start();
            var tupleDictionary = new Dictionary<Tuple<string, int>, string>();
            for (int i = 0; i < firstKeyPattern; i++)
            {
                for (int j = 0; j < secondKeyPattern; j++)
                {
                    tupleDictionary.Add(new Tuple<string, int>(i.ToString(), j), name);
                }
            }
            sw.Stop();
            Console.WriteLine("3.(Add): " + sw.ElapsedMilliseconds);
            sw.Reset();

            sw.Start();
            list = new List<string>();
            for (int i = 0; i < firstKeyPattern; i++)
            {
                for (int j = 0; j < secondKeyPattern; j++)
                {
                    var key = new Tuple<string, int>(i.ToString(), j);
                    if (tupleDictionary.ContainsKey(key))
                    {
                        list.Add(tupleDictionary[key]);
                    }
                }
            }
            sw.Stop();
            Console.WriteLine("3.(Get): " + sw.ElapsedMilliseconds);
        }
    }
}

Macbook Pro(.net core 1.1)の環境で実行した結果は以下の通りでした。

  • TKey1のパターンが少ない場合は、2.の方法が性能的には優位
  • 最悪ケース(firstKeyPattern=1000000, secondKeyPattern=1)でも両者の性能差はそれほど無い
    • Tupleの生成や比較にかかるコストが高そう
実行時間(ms) 2.値の追加 2.値の参照 3.値の追加 3.値の参照
firstKeyPattern=1, secondKeyPattern=1000000 60 359 600 781
firstKeyPattern=1000, secondKeyPattern=1000 124 345 691 726
firstKeyPattern=1000000, secondKeyPattern=1 978 741 853 937

まとめ

複数の変数を組み合わせてDictionaryのキーとする方法をそれぞれ比較してみました。

実装の素直さを優先したり格納するデータが少ない場合はDictionary<Tuple<TKey1,TKey2>, TValue>、データ数が多く一方のキーに重複が多い(カーディナリティが低い)場合はDictionary<TKey1, Dictionary<TKey2, TValue>>のデータ構造を使う、というのが妥当な線ですね。

C#でDynamoDBをバルクで取得・更新する

DynamoDBをバッチなどでアクセスすることを想定して、今回はDynamoDBのデータをバルクで取得・更新させてみます。

BatGetとBatchWrite

DynamoDBをバルクで取得・更新する場合、C#の永続性モデルではDynamoDBContextクラスで提供されるBatchGetおよびBatchWriteを使います。

docs.aws.amazon.com

// バルクで取得する場合
using (var dbContext = new DynamoDBContext(DbClient))
{
    // DynamoDBContextでBatchGetを作成して、
    var batchGet = dbContext.CreateBatchGet<BulkTestTableItem>();
    for (var j = 0; j < recordCount; j++)
    {
        // 取得するアイテムのキーをセットして、
        batchGet.AddKey(j.ToString());
    }
    // ExecuteAsyncで非同期に取得する
    batchGet.ExecuteAsync().Wait();
    var items = batchGet.Results;
}
// バルクで更新する場合
using (var dbContext = new DynamoDBContext(DbClient))
{
    // DynamoDBContextでBatchWriteを作成して、
    var batchWrite = dbContext.CreateBatchWrite<BulkTestTableItem>();
    // アイテムを追加して、
    batchWrite.AddPutItems(items);
    // ExecuteAsyncで非同期に更新する
    batchWrite.ExecuteAsync().Wait();
}

実例と性能測定

実例としてDynamoDBをバルクで取得して、カウンタをインクリメントして、バルクで更新するLamdaを作成します。
また、1件ずつ取得・更新する場合と比較して、どの程度速くなるのかを計測してみます。

DynamoDBテーブルの作成

テスト用に、文字列型のパーティションキーIdのみが設定されたシンプルなDynamoDBテーブル(bulk-test-table)を作成しました。
DynamoDBの読み書きがボトルネックとなることを防ぐため、今回は読み込み・書き込みのキャパシティを100に設定しています。

f:id:ohke:20170309225756j:plain

Lambdaの実装

2パターンで取得・更新する、性能測定用のLambdaを作成します。

  1. 1アイテムずつ取得・更新
  2. 全アイテムをバルクで取得・更新

引数(input)には1回で取得・更新するアイテム数と、試行回数を指定します。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading.Tasks;
using Amazon;
using Amazon.DynamoDBv2;
using Amazon.DynamoDBv2.DataModel;
using Amazon.Lambda.Core;

[assembly: LambdaSerializerAttribute(typeof(Amazon.Lambda.Serialization.Json.JsonSerializer))]

namespace DynamoReplicationLambda
{
    public class Function
    {
        private static readonly AmazonDynamoDBClient DbClient = new AmazonDynamoDBClient(RegionEndpoint.USWest2);

        // inputは1試行で取得・更新するアイテム数と試行数を指定します("100 10"の場合は、100アイテムの取得・更新を10回試行する)
        public void FunctionHandler(string input, ILambdaContext context)
        {
            var sw1 = new Stopwatch();
            var sw2 = new Stopwatch();

            var recordCount = int.Parse(input.Split(' ')[0]);
            Console.WriteLine("Record count: " + recordCount);

            var tryCount = int.Parse(input.Split(' ')[1]);
            Console.WriteLine("Try count: " + tryCount);

            // 初期化用のデータの投入
            using (var dbContext = new DynamoDBContext(DbClient))
            {
                for (int i = 0; i < recordCount; i++)
                {
                    dbContext.SaveAsync(new BulkTestTableItem
                    {
                        Id = i.ToString(),
                        Count = 0
                    }).Wait();
                }
            }

            // ①1アイテムずつ取得・更新(同期版)
            using (var dbContext = new DynamoDBContext(DbClient))
            {
                sw1.Start();
                for (var i = 0; i < tryCount; i++)
                {
                    for (var j = 0; j < recordCount; j++)
                    {
                        var task = dbContext.LoadAsync<BulkTestTableItem>(hashKey: j.ToString());
                        task.Wait();
                        var item = task.Result;

                        item.Count++;

                        dbContext.SaveAsync(item).Wait();
                    }
                }
                sw1.Stop();
            }

            // ②全アイテムをバルクで取得・更新
            using (var dbContext = new DynamoDBContext(DbClient))
            {
                sw2.Start();
                for (var i = 0; i < tryCount; i++)
                {
                    var batchGet = dbContext.CreateBatchGet<BulkTestTableItem>();
                    for (var j = 0; j < recordCount; j++)
                    {
                        batchGet.AddKey(j.ToString());
                    }
                    batchGet.ExecuteAsync().Wait();
                    var items = batchGet.Results;

                    items = items.Select(item => new BulkTestTableItem {Id = item.Id, Count = item.Count + 1}).ToList();

                    var batchWrite = dbContext.CreateBatchWrite<BulkTestTableItem>();
                    batchWrite.AddPutItems(items);
                    batchWrite.ExecuteAsync().Wait();
                }
                sw2.Stop();
            }

            Console.WriteLine($"①実行時間[ms]: {sw1.ElapsedMilliseconds}");
            Console.WriteLine($"②実行時間[ms]: {sw2.ElapsedMilliseconds}");
        }
    }

    [DynamoDBTable("bulk-test-table")]
    internal class BulkTestTableItem
    {
        [DynamoDBHashKey]
        [DynamoDBProperty(AttributeName = "Id")]
        public string Id { get; set; }
        
        [DynamoDBProperty(AttributeName = "Count")]
        public int Count { get; set; }
    }
}

測定結果

1アイテムずつ1000回取得・更新した場合と、100アイテムずつ10回バルク取得・更新するのにかかった処理時間をそれぞれ示します。
見ての通り、バルクで取得・更新するほうが約23倍高速になっており、効果は大きいことがわかるかと思います。

処理時間[ms]
1アイテムずつ1000アイテムを取得・更新 20678
100アイテムを10回バルクで取得・更新 886