The Pi Day Challenge for the Most Expressive Code – Results

Today is Pi Day!! To celebrate, we launched a challenge for the most expressive code on Fluent C++, and today is the outcome of this challenge!

Thank you so much for all of you that submitted a solution. I sincerely hope that you enjoyed participating to this challenge, and learned some things in the process.

And even though there is only one winner, every one gets to eat a slice of pie today. As pies, as you would have guessed, are a typical treat for Pi Day.

The challenge

The challenge consisted in writing expressive code that computed various estimates of Pi by generating random points inside a circle, and find out which parameter (radius or number of points) influences more the precision of this estimate. If you want to see all the details, head over to the description of the challenge.

The winner

The winner of this challenge is… William Killian! Congratulations William!

William is a Ph.D. student at the University of Delaware, and his focus is on parallel runtimes, performance portability, and machine learning. You can visit his website and congratulate him too, for winning the Fluent C++ Pi Day challenge for the most Expressive code.

Note that I have personally reviewed each solution, and I must say that there were other very good pieces of code too. But there has to be only one winner, and William came out first.

Also, note that I’m not the only one to elect the winner. I show submitted solutions to the youngest person of my team, for him to tell which piece of code he has the easiest time understanding (and I provide any necessary information about external libraries so that there is no bias about that).

Our winner made some choices as to which abstractions to represent in its code. Let’s take a closer look to that.

A solution

Of course, there were many ways to go about solving this problem. Here is William’s.

First off here are the copyright terms that accompany the code and that I have to mention:

Copyright 2017 William Killian
//
// Redistribution and use in source and binary forms, with or without modification,
// are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
//    list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
// IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
// INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

William starts by explaining how he proceeds to make code expressive:

I thought the most expressive way to solve this problem was to:
1. Eliminate functions from doing more than one thing
2. Eliminate confusing chains of expressions as a single line of code
    * In general, breaking up expressions is perfectly valid, and the compiler
    often sees no difference (and sometimes it even helps!)
3. Give sensible variable names to avoid any potential confusion
4. Use const wherever data does not need mutated

Here is his actual solution:

#include <array>
#include <random>
#include <cmath>
#include <cstdio>
#include <range/v3/algorithm.hpp>
#include <range/v3/view.hpp>

using Point = std::array<double, 2>;

auto generatePoint(double radius) {
  static std::mt19937 rng(std::random_device{}());
  return [radius] () -> Point {
    std::uniform_real_distribution<double> dist{-radius, std::nexttoward(radius, 2 * radius)};
    return {{dist(rng), dist(rng)}};
  };
}

auto checkWithinCircle(double radius) {
  return [radius] (const Point &p) -> bool {
    return std::hypot(std::get<0>(p), std::get<1>(p)) <= radius;
  };
}

template <size_t Base, typename T = int>
T pow(const T raised) {
  return std::pow(Base, raised);
}

int main() {
  const auto POWERS_OF_TEN = ranges::view::ints(0) | ranges::view::transform(pow<10>);
  const auto RADIUS_SIZES  = POWERS_OF_TEN | ranges::view::take(10);
  const auto POINTS_COUNT  = POWERS_OF_TEN | ranges::view::take(8);

  for (int radius : RADIUS_SIZES) {
    for (int points : POINTS_COUNT) {
      auto GENERATED_POINTS      = ranges::view::generate_n(generatePoint(radius), points);
      const int POINTS_IN_CIRCLE = ranges::count_if(GENERATED_POINTS, checkWithinCircle(radius));
      const double MY_PI         = 4.0 * static_cast<double>(POINTS_IN_CIRCLE) / points;
      const double PI_ERROR      = std::abs(MY_PI - M_PI);
      printf(" %0.6lf", PI_ERROR);
    }
    putchar('\n');
  }
  return EXIT_SUCCESS;
}

As a bonus, William has performed some measurements on the memory consumption of his solution. Note that this was absolutely not mandatory, and that the outcome of the challenge was based on his solution only. But I find these notes very interesting, so let me share them with you to learn about how ranges behave regarding memory:

Fun fact: I nerd-sniped myself and investigated the total memory consumption of the program

Using the massif utility within valgrind I discovered that there is never more than 79376B allocated across the heap and stack.. Looking deeper into the 79,376B, most of the usage comes from iostream and friends.

• Even in a simple hello world program in C++, 72704B gets allocated on the heap. Boo 🙁
• static and global initialization consumes up to 6672B on the stack

And that’s where we get our maximum memory usage — before our program is actually run.

During runtime in main, the overhead is pretty low. We still have the 72704B allocated in the heap from libstdc++

• Only 1024B is allocated on the heap for printfs buffer
• A peak of 360B is allocated on the stack within main

What does this mean? Using ranges eliminates the storage requirements for generated data that can be processed on the fly. Up to 2e7 random double-precision numbers (two for each point with 10M points) no longer need generated or stored. Mind you, that adds up to 160,000,000B, or about 150,000x more heap space than what the range version uses.

Bottom line: using ranges with lazy evaluation is not only more elegant, but also eliminates a lot of temporary storage otherwise thought necessary.

His complete submission on gist can be found here.

Time to eat a slice now

If you have participated to this challenge, I sincerely hope that you enjoyed it. If you have remarks on how you would have enjoyed it better, feel free to let me know.

If you haven’t participated, I hope you’ll make it next time!

And whichever way, why don’t you tell us what you do today to celebrate Pi Day? Just drop a comment below, and show us a picture if you can take one!!

Don't want to miss out ? Follow:   
Share this post!