Thread Safe な Interlocked Singly Linked Lists を使ってみる

iislua でスレッドセーフなリストが必要になったので調べてみると、Windows API には Interlocked Singly Linked Lists (SList) というのが用意されていることを知りました。MSDN にちゃんと解説がありました。

Interlocked Singly Linked Lists - Win32 apps | Microsoft Learn

リストと言っても API 的にはスタックとして使うような形になっています。

ノンブロッキングなアルゴリズムで SList は実装されているようです。MSDN よりも以下のページの解説の方が分かりやすい気がするので紹介しておきます。パフォーマンスの比較もあります。

やはり Windows にネイティブ実装されているので、パフォーマンスは優れているようです。

一応 MSDN には簡単なサンプルコードも用意されています。

Using Singly Linked Lists - Win32 apps | Microsoft Learn

サンプルコードが地味に分かりにくかったので、もっとシンプルにしたものを用意しておきました。

// 先頭に必ず SLIST_ENTRY が必要
typedef struct _SLIST_ITEM {
    SLIST_ENTRY ItemEntry;
    int Value;
} SLIST_ITEM, *PSLIST_ITEM;

int main()
{
    // SList を初期化
    auto pListHead = static_cast<PSLIST_HEADER>(_aligned_malloc(sizeof(SLIST_HEADER), MEMORY_ALLOCATION_ALIGNMENT));

    InitializeSListHead(pListHead);

    for (int i = 1; i <= 5; i += 1)
    {
        // SList にアイテムを追加する
        auto pListItem = static_cast<PSLIST_ITEM>(_aligned_malloc(sizeof(SLIST_ITEM), MEMORY_ALLOCATION_ALIGNMENT));

        pListItem->Value = i;

        InterlockedPushEntrySList(pListHead, &pListItem->ItemEntry);

        printf("Push Value is %d\n", pListItem->Value);
    }

    printf("=====================\n");

    while (true)
    {
        // SList からアイテムを取り出す
        auto pListEntry = InterlockedPopEntrySList(pListHead);

        if (pListEntry == nullptr)
        {
            printf("List is empty.\n");
            break;
        }

        auto pListItem = reinterpret_cast<PSLIST_ITEM>(pListEntry);

        printf("Pop Value is %d\n", pListItem->Value);

        _aligned_free(pListEntry);
    }

    _aligned_free(pListHead);

    return 1;
}

このサンプルコードを実行すると以下のようになります。スタックとして動作していることが分かります。

注意点としては SList で使うメモリは全て 8/16 バイトでアライメントされたものが必要になるみたいです。なので new などを使うのではなく _aligned_malloc で確保する必要があります。

複数スレッドでアクセスした時の挙動も確認しようと思ったんですが、ここまで書いてめんどくさくなったのでドキュメントを信じることにします。