ExpressivePi.cpp

// Expressive Pi
// -------------
//
// Fluent C++ Blog Post: The Pi Day Challenge for Expressive Code
// http://www.fluentcpp.com/2017/03/02/the-pi-day-challenge-for-expressive-code-in-c/
//
// Author: William Killian
// Email:  william.killian@gmail.com
// Github: http://www.github.com/willkill07
// Website: https://www.eecis.udel.edu/~wkillian
//
// ================================================================================
//
// 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.

// Notes:
//  - requires a C++1z compiler with support for WG21 P0184 (http://wg21.link/P0184)
//  - This was my first time using Range-V3 (https://github.com/ericniebler/range-v3)
//  - 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

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

using RealType = double;
using RandomNumberGenerator = std::mt19937;
using Distribution = std::uniform_real_distribution<RealType>;
using DistributionParams = typename Distribution::param_type;
using Point = std::array<RealType, 2>;

auto generatePoint(RealType radius) {
  static RandomNumberGenerator rng(std::random_device{}());
  static Distribution dist;
  dist.param(DistributionParams{-radius, std::nexttoward(radius, 2 * radius)});
  return [radius] {
    return Point{{dist(rng), dist(rng)}};
  };
}

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

int pow10(int raised) {
  return std::pow(10, raised);
}

int main() {
  const auto RADIUS_SIZES  = ranges::view::ints(0, 10) | ranges::view::transform(pow10);
  const auto POINTS_COUNT  = ranges::view::ints(0, 8) | ranges::view::transform(pow10);
  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 RealType MY_PI       = 4.0 * static_cast<RealType>(POINTS_IN_CIRCLE) / points;
      const RealType PI_ERROR    = std::abs(MY_PI - M_PI);
      printf(" %0.6lf", PI_ERROR);
    }
    putchar('\n');
  }
  return EXIT_SUCCESS;
}

Makefile

CXX := /usr/local/opt/llvm/bin/clang++
CXXFLAGS := -O3 -march=native -std=c++1z -Wall -Wextra -pedantic-errors
CPPFLAGS := -I/opt/range-v3/include

.PHONY: all

all : ExpressivePi

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.

I made a small update since the PiDay contest.

The uniform_real_distribution is now static and I set the params each time I call generate. This removes a lot of boilerplate code generation during each loop iteration. Runtime went from ~5.2s on my laptop down to 3.7s

I also attempted to make the power-of-ten generation easier to understand (view::ints(0,upper) | view::transform(pow10)) instead of creating an infinite range and taking the first 8 (or 10).