A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
bench-scheduler.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2006 INRIA
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
7 */
8
9#include "ns3/core-module.h"
10
11#include <cmath> // sqrt
12#include <fstream>
13#include <iomanip>
14#include <iostream>
15#include <string.h>
16#include <vector>
17
18using namespace ns3;
19
20/** Flag to write debugging output. */
21bool g_debug = false;
22
23/** Name of this program. */
24std::string g_me;
25/** Log to std::cout */
26#define LOG(x) std::cout << x << std::endl
27/** Log with program name prefix. */
28#define LOGME(x) LOG(g_me << x)
29/** Log debugging output. */
30#define DEB(x) \
31 if (g_debug) \
32 { \
33 LOGME(x); \
34 }
35
36/** Output field width for numeric data. */
37int g_fwidth = 6;
38
39/**
40 * Benchmark instance which can do a single run.
41 *
42 * The run is controlled by the event population size and
43 * total number of events, which are set at construction.
44 *
45 * The event distribution in time is set by SetRandomStream()
46 */
47class Bench
48{
49 public:
50 /**
51 * Constructor
52 * @param [in] population The number of events to keep in the scheduler.
53 * @param [in] total The total number of events to execute.
54 */
55 Bench(const uint64_t population, const uint64_t total)
56 : m_population(population),
57 m_total(total),
58 m_count(0)
59 {
60 }
61
62 /**
63 * Set the event delay interval random stream.
64 *
65 * @param [in] stream The random variable stream to be used to generate
66 * delays for future events.
67 */
69 {
70 m_rand = stream;
71 }
72
73 /**
74 * Set the number of events to populate the scheduler with.
75 * Each event executed schedules a new event, maintaining the population.
76 * @param [in] population The number of events to keep in the scheduler.
77 */
78 void SetPopulation(const uint64_t population)
79 {
80 m_population = population;
81 }
82
83 /**
84 * Set the total number of events to execute.
85 * @param [in] total The total number of events to execute.
86 */
87 void SetTotal(const uint64_t total)
88 {
89 m_total = total;
90 }
91
92 /** The output. */
93 struct Result
94 {
95 double init; /**< Time (s) for initialization. */
96 double simu; /**< Time (s) for simulation. */
97 uint64_t pop; /**< Event population. */
98 uint64_t events; /**< Number of events executed. */
99 };
100
101 /**
102 * Run the benchmark as configured.
103 *
104 * @returns The Result.
105 */
106 Result Run();
107
108 private:
109 /**
110 * Event function. This checks for completion (total number of events
111 * executed) and schedules a new event if not complete.
112 */
113 void Cb();
114
115 Ptr<RandomVariableStream> m_rand; /**< Stream for event delays. */
116 uint64_t m_population; /**< Event population size. */
117 uint64_t m_total; /**< Total number of events to execute. */
118 uint64_t m_count; /**< Count of events executed so far. */
119};
120
123{
124 SystemWallClockMs timer;
125 double init;
126 double simu;
127
128 DEB("initializing");
129 m_count = 0;
130
131 timer.Start();
132 for (uint64_t i = 0; i < m_population; ++i)
133 {
135 Simulator::Schedule(at, &Bench::Cb, this);
136 }
137 init = timer.End() / 1000.0;
138 DEB("initialization took " << init << "s");
139
140 DEB("running");
141 timer.Start();
143 simu = timer.End() / 1000.0;
144 DEB("run took " << simu << "s");
145
147
148 return Result{init, simu, m_population, m_count};
149}
150
151void
153{
154 if (m_count >= m_total)
155 {
157 return;
158 }
159 DEB("event at " << Simulator::Now().GetSeconds() << "s");
160
161 Time after = NanoSeconds(m_rand->GetValue());
162 Simulator::Schedule(after, &Bench::Cb, this);
163 ++m_count;
164}
165
166/** Benchmark which performs an ensemble of runs. */
168{
169 public:
170 /**
171 * Perform the runs for a single scheduler type.
172 *
173 * This will create and set the scheduler, then execute a priming run
174 * followed by the number of data runs requested.
175 *
176 * Output will be in the form of a table showing performance for each run.
177 *
178 * @param [in] factory Factory pre-configured to create the desired Scheduler.
179 * @param [in] pop The event population size.
180 * @param [in] total The total number of events to execute.
181 * @param [in] runs The number of replications.
182 * @param [in] eventStream The random stream of event delays.
183 * @param [in] calRev For the CalendarScheduler, whether the Reverse attribute was set.
184 */
185 BenchSuite(ObjectFactory& factory,
186 uint64_t pop,
187 uint64_t total,
188 uint64_t runs,
189 Ptr<RandomVariableStream> eventStream,
190 bool calRev);
191
192 /** Write the results to \c LOG() */
193 void Log() const;
194
195 private:
196 /** Print the table header. */
197 void Header() const;
198
199 /** Statistics from a single phase, init or run. */
201 {
202 double time; /**< Phase run time time (s). */
203 double rate; /**< Phase event rate (events/s). */
204 double period; /**< Phase period (s/event). */
205 };
206
207 /** Results from initialization and execution of a single run. */
208 struct Result
209 {
210 PhaseResult init; /**< Initialization phase results. */
211 PhaseResult run; /**< Run (simulation) phase results. */
212 /**
213 * Construct from the individual run result.
214 *
215 * @param [in] r The result from a single run.
216 * @returns The run result.
217 */
218 static Result Bench(Bench::Result r);
219
220 /**
221 * Log this result.
222 *
223 * @tparam T The type of the label.
224 * @param label The label for the line.
225 */
226 template <typename T>
227 void Log(T label) const;
228 }; // struct Result
229
230 std::string m_scheduler; /**< Descriptive string for the scheduler. */
231 std::vector<Result> m_results; /**< Store for the run results. */
232
233}; // BenchSuite
234
235/* static */
238{
239 return Result{{r.init, r.pop / r.init, r.init / r.pop},
240 {r.simu, r.events / r.simu, r.simu / r.events}};
241}
242
243template <typename T>
244void
246{
247 // Need std::left for string labels
248
249 LOG(std::left << std::setw(g_fwidth) << label << std::setw(g_fwidth) << init.time
250 << std::setw(g_fwidth) << init.rate << std::setw(g_fwidth) << init.period
251 << std::setw(g_fwidth) << run.time << std::setw(g_fwidth) << run.rate
252 << std::setw(g_fwidth) << run.period);
253}
254
256 uint64_t pop,
257 uint64_t total,
258 uint64_t runs,
259 Ptr<RandomVariableStream> eventStream,
260 bool calRev)
261{
263
264 m_scheduler = factory.GetTypeId().GetName();
265 if (m_scheduler == "ns3::CalendarScheduler")
266 {
267 m_scheduler += ": insertion order: " + std::string(calRev ? "reverse" : "normal");
268 }
269 if (m_scheduler == "ns3::MapScheduler")
270 {
271 m_scheduler += " (default)";
272 }
273
274 Bench bench(pop, total);
275 bench.SetRandomStream(eventStream);
276 bench.SetPopulation(pop);
277 bench.SetTotal(total);
278
279 m_results.reserve(runs);
280 Header();
281
282 // Prime
283 DEB("priming");
284 auto prime = bench.Run();
285 Result::Bench(prime).Log("prime");
286
287 // Perform the actual runs
288 for (uint64_t i = 0; i < runs; i++)
289 {
290 auto run = bench.Run();
291 m_results.push_back(Result::Bench(run));
292 m_results.back().Log(i);
293 }
294
296}
297
298void
300{
301 // table header
302 LOG("");
304 LOG(std::left << std::setw(g_fwidth) << "Run #" << std::left << std::setw(3 * g_fwidth)
305 << "Initialization:" << std::left << "Simulation:");
306 LOG(std::left << std::setw(g_fwidth) << "" << std::left << std::setw(g_fwidth) << "Time (s)"
307 << std::left << std::setw(g_fwidth) << "Rate (ev/s)" << std::left
308 << std::setw(g_fwidth) << "Per (s/ev)" << std::left << std::setw(g_fwidth)
309 << "Time (s)" << std::left << std::setw(g_fwidth) << "Rate (ev/s)" << std::left
310 << "Per (s/ev)");
311 LOG(std::setfill('-') << std::right << std::setw(g_fwidth) << " " << std::right
312 << std::setw(g_fwidth) << " " << std::right << std::setw(g_fwidth) << " "
313 << std::right << std::setw(g_fwidth) << " " << std::right
314 << std::setw(g_fwidth) << " " << std::right << std::setw(g_fwidth) << " "
315 << std::right << std::setw(g_fwidth) << " " << std::setfill(' '));
316}
317
318void
320{
321 if (m_results.size() < 2)
322 {
323 LOG("");
324 return;
325 }
326
327 // Average the results
328
329 // See Welford's online algorithm for these expressions,
330 // which avoid subtracting large numbers.
331 // https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Welford's_online_algorithm
332
333 uint64_t n{0}; // number of samples
334 Result average{m_results[0]}; // average
335 Result moment2{{0, 0, 0}, // 2nd moment, to calculate stdev
336 {0, 0, 0}};
337
338 for (; n < m_results.size(); ++n)
339 {
340 double deltaPre;
341 double deltaPost;
342 const auto& run = m_results[n];
343 uint64_t count = n + 1;
344
345#define ACCUMULATE(phase, field) \
346 deltaPre = run.phase.field - average.phase.field; \
347 average.phase.field += deltaPre / count; \
348 deltaPost = run.phase.field - average.phase.field; \
349 moment2.phase.field += deltaPre * deltaPost
350
351 ACCUMULATE(init, time);
352 ACCUMULATE(init, rate);
353 ACCUMULATE(init, period);
354 ACCUMULATE(run, time);
355 ACCUMULATE(run, rate);
356 ACCUMULATE(run, period);
357
358#undef ACCUMULATE
359 }
360
361 auto stdev = Result{
362 {std::sqrt(moment2.init.time / n),
363 std::sqrt(moment2.init.rate / n),
364 std::sqrt(moment2.init.period / n)},
365 {std::sqrt(moment2.run.time / n),
366 std::sqrt(moment2.run.rate / n),
367 std::sqrt(moment2.run.period / n)},
368 };
369
370 average.Log("average");
371 stdev.Log("stdev");
372
373 LOG("");
374}
375
376/**
377 * Create a RandomVariableStream to generate next event delays.
378 *
379 * If the \p filename parameter is empty a default exponential time
380 * distribution will be used, with mean delay of 100 ns.
381 *
382 * If the \p filename is `-` standard input will be used.
383 *
384 * @param [in] filename The delay interval source file name.
385 * @returns The RandomVariableStream.
386 */
388GetRandomStream(std::string filename)
389{
390 Ptr<RandomVariableStream> stream = nullptr;
391
392 if (filename.empty())
393 {
394 LOG(" Event time distribution: default exponential");
396 erv->SetAttribute("Mean", DoubleValue(100));
397 stream = erv;
398 }
399 else
400 {
401 std::istream* input;
402
403 if (filename == "-")
404 {
405 LOG(" Event time distribution: from stdin");
406 input = &std::cin;
407 }
408 else
409 {
410 LOG(" Event time distribution: from " << filename);
411 input = new std::ifstream(filename);
412 }
413
414 double value;
415 std::vector<double> nsValues;
416
417 while (!input->eof())
418 {
419 if (*input >> value)
420 {
421 auto ns = (uint64_t)(value * 1000000000);
422 nsValues.push_back(ns);
423 }
424 else
425 {
426 input->clear();
427 std::string line;
428 *input >> line;
429 }
430 }
431 LOG(" Found " << nsValues.size() << " entries");
433 drv->SetValueArray(&nsValues[0], nsValues.size());
434 stream = drv;
435 }
436
437 return stream;
438}
439
440int
441main(int argc, char* argv[])
442{
443 bool allSched = false;
444 bool schedCal = false;
445 bool schedHeap = false;
446 bool schedList = false;
447 bool schedMap = false; // default scheduler
448 bool schedPQ = false;
449
450 uint64_t pop = 100000;
451 uint64_t total = 1000000;
452 uint64_t runs = 1;
453 std::string filename = "";
454 bool calRev = false;
455
456 CommandLine cmd(__FILE__);
457 cmd.Usage("Benchmark the simulator scheduler.\n"
458 "\n"
459 "Event intervals are taken from one of:\n"
460 " an exponential distribution, with mean 100 ns,\n"
461 " an ascii file, given by the --file=\"<filename>\" argument,\n"
462 " or standard input, by the argument --file=\"-\"\n"
463 "In the case of either --file form, the input is expected\n"
464 "to be ascii, giving the relative event times in ns.\n"
465 "\n"
466 "If no scheduler is specified the MapScheduler will be run.");
467 cmd.AddValue("all", "use all schedulers", allSched);
468 cmd.AddValue("cal", "use CalendarScheduler", schedCal);
469 cmd.AddValue("calrev", "reverse ordering in the CalendarScheduler", calRev);
470 cmd.AddValue("heap", "use HeapScheduler", schedHeap);
471 cmd.AddValue("list", "use ListScheduler", schedList);
472 cmd.AddValue("map", "use MapScheduler (default)", schedMap);
473 cmd.AddValue("pri", "use PriorityQueue", schedPQ);
474 cmd.AddValue("debug", "enable debugging output", g_debug);
475 cmd.AddValue("pop", "event population size", pop);
476 cmd.AddValue("total", "total number of events to run", total);
477 cmd.AddValue("runs", "number of runs", runs);
478 cmd.AddValue("file", "file of relative event times", filename);
479 cmd.AddValue("prec", "printed output precision", g_fwidth);
480 cmd.Parse(argc, argv);
481
482 g_me = cmd.GetName() + ": ";
483 g_fwidth += 6; // 5 extra chars in '2.000002e+07 ': . e+0 _
484
485 LOG(std::setprecision(g_fwidth - 6)); // prints blank line
486 LOGME(" Benchmark the simulator scheduler");
487 LOG(" Event population size: " << pop);
488 LOG(" Total events per run: " << total);
489 LOG(" Number of runs per scheduler: " << runs);
490 DEB("debugging is ON");
491
492 if (allSched)
493 {
494 schedCal = schedHeap = schedList = schedMap = schedPQ = true;
495 }
496 // Set the default case if nothing else is set
497 if (!(schedCal || schedHeap || schedList || schedMap || schedPQ))
498 {
499 schedMap = true;
500 }
501
502 auto eventStream = GetRandomStream(filename);
503
504 ObjectFactory factory("ns3::MapScheduler");
505 if (schedCal)
506 {
507 factory.SetTypeId("ns3::CalendarScheduler");
508 factory.Set("Reverse", BooleanValue(calRev));
509 BenchSuite(factory, pop, total, runs, eventStream, calRev).Log();
510 if (allSched)
511 {
512 factory.Set("Reverse", BooleanValue(!calRev));
513 BenchSuite(factory, pop, total, runs, eventStream, !calRev).Log();
514 }
515 }
516 if (schedHeap)
517 {
518 factory.SetTypeId("ns3::HeapScheduler");
519 BenchSuite(factory, pop, total, runs, eventStream, calRev).Log();
520 }
521 if (schedList)
522 {
523 factory.SetTypeId("ns3::ListScheduler");
524 auto listTotal = total;
525 if (allSched)
526 {
527 LOG("Running List scheduler with 1/10 total events");
528 listTotal /= 10;
529 }
530 BenchSuite(factory, pop, listTotal, runs, eventStream, calRev).Log();
531 }
532 if (schedMap)
533 {
534 factory.SetTypeId("ns3::MapScheduler");
535 BenchSuite(factory, pop, total, runs, eventStream, calRev).Log();
536 }
537 if (schedPQ)
538 {
539 factory.SetTypeId("ns3::PriorityQueueScheduler");
540 BenchSuite(factory, pop, total, runs, eventStream, calRev).Log();
541 }
542
543 return 0;
544}
Ptr< RandomVariableStream > GetRandomStream(std::string filename)
Create a RandomVariableStream to generate next event delays.
bool g_debug
Flag to write debugging output.
#define LOGME(x)
Log with program name prefix.
int g_fwidth
Output field width for numeric data.
std::string g_me
Name of this program.
#define ACCUMULATE(phase, field)
#define LOG(x)
Log to std::cout.
#define DEB(x)
Log debugging output.
Benchmark instance which can do a single run.
void SetRandomStream(Ptr< RandomVariableStream > stream)
Set the event delay interval random stream.
uint64_t m_population
Event population size.
void SetTotal(const uint64_t total)
Set the total number of events to execute.
Result Run()
Run the benchmark as configured.
Ptr< RandomVariableStream > m_rand
Stream for event delays.
uint64_t m_count
Count of events executed so far.
Bench(const uint64_t population, const uint64_t total)
Constructor.
void SetPopulation(const uint64_t population)
Set the number of events to populate the scheduler with.
uint64_t m_total
Total number of events to execute.
void Cb()
Event function.
Benchmark which performs an ensemble of runs.
void Log() const
Write the results to LOG()
BenchSuite(ObjectFactory &factory, uint64_t pop, uint64_t total, uint64_t runs, Ptr< RandomVariableStream > eventStream, bool calRev)
Perform the runs for a single scheduler type.
void Header() const
Print the table header.
std::vector< Result > m_results
Store for the run results.
std::string m_scheduler
Descriptive string for the scheduler.
AttributeValue implementation for Boolean.
Definition boolean.h:26
Parse command-line arguments.
This class can be used to hold variables of floating point type such as 'double' or 'float'.
Definition double.h:31
Instantiate subclasses of ns3::Object.
TypeId GetTypeId() const
Get the TypeId which will be created by this ObjectFactory.
Smart pointer class similar to boost::intrusive_ptr.
virtual double GetValue()=0
Get the next random value drawn from the distribution.
static EventId Schedule(const Time &delay, FUNC f, Ts &&... args)
Schedule an event to expire after delay.
Definition simulator.h:561
static void Destroy()
Execute the events scheduled with ScheduleDestroy().
Definition simulator.cc:131
static Time Now()
Return the current simulation virtual time.
Definition simulator.cc:197
static void Run()
Run the simulation.
Definition simulator.cc:167
static void SetScheduler(ObjectFactory schedulerFactory)
Set the scheduler type with an ObjectFactory.
Definition simulator.cc:153
static void Stop()
Tell the Simulator the calling event should be the last one executed.
Definition simulator.cc:175
Measure elapsed wall clock time in milliseconds.
int64_t End()
Stop measuring the time since Start() was called.
void Start()
Start a measure.
Simulation virtual time values and global simulation resolution.
Definition nstime.h:94
std::string GetName() const
Get the name.
Definition type-id.cc:1061
Ptr< T > CreateObject(Args &&... args)
Create an object by type, with varying number of constructor parameters.
Definition object.h:619
Time NanoSeconds(uint64_t value)
Construct a Time in the indicated unit.
Definition nstime.h:1381
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::StringValue attribute value declarations.
uint64_t events
Number of events executed.
uint64_t pop
Event population.
double init
Time (s) for initialization.
double simu
Time (s) for simulation.
Statistics from a single phase, init or run.
double rate
Phase event rate (events/s).
double period
Phase period (s/event).
double time
Phase run time time (s).
Results from initialization and execution of a single run.
PhaseResult init
Initialization phase results.
static Result Bench(Bench::Result r)
Construct from the individual run result.
void Log(T label) const
Log this result.
PhaseResult run
Run (simulation) phase results.