106: Chapter 106 Thirty-two Witnesses

Jiang Lin's original plan was to seal away all these long-term issues and leave them to be resolved during the upcoming Wasteland time.

But back home, deep in the night, once he had some free time, he still couldn't help dragging the archive given by Chen Qiming into his computer's working directory.

microkernel_rank_sort_baseline.zip

Right-click and extract.

The folders unfolded layer by layer in the screen's tree diagram, and the neatness of their internal structure was much cleaner than Jiang Lin had originally imagined.

Three subfolders lay under the root directory.

Jiang Lin clicked on /baseline.

Inside were three sets of classic benchmark implementations of microkernel base algorithms: rank5 (five-element rank calculation), sort5 (five-element complete sorting), and top3_of_8 (selecting the top three from eight elements).

For each set of algorithms, Chen Qiming rigorously provided two completely different pieces of code.

One was a pure C-language readable version without any underlying optimization, used to anchor logical correctness.

The other was a handwritten, ultimate-optimized version polished by Chen Qiming's team over many years.

Jiang Lin glanced at it; the latter's code was filled with obscure compiler inline hints, forced loop unrolling, and a small amount of platform-dependent writing relying on specific CPU instruction sets.

Jiang Lin exited and clicked on /verify.

Inside were dozens of detailed verification scripts covering various extreme boundary test cases.

Finally came the /bench (performance testing) folder, the one that made system engineers' scalps tingle.

Inside was only a raw performance counter statistical table in .csv format.

This table was run and generated through a long, marathon-style stress test on three enterprise-level servers with completely different underlying microarchitectures.

Jiang Lin enlarged the table.

At the end of the rows, the absolute variables of the test environment were densely marked: CPU model, microcode update version number, L1/L2 cache hit rate, branch prediction failure rate, and whether the frequency was forcibly locked.

This item of forcibly locking the frequency earned Jiang Lin's considerable praise.

Modern commercial CPUs would cunningly adjust their clock frequencies dynamically based on temperature and load.

When conducting such nanosecond-level kernel code tests, even the slightest jitter in the CPU frequency would cause huge noise in the tested clock cycles, thereby completely masking the genuine one or two nanosecond improvement brought by code optimization.

Chen Qiming and his group not only understood this point, but also brutally locked the frequency at the BIOS level.

This data sheet alone silently proved that Chen Qiming and his people were truly seasoned veterans who knew their stuff.

They had pushed the variables that humans could manually control to the ultimate limit of Physics.

This was getting interesting.

Jiang Lin decided to start dissecting from sort5, which looked the most basic.

The problem statement was very simple: given five random integers, arrange them in ascending order.

Any novice who learned to write for loops and if statements could hand over a piece of bubble sort or insertion sort code based on two nested loops within a short three minutes.

Of course, this was merely a toy that could run.

Someone like Chen Qiming, who had long dealt with underlying performance, certainly didn't want this kind of inefficient correctness full of branch jumps that clogged up modern CPU pipelines everywhere.

And before pursuing that ultimate speed, Jiang Lin's mathematical intuition told him that he must first solve a philosophical problem.

["How to use rigorous mathematical logic to prove that a piece of obscure sorting code is one hundred percent correct for all possible input combinations in the universe?"]

The most intuitive and clunkiest method was to brutally enumerate all the size relationship combinations of these five numbers one by one.

Then how many different full permutations of five numbers were there actually?

Simple combinatorial mathematics.

5!

One hundred and twenty types.

This number was so small that the machine could finish running and verifying it in an instant.

This inevitably reminded Jiang Lin of that brick.

When making Jiangs Brick, the mathematical action carved into his bones was to exquisitely compress a boundary state space so massive it tended toward infinity into a finite state form that machines could exhaustively list and humans could recheck.

One hundred and twenty indeed wasn't large.

But what about sorting eight numbers or sixteen numbers, which frequently appeared in advanced database indexes?

8!

Forty thousand combinations, and the machine could still easily breeze through them.

But when it came to sixteen numbers—

16!

At the level of twenty trillion.

For ordinary programs, this was no longer a matter of running a bit longer, but enough to drag the clunkiest full-permutation verification into the quagmire.

If the MPS framework were built on such stupid full-permutation enumeration, it would quickly die at the starting line.

Jiang Lin twirled the ballpoint pen in his hand, and his brain's memory palace began high-speed retrieval.

Soon, he put down the pen and typed a line of academic retrieval terms on the keyboard.

Zero-One Principle sorting network

(Sorting Network: Zero-One Principle)

In fact, back in the Wasteland time, while devouring those vast and boundless computer science masterpieces, he had already made relevant knowledge preparations.

It was just that before this, it had merely stayed at the level of a theorem in a discrete mathematics textbook and didn't have an urgent place to be put into practice.

And now, Jiang Lin believed that this elegant theorem could become the first foundation stone of MPS-Kernel.

In theoretical computer science, the Zero-One Principle could proudly declare—

A comparison network fixedly composed of compare-swap operations is an absolutely correct sorting network if and only if it can extremely correctly sort all finite input sequences composed solely of the numbers 0 and 1 completely.

The lethality of this theorem lay in the fact that it ruthlessly severed the boundary between infinity and finiteness.

It did not require you to check all 120 permutations, nor did it require you to feed any actual inputs with specific values into this sorting code.

It only required you to check those binary sequences pieced together from 0 and 1.

For sort5 (five positions), according to the Zero-One Principle, it could be regarded as each independent position being either absolute 0 or absolute 1 (either 0 or 1).

Thus, its verification space suddenly and miraculously collapsed into 2⁵ = 32.

As long as the code network you wrote could correctly and flawlessly arrange these thirty-two sequences entirely composed of 0 and 1 into a monotonically increasing shape—

Then, magically and absolutely, this comparison network would be correct for any five inputs coming from the same total order type.

The originally small 120 was once again dimensionally compressed down to 32.

If it were sixteen numbers, the originally terrifying twenty trillion could also be compressed into sixty-five thousand.

A number that a microprocessor could finish running with its eyes closed.

What was more important was that these thirty-two crude 0-1 sequences were neither metaphysical sampling tests in software engineering nor boundary test cases racked test engineers' brains to come up with.

In a mathematical sense, it was a comprehensive check without dead corners.

As long as these thirty-two simple sequences were smoothly run through, the absolute correctness of this code's underlying layer would be welded tightly onto the iron plate of truth.

This thrill of using abstract mathematical theorems to slay the infinite state space was simply too wonderful.

Jiang Lin immediately created a new Python script file under the root directory of MPS-Kernel.

verify_sort5_zero_one.py

Import itertools.product to brutally generate all determined thirty-two 0-1 sequences.

For each independent sequence, mechanically run the externally mounted candidate sorting network code once.

Strictly check whether the output sequence satisfied monotonic non-decrease.

Thirty-two rigorous witnesses—as long as they all passed, the program would return green ["PROVEN VALID"] (proven valid).

And as long as any tiny sequence failed to pass, the program would directly spit out that counterexample and mercilessly shoot down this piece of code.

All thirty-two passed, return proven.

If any single one failed, spit out that counterexample.

Jiang Lin pressed the enter key and brutally ran the fixture once with the raw /baseline/sort5_pure.c provided by Chen Qiming's team.

Green.

In the rigorous mathematical courtroom, not a single one of the thirty-two 0-1 witnesses recanted their testimony.

The foundation of correctness was established.

What followed was the work of immortals fighting: among all correct sorting networks, finding the best one.

Jiang Lin began to cleverly apply his MPS search skeleton, tempered through thousands of refinements in tiling geometry, onto this code problem.

When making bricks, the state was a local tiling, the action was laying down a new brick, and the victory condition was eliminating all topological escapes.

And now?

The state was a comparator sequence already written down.

The action was appending a comparator to the back, comparing two positions, throwing the smaller one forward and the larger one backward.

The victory condition was that this sequence made all thirty-two witnesses nod.

The structure was identical.

It just replaced geometry with instructions.

He wrote a version of search: starting from an empty network, appending comparators one by one, pruning with the Zero-One Principle every time one was added, leaving branches with hope and hacking away those that had walked to a dead end.

The search first ran all candidates within a length of eight.

MPS didn't find any network that could make all thirty-two 0-1 witnesses nod.

Then the length was set to nine.

The first group of passing networks appeared.

Jiang Lin matched the result with the line S(5) = 9 in Knuth.

This meant that for sorting five elements, nine comparators weren't just able to do it, but were the absolute minimum limit.

[part:gemini-3.6-flash]

That number that had been in textbooks for decades was independently searched out from scratch by his framework that grew out of a brick.

Framework, successfully migrated.

Jiang Lin leaned back in his chair, looking at those nine clean rows of comparators on the screen.

For a moment, he felt a light, airy sense of success.

But this floaty feeling lasted only a few seconds before he suppressed it himself.

He pulled up Chen Qiming's bloody flame graph again.

median7_fast, rank5_inline, top3_window...

Chen Qiming had long said that the dividends of manual optimization had been squeezed very thin by those who spent years immersed in low-level code.

Meaning that the code in his team's possession likely already had nine comparators, or was very close to nine.

And the minimum of nine comparators he had searched out using high-dimensional mathematics and search algorithms was not something new to Chen Qiming at all.

Jiang Lin stared at his nine lines of results, his brows gradually furrowing.

He had made a rookie mistake.

Subconsciously, he had optimized the cleanest, best-defined, and easiest combinatorial target to write a fitness function for—the number of comparators.

But what Chen Qiming wanted was never the minimum quantity in a mathematical sense.

Rather, it was running the fastest on his specific servers.

Minimum quantity and running fastest were not the same thing at all in the real physical world.

Jiang Lin remembered the last sentence Chen Qiming left in the lecture hall.

His search space was full of correct, inefficient trash.

At this moment, he understood at a deeper level.

Nine comparators were arranged by quantity.

But inside a real CPU, what determines the speed of a piece of code is never just the number of instructions.

It is the data dependency chain between these nine comparators: which ones must queue and wait for the previous one to finish calculating, and which ones can be calculated side-by-side simultaneously.

It is which ports of the out-of-order execution engine they land on, and whether they will crowd together to compete for resources.

It is the latency and throughput of each min, max, and conditional move instruction.

It is whether there are enough registers, or if it will be forced to shuffle data back and forth with memory.

For the same nine comparators, arranging them in a long, thin dependency chain versus a shallow, five-layer parallel tower can result in a huge difference in pipeline performance.

Fewer comparators and shallow comparator depth are two different goals.

The goal Chen Qiming truly wanted—the optimal solution that squeezes out every last drop of performance on Model A servers and minimizes latency—was hidden deep within the filthy low levels of hardware.

Tightly bound to the microarchitecture.

Switching to a CPU of a different generation, even just from Intel's Skylake to the Zen 3 architecture, slight changes in cache latency and instruction ports would cause that optimal solution to instantly fall from grace and become sub-optimal.

Jiang Lin stared at the perf tables of those three machines, suddenly realizing that to find the optimal solution that truly fits the physical world, mathematical proof alone was not enough.

He had to integrate a cost model into his MPS framework.

Among the vast number of correct candidate networks, he had to look not only at quantity, but also at depth and parallelism.

Even in the end, he would need to write an automated script to compile the hundreds of promising candidate networks selected one by one into machine code, throw them into real physical servers for actual testing, scoring, and filtering.

Every actual test is accompanied by operating system scheduling noise and cache warmup fluctuations.

He would have to run each candidate a million times, take the median and 99th percentile latency, and engage in tedious statistical combat.

It was not something that could be finished in a single night, or even half a year or a year in the Real World.

After realizing the limitations of pure algorithms in front of low-level hardware, Jiang Lin's mind actually calmed down.

He casually clicked on rank5, wondering if this logic could also be crushed using the existing framework.

Problem description: Given five numbers, not requiring all of them to be fully sorted, but only asking what rank the number at the center of the input window holds among these five numbers.

Almost out of habit, he instinctively wanted to apply the newly written Zero-One Principle verification script.

Fortunately, the next moment, he checked himself in time.

The Zero-One Principle governs whether things are sorted, which is global monotonicity.

But what rank5 requires is not to sort all numbers obediently, but to attach a precise rank label to each number, or to a specific number.

Thus, its correctness criterion is no longer asking whether the final output sequence is monotonically increasing, but rather: is the rank assigned to the number originally at the center of the input actually the correct rank?

What would happen if the inputs were forcibly replaced with all 0s and 1s?

For example, if the original input is [10, 50, 30, 20, 40], the middle number is 30, which ranks third.

If crudely binarized into a 0-1 sequence, it might become [0, 1, 1, 0, 1].

In this binary sequence, there are three 1s and two 0s.

Absolute rank cases that originally needed to be distinguished collapsed due to the reduction in numerical dimensions, turning into a complete mess where it was impossible to tell who was the true third.

The Zero-One Principle does not hold directly here.

Or rather, it has failed.

rank5 ≠ sorting network.

To verify rank5, one must return to the level of relative size relationships (such as permutation groups), rather than purely the 0-1 input space.

Its underlying structure is closer to a dynamically updated pairwise comparison matrix composed of partial order relationships.

This was yet another new pitfall.

Jiang Lin's eyes swept across the last question: top3_of_8.

Pick out the top three largest numbers from eight numbers.

This problem also concealed hidden dangers.

For top-k selection in the form of comparison networks, a similar Zero-One test can be used.

Eight positions means 2^8=256 0-1 witnesses.

But the prerequisite is that you must first define the correct semantics with the problem creator.

What does picking out the top three mean?

Criterion A: As long as the three largest numbers fall into the first three slots of the output array, does it not matter if the order among these three numbers is scrambled?

Criterion B: Or is it that not only must the three largest numbers enter the top three, but these three numbers must also be strictly sorted from largest to smallest among themselves?

If the criterion is not firmly defined, then what the MPS framework searches out will be castles in the air.

If the standard is relaxed by one degree, the search space shrinks exponentially.

If the standard is tightened by one degree, the dependency chain inevitably lengthens.

Three problems, three completely different temperaments, three different verification systems.

Jiang Lin was in no rush to write code to solve the problems.

Because direction is ten thousand times more important than speed.

He opened a text editor and, like a combat engineer flagging a minefield, recorded the logical boundaries, verification difficulties, and hardware coupling points of each problem set word for word into a document.

Around dawn, Jiang Lin put together something he could hand over to Chen Qiming.

The first item was a verification harness based on the Zero-One Principle.

This was an ultimate weapon.

It could provide an absolutely exhaustive, mathematically undeniable proof of correctness for any sort5 candidate code written by anyone in Chen Qiming's team, completely independent of the underlying CPU architecture.

In the future, if anyone submitted a piece of bitwise operation code they thought was brilliant, there would be no need to argue—just run this harness.

Thirty-two 0-1 witnesses would make their stance clear on the spot.

Those that failed would be rejected outright.

This was the foundation.

The second item was a boundary specification document.

He divided the chaotic problem Chen Qiming faced into two parts.

The first layer was theoretical goals at a purely combinatorial level.

Could the total number of comparators be even smaller?

Could the number of layers in the dependency chain be even shallower?

For small-scale problems like sort5, Jiang Lin promised that he could use his MPS framework to fully map out and uproot all theoretical optimal solutions at this layer.

But he also stated bluntly that facing larger n (for instance, 1PS), combinatorial explosion would still occur in the face of computing power.

Heuristic pruning must be introduced.

The second layer was microarchitecture optimality tied to specific physical hardware.

That is, minimizing latency on a specific server designated by Chen Qiming.

This layer required Chen Qiming's empirical testing harness and a massive amount of candidate code to run statistics on real machines.

The workload was immense and required time.

This was by no means a problem that could be solved by pulling a few all-nighters in the Real World.

He would bring the entire MPS-Kernel framework into the Wasteland to polish.

There, he would have decades to expand, debug, and stabilize the search framework, pruning strategies, and cost models inch by inch.

Of course, the workstation in the Outpost was a specific machine he carried in from reality.

The fastest it ran was merely the fastest on that particular machine.

Chen Qiming's targets were several other servers of completely different models.

Once the microarchitecture changes, the optimal solution changes.

Therefore, during those decades in the Wasteland, what he could truly bring back would not be a piece of code that ran lightning-fast on Wasteland hardware.

But rather a super search framework that had been repeatedly polished, debugged, and verified, a mature cost modeling methodology, plus a library of candidate network structures dual-filtered through mathematical verification and Real World testing.

With everything planned properly, Jiang Lin renamed the packaged documents and scripts to J_MPS_Phase1_Deliverables.zip.

Outside the window, the sky was already turning white; the rain in Jiangcheng that had been held back all night ultimately failed to fall.