Two-bit Branch Predictor
Problem statement
Implement a table of two-bit saturating branch-prediction counters. There are entries counters, all initially1 (weakly not taken). For each [pc,outcome] event, use index pc % entries. Different PCs with the same index share a counter.
First emit a prediction from the current state:0 for states0 or1, and1 for states2 or3. Then train that counter using the actual outcome: increment by1 up to3 for outcome1, or decrement by1 down to0 for outcome0. Process events sequentially and return the predictions in order. Predictions always precede training on that event.
Function
branchPredictions(entries: int, events: int[][]) → int[]Examples
Example 1
entries = 1events = [[0,1],[0,1],[0,0],[0,0],[0,0]]return = [0,1,1,1,0]Starting at state1, the states before these predictions are1,2,3,2,1. States2 and3 predict taken.
Example 2
entries = 2events = [[0,1],[2,1],[0,0],[1,1],[3,0]]return = [0,1,1,0,1]PCs0 and2 share index0; PCs1 and3 share index1. Aliasing shares the learned counter state.
Example 3
entries = 4events = []return = []No branches produce no predictions.
Constraints
1 <= entries <= 64.0 <= events.length <= 10000.Every event has exactly 2 integers.Every event value is from 0 to 1000000.Each event is [pc, outcome], where outcome is 0 or 1.