seq

連続

Glenn Fiedler によるこのブログ投稿で説明されているシーケンス バッファーの Go での高速実装。単体テスト カバレッジは 100% です。

これは、信頼性の高い UDP ネットワーキング プロトコルを作成する目的で構築されており、シーケンス バッファーは、以下の目的で効率的で回復力のある固定サイズのローリング バッファーとして使用できます。

1. 送受信パケット上のメタデータの追跡、
2. 信頼性の低いストリームから受信したパケットの順序付け、または
3. ピアから送信されたパケットの受信者に対する確認応答を追跡します。

エントリのバッファリングに使用されるシーケンス番号は、符号なし 16 ビット整数に固定されています。これは、大量のエントリは冗長であり、パケット確認応答システムに無視できる程度の改善しか与えないためです。

注意事項

バッファのサイズは、符号なし 16 ビット整数の最大値 (65536) で割り切れる必要があります。そうでないと、シーケンス番号によってバッファリングされたデータがバッファ全体にラップされません。この問題は、このライブラリのテストを作成中に発生しました。

RemoveRangeメソッドは、for ループ上でいくつかのmemcpy呼び出しを使用するために、リファレンス C コードベース Reliable.io のシーケンス バッファー実装に対してベンチマークされ、最適化されました。

実際のシーケンスとバッファリングされたデータは 2 つの別々の連続したスライスに格納されるため、ローリング バッファからポップされたエントリは古いメモリとして残り、後で必要に応じてガベージ コレクトされる可能性があります。

設定

 go get github.com/lithdew/seq

ベンチマーク

 $ go test -bench=. -benchtime=10s
goos: linux
goarch: amd64
pkg: github.com/lithdew/seq
BenchmarkTestBufferInsert-8                     327525945               35.6 ns/op             0 B/op          0 allocs/op
BenchmarkTestBufferRemoveRange-8                243091503               51.3 ns/op             0 B/op          0 allocs/op
BenchmarkTestBufferGenerateBitset32-8           84982886               137 ns/op               0 B/op          0 allocs/op