solana_runtime/
execute_cost_table.rs

1/// ExecuteCostTable is aggregated by Cost Model, it keeps each program's
2/// average cost in its HashMap, with fixed capacity to avoid from growing
3/// unchecked.
4/// When its capacity limit is reached, it prunes old and less-used programs
5/// to make room for new ones.
6use {
7    log::*, solana_program_runtime::compute_budget::DEFAULT_INSTRUCTION_COMPUTE_UNIT_LIMIT,
8    solana_sdk::pubkey::Pubkey, std::collections::HashMap,
9};
10
11// prune is rather expensive op, free up bulk space in each operation
12// would be more efficient. PRUNE_RATIO defines that after prune, table
13// size will be original_size * PRUNE_RATIO. The value is defined in
14// scale of 100.
15const PRUNE_RATIO: usize = 75;
16// with 50_000 TPS as norm, weights occurrences '100' per microsec
17const OCCURRENCES_WEIGHT: i64 = 100;
18
19const DEFAULT_CAPACITY: usize = 1024;
20
21#[derive(AbiExample, Debug)]
22pub struct ExecuteCostTable {
23    capacity: usize,
24    table: HashMap<Pubkey, u64>,
25    occurrences: HashMap<Pubkey, (usize, u128)>,
26}
27
28impl Default for ExecuteCostTable {
29    fn default() -> Self {
30        ExecuteCostTable::new(DEFAULT_CAPACITY)
31    }
32}
33
34impl ExecuteCostTable {
35    pub fn new(cap: usize) -> Self {
36        Self {
37            capacity: cap,
38            table: HashMap::with_capacity(cap),
39            occurrences: HashMap::with_capacity(cap),
40        }
41    }
42
43    pub fn get_count(&self) -> usize {
44        self.table.len()
45    }
46
47    /// default program cost, set to ComputeBudget::DEFAULT_COMPUTE_UNIT_LIMIT
48    pub fn get_default_compute_unit_limit(&self) -> u64 {
49        DEFAULT_INSTRUCTION_COMPUTE_UNIT_LIMIT as u64
50    }
51
52    /// average cost of all recorded programs
53    pub fn get_global_average_program_cost(&self) -> u64 {
54        if self.table.is_empty() {
55            self.get_default_compute_unit_limit()
56        } else {
57            self.table.values().sum::<u64>() / self.get_count() as u64
58        }
59    }
60
61    /// the most frequently occurring program's cost
62    pub fn get_statistical_mode_program_cost(&self) -> u64 {
63        if self.occurrences.is_empty() {
64            self.get_default_compute_unit_limit()
65        } else {
66            let key = self
67                .occurrences
68                .iter()
69                .max_by_key(|&(_, count)| count)
70                .map(|(key, _)| key)
71                .expect("cannot find mode from cost table");
72
73            *self.table.get(key).unwrap()
74        }
75    }
76
77    /// returns None if program doesn't exist in table. In this case,
78    /// `get_default_compute_unit_limit()`, `get_global_average_program_cost()`
79    /// or `get_statistical_mode_program_cost()` can be used to assign a value
80    /// to new program.
81    pub fn get_cost(&self, key: &Pubkey) -> Option<&u64> {
82        self.table.get(key)
83    }
84
85    /// update-or-insert should be infallible. Query the result of upsert,
86    /// often requires additional calculation, should be lazy.
87    pub fn upsert(&mut self, key: &Pubkey, value: u64) {
88        let need_to_add = !self.table.contains_key(key);
89        let current_size = self.get_count();
90        if current_size >= self.capacity && need_to_add {
91            let prune_to_size = current_size
92                .checked_mul(PRUNE_RATIO)
93                .and_then(|v| v.checked_div(100))
94                .unwrap_or(self.capacity);
95            self.prune_to(&prune_to_size);
96        }
97
98        let program_cost = self.table.entry(*key).or_insert(value);
99        *program_cost = (*program_cost + value) / 2;
100
101        let (count, timestamp) = self
102            .occurrences
103            .entry(*key)
104            .or_insert((0, Self::micros_since_epoch()));
105        *count += 1;
106        *timestamp = Self::micros_since_epoch();
107    }
108
109    /// prune the old programs so the table contains `new_size` of records,
110    /// where `old` is defined as weighted age, which is negatively correlated
111    /// with program's age and how frequently the program is occurrenced.
112    fn prune_to(&mut self, new_size: &usize) {
113        debug!(
114            "prune cost table, current size {}, new size {}",
115            self.get_count(),
116            new_size
117        );
118
119        if *new_size == self.get_count() {
120            return;
121        }
122
123        if *new_size == 0 {
124            self.table.clear();
125            self.occurrences.clear();
126            return;
127        }
128
129        let now = Self::micros_since_epoch();
130        let mut sorted_by_weighted_age: Vec<_> = self
131            .occurrences
132            .iter()
133            .map(|(key, (count, timestamp))| {
134                let age = now - timestamp;
135                let weighted_age = *count as i64 * OCCURRENCES_WEIGHT + -(age as i64);
136                (weighted_age, *key)
137            })
138            .collect();
139        sorted_by_weighted_age.sort_by(|x, y| x.0.partial_cmp(&y.0).unwrap());
140
141        for i in sorted_by_weighted_age.iter() {
142            self.table.remove(&i.1);
143            self.occurrences.remove(&i.1);
144            if *new_size == self.get_count() {
145                break;
146            }
147        }
148    }
149
150    fn micros_since_epoch() -> u128 {
151        std::time::SystemTime::now()
152            .duration_since(std::time::UNIX_EPOCH)
153            .unwrap()
154            .as_micros()
155    }
156}
157
158#[cfg(test)]
159mod tests {
160    use super::*;
161
162    #[test]
163    fn test_execute_cost_table_prune_simple_table() {
164        solana_logger::setup();
165        let capacity: usize = 3;
166        let mut testee = ExecuteCostTable::new(capacity);
167
168        let key1 = Pubkey::new_unique();
169        let key2 = Pubkey::new_unique();
170        let key3 = Pubkey::new_unique();
171
172        testee.upsert(&key1, 1);
173        testee.upsert(&key2, 2);
174        testee.upsert(&key3, 3);
175
176        testee.prune_to(&(capacity - 1));
177
178        // the oldest, key1, should be pruned
179        assert!(testee.get_cost(&key1).is_none());
180        assert!(testee.get_cost(&key2).is_some());
181        assert!(testee.get_cost(&key2).is_some());
182    }
183
184    #[test]
185    fn test_execute_cost_table_prune_weighted_table() {
186        solana_logger::setup();
187        let capacity: usize = 3;
188        let mut testee = ExecuteCostTable::new(capacity);
189
190        let key1 = Pubkey::new_unique();
191        let key2 = Pubkey::new_unique();
192        let key3 = Pubkey::new_unique();
193
194        // simulate a lot of occurrences to key1, so even there're longer than
195        // usual delay between upsert(key1..) and upsert(key2, ..), test
196        // would still satisfy as key1 has enough occurrences to compensate
197        // its age.
198        for i in 0..1000 {
199            testee.upsert(&key1, i);
200        }
201        testee.upsert(&key2, 2);
202        testee.upsert(&key3, 3);
203
204        testee.prune_to(&(capacity - 1));
205
206        // the oldest, key1, has many counts; 2nd oldest Key2 has 1 count;
207        // expect key2 to be pruned.
208        assert!(testee.get_cost(&key1).is_some());
209        assert!(testee.get_cost(&key2).is_none());
210        assert!(testee.get_cost(&key3).is_some());
211    }
212
213    #[test]
214    fn test_execute_cost_table_upsert_within_capacity() {
215        solana_logger::setup();
216        let mut testee = ExecuteCostTable::default();
217
218        let key1 = Pubkey::new_unique();
219        let key2 = Pubkey::new_unique();
220        let cost1: u64 = 100;
221        let cost2: u64 = 110;
222
223        // query empty table
224        assert!(testee.get_cost(&key1).is_none());
225
226        // insert one record
227        testee.upsert(&key1, cost1);
228        assert_eq!(1, testee.get_count());
229        assert_eq!(cost1, testee.get_global_average_program_cost());
230        assert_eq!(cost1, testee.get_statistical_mode_program_cost());
231        assert_eq!(&cost1, testee.get_cost(&key1).unwrap());
232
233        // insert 2nd record
234        testee.upsert(&key2, cost2);
235        assert_eq!(2, testee.get_count());
236        assert_eq!(
237            (cost1 + cost2) / 2_u64,
238            testee.get_global_average_program_cost()
239        );
240        assert_eq!(cost2, testee.get_statistical_mode_program_cost());
241        assert_eq!(&cost1, testee.get_cost(&key1).unwrap());
242        assert_eq!(&cost2, testee.get_cost(&key2).unwrap());
243
244        // update 1st record
245        testee.upsert(&key1, cost2);
246        assert_eq!(2, testee.get_count());
247        assert_eq!(
248            ((cost1 + cost2) / 2 + cost2) / 2_u64,
249            testee.get_global_average_program_cost()
250        );
251        assert_eq!(
252            (cost1 + cost2) / 2,
253            testee.get_statistical_mode_program_cost()
254        );
255        assert_eq!(&((cost1 + cost2) / 2), testee.get_cost(&key1).unwrap());
256        assert_eq!(&cost2, testee.get_cost(&key2).unwrap());
257    }
258
259    #[test]
260    fn test_execute_cost_table_upsert_exceeds_capacity() {
261        solana_logger::setup();
262        let capacity: usize = 2;
263        let mut testee = ExecuteCostTable::new(capacity);
264
265        let key1 = Pubkey::new_unique();
266        let key2 = Pubkey::new_unique();
267        let key3 = Pubkey::new_unique();
268        let key4 = Pubkey::new_unique();
269        let cost1: u64 = 100;
270        let cost2: u64 = 110;
271        let cost3: u64 = 120;
272        let cost4: u64 = 130;
273
274        // insert one record
275        testee.upsert(&key1, cost1);
276        assert_eq!(1, testee.get_count());
277        assert_eq!(&cost1, testee.get_cost(&key1).unwrap());
278
279        // insert 2nd record
280        testee.upsert(&key2, cost2);
281        assert_eq!(2, testee.get_count());
282        assert_eq!(&cost1, testee.get_cost(&key1).unwrap());
283        assert_eq!(&cost2, testee.get_cost(&key2).unwrap());
284
285        // insert 3rd record, pushes out the oldest (eg 1st) record
286        testee.upsert(&key3, cost3);
287        assert_eq!(2, testee.get_count());
288        assert_eq!(
289            (cost2 + cost3) / 2_u64,
290            testee.get_global_average_program_cost()
291        );
292        assert_eq!(cost3, testee.get_statistical_mode_program_cost());
293        assert!(testee.get_cost(&key1).is_none());
294        assert_eq!(&cost2, testee.get_cost(&key2).unwrap());
295        assert_eq!(&cost3, testee.get_cost(&key3).unwrap());
296
297        // update 2nd record, so the 3rd becomes the oldest
298        // add 4th record, pushes out 3rd key
299        testee.upsert(&key2, cost1);
300        testee.upsert(&key4, cost4);
301        assert_eq!(
302            ((cost1 + cost2) / 2 + cost4) / 2_u64,
303            testee.get_global_average_program_cost()
304        );
305        assert_eq!(
306            (cost1 + cost2) / 2,
307            testee.get_statistical_mode_program_cost()
308        );
309        assert_eq!(2, testee.get_count());
310        assert!(testee.get_cost(&key1).is_none());
311        assert_eq!(&((cost1 + cost2) / 2), testee.get_cost(&key2).unwrap());
312        assert!(testee.get_cost(&key3).is_none());
313        assert_eq!(&cost4, testee.get_cost(&key4).unwrap());
314    }
315}
solana_runtime/execute_cost_table.rs

solana_runtime/
execute_cost_table.rs
