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
|
\title{A2: Measurement}
\input{preamble.tex}
In this assignment some std algorithms are executed on vectors and
their performance measured.
A reuseable measurement mechanism based on RIAA, \texttt{class
Measure}, was made and a simple templated function, \texttt{measure}, was made
for executing multiple times and printing the results.
The RIAA class did not turn out as elegant as I originally
anticipated, but I decided to keep it anyway.
These are intended for re-use in the upcoming assigments.
As with assignment 1, I started out using modules instead of includes,
but I got some really wierd behaviour
from \texttt{std::this\_thread::sleep\_for()} and even a crash and
ended up having to go back to using \texttt{\#include} which solved
the issues.
I found the random mildly confusing although I can recognize how it is
very modular and customizable for a variety of purposes.
The assignment instructions are kept in the code as comments for easy
navigation.
Each sub-task is put in its own scope to not pollute scope and at the
same time give the reader some notion of where the blocks seperate.
Functions could also have been used, but I decided this was easier to
read.
I particularly enjoyed the fact that I could generate the random
characters directly as characters instead of having to generate
numbers and then convert them to characters afterwards.
\bigskip
The program is being compiled four times, with optimization levels set to 0
through 3.
The following pages shows the console outputs of the four being executed:
\noindent\begin{minipage}{0.5\textwidth}
Running measurement -O0:
\scriptsize\begin{verbatim}
Sanity check (sleep 100ms):
100.11 ms passed
100.293 ms passed
100.145 ms passed
std::find 7 in the middle:
23.2664 ms passed
23.6302 ms passed
23.3487 ms passed
std::find 7 not there:
46.4612 ms passed
46.3373 ms passed
46.3307 ms passed
std::find_if x < 7 in the middle:
30.6713 ms passed
30.6191 ms passed
30.4679 ms passed
std::find_if x < 7 not there:
60.8465 ms passed
60.7847 ms passed
60.9189 ms passed
Find XXXXXXXXXXXXXXXXXXXX (not there):
87.4575 ms passed
87.0677 ms passed
87.0778 ms passed
Find XXXXXXXXXXXXXXXXXXXX (in the middle):
43.5735 ms passed
43.6536 ms passed
43.5371 ms passed
\end{verbatim}
\end{minipage}\hspace{1em}
\begin{minipage}{0.5\textwidth}
Running measurement -O1:
\scriptsize\begin{verbatim}
Sanity check (sleep 100ms):
100.072 ms passed
100.205 ms passed
100.272 ms passed
std::find 7 in the middle:
2.4489 ms passed
2.27078 ms passed
2.09195 ms passed
std::find 7 not there:
3.48041 ms passed
3.0423 ms passed
3.26511 ms passed
std::find_if x < 7 in the middle:
1.75712 ms passed
1.67603 ms passed
1.54085 ms passed
std::find_if x < 7 not there:
3.49353 ms passed
3.13966 ms passed
3.02858 ms passed
Find XXXXXXXXXXXXXXXXXXXX (not there):
19.4014 ms passed
19.1675 ms passed
19.199 ms passed
Find XXXXXXXXXXXXXXXXXXXX (in the middle):
9.98892 ms passed
9.75758 ms passed
10.0103 ms passed
\end{verbatim}
\end{minipage}
\noindent\begin{minipage}{0.5\textwidth}
Running measurement -O2:
\scriptsize\begin{verbatim}
Sanity check (sleep 100ms):
100.285 ms passed
100.284 ms passed
100.109 ms passed
std::find 7 in the middle:
2.41485 ms passed
2.24354 ms passed
2.05605 ms passed
std::find 7 not there:
3.3622 ms passed
3.04281 ms passed
3.19882 ms passed
std::find_if x < 7 in the middle:
1.82075 ms passed
1.64321 ms passed
1.56913 ms passed
std::find_if x < 7 not there:
3.4318 ms passed
3.0527 ms passed
3.00441 ms passed
Find XXXXXXXXXXXXXXXXXXXX (not there):
19.4918 ms passed
19.1717 ms passed
19.1356 ms passed
Find XXXXXXXXXXXXXXXXXXXX (in the middle):
9.77586 ms passed
9.72502 ms passed
9.92281 ms passed
\end{verbatim}
\end{minipage}\hspace{1em}
\begin{minipage}{0.5\textwidth}
Running measurement -O3:
\scriptsize\begin{verbatim}
Sanity check (sleep 100ms):
100.289 ms passed
100.131 ms passed
100.278 ms passed
std::find 7 in the middle:
2.88775 ms passed
2.72746 ms passed
2.34705 ms passed
std::find 7 not there:
3.45066 ms passed
3.20888 ms passed
2.97772 ms passed
std::find_if x < 7 in the middle:
1.67701 ms passed
1.55496 ms passed
1.5005 ms passed
std::find_if x < 7 not there:
3.11582 ms passed
3.02069 ms passed
3.05484 ms passed
Find XXXXXXXXXXXXXXXXXXXX (not there):
19.4556 ms passed
19.0535 ms passed
19.0312 ms passed
Find XXXXXXXXXXXXXXXXXXXX (in the middle):
10.1083 ms passed
9.98972 ms passed
9.90104 ms passed
\end{verbatim}
\end{minipage}
\bigskip
Observing the one without optimization; The execution time of the
two \texttt{std::find} operations correllate nicely with the fact that
they are linear in execution time.
The same goes for the \texttt{std::find\_if} ones, and a slight
decrease in performance compared to the \texttt{std::find} one can be
attributed to the fact that the comparison is more involved than a
simple \texttt{==} (it is calling the lambda on each element.
On the optimized versions the lambda is probably inlined, so
difference between \texttt{std::find} and \texttt{std::find\_if} can
be expected to become smaller. This is also what can be observed.
It is interesting to see the \texttt{std::find} actually becoming
slower than \texttt{std::find\_if} when optimizations are enabled -
that leaves food for thought...
Looking at the string searches, these are, as expected, an order of
magnitude slower than the integer ones, since more data must be
traversed (20 bytes instead of 4 bytes for the integers). And again,
being liniear, finding the string in the middle about halves the
execution time as expected.
\bigskip
I was expecting the execution time to gradually decrease as the
amount of optimization increased, but this did not seem to be the
case.
\end{document}
|
