flyology_cachelines 0.1.1-dev

Flyology Cachelines

Cache-line-aligned storage and cache information for Ada, with no runtime crate dependencies.

The Alire crate is flyology_cachelines; its Ada root package is Flyology_Cachelines. It is a standalone related package in the Flyology repository and does not depend on the Flyology runtime.

The crate is currently available on Linux and macOS. Windows support is not included in this adoption.

Why cache-line-aware storage?

Modern processors maintain cache coherence in cache-line-sized units. Two Ada tasks can update completely different objects and still contend if those objects occupy the same line: each write invalidates the other core's cached copy and the line repeatedly moves between cores. This is false sharing—the program has no logical shared value, but its physical layout creates interference.

Avoiding false sharing requires more than aligning the first object. Every independently written object must start on an appropriate boundary, and its size or array stride must keep the next object out of the same interference region. This crate packages those representation rules into reusable Ada types for stack objects, heap objects, records, and arrays.

The compile-time Destructive_Interference_Size is a conservative spacing policy, not merely the detected physical cache-line size. For example, x86-64 normally reports a 64-byte line while this crate selects 128-byte spacing to also separate adjacent-line prefetch pairs. Runtime cache queries are provided for inspection and capacity planning; they do not change a type's compiled representation.

This crate controls placement only. It does not make values atomic or make unsynchronized concurrent access safe. Use atomic types, protected objects, or clear task ownership independently of the chosen layout.

Choosing a representation

Need	Package or type	Trade-off
Isolate every independently written value	`Flyology_Cachelines.Padded`	Strongest separation; every value consumes one or more whole interference regions.
Keep a known number of same-owner values together	`Flyology_Cachelines.Padded_Groups`	Explicit density; instantiation fails if the group would spill beyond one region.
Pack as many same-owner values as safely fit	`Flyology_Cachelines.Fitted_Groups`	Maximum per-region density; capacity depends on the selected architecture spacing and element representation.
Treat multiple isolated groups as one logical sequence	`Grouped_Array` from either group package	Flat indexing and iteration with physical group gaps; choose standard iteration or `Fast_View` for measured hot loops.

Grouping is an ownership decision: elements within a group may share cache lines and should normally be written by the same task or shard. Values with independent writers should receive separate groups or individual Padded wrappers.

Individually padded values

The generic Flyology_Cachelines.Padded package wraps any definite Ada type. Its Padded type is aligned to a destructive-interference boundary and rounded up to a whole number of boundaries, so adjacent objects do not falsely share the same boundary.

with Flyology_Cachelines.Padded;

procedure Example is
   package Padded_Counters is new Flyology_Cachelines.Padded (Natural);

   Counters : array (1 .. 2) of Padded_Counters.Padded :=
     [others => Padded_Counters.Create (0)];
begin
   Counters (1).Value := Counters (1).Value + 1;
end Example;

Ownership-aware groups

Flyology_Cachelines.Padded_Groups packs an explicit number of elements into one destructive-interference region. Elements inside a group may share cache lines; separate groups cannot share the selected region. This is useful when every group belongs to one task or shard:

with Flyology_Cachelines.Padded_Groups;

package Worker_Counters is new Flyology_Cachelines.Padded_Groups
  (Element_Type => Atomic_Counter,
   Group_Length => 8);

Counters : array (Worker_Id) of Worker_Counters.Group;

Group is itself an array, so one group is directly indexable and iterable:

for Counter of Counters (Worker) loop
   Counter := Counter + 1;
end loop;

The instantiation is rejected at compile time if either its element array or the final aligned representation exceeds one region. It can therefore never silently turn a one-region group into a multi-region object.

Flyology_Cachelines.Fitted_Groups chooses the largest safe element count for the architecture selected by the build:

with Flyology_Cachelines.Fitted_Groups;

package Worker_Counters is new Flyology_Cachelines.Fitted_Groups (Atomic_Counter);

--  Compile-time constant; for an eight-byte counter this is 16 when the
--  selected destructive-interference size is 128 bytes.
Capacity : constant Positive := Worker_Counters.Elements_Per_Group;

Both generics also provide Grouped_Array, which preserves the physical group boundaries while presenting every logical element as one flat sequence:

Counters : aliased Worker_Counters.Grouped_Array :=
  Worker_Counters.Create
    (Element_Count => 2 * Worker_Counters.Elements_Per_Group,
     Initial_Value => 0);

Counters (Worker_Counters.Elements_Per_Group + 1) :=
  Counters (Worker_Counters.Elements_Per_Group + 1) + 1;

for Counter of Counters loop
   Counter := Counter + 1;
end loop;

Flat indexing and mutable iteration cross group boundaries without copying. Length returns the logical element count, and iteration skips unused elements in a partial final group. Counters.Groups remains available when code needs to assign or process whole physical groups directly.

There are two whole-sequence traversal choices:

Direct for Counter of Counters uses the standard Ada iterator protocol. It is the simplest choice and supports constant and mutable containers. GNAT currently implements the class-wide iterator with cursor dispatch, reference objects, and secondary-stack work, which can be expensive in a tiny hot loop.
Fast_View uses GNAT's lightweight Iterable aspect and a cached address cursor. It retains one-level mutable for ... of syntax for measured hot loops.

Using `Fast_View`

Declare the Grouped_Array as aliased, then construct a short-lived view with the container's 'Access. A reusable traversal procedure looks like this:

with Flyology_Cachelines.Fitted_Groups;

procedure Increment_Counters is
   type Counter is mod 2 ** 64 with Atomic;

   package Worker_Counters is new Flyology_Cachelines.Fitted_Groups (Counter);

   procedure Increment_All
     (Container : aliased in out Worker_Counters.Grouped_Array)
   is
      View : Worker_Counters.Fast_View (Container'Access);
   begin
      for Item of View loop
         Item := Item + 1;
      end loop;
   end Increment_All;

   Counters : aliased Worker_Counters.Grouped_Array :=
     Worker_Counters.Create
       (Element_Count => 10_003,
        Initial_Value => 0);
begin
   Increment_All (Counters);
end Increment_Counters;

The same Fast_View (Container'Access) pattern is available from Flyology_Cachelines.Padded_Groups when the group length is chosen explicitly.

The usage rules are:

Fast_View operates on Grouped_Array; a single Group is already an array and can be iterated directly.
The container must be aliased. The view's access discriminant ties its lifetime to that container, and the limited view is intended to remain local to the traversal.
Creating a view allocates no storage and copies no elements.
Iteration is mutable and flat. It visits exactly Length (Container) logical elements, crosses aligned group gaps, and never exposes the unused tail of a partial final group.
The view adds no synchronization. Elements shared between tasks still need atomic operations, protected access, or an ownership scheme.
A constant or read-only traversal should use the standard for Item of Container form instead.

Internally, the cursor stores the current element address, remaining logical element count, and slot within the physical group. Advancing uses the component stride inside a group and the aligned group stride at a boundary. This avoids logical-index division and the class-wide standard iterator machinery.

Fast_View is intentionally opt-in: Iterable is a GNAT-defined aspect and the view is mutable-only. These group packages already target GNAT for their compile-time spill checks; Fast_View adds another explicitly implementation-defined dependency. Use it only after measuring the relevant hot loop. The benchmark reports standard and fast-view traversal separately against explicit group/slot traversal over identical storage.

If even one element cannot fit, instantiation fails. Both generics describe a compile-time destructive-interference region, not necessarily one physical cache line: x86-64 deliberately selects 128-byte regions even though its physical lines are normally 64 bytes. Grouping must be based on common ownership; automatically packing independently written values would recreate false sharing.

The root package also exposes:

Destructive_Interference_Size
Hardware_Cache_Line_Size
L1_Data_Cache_Size and L1_Data_Cache_Slots
L2_Cache_Size and L2_Sharing_Cores
Core_Class, Core_Class_Count, Core_Class_Ordering, Core_Class_Cores, and Core_Class_CPUs
Cache_Query_Result and Value_Or

Runtime cache detection uses sysctlbyname on macOS and /sys/devices/system/cpu on Linux. Linux x86-64 queries CPUID and other Linux targets query sysconf when sysfs describes nothing at all. The host is inspected once, on the first query rather than during package elaboration, and the result is reused because cache geometry is stable for the life of a process. Deferring the inspection matters because describing every core class means reading one description per CPU on Linux, which costs tens of milliseconds on a host with many CPUs; a program that never asks pays nothing. Malformed or failed host queries return (Available => False) rather than an ambiguous default value or a conversion exception.

declare
   Line : constant Flyology_Cachelines.Cache_Query_Result :=
     Flyology_Cachelines.Hardware_Cache_Line_Size;
begin
   if Line.Available then
      Put_Line ("hardware line:" & Line.Value'Image);
   end if;

   --  A fallback is only used when the caller explicitly requests one.
   Put_Line (Flyology_Cachelines.Value_Or (Line, 64)'Image);
end;

The compile-time spacing follows the documented architecture table: 128 bytes for x86-64, AArch64, and PowerPC64; 32 bytes for ARM, MIPS, SPARC, and Hexagon; 16 bytes for m68k; 256 bytes for s390x; and 64 bytes otherwise.

Core classes

A host whose cores are not identical has no single L1 data-cache capacity. The crate groups such a host's cores into core classes, one per distinct cache geometry, and every cache query names the class it describes:

--  Without a class, queries describe the class the host ranks highest.
Fast : constant Flyology_Cachelines.Cache_Query_Result :=
  Flyology_Cachelines.L1_Data_Cache_Size;

for Position in 1 .. Flyology_Cachelines.Value_Or
                       (Flyology_Cachelines.Core_Class_Count, 0)
loop
   declare
      Class : constant Flyology_Cachelines.Core_Class :=
        Flyology_Cachelines.Core_Class (Position);
   begin
      Put_Line
        (Flyology_Cachelines.L1_Data_Cache_Size (Class)'Image & " bytes across"
         & Flyology_Cachelines.Core_Class_Cores (Class)'Image & " cores");
   end;
end loop;

Core_Class_Cores counts physical cores and Core_Class_CPUs counts logical ones. They differ under simultaneous multithreading, where sibling CPUs share one core's L1 data cache: a 24-core host with two threads per core reports 24 cores and 48 CPUs in one class.

Hardware_Cache_Line_Size takes no class. macOS publishes no per-class line size, and the core types of current heterogeneous parts share one line size.

L2 is shared

L2_Cache_Size reports a class's level 2 capacity, and L2_Sharing_Cores reports how many cores share one such cache. The pair matters because L2 is rarely private: a 12P/4E Apple silicon host reports 16 MiB of L2 shared by six performance cores and 4 MiB shared by four efficiency cores, so neither figure is a per-core budget. A server x86-64 part with two threads per core reports 2 MiB shared by one core, which is private. Divide by L2_Sharing_Cores before sizing a per-core working set.

The flat hw.l2cachesize on Apple silicon reports the efficiency cluster, so it understates the performance cluster by a factor of four — the same defect the flat hw.l1dcachesize has at a factor of two. Naming a class avoids both.

How much the order means

Core_Class_Ordering reports what ordered the classes, because that differs by platform and is sometimes an inference rather than a host-reported fact:

Ordering	Meaning
`Host_Reported`	The host published a performance rank and the classes follow it.
`Inferred`	The host published no rank, so classes are ordered by descending L1 data-cache capacity.
`Unordered`	Fewer than two classes exist, or nothing distinguished them.

macOS 12 and later publish per-core-type geometry as ordered performance levels, where hw.perflevel0 is the highest-performing level, so macOS reports Host_Reported. On Apple silicon the flat hw.l1dcachesize reports the efficiency-core capacity: one 12P/4E host reports 65536 bytes for the flat name against 131072 for hw.perflevel0.l1dcachesize. The crate uses the flat name only on a host publishing no performance level, such as macOS 11 and earlier or an Intel Mac.

Linux publishes per-CPU descriptions and no single ordering. Where the kernel publishes cpuN/cpu_capacity — its own measure of relative CPU performance, normalized to 1024 — that value both separates and orders the classes, and the ordering is Host_Reported. Architectures selecting the generic topology code publish it; x86-64 does not, so an x86-64 hybrid part falls back to ordering by descending L1 data-cache capacity and reports Inferred. That inference holds on current hybrid parts, where the higher-performing core has the larger L1 data cache, and carries no meaning on a host whose classes differ some other way.

Why these alignment sizes?

The policy is adapted from the CachePadded implementation in crossbeam-utils, which is available under MIT or Apache-2.0. It is the same policy used by the Rust crate this project ports.

128 bytes: x86-64, AArch64, Arm64EC, and PowerPC64

Starting with Intel Sandy Bridge, the spatial prefetcher can fetch pairs of adjacent 64-byte cache lines. Aligning independent values to only 64 bytes can therefore still create destructive interference through prefetching. The 128-byte spacing keeps independently written values out of the prefetched pair. See Intel's Optimization Reference Manual and Folly's hardware_destructive_interference_size.

AArch64 systems may combine asymmetric cores in a big.LITTLE design, and the larger cores can use 128-byte cache lines. See Mono's ARM64 cache-line discussion. PowerPC64 also conventionally uses 128-byte cache lines, as reflected in Go's PPC64 CPU definitions and the Linux PowerPC cache definitions.

32 bytes: ARM, MIPS, SPARC, and Hexagon

These targets conventionally use 32-byte cache lines. The policy follows the corresponding Go CPU definitions and the Linux architecture cache headers, including Linux SPARC and Linux Hexagon.

16 bytes: m68k

The m68k alignment follows the Linux m68k cache definition.

256 bytes: s390x

s390x uses 256-byte spacing, following Go's s390x CPU definition and the Linux s390 cache definition.

64 bytes: x86, WebAssembly, RISC-V, SPARC64, and fallback

These targets use the common 64-byte alignment. Unknown architectures also default to 64 bytes. Relevant references include Go's x86 CPU definition and the Linux RISC-V cache definition.

Build and test:

alr build
cd tests
alr test

The native test compares the architecture-selected interference spacing with the queried physical cache-line size. The values need not be equal: x86-64 normally selects 128-byte spacing around a 64-byte hardware line. Instead, the compiled spacing must be the architecture's expected value and an exact multiple of the physical line. When the OS reports L1 capacity, the test also checks that it consists of whole hardware lines and that L1_Data_Cache_Slots derives the correct number of interference-sized slots. Tests also distinguish an unavailable query with an explicit 64-byte fallback from a successfully detected 64-byte line.

alr test also compares the five architecture-selected public specifications after normalizing their alignment literal. This prevents the duplicated specs from drifting as the public API or its documentation changes. On Linux, it also invokes the private sysconf and sysfs detectors independently; the ordinary native test exercises the public CPUID-first x86-64 path. On macOS, it invokes the private sysctl reader directly and checks that the reported L1 capacity is the highest performance level the host publishes, and that the flat name is used only when the host publishes no performance level. Compile-fail tests verify that explicit and automatically fitted groups which would spill beyond one region are rejected.

Benchmarks

The nested benchmarks crate compares compact and padded storage under nine workloads. Same-task measurements cover sequential, coprime-stride, hot-set, and standard and GNAT Iterable grouped traversal versus explicit group/slot loops. Multi-task measurements cover isolated hot counters, task-owned compact groups, fitted versus individually aligned groups, interleaved ownership, and contiguous shards. Defaults use one million elements, up to 16 tasks, and three alternating-order samples.

cd benchmarks
alr -n build --release
./bin/benchmarks

See benchmarks/README.md for workload definitions, positional scale controls, memory requirements, and interpretation guidance.

License

Licensed under either the MIT License or Apache License 2.0, at your option. The architecture spacing policy is adapted from Crossbeam's CachePadded; see NOTICE and the repository's LICENSE-MIT and LICENSE-APACHE files.

0.1.1-dev