Write a simple histogramming application

Why Histograms?

In high-energy physics experiments, histograms are among the most fundamental data structures. From reconstructing particle masses from collisions to monitoring detector health, the ability to bin and analyze distributions efficiently is a core competency for research software engineers. You will encounter them in trigger decision systems, calibration pipelines, and virtually every analysis notebook you open. (Granted, most of the time you will be reusing existing histogramming facilities, though.)

Learning Objectives

By the end of this exercise you will be able to:

  • Set up a CMake project with custom build-and-run targets and generator expressions
  • Generate reproducible random data using <random>
  • Format and print output with std::print / std::println
  • Choose container types based on access-pattern requirements, not convenience
  • Measure wall-clock time and hardware counters with hyperfine and perf stat
  • Diagnose the performance impact of Debug vs. Release compilation modes
  • Structure a multi-file project with headers, shared libraries, and CMake targets
  • Evaluate trade-offs between error-handling mechanisms (bool, exceptions, std::optional, std::expected)
  • Articulate design decisions when building reusable library interfaces

Set up CMake

Create a new directory in your repo

cd ~/src/exercises
mkdir histograms
touch histograms/main.cpp

Add a histograms/CMakeLists.txt file:

add_executable(hist main.cpp)

and add the directory to the toplevel CMakeLists.txt:

add_subdirectory(histograms)

Add and commit to the git repo:

git add histograms/CMakeLists.txt histograms/main.cpp CMakeLists.txt
git commit

On commit messages

Write a commit message that lets you understand what changed without reading the diff. As the official git-commit documentation recommends:

begin the commit message with a single short (no more than 50 characters) line summarizing the change, followed by a blank line and then a more thorough description.

Also consider git’s documentation on how to describe changes when submitting patches:

The goal of your log message is to convey the why behind your change to help future developers.

Always practice writing good commit messages

Implement a simple C++ application

Edit main.cpp

  1. Fill a container data with N random floating-point values, using a normal distribution with \(\mu = 0\) and \(\sigma = 1\). (use a constant seed for reproducibility)
    • Start small (e.g., N = 40) so you can inspect output easily.
    • Later you can try orders of magnitude larger: 1000, 100'000, … up to Gigabytes of memory?
  2. Print all values (simple verification).

Build like this:

cmake --build build

Documentation

Commit to git

Extend CMakeLists.txt with a build-and-run target

  1. Define a function(add_runnable name) which calls add_executable
  2. Change add_executable(hist main.cpp) to add_runnable(hist main.cpp).
  3. Use add_custom_target to add a run_${name} target.
  4. The path to your binary is $<TARGET_FILE:${name}>, a “generator expression”.
  5. cmake --build build -- run_hist builds and executes in one step.

Documentation

Commit to git

Create and print a histogram

Define n_bins = 21.

  1. Remove the println from before.
  2. Choose a data structure for computing a histogram.
  3. Iterate over data and fill the histogram.
  4. Use std::string(count, '#') to print a simple histogram.
  5. Scale as needed for your terminal.

Example output:


#
###
########
##################
###############################
######################################################
############################################################################
###############################################################################################
####################################################################################################
#############################################################################################
############################################################################
####################################################
###############################
#################
########
###
#

Bin boundaries are a design decision

Think about what happens at the edges: Is your interval [a, b) or [a, b]? What if a value equals exactly max? Different use cases demand different conventions: a particle physics analysis might want right-edge-inclusive bins so no event is silently dropped, while a real-time monitoring system might clamp outliers to the nearest bin. Document the convention you choose and why. You will revisit this trade-off in the Software Design section below.

Commit to git

Performance

Let’s consider performance.

  1. Build with -v to see the call to g++. Inspect the compiler flags.
  2. ls -l build/hist: Note down the binary size.
  3. Run hyperfine build/hist (if the time is below 300ms, increase N)
  4. Run perf stat build/hist (prepend taskset 1 to inhibit cpu-migrations)

What are you measuring?

  • Can you map your measurements to parts of your code?
  • If you cannot, what could you do to estimate or measure more precisely?

TIP

Consider random number generation vs. histogramming …

Keep a measurement log

Keep notes of whatever numbers you find important / interesting.

Configure in “Release” mode

  1. CMake defaults to an empty CMAKE_BUILD_TYPE
  2. use ccmake on the build directory to set it to Release
  3. Redo hyperfine and perf stat

CMake defaults

I disagree with the CMake build type default. Whenever you get a package and just build it with defaults you typically get an unoptimized Debug build. IMHO, the default should be Release or RelWithDebInfo.

Whenever you change the build type, CMake ensures everything get’s rebuild accordingly. (You still need to run ninja / cmake --build build, though.)

Experiment with -fhardened and make an out-of-bounds access trigger it.

Use the right tools

  • Did you use a std::map, as in the cppreference example? Consider a std::vector<int> or a std::array.
    • How do you decide vector vs array?
  • Try with std::deque and see what perf stat tells you.
  • Try with std::list and … oh 😉
    • Try make it work, anyway. Can you see the pointer chasing implementation via perf? Or maybe even via vir_inspect.sh?

Commit to git

(you might want to go back to this state to compare and maybe even git branch from here)

Extracting a Library — headers, shared objects, and CMake targets

As your codebase grows beyond a single file, keeping everything in one translation unit becomes unwieldy. In real-world software, the core algorithms often live in libraries that multiple executables link against. This section teaches you to extract the histogramming logic into a shared library.

Split main.cpp into a header and an implementation

  1. Create histograms/histogram.h and histograms/histogram.cpp
    • Determine what can move from main.cpp at this point.
    • Add the necessary #include directives
  2. Try to #include "histogram.h" twice. If it doesn’t work, you need an include guard.

Your directory should now look like:

histograms/
  CMakeLists.txt
  main.cpp          # main() — generates data, drives the workflow
  histogram.h       # public interface
  histogram.cpp     # implementation

histogram.cpp may be empty at this point

However, for the sake of the following task, just add something. E.g.

int this_is_just_for_testing(int x) {
  return x + 1;
}

Build a shared library with CMake

Edit histograms/CMakeLists.txt:

add_library(histogram SHARED histogram.cpp)
target_include_directories(histogram PUBLIC ${CMAKE_CURRENT_SOURCE_DIR})

add_runnable(hist main.cpp)
target_link_libraries(hist PRIVATE histogram)

Key concepts:

  • add_library(name SHARED sources) creates a shared library. Use STATIC to create a static library instead.
  • target_include_directories(target PUBLIC ...) tells consumers of this target where to find its headers. Using PUBLIC propagates the include path to anything that links against this library.
  • target_link_libraries(executable PRIVATE lib_target) links the library and inherits its PUBLIC properties (like include directories).

Verify the build works: ninja -v hist

Shared vs. static library

Also inspect how static libraries are built and used.

add_library(histogram STATIC histogram.cpp)

Rebuild with -v and inspect the output.

  • A static library (libhistogram.a) is an archive of object files. The linker copies its contents directly into your executable at link time.
  • A shared library (libhistogram.so) is loaded at runtime. Multiple executables can share a single copy in memory.

For this exercise either works. In general, shared libraries are more common because they can reduce memory usage and can be updated without rebuilding every executable.

Inspect the binary

Use nm, ldd, objdump -t, and objdump -T on the build artefacts (executable and libraries).

Why PUBLIC vs PRIVATE on include directories?

target_include_directories accepts a visibility keyword:

  • PUBLIC: the include path is needed both to compile the library itself AND by code that includes the library’s headers. Propagates to linkers.
  • PRIVATE: the include path is only needed to compile the library itself. Does not propagate.
  • INTERFACE: the include path is not needed for the library itself, but IS needed by consumers. Propagates to linkers.

Since histogram.h is a public header that consumers include, PUBLIC is correct here. If the library had internal helper headers consumed only by histogram.cpp, those would be PRIVATE.

Commit to git

… after you changed it back to SHARED and removed any dummy functions.

Software Design — build a generic histogram library

Code that survives beyond its author has a different contract than throw-away scripts. Functions with clear single responsibilities compose predictably. Interfaces that express their constraints at the call site prevent misuse before it reaches production. Error handling that encodes success or failure in the type system forces callers to confront exceptional paths explicitly rather than silently discarding them. Apply those principles here.

List requirements and use cases

Consider how you should design this if it were not a throw-away project but rather intended to be used and re-used for 20 years and more.

  • How is your library going to be used?
  • Try to follow C++ standard library patterns.
    • Trying is more important than perfection (whatever that is)
  • Think of a few different use cases that could influence your design flexibility. E.g.
    • The user knows the number of bins at compile time
    • The code computes the number of bins at run time

Handle out-of-range values to the histogram

A std::map is able to handle any possible key value. A std::vector or std::array would have a certain size and not expand. How did you handle values that don’t “fit” into the histogram range? The normal distribution allows values that are far away from the mean.

  • Do you have one monolithic function that does everything?
  • Cut it into the smallest logical entities you can find, and give everything a good name (function names, mostly).

You should arrive at a point where you have a function (in histogram.h) that determines (and returns) the index in the histogram. That index can be out-of bounds.

Try different approaches:

  1. just return an unsanitized index value and let the caller check it
  2. Only return a valid index into the histogram, but now you need to signal out-of-bounds. Try all your options:
    1. Return bool.
    2. Throw an exception.
    3. Return std::optional
    4. Return std::expected.
    5. Anything else?

Discuss

  • Discuss with your partner what you think the trade-offs in your current case are.
  • If you decide one is best, can you imagine why it’s not always the best solution? In other words, is it useful that C++ allows different mechanisms?

Commit to git

results matching ""

    No results matching ""