Hello, and welcome to C++Weekly. I'm your host Jason Turner, available for code reviews
and on-site training. Now there's a decent chance that you have seen this video from
Dave's Garage, and I say a decent chance because Dave here has had at this moment 263,000 views of
this particular video. This is a software drag race of C++ versus Python versus C#,
and it's for doing a calculation counting the number of primes up to a certain integer with a
prime sieve. Dave made the source code available on GitHub and I thought since I do C++ things
I would check it out. First of all definitely not the first person to check it out, but I noticed
something simple and if you've seen the title of this episode you're probably thinking, "Well duh,
obviously if you repeat your work you're going to get slow results," but I was looking at Dave's
code and I saw something that really jumped out at me. We'll take a look at that in this
episode.
So this is on PlummersSoftwareLLC/primes and as you can see there's a whole lot more
implementations - basic C and such, not just the C++, Python and C# ones from the episode. So I've
got PrimeCpp.cpp up and it is currently listed as solution_1. This was the original solution as
far as I can tell. Now I was reading through this code and I, starting at the bottom where this code
actually runs, noticing that the sieve here is actually being constructed on each loop iteration.
Construct the sieve, run the sieve, count the number of passes, which immediately makes me ask,
"Well, what is happening each time the constructor is called for the sieve?" So let's go ahead and
scroll up here (and this is the prime sieve) and we can see that it actually has this private
const map resultsDictionary. Now the only reason this results dictionary exists is for the
validateResults, so for each run, the run is made, printResults validates the results right here,
and it tells you how many passes were made and whether or not it was correct. If the counts that
were performed were the expected number of counts - so the number of primes up to the value 10
is what 1, 3, 5, 7, right, and I'm not going to count the primes up to the value 100 but that's
how you end up with four here. This immediately jumps out at me - this resultsDictionary
is actually being constructed on each iteration here. That results map is constructed for each
loop of this "while" loop here; so passes=0 and for each loop passes is incremented,
the sieve is constructed, it's run, passes incremented. If five seconds have passed,
then it prints the results based on the number of passes that were performed,
and then it loops back around. So for each loop, each time it creates a sieve it's having to
create this map. If you're not familiar with C++ std::map that means this is having to do 1, 2, 3,
4, 5, 6, 7, 8, 9, 10 heap allocations and construct a balanced red black tree effectively,
and that's a fair bit of work, which makes me wonder how much is Dave's test
actually testing the cost to construct the map that only exists for validating the results
of actually calculating how much time it took, or how efficient it was to actually run the sieve
and count all the primes. So of course I put this into quick-bench that's "quick dash bench.com"
and I will remember to have some links at the bottom of this description here so that you can
go back and look at these yourselves. I've got two versions here which is copied from a slightly
older version of this but I've got a namespace for Dave and a namespace for Jason. So I'm doing
a quick-bench comparison of Jason versus Dave. Now I had to comment out this DoNotOptimize. For
some reason that is completely lost on me, I can't actually compile if I have the DoNotOptimize here,
but as you can see it is clearly not optimizing away the use of this sieve variable. It is clearly
actually doing this work otherwise it wouldn't be taking such a long amount of time here; and as you
can see at the moment they are equivalent. Okay, so at the moment my version is identical to Dave's
version - they take the exact same amount of time, and it is not an insignificant amount of time
so I wondered just simply what would happen if I made my map into a static const map and I am
going to use what is known as a Meyer's singleton to some people, utilizing the "construct on first
use" idiom, so this is effectively the result of that. I have a static const auto reference here,
return value from a function called myDict, and then I am constructing a static const map. That
is this dictionary. Now the first time this function is entered, the map will be created.
Each subsequent time after that that this function is entered, the runtime will do a check to see
if the map has been created. If it has not been created then it will create the map. So that's all
I've done, and then I wrapped this in this little handy function here, and I have to call myDict
three times in the validateResults function. So that's the only difference now between
my sieve and Dave's. So let's go ahead and run this benchmark again. So we can see here with
clang 12-03 with my modifications that I got a 10% faster run, and that's simply by not re-running
the work every time of creating this map on every iteration - this map that's not even used for the
actual calculation - this map that's only used for validating the data. Now this is a perfectly fine
and safe thing to do since this is const data. If this was a non-const map and I was mutating it
then I really don't want to make this global data, but as a compile time known results
then this seems reasonable and that's with clang. If we look at the GCC 10.3,
then uh, you know, it's a tiny bit faster to have my modified version.
It's not much faster but, yeah, we can see here with clang it's 10% faster, but now you may have,
if you were paying attention, noticed that I said this is a compile time known data,
so of course the better thing to do here would be to make this constexpr. So that's what I've gone
ahead and done here. I have my version which is a constexpr map, and this is a compile-time known
map of int to int of size 8, and I'm initializing it here. Now due to type deduction and such,
I had to go ahead and spell out std::pair here, but it all works exactly the same;
and with clang I still get the same thing - 10% faster with my version. We can see if this makes
any difference with GCC. I know that GCC is quite a bit more um, aggressive, about optimizing its
constructs for usage. Okay, so it still didn't make a whole lot of difference with GCC,
and we're not going to bother digging into why, or where, or not here, but the idea that I wanted to
communicate is "Don't recalculate a value many times when there's a way to do it only once,
and if a value is compile time known then move it to compile time." As we can see this made a pretty
big difference with clang with the benchmarks, but either way it just logically makes more sense,
and that's something I want to try to drive home for just a moment. If you don't mind a lot of
people, or some people, think that I'm like, super focused on the performance aspects here,
and that's really not the goal. It's if something is more correct AND gives better performance,
then that should clearly be the choice, right? I mean the idea that this expected value
set is going to be recalculated each time you run this code that - just simply makes
no sense. This is a compile time constant. It's a universal constant. Let's do those things at
compile time when we can, or at least only do them once for the lifetime of the project when we can.
Uh, so, you know, thanks for watching this episode of C++ Weekly, and you know, be sure to subscribe.
you