Skip to content

Commit 78cbf3a

Browse files
liangxsxuesenliang
liangxs
and
xuesenliang
authored
Reduce PoolChunk's metadata size: change LongPriorityQueue to IntPriorityQueue (#13504)
Motivation: `LongPriorityQueue[]` is used by `PoolChunk` to store available run information of all page classes. This information (i.e., `handle`) contains page offset, page count, isUsed, isSubpage, and bitmapIdx of subpage. * Handle is inserted to `LongPriorityQueue` and `LongLongHashMap` when some memory is freed back to the chunk. * Handle is removed from `LongPriorityQueue` and `LongLongHashMap` when some memory is allocated. * One Handle can be split to two handles, and two continuous handles can be collapsed to one handle. All the `LongPriorityQueue` operations are only related to page offset and page count. The low 32bit `bitmapIdx` is not used at all. So the high 32bit of handle is enough. Modification: 1) Change `LongPriorityQueue` to `IntPriorityQueue` 2) Store high 32bit handle in `IntPriorityQueue` Result: PoolChunk's metadata is smaller. --------- Co-authored-by: xuesenliang <xuesenliang@tencent.com>
1 parent 1b5a3e9 commit 78cbf3a

3 files changed

Lines changed: 46 additions & 46 deletions

File tree

buffer/src/main/java/io/netty/buffer/LongPriorityQueue.java renamed to buffer/src/main/java/io/netty/buffer/IntPriorityQueue.java

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -21,12 +21,12 @@
2121
* Internal primitive priority queue, used by {@link PoolChunk}.
2222
* The implementation is based on the binary heap, as described in Algorithms by Sedgewick and Wayne.
2323
*/
24-
final class LongPriorityQueue {
24+
final class IntPriorityQueue {
2525
public static final int NO_VALUE = -1;
26-
private long[] array = new long[9];
26+
private int[] array = new int[9];
2727
private int size;
2828

29-
public void offer(long handle) {
29+
public void offer(int handle) {
3030
if (handle == NO_VALUE) {
3131
throw new IllegalArgumentException("The NO_VALUE (" + NO_VALUE + ") cannot be added to the queue.");
3232
}
@@ -39,7 +39,7 @@ public void offer(long handle) {
3939
lift(size);
4040
}
4141

42-
public void remove(long value) {
42+
public void remove(int value) {
4343
for (int i = 1; i <= size; i++) {
4444
if (array[i] == value) {
4545
array[i] = array[size--];
@@ -50,18 +50,18 @@ public void remove(long value) {
5050
}
5151
}
5252

53-
public long peek() {
53+
public int peek() {
5454
if (size == 0) {
5555
return NO_VALUE;
5656
}
5757
return array[1];
5858
}
5959

60-
public long poll() {
60+
public int poll() {
6161
if (size == 0) {
6262
return NO_VALUE;
6363
}
64-
long val = array[1];
64+
int val = array[1];
6565
array[1] = array[size];
6666
array[size] = 0;
6767
size--;
@@ -100,7 +100,7 @@ private boolean subord(int a, int b) {
100100
}
101101

102102
private void swap(int a, int b) {
103-
long value = array[a];
103+
int value = array[a];
104104
array[a] = array[b];
105105
array[b] = value;
106106
}

‎buffer/src/main/java/io/netty/buffer/PoolChunk.java‎

Lines changed: 14 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -157,7 +157,7 @@ final class PoolChunk<T> implements PoolChunkMetric {
157157
/**
158158
* manage all avail runs
159159
*/
160-
private final LongPriorityQueue[] runsAvail;
160+
private final IntPriorityQueue[] runsAvail;
161161

162162
private final ReentrantLock runsAvailLock;
163163

@@ -231,18 +231,19 @@ final class PoolChunk<T> implements PoolChunkMetric {
231231
cachedNioBuffers = null;
232232
}
233233

234-
private static LongPriorityQueue[] newRunsAvailqueueArray(int size) {
235-
LongPriorityQueue[] queueArray = new LongPriorityQueue[size];
234+
private static IntPriorityQueue[] newRunsAvailqueueArray(int size) {
235+
IntPriorityQueue[] queueArray = new IntPriorityQueue[size];
236236
for (int i = 0; i < queueArray.length; i++) {
237-
queueArray[i] = new LongPriorityQueue();
237+
queueArray[i] = new IntPriorityQueue();
238238
}
239239
return queueArray;
240240
}
241241

242242
private void insertAvailRun(int runOffset, int pages, long handle) {
243243
int pageIdxFloor = arena.pages2pageIdxFloor(pages);
244-
LongPriorityQueue queue = runsAvail[pageIdxFloor];
245-
queue.offer(handle);
244+
IntPriorityQueue queue = runsAvail[pageIdxFloor];
245+
assert isRun(handle);
246+
queue.offer((int) (handle >> BITMAP_IDX_BIT_LENGTH));
246247

247248
//insert first page of run
248249
insertAvailRun0(runOffset, handle);
@@ -259,7 +260,7 @@ private void insertAvailRun0(int runOffset, long handle) {
259260

260261
private void removeAvailRun(long handle) {
261262
int pageIdxFloor = arena.pages2pageIdxFloor(runPages(handle));
262-
runsAvail[pageIdxFloor].remove(handle);
263+
runsAvail[pageIdxFloor].remove((int) (handle >> BITMAP_IDX_BIT_LENGTH));
263264
removeAvailRun0(handle);
264265
}
265266

@@ -348,16 +349,15 @@ private long allocateRun(int runSize) {
348349
}
349350

350351
//get run with min offset in this queue
351-
LongPriorityQueue queue = runsAvail[queueIdx];
352+
IntPriorityQueue queue = runsAvail[queueIdx];
352353
long handle = queue.poll();
353-
354-
assert handle != LongPriorityQueue.NO_VALUE && !isUsed(handle) : "invalid handle: " + handle;
354+
assert handle != IntPriorityQueue.NO_VALUE;
355+
handle <<= BITMAP_IDX_BIT_LENGTH;
356+
assert !isUsed(handle) : "invalid handle: " + handle;
355357

356358
removeAvailRun0(handle);
357359

358-
if (handle != -1) {
359-
handle = splitLargeRun(handle, pages);
360-
}
360+
handle = splitLargeRun(handle, pages);
361361

362362
int pinnedSize = runSize(pageShifts, handle);
363363
freeBytes -= pinnedSize;
@@ -397,7 +397,7 @@ private int runFirstBestFit(int pageIdx) {
397397
return arena.nPSizes - 1;
398398
}
399399
for (int i = pageIdx; i < arena.nPSizes; i++) {
400-
LongPriorityQueue queue = runsAvail[i];
400+
IntPriorityQueue queue = runsAvail[i];
401401
if (queue != null && !queue.isEmpty()) {
402402
return i;
403403
}

buffer/src/test/java/io/netty/buffer/LongPriorityQueueTest.java renamed to buffer/src/test/java/io/netty/buffer/IntPriorityQueueTest.java

Lines changed: 24 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -26,14 +26,14 @@
2626
import static org.assertj.core.api.Assertions.assertThat;
2727
import static org.junit.jupiter.api.Assertions.*;
2828

29-
class LongPriorityQueueTest {
29+
class IntPriorityQueueTest {
3030
@Test
3131
public void mustThrowWhenAddingNoValue() {
32-
final LongPriorityQueue pq = new LongPriorityQueue();
32+
final IntPriorityQueue pq = new IntPriorityQueue();
3333
assertThrows(IllegalArgumentException.class, new Executable() {
3434
@Override
3535
public void execute() {
36-
pq.offer(LongPriorityQueue.NO_VALUE);
36+
pq.offer(IntPriorityQueue.NO_VALUE);
3737
}
3838
});
3939
}
@@ -42,26 +42,26 @@ public void execute() {
4242
public void mustReturnValuesInOrder() {
4343
ThreadLocalRandom tlr = ThreadLocalRandom.current();
4444
int initialValues = tlr.nextInt(5, 30);
45-
ArrayList<Long> values = new ArrayList<Long>();
45+
ArrayList<Integer> values = new ArrayList<Integer>();
4646
for (int i = 0; i < initialValues; i++) {
47-
values.add(tlr.nextLong(0, Long.MAX_VALUE));
47+
values.add(tlr.nextInt(0, Integer.MAX_VALUE));
4848
}
49-
LongPriorityQueue pq = new LongPriorityQueue();
49+
IntPriorityQueue pq = new IntPriorityQueue();
5050
assertTrue(pq.isEmpty());
51-
for (Long value : values) {
51+
for (Integer value : values) {
5252
pq.offer(value);
5353
}
5454
Collections.sort(values);
5555
int valuesToRemove = initialValues / 2;
56-
ListIterator<Long> itr = values.listIterator();
56+
ListIterator<Integer> itr = values.listIterator();
5757
for (int i = 0; i < valuesToRemove; i++) {
5858
assertTrue(itr.hasNext());
5959
assertThat(pq.poll()).isEqualTo(itr.next());
6060
itr.remove();
6161
}
6262
int moreValues = tlr.nextInt(5, 30);
6363
for (int i = 0; i < moreValues; i++) {
64-
long value = tlr.nextLong(0, Long.MAX_VALUE);
64+
int value = tlr.nextInt(0, Integer.MAX_VALUE);
6565
pq.offer(value);
6666
values.add(value);
6767
}
@@ -71,54 +71,54 @@ public void mustReturnValuesInOrder() {
7171
assertThat(pq.poll()).isEqualTo(itr.next());
7272
}
7373
assertTrue(pq.isEmpty());
74-
assertThat(pq.poll()).isEqualTo(LongPriorityQueue.NO_VALUE);
74+
assertThat(pq.poll()).isEqualTo(IntPriorityQueue.NO_VALUE);
7575
}
7676

7777
@Test
7878
public void internalRemoveOfAllElements() {
7979
ThreadLocalRandom tlr = ThreadLocalRandom.current();
8080
int initialValues = tlr.nextInt(5, 30);
81-
ArrayList<Long> values = new ArrayList<Long>();
82-
LongPriorityQueue pq = new LongPriorityQueue();
81+
ArrayList<Integer> values = new ArrayList<Integer>();
82+
IntPriorityQueue pq = new IntPriorityQueue();
8383
for (int i = 0; i < initialValues; i++) {
84-
long value = tlr.nextLong(0, Long.MAX_VALUE);
84+
int value = tlr.nextInt(0, Integer.MAX_VALUE);
8585
pq.offer(value);
8686
values.add(value);
8787
}
88-
for (Long value : values) {
88+
for (Integer value : values) {
8989
pq.remove(value);
9090
}
9191
assertTrue(pq.isEmpty());
92-
assertThat(pq.poll()).isEqualTo(LongPriorityQueue.NO_VALUE);
92+
assertThat(pq.poll()).isEqualTo(IntPriorityQueue.NO_VALUE);
9393
}
9494

9595
@Test
9696
public void internalRemoveMustPreserveOrder() {
9797
ThreadLocalRandom tlr = ThreadLocalRandom.current();
9898
int initialValues = tlr.nextInt(1, 30);
99-
ArrayList<Long> values = new ArrayList<Long>();
100-
LongPriorityQueue pq = new LongPriorityQueue();
99+
ArrayList<Integer> values = new ArrayList<Integer>();
100+
IntPriorityQueue pq = new IntPriorityQueue();
101101
for (int i = 0; i < initialValues; i++) {
102-
long value = tlr.nextLong(0, Long.MAX_VALUE);
102+
int value = tlr.nextInt(0, Integer.MAX_VALUE);
103103
pq.offer(value);
104104
values.add(value);
105105
}
106106

107-
long toRemove = values.get(values.size() / 2);
107+
Integer toRemove = values.get(values.size() / 2);
108108
values.remove(toRemove);
109109
pq.remove(toRemove);
110110

111111
Collections.sort(values);
112-
for (Long value : values) {
112+
for (Integer value : values) {
113113
assertThat(pq.poll()).isEqualTo(value);
114114
}
115115
assertTrue(pq.isEmpty());
116-
assertThat(pq.poll()).isEqualTo(LongPriorityQueue.NO_VALUE);
116+
assertThat(pq.poll()).isEqualTo(IntPriorityQueue.NO_VALUE);
117117
}
118118

119119
@Test
120120
public void mustSupportDuplicateValues() {
121-
LongPriorityQueue pq = new LongPriorityQueue();
121+
IntPriorityQueue pq = new IntPriorityQueue();
122122
pq.offer(10);
123123
pq.offer(5);
124124
pq.offer(6);
@@ -141,7 +141,7 @@ public void mustSupportDuplicateValues() {
141141
assertThat(pq.poll()).isEqualTo(10);
142142
assertThat(pq.poll()).isEqualTo(10);
143143
assertTrue(pq.isEmpty());
144-
assertThat(pq.poll()).isEqualTo(LongPriorityQueue.NO_VALUE);
145-
assertThat(pq.peek()).isEqualTo(LongPriorityQueue.NO_VALUE);
144+
assertThat(pq.poll()).isEqualTo(IntPriorityQueue.NO_VALUE);
145+
assertThat(pq.peek()).isEqualTo(IntPriorityQueue.NO_VALUE);
146146
}
147147
}

0 commit comments

Comments
 (0)