1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab
#include "gtest/gtest.h"
#include "common/PrioritizedQueue.h"
#include <numeric>
#include <vector>
#include <algorithm>
#include <random>
using std::vector;
class PrioritizedQueueTest : public testing::Test
{
protected:
typedef int Klass;
typedef unsigned Item;
typedef PrioritizedQueue<Item, Klass> PQ;
enum { item_size = 100, };
vector<Item> items;
void SetUp() override {
for (int i = 0; i < item_size; i++) {
items.push_back(Item(i));
}
std::random_device rd;
std::default_random_engine rng(rd());
std::shuffle(items.begin(), items.end(), rng);
}
void TearDown() override {
items.clear();
}
};
TEST_F(PrioritizedQueueTest, capacity) {
const unsigned min_cost = 10;
const unsigned max_tokens_per_subqueue = 50;
PQ pq(max_tokens_per_subqueue, min_cost);
EXPECT_TRUE(pq.empty());
EXPECT_EQ(0u, pq.length());
pq.enqueue_strict(Klass(1), 0, Item(0));
EXPECT_FALSE(pq.empty());
EXPECT_EQ(1u, pq.length());
for (int i = 0; i < 3; i++) {
pq.enqueue(Klass(1), 0, 10, Item(0));
}
for (unsigned i = 4; i > 0; i--) {
EXPECT_FALSE(pq.empty());
EXPECT_EQ(i, pq.length());
pq.dequeue();
}
EXPECT_TRUE(pq.empty());
EXPECT_EQ(0u, pq.length());
}
TEST_F(PrioritizedQueueTest, strict_pq) {
const unsigned min_cost = 1;
const unsigned max_tokens_per_subqueue = 50;
PQ pq(max_tokens_per_subqueue, min_cost);
// 0 .. item_size-1
for (unsigned i = 0; i < item_size; i++) {
unsigned priority = items[i];
const Item& item = items[i];
pq.enqueue_strict(Klass(0), priority, Item(item));
}
// item_size-1 .. 0
for (unsigned i = item_size; i > 0; i--) {
Item item = pq.dequeue();
unsigned priority = item;
EXPECT_EQ(i - 1, priority);
}
}
TEST_F(PrioritizedQueueTest, lowest_among_eligible_otherwise_highest) {
// to minimize the effect of `distribute_tokens()`
// all eligible items will be assigned with cost of min_cost
const unsigned min_cost = 0;
const unsigned max_tokens_per_subqueue = 100;
PQ pq(max_tokens_per_subqueue, min_cost);
#define ITEM_TO_COST(item_) (item_ % 5 ? min_cost : max_tokens_per_subqueue)
unsigned num_low_cost = 0, num_high_cost = 0;
for (int i = 0; i < item_size; i++) {
const Item& item = items[i];
unsigned cost = ITEM_TO_COST(item);
unsigned priority = item;
if (cost == min_cost) {
num_low_cost++;
} else {
num_high_cost++;
}
pq.enqueue(Klass(0), priority, cost, Item(item));
}
// the token in all buckets is 0 at the beginning, so dequeue() should pick
// the first one with the highest priority.
unsigned highest_priority;
{
Item item = pq.dequeue();
unsigned cost = ITEM_TO_COST(item);
unsigned priority = item;
if (cost == min_cost) {
num_low_cost--;
} else {
num_high_cost--;
}
EXPECT_EQ(item_size - 1u, priority);
highest_priority = priority;
}
unsigned lowest_priority = 0;
for (unsigned i = 0; i < num_low_cost; i++) {
Item item = pq.dequeue();
unsigned cost = ITEM_TO_COST(item);
unsigned priority = item;
EXPECT_EQ(min_cost, cost);
EXPECT_GT(priority, lowest_priority);
lowest_priority = priority;
}
for (unsigned i = 0; i < num_high_cost; i++) {
Item item = pq.dequeue();
unsigned cost = ITEM_TO_COST(item);
unsigned priority = item;
EXPECT_EQ(max_tokens_per_subqueue, cost);
EXPECT_LT(priority, highest_priority);
highest_priority = priority;
}
#undef ITEM_TO_COST
}
static const unsigned num_classes = 4;
// just a determinitic number
#define ITEM_TO_CLASS(item_) Klass((item_ + 43) % num_classes)
TEST_F(PrioritizedQueueTest, fairness_by_class) {
// dequeue should be fair to all classes in a certain bucket
const unsigned min_cost = 1;
const unsigned max_tokens_per_subqueue = 50;
PQ pq(max_tokens_per_subqueue, min_cost);
for (int i = 0; i < item_size; i++) {
const Item& item = items[i];
Klass k = ITEM_TO_CLASS(item);
unsigned priority = 0;
unsigned cost = 1;
pq.enqueue(k, priority, cost, Item(item));
}
// just sample first 1/2 of the items
// if i pick too small a dataset, the result won't be statisitcally
// significant. if the sample dataset is too large, it will converge to the
// distribution of the full set.
vector<unsigned> num_picked_in_class(num_classes, 0u);
for (int i = 0; i < item_size / 2; i++) {
Item item = pq.dequeue();
Klass k = ITEM_TO_CLASS(item);
num_picked_in_class[k]++;
}
unsigned total = std::accumulate(num_picked_in_class.begin(),
num_picked_in_class.end(),
0);
float avg = float(total) / num_classes;
for (unsigned i = 0; i < num_classes; i++) {
EXPECT_NEAR(avg, num_picked_in_class[i], 0.5);
}
}
TEST_F(PrioritizedQueueTest, remove_by_class) {
const unsigned min_cost = 1;
const unsigned max_tokens_per_subqueue = 50;
PQ pq(max_tokens_per_subqueue, min_cost);
const Klass class_to_remove(2);
unsigned num_to_remove = 0;
for (int i = 0; i < item_size; i++) {
const Item& item = items[i];
Klass k = ITEM_TO_CLASS(item);
pq.enqueue(k, 0, 0, Item(item));
if (k == class_to_remove) {
num_to_remove++;
}
}
std::list<Item> removed;
pq.remove_by_class(class_to_remove, &removed);
// see if the removed items are expected ones.
for (std::list<Item>::iterator it = removed.begin();
it != removed.end();
++it) {
const Item& item = *it;
Klass k = ITEM_TO_CLASS(item);
EXPECT_EQ(class_to_remove, k);
items.erase(remove(items.begin(), items.end(), item), items.end());
}
EXPECT_EQ(num_to_remove, removed.size());
EXPECT_EQ(item_size - num_to_remove, pq.length());
EXPECT_EQ(item_size - num_to_remove, items.size());
// see if the remainder are expeceted also.
while (!pq.empty()) {
const Item item = pq.dequeue();
Klass k = ITEM_TO_CLASS(item);
EXPECT_NE(class_to_remove, k);
items.erase(remove(items.begin(), items.end(), item), items.end());
}
EXPECT_TRUE(items.empty());
}
|
