Use a generic heap implementation for request selection

diff --git a/go.mod b/go.mod
index c77eb3f9239de0f9400fb9c22fd4f8141e2cef14..3a6f9bfe0ff40e19e667ed8e0ec160ac861487ff 100644 (file)
--- a/go.mod
+++ b/go.mod
@@ -24,6 +24,7 @@ require (
        github.com/anacrolix/tagflag v1.3.0
        github.com/anacrolix/upnp v0.1.3-0.20220123035249-922794e51c96
        github.com/anacrolix/utp v0.1.0
+       github.com/bahlo/generic-list-go v0.2.0
        github.com/bradfitz/iter v0.0.0-20191230175014-e8f45d346db8
        github.com/davecgh/go-spew v1.1.1
        github.com/dustin/go-humanize v1.0.0
@@ -35,12 +36,13 @@ require (
        github.com/google/go-cmp v0.5.6
        github.com/gorilla/websocket v1.4.2
        github.com/jessevdk/go-flags v1.5.0
+       github.com/lispad/go-generics-tools v1.0.0
        github.com/pion/datachannel v1.5.2
        github.com/pion/logging v0.2.2
        github.com/pion/webrtc/v3 v3.1.24-0.20220208053747-94262c1b2b38
        github.com/pkg/errors v0.9.1
        github.com/prometheus/client_golang v1.5.1
-       github.com/stretchr/testify v1.7.0
+       github.com/stretchr/testify v1.7.1
        github.com/tidwall/btree v0.7.2-0.20211211132910-4215444137fc
        go.etcd.io/bbolt v1.3.6
        golang.org/x/time v0.0.0-20210723032227-1f47c861a9ac
@@ -50,7 +52,6 @@ require (
        github.com/alexflint/go-scalar v1.1.0 // indirect
        github.com/anacrolix/mmsg v1.0.0 // indirect
        github.com/anacrolix/stm v0.3.0 // indirect
-       github.com/bahlo/generic-list-go v0.2.0 // indirect
        github.com/benbjohnson/immutable v0.3.0 // indirect
        github.com/beorn7/perks v1.0.1 // indirect
        github.com/bits-and-blooms/bitset v1.2.0 // indirect
@@ -84,6 +85,7 @@ require (
        github.com/rs/dnscache v0.0.0-20210201191234-295bba877686 // indirect
        github.com/ryszard/goskiplist v0.0.0-20150312221310-2dfbae5fcf46 // indirect
        golang.org/x/crypto v0.0.0-20220131195533-30dcbda58838 // indirect
+       golang.org/x/exp v0.0.0-20220328175248-053ad81199eb // indirect
        golang.org/x/net v0.0.0-20220127200216-cd36cc0744dd // indirect
        golang.org/x/sync v0.0.0-20210220032951-036812b2e83c // indirect
        golang.org/x/sys v0.0.0-20211216021012-1d35b9e2eb4e // indirect

diff --git a/go.sum b/go.sum
index 7cf2d2a2b87b623ec3b783afc418958028dad54d..c4213524c1d5e6d2f035ad731c64d2fca79e66cf 100644 (file)
--- a/go.sum
+++ b/go.sum
@@ -210,6 +210,8 @@ github.com/kr/pty v1.1.1/go.mod h1:pFQYn66WHrOpPYNljwOMqo10TkYh1fy3cYio2l3bCsQ=
 github.com/kr/text v0.1.0/go.mod h1:4Jbv+DJW3UT/LiOwJeYQe1efqtUx/iVham/4vfdArNI=
 github.com/kr/text v0.2.0 h1:5Nx0Ya0ZqY2ygV366QzturHI13Jq95ApcVaJBhpS+AY=
 github.com/kr/text v0.2.0/go.mod h1:eLer722TekiGuMkidMxC/pM04lWEeraHUUmBw8l2grE=
+github.com/lispad/go-generics-tools v1.0.0 h1:pPtt9QERE5sGQfwvLakKe2sjhcNKKsDSnr3939ofj1E=
+github.com/lispad/go-generics-tools v1.0.0/go.mod h1:stn7X24ZIyFvaSyttafq3VlJzGJJJkUtLYdbgi/gopM=
 github.com/matttproud/golang_protobuf_extensions v1.0.1 h1:4hp9jkHxhMHkqkrB3Ix0jegS5sx/RkqARlsWZ6pIwiU=
 github.com/matttproud/golang_protobuf_extensions v1.0.1/go.mod h1:D8He9yQNgCq6Z5Ld7szi9bcBfOoFv/3dc6xSMkL2PC0=
 github.com/modern-go/concurrent v0.0.0-20180228061459-e0a39a4cb421/go.mod h1:6dJC0mAP4ikYIbvyc7fijjWJddQyLn8Ig3JB5CqoB9Q=
@@ -326,8 +328,9 @@ github.com/stretchr/testify v1.3.0/go.mod h1:M5WIy9Dh21IEIfnGCwXGc5bZfKNJtfHm1UV
 github.com/stretchr/testify v1.4.0/go.mod h1:j7eGeouHqKxXV5pUuKE4zz7dFj8WfuZ+81PSLYec5m4=
 github.com/stretchr/testify v1.5.1/go.mod h1:5W2xD1RspED5o8YsWQXVCued0rvSQ+mT+I5cxcmMvtA=
 github.com/stretchr/testify v1.6.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
-github.com/stretchr/testify v1.7.0 h1:nwc3DEeHmmLAfoZucVR881uASk0Mfjw8xYJ99tb5CcY=
 github.com/stretchr/testify v1.7.0/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
+github.com/stretchr/testify v1.7.1 h1:5TQK59W5E3v0r2duFAb7P95B6hEeOyEnHRa8MjYSMTY=
+github.com/stretchr/testify v1.7.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
 github.com/tidwall/btree v0.7.2-0.20211211132910-4215444137fc h1:THtJVe/QBctKEe8kjnXwt7RAlvHNtUjFJOEmgZkN05w=
 github.com/tidwall/btree v0.7.2-0.20211211132910-4215444137fc/go.mod h1:LGm8L/DZjPLmeWGjv5kFrY8dL4uVhMmzmmLYmsObdKE=
 github.com/tinylib/msgp v1.0.2/go.mod h1:+d+yLhGm8mzTaHzB+wgMYrodPfmZrzkirds8fDWklFE=
@@ -352,6 +355,8 @@ golang.org/x/crypto v0.0.0-20211215153901-e495a2d5b3d3/go.mod h1:IxCIyHEi3zRg3s0
 golang.org/x/crypto v0.0.0-20220131195533-30dcbda58838 h1:71vQrMauZZhcTVK6KdYM+rklehEEwb3E+ZhaE5jrPrE=
 golang.org/x/crypto v0.0.0-20220131195533-30dcbda58838/go.mod h1:IxCIyHEi3zRg3s0A5j5BB6A9Jmi73HwBIUl50j+osU4=
 golang.org/x/exp v0.0.0-20190121172915-509febef88a4/go.mod h1:CJ0aWSM057203Lf6IL+f9T1iT9GByDxfZKAQTCR3kQA=
+golang.org/x/exp v0.0.0-20220328175248-053ad81199eb h1:pC9Okm6BVmxEw76PUu0XUbOTQ92JX11hfvqTjAV3qxM=
+golang.org/x/exp v0.0.0-20220328175248-053ad81199eb/go.mod h1:lgLbSvA5ygNOMpwM/9anMpWVlVJ7Z+cHWq/eFuinpGE=
 golang.org/x/lint v0.0.0-20181026193005-c67002cb31c3/go.mod h1:UVdnD1Gm6xHRNCYTkRU2/jEulfH38KcIWyp/GAMgvoE=
 golang.org/x/lint v0.0.0-20190227174305-5b3e6a55c961/go.mod h1:wehouNa3lNwaWXcvxsM5YxQ5yQlVC4a0KAMCusXpPoU=
 golang.org/x/lint v0.0.0-20190301231843-5614ed5bae6f/go.mod h1:UVdnD1Gm6xHRNCYTkRU2/jEulfH38KcIWyp/GAMgvoE=

diff --git a/requesting.go b/requesting.go
index 75bb352edd29ca1d6adfc784024bf9a9294e892b..411fac53c203fb67f7d56dd1f244cf50279f4700 100644 (file)
--- a/requesting.go
+++ b/requesting.go
@@ -1,7 +1,6 @@
 package torrent
 
 import (
-       "container/heap"
        "context"
        "encoding/gob"
        "fmt"
@@ -12,6 +11,7 @@ import (
 
        "github.com/anacrolix/log"
        "github.com/anacrolix/multiless"
+       "github.com/lispad/go-generics-tools/binheap"
 
        request_strategy "github.com/anacrolix/torrent/request-strategy"
 )
@@ -77,8 +77,10 @@ func (p *desiredPeerRequests) Len() int {
 }
 
 func (p *desiredPeerRequests) Less(i, j int) bool {
-       leftRequest := p.requestIndexes[i]
-       rightRequest := p.requestIndexes[j]
+       return p.lessByValue(p.requestIndexes[i], p.requestIndexes[j])
+}
+
+func (p *desiredPeerRequests) lessByValue(leftRequest, rightRequest RequestIndex) bool {
        t := p.peer.t
        leftPieceIndex := t.pieceIndexOfRequestIndex(leftRequest)
        rightPieceIndex := t.pieceIndexOfRequestIndex(rightRequest)
@@ -259,7 +261,7 @@ func (p *Peer) applyRequestState(next desiredRequestState) {
                panic("insufficient write buffer")
        }
        more := true
-       requestHeap := &next.Requests
+       requestHeap := binheap.FromSlice(next.Requests.requestIndexes, next.Requests.lessByValue)
        t := p.t
        originalRequestCount := current.Requests.GetCardinality()
        // We're either here on a timer, or because we ran out of requests. Both are valid reasons to
@@ -269,9 +271,8 @@ func (p *Peer) applyRequestState(next desiredRequestState) {
                        "expected zero existing requests (%v) for update reason %q",
                        originalRequestCount, p.needRequestUpdate))
        }
-       heap.Init(requestHeap)
        for requestHeap.Len() != 0 && maxRequests(current.Requests.GetCardinality()+current.Cancelled.GetCardinality()) < p.nominalMaxRequests() {
-               req := heap.Pop(requestHeap).(RequestIndex)
+               req := requestHeap.Pop()
                existing := t.requestingPeer(req)
                if existing != nil && existing != p {
                        // Don't steal from the poor.