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}; // class Bench
121
124{
125 SystemWallClockMs timer;
126 double init;
127 double simu;
128
129 DEB("initializing");
130 m_count = 0;
131
132 timer.Start();
133 for (uint64_t i = 0; i < m_population; ++i)
134 {
136 Simulator::Schedule(at, &Bench::Cb, this);
137 }
138 init = timer.End() / 1000.0;
139 DEB("initialization took " << init << "s");
140
141 DEB("running");
142 timer.Start();
144 simu = timer.End() / 1000.0;
145 DEB("run took " << simu << "s");
146
148
149 return Result{init, simu, m_population, m_count};
150}
151
152void
154{
155 if (m_count >= m_total)
156 {
158 return;
159 }
160 DEB("event at " << Simulator::Now().GetSeconds() << "s");
161
162 Time after = NanoSeconds(m_rand->GetValue());
163 Simulator::Schedule(after, &Bench::Cb, this);
164 ++m_count;
165}
166
167/** Benchmark which performs an ensemble of runs. */
169{
170 public:
171 /**
172 * Perform the runs for a single scheduler type.
173 *
174 * This will create and set the scheduler, then execute a priming run
175 * followed by the number of data runs requested.
176 *
177 * Output will be in the form of a table showing performance for each run.
178 *
179 * @param [in] factory Factory pre-configured to create the desired Scheduler.
180 * @param [in] pop The event population size.
181 * @param [in] total The total number of events to execute.
182 * @param [in] runs The number of replications.
183 * @param [in] eventStream The random stream of event delays.
184 * @param [in] calRev For the CalendarScheduler, whether the Reverse attribute was set.
185 */
186 BenchSuite(ObjectFactory& factory,
187 uint64_t pop,
188 uint64_t total,
189 uint64_t runs,
190 Ptr<RandomVariableStream> eventStream,
191 bool calRev);
192
193 /** Write the results to \c LOG() */
194 void Log() const;
195
196 private:
197 /** Print the table header. */
198 void Header() const;
199
200 /** Statistics from a single phase, init or run. */
202 {
203 double time; /**< Phase run time time (s). */
204 double rate; /**< Phase event rate (events/s). */
205 double period; /**< Phase period (s/event). */
206 };
207
208 /** Results from initialization and execution of a single run. */
209 struct Result
210 {
211 PhaseResult init; /**< Initialization phase results. */
212 PhaseResult run; /**< Run (simulation) phase results. */
213 /**
214 * Construct from the individual run result.
215 *
216 * @param [in] r The result from a single run.
217 * @returns The run result.
218 */
219 static Result Bench(Bench::Result r);
220
221 /**
222 * Log this result.
223 *
224 * @tparam T The type of the label.
225 * @param label The label for the line.
226 */
227 template <typename T>
228 void Log(T label) const;
229 }; // struct Result
230
231 std::string m_scheduler; /**< Descriptive string for the scheduler. */
232 std::vector<Result> m_results; /**< Store for the run results. */
233
234}; // BenchSuite
235
236/* static */
239{
240 return Result{{r.init, r.pop / r.init, r.init / r.pop},
241 {r.simu, r.events / r.simu, r.simu / r.events}};
242}
243
244template <typename T>
245void
247{
248 // Need std::left for string labels
249
250 LOG(std::left << std::setw(g_fwidth) << label << std::setw(g_fwidth) << init.time
251 << std::setw(g_fwidth) << init.rate << std::setw(g_fwidth) << init.period
252 << std::setw(g_fwidth) << run.time << std::setw(g_fwidth) << run.rate
253 << std::setw(g_fwidth) << run.period);
254}
255
257 uint64_t pop,
258 uint64_t total,
259 uint64_t runs,
260 Ptr<RandomVariableStream> eventStream,
261 bool calRev)
262{
264
265 m_scheduler = factory.GetTypeId().GetName();
266 if (m_scheduler == "ns3::CalendarScheduler")
267 {
268 m_scheduler += ": insertion order: " + std::string(calRev ? "reverse" : "normal");
269 }
270 if (m_scheduler == "ns3::MapScheduler")
271 {
272 m_scheduler += " (default)";
273 }
274
275 Bench bench(pop, total);
276 bench.SetRandomStream(eventStream);
277 bench.SetPopulation(pop);
278 bench.SetTotal(total);
279
280 m_results.reserve(runs);
281 Header();
282
283 // Prime
284 DEB("priming");
285 auto prime = bench.Run();
286 Result::Bench(prime).Log("prime");
287
288 // Perform the actual runs
289 for (uint64_t i = 0; i < runs; i++)
290 {
291 auto run = bench.Run();
292 m_results.push_back(Result::Bench(run));
293 m_results.back().Log(i);
294 }
295
297
298} // BenchSuite::Run
299
300void
302{
303 // table header
304 LOG("");
306 LOG(std::left << std::setw(g_fwidth) << "Run #" << std::left << std::setw(3 * g_fwidth)
307 << "Initialization:" << std::left << "Simulation:");
308 LOG(std::left << std::setw(g_fwidth) << "" << std::left << std::setw(g_fwidth) << "Time (s)"
309 << std::left << std::setw(g_fwidth) << "Rate (ev/s)" << std::left
310 << std::setw(g_fwidth) << "Per (s/ev)" << std::left << std::setw(g_fwidth)
311 << "Time (s)" << std::left << std::setw(g_fwidth) << "Rate (ev/s)" << std::left
312 << "Per (s/ev)");
313 LOG(std::setfill('-') << 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::right
316 << std::setw(g_fwidth) << " " << std::right << std::setw(g_fwidth) << " "
317 << std::right << std::setw(g_fwidth) << " " << std::setfill(' '));
318}
319
320void
322{
323 if (m_results.size() < 2)
324 {
325 LOG("");
326 return;
327 }
328
329 // Average the results
330
331 // See Welford's online algorithm for these expressions,
332 // which avoid subtracting large numbers.
333 // https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Welford's_online_algorithm
334
335 uint64_t n{0}; // number of samples
336 Result average{m_results[0]}; // average
337 Result moment2{{0, 0, 0}, // 2nd moment, to calculate stdev
338 {0, 0, 0}};
339
340 for (; n < m_results.size(); ++n)
341 {
342 double deltaPre;
343 double deltaPost;
344 const auto& run = m_results[n];
345 uint64_t count = n + 1;
346
347#define ACCUMULATE(phase, field) \
348 deltaPre = run.phase.field - average.phase.field; \
349 average.phase.field += deltaPre / count; \
350 deltaPost = run.phase.field - average.phase.field; \
351 moment2.phase.field += deltaPre * deltaPost
352
353 ACCUMULATE(init, time);
354 ACCUMULATE(init, rate);
355 ACCUMULATE(init, period);
356 ACCUMULATE(run, time);
357 ACCUMULATE(run, rate);
358 ACCUMULATE(run, period);
359
360#undef ACCUMULATE
361 }
362
363 auto stdev = Result{
364 {std::sqrt(moment2.init.time / n),
365 std::sqrt(moment2.init.rate / n),
366 std::sqrt(moment2.init.period / n)},
367 {std::sqrt(moment2.run.time / n),
368 std::sqrt(moment2.run.rate / n),
369 std::sqrt(moment2.run.period / n)},
370 };
371
372 average.Log("average");
373 stdev.Log("stdev");
374
375 LOG("");
376
377} // BenchSuite::Log()
378
379/**
380 * Create a RandomVariableStream to generate next event delays.
381 *
382 * If the \p filename parameter is empty a default exponential time
383 * distribution will be used, with mean delay of 100 ns.
384 *
385 * If the \p filename is `-` standard input will be used.
386 *
387 * @param [in] filename The delay interval source file name.
388 * @returns The RandomVariableStream.
389 */
391GetRandomStream(std::string filename)
392{
393 Ptr<RandomVariableStream> stream = nullptr;
394
395 if (filename.empty())
396 {
397 LOG(" Event time distribution: default exponential");
399 erv->SetAttribute("Mean", DoubleValue(100));
400 stream = erv;
401 }
402 else
403 {
404 std::istream* input;
405
406 if (filename == "-")
407 {
408 LOG(" Event time distribution: from stdin");
409 input = &std::cin;
410 }
411 else
412 {
413 LOG(" Event time distribution: from " << filename);
414 input = new std::ifstream(filename);
415 }
416
417 double value;
418 std::vector<double> nsValues;
419
420 while (!input->eof())
421 {
422 if (*input >> value)
423 {
424 auto ns = (uint64_t)(value * 1000000000);
425 nsValues.push_back(ns);
426 }
427 else
428 {
429 input->clear();
430 std::string line;
431 *input >> line;
432 }
433 }
434 LOG(" Found " << nsValues.size() << " entries");
436 drv->SetValueArray(&nsValues[0], nsValues.size());
437 stream = drv;
438 }
439
440 return stream;
441}
442
443int
444main(int argc, char* argv[])
445{
446 bool allSched = false;
447 bool schedCal = false;
448 bool schedHeap = false;
449 bool schedList = false;
450 bool schedMap = false; // default scheduler
451 bool schedPQ = false;
452
453 uint64_t pop = 100000;
454 uint64_t total = 1000000;
455 uint64_t runs = 1;
456 std::string filename = "";
457 bool calRev = false;
458
459 CommandLine cmd(__FILE__);
460 cmd.Usage("Benchmark the simulator scheduler.\n"
461 "\n"
462 "Event intervals are taken from one of:\n"
463 " an exponential distribution, with mean 100 ns,\n"
464 " an ascii file, given by the --file=\"<filename>\" argument,\n"
465 " or standard input, by the argument --file=\"-\"\n"
466 "In the case of either --file form, the input is expected\n"
467 "to be ascii, giving the relative event times in ns.\n"
468 "\n"
469 "If no scheduler is specified the MapScheduler will be run.");
470 cmd.AddValue("all", "use all schedulers", allSched);
471 cmd.AddValue("cal", "use CalendarScheduler", schedCal);
472 cmd.AddValue("calrev", "reverse ordering in the CalendarScheduler", calRev);
473 cmd.AddValue("heap", "use HeapScheduler", schedHeap);
474 cmd.AddValue("list", "use ListScheduler", schedList);
475 cmd.AddValue("map", "use MapScheduler (default)", schedMap);
476 cmd.AddValue("pri", "use PriorityQueue", schedPQ);
477 cmd.AddValue("debug", "enable debugging output", g_debug);
478 cmd.AddValue("pop", "event population size", pop);
479 cmd.AddValue("total", "total number of events to run", total);
480 cmd.AddValue("runs", "number of runs", runs);
481 cmd.AddValue("file", "file of relative event times", filename);
482 cmd.AddValue("prec", "printed output precision", g_fwidth);
483 cmd.Parse(argc, argv);
484
485 g_me = cmd.GetName() + ": ";
486 g_fwidth += 6; // 5 extra chars in '2.000002e+07 ': . e+0 _
487
488 LOG(std::setprecision(g_fwidth - 6)); // prints blank line
489 LOGME(" Benchmark the simulator scheduler");
490 LOG(" Event population size: " << pop);
491 LOG(" Total events per run: " << total);
492 LOG(" Number of runs per scheduler: " << runs);
493 DEB("debugging is ON");
494
495 if (allSched)
496 {
497 schedCal = schedHeap = schedList = schedMap = schedPQ = true;
498 }
499 // Set the default case if nothing else is set
500 if (!(schedCal || schedHeap || schedList || schedMap || schedPQ))
501 {
502 schedMap = true;
503 }
504
505 auto eventStream = GetRandomStream(filename);
506
507 ObjectFactory factory("ns3::MapScheduler");
508 if (schedCal)
509 {
510 factory.SetTypeId("ns3::CalendarScheduler");
511 factory.Set("Reverse", BooleanValue(calRev));
512 BenchSuite(factory, pop, total, runs, eventStream, calRev).Log();
513 if (allSched)
514 {
515 factory.Set("Reverse", BooleanValue(!calRev));
516 BenchSuite(factory, pop, total, runs, eventStream, !calRev).Log();
517 }
518 }
519 if (schedHeap)
520 {
521 factory.SetTypeId("ns3::HeapScheduler");
522 BenchSuite(factory, pop, total, runs, eventStream, calRev).Log();
523 }
524 if (schedList)
525 {
526 factory.SetTypeId("ns3::ListScheduler");
527 auto listTotal = total;
528 if (allSched)
529 {
530 LOG("Running List scheduler with 1/10 total events");
531 listTotal /= 10;
532 }
533 BenchSuite(factory, pop, listTotal, runs, eventStream, calRev).Log();
534 }
535 if (schedMap)
536 {
537 factory.SetTypeId("ns3::MapScheduler");
538 BenchSuite(factory, pop, total, runs, eventStream, calRev).Log();
539 }
540 if (schedPQ)
541 {
542 factory.SetTypeId("ns3::PriorityQueueScheduler");
543 BenchSuite(factory, pop, total, runs, eventStream, calRev).Log();
544 }
545
546 return 0;
547}
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:560
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:1380
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.