[ https://issues.apache.org/jira/browse/BEAM-4858?focusedWorklogId=152566&page=com.atlassian.jira.plugin.system.issuetabpanels:worklog-tabpanel#worklog-152566 ]
ASF GitHub Bot logged work on BEAM-4858: ---------------------------------------- Author: ASF GitHub Bot Created on: 09/Oct/18 07:23 Start Date: 09/Oct/18 07:23 Worklog Time Spent: 10m Work Description: robertwb commented on a change in pull request #6375: [BEAM-4858] Clean up division in batch size estimator. URL: https://github.com/apache/beam/pull/6375#discussion_r223584542 ########## File path: sdks/python/apache_beam/transforms/util.py ########## @@ -269,23 +270,62 @@ def record_time(self, batch_size): self._thin_data() def _thin_data(self): - sorted_data = sorted(self._data) - odd_one_out = [sorted_data[-1]] if len(sorted_data) % 2 == 1 else [] - # Sort the pairs by how different they are. - - def div_keys(kv1_kv2): - (x1, _), (x2, _) = kv1_kv2 - return old_div(x2, x1) # TODO(BEAM-4858) - - pairs = sorted(zip(sorted_data[::2], sorted_data[1::2]), - key=div_keys) - # Keep the top 1/3 most different pairs, average the top 2/3 most similar. - threshold = 2 * len(pairs) // 3 - self._data = ( - list(sum(pairs[threshold:], ())) - + [((x1 + x2) / 2.0, (t1 + t2) / 2.0) - for (x1, t1), (x2, t2) in pairs[:threshold]] - + odd_one_out) + # Make sure we don't change the parity of len(self._data) + # As it's used below to alternate jitter. + self._data.pop(random.randrange(len(self._data) // 4)) + self._data.pop(random.randrange(len(self._data) // 2)) + + @staticmethod + def linear_regression_no_numpy(xs, ys): + # Least squares fit for y = a + bx over all points. + n = float(len(xs)) + xbar = sum(xs) / n + ybar = sum(ys) / n + b = (sum([(x - xbar) * (y - ybar) for x, y in zip(xs, ys)]) + / sum([(x - xbar)**2 for x in xs])) + a = ybar - b * xbar + return a, b + + @staticmethod + def linear_regression_numpy(xs, ys): + # pylint: disable=wrong-import-order, wrong-import-position + import numpy as np + from numpy import sum + xs = np.asarray(xs, dtype=float) + ys = np.asarray(ys, dtype=float) + + # First do a simple least squares fit for y = a + bx over all points. + b, a = np.polyfit(xs, ys, 1) + + n = len(xs) + if n < 10: + return a, b + else: + # Refine this by throwing out outliers, according to Cook's distance. + # https://en.wikipedia.org/wiki/Cook%27s_distance + sum_x = sum(xs) + sum_x2 = sum(xs**2) + errs = a + b * xs - ys + s2 = sum(errs**2) / (n - 2) + if s2 == 0: + # It's an exact fit! + return a, b + h = (sum_x2 - 2 * sum_x * xs + n * xs**2) / (n * sum_x2 - sum_x**2) + cook_ds = 0.5 / s2 * errs**2 * (h / (1 - h)**2) + + # Re-compute the regression, excluding those points with Cook's distance + # greater than 0.5, and weighting by the inverse of x to give a more + # stable y-intercept. + weight = (cook_ds <= 0.5) / xs Review comment: Smaller batches are more accurate predictors of the fixed cost. I'll update the comment. ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org Issue Time Tracking ------------------- Worklog Id: (was: 152566) Time Spent: 5h 10m (was: 5h) > Clean up _BatchSizeEstimator in element-batching transform. > ----------------------------------------------------------- > > Key: BEAM-4858 > URL: https://issues.apache.org/jira/browse/BEAM-4858 > Project: Beam > Issue Type: Bug > Components: sdk-py-core > Reporter: Valentyn Tymofieiev > Assignee: Robert Bradshaw > Priority: Minor > Time Spent: 5h 10m > Remaining Estimate: 0h > > Beam Python 3 conversion [exposed|https://github.com/apache/beam/pull/5729] > non-trivial performance-sensitive logic in element-batching transform. Let's > take a look at > [util.py#L271|https://github.com/apache/beam/blob/e98ff7c96afa2f72b3a98426dc1e9a47224da5c8/sdks/python/apache_beam/transforms/util.py#L271]. > > Due to Python 2 language semantics, the result of {{x2 / x1}} will depend on > the type of the keys - whether they are integers or floats. > The keys of key-value pairs contained in {{self._data}} are added as integers > [here|https://github.com/apache/beam/blob/d2ac08da2dccce8930432fae1ec7c30953880b69/sdks/python/apache_beam/transforms/util.py#L260], > however, when we 'thin' the collected entries > [here|https://github.com/apache/beam/blob/d2ac08da2dccce8930432fae1ec7c30953880b69/sdks/python/apache_beam/transforms/util.py#L279], > the keys will become floats. Surprisingly, using either integer or float > division consistently [in the > comparator|https://github.com/apache/beam/blob/e98ff7c96afa2f72b3a98426dc1e9a47224da5c8/sdks/python/apache_beam/transforms/util.py#L271] > negatively affects the performance of a custom pipeline I was using to > benchmark these changes. The performance impact likely comes from changes in > the logic that depends on how division is evaluated, not from the > performance of division operation itself. > In terms of Python 3 conversion the best course of action that avoids > regression seems to be to preserve the existing Python 2 behavior using > {{old_div}} from {{past.utils.division}}, in the medium term we should clean > up the logic. We may want to add a targeted microbenchmark to evaluate > performance of this code, and maybe cythonize the code, since it seems to be > performance-sensitive. -- This message was sent by Atlassian JIRA (v7.6.3#76005)