Repository: quic-go/quic-go
Pull request #4584 (2024-07-18 23:46:31)

ackhandler: optimize received packet tracking
And once again, using a simple slice (and a bunch of `copy`s) turns out to be significantly faster than the textbook data structure:
```
HistoryReceiveSequentialPackets-16            2.99ns ± 2%    2.50ns ± 2%  -16.64%  (p=0.008 n=5+5)
HistoryReceiveCommonCase-16                   3.25ns ± 2%    2.74ns ± 3%  -15.62%  (p=0.008 n=5+5)
HistoryReceiveSequentialPacketsWithGaps-16    12.5ns ± 1%     9.7ns ± 3%  -22.84%  (p=0.008 n=5+5)
HistoryReceiveReversePacketsWithGaps-16       48.3ns ± 2%    35.8ns ± 1%  -25.92%  (p=0.008 n=5+5)
HistoryIsDuplicate-16                         16.6ns ± 2%     8.3ns ± 1%  -49.80%  (p=0.008 n=5+5)
```

codecov[bot]: ## [Codecov](https://app.codecov.io/gh/quic-go/quic-go/pull/4584?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 85.05%. Comparing base [(`7825250`)](https://app.codecov.io/gh/quic-go/quic-go/commit/7825250d3fd53afde42f09171979a95dc6802e37?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go) to head [(`2023f18`)](https://app.codecov.io/gh/quic-go/quic-go/commit/2023f18c32790c5628da29a4a1ed989e372265ed?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go).

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##           master    #4584      +/-   ##
==========================================
+ Coverage   85.04%   85.05%   +0.01%     
==========================================
  Files         154      154              
  Lines       14874    14878       +4     
==========================================
+ Hits        12649    12654       +5     
+ Misses       1716     1714       -2     
- Partials      509      510       +1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/quic-go/quic-go/pull/4584?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go).

marten-seemann: Note to self: this code should make extensive use of the slices package. Ideally, we don’t copy elements around by hand at all.
marten-seemann: The `slices` package is quite neat! I was able to remove all instances of `copy` in [9d3d0a0](https://github.com/quic-go/quic-go/pull/4584/commits/9d3d0a076a957a7d15e35a3d5a4b28264ebfef6d).

However, it doesn't perform as well as simply using `copy`. It's still better than using a linked list though (and is even faster in what I - very crudely - declared to be the common case), so I don't feel very motivated to dig into this at this point.
```
name                                        old time/op    new time/op    delta
HistoryReceiveSequentialPackets-16            2.99ns ± 2%    2.18ns ± 1%  -27.06%  (p=0.008 n=5+5)
HistoryReceiveCommonCase-16                   3.25ns ± 2%    2.43ns ± 1%  -25.32%  (p=0.008 n=5+5)
HistoryReceiveSequentialPacketsWithGaps-16    12.5ns ± 1%    12.1ns ± 1%   -3.50%  (p=0.008 n=5+5)
HistoryReceiveReversePacketsWithGaps-16       48.3ns ± 2%    38.5ns ± 1%  -20.44%  (p=0.008 n=5+5)
HistoryIsDuplicate-16                         16.6ns ± 2%     7.9ns ± 1%  -52.44%  (p=0.008 n=5+5)
```

Patch:
diff --git a/internal/ackhandler/received_packet_history.go b/internal/ackhandler/received_packet_history.go
index 3143bfe1..f9feae1d 100644
--- a/internal/ackhandler/received_packet_history.go
+++ b/internal/ackhandler/received_packet_history.go
@@ -1,10 +1,9 @@
 package ackhandler
 
 import (
-	"sync"
+	"slices"
 
 	"github.com/quic-go/quic-go/internal/protocol"
-	list "github.com/quic-go/quic-go/internal/utils/linkedlist"
 	"github.com/quic-go/quic-go/internal/wire"
 )
 
@@ -14,25 +13,17 @@ type interval struct {
 	End   protocol.PacketNumber
 }
 
-var intervalElementPool sync.Pool
-
-func init() {
-	intervalElementPool = *list.NewPool[interval]()
-}
-
 // The receivedPacketHistory stores if a packet number has already been received.
 // It generates ACK ranges which can be used to assemble an ACK frame.
 // It does not store packet contents.
 type receivedPacketHistory struct {
-	ranges *list.List[interval]
+	ranges []interval // maximum length: protocol.MaxNumAckRanges
 
 	deletedBelow protocol.PacketNumber
 }
 
 func newReceivedPacketHistory() *receivedPacketHistory {
-	return &receivedPacketHistory{
-		ranges: list.NewWithPool[interval](&intervalElementPool),
-	}
+	return &receivedPacketHistory{}
 }
 
 // ReceivedPacket registers a packet with PacketNumber p and updates the ranges
@@ -41,58 +32,54 @@ func (h *receivedPacketHistory) ReceivedPacket(p protocol.PacketNumber) bool /*
 	if p < h.deletedBelow {
 		return false
 	}
+
 	isNew := h.addToRanges(p)
-	h.maybeDeleteOldRanges()
+	// Delete old ranges, if we're tracking too many of them.
+	// This is a DoS defense against a peer that sends us too many gaps.
+	if len(h.ranges) > protocol.MaxNumAckRanges {
+		h.ranges = slices.Delete(h.ranges, 0, len(h.ranges)-protocol.MaxNumAckRanges)
+	}
 	return isNew
 }
 
 func (h *receivedPacketHistory) addToRanges(p protocol.PacketNumber) bool /* is a new packet (and not a duplicate / delayed packet) */ {
-	if h.ranges.Len() == 0 {
-		h.ranges.PushBack(interval{Start: p, End: p})
+	if len(h.ranges) == 0 {
+		h.ranges = append(h.ranges, interval{Start: p, End: p})
 		return true
 	}
 
-	for el := h.ranges.Back(); el != nil; el = el.Prev() {
+	for i := len(h.ranges) - 1; i >= 0; i-- {
 		// p already included in an existing range. Nothing to do here
-		if p >= el.Value.Start && p <= el.Value.End {
+		if p >= h.ranges[i].Start && p <= h.ranges[i].End {
 			return false
 		}
 
-		if el.Value.End == p-1 { // extend a range at the end
-			el.Value.End = p
+		if h.ranges[i].End == p-1 { // extend a range at the end
+			h.ranges[i].End = p
 			return true
 		}
-		if el.Value.Start == p+1 { // extend a range at the beginning
-			el.Value.Start = p
+		if h.ranges[i].Start == p+1 { // extend a range at the beginning
+			h.ranges[i].Start = p
 
-			prev := el.Prev()
-			if prev != nil && prev.Value.End+1 == el.Value.Start { // merge two ranges
-				prev.Value.End = el.Value.End
-				h.ranges.Remove(el)
+			if i > 0 && h.ranges[i-1].End+1 == h.ranges[i].Start { // merge two ranges
+				h.ranges[i-1].End = h.ranges[i].End
+				h.ranges = slices.Delete(h.ranges, i, i+1)
 			}
 			return true
 		}
 
-		// create a new range at the end
-		if p > el.Value.End {
-			h.ranges.InsertAfter(interval{Start: p, End: p}, el)
+		// create a new range after the current one
+		if p > h.ranges[i].End {
+			h.ranges = slices.Insert(h.ranges, i+1, interval{Start: p, End: p})
 			return true
 		}
 	}
 
 	// create a new range at the beginning
-	h.ranges.InsertBefore(interval{Start: p, End: p}, h.ranges.Front())
+	h.ranges = slices.Insert(h.ranges, 0, interval{Start: p, End: p})
 	return true
 }
 
-// Delete old ranges, if we're tracking more than 500 of them.
-// This is a DoS defense against a peer that sends us too many gaps.
-func (h *receivedPacketHistory) maybeDeleteOldRanges() {
-	for h.ranges.Len() > protocol.MaxNumAckRanges {
-		h.ranges.Remove(h.ranges.Front())
-	}
-}
-
 // DeleteBelow deletes all entries below (but not including) p
 func (h *receivedPacketHistory) DeleteBelow(p protocol.PacketNumber) {
 	if p < h.deletedBelow {
@@ -100,37 +87,39 @@ func (h *receivedPacketHistory) DeleteBelow(p protocol.PacketNumber) {
 	}
 	h.deletedBelow = p
 
-	nextEl := h.ranges.Front()
-	for el := h.ranges.Front(); nextEl != nil; el = nextEl {
-		nextEl = el.Next()
+	if len(h.ranges) == 0 {
+		return
+	}
 
-		if el.Value.End < p { // delete a whole range
-			h.ranges.Remove(el)
-		} else if p > el.Value.Start && p <= el.Value.End {
-			el.Value.Start = p
-			return
+	idx := -1
+	for i := 0; i < len(h.ranges); i++ {
+		if h.ranges[i].End < p { // delete a whole range
+			idx = i
+		} else if p > h.ranges[i].Start && p <= h.ranges[i].End {
+			h.ranges[i].Start = p
+			break
 		} else { // no ranges affected. Nothing to do
-			return
+			break
 		}
 	}
+	if idx >= 0 {
+		h.ranges = slices.Delete(h.ranges, 0, idx+1)
+	}
 }
 
 // AppendAckRanges appends to a slice of all AckRanges that can be used in an AckFrame
 func (h *receivedPacketHistory) AppendAckRanges(ackRanges []wire.AckRange) []wire.AckRange {
-	if h.ranges.Len() > 0 {
-		for el := h.ranges.Back(); el != nil; el = el.Prev() {
-			ackRanges = append(ackRanges, wire.AckRange{Smallest: el.Value.Start, Largest: el.Value.End})
-		}
+	for i := len(h.ranges) - 1; i >= 0; i-- {
+		ackRanges = append(ackRanges, wire.AckRange{Smallest: h.ranges[i].Start, Largest: h.ranges[i].End})
 	}
 	return ackRanges
 }
 
 func (h *receivedPacketHistory) GetHighestAckRange() wire.AckRange {
 	ackRange := wire.AckRange{}
-	if h.ranges.Len() > 0 {
-		r := h.ranges.Back().Value
-		ackRange.Smallest = r.Start
-		ackRange.Largest = r.End
+	if len(h.ranges) > 0 {
+		ackRange.Smallest = h.ranges[len(h.ranges)-1].Start
+		ackRange.Largest = h.ranges[len(h.ranges)-1].End
 	}
 	return ackRange
 }
@@ -139,11 +128,12 @@ func (h *receivedPacketHistory) IsPotentiallyDuplicate(p protocol.PacketNumber)
 	if p < h.deletedBelow {
 		return true
 	}
-	for el := h.ranges.Back(); el != nil; el = el.Prev() {
-		if p > el.Value.End {
+	// Iterating over the slices is faster than using a binary search (using slices.BinarySearchFunc).
+	for i := len(h.ranges) - 1; i >= 0; i-- {
+		if p > h.ranges[i].End {
 			return false
 		}
-		if p <= el.Value.End && p >= el.Value.Start {
+		if p <= h.ranges[i].End && p >= h.ranges[i].Start {
 			return true
 		}
 	}
diff --git a/internal/handshake/token_generator.go b/internal/handshake/token_generator.go
index 2d91e6b2..84e58cfc 100644
--- a/internal/handshake/token_generator.go
+++ b/internal/handshake/token_generator.go
@@ -46,7 +46,7 @@ type TokenGenerator struct {
 
 // NewTokenGenerator initializes a new TokenGenerator
 func NewTokenGenerator(key TokenProtectorKey) *TokenGenerator {
-	return &TokenGenerator{tokenProtector: newTokenProtector(key)}
+	return &TokenGenerator{tokenProtector: *newTokenProtector(key)}
 }
 
 // NewRetryToken generates a new token for a Retry for a given source address
diff --git a/internal/handshake/token_protector.go b/internal/handshake/token_protector.go
index f3a99e41..15779189 100644
--- a/internal/handshake/token_protector.go
+++ b/internal/handshake/token_protector.go
@@ -14,28 +14,20 @@ import (
 // TokenProtectorKey is the key used to encrypt both Retry and session resumption tokens.
 type TokenProtectorKey [32]byte
 
-// TokenProtector is used to create and verify a token
-type tokenProtector interface {
-	// NewToken creates a new token
-	NewToken([]byte) ([]byte, error)
-	// DecodeToken decodes a token
-	DecodeToken([]byte) ([]byte, error)
-}
-
 const tokenNonceSize = 32
 
 // tokenProtector is used to create and verify a token
-type tokenProtectorImpl struct {
+type tokenProtector struct {
 	key TokenProtectorKey
 }
 
 // newTokenProtector creates a source for source address tokens
-func newTokenProtector(key TokenProtectorKey) tokenProtector {
-	return &tokenProtectorImpl{key: key}
+func newTokenProtector(key TokenProtectorKey) *tokenProtector {
+	return &tokenProtector{key: key}
 }
 
 // NewToken encodes data into a new token.
-func (s *tokenProtectorImpl) NewToken(data []byte) ([]byte, error) {
+func (s *tokenProtector) NewToken(data []byte) ([]byte, error) {
 	var nonce [tokenNonceSize]byte
 	if _, err := rand.Read(nonce[:]); err != nil {
 		return nil, err
@@ -48,7 +40,7 @@ func (s *tokenProtectorImpl) NewToken(data []byte) ([]byte, error) {
 }
 
 // DecodeToken decodes a token.
-func (s *tokenProtectorImpl) DecodeToken(p []byte) ([]byte, error) {
+func (s *tokenProtector) DecodeToken(p []byte) ([]byte, error) {
 	if len(p) < tokenNonceSize {
 		return nil, fmt.Errorf("token too short: %d", len(p))
 	}
@@ -60,7 +52,7 @@ func (s *tokenProtectorImpl) DecodeToken(p []byte) ([]byte, error) {
 	return aead.Open(nil, aeadNonce, p[tokenNonceSize:], nil)
 }
 
-func (s *tokenProtectorImpl) createAEAD(nonce []byte) (cipher.AEAD, []byte, error) {
+func (s *tokenProtector) createAEAD(nonce []byte) (cipher.AEAD, []byte, error) {
 	h := hkdf.New(sha256.New, s.key[:], nonce, []byte("quic-go token source"))
 	key := make([]byte, 32) // use a 32 byte key, in order to select AES-256
 	if _, err := io.ReadFull(h, key); err != nil {


Test patch:
diff --git a/internal/ackhandler/received_packet_history_test.go b/internal/ackhandler/received_packet_history_test.go
index af6385be..1e21e5b2 100644
--- a/internal/ackhandler/received_packet_history_test.go
+++ b/internal/ackhandler/received_packet_history_test.go
@@ -4,6 +4,7 @@ import (
 	"fmt"
 	"math/rand"
 	"sort"
+	"testing"
 
 	"github.com/quic-go/quic-go/internal/protocol"
 	"github.com/quic-go/quic-go/internal/wire"
@@ -22,23 +23,20 @@ var _ = Describe("receivedPacketHistory", func() {
 	Context("ranges", func() {
 		It("adds the first packet", func() {
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 4, End: 4}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 4, End: 4}}))
 		})
 
 		It("doesn't care about duplicate packets", func() {
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
 			Expect(hist.ReceivedPacket(4)).To(BeFalse())
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 4, End: 4}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 4, End: 4}}))
 		})
 
 		It("adds a few consecutive packets", func() {
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
 			Expect(hist.ReceivedPacket(5)).To(BeTrue())
 			Expect(hist.ReceivedPacket(6)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 4, End: 6}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 4, End: 6}}))
 		})
 
 		It("doesn't care about a duplicate packet contained in an existing range", func() {
@@ -46,69 +44,71 @@ var _ = Describe("receivedPacketHistory", func() {
 			Expect(hist.ReceivedPacket(5)).To(BeTrue())
 			Expect(hist.ReceivedPacket(6)).To(BeTrue())
 			Expect(hist.ReceivedPacket(5)).To(BeFalse())
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 4, End: 6}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 4, End: 6}}))
 		})
 
 		It("extends a range at the front", func() {
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
 			Expect(hist.ReceivedPacket(3)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 3, End: 4}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 3, End: 4}}))
 		})
 
 		It("creates a new range when a packet is lost", func() {
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
 			Expect(hist.ReceivedPacket(6)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(2))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 4, End: 4}))
-			Expect(hist.ranges.Back().Value).To(Equal(interval{Start: 6, End: 6}))
+			Expect(hist.ranges).To(Equal([]interval{
+				{Start: 4, End: 4},
+				{Start: 6, End: 6},
+			}))
 		})
 
 		It("creates a new range in between two ranges", func() {
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
 			Expect(hist.ReceivedPacket(10)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(2))
+			Expect(hist.ranges).To(HaveLen(2))
 			Expect(hist.ReceivedPacket(7)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(3))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 4, End: 4}))
-			Expect(hist.ranges.Front().Next().Value).To(Equal(interval{Start: 7, End: 7}))
-			Expect(hist.ranges.Back().Value).To(Equal(interval{Start: 10, End: 10}))
+			Expect(hist.ranges).To(Equal([]interval{
+				{Start: 4, End: 4},
+				{Start: 7, End: 7},
+				{Start: 10, End: 10},
+			}))
 		})
 
 		It("creates a new range before an existing range for a belated packet", func() {
 			Expect(hist.ReceivedPacket(6)).To(BeTrue())
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(2))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 4, End: 4}))
-			Expect(hist.ranges.Back().Value).To(Equal(interval{Start: 6, End: 6}))
+			Expect(hist.ranges).To(Equal([]interval{
+				{Start: 4, End: 4},
+				{Start: 6, End: 6},
+			}))
 		})
 
 		It("extends a previous range at the end", func() {
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
 			Expect(hist.ReceivedPacket(7)).To(BeTrue())
 			Expect(hist.ReceivedPacket(5)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(2))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 4, End: 5}))
-			Expect(hist.ranges.Back().Value).To(Equal(interval{Start: 7, End: 7}))
+			Expect(hist.ranges).To(Equal([]interval{
+				{Start: 4, End: 5},
+				{Start: 7, End: 7},
+			}))
 		})
 
 		It("extends a range at the front", func() {
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
 			Expect(hist.ReceivedPacket(7)).To(BeTrue())
 			Expect(hist.ReceivedPacket(6)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(2))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 4, End: 4}))
-			Expect(hist.ranges.Back().Value).To(Equal(interval{Start: 6, End: 7}))
+			Expect(hist.ranges).To(Equal([]interval{
+				{Start: 4, End: 4},
+				{Start: 6, End: 7},
+			}))
 		})
 
 		It("closes a range", func() {
 			Expect(hist.ReceivedPacket(6)).To(BeTrue())
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(2))
+			Expect(hist.ranges).To(HaveLen(2))
 			Expect(hist.ReceivedPacket(5)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 4, End: 6}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 4, End: 6}}))
 		})
 
 		It("closes a range in the middle", func() {
@@ -116,19 +116,20 @@ var _ = Describe("receivedPacketHistory", func() {
 			Expect(hist.ReceivedPacket(10)).To(BeTrue())
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
 			Expect(hist.ReceivedPacket(6)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(4))
+			Expect(hist.ranges).To(HaveLen(4))
 			Expect(hist.ReceivedPacket(5)).To(BeTrue())
-			Expect(hist.ranges.Len()).To(Equal(3))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 1, End: 1}))
-			Expect(hist.ranges.Front().Next().Value).To(Equal(interval{Start: 4, End: 6}))
-			Expect(hist.ranges.Back().Value).To(Equal(interval{Start: 10, End: 10}))
+			Expect(hist.ranges).To(Equal([]interval{
+				{Start: 1, End: 1},
+				{Start: 4, End: 6},
+				{Start: 10, End: 10},
+			}))
 		})
 	})
 
 	Context("deleting", func() {
 		It("does nothing when the history is empty", func() {
 			hist.DeleteBelow(5)
-			Expect(hist.ranges.Len()).To(BeZero())
+			Expect(hist.ranges).To(BeEmpty())
 		})
 
 		It("deletes a range", func() {
@@ -136,8 +137,7 @@ var _ = Describe("receivedPacketHistory", func() {
 			Expect(hist.ReceivedPacket(5)).To(BeTrue())
 			Expect(hist.ReceivedPacket(10)).To(BeTrue())
 			hist.DeleteBelow(6)
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 10, End: 10}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 10, End: 10}}))
 		})
 
 		It("deletes multiple ranges", func() {
@@ -145,8 +145,7 @@ var _ = Describe("receivedPacketHistory", func() {
 			Expect(hist.ReceivedPacket(5)).To(BeTrue())
 			Expect(hist.ReceivedPacket(10)).To(BeTrue())
 			hist.DeleteBelow(8)
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 10, End: 10}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 10, End: 10}}))
 		})
 
 		It("adjusts a range, if packets are delete from an existing range", func() {
@@ -156,8 +155,7 @@ var _ = Describe("receivedPacketHistory", func() {
 			Expect(hist.ReceivedPacket(6)).To(BeTrue())
 			Expect(hist.ReceivedPacket(7)).To(BeTrue())
 			hist.DeleteBelow(5)
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 5, End: 7}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 5, End: 7}}))
 		})
 
 		It("adjusts a range, if only one packet remains in the range", func() {
@@ -165,16 +163,16 @@ var _ = Describe("receivedPacketHistory", func() {
 			Expect(hist.ReceivedPacket(5)).To(BeTrue())
 			Expect(hist.ReceivedPacket(10)).To(BeTrue())
 			hist.DeleteBelow(5)
-			Expect(hist.ranges.Len()).To(Equal(2))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 5, End: 5}))
-			Expect(hist.ranges.Back().Value).To(Equal(interval{Start: 10, End: 10}))
+			Expect(hist.ranges).To(Equal([]interval{
+				{Start: 5, End: 5},
+				{Start: 10, End: 10},
+			}))
 		})
 
 		It("keeps a one-packet range, if deleting up to the packet directly below", func() {
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
 			hist.DeleteBelow(4)
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 4, End: 4}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 4, End: 4}}))
 		})
 
 		It("doesn't add delayed packets below deleted ranges", func() {
@@ -182,23 +180,21 @@ var _ = Describe("receivedPacketHistory", func() {
 			Expect(hist.ReceivedPacket(5)).To(BeTrue())
 			Expect(hist.ReceivedPacket(6)).To(BeTrue())
 			hist.DeleteBelow(5)
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 5, End: 6}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 5, End: 6}}))
 			Expect(hist.ReceivedPacket(2)).To(BeFalse())
-			Expect(hist.ranges.Len()).To(Equal(1))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 5, End: 6}))
+			Expect(hist.ranges).To(Equal([]interval{{Start: 5, End: 6}}))
 		})
 
 		It("doesn't create more than MaxNumAckRanges ranges", func() {
 			for i := protocol.PacketNumber(0); i < protocol.MaxNumAckRanges; i++ {
 				Expect(hist.ReceivedPacket(2 * i)).To(BeTrue())
 			}
-			Expect(hist.ranges.Len()).To(Equal(protocol.MaxNumAckRanges))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 0, End: 0}))
+			Expect(hist.ranges).To(HaveLen(protocol.MaxNumAckRanges))
+			Expect(hist.ranges[0]).To(Equal(interval{Start: 0, End: 0}))
 			hist.ReceivedPacket(2*protocol.MaxNumAckRanges + 1000)
 			// check that the oldest ACK range was deleted
-			Expect(hist.ranges.Len()).To(Equal(protocol.MaxNumAckRanges))
-			Expect(hist.ranges.Front().Value).To(Equal(interval{Start: 2, End: 2}))
+			Expect(hist.ranges).To(HaveLen(protocol.MaxNumAckRanges))
+			Expect(hist.ranges[0]).To(Equal(interval{Start: 2, End: 2}))
 		})
 	})
 
@@ -211,17 +207,17 @@ var _ = Describe("receivedPacketHistory", func() {
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
 			Expect(hist.ReceivedPacket(5)).To(BeTrue())
 			ackRanges := hist.AppendAckRanges(nil)
-			Expect(ackRanges).To(HaveLen(1))
-			Expect(ackRanges[0]).To(Equal(wire.AckRange{Smallest: 4, Largest: 5}))
+			Expect(ackRanges).To(Equal([]wire.AckRange{{Smallest: 4, Largest: 5}}))
 		})
 
 		It("appends ACK ranges", func() {
 			Expect(hist.ReceivedPacket(4)).To(BeTrue())
 			Expect(hist.ReceivedPacket(5)).To(BeTrue())
 			ackRanges := hist.AppendAckRanges([]wire.AckRange{{Smallest: 1, Largest: 2}})
-			Expect(ackRanges).To(HaveLen(2))
-			Expect(ackRanges[0]).To(Equal(wire.AckRange{Smallest: 1, Largest: 2}))
-			Expect(ackRanges[1]).To(Equal(wire.AckRange{Smallest: 4, Largest: 5}))
+			Expect(ackRanges).To(Equal([]wire.AckRange{
+				{Smallest: 1, Largest: 2},
+				{Smallest: 4, Largest: 5},
+			}))
 		})
 
 		It("gets multiple ACK ranges", func() {
@@ -233,10 +229,11 @@ var _ = Describe("receivedPacketHistory", func() {
 			Expect(hist.ReceivedPacket(10)).To(BeTrue())
 			Expect(hist.ReceivedPacket(2)).To(BeTrue())
 			ackRanges := hist.AppendAckRanges(nil)
-			Expect(ackRanges).To(HaveLen(3))
-			Expect(ackRanges[0]).To(Equal(wire.AckRange{Smallest: 10, Largest: 11}))
-			Expect(ackRanges[1]).To(Equal(wire.AckRange{Smallest: 4, Largest: 6}))
-			Expect(ackRanges[2]).To(Equal(wire.AckRange{Smallest: 1, Largest: 2}))
+			Expect(ackRanges).To(Equal([]wire.AckRange{
+				{Smallest: 10, Largest: 11},
+				{Smallest: 4, Largest: 6},
+				{Smallest: 1, Largest: 2},
+			}))
 		})
 	})
 
@@ -361,3 +358,55 @@ var _ = Describe("receivedPacketHistory", func() {
 		})
 	})
 })
+
+func BenchmarkHistoryReceiveSequentialPackets(b *testing.B) {
+	hist := newReceivedPacketHistory()
+	for i := 0; i < b.N; i++ {
+		hist.ReceivedPacket(protocol.PacketNumber(i))
+	}
+}
+
+// Packets are received sequentially, with occasional gaps
+func BenchmarkHistoryReceiveCommonCase(b *testing.B) {
+	hist := newReceivedPacketHistory()
+	var pn protocol.PacketNumber
+	for i := 0; i < b.N; i++ {
+		hist.ReceivedPacket(pn)
+		pn++
+		if i%2000 == 0 {
+			pn += 4
+		}
+	}
+}
+
+func BenchmarkHistoryReceiveSequentialPacketsWithGaps(b *testing.B) {
+	hist := newReceivedPacketHistory()
+	for i := 0; i < b.N; i++ {
+		hist.ReceivedPacket(protocol.PacketNumber(2 * i))
+	}
+}
+
+func BenchmarkHistoryReceiveReversePacketsWithGaps(b *testing.B) {
+	hist := newReceivedPacketHistory()
+	for i := 0; i < b.N; i++ {
+		hist.ReceivedPacket(protocol.PacketNumber(2 * (b.N - i)))
+	}
+}
+
+func BenchmarkHistoryIsDuplicate(b *testing.B) {
+	b.ReportAllocs()
+	hist := newReceivedPacketHistory()
+	var pn protocol.PacketNumber
+	for i := 0; i < protocol.MaxNumAckRanges; i++ {
+		for j := 0; j < 5; j++ {
+			hist.ReceivedPacket(pn)
+			pn++
+		}
+		pn += 5 // create a gap
+	}
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		hist.IsPotentiallyDuplicate(protocol.PacketNumber(i) % pn)
+	}
+}
diff --git a/internal/handshake/token_protector_test.go b/internal/handshake/token_protector_test.go
index 74eb1f0c..fb342f3a 100644
--- a/internal/handshake/token_protector_test.go
+++ b/internal/handshake/token_protector_test.go
@@ -8,7 +8,7 @@ import (
 )
 
 var _ = Describe("Token Protector", func() {
-	var tp tokenProtector
+	var tp *tokenProtector
 
 	BeforeEach(func() {
 		var key TokenProtectorKey