diff options
Diffstat (limited to '.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram')
8 files changed, 885 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/__init__.py b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/__init__.py new file mode 100644 index 00000000..e69de29b --- /dev/null +++ b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/__init__.py diff --git a/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/buckets.py b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/buckets.py new file mode 100644 index 00000000..e8a93326 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/buckets.py @@ -0,0 +1,190 @@ +# Copyright The OpenTelemetry Authors +# +# 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. + +from math import ceil, log2 + + +class Buckets: + # No method of this class is protected by locks because instances of this + # class are only used in methods that are protected by locks themselves. + + def __init__(self): + self._counts = [0] + + # The term index refers to the number of the exponential histogram bucket + # used to determine its boundaries. The lower boundary of a bucket is + # determined by base ** index and the upper boundary of a bucket is + # determined by base ** (index + 1). index values are signedto account + # for values less than or equal to 1. + + # self._index_* will all have values equal to a certain index that is + # determined by the corresponding mapping _map_to_index function and + # the value of the index depends on the value passed to _map_to_index. + + # Index of the 0th position in self._counts: self._counts[0] is the + # count in the bucket with index self.__index_base. + self.__index_base = 0 + + # self.__index_start is the smallest index value represented in + # self._counts. + self.__index_start = 0 + + # self.__index_start is the largest index value represented in + # self._counts. + self.__index_end = 0 + + @property + def index_start(self) -> int: + return self.__index_start + + @index_start.setter + def index_start(self, value: int) -> None: + self.__index_start = value + + @property + def index_end(self) -> int: + return self.__index_end + + @index_end.setter + def index_end(self, value: int) -> None: + self.__index_end = value + + @property + def index_base(self) -> int: + return self.__index_base + + @index_base.setter + def index_base(self, value: int) -> None: + self.__index_base = value + + @property + def counts(self): + return self._counts + + def get_offset_counts(self): + bias = self.__index_base - self.__index_start + return self._counts[-bias:] + self._counts[:-bias] + + def grow(self, needed: int, max_size: int) -> None: + size = len(self._counts) + bias = self.__index_base - self.__index_start + old_positive_limit = size - bias + + # 2 ** ceil(log2(needed)) finds the smallest power of two that is larger + # or equal than needed: + # 2 ** ceil(log2(1)) == 1 + # 2 ** ceil(log2(2)) == 2 + # 2 ** ceil(log2(3)) == 4 + # 2 ** ceil(log2(4)) == 4 + # 2 ** ceil(log2(5)) == 8 + # 2 ** ceil(log2(6)) == 8 + # 2 ** ceil(log2(7)) == 8 + # 2 ** ceil(log2(8)) == 8 + new_size = min(2 ** ceil(log2(needed)), max_size) + + new_positive_limit = new_size - bias + + tmp = [0] * new_size + tmp[new_positive_limit:] = self._counts[old_positive_limit:] + tmp[0:old_positive_limit] = self._counts[0:old_positive_limit] + self._counts = tmp + + @property + def offset(self) -> int: + return self.__index_start + + def __len__(self) -> int: + if len(self._counts) == 0: + return 0 + + if self.__index_end == self.__index_start and self[0] == 0: + return 0 + + return self.__index_end - self.__index_start + 1 + + def __getitem__(self, key: int) -> int: + bias = self.__index_base - self.__index_start + + if key < bias: + key += len(self._counts) + + key -= bias + + return self._counts[key] + + def downscale(self, amount: int) -> None: + """ + Rotates, then collapses 2 ** amount to 1 buckets. + """ + + bias = self.__index_base - self.__index_start + + if bias != 0: + self.__index_base = self.__index_start + + # [0, 1, 2, 3, 4] Original backing array + + self._counts = self._counts[::-1] + # [4, 3, 2, 1, 0] + + self._counts = ( + self._counts[:bias][::-1] + self._counts[bias:][::-1] + ) + # [3, 4, 0, 1, 2] This is a rotation of the backing array. + + size = 1 + self.__index_end - self.__index_start + each = 1 << amount + inpos = 0 + outpos = 0 + + pos = self.__index_start + + while pos <= self.__index_end: + mod = pos % each + if mod < 0: + mod += each + + index = mod + + while index < each and inpos < size: + if outpos != inpos: + self._counts[outpos] += self._counts[inpos] + self._counts[inpos] = 0 + + inpos += 1 + pos += 1 + index += 1 + + outpos += 1 + + self.__index_start >>= amount + self.__index_end >>= amount + self.__index_base = self.__index_start + + def increment_bucket(self, bucket_index: int, increment: int = 1) -> None: + self._counts[bucket_index] += increment + + def copy_empty(self) -> "Buckets": + copy = Buckets() + + # pylint: disable=no-member + # pylint: disable=protected-access + # pylint: disable=attribute-defined-outside-init + # pylint: disable=invalid-name + copy._Buckets__index_base = self._Buckets__index_base + copy._Buckets__index_start = self._Buckets__index_start + copy._Buckets__index_end = self._Buckets__index_end + copy._counts = [0 for _ in self._counts] + + return copy diff --git a/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/__init__.py b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/__init__.py new file mode 100644 index 00000000..387b1d14 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/__init__.py @@ -0,0 +1,98 @@ +# Copyright The OpenTelemetry Authors +# +# 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. + +from abc import ABC, abstractmethod + + +class Mapping(ABC): + """ + Parent class for `LogarithmMapping` and `ExponentialMapping`. + """ + + # pylint: disable=no-member + def __new__(cls, scale: int): + with cls._mappings_lock: + # cls._mappings and cls._mappings_lock are implemented in each of + # the child classes as a dictionary and a lock, respectively. They + # are not instantiated here because that would lead to both child + # classes having the same instance of cls._mappings and + # cls._mappings_lock. + if scale not in cls._mappings: + cls._mappings[scale] = super().__new__(cls) + cls._mappings[scale]._init(scale) + + return cls._mappings[scale] + + @abstractmethod + def _init(self, scale: int) -> None: + # pylint: disable=attribute-defined-outside-init + + if scale > self._get_max_scale(): + # pylint: disable=broad-exception-raised + raise Exception(f"scale is larger than {self._max_scale}") + + if scale < self._get_min_scale(): + # pylint: disable=broad-exception-raised + raise Exception(f"scale is smaller than {self._min_scale}") + + # The size of the exponential histogram buckets is determined by a + # parameter known as scale, larger values of scale will produce smaller + # buckets. Bucket boundaries of the exponential histogram are located + # at integer powers of the base, where: + # + # base = 2 ** (2 ** (-scale)) + # https://github.com/open-telemetry/opentelemetry-specification/blob/main/specification/metrics/data-model.md#all-scales-use-the-logarithm-function + self._scale = scale + + @abstractmethod + def _get_min_scale(self) -> int: + """ + Return the smallest possible value for the mapping scale + """ + + @abstractmethod + def _get_max_scale(self) -> int: + """ + Return the largest possible value for the mapping scale + """ + + @abstractmethod + def map_to_index(self, value: float) -> int: + """ + Maps positive floating point values to indexes corresponding to + `Mapping.scale`. Implementations are not expected to handle zeros, + +inf, NaN, or negative values. + """ + + @abstractmethod + def get_lower_boundary(self, index: int) -> float: + """ + Returns the lower boundary of a given bucket index. The index is + expected to map onto a range that is at least partially inside the + range of normal floating point values. If the corresponding + bucket's upper boundary is less than or equal to 2 ** -1022, + :class:`~opentelemetry.sdk.metrics.MappingUnderflowError` + will be raised. If the corresponding bucket's lower boundary is greater + than ``sys.float_info.max``, + :class:`~opentelemetry.sdk.metrics.MappingOverflowError` + will be raised. + """ + + @property + def scale(self) -> int: + """ + Returns the parameter that controls the resolution of this mapping. + See: https://github.com/open-telemetry/opentelemetry-specification/blob/main/specification/metrics/datamodel.md#exponential-scale + """ + return self._scale diff --git a/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/errors.py b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/errors.py new file mode 100644 index 00000000..477ed6f0 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/errors.py @@ -0,0 +1,26 @@ +# Copyright The OpenTelemetry Authors +# +# 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. + + +class MappingUnderflowError(Exception): + """ + Raised when computing the lower boundary of an index that maps into a + denormal floating point value. + """ + + +class MappingOverflowError(Exception): + """ + Raised when computing the lower boundary of an index that maps into +inf. + """ diff --git a/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/exponent_mapping.py b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/exponent_mapping.py new file mode 100644 index 00000000..297bb7a4 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/exponent_mapping.py @@ -0,0 +1,141 @@ +# Copyright The OpenTelemetry Authors +# +# 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. + +from math import ldexp +from threading import Lock + +from opentelemetry.sdk.metrics._internal.exponential_histogram.mapping import ( + Mapping, +) +from opentelemetry.sdk.metrics._internal.exponential_histogram.mapping.errors import ( + MappingOverflowError, + MappingUnderflowError, +) +from opentelemetry.sdk.metrics._internal.exponential_histogram.mapping.ieee_754 import ( + MANTISSA_WIDTH, + MAX_NORMAL_EXPONENT, + MIN_NORMAL_EXPONENT, + MIN_NORMAL_VALUE, + get_ieee_754_exponent, + get_ieee_754_mantissa, +) + + +class ExponentMapping(Mapping): + # Reference implementation here: + # https://github.com/open-telemetry/opentelemetry-go/blob/0e6f9c29c10d6078e8131418e1d1d166c7195d61/sdk/metric/aggregator/exponential/mapping/exponent/exponent.go + + _mappings = {} + _mappings_lock = Lock() + + _min_scale = -10 + _max_scale = 0 + + def _get_min_scale(self): + # _min_scale defines the point at which the exponential mapping + # function becomes useless for 64-bit floats. With scale -10, ignoring + # subnormal values, bucket indices range from -1 to 1. + return -10 + + def _get_max_scale(self): + # _max_scale is the largest scale supported by exponential mapping. Use + # a logarithm mapping for larger scales. + return 0 + + def _init(self, scale: int): + # pylint: disable=attribute-defined-outside-init + + super()._init(scale) + + # self._min_normal_lower_boundary_index is the largest index such that + # base ** index < MIN_NORMAL_VALUE and + # base ** (index + 1) >= MIN_NORMAL_VALUE. An exponential histogram + # bucket with this index covers the range + # (base ** index, base (index + 1)], including MIN_NORMAL_VALUE. This + # is the smallest valid index that contains at least one normal value. + index = MIN_NORMAL_EXPONENT >> -self._scale + + if -self._scale < 2: + # For scales -1 and 0, the maximum value 2 ** -1022 is a + # power-of-two multiple, meaning base ** index == MIN_NORMAL_VALUE. + # Subtracting 1 so that base ** (index + 1) == MIN_NORMAL_VALUE. + index -= 1 + + self._min_normal_lower_boundary_index = index + + # self._max_normal_lower_boundary_index is the index such that + # base**index equals the greatest representable lower boundary. An + # exponential histogram bucket with this index covers the range + # ((2 ** 1024) / base, 2 ** 1024], which includes opentelemetry.sdk. + # metrics._internal.exponential_histogram.ieee_754.MAX_NORMAL_VALUE. + # This bucket is incomplete, since the upper boundary cannot be + # represented. One greater than this index corresponds with the bucket + # containing values > 2 ** 1024. + self._max_normal_lower_boundary_index = ( + MAX_NORMAL_EXPONENT >> -self._scale + ) + + def map_to_index(self, value: float) -> int: + if value < MIN_NORMAL_VALUE: + return self._min_normal_lower_boundary_index + + exponent = get_ieee_754_exponent(value) + + # Positive integers are represented in binary as having an infinite + # amount of leading zeroes, for example 2 is represented as ...00010. + + # A negative integer -x is represented in binary as the complement of + # (x - 1). For example, -4 is represented as the complement of 4 - 1 + # == 3. 3 is represented as ...00011. Its compliment is ...11100, the + # binary representation of -4. + + # get_ieee_754_mantissa(value) gets the positive integer made up + # from the rightmost MANTISSA_WIDTH bits (the mantissa) of the IEEE + # 754 representation of value. If value is an exact power of 2, all + # these MANTISSA_WIDTH bits would be all zeroes, and when 1 is + # subtracted the resulting value is -1. The binary representation of + # -1 is ...111, so when these bits are right shifted MANTISSA_WIDTH + # places, the resulting value for correction is -1. If value is not an + # exact power of 2, at least one of the rightmost MANTISSA_WIDTH + # bits would be 1 (even for values whose decimal part is 0, like 5.0 + # since the IEEE 754 of such number is too the product of a power of 2 + # (defined in the exponent part of the IEEE 754 representation) and the + # value defined in the mantissa). Having at least one of the rightmost + # MANTISSA_WIDTH bit being 1 means that get_ieee_754(value) will + # always be greater or equal to 1, and when 1 is subtracted, the + # result will be greater or equal to 0, whose representation in binary + # will be of at most MANTISSA_WIDTH ones that have an infinite + # amount of leading zeroes. When those MANTISSA_WIDTH bits are + # shifted to the right MANTISSA_WIDTH places, the resulting value + # will be 0. + + # In summary, correction will be -1 if value is a power of 2, 0 if not. + + # FIXME Document why we can assume value will not be 0, inf, or NaN. + correction = (get_ieee_754_mantissa(value) - 1) >> MANTISSA_WIDTH + + return (exponent + correction) >> -self._scale + + def get_lower_boundary(self, index: int) -> float: + if index < self._min_normal_lower_boundary_index: + raise MappingUnderflowError() + + if index > self._max_normal_lower_boundary_index: + raise MappingOverflowError() + + return ldexp(1, index << -self._scale) + + @property + def scale(self) -> int: + return self._scale diff --git a/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/ieee_754.md b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/ieee_754.md new file mode 100644 index 00000000..0cf5c8c5 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/ieee_754.md @@ -0,0 +1,175 @@ +# IEEE 754 Explained + +IEEE 754 is a standard that defines a way to represent certain mathematical +objects using binary numbers. + +## Binary Number Fields + +The binary numbers used in IEEE 754 can have different lengths, the length that +is interesting for the purposes of this project is 64 bits. These binary +numbers are made up of 3 contiguous fields of bits, from left to right: + +1. 1 sign bit +2. 11 exponent bits +3. 52 mantissa bits + +Depending on the values these fields have, the represented mathematical object +can be one of: + +* Floating point number +* Zero +* NaN +* Infinite + +## Floating Point Numbers + +IEEE 754 represents a floating point number $f$ using an exponential +notation with 4 components: $sign$, $mantissa$, $base$ and $exponent$: + +$$f = sign \times mantissa \times base ^ {exponent}$$ + +There are two possible representations of floating point numbers: +_normal_ and _denormal_, which have different valid values for +their $mantissa$ and $exponent$ fields. + +### Binary Representation + +$sign$, $mantissa$, and $exponent$ are represented in binary, the +representation of each component has certain details explained next. + +$base$ is always $2$ and it is not represented in binary. + +#### Sign + +$sign$ can have 2 values: + +1. $1$ if the `sign` bit is `0` +2. $-1$ if the `sign` bit is `1`. + +#### Mantissa + +##### Normal Floating Point Numbers + +$mantissa$ is a positive fractional number whose integer part is $1$, for example +$1.2345 \dots$. The `mantissa` bits represent only the fractional part and the +$mantissa$ value can be calculated as: + +$$mantissa = 1 + \sum_{i=1}^{52} b_{i} \times 2^{-i} = 1 + \frac{b_{1}}{2^{1}} + \frac{b_{2}}{2^{2}} + \dots + \frac{b_{51}}{2^{51}} + \frac{b_{52}}{2^{52}}$$ + +Where $b_{i}$ is: + +1. $0$ if the bit at the position `i - 1` is `0`. +2. $1$ if the bit at the position `i - 1` is `1`. + +##### Denormal Floating Point Numbers + +$mantissa$ is a positive fractional number whose integer part is $0$, for example +$0.12345 \dots$. The `mantissa` bits represent only the fractional part and the +$mantissa$ value can be calculated as: + +$$mantissa = \sum_{i=1}^{52} b_{i} \times 2^{-i} = \frac{b_{1}}{2^{1}} + \frac{b_{2}}{2^{2}} + \dots + \frac{b_{51}}{2^{51}} + \frac{b_{52}}{2^{52}}$$ + +Where $b_{i}$ is: + +1. $0$ if the bit at the position `i - 1` is `0`. +2. $1$ if the bit at the position `i - 1` is `1`. + +#### Exponent + +##### Normal Floating Point Numbers + +Only the following bit sequences are allowed: `00000000001` to `11111111110`. +That is, there must be at least one `0` and one `1` in the exponent bits. + +The actual value of the $exponent$ can be calculated as: + +$$exponent = v - bias$$ + +where $v$ is the value of the binary number in the exponent bits and $bias$ is $1023$. +Considering the restrictions above, the respective minimum and maximum values for the +exponent are: + +1. `00000000001` = $1$, $1 - 1023 = -1022$ +2. `11111111110` = $2046$, $2046 - 1023 = 1023$ + +So, $exponent$ is an integer in the range $\left[-1022, 1023\right]$. + + +##### Denormal Floating Point Numbers + +$exponent$ is always $-1022$. Nevertheless, it is always represented as `00000000000`. + +### Normal and Denormal Floating Point Numbers + +The smallest absolute value a normal floating point number can have is calculated +like this: + +$$1 \times 1.0\dots0 \times 2^{-1022} = 2.2250738585072014 \times 10^{-308}$$ + +Since normal floating point numbers always have a $1$ as the integer part of the +$mantissa$, then smaller values can be achieved by using the smallest possible exponent +( $-1022$ ) and a $0$ in the integer part of the $mantissa$, but significant digits are lost. + +The smallest absolute value a denormal floating point number can have is calculated +like this: + +$$1 \times 2^{-52} \times 2^{-1022} = 5 \times 10^{-324}$$ + +## Zero + +Zero is represented like this: + +* Sign bit: `X` +* Exponent bits: `00000000000` +* Mantissa bits: `0000000000000000000000000000000000000000000000000000` + +where `X` means `0` or `1`. + +## NaN + +There are 2 kinds of NaNs that are represented: + +1. QNaNs (Quiet NaNs): represent the result of indeterminate operations. +2. SNaNs (Signalling NaNs): represent the result of invalid operations. + +### QNaNs + +QNaNs are represented like this: + +* Sign bit: `X` +* Exponent bits: `11111111111` +* Mantissa bits: `1XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX` + +where `X` means `0` or `1`. + +### SNaNs + +SNaNs are represented like this: + +* Sign bit: `X` +* Exponent bits: `11111111111` +* Mantissa bits: `0XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX1` + +where `X` means `0` or `1`. + +## Infinite + +### Positive Infinite + +Positive infinite is represented like this: + +* Sign bit: `0` +* Exponent bits: `11111111111` +* Mantissa bits: `0000000000000000000000000000000000000000000000000000` + +where `X` means `0` or `1`. + +### Negative Infinite + +Negative infinite is represented like this: + +* Sign bit: `1` +* Exponent bits: `11111111111` +* Mantissa bits: `0000000000000000000000000000000000000000000000000000` + +where `X` means `0` or `1`. diff --git a/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/ieee_754.py b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/ieee_754.py new file mode 100644 index 00000000..d4b7e861 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/ieee_754.py @@ -0,0 +1,117 @@ +# Copyright The OpenTelemetry Authors +# +# 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. + +from ctypes import c_double, c_uint64 +from sys import float_info + +# IEEE 754 64-bit floating point numbers use 11 bits for the exponent and 52 +# bits for the mantissa. +MANTISSA_WIDTH = 52 +EXPONENT_WIDTH = 11 + +# This mask is equivalent to 52 "1" bits (there are 13 hexadecimal 4-bit "f"s +# in the mantissa mask, 13 * 4 == 52) or 0xfffffffffffff in hexadecimal. +MANTISSA_MASK = (1 << MANTISSA_WIDTH) - 1 + +# There are 11 bits for the exponent, but the exponent values 0 (11 "0" +# bits) and 2047 (11 "1" bits) have special meanings so the exponent range is +# from 1 to 2046. To calculate the exponent value, 1023 (the bias) is +# subtracted from the exponent, so the exponent value range is from -1022 to +# +1023. +EXPONENT_BIAS = (2 ** (EXPONENT_WIDTH - 1)) - 1 + +# All the exponent mask bits are set to 1 for the 11 exponent bits. +EXPONENT_MASK = ((1 << EXPONENT_WIDTH) - 1) << MANTISSA_WIDTH + +# The sign mask has the first bit set to 1 and the rest to 0. +SIGN_MASK = 1 << (EXPONENT_WIDTH + MANTISSA_WIDTH) + +# For normal floating point numbers, the exponent can have a value in the +# range [-1022, 1023]. +MIN_NORMAL_EXPONENT = -EXPONENT_BIAS + 1 +MAX_NORMAL_EXPONENT = EXPONENT_BIAS + +# The smallest possible normal value is 2.2250738585072014e-308. +# This value is the result of using the smallest possible number in the +# mantissa, 1.0000000000000000000000000000000000000000000000000000 (52 "0"s in +# the fractional part) and a single "1" in the exponent. +# Finally 1 * (2 ** -1022) = 2.2250738585072014e-308. +MIN_NORMAL_VALUE = float_info.min + +# Greatest possible normal value (1.7976931348623157e+308) +# The binary representation of a float in scientific notation uses (for the +# mantissa) one bit for the integer part (which is implicit) and 52 bits for +# the fractional part. Consider a float binary 1.111. It is equal to 1 + 1/2 + +# 1/4 + 1/8. The greatest possible value in the 52-bit binary mantissa would be +# then 1.1111111111111111111111111111111111111111111111111111 (52 "1"s in the +# fractional part) whose decimal value is 1.9999999999999998. Finally, +# 1.9999999999999998 * (2 ** 1023) = 1.7976931348623157e+308. +MAX_NORMAL_VALUE = float_info.max + + +def get_ieee_754_exponent(value: float) -> int: + """ + Gets the exponent of the IEEE 754 representation of a float. + """ + + return ( + ( + # This step gives the integer that corresponds to the IEEE 754 + # representation of a float. For example, consider + # -MAX_NORMAL_VALUE for an example. We choose this value because + # of its binary representation which makes easy to understand the + # subsequent operations. + # + # c_uint64.from_buffer(c_double(-MAX_NORMAL_VALUE)).value == 18442240474082181119 + # bin(18442240474082181119) == '0b1111111111101111111111111111111111111111111111111111111111111111' + # + # The first bit of the previous binary number is the sign bit: 1 (1 means negative, 0 means positive) + # The next 11 bits are the exponent bits: 11111111110 + # The next 52 bits are the mantissa bits: 1111111111111111111111111111111111111111111111111111 + # + # This step isolates the exponent bits, turning every bit outside + # of the exponent field (sign and mantissa bits) to 0. + c_uint64.from_buffer(c_double(value)).value & EXPONENT_MASK + # For the example this means: + # 18442240474082181119 & EXPONENT_MASK == 9214364837600034816 + # bin(9214364837600034816) == '0b111111111100000000000000000000000000000000000000000000000000000' + # Notice that the previous binary representation does not include + # leading zeroes, so the sign bit is not included since it is a + # zero. + ) + # This step moves the exponent bits to the right, removing the + # mantissa bits that were set to 0 by the previous step. This + # leaves the IEEE 754 exponent value, ready for the next step. + >> MANTISSA_WIDTH + # For the example this means: + # 9214364837600034816 >> MANTISSA_WIDTH == 2046 + # bin(2046) == '0b11111111110' + # As shown above, these are the original 11 bits that correspond to the + # exponent. + # This step subtracts the exponent bias from the IEEE 754 value, + # leaving the actual exponent value. + ) - EXPONENT_BIAS + # For the example this means: + # 2046 - EXPONENT_BIAS == 1023 + # As mentioned in a comment above, the largest value for the exponent is + + +def get_ieee_754_mantissa(value: float) -> int: + return ( + c_uint64.from_buffer(c_double(value)).value + # This step isolates the mantissa bits. There is no need to do any + # bit shifting as the mantissa bits are already the rightmost field + # in an IEEE 754 representation. + & MANTISSA_MASK + ) diff --git a/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/logarithm_mapping.py b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/logarithm_mapping.py new file mode 100644 index 00000000..e73f3a81 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/opentelemetry/sdk/metrics/_internal/exponential_histogram/mapping/logarithm_mapping.py @@ -0,0 +1,138 @@ +# Copyright The OpenTelemetry Authors +# +# 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. + +from math import exp, floor, ldexp, log +from threading import Lock + +from opentelemetry.sdk.metrics._internal.exponential_histogram.mapping import ( + Mapping, +) +from opentelemetry.sdk.metrics._internal.exponential_histogram.mapping.errors import ( + MappingOverflowError, + MappingUnderflowError, +) +from opentelemetry.sdk.metrics._internal.exponential_histogram.mapping.ieee_754 import ( + MAX_NORMAL_EXPONENT, + MIN_NORMAL_EXPONENT, + MIN_NORMAL_VALUE, + get_ieee_754_exponent, + get_ieee_754_mantissa, +) + + +class LogarithmMapping(Mapping): + # Reference implementation here: + # https://github.com/open-telemetry/opentelemetry-go/blob/0e6f9c29c10d6078e8131418e1d1d166c7195d61/sdk/metric/aggregator/exponential/mapping/logarithm/logarithm.go + + _mappings = {} + _mappings_lock = Lock() + + _min_scale = 1 + _max_scale = 20 + + def _get_min_scale(self): + # _min_scale ensures that ExponentMapping is used for zero and negative + # scale values. + return self._min_scale + + def _get_max_scale(self): + # FIXME The Go implementation uses a value of 20 here, find out the + # right value for this implementation, more information here: + # https://github.com/lightstep/otel-launcher-go/blob/c9ca8483be067a39ab306b09060446e7fda65f35/lightstep/sdk/metric/aggregator/histogram/structure/README.md#mapping-function + # https://github.com/open-telemetry/opentelemetry-go/blob/0e6f9c29c10d6078e8131418e1d1d166c7195d61/sdk/metric/aggregator/exponential/mapping/logarithm/logarithm.go#L32-L45 + return self._max_scale + + def _init(self, scale: int): + # pylint: disable=attribute-defined-outside-init + + super()._init(scale) + + # self._scale_factor is defined as a multiplier because multiplication + # is faster than division. self._scale_factor is defined as: + # index = log(value) * self._scale_factor + # Where: + # index = log(value) / log(base) + # index = log(value) / log(2 ** (2 ** -scale)) + # index = log(value) / ((2 ** -scale) * log(2)) + # index = log(value) * ((1 / log(2)) * (2 ** scale)) + # self._scale_factor = ((1 / log(2)) * (2 ** scale)) + # self._scale_factor = (1 /log(2)) * (2 ** scale) + # self._scale_factor = ldexp(1 / log(2), scale) + # This implementation was copied from a Java prototype. See: + # https://github.com/newrelic-experimental/newrelic-sketch-java/blob/1ce245713603d61ba3a4510f6df930a5479cd3f6/src/main/java/com/newrelic/nrsketch/indexer/LogIndexer.java + # for the equations used here. + self._scale_factor = ldexp(1 / log(2), scale) + + # self._min_normal_lower_boundary_index is the index such that + # base ** index == MIN_NORMAL_VALUE. An exponential histogram bucket + # with this index covers the range + # (MIN_NORMAL_VALUE, MIN_NORMAL_VALUE * base]. One less than this index + # corresponds with the bucket containing values <= MIN_NORMAL_VALUE. + self._min_normal_lower_boundary_index = ( + MIN_NORMAL_EXPONENT << self._scale + ) + + # self._max_normal_lower_boundary_index is the index such that + # base ** index equals the greatest representable lower boundary. An + # exponential histogram bucket with this index covers the range + # ((2 ** 1024) / base, 2 ** 1024], which includes opentelemetry.sdk. + # metrics._internal.exponential_histogram.ieee_754.MAX_NORMAL_VALUE. + # This bucket is incomplete, since the upper boundary cannot be + # represented. One greater than this index corresponds with the bucket + # containing values > 2 ** 1024. + self._max_normal_lower_boundary_index = ( + (MAX_NORMAL_EXPONENT + 1) << self._scale + ) - 1 + + def map_to_index(self, value: float) -> int: + """ + Maps positive floating point values to indexes corresponding to scale. + """ + + # value is subnormal + if value <= MIN_NORMAL_VALUE: + return self._min_normal_lower_boundary_index - 1 + + # value is an exact power of two. + if get_ieee_754_mantissa(value) == 0: + exponent = get_ieee_754_exponent(value) + return (exponent << self._scale) - 1 + + return min( + floor(log(value) * self._scale_factor), + self._max_normal_lower_boundary_index, + ) + + def get_lower_boundary(self, index: int) -> float: + if index >= self._max_normal_lower_boundary_index: + if index == self._max_normal_lower_boundary_index: + return 2 * exp( + (index - (1 << self._scale)) / self._scale_factor + ) + raise MappingOverflowError() + + if index <= self._min_normal_lower_boundary_index: + if index == self._min_normal_lower_boundary_index: + return MIN_NORMAL_VALUE + if index == self._min_normal_lower_boundary_index - 1: + return ( + exp((index + (1 << self._scale)) / self._scale_factor) / 2 + ) + raise MappingUnderflowError() + + return exp(index / self._scale_factor) + + @property + def scale(self) -> int: + return self._scale |