Perl Part II · Module 23 · Static Timing Analysis Report Parsing
Top-N Endpoints and Slack Histograms
A timing report can hold a hundred thousand endpoints, and nobody reads a hundred thousand rows. Two views make it reviewable: the worst N endpoints, and a bucketed distribution. Both are a few lines of Perl, and all three of the obvious ways to write those lines are wrong in a way that still prints a clean table — a slice that invents elements, a bucket that is twice as wide as the others, and a tie that comes out in a different order every time you run it.
Advanced13 min readPerlPart IISTA Reports
Part II · Module 23 · Chapter 23.10 · Top-N Endpoints and Slack Histograms
1. The Twenty That Matter
The fixture for this chapter is bigger than the one the rest of the module used, because four endpoints cannot show a distribution. It is a four-lane sixteen-bit adder block — 208 flops and 423 gates — whose netlist was checked against a behavioural reference by simulation before any timing was derived from it.
use strict;
use warnings;
use POSIX qw(floor);
# ---- 1. the population: every endpoint and its slack, from one report
my %slack;
{
open my $fh, "<", "reports/block_slow.pt.rpt" or die "report: $!";
my $ep;
while (my $l = <$fh>) {
$ep = $1 if $l =~ /^\s*Endpoint:\s+(\S+)/;
if (defined $ep && $l =~ /^\s*slack \((MET|VIOLATED)\)\s+(\S+)/) {
$slack{$ep} = $2 + 0;
undef $ep;
}
}
close $fh;
}
printf "endpoints read : %d\n", scalar keys %slack;
printf "violating : %d\n", scalar grep { $slack{$_} < 0 } keys %slack;
# ---- 2. top-N worst: the twenty that matter
my $N = 20;
my @by_slack = sort { $slack{$a} <=> $slack{$b} or $a cmp $b } keys %slack;
my @worst = @by_slack[0 .. $N - 1];
print "\n==== top $N worst endpoints ====\n";
printf "%3s %-12s %9s %s\n", "#", "ENDPOINT", "SLACK", "";
for my $k (0 .. $#worst) {
printf "%3d %-12s %+9.4f %s\n", $k + 1, $worst[$k], $slack{$worst[$k]},
$slack{$worst[$k]} < 0 ? "VIOLATED" : "";
}
# ---- 3. the registry idiom on a population SMALLER than N
print "\n==== the same slice on a 12-endpoint report ====\n";
my %small = map { $_ => $slack{$_} } @by_slack[0 .. 11];
{
my @s = sort { $small{$a} <=> $small{$b} } keys %small;
my @slice = @s[0 .. 19]; # the idiom, unchanged
my $undef = grep { !defined } @slice;
printf "population %d, slice asked for 20 -> %d element(s), %d undefined\n",
scalar(keys %small), scalar(@slice), $undef;
my @safe = @s[0 .. ($N > @s ? $#s : $N - 1)];
printf "clamped slice -> %d element(s), %d undefined\n",
scalar(@safe), scalar(grep { !defined } @safe);
}
# ---- 4. the histogram, two ways of finding the bucket
my $W = 0.05;
my (%int_b, %flo_b);
for my $ep (keys %slack) {
$int_b{ int($slack{$ep} / $W) }++;
$flo_b{ floor($slack{$ep} / $W) }++;
}
print "\n==== bucket width 0.05: int() against floor() ====\n";
printf "int() distinct buckets: %d\n", scalar keys %int_b;
printf "floor() distinct buckets: %d\n", scalar keys %flo_b;
printf "int() bucket 0 holds %d endpoint(s)\n", $int_b{0} // 0;
printf "floor() bucket 0 holds %d endpoint(s)\n", $flo_b{0} // 0;
printf "floor() bucket -1 holds %d endpoint(s)\n", $flo_b{-1} // 0;
print "\nthe endpoints int() puts in bucket 0:\n";
for my $ep (sort { $slack{$a} <=> $slack{$b} } keys %slack) {
next unless int($slack{$ep} / $W) == 0;
printf " %-12s %+8.4f floor bucket %+d %s\n", $ep, $slack{$ep},
floor($slack{$ep} / $W), $slack{$ep} < 0 ? "VIOLATED" : "MET";
}
printf "\nint() bucket 0 spans %.2f to %.2f (width %.2f)\n", -$W, $W, 2 * $W;
printf "every other int() bucket spans %.2f\n", $W;
# ---- 5. how much of the full-range histogram is empty
my @ks = sort { $a <=> $b } keys %flo_b;
printf "\nfull range: buckets %d .. %d = %d slots, %d non-empty (%.0f%% empty)\n",
$ks[0], $ks[-1], $ks[-1] - $ks[0] + 1, scalar(@ks),
100 * (1 - @ks / ($ks[-1] - $ks[0] + 1));
# ---- 6. the histogram people actually read: clipped, with an overflow row
print "\n==== slack distribution, clipped at +0.40 ====\n";
my $CLIP = 0.40;
my %h;
my $over = 0;
for my $ep (keys %slack) {
if ($slack{$ep} >= $CLIP) { $over++; next }
$h{ floor($slack{$ep} / $W) }++;
}
for my $b (sort { $a <=> $b } keys %h) {
my $lo = $b * $W;
printf " %+6.2f .. %+6.2f %-20s %2d%s\n", $lo, $lo + $W,
"#" x $h{$b}, $h{$b}, $lo < 0 ? " <- VIOLATED" : "";
}
printf " %+6.2f and above %-20s %2d\n", $CLIP, "", $over;
printf "\ntotal %d = %d shown + %d above the clip\n",
scalar(keys %slack), scalar(keys %slack) - $over, $over;
# ---- 7. a tie across the cut, measured across SEPARATE processes
print "\n==== a cut that lands inside a tie ====\n";
my %count;
$count{ sprintf "%.4f", $slack{$_} }++ for keys %slack;
my ($big) = sort { $count{$b} <=> $count{$a} } keys %count;
printf "largest group of equal slacks: %d endpoints at %+.4f\n", $count{$big}, $big;
# hash order is fixed WITHIN a process, so three loops in one process prove
# nothing. Each sample below is a separate perl process.
if (!$ENV{TIE_CHILD}) {
my (%plain, %broken);
for my $run (1 .. 5) {
local $ENV{TIE_CHILD} = 1;
my $out = `perl "$0" 2>/dev/null`;
$plain{$1}++ if $out =~ /^no tie-breaker: (.*)$/m;
$broken{$1}++ if $out =~ /^with tie-breaker: (.*)$/m;
}
printf "5 separate processes, places 69-72 of the sort:\n";
printf " no tie-breaker : %d distinct ordering(s)\n", scalar keys %plain;
printf " with a name tie-breaker: %d distinct ordering(s)\n",
scalar keys %broken;
printf " the stable answer: %s\n", (keys %broken)[0]
if keys %broken == 1;
} else {
my @a = (sort { $slack{$a} <=> $slack{$b} } keys %slack)[68 .. 71];
my @b = (sort { $slack{$a} <=> $slack{$b} or $a cmp $b } keys %slack)[68 .. 71];
printf "no tie-breaker: %s\n", join " ", @a;
printf "with tie-breaker: %s\n", join " ", @b;
exit 0;
}
# ---- 8. what each view answers, and what it hides
print "\n==== the two views answer different questions ====\n";
printf "top-20 says : worst %+.4f at %s; %d of the 20 are violating,\n",
$slack{$worst[0]}, $worst[0], scalar grep { $slack{$_} < 0 } @worst;
printf " so %d rows describe endpoints that already pass\n",
scalar grep { $slack{$_} >= 0 } @worst;
my $near = grep { $slack{$_} >= 0 && $slack{$_} < 0.05 } keys %slack;
printf "histogram says : %d violating, %d more within 0.05 of failing,\n",
scalar(grep { $slack{$_} < 0 } keys %slack), $near;
printf " and %d of %d endpoints are above the clip\n",
$over, scalar keys %slack;
my %lane;
for my $ep (@worst) { $lane{$1}++ if $ep =~ /^sf(\d)_\d+/ }
printf "top-20 by lane : %s\n",
join ", ", map { "lane $_ = $lane{$_}" } sort keys %lane;
printf "every one of the 20 is a sum flop, %d per lane -- the finding is the\n",
$lane{0};
print "carry chain, not any one lane\n";
printf "\nrows needed: full-range histogram %d, clipped %d, top-20 list %d\n",
$ks[-1] - $ks[0] + 1, scalar(keys %h) + 1, $N;endpoints read : 80
violating : 6
==== top 20 worst endpoints ====
# ENDPOINT SLACK
1 sf3_15/D -0.2580 VIOLATED
2 sf2_15/D -0.2070 VIOLATED
3 sf1_15/D -0.1560 VIOLATED
4 sf0_15/D -0.1050 VIOLATED
5 sf3_14/D -0.0820 VIOLATED
6 sf2_14/D -0.0310 VIOLATED
7 sf1_14/D +0.0200
8 sf0_14/D +0.0710
9 sf3_13/D +0.0940
10 sf2_13/D +0.1450
11 sf1_13/D +0.1960
12 sf0_13/D +0.2470
13 sf3_12/D +0.2700
14 sf2_12/D +0.3210
15 sf1_12/D +0.3720
16 sf0_12/D +0.4230
17 sf3_11/D +0.4460
18 sf2_11/D +0.4970
19 sf1_11/D +0.5480
20 sf0_11/D +0.5990
==== the same slice on a 12-endpoint report ====
population 12, slice asked for 20 -> 20 element(s), 8 undefined
clamped slice -> 12 element(s), 0 undefined
==== bucket width 0.05: int() against floor() ====
int() distinct buckets: 55
floor() distinct buckets: 56
int() bucket 0 holds 2 endpoint(s)
floor() bucket 0 holds 1 endpoint(s)
floor() bucket -1 holds 1 endpoint(s)
the endpoints int() puts in bucket 0:
sf2_14/D -0.0310 floor bucket -1 VIOLATED
sf1_14/D +0.0200 floor bucket +0 MET
int() bucket 0 spans -0.05 to 0.05 (width 0.10)
every other int() bucket spans 0.05
full range: buckets -6 .. 52 = 59 slots, 56 non-empty (5% empty)
==== slack distribution, clipped at +0.40 ====
-0.30 .. -0.25 # 1 <- VIOLATED
-0.25 .. -0.20 # 1 <- VIOLATED
-0.20 .. -0.15 # 1 <- VIOLATED
-0.15 .. -0.10 # 1 <- VIOLATED
-0.10 .. -0.05 # 1 <- VIOLATED
-0.05 .. +0.00 # 1 <- VIOLATED
+0.00 .. +0.05 # 1
+0.05 .. +0.10 ## 2
+0.10 .. +0.15 # 1
+0.15 .. +0.20 # 1
+0.20 .. +0.25 # 1
+0.25 .. +0.30 # 1
+0.30 .. +0.35 # 1
+0.35 .. +0.40 # 1
+0.40 and above 65
total 80 = 15 shown + 65 above the clip
==== a cut that lands inside a tie ====
largest group of equal slacks: 16 endpoints at +2.6110
5 separate processes, places 69-72 of the sort:
no tie-breaker : 5 distinct ordering(s)
with a name tie-breaker: 1 distinct ordering(s)
the stable answer: cff_12/D cff_13/D cff_14/D cff_15/D
==== the two views answer different questions ====
top-20 says : worst -0.2580 at sf3_15/D; 6 of the 20 are violating,
so 14 rows describe endpoints that already pass
histogram says : 6 violating, 1 more within 0.05 of failing,
and 65 of 80 endpoints are above the clip
top-20 by lane : lane 0 = 5, lane 1 = 5, lane 2 = 5, lane 3 = 5
every one of the 20 is a sum flop, 5 per lane -- the finding is the
carry chain, not any one lane
rows needed: full-range histogram 59, clipped 15, top-20 list 20The top-N itself is one line, and it is Chapter 5.9's sort with Chapter 5.3's slice on the end:
my @worst = (sort { $slack{$a} <=> $slack{$b} } keys %slack)[0 .. $N - 1];<=>, never cmp — a string sort puts -1.5 after -0.2, which is the wrong end of the list for the one thing you are looking for.
2. The Slice That Grows
Now the first defect, and it is in the obvious code:
population 12, slice asked for 20 -> 20 element(s), 8 undefined
clamped slice -> 12 element(s), 0 undefinedA list slice extends a short list rather than truncating it. Asking for [0 .. 19] of twelve elements returns twenty values, the last eight undef. Perl does not complain at the slice; it complains later, somewhere else, when something uses one of those undefs — or it does not complain at all and your report has eight blank rows.
This is not a contrived case. A report written with -max_paths 10 has ten endpoints in it. So does a report whose run died early. Either way the summary script asks for twenty and gets twelve real answers padded with eight holes.
The clamp is small:
my $last = $N > @sorted ? $#sorted : $N - 1;
my @worst = @sorted[0 .. $last];And then say the number out loud in the heading — top 12 of 12 rather than top 20 — because a reader who sees "top 20" above twelve rows has to work out which of the two numbers is lying.
3. The Bucket At Zero Is The Wrong Width
The histogram is also one line, and the registry's own form of it uses int:
$bucket{ int($slack{$_} / 0.05) }++ for keys %slack;That looks right and is wrong in exactly one place:
int() bucket 0 holds 2 endpoint(s)
floor() bucket 0 holds 1 endpoint(s)
floor() bucket -1 holds 1 endpoint(s)
the endpoints int() puts in bucket 0:
sf2_14/D -0.0310 floor bucket -1 VIOLATED
sf1_14/D +0.0200 floor bucket +0 MET
int() bucket 0 spans -0.05 to 0.05 (width 0.10)
every other int() bucket spans 0.05int truncates toward zero, not downward. So int(-0.031 / 0.05) is int(-0.62) which is 0, and int(0.020 / 0.05) is int(0.40) which is also 0. Both land in bucket 0, which therefore spans -0.05 to +0.05 — double the width of every other bucket, and straddling the sign.
The consequence is the measurement above: a VIOLATED endpoint and a MET endpoint in the same histogram row, in the one row a reviewer reads hardest. Every other row in the table is honest, the totals add up, and the bucket that decides whether the block is failing is the one that is wrong.
POSIX::floor rounds downward for negatives too, which is what bucketing means:
use POSIX qw(floor);
$bucket{ floor($slack{$_} / 0.05) }++ for keys %slack;Negative bucket indices are then real: bucket -1 is "failing by up to 0.05", and that is a row worth having. The same trap applies to any signed quantity you bucket — a day offset, a temperature delta, a percentage change.
4. A Tie At The Cut
The third defect only appears when you run the script twice.
largest group of equal slacks: 16 endpoints at +2.6110
5 separate processes, places 69-72 of the sort:
no tie-breaker : 5 distinct ordering(s)
with a name tie-breaker: 1 distinct ordering(s)Sixteen endpoints share a slack, because sixteen bits of one register have identical logic in front of them — which is normal, not a coincidence. sort with a comparison that returns 0 for all sixteen leaves them in the order keys produced, and keys order is chosen per process (6.6), so five processes gave five different orderings.
For the worst-20 that may not matter, since the cut is far from the tie. It matters the moment anything cuts inside a tie block: a per-lane top-5, a "ten best to confirm the fix", a diff of this run's list against last night's. That diff is the painful one — the lists differ, nothing changed, and someone spends an afternoon on it. Chapter 17.8 made exactly this a rule for whole reports, and a top-N list is a report.
Add a second key and the comparison never returns 0:
sort { $slack{$a} <=> $slack{$b} or $a cmp $b } keys %slackMeasured: one ordering in five processes. The tie-breaker does not have to be meaningful. It has to be total.
5. The Two Views Answer Different Questions
With the defects fixed, the useful finding is that the two views do not say the same thing about the same eighty numbers:
top-20 says : worst -0.2580 at sf3_15/D; 6 of the 20 are violating,
so 14 rows describe endpoints that already pass
histogram says : 6 violating, 1 more within 0.05 of failing,
and 65 of 80 endpoints are above the clip
top-20 by lane : lane 0 = 5, lane 1 = 5, lane 2 = 5, lane 3 = 5A fixed N is the wrong size almost always. Here it spent 14 of its 20 rows on endpoints nobody needs to look at. On a block with 300 violations it would show 20 of them and hide the rest. What a reviewer actually wants is every violation plus a few of the nearest passes — grep { $_ < 0 } first, then top up to a floor of five or ten. The count is the output, not the input.
The distribution adds the thing a worst-slack number cannot: how many are nearly failing. One endpoint sits within 0.05 of zero. If a fix moves the whole block by 0.1 that endpoint joins the violations, and the worst-slack number never hinted at it.
And the shape of the top-20 is a third finding neither view was built for. Five endpoints per lane, all four lanes, every one a sum flop — so this is not one bad lane and not one bad cell. It is the carry chain, in all four copies of it. One number cannot say that; a list of twenty names says it at a glance.
So print both, and print the distribution clipped:
rows needed: full-range histogram 59, clipped 15, top-20 list 20The full range is 59 bucket rows for a block whose entire problem lives in seven of them. Clipping at a threshold and adding one and above overflow row gives 15 rows that carry the same information — and the overflow row keeps the total honest. That is the rule worth carrying out of this module: a reduced report says what it reduced, so the total in the last line still equals the number of endpoints the tool reported.
6. What To Remember
- Two views make a large timing report reviewable: the worst N endpoints, and a bucketed distribution.
- Sort slack with
<=>, nevercmp— a string sort puts-1.5after-0.2. - Measured: a list slice EXTENDS a short list.
[0 .. 19]over 12 elements returned 20 values, 8 undefined — it does not truncate. - Clamp the upper index and print the real count in the heading (
top 12 of 12). inttruncates toward zero, soint($s / $w)makes the bucket at zero DOUBLE WIDTH and straddle the sign.- Measured: that bucket held a VIOLATED endpoint and a MET endpoint in the same row — the one row a reviewer reads hardest.
- Use
POSIX::floorfor any signed quantity you bucket; negative bucket indices are real and useful. - Measured: a tie at the cut gave 5 distinct orderings in 5 processes, because
keysorder is per-process. - Add a total tie-breaker —
or $a cmp $b— and it was 1 ordering in 5. It need not be meaningful, only total. - A fixed N is almost always the wrong size — 14 of 20 rows described endpoints that already pass.
- Select by verdict, then top up: every violation plus a few nearest passes, so the count is an output.
- The distribution says how many are NEARLY failing — one endpoint within 0.05 of zero, invisible in any worst-slack number.
- The shape of the list is a finding too: 5 per lane across all four lanes, every one a sum flop, names the carry chain.
- Clip the histogram and keep an overflow row — 15 rows instead of 59, and the total still adds up to the endpoint count.
That closes Module 23. The module started with the one block a timing report is made of and ended with two views of a whole block's worth of them, and the pattern in between was the same every time: the number the tool prints is reliable, and the number you derive from it is only as good as the one edge case you did not try. Module 24 turns to the output side — coverage and regression reporting — where the inputs are no longer one tool's report but hundreds of runs, and the question becomes how to aggregate them without losing the detail that explains a failure.
Where this fits
Part of the Perl curriculum.