Why Output Order Must Be the Same Every Run

Part II · Module 17 · Chapter 17.8 · Why Output Order Must Be the Same Every Run

1. Two Runs, One Input, a Diff

use strict;
use warnings;
use File::Temp qw(tempdir);
use File::Spec;

my $dir = tempdir(CLEANUP => 1);

# two report scripts, identical except that one sorts its keys
my %variant = (
  "unsorted.pl" => 'for my $c (keys %w)      { printf "%-10s %6.2f\n", $c, $w{$c} }',
  "sorted.pl"   => 'for my $c (sort keys %w) { printf "%-10s %6.2f\n", $c, $w{$c} }',
);
for my $name (sort keys %variant) {
    open my $w, ">", File::Spec->catfile($dir, $name) or die "cannot write: $!\n";
    print $w 'my %w = (clk_core => -0.07, clk_ddr => -0.21, clk_io => 0.33,'
           . ' clk_pll => -0.02, clk_usb => 0.05, clk_pcie => -0.11,'
           . ' clk_mem => 0.19, clk_dbg => -0.44, clk_ref => 0.02);' . "\n";
    print $w $variant{$name}, "\n";
    close $w;
}

# run each FOUR times in separate processes and count distinct outputs
printf "%-13s %-24s %s\n", "SCRIPT", "distinct outputs in 4 runs", "two runs ever differ?";
for my $name (sort keys %variant) {
    my %seen;
    for (1 .. 4) {
        my $out = `cd '$dir' && perl $name`;
        $seen{$out} = 1;
    }
    my $many = keys(%seen) > 1;
    printf "%-13s %-24s %s\n", $name,
        ($many ? "more than one" : "exactly one"),
        ($many ? "YES — a diff is meaningless" : "no — a diff means something");
}

SCRIPT        distinct outputs in 4 runs two runs ever differ?
sorted.pl     exactly one              no — a diff means something
unsorted.pl   more than one            YES — a diff is meaningless

The unsorted script produced more than one distinct output across four runs of identical input. The sorted one produced exactly one.

That is the whole argument, and the consequence is worth stating in the terms a flow cares about. If diff yesterday.rpt today.rpt shows changes when nothing changed, then:

• nobody can use the diff, so nobody looks at it
• a real regression hides among the noise
• an automated check comparing the two reports fails every night and gets switched off

Chapter 16.10 made reproducible output one of the five conditions for a trustworthy flow script. This is the measurement behind that condition.

2. The Three Sources of Disorder

use strict;
use warnings;
use File::Temp qw(tempdir);
use File::Spec;

my $dir = tempdir(CLEANUP => 1);

# ---- 1. readdir
for my $f (qw(zebra.v alpha.v mike.v bravo.v yankee.v kilo.v delta.v)) {
    open my $w, ">", File::Spec->catfile($dir, $f) or die "cannot write: $!\n";
    close $w;
}
opendir my $dh, $dir or die "cannot read dir: $!\n";
my @raw = grep { !/^\./ } readdir $dh;
closedir $dh;
printf "1. readdir returned %d entries; already sorted? %s\n",
    scalar @raw, (join(",", @raw) eq join(",", sort @raw) ? "yes" : "NO");

# ---- 2. hash iteration, across separate processes
my $probe = File::Spec->catfile($dir, "keys.pl");
for my $mode ("keys %h", "sort keys %h") {
    open my $w, ">", $probe or die "cannot write: $!\n";
    print $w 'my %h = map { ("clk_$_" => 1) } (1 .. 9); print join(",", '
           . $mode . '), "\n";' . "\n";
    close $w;
    my %seen;
    for (1 .. 6) {
        chomp(my $o = `perl '$probe'`);
        $seen{$o} = 1;
    }
    printf "2. 6 processes, %-16s -> %s distinct ordering\n", "'$mode'",
        (keys(%seen) > 1 ? "MORE THAN ONE" : "exactly one");
}

# ---- 3. glob with braces (the Chapter 17.3 finding)
for my $f (qw(b.v a.sv c.v d.sv)) {
    open my $w, ">", File::Spec->catfile($dir, $f) or die "cannot write: $!\n";
    close $w;
}
my $start = File::Spec->curdir();
chdir $dir or die "cannot chdir: $!\n";
for my $pat ("*.v", "{*.v,*.sv}") {
    my @g = glob($pat);
    printf "3. glob('%-11s) sorted? %s\n", "$pat'",
        (join(",", @g) eq join(",", sort @g) ? "yes" : "NO");
}

# ---- 4. and the sort that LOOKS right: string order on numbers
my @slack = qw(-0.03 -0.2 0.44 -0.07 0.1 -1.5);
printf "4. sort (default, string)  : %s\n", join("  ", sort @slack);
printf "   sort { \$a <=> \$b }      : %s\n", join("  ", sort { $a <=> $b } @slack);
printf "   same order? %s\n",
    (join(",", sort @slack) eq join(",", sort { $a <=> $b } @slack) ? "yes" : "NO");

1. readdir returned 7 entries; already sorted? NO
2. 6 processes, 'keys %h'        -> MORE THAN ONE distinct ordering
2. 6 processes, 'sort keys %h'   -> exactly one distinct ordering
3. glob('*.v'       ) sorted? yes
3. glob('{*.v,*.sv}') sorted? NO
4. sort (default, string)  : -0.03  -0.07  -0.2  -1.5  0.1  0.44
   sort { $a <=> $b }      : -1.5  -0.2  -0.07  -0.03  0.1  0.44
   same order? NO

Three different mechanisms, three different reasons.

readdir returns entries in filesystem order. Not alphabetical, not creation order, and not the same on a different filesystem. The measurement shows seven files coming back unsorted. Chapter 13.9 covered the call; the fix is sort readdir.

Hash iteration is randomised per process. Perl deliberately randomises the order in which keys walks a hash, as a defence against algorithmic attacks, and the seed differs per process. So the same hash in the same program gives a different order on the next run — which is Chapter 6.6's subject, and the reason it is Chapter 6.6 rather than a footnote.

A braced glob is not sorted. Chapter 17.3 measured this: each alternative is sorted internally, and the alternatives are concatenated in the order you wrote them. glob("*.v") is sorted; glob("{*.v,*.sv}") is not.

The fix for all three is the same word, and it belongs at the point of iteration rather than somewhere earlier:

for my $f (sort readdir $dh)      { ... }
for my $k (sort keys %slack)      { ... }
my @files = sort glob("*.{v,sv}");

3. Sorting Correctly

sort with no comparator sorts as strings, and for a report full of numbers that is wrong in a way that looks plausible.

Section 4 of the block above measures it on real-looking slack values -0.03 -0.2 0.44 -0.07 0.1 -1.5:

sort @slack              ->  -0.03  -0.07  -0.2  -1.5  0.1  0.44
sort { $a <=> $b } @slack ->  -1.5   -0.2   -0.07 -0.03 0.1  0.44

The string sort puts -1.5 after -0.2, because it compares character by character: -0 sorts before -1, and 0.03 before 0.07 before 0.2. The result is monotonic-looking nonsense, and on a worst-slack report the worst path is not at the top.

So:

sort { $a <=> $b } for numbers. Chapter 3.7's <=>.

sort { $a cmp $b } or bare sort for strings. Explicit cmp is better in a script that also sorts numbers nearby, because the reader does not have to remember which default applies.

A two-level sort for a report, which is what you almost always want:

for my $row (sort { $a->{slack} <=> $b->{slack}      # worst first
                 || $a->{pin}   cmp $b->{pin} }      # then by name, for ties
             @rows) { ... }

That second clause is the one people leave out, and it matters: without it, two paths with identical slack can swap places between runs, and you are back to a meaningless diff for exactly the rows a reviewer is most likely to be looking at. Chapter 5.9 covered custom comparators.

4. What Else Must Be Stable

Order is the common failure. Four more things make two runs differ on identical input, and each has a fix.

A timestamp in the output. Chapter 16.10 measured a script that printed localtime into its report, making every line after the header differ. If the report needs a date, put it in a header the comparison skips, or in a separate metadata file.

A process id or job id. $$ in a filename or a header. Fine in a log; never in a report that gets diffed.

An absolute path that includes a run directory. /scratch/jm/runs/alu_1_4412/sim.log differs between runs because the run name does. Print paths relative to the run directory, which is also shorter and more readable:

(my $rel = $path) =~ s{^\Q$rundir\E/}{};

A floating-point value printed at full precision. printf "%.3f" is stable; print $slack can produce -0.0300000000000000006 on one platform and -0.03 on another. Fix the precision in the format and the diff becomes meaningful.

And one that is not about your script at all: the tool's own output order. If a simulator lists coverage items in a non-deterministic order, sorting your parse of it fixes your report even though you cannot fix the tool. That is usually the right place to intervene — Module 18 is about parsing such output, and sorting at the point you build your own structure is the cheapest possible insurance.

5. What To Remember

• A report earns its keep by being compared, and a diff only carries information if both sides agree about order.
• Measured: an unsorted report produced more than one distinct output across four runs of identical input. Sorted, exactly one.
• A diff that changes when nothing changed gets ignored, then switched off, and a real regression hides in it.
• Publish a verdict, not a random value — this chapter's own output reports "more than one" rather than the orderings.
• Three sources of disorder: readdir, hash iteration, and a braced glob.
• readdir returns filesystem order — not alphabetical, not stable across filesystems.
• Hash iteration is randomised per process, deliberately. Chapter 6.6.
• A braced glob concatenates alternatives in written order; plain glob("*.v") is sorted.
• Sort at the point of iteration — sort readdir, sort keys, sort glob.
• Measured: a string sort put -1.5 after -0.2. Character-by-character comparison on numbers is plausible-looking nonsense.
• <=> for numbers, cmp for strings, and write cmp explicitly where both appear nearby.
• Add a tie-breaker — || $a->{pin} cmp $b->{pin} — or equal-slack rows swap between runs.
• Hierarchical names sort oddly but stably. Leave them; stability is the requirement.
• A numeric sort over a column containing INFEASIBLE places it as 0 with no warning. Validate or partition.
• Four more sources of instability: a timestamp, a pid, an absolute path containing the run name, and full-precision floats.
• Print paths relative to the run directory, and fix precision with printf "%.3f".
• Sort your parse of a tool's output when you cannot fix the tool's order.

Chapter 17.9 closes the module with the check that catches a flow step which silently did not run. Comparing two modification times sounds simple, and the resolution of the timestamps turns out to decide whether the check works at all.