From e5dbe10d9599b9a53fa07e6fadfaf427ba6d69e3 Mon Sep 17 00:00:00 2001 From: Vratko Polak Date: Tue, 17 Oct 2023 16:31:35 +0200 Subject: feat(MLRsearch): MLRsearch v7 Replaces MLRv2, suitable for "big bang" upgrade across CSIT. PyPI metadata updated only partially (full edits will come separately). Pylint wants less complexity, but the differences are only minor. + Use the same (new CSIT) defaults everywhere, also in Python library. + Update also PLRsearch to use the new result class. + Make upper bound optional in UTI. + Fix ASTF approximate duration detection. + Do not keep approximated_receive_rate (for MRR) in result structure. Change-Id: I03406f32d5c93f56b527cb3f93791b61955dfd74 Signed-off-by: Vratko Polak --- .../python/MLRsearch/discrete_interval.py | 140 +++++++++++++++++++++ 1 file changed, 140 insertions(+) create mode 100644 resources/libraries/python/MLRsearch/discrete_interval.py (limited to 'resources/libraries/python/MLRsearch/discrete_interval.py') diff --git a/resources/libraries/python/MLRsearch/discrete_interval.py b/resources/libraries/python/MLRsearch/discrete_interval.py new file mode 100644 index 0000000000..0a3bf443a8 --- /dev/null +++ b/resources/libraries/python/MLRsearch/discrete_interval.py @@ -0,0 +1,140 @@ +# Copyright (c) 2023 Cisco and/or its affiliates. +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at: +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +"""Module defining DiscreteInterval class.""" + +from dataclasses import dataclass + +from .dataclass import secondary_field +from .discrete_load import DiscreteLoad +from .discrete_width import DiscreteWidth + + +# TODO: Can this be frozen? +@dataclass +class DiscreteInterval: + """Interval class with more computations available. + + Along discrete form of width, + a MLR specific way for halving the interval is also included. + + The two primary field values do not have to be valid relevant bounds, + but at the end of the search, they usually are. + + The load values must be round. + """ + + lower_bound: DiscreteLoad + """Value for the lower intended load (or load stats or similar).""" + upper_bound: DiscreteLoad + """Value for the higher intended load (or load stats or similar).""" + # Primary fields above, derived below. + discrete_width: DiscreteWidth = secondary_field() + """Discrete width between intended loads (upper_bound minus lower_bound).""" + + def __post_init__(self) -> None: + """Sort bounds by intended load, compute secondary quantities. + + :raises RuntimeError: If a result used non-rounded load. + """ + if not self.lower_bound.is_round: + raise RuntimeError(f"Non-round lower bound: {self.lower_bound!r}") + if not self.upper_bound.is_round: + raise RuntimeError(f"Non-round upper bound: {self.upper_bound!r}") + if self.lower_bound > self.upper_bound: + tmp = self.lower_bound + self.lower_bound = self.upper_bound + self.upper_bound = tmp + self.discrete_width = self.upper_bound - self.lower_bound + + def __str__(self) -> str: + """Convert to a short human-readable string. + + :returns: The short string. + :rtype: str + """ + return ( + f"lower_bound=({self.lower_bound}),upper_bound=({self.upper_bound})" + ) + + # TODO: Use "target" instad of "goal" in argument and variable names. + + def width_in_goals(self, goal: DiscreteWidth) -> float: + """Return relative width as a multiple of the given goal (int form). + + Integer forms are used for computation, safe as loads are rounded. + The result is a float, as self int may not be divisible by goal int. + + :param goal: A relative width amount to be used as a unit. + :type goal: DiscreteWidth + :returns: Self width in multiples of (integer form of) goal width. + :rtype: float + """ + return int(self.discrete_width) / int(goal) + + def middle(self, goal: DiscreteWidth) -> DiscreteLoad: + """Return new intended load (discrete form) in the middle. + + All calculations are based on int forms. + + One of the halfs is rounded to a power-of-two multiple of the goal. + The power that leads to most even split is used. + Lower width is the smaller one (if not exactly even). + + This approach prefers lower loads (to remain conservative) and can save + some measurements (when all middle measurements have high loss). + Note that when competing with external search from above, + that search is already likely to produce widths that are + power-of-two multiples of the target width. + + If the interval width is one goal (or less), RuntimeError is raised. + If the interval width is between one and two goals (not including), + a more even split is attempted (using half the goal value). + + :param goal: Target width goal to use for uneven halving. + :type goal: DiscreteWidth + :returns: New load to use for bisecting. + :rtype: DiscreteLoad + :raises RuntimeError: If an internal inconsistency is detected. + """ + int_self, int_goal = int(self.discrete_width), int(goal) + if int_self <= int_goal: + raise RuntimeError(f"Do not halve small enough interval: {self!r}") + if int_self == 2 * int_goal: + # Even split, return here simplifies the while loop below. + return self.lower_bound + goal + if int_self < 2 * int_goal: + # This can only happen when int_goal >= 2. + # In this case, we do not have good enough split at this width goal, + # but maybe this is not the final target, so we can attempt + # a split at half width goal. + if not int_goal % 2: + return self.middle(goal=goal.half_rounded_down()) + # Odd int_goal, so this must by the last phase. Do even split. + lo_width = self.discrete_width.half_rounded_down() + return self.lower_bound + lo_width + hi_width = goal + lo_width = self.discrete_width - hi_width + # We know lo_width > hi_width because we did not do the even split. + while 1: + hi2_width = hi_width * 2 + lo2_width = self.discrete_width - hi2_width + if lo2_width <= hi2_width: + break + hi_width, lo_width = hi2_width, lo2_width + # Which of the two options is more even? Product decides. + if int(hi_width) * int(lo_width) > int(hi2_width) * int(lo2_width): + # Previous attempt was more even, but hi_width was the smaller one. + lo2_width = hi_width + # Else lo2_width is more even and no larger than hi2_width. + return self.lower_bound + lo2_width -- cgit 1.2.3-korg