We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Consider using binary search for ExplicitBucketHistogram
https://github.com/open-telemetry/opentelemetry-python/blob/dfb5c66ae310001bb40326f6286345b7fa252aba/opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py#L129-L134

Could use some benchmarks, but this is likely to perform better with binary search (builtin `bisect` module) above a certain number of buckets. Also, using a list instead of `OrderedDict` may be faster

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py`
Content:
```
1 # Copyright The OpenTelemetry Authors
2 #
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
6 #
7 #     http://www.apache.org/licenses/LICENSE-2.0
8 #
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
14 
15 from abc import ABC, abstractmethod
16 from collections import OrderedDict
17 from logging import getLogger
18 from math import inf
19 from threading import Lock
20 from typing import Generic, Optional, Sequence, TypeVar
21 
22 from opentelemetry.sdk._metrics.measurement import Measurement
23 from opentelemetry.sdk._metrics.point import (
24     AggregationTemporality,
25     Gauge,
26     Histogram,
27     PointT,
28     Sum,
29 )
30 from opentelemetry.util._time import _time_ns
31 
32 _PointVarT = TypeVar("_PointVarT", bound=PointT)
33 
34 _logger = getLogger(__name__)
35 
36 
37 class _InstrumentMonotonicityAwareAggregation:
38     def __init__(self, instrument_is_monotonic: bool):
39         self._instrument_is_monotonic = instrument_is_monotonic
40         super().__init__()
41 
42 
43 class Aggregation(ABC, Generic[_PointVarT]):
44     def __init__(self):
45         self._lock = Lock()
46 
47     @abstractmethod
48     def aggregate(self, measurement: Measurement) -> None:
49         pass
50 
51     @abstractmethod
52     def collect(self) -> Optional[_PointVarT]:
53         pass
54 
55 
56 class SynchronousSumAggregation(
57     _InstrumentMonotonicityAwareAggregation, Aggregation[Sum]
58 ):
59     def __init__(self, instrument_is_monotonic: bool):
60         super().__init__(instrument_is_monotonic)
61         self._value = 0
62         self._start_time_unix_nano = _time_ns()
63 
64     def aggregate(self, measurement: Measurement) -> None:
65         with self._lock:
66             self._value = self._value + measurement.value
67 
68     def collect(self) -> Optional[Sum]:
69         """
70         Atomically return a point for the current value of the metric and
71         reset the aggregation value.
72         """
73         now = _time_ns()
74 
75         with self._lock:
76             value = self._value
77             start_time_unix_nano = self._start_time_unix_nano
78 
79             self._value = 0
80             self._start_time_unix_nano = now + 1
81 
82         return Sum(
83             aggregation_temporality=AggregationTemporality.DELTA,
84             is_monotonic=self._instrument_is_monotonic,
85             start_time_unix_nano=start_time_unix_nano,
86             time_unix_nano=now,
87             value=value,
88         )
89 
90 
91 class AsynchronousSumAggregation(
92     _InstrumentMonotonicityAwareAggregation, Aggregation[Sum]
93 ):
94     def __init__(self, instrument_is_monotonic: bool):
95         super().__init__(instrument_is_monotonic)
96         self._value = None
97         self._start_time_unix_nano = _time_ns()
98 
99     def aggregate(self, measurement: Measurement) -> None:
100         with self._lock:
101             self._value = measurement.value
102 
103     def collect(self) -> Optional[Sum]:
104         """
105         Atomically return a point for the current value of the metric.
106         """
107         if self._value is None:
108             return None
109 
110         return Sum(
111             start_time_unix_nano=self._start_time_unix_nano,
112             time_unix_nano=_time_ns(),
113             value=self._value,
114             aggregation_temporality=AggregationTemporality.CUMULATIVE,
115             is_monotonic=self._instrument_is_monotonic,
116         )
117 
118 
119 class LastValueAggregation(Aggregation[Gauge]):
120     def __init__(self):
121         super().__init__()
122         self._value = None
123 
124     def aggregate(self, measurement: Measurement):
125         with self._lock:
126             self._value = measurement.value
127 
128     def collect(self) -> Optional[Gauge]:
129         """
130         Atomically return a point for the current value of the metric.
131         """
132         if self._value is None:
133             return None
134 
135         return Gauge(
136             time_unix_nano=_time_ns(),
137             value=self._value,
138         )
139 
140 
141 class ExplicitBucketHistogramAggregation(Aggregation[Histogram]):
142     def __init__(
143         self,
144         boundaries: Sequence[int] = (
145             0,
146             5,
147             10,
148             25,
149             50,
150             75,
151             100,
152             250,
153             500,
154             1000,
155         ),
156         record_min_max: bool = True,
157     ):
158         super().__init__()
159         self._value = OrderedDict([(key, 0) for key in (*boundaries, inf)])
160         self._min = inf
161         self._max = -inf
162         self._sum = 0
163         self._record_min_max = record_min_max
164         self._start_time_unix_nano = _time_ns()
165         self._boundaries = boundaries
166 
167     def aggregate(self, measurement: Measurement) -> None:
168 
169         value = measurement.value
170 
171         if self._record_min_max:
172             self._min = min(self._min, value)
173             self._max = max(self._max, value)
174 
175         self._sum += value
176 
177         for key in self._value.keys():
178 
179             if value < key:
180                 self._value[key] = self._value[key] + 1
181 
182                 break
183 
184     def collect(self) -> Optional[Histogram]:
185         """
186         Atomically return a point for the current value of the metric.
187         """
188         now = _time_ns()
189 
190         with self._lock:
191             value = self._value
192             start_time_unix_nano = self._start_time_unix_nano
193 
194             self._value = OrderedDict(
195                 [(key, 0) for key in (*self._boundaries, inf)]
196             )
197             self._start_time_unix_nano = now + 1
198 
199         return Histogram(
200             start_time_unix_nano=start_time_unix_nano,
201             time_unix_nano=now,
202             bucket_counts=tuple(value.values()),
203             explicit_bounds=self._boundaries,
204             aggregation_temporality=AggregationTemporality.DELTA,
205         )
206
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py b/opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py
--- a/opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py
+++ b/opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py
@@ -13,7 +13,7 @@
 # limitations under the License.
 
 from abc import ABC, abstractmethod
-from collections import OrderedDict
+from bisect import bisect_left
 from logging import getLogger
 from math import inf
 from threading import Lock
@@ -156,13 +156,14 @@
         record_min_max: bool = True,
     ):
         super().__init__()
-        self._value = OrderedDict([(key, 0) for key in (*boundaries, inf)])
+        # pylint: disable=unnecessary-comprehension
+        self._boundaries = [boundary for boundary in (*boundaries, inf)]
+        self.value = [0 for _ in range(len(self._boundaries))]
         self._min = inf
         self._max = -inf
         self._sum = 0
         self._record_min_max = record_min_max
         self._start_time_unix_nano = _time_ns()
-        self._boundaries = boundaries
 
     def aggregate(self, measurement: Measurement) -> None:
 
@@ -174,12 +175,7 @@
 
         self._sum += value
 
-        for key in self._value.keys():
-
-            if value < key:
-                self._value[key] = self._value[key] + 1
-
-                break
+        self.value[bisect_left(self._boundaries, value)] += 1
 
     def collect(self) -> Optional[Histogram]:
         """
@@ -188,18 +184,16 @@
         now = _time_ns()
 
         with self._lock:
-            value = self._value
+            value = self.value
             start_time_unix_nano = self._start_time_unix_nano
 
-            self._value = OrderedDict(
-                [(key, 0) for key in (*self._boundaries, inf)]
-            )
+            self.value = [0 for _ in range(len(self._boundaries))]
             self._start_time_unix_nano = now + 1
 
         return Histogram(
             start_time_unix_nano=start_time_unix_nano,
             time_unix_nano=now,
-            bucket_counts=tuple(value.values()),
+            bucket_counts=tuple(value),
             explicit_bounds=self._boundaries,
             aggregation_temporality=AggregationTemporality.DELTA,
         )

{"golden_diff": "diff --git a/opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py b/opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py\n--- a/opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py\n+++ b/opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py\n@@ -13,7 +13,7 @@\n # limitations under the License.\n \n from abc import ABC, abstractmethod\n-from collections import OrderedDict\n+from bisect import bisect_left\n from logging import getLogger\n from math import inf\n from threading import Lock\n@@ -156,13 +156,14 @@\n         record_min_max: bool = True,\n     ):\n         super().__init__()\n-        self._value = OrderedDict([(key, 0) for key in (*boundaries, inf)])\n+        # pylint: disable=unnecessary-comprehension\n+        self._boundaries = [boundary for boundary in (*boundaries, inf)]\n+        self.value = [0 for _ in range(len(self._boundaries))]\n         self._min = inf\n         self._max = -inf\n         self._sum = 0\n         self._record_min_max = record_min_max\n         self._start_time_unix_nano = _time_ns()\n-        self._boundaries = boundaries\n \n     def aggregate(self, measurement: Measurement) -> None:\n \n@@ -174,12 +175,7 @@\n \n         self._sum += value\n \n-        for key in self._value.keys():\n-\n-            if value < key:\n-                self._value[key] = self._value[key] + 1\n-\n-                break\n+        self.value[bisect_left(self._boundaries, value)] += 1\n \n     def collect(self) -> Optional[Histogram]:\n         \"\"\"\n@@ -188,18 +184,16 @@\n         now = _time_ns()\n \n         with self._lock:\n-            value = self._value\n+            value = self.value\n             start_time_unix_nano = self._start_time_unix_nano\n \n-            self._value = OrderedDict(\n-                [(key, 0) for key in (*self._boundaries, inf)]\n-            )\n+            self.value = [0 for _ in range(len(self._boundaries))]\n             self._start_time_unix_nano = now + 1\n \n         return Histogram(\n             start_time_unix_nano=start_time_unix_nano,\n             time_unix_nano=now,\n-            bucket_counts=tuple(value.values()),\n+            bucket_counts=tuple(value),\n             explicit_bounds=self._boundaries,\n             aggregation_temporality=AggregationTemporality.DELTA,\n         )\n", "issue": "Consider using binary search for ExplicitBucketHistogram\nhttps://github.com/open-telemetry/opentelemetry-python/blob/dfb5c66ae310001bb40326f6286345b7fa252aba/opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py#L129-L134\r\n\r\nCould use some benchmarks, but this is likely to perform better with binary search (builtin `bisect` module) above a certain number of buckets. Also, using a list instead of `OrderedDict` may be faster\n", "before_files": [{"content": "# Copyright The OpenTelemetry Authors\n#\n# Licensed under the Apache License, Version 2.0 (the \"License\");\n# you may not use this file except in compliance with the License.\n# You may obtain a copy of the License at\n#\n#     http://www.apache.org/licenses/LICENSE-2.0\n#\n# Unless required by applicable law or agreed to in writing, software\n# distributed under the License is distributed on an \"AS IS\" BASIS,\n# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n# See the License for the specific language governing permissions and\n# limitations under the License.\n\nfrom abc import ABC, abstractmethod\nfrom collections import OrderedDict\nfrom logging import getLogger\nfrom math import inf\nfrom threading import Lock\nfrom typing import Generic, Optional, Sequence, TypeVar\n\nfrom opentelemetry.sdk._metrics.measurement import Measurement\nfrom opentelemetry.sdk._metrics.point import (\n    AggregationTemporality,\n    Gauge,\n    Histogram,\n    PointT,\n    Sum,\n)\nfrom opentelemetry.util._time import _time_ns\n\n_PointVarT = TypeVar(\"_PointVarT\", bound=PointT)\n\n_logger = getLogger(__name__)\n\n\nclass _InstrumentMonotonicityAwareAggregation:\n    def __init__(self, instrument_is_monotonic: bool):\n        self._instrument_is_monotonic = instrument_is_monotonic\n        super().__init__()\n\n\nclass Aggregation(ABC, Generic[_PointVarT]):\n    def __init__(self):\n        self._lock = Lock()\n\n    @abstractmethod\n    def aggregate(self, measurement: Measurement) -> None:\n        pass\n\n    @abstractmethod\n    def collect(self) -> Optional[_PointVarT]:\n        pass\n\n\nclass SynchronousSumAggregation(\n    _InstrumentMonotonicityAwareAggregation, Aggregation[Sum]\n):\n    def __init__(self, instrument_is_monotonic: bool):\n        super().__init__(instrument_is_monotonic)\n        self._value = 0\n        self._start_time_unix_nano = _time_ns()\n\n    def aggregate(self, measurement: Measurement) -> None:\n        with self._lock:\n            self._value = self._value + measurement.value\n\n    def collect(self) -> Optional[Sum]:\n        \"\"\"\n        Atomically return a point for the current value of the metric and\n        reset the aggregation value.\n        \"\"\"\n        now = _time_ns()\n\n        with self._lock:\n            value = self._value\n            start_time_unix_nano = self._start_time_unix_nano\n\n            self._value = 0\n            self._start_time_unix_nano = now + 1\n\n        return Sum(\n            aggregation_temporality=AggregationTemporality.DELTA,\n            is_monotonic=self._instrument_is_monotonic,\n            start_time_unix_nano=start_time_unix_nano,\n            time_unix_nano=now,\n            value=value,\n        )\n\n\nclass AsynchronousSumAggregation(\n    _InstrumentMonotonicityAwareAggregation, Aggregation[Sum]\n):\n    def __init__(self, instrument_is_monotonic: bool):\n        super().__init__(instrument_is_monotonic)\n        self._value = None\n        self._start_time_unix_nano = _time_ns()\n\n    def aggregate(self, measurement: Measurement) -> None:\n        with self._lock:\n            self._value = measurement.value\n\n    def collect(self) -> Optional[Sum]:\n        \"\"\"\n        Atomically return a point for the current value of the metric.\n        \"\"\"\n        if self._value is None:\n            return None\n\n        return Sum(\n            start_time_unix_nano=self._start_time_unix_nano,\n            time_unix_nano=_time_ns(),\n            value=self._value,\n            aggregation_temporality=AggregationTemporality.CUMULATIVE,\n            is_monotonic=self._instrument_is_monotonic,\n        )\n\n\nclass LastValueAggregation(Aggregation[Gauge]):\n    def __init__(self):\n        super().__init__()\n        self._value = None\n\n    def aggregate(self, measurement: Measurement):\n        with self._lock:\n            self._value = measurement.value\n\n    def collect(self) -> Optional[Gauge]:\n        \"\"\"\n        Atomically return a point for the current value of the metric.\n        \"\"\"\n        if self._value is None:\n            return None\n\n        return Gauge(\n            time_unix_nano=_time_ns(),\n            value=self._value,\n        )\n\n\nclass ExplicitBucketHistogramAggregation(Aggregation[Histogram]):\n    def __init__(\n        self,\n        boundaries: Sequence[int] = (\n            0,\n            5,\n            10,\n            25,\n            50,\n            75,\n            100,\n            250,\n            500,\n            1000,\n        ),\n        record_min_max: bool = True,\n    ):\n        super().__init__()\n        self._value = OrderedDict([(key, 0) for key in (*boundaries, inf)])\n        self._min = inf\n        self._max = -inf\n        self._sum = 0\n        self._record_min_max = record_min_max\n        self._start_time_unix_nano = _time_ns()\n        self._boundaries = boundaries\n\n    def aggregate(self, measurement: Measurement) -> None:\n\n        value = measurement.value\n\n        if self._record_min_max:\n            self._min = min(self._min, value)\n            self._max = max(self._max, value)\n\n        self._sum += value\n\n        for key in self._value.keys():\n\n            if value < key:\n                self._value[key] = self._value[key] + 1\n\n                break\n\n    def collect(self) -> Optional[Histogram]:\n        \"\"\"\n        Atomically return a point for the current value of the metric.\n        \"\"\"\n        now = _time_ns()\n\n        with self._lock:\n            value = self._value\n            start_time_unix_nano = self._start_time_unix_nano\n\n            self._value = OrderedDict(\n                [(key, 0) for key in (*self._boundaries, inf)]\n            )\n            self._start_time_unix_nano = now + 1\n\n        return Histogram(\n            start_time_unix_nano=start_time_unix_nano,\n            time_unix_nano=now,\n            bucket_counts=tuple(value.values()),\n            explicit_bounds=self._boundaries,\n            aggregation_temporality=AggregationTemporality.DELTA,\n        )\n", "path": "opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py"}], "after_files": [{"content": "# Copyright The OpenTelemetry Authors\n#\n# Licensed under the Apache License, Version 2.0 (the \"License\");\n# you may not use this file except in compliance with the License.\n# You may obtain a copy of the License at\n#\n#     http://www.apache.org/licenses/LICENSE-2.0\n#\n# Unless required by applicable law or agreed to in writing, software\n# distributed under the License is distributed on an \"AS IS\" BASIS,\n# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n# See the License for the specific language governing permissions and\n# limitations under the License.\n\nfrom abc import ABC, abstractmethod\nfrom bisect import bisect_left\nfrom logging import getLogger\nfrom math import inf\nfrom threading import Lock\nfrom typing import Generic, Optional, Sequence, TypeVar\n\nfrom opentelemetry.sdk._metrics.measurement import Measurement\nfrom opentelemetry.sdk._metrics.point import (\n    AggregationTemporality,\n    Gauge,\n    Histogram,\n    PointT,\n    Sum,\n)\nfrom opentelemetry.util._time import _time_ns\n\n_PointVarT = TypeVar(\"_PointVarT\", bound=PointT)\n\n_logger = getLogger(__name__)\n\n\nclass _InstrumentMonotonicityAwareAggregation:\n    def __init__(self, instrument_is_monotonic: bool):\n        self._instrument_is_monotonic = instrument_is_monotonic\n        super().__init__()\n\n\nclass Aggregation(ABC, Generic[_PointVarT]):\n    def __init__(self):\n        self._lock = Lock()\n\n    @abstractmethod\n    def aggregate(self, measurement: Measurement) -> None:\n        pass\n\n    @abstractmethod\n    def collect(self) -> Optional[_PointVarT]:\n        pass\n\n\nclass SynchronousSumAggregation(\n    _InstrumentMonotonicityAwareAggregation, Aggregation[Sum]\n):\n    def __init__(self, instrument_is_monotonic: bool):\n        super().__init__(instrument_is_monotonic)\n        self._value = 0\n        self._start_time_unix_nano = _time_ns()\n\n    def aggregate(self, measurement: Measurement) -> None:\n        with self._lock:\n            self._value = self._value + measurement.value\n\n    def collect(self) -> Optional[Sum]:\n        \"\"\"\n        Atomically return a point for the current value of the metric and\n        reset the aggregation value.\n        \"\"\"\n        now = _time_ns()\n\n        with self._lock:\n            value = self._value\n            start_time_unix_nano = self._start_time_unix_nano\n\n            self._value = 0\n            self._start_time_unix_nano = now + 1\n\n        return Sum(\n            aggregation_temporality=AggregationTemporality.DELTA,\n            is_monotonic=self._instrument_is_monotonic,\n            start_time_unix_nano=start_time_unix_nano,\n            time_unix_nano=now,\n            value=value,\n        )\n\n\nclass AsynchronousSumAggregation(\n    _InstrumentMonotonicityAwareAggregation, Aggregation[Sum]\n):\n    def __init__(self, instrument_is_monotonic: bool):\n        super().__init__(instrument_is_monotonic)\n        self._value = None\n        self._start_time_unix_nano = _time_ns()\n\n    def aggregate(self, measurement: Measurement) -> None:\n        with self._lock:\n            self._value = measurement.value\n\n    def collect(self) -> Optional[Sum]:\n        \"\"\"\n        Atomically return a point for the current value of the metric.\n        \"\"\"\n        if self._value is None:\n            return None\n\n        return Sum(\n            start_time_unix_nano=self._start_time_unix_nano,\n            time_unix_nano=_time_ns(),\n            value=self._value,\n            aggregation_temporality=AggregationTemporality.CUMULATIVE,\n            is_monotonic=self._instrument_is_monotonic,\n        )\n\n\nclass LastValueAggregation(Aggregation[Gauge]):\n    def __init__(self):\n        super().__init__()\n        self._value = None\n\n    def aggregate(self, measurement: Measurement):\n        with self._lock:\n            self._value = measurement.value\n\n    def collect(self) -> Optional[Gauge]:\n        \"\"\"\n        Atomically return a point for the current value of the metric.\n        \"\"\"\n        if self._value is None:\n            return None\n\n        return Gauge(\n            time_unix_nano=_time_ns(),\n            value=self._value,\n        )\n\n\nclass ExplicitBucketHistogramAggregation(Aggregation[Histogram]):\n    def __init__(\n        self,\n        boundaries: Sequence[int] = (\n            0,\n            5,\n            10,\n            25,\n            50,\n            75,\n            100,\n            250,\n            500,\n            1000,\n        ),\n        record_min_max: bool = True,\n    ):\n        super().__init__()\n        # pylint: disable=unnecessary-comprehension\n        self._boundaries = [boundary for boundary in (*boundaries, inf)]\n        self.value = [0 for _ in range(len(self._boundaries))]\n        self._min = inf\n        self._max = -inf\n        self._sum = 0\n        self._record_min_max = record_min_max\n        self._start_time_unix_nano = _time_ns()\n\n    def aggregate(self, measurement: Measurement) -> None:\n\n        value = measurement.value\n\n        if self._record_min_max:\n            self._min = min(self._min, value)\n            self._max = max(self._max, value)\n\n        self._sum += value\n\n        self.value[bisect_left(self._boundaries, value)] += 1\n\n    def collect(self) -> Optional[Histogram]:\n        \"\"\"\n        Atomically return a point for the current value of the metric.\n        \"\"\"\n        now = _time_ns()\n\n        with self._lock:\n            value = self.value\n            start_time_unix_nano = self._start_time_unix_nano\n\n            self.value = [0 for _ in range(len(self._boundaries))]\n            self._start_time_unix_nano = now + 1\n\n        return Histogram(\n            start_time_unix_nano=start_time_unix_nano,\n            time_unix_nano=now,\n            bucket_counts=tuple(value),\n            explicit_bounds=self._boundaries,\n            aggregation_temporality=AggregationTemporality.DELTA,\n        )\n", "path": "opentelemetry-sdk/src/opentelemetry/sdk/_metrics/aggregation.py"}]}