実装上の課題:反復トラバーサルによるロスレスでコンパクトな解析ツリー

私のパーサー コンビネーター ライブラリ lexy は、元々、Boost.Spirit に匹敵するユーザー定義のデータ構造にいくつかの文法を解析するように設計されました。単純に AST に解析します。しかし、設計上 01 句読点、コメント、または空白を含まない解析コンビネータによって明示的に生成されたデータのみを転送します。

最新のパーサー ジェネレーターに関する matklad のブログ投稿に触発されて、すべての情報を保持し、15 を呼び出してロスレスの解析ツリーを生成する方法を追加することにしました。 .これには、既存の文法を変更する必要はなく、単に出力を切り替えるだけです。これにより、特定の入力で特定の文法の解析ツリーを視覚化するオンライン プレイグラウンドを追加することもできます。

解析中に解析ツリーを生成する実際のコードを実装することは、それほど難しくありませんでした – 22 を実装するために、解析中に何が起こるかを制御するハンドラーが既にありました。 と 33 難しい部分は、解析ツリーを格納するための実際のデータ構造でした。大きくなる可能性があるため、メモリ効率が高く、ユーザーは再帰を必要とせずにすべてのノードを簡単に反復できる必要があります。

ベースライン

基本的に、48 元の入力に対する構造化されたビューであり、維持する必要があります。これは、2 種類のノードを含む m-ary ツリーです:トークン および生産 .トークン ノードはツリーのリーフ ノードであり、入力のスパンをトークンの種類 (基本的には 55 ツリー内のすべてのトークンを反復し、それらのスパンを連結すると、元の入力が返されます (ツリーはロスレスです)。プロダクション ノードは非リーフ ノードです。その子は他のプロダクション ノードまたはトークンです。ノード自体は、プロダクションの識別子のみを保存します。

C++ では、次のようになります (簡略化):

template <typename Iterator, typename TokenKind>
struct pt_node_token
{
    // The span of the input occupied by the token.
    Iterator begin, end;
    // What kind of token it is.
    TokenKind kind;
};

template <typename Iterator, typename TokenKind>
struct pt_node_production
{
    // In the grammar, productions are identified by their type.
    // Here we type-erase that to the name of the productions
    // (two productions are equal iff the name has the same address).
    const char* production_name;
    // The children are either other production nodes or tokens.
    std::vector<std::variant<pt_node_production<Iterator, TokenKind>,
        pt_node_token<Iterator, TokenKind>> children;
};

2 つの異なるノードがあるという事実は、実装の詳細です。実際の解析ツリーはそれらを隠します:

template <typename Iterator, typename TokenKind>
class parse_tree
{
    using node_p = pt_node_production<Iterator, TokenKind>;
    using node_t = pt_node_token<Iterator, TokenKind>;

public:
    // A view over an actual node.
    class node
    {
    public:
      // Returns something that can be compared to a token kind,
      // with functions like `.is_token()`, `.is_production()` etc.
      auto kind() const;

      // A range that iterates over the children of the node.
      // For a token node, this is the empty range.
      auto children() const;

      // A range that iterates over the span of a token in the input.
      // For a production node, this is empty.
      auto lexeme() const;

    private:
        // The pointer to the implementation.
        // This is okay, as the tree is immutable,
        // so once we've parsed everything, the address won't change.
        std::variant<node_p*, node_t*> _ptr;
    };

    node root() const
    {
        return node{&_root};
    }

private:
    // The tree stores the root node, which owns all children.
    pt_node_production<Iterator, TokenKind> _root;
};

65 の完全なインターフェース 入力を解析して解析ツリーに入れ、それを出力する完全な例は、Compiler Explorer にあります。

この基本的な設計は確かに機能しますが、いくつかの問題があります:

  • 使いやすさ :ノードには親へのポインタがありません。これは、ノードのすべての兄弟を反復することが不可能であることも意味します。
  • メモリ効率 :74 87 です 、 97 101 です 、および 115 120 です (最大バリアントのサイズ + タグをポインター サイズに切り上げたもの)。解析ツリーには、ロット が含まれます。 ノードの数であるため、これらの 48 バイトを合計できます (さらに、親ポインターは含まれません)。
  • メモリ割り当て :ほとんどの実稼働ノードには子ノードが 2 つしかないため、多くの小さなベクトルの割り当てを行っています。
  • 再帰 :ノードのすべての子孫を反復処理する場合は、再帰 (または別のスタック) を必要とする DFS を実行する必要があります。

131 を必要とする最適化された実装を作成するために、これらすべての問題に取り組みます。 親にアクセスする方法を含むノードごとに、4 KiB の倍数で割り当てを行い、再帰なしでポインターをたどるだけでトラバースできます。

ステップ 1:トークンの圧縮

現在、140 ほとんどの入力のポインタである 2 つの反復子と 153 を格納します 、これは 163 です .デフォルトでは、176180 です 、これは 40 億の異なるトークンの種類を可能にします。これはやり過ぎなので、191 を使用しましょう。 代わりに:65536 個の異なるトークンで十分です。その場合、202 も必要ありません。 テンプレート パラメータ – 高レベルの 214 まだ (間接的に) テンプレート化されており、キャストを行うことができます。

template <typename Iterator>
struct pt_node_token
{
    Iterator begin, end;
    std::uint_least16_t kind;
};

223 に注意してください まだ 239 です バイトですが、2 つのポインターと 16 ビットだけを格納したいのです!それを修正しましょう.

ランダム アクセス イテレータに制限する場合、範囲を定義するために 2 つのイテレータを格納する必要はありません。代わりにイテレータとサイズを格納できます。トークンはほとんどの場合小さいです。多くの単一文字トークンまたは <のような短いキーワードがあります。コード>242 .最長のトークンは文字列リテラルですが、それでも 32 ビット整数の 4 ギガバイト制限を超える可能性は低いです:

template <typename Iterator>
struct pt_node_token
{
    Iterator begin;
    std::uint_least32_t size;
    std::uint_least16_t kind;
};

現在、トークンは 256 のみです 、しかし 269 同じ情報を再構築できます。

ステップ 2:圧縮されたノード ポインター型

最終的な設計には、ノードへの多くのポインターが必要です。ベースラインでは、それらは 273 として表現されます。;別のタイプを作成しましょう:

template <typename Iterator>
class pt_node_ptr
{
    void* _ptr;
    bool _is_token;

public:
    pt_node_ptr()
    : _ptr(nullptr), _is_token(fale)
    {}

    void set(pt_node_token<Iterator>* ptr)
    {
        _ptr = ptr;
        _is_token = true;
    }
    void set(pt_node_production<Iterator>* ptr) { … }

    auto token() const
    {
        return _is_token
          ? static_cast<pt_node_token<Iterator>*>(_ptr) : nullptr;
    }
    auto production() const { … }
};

282 基本的にバリアントと同じですが、共用体の代わりに 290 を使用しています .これで何も得られませんでしたが、306 の可能な値について何かを実現することで最適化できるようになりました。 :null の場合は気にしないか、特定のアライメントを持つトークンまたはプロダクション ノードを指します!

両方 318328 64 ビット システムでは 8 のアライメントを持つストア ポインター。これは、ノードに有効なすべてのアドレスが 8 の倍数である必要があることを意味します。バイナリでは、8 の倍数であるアドレスは 3 つのゼロで終わります。

したがって、64 ビットのポインターが必要ですが、ポインター値の 3 ビットは常にわかっています。最後のビットは 0 になります。ブール値を格納するには、これで十分です!

template <typename Iterator>
class pt_node_ptr
{
    std::uintptr_t _address;

    explicit pt_node_ptr(void* ptr, unsigned type)
    : _value(reinterpret_cast<std::uintptr_t>(ptr))
    {
        // Assert that the alignment is correct.
        assert((_value & 0b1) == 0);
        // Set the type.
        _value |= (type & 0b1);
    }

public:
    // Pointers to a token have the last bit set to zero.
    static constexpr auto type_token      = 0b0u;
    // Pointers to a production have the last bit set to one.
    static constexpr auto type_production = 0b1u;

    pt_node_ptr() : pt_node_ptr(nullptr, type_token) {}

    void set(pt_node_token<Iterator>* ptr)
    {
        *this = pt_node_ptr(ptr, type_token);
    }
    void set(pt_node_production<Iterator>* ptr)
    {
        *this = pt_node_ptr(ptr, type_production);
    }

    unsigned type() const
    {
        // The type is given in the last bit.
        return _address & 0b1;
    }
    void* base() const
    {
        // The pointer value has the last bit set to zero.
        auto cleared = _address & ~std::uintptr_t(0b1);
        return reinterpret_cast<void*>(cleared);
    }

    auto token() const
    {
        return type() == type_token
          ? static_cast<pt_node_token<Iterator>*>(base()) : nullptr;
    }
    auto production() const { … }
};

これで 338 になりました スペース オーバーヘッドのない plus タグ!

ステップ 3:スタックの割り当て

この時点で、ツリー内のノードを指すスペース効率の良い方法が得られたので、先に進んですべてのノードに親ポインターを追加することができます。ただし、これは機能しません。たとえば、運用ノードの作成中、その子を 349 に繰り返し押し込んでいます 、これはある時点で再割り当てする必要があります。再割り当てすると、すべての要素のメモリ アドレスが変更されます。これは、1 つの要素が完成した運用ノードであり、子がそれを指している場合に問題になります。

そのため、ノードに安定したアドレスを提供する方法が必要です。簡単な方法の 1 つは、356 から切り替えることです。 364 へ .しかし、これはメモリ割り当ての状況を改善しません.

代わりに、スタック アロケータを使用しました。大きな (4 KiB) メモリ ブロックを割り当て、そのメモリをすべてのノードに使用します。ツリー全体が破壊されるまでノードを解放しないため、ポインタを進めるだけで割り当てることができます。 .ブロックの最後に到達したら、新しいブロックを割り当て、ブロックのリンク リストに格納します。

class pt_buffer
{
    static constexpr std::size_t block_size = 4096 - sizeof(void*);

    // One of the memory blocks.
    struct block
    {
        // Pointer to the next block;
        // for the active block it is nullptr.
        block* next;
        // The actual memory we're re-using.
        unsigned char memory[block_size];

        static block* allocate()
        {
            auto memory = ::operator new (sizeof(block));
            auto b = ::new (memory) block;
            b->next = nullptr;
            return b;
        }
    };

    // The initial block in our linked list of blocks.
    // It only matters in the destructor,
    // where we walk all the blocks.
    block* _head;

    block* _cur_block;
    unsigned char* _cur_pos;

public:
    // Appropriate constructors/destructors.
    // Destructor releases everything by deallocating all blocks.

    // Reserves space by allocating a new block if necessary.
    void reserve(std::size_t size)
    {
        auto remaining_capacity
          = (_cur_block->memory + block_size) - _cur_pos;
        if (remaining_capacity < size)
        {
            // Allocate new block and add to list.
            auto next = block::allocate();
            _cur_block->next = next;
            // Update current block and memory.
            _cur_block = next;
            _cur_pos = &_cur_block->memory[0];
        }
        // Now we can safely use [_cur_pos, _cur_pos + size)
    }

    // Creates an object of the given type.
    // Space must have been reserved before.
    template <typename T, typename... Args>
    T* allocate(Args&&... args)
    {
        // Sanity checks omitted:
        // T needs to have pointer alignment
        // (otherwise we need to take care of alignment),
        // and reserve() must have been called.

        // The memory is [_cur_pos, _cur_pos + sizeof(T)).
        auto memory = _cur_pos;
        _cur_pos += sizeof(T);
        return ::new (memory) T(LEXY_FWD(args)...);
    }
};

メモリを予約して割り当てて、ツリーのすべてのノードをバッファに格納すると、そのメモリ アドレスは決して変更されないため、ツリーの構築中であっても、ノードへのポインタを安全に格納できます。

プロダクション ノードの子は 376 になりました :メモリは個々のノードではなくツリーによって所有され、余分なメモリ オーバーヘッドなしで暗黙的にノードの型を格納するため、単純なポインタで十分です。

ステップ 4:リンクされたリスト

382 を格納する利点 ただし、これはここではあまり役に立ちません:ノードの n 番目の子にアクセスすることはめったにありませんが、特定の種類を持つ子 (空白のためにインデックスが異なる場合があります) 394 のマイナス面 は、すべてのポインターとスペース オーバーヘッド (3 つのポインター) を格納するための追加のメモリ割り当てです。

代わりに、古き良き侵入型リンクリストに切り替えることができます:すべてのノード (プロダクションとトークン) に 404 リスト内の次のノードに移動します。すべてのノードは、親が 1 つしかないため、1 つのリストにのみ含まれるため、これでうまくいきます。

これであなたの言っていることがわかります:リンクされたリストは悪いデータ構造です.

そして、これは 417 のようなものにも当てはまります ここでは、すべてのノードを個別に割り当てます。しかし、ここでは、すべてのノードが既にバッファ内に存在し、個別に割り当てられていません。また、それらは互いに近くにあるため、キャッシュ効果に役立ちます。たとえば、次のツリーを考えてみましょう:

そのメモリ レイアウトは次のとおりです。

production | Hello | child | w | o | r | l | d | !

ご覧のとおり、428 の子ノードは すぐにノードをたどります。子プロダクションを飛び越える場合にのみ、すべての子をスキップする必要があります。

リンクされたリストを実装するために、すべてのノードに共通のすべてのメンバー、つまり次のポインターを格納する基本クラスを導入しています:

template <typename Iterator>
struct pt_node
{
    pt_node_ptr<Iterator> ptr;
};

template <typename Iterator>
struct pt_node_token : pt_node<Iterator>
{
    // as before
};

template <typename Iterator>
struct pt_node_production : pt_node<Iterator>
{
    // see below
};

次に 438 も変更できます 447 のように 451 を返しません しかし、共通の基底クラス ポインター 464 .これにより、473 へのアクセスが許可されます 最初に型を照会する分岐を取らずにメンバーを呼び出します。

480 で 、 496 を置き換えます 最初の要素へのポインタと子の数:

template <typename Iterator>
struct pt_node_production : pt_node<Iterator>
{
    const char* production_name;
    std::size_t child_count;
    pt_node_ptr<Iterator> first_child;
};

子を追加するには、連結リストの最後に挿入し、子の数を増やします。連結リストに何かを追加するには、リストの現在の最後の要素へのポインタが必要ですが、これは構築にのみ関連するため、そうではありません。ツリーの一部として保存する必要はありません。

ノードの子に対する反復は 507 で始まります そして、各ノードの 511 に従います .

これはすでに改善されていますが、さらに改善することができます。ほとんどの場合、本番ノードの最初の子は直後に保存されるため、526 は必要ありません。 .必要なのは型を覚えておくことだけです。アドレスは 537 です !バッファの最後に本番ノードがある場合にのみ、最初の子ノードへのポインタが必要です。これは別のメモリ ブロックにあるためです。

今のアイデアは 540 を削除することです ポインターの代わりに、最初の子の型と、それがすぐ隣接しているかどうかを記憶するフラグを格納します。そうであれば、552 を再構築できます タイプとアドレス 566 を組み合わせて最初の子に そうでない場合、本番ノードの直後のメモリに実際のアドレスが含まれます。定義により、これは 4 KiB ブロックごとに 1 回だけ発生することに注意してください。

template <typename Iterator>
struct pt_node_production : pt_node<Iterator>
{
    const char* production_name;
    // We use a bit field to store the flags as one std::size_t.
    std::size_t child_count : sizeof(std::size_t) * CHAR_BIT - 2;
    std::size_t first_child_adjacent : 1;
    std::size_t first_child_type : 1;

    pt_node_ptr<Iterator> first_child()
    {
        // Get a pointer to the memory immediately afterwards.
        auto memory = static_cast<void*>(this + 1);
        if (first_child_adjacent)
        {
            // The memory contains the node.
            pt_node_ptr<Iterator> result;
            result.set(static_cast<pt_node<Iterator>*>(memory),
                       first_child_type);
            return result;
        }
        else
        {
            // The memory contains the actual pointer.
            return *static_cast<pt_node_ptr<Iterator>*>(memory);
        }
    }
};

もちろん、隣接するポインターを格納するためのスペースを確保することは重要です:

// In the code that adds a production node.

// Reserve enough for production and trailing pointer.
auto space_needed
  = sizeof(pt_node_production<Iterator>)
  + sizeof(pt_node_ptr<Iterator>);
buffer.reserve(space_needed);
auto node = buffer.allocate<pt_node_production<Iterator>>(…);

578 両方に十分な連続メモリがあることを保証しますが、586 ノードに適合するために必要な部分だけを進めます。同じブロックの子ノードに後続の割り当てを行う場合、これはポインター用に予約したメモリを使用しますが、そのメモリは直後であるため問題ありません。最初の子へのポインターは必要ありません!後続の割り当てが新しいブロックに配置される場合にのみポインターが必要ですが、その場合、古いブロックの残りのスペースはそのまま残され、そこに保存できます.

詳細については、ビルダー コードを確認してください。

ステップ 5:親ポインター

これで、ノードの安定したアドレスとコンパクトなポインターが得られました:593 を追加するだけです 609 のメンバー すべてのノードがポインターにアクセスできるようにするための基本クラスですよね?

まあ、それはすべてのノードに 8 バイトを追加し、サイズを 32 にします。特に、親へのアクセスは一般的な操作ではないため、許容できるとは思いません。幸いなことに、追加のメンバーを追加する必要はありません。 、利用可能なものがあります:既存の 613 リンクされたリストのメンバー。

すべての生産ノードは最初の子に到達する方法を知っており、そこから 623 に従います メンバーから次の子へ。本番ノードの最後の子は 638 で識別されます 645 のメンバー .それでは、代わりに本番ノードに戻りましょう!

そのためには、658 を変更する必要があります ポインタの追加情報を 1 つ格納するようにします:役割です。 親の次の子 (つまり、その兄弟)、または「親」ロールを指します。これは、ノードが最後の子であり、676 であることを意味します 親を指します。アライメントが 8 であるため、まだ使用していないゼロが 2 つあります:

template <typename Iterator>
class pt_node_ptr
{
    std::uintptr_t _address;

    explicit pt_node_ptr(void* ptr, unsigned type, unsigned role)
    : _value(reinterpret_cast<std::uintptr_t>(ptr))
    {
        // Assert that the alignment is correct.
        assert((_value & 0b11) == 0);
        // Set the type.
        _value |= (type & 0b1);
        // Set the role.
        _value |= (role & 0b1) << 1;
    }

public:
    static constexpr auto role_sibling = 0b0u;
    static constexpr auto role_parent  = 0b1u;

    …

    // previously, it was just `set`
    void set_sibling(pt_node_token<Iterator>* ptr) { … }
    void set_sibling(pt_node_production<Iterator>* ptr) { … }

    // No need to overload for token nodes;
    // they won't ever be parents.
    void set_parent(pt_node_production<Iterator>* ptr)
    {
        *this = pt_node_ptr(ptr, type_production, role_parent);
    }

    unsigned type() const
    {
        // The type is given in the last bit.
        return _address & 0b1;
    }
    unsigned role() const
    {
        // The role is given in the second last bit.
        return (_address & 0b10) >> 1;
    }

    pt_node<Iterator>* base() const
    {
        // The pointer value has the last two bits set to zero.
        auto cleared = _address & ~std::uintptr_t(0b11);
        return reinterpret_cast<pt_node<Iterator>*>(cleared);
    }

    auto token() const { … }
    auto production() const { … }
};

ビルダーは 681 プロダクションの最後の子のメンバーが適切に設定されたので、準備完了です。ノードの親を照会するには、その 696 をたどり続けるだけです ロールが 708 のメンバーになるまで – 親ノードを指します。これは 717 です 、しかし、私たちは何か他のものを無料で手に入れているので、それは問題ありません.

ステップ 6:トラバーサル

どのツリーにも、反復したい有用な範囲が 3 つあります。

最初の範囲は、ノードのすべての直接の子の範囲です。これは常に可能でした。新しい設計では、プロダクション ノードから最初の子へのポインタを取得し、720 を繰り返し続けます。 730 になるまで 、それで終わりです。

2 番目の範囲は、ノードのすべての兄弟の範囲です。新しい設計では、これも可能です。744 に従うだけです。 759に達するまで 、次に親の最初の子に移動します。最初のノードに再び到達すると、反復は停止します。

3 番目の範囲は、ノードの直接および間接のすべての子を反復することです。ルート ノードの場合、これは深さ優先の方法でツリー全体を反復することを意味します。通常、これには、直接の子に対するループと、各子に再帰的にアクセスします。これには線形のスタック スペースが必要であり、C++ の反復子モデルにはうまく適合しません。

しかし、新しい設計では、再帰なしで完全に反復的に実行できます。アイデアは、開始ノードの最初の子に移動してから、763 をたどり続けることです。 .772 の型の場合 がプロダクションでロールが「兄弟」の場合、初めてプロダクションに到達したので、その子を訪問する必要があります。そのため、次はプロダクションの最初の子に移動します。しかし、 <のタイプがコード>781 はプロダクションであり、役割は「親」です。以前に訪問したことがあり、戻ってきたばかりです。次に、プロダクションの 793 に進みます。 兄弟を続行します。

または、C++ イテレータのインクリメント演算子のロジックとして:

iterator& operator++()
{
    if (_cur.token())
        // A token has no children, so we continue with its sibling.
        _cur = _cur.base()->ptr;
    else if (_cur.is_sibling_ptr())
        // We've reached the production for the first time,
        // go to its first child.
        _cur = _cur.production()->first_child();
    else if (_cur.is_parent_ptr())
        // We've reached the production for the second time,
        // go to its sibling.
        _cur = _cur.base()->ptr;

    return *this;
}

したがって、解析ツリーのトラバースは、リンクされたリストのトラバースと同じくらい簡単です!再帰もスタックもなく、単純なポインターの追跡のみです.そして、サンプル ツリーのメモリ レイアウトを思い出してください:

production | Hello | child | w | o | r | l | d | !

806 にアクセスします 、次に 819 、次に 823 、次に 831 , … – トラバーサルは単にブロックを順番にたどります.子の後にのみ親に戻り、次にすべての子に戻ります.しかし、ほとんどの場合、さらに24バイトを指すポインターを逆参照しているだけです.あたかも配列を反復処理しているかのように、メモリ ブロック!

結論

この時点で停止しましたが、さらなる最適化が可能です。たとえば、仮想メモリを使用すると、ツリーに必要以上に大量のメモリを割り当てることができ、必要なときにのみコミットできます。ブロックのリンクされたリストが不要になり、バッファ内の割り当てが高速になり、生産ノードが簡素化されます。

拡張ヘッダー 843 解析ツリーを操作するための便利なアルゴリズムがいくつか含まれています。たとえば、857 識別子である最初の (直接の) 子ノードを返します。これには、すべての子を反復処理する必要があります。これには、前のすべての子をメモリにロードし、その種類を確認し、それが識別子であるかどうかを判断する必要があります。何かを追加する方が高速です。 866 のように 実稼働ノードへ – その後、アルゴリズムはベクトルを反復処理するだけでよく、以前のすべての子ノードをメモリにロードしません。

ただし、そのような最適化が価値があるかどうかは、これまでよりも多くのベンチマークが必要です。