Code Complexity#

The code-complexity workflow computes the classic Halstead measures [Halstead1977] (volume, difficulty, effort, language level, …) and line-based size metrics for a set of C++ and GPU source files. All formulas follow Halstead’s original definitions; see References for the source and Halstead metric definitions for the concrete expressions used here.

Its distinguishing feature is that it understands the constructs of GPU/parallel programming paradigms and counts them as dialect operators, so you can quantify how much syntactic surface a paradigm adds on top of the plain C++ baseline.

Note

This workflow is stand-alone. It has no dependency on the benchmark or plotting parts of ppbcc and works on any C++/GPU source tree.

Command line#

# Analyse a directory recursively, auto-detect the dialect of every file,
# print the table and save it as CSV:
ppbcc code-complexity path/to/src -o report.csv

# Force a dialect (several may be combined), restrict the metrics, and
# additionally report the plain-C++ baseline and the paradigm's delta:
ppbcc code-complexity src/kokkos -d kokkos -m halstead loc --diff -o kokkos.csv

# Aggregate all files into an additional TOTAL row:
ppbcc code-complexity src/cuda -d cuda --aggregate

# Disregard instrumentation: invocations of and conditionals on the matching
# macros, and the headers defining them (see "Excluding code" below):
ppbcc code-complexity src --exclude-macro 'PPB_MARKER_\w+' PPB_PROFILING \
    --exclude-header common/Marker.h common/Profiling.h

# More logging: -v (DEBUG), -vv (TRACE); the default level is INFO.
ppbcc code-complexity src -vv

# List all known dialects and their aliases:
ppbcc code-complexity --list-dialects

A run on a single Kokkos implementation looks like this:

$ ppbcc code-complexity src/matrixMultiplication/kokkos \
    -m sloc halstead_volume halstead_difficulty dialect --table-format github

INFO | Analyzing with automatic per-file dialect detection
INFO | Analyzing 3 source file(s)

| file                     | dialect | sloc | volume  | difficulty | dialect_distinct_operators | dialect_total_operators |
|--------------------------|---------|------|---------|------------|----------------------------|-------------------------|
| .../kokkos/Impl_Kokkos.cpp | kokkos  |   41 | 2581.89 |    60.2727 |                         12 |                      30 |
| .../kokkos/Impl_Kokkos.h   | cpp     |   14 |  412.26 |    16.3333 |                          0 |                       0 |
| .../kokkos/main.cpp        | kokkos  |   20 |  616.56 |    12.6452 |                          1 |                       1 |

Note that Impl_Kokkos.h is auto-detected as plain cpp — automatic detection is per file, not per directory.

The full option list is in Command Line Interface, or run ppbcc code-complexity --help.

Python API#

from pathlib import Path
from ppbcc.code_complexity import evaluate

frame = evaluate(
    sources=[Path("src/")],            # files and/or directories
    language_dialect="auto",           # or "cpp", "kokkos", "cuda,openmp", ...
    metrics=["halstead", "loc"],       # None = all metrics
    diff=True,                         # add baseline_*/delta_* columns
    aggregate=False,                   # add a TOTAL row
    output=Path("report.csv"),         # optionally write the CSV directly
)
print(frame[["file", "dialect", "effort", "delta_effort"]])

The result is a pandas.DataFrame with one row per file.

Excluding code#

A benchmark usually carries code which is not part of the algorithm under study, profiler region markers being the typical example. Counted as-is, it inflates every implementation by the same boilerplate. Two exclusions remove such code before the analysis, so the metrics are those of the program as if it had never been added:

--exclude-macro REGEX ... / exclude_macros

Regular expressions matched against whole macro names.

An invocation is removed together with its argument list and a directly following ; — PPB_MARKER_GPU_SCOPE("evaluate"); disappears.
A conditional on the macro (#ifdef, #ifndef, #if defined(...), #if !defined(...), #if NAME) is resolved as if the macro was undefined: the branch the preprocessor would drop goes, the other branch stays, and so does an #elif that takes over. A condition which combines the macro with others is left untouched, with a warning.

--exclude-header GLOB ... / exclude_headers

Glob patterns matched against the spelling of an #include and against the tail of a file path. The header is not analysed, and its #include lines are removed.

A line which held nothing but removed code — and possibly a comment behind it — is removed as a whole, so loc and sloc shrink along with the Halstead counts. Ordinary functions are not touched: a call such as profiling::initialize(&argc, argv) is code like any other.

frame = evaluate(
    sources=[Path("src/")],
    exclude_macros=[r"PPB_MARKER_\w+", "PPB_PROFILING"],
    exclude_headers=["common/Marker.h", "common/Profiling.h"],
)

Halstead metric definitions#

Let \(n_1\) and \(n_2\) be the number of distinct operators and operands, and \(N_1\) and \(N_2\) their total number of occurrences. ppbcc derives Halstead’s measures [Halstead1977] exactly as originally defined:

Measure	Formula	Column
Vocabulary \(\eta\)	\(n_1 + n_2\)	`vocabulary`
Length \(N\)	\(N_1 + N_2\)	`length`
Calculated length \(\hat{N}\)	\(n_1 \log_2 n_1 + n_2 \log_2 n_2\)	`calculated_length`
Volume \(V\)	\(N \log_2 \eta\)	`volume`
Difficulty \(D\)	\(\frac{n_1}{2} \cdot \frac{N_2}{n_2}\)	`difficulty`
Effort \(E\)	\(D \cdot V\)	`effort`
Time \(T\)	\(E / 18\) seconds	`time_seconds`
Delivered bugs \(B\)	\(V / 3000\)	`delivered_bugs`
Program level \(L\)	\(1 / D\)	`program_level`
Language level \(\lambda\)	\(L^2 \cdot V\)	`language_level`

Degenerate inputs are handled defensively: an empty vocabulary yields a volume of zero, and a program without operands yields a difficulty — and therefore a program level — of zero rather than a division by zero.

Note

\(T = E/18\) and \(B = V/3000\) carry Halstead’s original empirical constants (the Stroud number and the bug-rate estimate). They are reported for completeness; for comparing paradigms, prefer volume, difficulty, or effort, which are what the Navchart and combined charts consume.

Result columns#

Column group	Columns
Identification	`file`, `dialect`
Line metrics	`loc`, `sloc`, `comment_lines`, `blank_lines`
Halstead base counts	`distinct_operators` (\(n_1\)), `distinct_operands` (\(n_2\)), `total_operators` (\(N_1\)), `total_operands` (\(N_2\))
Halstead derived	`vocabulary`, `length`, `calculated_length`, `volume`, `difficulty`, `effort`, `time_seconds`, `delivered_bugs`, `program_level`, `language_level`
Dialect share	`dialect_distinct_operators`, `dialect_total_operators`, `dialect_distinct_operands`, `dialect_total_operands`
With `--diff`	`baseline_<metric>` and `delta_<metric>` for the key Halstead columns

How tokens are counted#

The lexer strips comments and treats string/char literals, numbers, and identifiers as operands; keywords, punctuation, and preprocessor directives are operators. Closing brackets ), ], } pair with their (already counted) opening bracket and are not counted again.
Everything recognised as belonging to a dialect becomes a dialect operator:
- qualified names under a dialect namespace count as one operator (Kokkos::parallel_for),
- dialect keywords (__global__, threadIdx),
- API identifiers matched by patterns (cudaMalloc, cl_mem, vkCreateBuffer),
- CUDA/HIP kernel-launch brackets <<< >>>,
- dialect pragmas (#pragma omp ...), whose clauses are operators and whose referenced variables become dialect operands.
Namespace aliases are resolved: namespace bc = boost::compute; makes bc::vector a Boost.Compute operator.
In auto mode, dialects are detected per file via file extensions (.cu, .hip, .cl, .comp, .wgsl, .slang, …), included headers, pragma prefixes, namespace usage, and characteristic identifier patterns.

Configuration#

Keyword and dialect definitions live in TOML files packaged under src/ppbcc/code_complexity/share/ (cpp_keywords.toml, dialects.toml). They ship inside the package so pip-installed wheels carry them. Both can be replaced at runtime with --keywords-config / --dialects-config (CLI) or keywords_path / dialects_path (API).

Adding a new dialect is a matter of adding a [dialects.<name>] table — no code changes required.

Applied example: analysing a whole benchmark suite#

The CLI works well for a directory of files, but a real study usually needs finer control: several implementations may share one directory, a shader may belong to two hosts at once, and each logical implementation — not each file — should become one row.

The companion repository performance-portability-benchmark solves this with a script (scripts/generate_code_complexity.py) built on the Python API. It is a good template for your own study. The pattern has four parts.

1. An explicit implementation manifest. Every logical implementation names the files it owns, so variants sharing a directory stay separate:

@dataclass(frozen=True)
class Implementation:
    problem: str
    framework: str
    dialect: str
    sources: tuple[str, ...]

entries = [
    impl("MatrixMultiplication", "Cuda[Naive]", "cuda",
         "matrixMultiplication/cuda/Impl_CudaNaive.cu",
         "matrixMultiplication/cuda/Impl_CudaNaive.cuh"),
    impl("MatrixMultiplication", "Cuda[SharedMemory]", "cuda",
         "matrixMultiplication/cuda/Impl_Cuda.cu",
         "matrixMultiplication/cuda/Impl_Cuda.cuh"),
    # The same Slang shader is counted once with its CUDA host …
    impl("MatrixMultiplication", "Slang-Cuda", "slang,cuda",
         "matrixMultiplication/slang/Impl_SlangCuda.cu",
         "matrixMultiplication/slang/MatrixMultiplicationShader.slang"),
    # … and once with its Vulkan host.
    impl("MatrixMultiplication", "Slang-Vulkan", "slang,vulkan",
         "matrixMultiplication/slang/Impl_SlangVulkan.cpp",
         "matrixMultiplication/slang/MatrixMultiplicationShader.slang"),
]

Note how dialect may combine paradigms ("slang,cuda"): a Slang host program written against the CUDA runtime is both.

2. Transitive local includes. Seed files are expanded by following quoted #include directives, so shared definition headers are attributed to every implementation that pulls them in:

def local_dependencies(source: Path, seed_sources: tuple[str, ...]) -> tuple[Path, ...]:
    """Resolve repository-local quoted includes and common implementation units."""
    pending = [(source / relative).resolve() for relative in seed_sources]
    selected: set[Path] = set()
    while pending:
        path = pending.pop()
        ...  # parse `#include "..."` lines, resolve, and push onto `pending`
    return tuple(sorted(selected))

3. One aggregated row per implementation. evaluate is called per implementation with aggregate=True and the raw Halstead counts. The TOTAL row merges operator/operand sets before recomputing, so distinct counts are implementation-wide instead of a sum of per-file counts:

from ppbcc.code_complexity import AUTO_DIALECT_NAME, evaluate, save_csv

AGGREGATE_METRICS = (
    "sloc",
    "distinct_operators",
    "distinct_operands",
    "total_operators",
    "total_operands",
)

frame = evaluate(
    sources=list(sources),
    language_dialect=AUTO_DIALECT_NAME if dialect is None else dialect,
    metrics=list(AGGREGATE_METRICS),
    aggregate=True,
)
total = frame.loc[frame["file"] == "TOTAL"].iloc[0]

Instrumentation which is not part of any implementation is excluded in the same call (see Excluding code); the script passes its profiler region macros and headers as exclude_macros=[r"PPB_MARKER_\w+", "PPB_PROFILING", ...] and exclude_headers=["common/Marker.h", "common/Profiling.h"], and skips those headers when it resolves the local includes.

Important

Emit the raw counts (\(n_1, n_2, N_1, N_2\)) rather than derived figures. ppbcc p3analysis derives volume, difficulty, and effort from them, so all complexity metrics stay selectable at plotting time via --complexity-metric.

4. Two CSV products. A file-level report for browsing, and the implementation-level report consumed by ppbcc p3analysis:

Name,Framework,SLOC,n1,n2,N1,N2
MatrixMultiplication,Kokkos,548,90,313,2643,1683
MatrixMultiplication,Cuda[Naive],579,100,312,2844,1781
MatrixMultiplication,Slang-Cuda,732,123,402,3136,2027
...

Run it with:

# inside the performance-portability-benchmark repository
python scripts/generate_code_complexity.py --source src --output results/code-complexity

# preview every analysis without executing it
python scripts/generate_code_complexity.py --dry-run

The resulting results/code-complexity/code-complexity.csv is exactly the file passed to ppbcc p3analysis as COMPLEXITY_CSV in Available Plots.

References#

[Halstead1977] (1,2)

M. H. Halstead, Elements of Software Science, in Operating and Programming Systems Series. USA: Elsevier Science Inc., 1977. Catalogue entry.

The performance-portability side of ppbcc builds on a separate body of work; see References.

Code Complexity

Contents

Code Complexity#

Command line#

Python API#

Excluding code#

Halstead metric definitions#

Result columns#

How tokens are counted#

Configuration#

Applied example: analysing a whole benchmark suite#

References#