resources/libraries/python/MLRsearch/load_rounding.py

   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:
   5 #
   6 #     http://www.apache.org/licenses/LICENSE-2.0
   7 #
   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.
  13
  14 """Module defining LoadRounding class."""
  15
  16 import math
  17
  18 from dataclasses import dataclass
  19 from typing import List, Tuple
  20
  21 from .dataclass import secondary_field
  22
  23
  24 @dataclass
  25 class LoadRounding:
  26     """Class encapsulating stateful utilities that round intended load values.
  27
  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.
  31
  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.
  35
  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.
  39
  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.
  47
  48     An instance of this class is mutable only in the sense it contains
  49     a growing cache of previously computed values.
  50     """
  51
  52     # TODO: Hide the cache and present as frozen hashable object.
  53
  54     min_load: float
  55     """Minimal intended load [tps] to support, must be positive."""
  56     max_load: float
  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."""
  70
  71     def __post_init__(self) -> None:
  72         """Ensure types, perform checks, initialize conversion structures.
  73
  74         :raises RuntimeError: If a requirement is not met.
  75         """
  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}")
  84         goals = []
  85         for goal in self.float_goals:
  86             goal = float(goal)
  87             if not 0.0 < goal < 1.0:
  88                 raise RuntimeError(f"Goal width {goal} is not supported.")
  89             goals.append(goal)
  90         self.float_goals = tuple(sorted(set(goals)))
  91         self.max_int_load = self._find_ints()
  92         self._int2load = []
  93         self._int2load.append((0, self.min_load))
  94         self._int2load.append((self.max_int_load, self.max_load))
  95
  96     def _find_ints(self) -> int:
  97         """Find and return value for max_int_load.
  98
  99         Separated out of post init, as this is less conversion and checking,
 100         and more math and searching.
 101
 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.
 106
 107         :returns: Value to be stored as max_int_load.
 108         :rtype: int
 109         """
 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]
 112         candidate = 1
 113         while 1:
 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]
 117             acceptable = True
 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:
 123                     acceptable = False
 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.
 128             if acceptable:
 129                 return candidate
 130             candidate = int(math.ceil(max(next_tries)))
 131
 132     def int2float(self, int_load: int) -> float:
 133         """Convert from int to float tps load. Expand internal table as needed.
 134
 135         Too low or too high ints result in min or max load respectively.
 136
 137         :param int_load: Integer quantity to turn back into float load.
 138         :type int_load: int
 139         :returns: Converted load in tps.
 140         :rtype: float
 141         :raises RuntimeError: If internal inconsistency is detected.
 142         """
 143         if int_load <= 0:
 144             return self.min_load
 145         if int_load >= self.max_int_load:
 146             return self.max_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))
 158                 hi_index += 1
 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
 162                 continue
 163             if mid_int > int_load:
 164                 hi_index, hi_int, hi_load = mid_index, mid_int, mid_load
 165                 continue
 166             return mid_load
 167         raise RuntimeError("Bisect in int2float failed.")
 168
 169     def float2int(self, float_load: float) -> int:
 170         """Convert and round from tps load to int. Maybe expand internal table.
 171
 172         Too low or too high load result in zero or max int respectively.
 173
 174         Result value is rounded down to an integer.
 175
 176         :param float_load: Tps quantity to convert into int.
 177         :type float_load: float
 178         :returns: Converted integer value suitable for halving.
 179         :rtype: int
 180         """
 181         if float_load <= self.min_load:
 182             return 0
 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))
 196                 hi_index += 1
 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
 200                 continue
 201             if mid_load > float_load:
 202                 hi_index, hi_int, hi_load = mid_index, mid_int, mid_load
 203                 continue
 204             return mid_int
 205         return lo_int