1 # Copyright (c) 2023 Cisco and/or its affiliates.
2 # Licensed under the Apache License, Version 2.0 (the "License");
3 # you may not use this file except in compliance with the License.
4 # You may obtain a copy of the License at:
6 # http://www.apache.org/licenses/LICENSE-2.0
8 # Unless required by applicable law or agreed to in writing, software
9 # distributed under the License is distributed on an "AS IS" BASIS,
10 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 # See the License for the specific language governing permissions and
12 # limitations under the License.
14 """Module defining LoadRounding class."""
18 from dataclasses import dataclass
19 from typing import List, Tuple
21 from .dataclass import secondary_field
26 """Class encapsulating stateful utilities that round intended load values.
28 For MLRsearch algorithm logic to be correct, it is important that
29 interval width expansion and narrowing are exactly reversible,
30 which is not true in general for floating point number arithmetics.
32 This class offers conversion to and from an integer quantity.
33 Operations in the integer realm are guaranteed to be reversible,
34 so the only risk is when converting between float and integer realm.
36 Which relative width corresponds to the unit integer
37 is computed in initialization from width goals,
38 striking a balance between memory requirements and precision.
40 There are two quality knobs. One restricts how far
41 can an integer be from the exact float value.
42 The other restrict how close it can be. That is to make sure
43 even with unpredictable rounding errors during the conversion,
44 the converted integer value is never bigger than the intended float value,
45 to ensure the intervals returned from MLRsearch will always
46 meet the relative width goal.
48 An instance of this class is mutable only in the sense it contains
49 a growing cache of previously computed values.
52 # TODO: Hide the cache and present as frozen hashable object.
55 """Minimal intended load [tps] to support, must be positive."""
57 """Maximal intended load [tps] to support, must be bigger than min load."""
58 float_goals: Tuple[float]
59 """Relative width goals to approximate, each must be positive
60 and smaller than one. Deduplicated and sorted in post init."""
61 quality_lower: float = 0.99
62 """Minimal multiple of each goal to be achievable."""
63 quality_upper: float = 0.999999
64 """Maximal multiple of each goal to be achievable."""
65 # Primary fields above, computed fields below.
66 max_int_load: int = secondary_field()
67 """Integer for max load (min load int is zero)."""
68 _int2load: List[Tuple[int, float]] = secondary_field()
69 """Known int values (sorted) and their float equivalents."""
71 def __post_init__(self) -> None:
72 """Ensure types, perform checks, initialize conversion structures.
74 :raises RuntimeError: If a requirement is not met.
76 self.min_load = float(self.min_load)
77 self.max_load = float(self.max_load)
78 if not 0.0 < self.min_load < self.max_load:
79 raise RuntimeError("Load limits not supported: {self}")
80 self.quality_lower = float(self.quality_lower)
81 self.quality_upper = float(self.quality_upper)
82 if not 0.0 < self.quality_lower < self.quality_upper < 1.0:
83 raise RuntimeError("Qualities not supported: {self}")
85 for goal in self.float_goals:
87 if not 0.0 < goal < 1.0:
88 raise RuntimeError(f"Goal width {goal} is not supported.")
90 self.float_goals = tuple(sorted(set(goals)))
91 self.max_int_load = self._find_ints()
93 self._int2load.append((0, self.min_load))
94 self._int2load.append((self.max_int_load, self.max_load))
96 def _find_ints(self) -> int:
97 """Find and return value for max_int_load.
99 Separated out of post init, as this is less conversion and checking,
100 and more math and searching.
102 A dumb implementation would start with 1 and kept increasing by 1
103 until all goals are within quality limits.
104 An actual implementation is smarter with the increment,
105 so it is expected to find the resulting values somewhat faster.
107 :returns: Value to be stored as max_int_load.
110 minmax_log_width = math.log(self.max_load) - math.log(self.min_load)
111 log_goals = [-math.log1p(-goal) for goal in self.float_goals]
114 log_width_unit = minmax_log_width / candidate
115 # Fallback to increment by one if rounding errors make tries bad.
116 next_tries = [candidate + 1]
118 for log_goal in log_goals:
119 units = log_goal / log_width_unit
120 int_units = math.floor(units)
121 quality = int_units / units
122 if not self.quality_lower <= quality <= self.quality_upper:
124 target = (int_units + 1) / self.quality_upper
125 next_try = (target / units) * candidate
126 next_tries.append(next_try)
127 # Else quality acceptable, not bumping the candidate.
130 candidate = int(math.ceil(max(next_tries)))
132 def int2float(self, int_load: int) -> float:
133 """Convert from int to float tps load. Expand internal table as needed.
135 Too low or too high ints result in min or max load respectively.
137 :param int_load: Integer quantity to turn back into float load.
139 :returns: Converted load in tps.
141 :raises RuntimeError: If internal inconsistency is detected.
145 if int_load >= self.max_int_load:
147 lo_index, hi_index = 0, len(self._int2load)
148 lo_int, hi_int = 0, self.max_int_load
149 lo_load, hi_load = self.min_load, self.max_load
150 while hi_int - lo_int >= 2:
151 mid_index = (hi_index + lo_index + 1) // 2
152 if mid_index >= hi_index:
153 mid_int = (hi_int + lo_int) // 2
154 log_coeff = math.log(hi_load) - math.log(lo_load)
155 log_coeff *= (mid_int - lo_int) / (hi_int - lo_int)
156 mid_load = lo_load * math.exp(log_coeff)
157 self._int2load.insert(mid_index, (mid_int, mid_load))
159 mid_int, mid_load = self._int2load[mid_index]
160 if mid_int < int_load:
161 lo_index, lo_int, lo_load = mid_index, mid_int, mid_load
163 if mid_int > int_load:
164 hi_index, hi_int, hi_load = mid_index, mid_int, mid_load
167 raise RuntimeError("Bisect in int2float failed.")
169 def float2int(self, float_load: float) -> int:
170 """Convert and round from tps load to int. Maybe expand internal table.
172 Too low or too high load result in zero or max int respectively.
174 Result value is rounded down to an integer.
176 :param float_load: Tps quantity to convert into int.
177 :type float_load: float
178 :returns: Converted integer value suitable for halving.
181 if float_load <= self.min_load:
183 if float_load >= self.max_load:
184 return self.max_int_load
185 lo_index, hi_index = 0, len(self._int2load)
186 lo_int, hi_int = 0, self.max_int_load
187 lo_load, hi_load = self.min_load, self.max_load
188 while hi_int - lo_int >= 2:
189 mid_index = (hi_index + lo_index + 1) // 2
190 if mid_index >= hi_index:
191 mid_int = (hi_int + lo_int) // 2
192 log_coeff = math.log(hi_load) - math.log(lo_load)
193 log_coeff *= (mid_int - lo_int) / (hi_int - lo_int)
194 mid_load = lo_load * math.exp(log_coeff)
195 self._int2load.insert(mid_index, (mid_int, mid_load))
197 mid_int, mid_load = self._int2load[mid_index]
198 if mid_load < float_load:
199 lo_index, lo_int, lo_load = mid_index, mid_int, mid_load
201 if mid_load > float_load:
202 hi_index, hi_int, hi_load = mid_index, mid_int, mid_load