Benchmark PieceRequestOrder with varying styles of path hint usage

Add per-piece piece request order path hints

diff --git a/piece.go b/piece.go
index 1c4375f1af0e66b3c156a1104c0c37436a421336..6842f1f0f11f065cfc12a542521793a20bbe17d2 100644 (file)
--- a/piece.go
+++ b/piece.go
@@ -8,7 +8,6 @@ import (
        "github.com/RoaringBitmap/roaring"
        "github.com/anacrolix/chansync"
        "github.com/anacrolix/missinggo/v2/bitmap"
-
        "github.com/anacrolix/torrent/metainfo"
        pp "github.com/anacrolix/torrent/peer_protocol"
        "github.com/anacrolix/torrent/storage"

diff --git a/request-strategy/piece-request-order.go b/request-strategy/piece-request-order.go
index 35dcf709c9fea3336349a1b7d73ba0177ff1173a..d5b4f17545a5afb2873757384fb4e662c590e2ec 100644 (file)
--- a/request-strategy/piece-request-order.go
+++ b/request-strategy/piece-request-order.go
@@ -21,7 +21,7 @@ func NewPieceOrder() *PieceRequestOrder {
 type PieceRequestOrder struct {
        tree     *btree.BTree[pieceRequestOrderItem]
        keys     map[PieceRequestOrderKey]PieceRequestOrderState
-       pathHint btree.PathHint
+       PathHint *btree.PathHint
 }
 
 type PieceRequestOrderKey struct {
@@ -51,7 +51,7 @@ func (me *PieceRequestOrder) Add(key PieceRequestOrderKey, state PieceRequestOrd
        if _, ok := me.tree.SetHint(pieceRequestOrderItem{
                key:   key,
                state: state,
-       }, &me.pathHint); ok {
+       }, me.PathHint); ok {
                panic("shouldn't already have this")
        }
        me.keys[key] = state
@@ -59,7 +59,10 @@ func (me *PieceRequestOrder) Add(key PieceRequestOrderKey, state PieceRequestOrd
 
 type PieceRequestOrderPathHint = btree.PathHint
 
-func (me *PieceRequestOrder) Update(key PieceRequestOrderKey, state PieceRequestOrderState) {
+func (me *PieceRequestOrder) Update(
+       key PieceRequestOrderKey,
+       state PieceRequestOrderState,
+) {
        oldState, ok := me.keys[key]
        if !ok {
                panic("key should have been added already")
@@ -71,11 +74,11 @@ func (me *PieceRequestOrder) Update(key PieceRequestOrderKey, state PieceRequest
                key:   key,
                state: oldState,
        }
-       if _, ok := me.tree.DeleteHint(item, &me.pathHint); !ok {
+       if _, ok := me.tree.DeleteHint(item, me.PathHint); !ok {
                panic(fmt.Sprintf("%#v", key))
        }
        item.state = state
-       if _, ok := me.tree.SetHint(item, &me.pathHint); ok {
+       if _, ok := me.tree.SetHint(item, me.PathHint); ok {
                panic(key)
        }
        me.keys[key] = state
@@ -90,7 +93,7 @@ func (me *PieceRequestOrder) existingItemForKey(key PieceRequestOrderKey) pieceR
 
 func (me *PieceRequestOrder) Delete(key PieceRequestOrderKey) {
        item := me.existingItemForKey(key)
-       if _, ok := me.tree.DeleteHint(item, &me.pathHint); !ok {
+       if _, ok := me.tree.DeleteHint(item, me.PathHint); !ok {
                panic(key)
        }
        delete(me.keys, key)

diff --git a/request-strategy/piece-request-order_test.go b/request-strategy/piece-request-order_test.go
new file mode 100644 (file)
index 0000000..d279ad2
--- /dev/null
+++ b/request-strategy/piece-request-order_test.go
@@ -0,0 +1,74 @@
+package request_strategy
+
+import (
+       "testing"
+
+       "github.com/bradfitz/iter"
+)
+
+func benchmarkPieceRequestOrder(
+       b *testing.B,
+       hintForPiece func(index int) *PieceRequestOrderPathHint,
+       numPieces int,
+) {
+       b.ResetTimer()
+       b.ReportAllocs()
+       for range iter.N(b.N) {
+               pro := NewPieceOrder()
+               state := PieceRequestOrderState{}
+               doPieces := func(m func(PieceRequestOrderKey)) {
+                       for i := range iter.N(numPieces) {
+                               key := PieceRequestOrderKey{
+                                       Index: i,
+                               }
+                               pro.PathHint = hintForPiece(i)
+                               m(key)
+                       }
+               }
+               doPieces(func(key PieceRequestOrderKey) {
+                       pro.Add(key, state)
+               })
+               state.Availability++
+               doPieces(func(key PieceRequestOrderKey) {
+                       pro.Update(key, state)
+               })
+               doPieces(func(key PieceRequestOrderKey) {
+                       state.Priority = piecePriority(key.Index / 4)
+                       pro.Update(key, state)
+               })
+               // state.Priority = 0
+               state.Availability++
+               doPieces(func(key PieceRequestOrderKey) {
+                       pro.Update(key, state)
+               })
+               state.Availability--
+               doPieces(func(key PieceRequestOrderKey) {
+                       pro.Update(key, state)
+               })
+               doPieces(pro.Delete)
+               if pro.Len() != 0 {
+                       b.FailNow()
+               }
+       }
+}
+
+func BenchmarkPieceRequestOrder(b *testing.B) {
+       const numPieces = 2000
+       b.Run("NoPathHints", func(b *testing.B) {
+               benchmarkPieceRequestOrder(b, func(int) *PieceRequestOrderPathHint {
+                       return nil
+               }, numPieces)
+       })
+       b.Run("SharedPathHint", func(b *testing.B) {
+               var pathHint PieceRequestOrderPathHint
+               benchmarkPieceRequestOrder(b, func(int) *PieceRequestOrderPathHint {
+                       return &pathHint
+               }, numPieces)
+       })
+       b.Run("PathHintPerPiece", func(b *testing.B) {
+               pathHints := make([]PieceRequestOrderPathHint, numPieces)
+               benchmarkPieceRequestOrder(b, func(index int) *PieceRequestOrderPathHint {
+                       return &pathHints[index]
+               }, numPieces)
+       })
+}