Experiments and implementations · Intermediate

Observe input order and conditional branches

Compare three equally balanced input orders in C, verify the intended conditional jump, and record timings separately from unavailable PMU events.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Preserve outcome counts while changing order
  2. Compile an observation-oriented build
  3. Find the data-dependent jump
  4. Preserve the complete duration distribution
  5. Calculate event rates only when events were acquired
  6. Treat the ordinary optimized build as another implementation
  7. Solve a changed-population exercise
  8. Ask Logeia about this articleCheck your understanding

Preserve outcome counts while changing order

Prepare 1,048,576 Boolean elements, exactly half zero and half one. Add five for zero and three for one, giving the same expected total, 4,194,304, in every order. Compare sorted, alternating and fixed-seed shuffled inputs. Read the branch-prediction guide first. The goal is a reproducible relationship between input, generated instructions, timing and available events, not guessing the internal predictor from a speed ranking.

Sorted input changes from one long run to another; alternating input has a short repeating pattern. Shuffling swaps the same population, preserving the number of true outcomes. The fixed generator and exchange rule reproduce one order. They are not cryptographic randomness, and modulo selection can introduce bias. Here that is acceptable for constructing a specified balanced sequence; the experiment does not evaluate random-number quality. Save the generator and seed rather than describing the input only as random.

Compile an observation-oriented build

Save branch.c and compile with gcc -O2 -std=c11 -fno-ipa-pure-const -fno-if-conversion -fno-if-conversion2 -fno-tree-vectorize branch.c -o branch. Run ./branch. CSV fields identify input kind, repetition, nanoseconds and checksum; kinds zero, one and two mean sorted, alternating and shuffled. The conversion flags preserve the conditional under study rather than recommending a fastest production configuration. Record CPU, OS, GCC version and all settings together.

Allocation, generation and shuffling are outside timing. Assertions check the sum, and sink plus printed output consume it. Each kind receives nine observations. This compact program measures one kind at a time, so kind order may coincide with environmental drift. A follow-up can vary the order of kinds, preserving it as an additional labeled condition. Do not silently merge observations from different execution-order protocols. Reproducibility includes what happened between timed calls, not only the source of the inner loop.

Find the data-dependent jump

Save objdump -d branch output and follow the count implementation called from main. GCC 13.3 names the observed function count.constprop.0 and retains a conditional jump after comparing an input byte. A changed suffix does not mean the function disappeared. Separate the data-value comparison from the loop-end test. Counting jump mnemonics without their operands and control flow cannot establish which branch was manipulated.

The recorded build verifies the intended branch, but an option name does not guarantee the same decision in every compiler version. If you add a normal optimized build, keep a separate binary instead of overwriting the controlled one. SIMD or conditional moves in that build create a different comparison worth analyzing. Start with the actual instruction receiving the input, not the assumption that every source if must exercise a hardware predictor. Saving both source and the relevant disassembly makes that interpretation reviewable.

c
#define _POSIX_C_SOURCE 200809L
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static volatile uint64_t sink;
static uint64_t ns(void) { struct timespec t; assert(!clock_gettime(CLOCK_MONOTONIC,&t)); return (uint64_t)t.tv_sec*1000000000u+t.tv_nsec; }
static uint32_t state=12345;
static uint32_t random32(void) { state=state*1664525u+1013904223u; return state; }
__attribute__((noinline)) static uint64_t count(const uint8_t *a,size_t n) {
 uint64_t yes=0,no=0;
 for(size_t i=0;i<n;i++) { if(a[i]) yes+=3; else no+=5; }
 return yes+no;
}
int main(void) {
 size_t n=1048576; uint8_t *a=malloc(n);assert(a);
 for(int kind=0;kind<3;kind++) {
  for(size_t i=0;i<n;i++) a[i]=kind==1 ? (uint8_t)(i%2) : (uint8_t)(i>=n/2);
  if(kind==2) for(size_t i=n-1;i>0;i--) { size_t j=random32()%(i+1);uint8_t v=a[i];a[i]=a[j];a[j]=v; }
  for(int r=0;r<9;r++) { uint64_t start=ns(),sum=count(a,n),elapsed=ns()-start; assert(sum==4*n);sink=sum;printf("%d,%d,%llu,%llu\n",kind,r,(unsigned long long)elapsed,(unsigned long long)sum); }
 }
 free(a);return 0;
}

Preserve the complete duration distribution

A passing run produces 27 rows, nine per kind, with identical checksums. It asserts no timing ranking. Calculate medians and quantiles from all observations, preserving the first result even when it differs from later ones. Divide duration by the element count for time per element. Equal true fractions do not imply identical histories, and neither alternating-is-slowest nor shuffled-means-fifty-percent-misses is a valid universal expected result.

Compare samples from the same binary and environment. Scheduling and shared-resource changes in a virtual machine make small differences unsuitable for conversion into a fixed instruction latency. Do not multiply by a nominal GHz label and call the result measured cycles without establishing the frequency conditions. Report three distinct findings: verified equal work and generated instructions, observed duration differences, and the evidence supporting any proposed cause. This keeps the experiment useful even when its timing ranking changes on another machine.

Calculate event rates only when events were acquired

If branch and misprediction counts are available for the same scope, their ratio can describe that scope. Check whether events include all branches, particular conditional types or only user-space activity. Counts including generation, printing and loop control are not automatically the rate of the array if alone. Record multiplexing and scaling where used. Availability and event definitions must be verified for the target CPU and operating system.

The execution evidence here does not acquire PMU events. It records successful runs, sums, durations and generated instructions. Unavailable does not mean zero mispredictions. Timing can motivate hypotheses but still includes memory, instruction and predictor-state effects. Frame follow-up questions concretely, such as how many data-dependent predictions failed or when the condition became ready. Distinguishing evidence obtained from evidence still needed is part of the result, rather than a reason to invent a precise causal number.

Treat the ordinary optimized build as another implementation

An additional ordinary -O2 build should keep the controlled binary, inputs and sums available for comparison. If its data branch disappears, that is a different generated implementation, not proof the original branch predictor became more accurate. Align each CSV with its own disassembly. This separates an application-level compiler optimization comparison from the narrower mechanism study. It also prevents transferring an event count from one binary into the timing interpretation of another simply because both came from identical C source.

Solve a changed-population exercise

Change the true population to one quarter. Expected work is three times n/4 plus five times 3n/4, or 4.5n. At the original length the sum is 4,718,592. Update every input constructor and assertion consistently, including a repeating pattern such as zero, zero, zero, one. Editing only the assertion to match output does not independently verify that all three inputs preserved equal populations.

For another exercise, add the same amount for both outcomes. The compiler may then remove the condition entirely. Check that change in disassembly and explain why it no longer studies the original branch. At completion organize or remove the binary, source, disassembly and CSV. No server or external API is involved. Any branchless alternative should be a separately labeled implementation satisfying the required output contract, not a silent change to the measured workload.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 7

Prepare for AI systems · STEP 4

Choose a learning path