The serial core of the pure-Fortran sort engine: the ordering, and the introsort over it.
Stages 1 and 2 of feature_sort.md. The comparators decide what order rows go in;
sort_comparison_permutation is the serial sort that uses them. The shipped path still crosses
bind(C) into the C++ engine — this side is reached only when
parquet_debug_use_fortran_sort_engine(.true.) has selected it, which is Stage 2 scaffolding and
goes away at the Stage 6 cutover. What proves this code correct is test/test_sorting.f90, which
asks the C++ engine the same questions — pair by pair for the comparators, whole-permutation for
the sort — and requires the same answers.
Both halves live in one file on purpose. A call from a sibling submodule into sort_row_less
is a call to a global symbol in another translation unit, which no compiler can inline; keeping
the sort beside the comparator is the only thing that leaves inlining possible at all. It is not
sufficient — feature_sort.md §1e-B records that ELF semantic interposition under -fPIC blocks
it anyway on machine B — but a split would remove the possibility on every platform. Do not
separate them for tidiness.
sort_compare_key and sort_tier_of must keep FITTING GCC's default inlining budget, and
nothing fails when they stop. Past the budget GCC splits sort_compare_key into a
sort_compare_key.part.0 clone, inlines a cheap prologue and leaves the body out of line, so the
hot path takes a call on every comparison — on the critical path of a dependent branch chain.
Every answer stays identical and only speed moves: measured on machine A, gfortran 15.2,
--profile release, the serial f64 argsort ran at 1.28x the C++ engine without the split and
0.91x with it, a ~39% swing decided entirely by whether one procedure fit. Two places it hides:
sort_row_less is fully inlined either way, so grepping for a call to it reports success while
the damage sits one level down; and bench/benchmark_sort_comparator.f90 does not see it either,
because a sweep's iterations are independent and the call overlaps with them where a partition's
next iteration depends on this comparison's branch. So anything added to either procedure must
be paid for by taking something else out — a new tier, a new key family arm written inline
rather than behind a call (as compare_bytes already is), a validity scheme needing more than one
test, or a branch hoisted "for clarity" can each cross the threshold, and all of them look free.
The check is one command against a release build, and it must read 0:
nm <build>/.../src_parquet_argsort_engine.f90.o | grep -c 'sort_compare_key\.part'
bench/benchmark_sort_ab.sh sizes the loss once the symbol is seen. The budget is a property of
the compiler and its version, so a future GCC may reintroduce the split with no source change.
Why a submodule rather than a module. sort_key_buf is private to parquet_sorting, so a
standalone module could not see the type these procedures exist to compare.
Each row sits in exactly one tier under each key — value, NaN (real keys only) or null —
and the tiers are absolute: descending reorders within the value tier and never moves a
null or a NaN. Two rows in the same non-value tier compare equal, so they keep file order.
The sort comparator then adds a row-index tiebreaker, which makes it a total order in which no
two distinct rows compare equal. The tie-free comparator is the same walk without that tiebreaker,
and takes an nkeys prefix.
The tier rule is invisible to any ascending, null-free test. feature_sort.md §5.1 calls it
"the single most likely thing to get wrong here". A comparator that applies descending before
the tier test passes every ordinary test and silently moves nulls to the other end of a descending
sort.
String keys compare like memcmp, not like Fortran. Fortran's own < on character blank-pads
the shorter operand, so "ab" == "ab "; std::string_view::compare — which this must reproduce
exactly — treats a prefix as less, so "ab" < "ab ". compare_bytes below does it byte by byte
and then by length, and reads each byte as unsigned, because char_traits<char>::compare is
memcmp and a byte ≥ 128 must sort high.
sort_row_less and sort_keys_compare are one decision expressed twice, and feature_risks.md
Risk-34 is about them never drifting apart. Both walk the keys in precedence order and both
delegate every actual comparison to sort_compare_key. A change to one is a change to the other.
Every dummy here is a plain type(sort_key_buf), never class. Passing a type(T) actual to a
class(T) dummy across compilation units makes ifx build a runtime class descriptor in the
caller's prologue — one record per allocatable component, and sort_key_buf has five — which
this library has already measured at ~35 ns per call on a comparable type. Nothing in this file
may become polymorphic, and the objdump check in CLAUDE.md's typed-accessor-tier section is what
confirms it.
An earlier note here said Stage 2 was where the value arrays get hoisted — resolving
keys(k)%ints/%reals into local contiguous pointers once, rather than re-reaching through the
derived type on every comparison. It was not done, and the reason is worth recording: hoisting
means a comparator that takes the hoisted state, i.e. a second expression of the ordering, and
feature_risks.md Risk-34 is precisely about those two never drifting apart. That is a real cost
against an unmeasured gain, so it stays a measurement to take later rather than a design decision
taken now — and if it is ever taken, the hoisted comparator must be generated from the same source
as this one, not written twice.