Context Switch Overhead: The Hidden Performance Cost

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

/**
 * Measuring direct context switch cost using RDTSC
 * 
 * This measures the minimum time for a round-trip context switch
 * between two cooperating processes using a pipe for synchronization.
 */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <stdint.h>
 
/* Read CPU timestamp counter */
static inline uint64_t rdtsc(void) {
    uint32_t lo, hi;
    __asm__ volatile ("rdtsc" : "=a"(lo), "=d"(hi));
    return ((uint64_t)hi << 32) | lo;
}
 
#define ITERATIONS 100000
 
int main() {
    int pipe_parent_to_child[2];
    int pipe_child_to_parent[2];
    char buf = 'x';
    
    pipe(pipe_parent_to_child);
    pipe(pipe_child_to_parent);
    
    if (fork() == 0) {
        /* Child: bounce messages back */
        for (int i = 0; i < ITERATIONS; i++) {
            read(pipe_parent_to_child[0], &buf, 1);
            write(pipe_child_to_parent[1], &buf, 1);
        }
        exit(0);
    }
    
    /* Parent: measure round-trip time */
    uint64_t total_cycles = 0;
    
    /* Warmup */
    for (int i = 0; i < 1000; i++) {
        write(pipe_parent_to_child[1], &buf, 1);
        read(pipe_child_to_parent[0], &buf, 1);
    }
    
    /* Measurement */
    for (int i = 0; i < ITERATIONS; i++) {
        uint64_t start = rdtsc();
        write(pipe_parent_to_child[1], &buf, 1);
        read(pipe_child_to_parent[0], &buf, 1);
        uint64_t end = rdtsc();
        total_cycles += (end - start);
    }
    
    wait(NULL);
    
    /* Each round-trip = 2 context switches + pipe overhead */
    double cycles_per_roundtrip = (double)total_cycles / ITERATIONS;
    
    /*
     * Estimated context switch cost:
     * Subtract pipe overhead (~500-1000 cycles for small writes)
     * Divide by 2 for single switch
     */
    double estimated_switch = (cycles_per_roundtrip - 1000) / 2;
    
    printf("Cycles per round-trip: %.0f
", cycles_per_roundtrip);
    printf("Estimated cycles per context switch: %.0f
", estimated_switch);
    printf("At 3 GHz, approx %.3f microseconds per switch
", 
           estimated_switch / 3000.0);
    
    return 0;
}
 
/*
 * Typical output on modern Linux (3 GHz CPU):
 *   Cycles per round-trip: 3500
 *   Estimated cycles per context switch: 1250
 *   At 3 GHz, approx 0.417 microseconds per switch
 * 
 * But this is just the DIRECT cost...
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

/**
 * Demonstrating cache pollution from context switches
 * 
 * This program measures array access time before and after
 * a context switch to a memory-intensive process.
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <sys/wait.h>
 
#define ARRAY_SIZE (1 << 20)  /* 1M elements = 8MB (larger than L2) */
#define ITERATIONS 100
 
volatile uint64_t *array;
 
static inline uint64_t rdtsc(void) {
    uint32_t lo, hi;
    __asm__ volatile ("rdtsc" : "=a"(lo), "=d"(hi));
    return ((uint64_t)hi << 32) | lo;
}
 
/* Access array sequentially - should be cache-friendly */
uint64_t measure_array_access(void) {
    uint64_t sum = 0;
    uint64_t start = rdtsc();
    
    for (size_t i = 0; i < ARRAY_SIZE; i++) {
        sum += array[i];
    }
    
    uint64_t end = rdtsc();
    return end - start;
}
 
/* Pollute the cache with different data */
void pollute_cache(size_t size) {
    volatile uint64_t *polluter = malloc(size * sizeof(uint64_t));
    for (size_t i = 0; i < size; i++) {
        polluter[i] = i;  /* Read-modify-write forces cache fill */
    }
    free((void*)polluter);
}
 
int main() {
    array = malloc(ARRAY_SIZE * sizeof(uint64_t));
    for (size_t i = 0; i < ARRAY_SIZE; i++) {
        array[i] = i;
    }
    
    /* Warm up cache with our array */
    measure_array_access();
    measure_array_access();
    
    /* Measure with warm cache */
    uint64_t warm_cache_cycles = 0;
    for (int i = 0; i < ITERATIONS; i++) {
        warm_cache_cycles += measure_array_access();
        measure_array_access();  /* Keep cache warm */
    }
    warm_cache_cycles /= ITERATIONS;
    
    /* Now measure after cache pollution (simulating context switch) */
    uint64_t cold_cache_cycles = 0;
    for (int i = 0; i < ITERATIONS; i++) {
        pollute_cache(ARRAY_SIZE);  /* Evict our data from cache */
        cold_cache_cycles += measure_array_access();  /* First access after eviction */
    }
    cold_cache_cycles /= ITERATIONS;
    
    printf("Warm cache access: %lu cycles
", warm_cache_cycles);
    printf("Cold cache access: %lu cycles
", cold_cache_cycles);
    printf("Cache pollution penalty: %lu cycles (%.1fx slower)
",
           cold_cache_cycles - warm_cache_cycles,
           (double)cold_cache_cycles / warm_cache_cycles);
    printf("
At 3 GHz: %.2f ms warm, %.2f ms cold
",
           warm_cache_cycles / 3e6, cold_cache_cycles / 3e6);
    
    free((void*)array);
    return 0;
}
 
/*
 * Typical output:
 *   Warm cache access: 1,200,000 cycles
 *   Cold cache access: 18,000,000 cycles  
 *   Cache pollution penalty: 16,800,000 cycles (15.0x slower)
 *
 *   At 3 GHz: 0.40 ms warm, 6.00 ms cold
 *
 * The "direct" context switch cost is ~1 microsecond.
 * The INDIRECT cache penalty can be milliseconds!
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

/**
 * PCID (Process Context IDentifier) - Mitigating TLB Flush Cost
 * 
 * PCIDs allow keeping TLB entries from multiple address spaces,
 * tagged by a 12-bit identifier. This avoids full TLB flushes
 * on context switch.
 */
 
/* PCID is stored in lower 12 bits of CR3 */
#define CR3_PCID_MASK   0x0FFF
 
/* 
 * Bit 63 of CR3 controls TLB flush behavior:
 * - 0: Flush all entries with the new PCID
 * - 1: Don't flush (keep existing entries for this PCID)
 */
#define CR3_NOFLUSH     (1UL << 63)
 
/**
 * switch_mm_pcid() - Switch address space with PCID optimization
 * 
 * Instead of flushing all TLB entries, we tag entries with PCID.
 * When switching back to a process, its TLB entries may still be valid.
 */
void switch_mm_pcid(struct mm_struct *prev, struct mm_struct *next)
{
    unsigned long new_cr3;
    
    if (prev == next) {
        return;  /* Same address space - no CR3 change needed */
    }
    
    /*
     * Build CR3 value:
     * - Physical address of PML4 table
     * - PCID from mm_struct context
     * - NOFLUSH bit if this PCID was recently used
     */
    new_cr3 = __pa(next->pgd);
    new_cr3 |= next->context.pcid;
    
    /*
     * Check if we've used this PCID recently on this CPU.
     * If so, TLB entries might still be valid - don't flush.
     */
    if (this_cpu_read(tlb_gen[next->context.pcid]) == next->context.tlb_gen) {
        new_cr3 |= CR3_NOFLUSH;  /* Keep TLB entries */
    } else {
        /* PCID was used by different mm - must flush */
        this_cpu_write(tlb_gen[next->context.pcid], next->context.tlb_gen);
    }
    
    native_write_cr3(new_cr3);
}
 
/**
 * Performance impact of PCID:
 * 
 * Without PCID (before ~2013, or disabled):
 *   - Every process switch flushes entire TLB
 *   - New process gets 100% TLB misses until warmed up
 *   
 * With PCID:
 *   - TLB entries tagged with PCID survive switch
 *   - Switching back to a process may find hot TLB entries
 *   - 12-bit PCID = up to 4096 concurrent address spaces cached
 *   - Dramatic improvement for frequent process switches
 *
 * Measured improvement: 20-40% reduction in context switch overhead
 * on workloads with frequent process switches.
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

BRANCH MISPREDICTION COST ANALYSIS
====================================
 
Scenario: Process with tight loop containing conditional branch
 
Before Context Switch (warm predictor):
  - Branch misprediction rate: 2%
  - Loop iterations: 10,000
  - Mispredictions: 200
  - Penalty: 200 × 15 cycles = 3,000 cycles
 
After Context Switch (cold predictor):  
  - Branch misprediction rate: 25-50% initially
  - First 1,000 iterations: avg 35% mispredict
  - Mispredictions in warmup: 350
  - Penalty: 350 × 15 cycles = 5,250 extra cycles
  
Total warmup penalty: ~5,000-10,000 cycles
(in addition to direct context switch cost)
 
--------------------------------------------
 
REAL-WORLD EXAMPLE: Database Query Engine
 
A database executing B-tree traversals after context switch:
 
- B-tree has many conditional branches (key comparisons)
- Cold predictor: 30% misprediction rate
- 50 comparisons/query, 100 queries to warm up predictor
- Warmup penalty: 50 × 100 × 0.3 × 15 = 22,500 cycles
 
This is ~7 microseconds of CPU time "wasted" on mispredictions
during the warmup period after a context switch.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

/**
 * Comparing process switch vs thread switch overhead
 * 
 * Creates either thread pairs or process pairs, measures
 * round-trip time through pipe communication.
 */
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/wait.h>
 
#define ITERATIONS 100000
 
/* Measure round-trip through pipes */
uint64_t measure_switches(int read_fd, int write_fd) {
    char buf = 'x';
    uint64_t start = rdtsc();
    
    for (int i = 0; i < ITERATIONS; i++) {
        write(write_fd, &buf, 1);
        read(read_fd, &buf, 1);
    }
    
    return rdtsc() - start;
}
 
/* Thread function for thread-switch test */
void *thread_bouncer(void *arg) {
    int *fds = (int *)arg;
    char buf;
    for (int i = 0; i < ITERATIONS; i++) {
        read(fds[0], &buf, 1);
        write(fds[1], &buf, 1);
    }
    return NULL;
}
 
int main() {
    /*
     * Test 1: Process context switches
     */
    int p2c[2], c2p[2];
    pipe(p2c); pipe(c2p);
    
    if (fork() == 0) {
        char buf;
        for (int i = 0; i < ITERATIONS; i++) {
            read(p2c[0], &buf, 1);
            write(c2p[1], &buf, 1);
        }
        _exit(0);
    }
    
    uint64_t process_cycles = measure_switches(c2p[0], p2c[1]);
    wait(NULL);
    
    /*
     * Test 2: Thread context switches  
     */
    int t2t[2], t2m[2];
    pipe(t2t); pipe(t2m);
    
    pthread_t thread;
    int fds[2] = {t2t[0], t2m[1]};
    pthread_create(&thread, NULL, thread_bouncer, fds);
    
    uint64_t thread_cycles = measure_switches(t2m[0], t2t[1]);
    pthread_join(thread, NULL);
    
    /*
     * Results
     */
    double process_per_switch = (double)process_cycles / (ITERATIONS * 2);
    double thread_per_switch = (double)thread_cycles / (ITERATIONS * 2);
    
    printf("Process switch: %.0f cycles/switch
", process_per_switch);
    printf("Thread switch:  %.0f cycles/switch
", thread_per_switch);
    printf("Ratio: %.1fx
", process_per_switch / thread_per_switch);
    
    return 0;
}
 
/*
 * Typical results:
 *   Process switch: 3500 cycles/switch
 *   Thread switch:  1200 cycles/switch  
 *   Ratio: 2.9x
 *
 * Note: This understates the difference because:
 * 1. Both tests have pipe overhead
 * 2. Doesn't capture full cache/TLB warmup costs
 * 
 * In heavy workloads with large working sets, the
 * ratio can be 10-50x or more.
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#!/bin/bash
# Measuring context switch overhead with various tools
 
# 1. Basic count of context switches during workload
echo "=== Context Switch Count ==="
perf stat -e context-switches,cpu-migrations ./my_workload
 
# 2. Detailed timing of context switches
echo -e "
=== Context Switch Timing ==="
perf record -e sched:sched_switch -c 1 ./my_workload
perf script | head -20
 
# 3. Per-process scheduling statistics
echo -e "
=== Process Scheduling Stats ==="
# Run workload in background
./my_workload &
PID=$!
sleep 1
cat /proc/$PID/sched
kill $PID 2>/dev/null
 
# 4. System-wide context switch rate
echo -e "
=== System-Wide Context Switch Rate ==="
vmstat 1 5
 
# 5. Using lmbench for dedicated measurement
echo -e "
=== lmbench Context Switch Latency ==="
# lat_ctx -s 0 2     # 2 processes, 0KB working set
# lat_ctx -s 64 2    # 2 processes, 64KB working set  
# lat_ctx -s 1024 2  # 2 processes, 1MB working set
 
# Example output annotation:
# lat_ctx output format: "size=XXK ovr=Y.YY"
# - size: working set size per process
# - ovr: microseconds per context switch
#
# Typical results:
#   size=0K    ovr=1.5   (minimal working set)
#   size=64K   ovr=3.2   (L1 cache exceeded)
#   size=256K  ovr=12.4  (L2 cache exceeded)
#   size=1024K ovr=48.6  (L3 cache exceeded)
#
# Notice how overhead grows dramatically with working set size!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

WEB SERVER CONTEXT SWITCH OVERHEAD ANALYSIS
============================================
 
Scenario: Apache-style process-per-request model
 
Request Rate: 10,000 requests/second
Processes: 100 worker processes
Context Switches: ~2 per request (in + out) = 20,000 switches/sec
 
Direct Cost:
  - 2,000 cycles/switch × 20,000 switches/sec = 40 million cycles/sec
  - On 3 GHz CPU: 40M / 3G = 1.3% CPU overhead
 
Indirect Cost (estimated):
  - Cache/TLB warmup: ~20,000 cycles/switch average
  - 20,000 × 20,000 = 400 million cycles/sec  
  - On 3 GHz CPU: 400M / 3G = 13.3% CPU overhead
 
TOTAL OVERHEAD: ~15% of CPU capacity
 
On an 8-core server:
  - 15% overhead = 1.2 cores spent on switching
  - Effective capacity: 6.8 cores for actual work
  
============================================
 
Alternative: Event-driven model (nginx-style)
 
Worker Threads: 8 (one per core)
Context Switches: Minimal (mostly same-thread handling)
Estimated switches: 1,000/sec (10x fewer)
 
Direct Cost: 0.07% CPU
Indirect Cost: 1.3% CPU  
TOTAL OVERHEAD: ~1.5% of CPU capacity
 
IMPROVEMENT: 10x reduction in overhead
             15% → 1.5% of CPU freed
 
This is why event-driven servers (nginx, Node.js) can handle
more connections than process-per-request servers (Apache).