Repository: allegro/bigcache
Pull request #207 (2020-03-12 06:10:19)

Optimize bytes_queue
Hi there, I try to optimize bytes_queue in two ways:
1. The length is encoded in varint format(the assertion on capacity will fail so I commented them out).
2. When we insert an entry before the head of the queue, and the size of this entry exactly equals to unsued bytes, there is no need to reserve bytes. 

And below are the outputs of test on my Mac:
```
# Mine
2020/03/12 14:49:28 Allocated new queue in 130ns; Capacity: 88
2020/03/12 14:49:28 Allocated new queue in 211.918µs; Capacity: 585000
2020/03/12 14:49:28 Allocated new queue in 394.027µs; Capacity: 1170000
PASS
```

```
# Yours
2020/03/12 14:06:56 Allocated new queue in 156ns; Capacity: 94
2020/03/12 14:06:56 Allocated new queue in 719.26µs; Capacity: 585000
2020/03/12 14:06:56 Allocated new queue in 566.888µs; Capacity: 1170000
PASS
```

PS: It can save some bytes and avoid re-allocation of queue at some time

codecov-io: # [Codecov](https://codecov.io/gh/allegro/bigcache/pull/207?src=pr&el=h1) Report
> :exclamation: No coverage uploaded for pull request base (`master@75a65a8`). [Click here to learn what that means](https://docs.codecov.io/docs/error-reference#section-missing-base-commit).
> The diff coverage is `n/a`.

[![Impacted file tree graph](https://codecov.io/gh/allegro/bigcache/pull/207/graphs/tree.svg?width=650&height=150&src=pr&token=NRx0gXD6he)](https://codecov.io/gh/allegro/bigcache/pull/207?src=pr&el=tree)

```diff
@@            Coverage Diff            @@
##             master     #207   +/-   ##
=========================================
  Coverage          ?   89.18%           
=========================================
  Files             ?       15           
  Lines             ?      703           
  Branches          ?        0           
=========================================
  Hits              ?      627           
  Misses            ?       65           
  Partials          ?       11           
```



------

[Continue to review full report at Codecov](https://codecov.io/gh/allegro/bigcache/pull/207?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/allegro/bigcache/pull/207?src=pr&el=footer). Last update [75a65a8...410d43d](https://codecov.io/gh/allegro/bigcache/pull/207?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

neal-zhu: @janisz Hi, here's the benchmark result:
```
# Mine
2020/03/12 19:02:50 Allocated new queue in 180ns; Capacity: 88
2020/03/12 19:02:50 Allocated new queue in 226.702µs; Capacity: 585000
2020/03/12 19:02:50 Allocated new queue in 389.079µs; Capacity: 1170000
goos: darwin
goarch: amd64
pkg: github.com/allegro/bigcache/v2
BenchmarkWriteToCacheWith1Shard-4                            	 5192714	      1026 ns/op	     596 B/op	       3 allocs/op
BenchmarkWriteToLimitedCacheWithSmallInitSizeAnd1Shard-4     	 8772144	       508 ns/op	     104 B/op	       4 allocs/op
BenchmarkWriteToUnlimitedCacheWithSmallInitSizeAnd1Shard-4   	 1902460	      5424 ns/op	    3623 B/op	       2 allocs/op
BenchmarkWriteToCache/1-shards-4                             	 3431140	      1486 ns/op	     620 B/op	       3 allocs/op
BenchmarkWriteToCache/512-shards-4                           	 9916384	      1135 ns/op	     599 B/op	       3 allocs/op
BenchmarkWriteToCache/1024-shards-4                          	 7211010	       999 ns/op	     618 B/op	       3 allocs/op
BenchmarkWriteToCache/8192-shards-4                          	 6708818	      1065 ns/op	     602 B/op	       3 allocs/op
BenchmarkReadFromCache/1-shards-4                            	13963962	      2549 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCache/512-shards-4                          	 9840069	       828 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCache/1024-shards-4                         	 9384037	       923 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCache/8192-shards-4                         	10724266	      1131 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCacheWithInfo/1-shards-4                    	10171226	      1048 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCacheWithInfo/512-shards-4                  	 8341252	       888 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCacheWithInfo/1024-shards-4                 	10288347	      1135 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCacheWithInfo/8192-shards-4                 	 8065857	       827 ns/op	     271 B/op	       2 allocs/op
BenchmarkIterateOverCache/512-shards-4                       	24373030	       228 ns/op	      20 B/op	       2 allocs/op
BenchmarkIterateOverCache/1024-shards-4                      	22172804	       214 ns/op	      20 B/op	       2 allocs/op
BenchmarkIterateOverCache/8192-shards-4                      	22551939	       220 ns/op	      20 B/op	       2 allocs/op
BenchmarkWriteToCacheWith1024ShardsAndSmallShardInitSize-4   	 5228383	      1452 ns/op	    1108 B/op	       3 allocs/op
BenchmarkReadFromCacheNonExistentKeys/1-shards-4             	36336122	       137 ns/op	       7 B/op	       0 allocs/op
BenchmarkReadFromCacheNonExistentKeys/512-shards-4           	38118368	       141 ns/op	       7 B/op	       0 allocs/op
BenchmarkReadFromCacheNonExistentKeys/1024-shards-4          	36579570	       140 ns/op	       7 B/op	       0 allocs/op
BenchmarkReadFromCacheNonExistentKeys/8192-shards-4          	36496588	       149 ns/op	       7 B/op	       0 allocs/op
BenchmarkFnvHashSum64-4                                      	460839229	        10.1 ns/op	       0 B/op	       0 allocs/op
BenchmarkFnvHashStdLibSum64-4                                	90994177	        67.8 ns/op	      16 B/op	       2 allocs/op
PASS
ok  	github.com/allegro/bigcache/v2	555.615s
PASS
ok  	github.com/allegro/bigcache/v2/queue	0.012s
2020/03/12 19:12:05 Entry not found
2020/03/12 19:12:05 stored "testkey" in cache.
2020/03/12 19:12:05 empty request.
2020/03/12 19:12:05 stored "putKey" in cache.
2020/03/12 19:12:05 Entry not found
2020/03/12 19:12:05 test read error
2020/03/12 19:12:05 invalidDeleteKey not found.
2020/03/12 19:12:05  not found.
2020/03/12 19:12:05 empty request.
2020/03/12 19:12:05 entry is bigger than max shard size
PASS

# Yours
2020/03/12 18:48:16 Allocated new queue in 264.583µs; Capacity: 585000
2020/03/12 18:48:16 Allocated new queue in 182ns; Capacity: 94
2020/03/12 18:48:16 Allocated new queue in 478.836µs; Capacity: 1170000
goos: darwin
goarch: amd64
pkg: github.com/allegro/bigcache/v2
BenchmarkWriteToCacheWith1Shard-4                            	 4990784	      1342 ns/op	     598 B/op	       3 allocs/op
BenchmarkWriteToLimitedCacheWithSmallInitSizeAnd1Shard-4     	 8682642	       566 ns/op	      40 B/op	       3 allocs/op
BenchmarkWriteToUnlimitedCacheWithSmallInitSizeAnd1Shard-4   	 3486128	      8048 ns/op	    3953 B/op	       2 allocs/op
BenchmarkWriteToCache/1-shards-4                             	 3656758	      1755 ns/op	     616 B/op	       3 allocs/op
BenchmarkWriteToCache/512-shards-4                           	 5487960	      1203 ns/op	     595 B/op	       3 allocs/op
BenchmarkWriteToCache/1024-shards-4                          	 7292827	       952 ns/op	     617 B/op	       3 allocs/op
BenchmarkWriteToCache/8192-shards-4                          	 7152934	       986 ns/op	     631 B/op	       3 allocs/op
BenchmarkReadFromCache/1-shards-4                            	13202287	      2494 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCache/512-shards-4                          	 9122005	      1506 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCache/1024-shards-4                         	10188386	       964 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCache/8192-shards-4                         	10101868	      1393 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCacheWithInfo/1-shards-4                    	 8598147	       830 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCacheWithInfo/512-shards-4                  	 9947847	       873 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCacheWithInfo/1024-shards-4                 	 9378534	       900 ns/op	     271 B/op	       2 allocs/op
BenchmarkReadFromCacheWithInfo/8192-shards-4                 	 8794632	       953 ns/op	     271 B/op	       2 allocs/op
BenchmarkIterateOverCache/512-shards-4                       	21350042	       216 ns/op	      20 B/op	       2 allocs/op
BenchmarkIterateOverCache/1024-shards-4                      	20962723	       224 ns/op	      20 B/op	       2 allocs/op
BenchmarkIterateOverCache/8192-shards-4                      	21533272	       205 ns/op	      20 B/op	       2 allocs/op
BenchmarkWriteToCacheWith1024ShardsAndSmallShardInitSize-4   	 4855218	      1543 ns/op	    1190 B/op	       3 allocs/op
BenchmarkReadFromCacheNonExistentKeys/1-shards-4             	30844810	       150 ns/op	       7 B/op	       0 allocs/op
BenchmarkReadFromCacheNonExistentKeys/512-shards-4           	33429462	       139 ns/op	       7 B/op	       0 allocs/op
BenchmarkReadFromCacheNonExistentKeys/1024-shards-4          	32085747	       149 ns/op	       7 B/op	       0 allocs/op
BenchmarkReadFromCacheNonExistentKeys/8192-shards-4          	37587307	       141 ns/op	       7 B/op	       0 allocs/op
BenchmarkFnvHashSum64-4                                      	519146876	         9.40 ns/op	       0 B/op	       0 allocs/op
BenchmarkFnvHashStdLibSum64-4                                	70484605	        64.3 ns/op	      16 B/op	       2 allocs/op
PASS
ok  	github.com/allegro/bigcache/v2	556.285s
PASS
ok  	github.com/allegro/bigcache/v2/queue	0.010s
2020/03/12 18:57:32 Entry not found
2020/03/12 18:57:32 stored "testkey" in cache.
2020/03/12 18:57:32 empty request.
2020/03/12 18:57:32 stored "putKey" in cache.
2020/03/12 18:57:32 Entry not found
2020/03/12 18:57:32 empty request.
2020/03/12 18:57:32 invalidDeleteKey not found.
2020/03/12 18:57:32  not found.
2020/03/12 18:57:32 test read error
2020/03/12 18:57:32 entry is bigger than max shard size
PASS
```

I'm sorry that I'm not familiar with the go benchmark test, so I can not add a new benchmark for the encoding part. But according to the above result, I think using new uvarint encoding is not insufficient.
And It can really reduce the consumption of memory.
neal-zhu: @mxplusb I would not like to lose test coverage too, sir. 
But I think the problem is the old assertions about capacity rely on implementation detail too much, like this [test](https://github.com/allegro/bigcache/blob/master/queue/bytes_queue_test.go#L127).
neal-zhu: Why does the build fail? My pr should have nothing to do with data race I think.
neal-zhu: Greate! I would also like to help you guys with [this issue](https://github.com/allegro/bigcache/issues/204)

Patch:
diff --git a/.github/workflows/build.yml b/.github/workflows/build.yml
index f09f279..95e70d9 100644
--- a/.github/workflows/build.yml
+++ b/.github/workflows/build.yml
@@ -11,7 +11,7 @@ jobs:
       fail-fast: true
       max-parallel: 2
       matrix:
-        go: ["1.12.x", "1.13.x"]
+        go: ["1.13.x", "1.14.x"]
 
     steps:
       - name: Set up Go
diff --git a/queue/bytes_queue.go b/queue/bytes_queue.go
index 0af1861..9619550 100644
--- a/queue/bytes_queue.go
+++ b/queue/bytes_queue.go
@@ -7,13 +7,10 @@ import (
 )
 
 const (
-	// Number of bytes used to keep information about entry size
-	headerEntrySize = 4
+	// Number of bytes to encode 0 in uvarint format
+	minimumHeaderSize = 1
 	// Bytes before left margin are not used. Zero index means element does not exist in queue, useful while reading slice from index
 	leftMarginIndex = 1
-	// Minimum empty blob size in bytes. Empty blob fills space between tail and head in additional memory allocation.
-	// It keeps entries indexes unchanged
-	minimumEmptyBlobSize = 32 + headerEntrySize
 )
 
 var (
@@ -25,6 +22,7 @@ var (
 // BytesQueue is a non-thread safe queue type of fifo based on bytes array.
 // For every push operation index of entry is returned. It can be used to read the entry later
 type BytesQueue struct {
+	full            bool
 	array           []byte
 	capacity        int
 	maxCapacity     int
@@ -41,6 +39,21 @@ type queueError struct {
 	message string
 }
 
+// getUvarintSize returns the number of bytes to encode x in uvarint format
+func getUvarintSize(x uint32) int {
+	if x < 128 {
+		return 1
+	} else if x < 16384 {
+		return 2
+	} else if x < 2097152 {
+		return 3
+	} else if x < 268435456 {
+		return 4
+	} else {
+		return 5
+	}
+}
+
 // NewBytesQueue initialize new bytes queue.
 // Initial capacity is used in bytes array allocation
 // When verbose flag is set then information about memory allocation are printed
@@ -49,7 +62,7 @@ func NewBytesQueue(initialCapacity int, maxCapacity int, verbose bool) *BytesQue
 		array:           make([]byte, initialCapacity),
 		capacity:        initialCapacity,
 		maxCapacity:     maxCapacity,
-		headerBuffer:    make([]byte, headerEntrySize),
+		headerBuffer:    make([]byte, binary.MaxVarintLen32),
 		tail:            leftMarginIndex,
 		head:            leftMarginIndex,
 		rightMargin:     leftMarginIndex,
@@ -71,9 +84,10 @@ func (q *BytesQueue) Reset() {
 // Returns index for pushed data or error if maximum size queue limit is reached.
 func (q *BytesQueue) Push(data []byte) (int, error) {
 	dataLen := len(data)
+	headerEntrySize := getUvarintSize(uint32(dataLen))
 
-	if q.availableSpaceAfterTail() < dataLen+headerEntrySize {
-		if q.availableSpaceBeforeHead() >= dataLen+headerEntrySize {
+	if !q.canInsertAfterTail(dataLen + headerEntrySize) {
+		if q.canInsertBeforeHead(dataLen + headerEntrySize) {
 			q.tail = leftMarginIndex
 		} else if q.capacity+headerEntrySize+dataLen >= q.maxCapacity && q.maxCapacity > 0 {
 			return -1, &queueError{"Full queue. Maximum size limit reached."}
@@ -106,6 +120,7 @@ func (q *BytesQueue) allocateAdditionalMemory(minimum int) {
 		copy(q.array, oldArray[:q.rightMargin])
 
 		if q.tail < q.head {
+			headerEntrySize := getUvarintSize(uint32(q.head - q.tail))
 			emptyBlobLen := q.head - q.tail - headerEntrySize
 			q.push(make([]byte, emptyBlobLen), emptyBlobLen)
 			q.head = leftMarginIndex
@@ -119,7 +134,7 @@ func (q *BytesQueue) allocateAdditionalMemory(minimum int) {
 }
 
 func (q *BytesQueue) push(data []byte, len int) {
-	binary.LittleEndian.PutUint32(q.headerBuffer, uint32(len))
+	headerEntrySize := binary.PutUvarint(q.headerBuffer, uint64(len))
 	q.copy(q.headerBuffer, headerEntrySize)
 
 	q.copy(data, len)
@@ -127,6 +142,9 @@ func (q *BytesQueue) push(data []byte, len int) {
 	if q.tail > q.head {
 		q.rightMargin = q.tail
 	}
+	if q.tail == q.head {
+		q.full = true
+	}
 
 	q.count++
 }
@@ -137,10 +155,11 @@ func (q *BytesQueue) copy(data []byte, len int) {
 
 // Pop reads the oldest entry from queue and moves head pointer to the next one
 func (q *BytesQueue) Pop() ([]byte, error) {
-	data, size, err := q.peek(q.head)
+	data, headerEntrySize, err := q.peek(q.head)
 	if err != nil {
 		return nil, err
 	}
+	size := len(data)
 
 	q.head += headerEntrySize + size
 	q.count--
@@ -199,32 +218,45 @@ func (q *BytesQueue) peekCheckErr(index int) error {
 		return errInvalidIndex
 	}
 
-	if index+headerEntrySize >= len(q.array) {
+	if index >= len(q.array) {
 		return errIndexOutOfBounds
 	}
 	return nil
 }
 
+// peek returns the data from index and the number of bytes to encode the length of the data in uvarint format
 func (q *BytesQueue) peek(index int) ([]byte, int, error) {
 	err := q.peekCheckErr(index)
 	if err != nil {
 		return nil, 0, err
 	}
 
-	blockSize := int(binary.LittleEndian.Uint32(q.array[index : index+headerEntrySize]))
-	return q.array[index+headerEntrySize : index+headerEntrySize+blockSize], blockSize, nil
+	blockSize, n := binary.Uvarint(q.array[index:])
+	return q.array[index+n : index+n+int(blockSize)], n, nil
 }
 
-func (q *BytesQueue) availableSpaceAfterTail() int {
+// canInsertAfterTail returns true if it's possible to insert an entry of size of need after the tail of the queue
+func (q *BytesQueue) canInsertAfterTail(need int) bool {
+	if q.full {
+		return false
+	}
 	if q.tail >= q.head {
-		return q.capacity - q.tail
+		return q.capacity-q.tail >= need
 	}
-	return q.head - q.tail - minimumEmptyBlobSize
+	// 1. there is exactly need bytes between head and tail, so we do not need
+	// to reserve extra space for a potential emtpy entry when re-allco this queeu
+	// 2. still have unused space between tail and head, then we must reserve
+	// at least headerEntrySize bytes so we can put an empty entry
+	return q.head-q.tail == need || q.head-q.tail >= need+minimumHeaderSize
 }
 
-func (q *BytesQueue) availableSpaceBeforeHead() int {
+// canInsertBeforeHead returns true if it's possible to insert an entry of size of need before the head of the queue
+func (q *BytesQueue) canInsertBeforeHead(need int) bool {
+	if q.full {
+		return false
+	}
 	if q.tail >= q.head {
-		return q.head - leftMarginIndex - minimumEmptyBlobSize
+		return q.head-leftMarginIndex == need || q.head-leftMarginIndex >= need+minimumHeaderSize
 	}
-	return q.head - q.tail - minimumEmptyBlobSize
+	return q.head-q.tail == need || q.head-q.tail >= need+minimumHeaderSize
 }


Test patch:
diff --git a/bigcache_test.go b/bigcache_test.go
index cacb2db..8a04060 100644
--- a/bigcache_test.go
+++ b/bigcache_test.go
@@ -426,7 +426,7 @@ func TestCacheCapacity(t *testing.T) {
 
 	// then
 	assertEqual(t, keys, cache.Len())
-	assertEqual(t, 81920, cache.Capacity())
+	assertEqual(t, 40960, cache.Capacity())
 }
 
 func TestCacheStats(t *testing.T) {
diff --git a/queue/bytes_queue_test.go b/queue/bytes_queue_test.go
index 48b0853..eb29cef 100644
--- a/queue/bytes_queue_test.go
+++ b/queue/bytes_queue_test.go
@@ -145,13 +145,13 @@ func TestAllocateAdditionalSpaceForInsufficientFreeFragmentedSpaceWhereHeadIsBef
 	queue := NewBytesQueue(25, 0, false)
 
 	// when
-	queue.Push(blob('a', 3)) // header + entry + left margin = 8 bytes
-	queue.Push(blob('b', 6)) // additional 10 bytes
-	queue.Pop()              // space freed, 7 bytes available at the beginning
-	queue.Push(blob('c', 6)) // 10 bytes needed, 14 available but not in one segment, allocate additional memory
+	queue.Push(blob('a', 3)) // header + entry + left margin = 5 bytes
+	queue.Push(blob('b', 6)) // additional 7 bytes
+	queue.Pop()              // space freed, 4 bytes available at the beginning
+	queue.Push(blob('c', 6)) // 7 bytes needed, 13 bytes available at the tail
 
 	// then
-	assertEqual(t, 50, queue.Capacity())
+	assertEqual(t, 25, queue.Capacity())
 	assertEqual(t, blob('b', 6), pop(queue))
 	assertEqual(t, blob('c', 6), pop(queue))
 }
@@ -163,13 +163,13 @@ func TestUnchangedEntriesIndexesAfterAdditionalMemoryAllocationWhereHeadIsBefore
 	queue := NewBytesQueue(25, 0, false)
 
 	// when
-	queue.Push(blob('a', 3))                   // header + entry + left margin = 8 bytes
-	index, _ := queue.Push(blob('b', 6))       // additional 10 bytes
-	queue.Pop()                                // space freed, 7 bytes available at the beginning
-	newestIndex, _ := queue.Push(blob('c', 6)) // 10 bytes needed, 14 available but not in one segment, allocate additional memory
+	queue.Push(blob('a', 3))                   // header + entry + left margin = 5 bytes
+	index, _ := queue.Push(blob('b', 6))       // additional 7 bytes
+	queue.Pop()                                // space freed, 4 bytes available at the beginning
+	newestIndex, _ := queue.Push(blob('c', 6)) // 7 bytes needed, 13 available at the tail
 
 	// then
-	assertEqual(t, 50, queue.Capacity())
+	assertEqual(t, 25, queue.Capacity())
 	assertEqual(t, blob('b', 6), get(queue, index))
 	assertEqual(t, blob('c', 6), get(queue, newestIndex))
 }
@@ -181,11 +181,11 @@ func TestAllocateAdditionalSpaceForInsufficientFreeFragmentedSpaceWhereTailIsBef
 	queue := NewBytesQueue(100, 0, false)
 
 	// when
-	queue.Push(blob('a', 70)) // header + entry + left margin = 75 bytes
-	queue.Push(blob('b', 10)) // 75 + 10 + 4 = 89 bytes
+	queue.Push(blob('a', 70)) // header + entry + left margin = 72 bytes
+	queue.Push(blob('b', 10)) // 72 + 10 + 1 = 83 bytes
 	queue.Pop()               // space freed at the beginning
-	queue.Push(blob('c', 30)) // 34 bytes used at the beginning, tail pointer is before head pointer
-	queue.Push(blob('d', 40)) // 44 bytes needed but no available in one segment, allocate new memory
+	queue.Push(blob('c', 30)) // 31 bytes used at the beginning, tail pointer is before head pointer
+	queue.Push(blob('d', 40)) // 41 bytes needed but no available in one segment, allocate new memory
 
 	// then
 	assertEqual(t, 200, queue.Capacity())
@@ -193,7 +193,7 @@ func TestAllocateAdditionalSpaceForInsufficientFreeFragmentedSpaceWhereTailIsBef
 	// empty blob fills space between tail and head,
 	// created when additional memory was allocated,
 	// it keeps current entries indexes unchanged
-	assertEqual(t, blob(0, 36), pop(queue))
+	assertEqual(t, blob(0, 39), pop(queue))
 	assertEqual(t, blob('b', 10), pop(queue))
 	assertEqual(t, blob('d', 40), pop(queue))
 }
@@ -205,11 +205,11 @@ func TestUnchangedEntriesIndexesAfterAdditionalMemoryAllocationWhereTailIsBefore
 	queue := NewBytesQueue(100, 0, false)
 
 	// when
-	queue.Push(blob('a', 70))                   // header + entry + left margin = 75 bytes
-	index, _ := queue.Push(blob('b', 10))       // 75 + 10 + 4 = 89 bytes
+	queue.Push(blob('a', 70))                   // header + entry + left margin = 72 bytes
+	index, _ := queue.Push(blob('b', 10))       // 72 + 10 + 1 = 83 bytes
 	queue.Pop()                                 // space freed at the beginning
-	queue.Push(blob('c', 30))                   // 34 bytes used at the beginning, tail pointer is before head pointer
-	newestIndex, _ := queue.Push(blob('d', 40)) // 44 bytes needed but no available in one segment, allocate new memory
+	queue.Push(blob('c', 30))                   // 31 bytes used at the beginning, tail pointer is before head pointer
+	newestIndex, _ := queue.Push(blob('d', 40)) // 41 bytes needed but no available in one segment, allocate new memory
 
 	// then
 	assertEqual(t, 200, queue.Capacity())
@@ -225,10 +225,10 @@ func TestAllocateAdditionalSpaceForValueBiggerThanInitQueue(t *testing.T) {
 
 	// when
 	queue.Push(blob('a', 100))
-
 	// then
 	assertEqual(t, blob('a', 100), pop(queue))
-	assertEqual(t, 230, queue.Capacity())
+	// 224 = (101 + 11) * 2
+	assertEqual(t, 224, queue.Capacity())
 }
 
 func TestAllocateAdditionalSpaceForValueBiggerThanQueue(t *testing.T) {
@@ -246,7 +246,8 @@ func TestAllocateAdditionalSpaceForValueBiggerThanQueue(t *testing.T) {
 	queue.Pop()
 	queue.Pop()
 	assertEqual(t, make([]byte, 100), pop(queue))
-	assertEqual(t, 250, queue.Capacity())
+	// 244 = (101 + 21) * 2
+	assertEqual(t, 244, queue.Capacity())
 }
 
 func TestPopWholeQueue(t *testing.T) {
@@ -343,7 +344,7 @@ func TestMaxSizeLimit(t *testing.T) {
 	queue.Push(blob('a', 25))
 	queue.Push(blob('b', 5))
 	capacity := queue.Capacity()
-	_, err := queue.Push(blob('c', 15))
+	_, err := queue.Push(blob('c', 20))
 
 	// then
 	assertEqual(t, 50, capacity)