CS Performance Optimization 3 — Questions and Answers
Question 1: Which compiler optimization moves a computation out of a loop when its result never changes between iterations?
- Dead code elimination
- Register spilling
- Loop-invariant code motion (Correct answer)
- Constant folding
Correct answer: Loop-invariant code motion
Loop-invariant code motion hoists unchanging computations outside the loop so they run once.
Question 2: A multithreaded program on 8 cores shows almost no speedup over the single-threaded version. Threads frequently update the same shared counter. What is the likely cause?
- Lock contention and cache-line contention on the shared counter (Correct answer)
- The threads have too much stack space
- The CPU lacks floating-point units
- The compiler disabled all optimizations
Correct answer: Lock contention and cache-line contention on the shared counter
Serialized access to a shared counter forces threads to wait and invalidate each other's cache lines.
Question 3: What does 'false sharing' refer to in parallel programming?
- A thread sharing a lock it never uses
- Copying data instead of passing a reference
- Threads on different cores modifying separate variables that share a cache line (Correct answer)
- Two threads reading the same immutable data
Correct answer: Threads on different cores modifying separate variables that share a cache line
When independent variables occupy the same cache line, writes by one core invalidate the line for others.
Question 4: Which approach best reduces perceived latency when loading a large image gallery on a website?
- Converting images to uncompressed BMP
- Loading all images before rendering the page
- Disabling browser caching
- Lazy loading images as they scroll into view (Correct answer)
Correct answer: Lazy loading images as they scroll into view
Lazy loading defers off-screen images so the visible content appears quickly.
Question 5: In Big-O terms, what improvement does switching from bubble sort to merge sort provide for large inputs?
- O(n³) to O(n²)
- O(n²) to O(log n)
- O(n log n) to O(n)
- O(n²) to O(n log n) (Correct answer)
Correct answer: O(n²) to O(n log n)
Bubble sort runs in O(n²) while merge sort guarantees O(n log n).
Question 6: Which technique lets a CPU keep executing instructions while waiting for a slow memory load by starting the fetch early?
- Checkpointing
- Garbage collection
- Prefetching (Correct answer)
- Paging
Correct answer: Prefetching
Prefetching requests data before it is needed so it arrives in cache by the time it is used.
Question 7: A recursive Fibonacci implementation runs in exponential time. Rewriting it with dynamic programming reduces the complexity to what?
- O(2^n)
- O(n!)
- O(n²)
- O(n) (Correct answer)
Correct answer: O(n)
Storing each subproblem result once reduces the computation to linear time.
CS Performance Optimization 3
Which compiler optimization moves a computation out of a loop when its result never changes between iterations?