|
Packit Service |
ba2b9f |
#!/usr/bin/python3
|
|
Packit Service |
82fcde |
# Copyright (C) 2015-2018 Free Software Foundation, Inc.
|
|
Packit Service |
82fcde |
# This file is part of the GNU C Library.
|
|
Packit Service |
82fcde |
#
|
|
Packit Service |
82fcde |
# The GNU C Library is free software; you can redistribute it and/or
|
|
Packit Service |
82fcde |
# modify it under the terms of the GNU Lesser General Public
|
|
Packit Service |
82fcde |
# License as published by the Free Software Foundation; either
|
|
Packit Service |
82fcde |
# version 2.1 of the License, or (at your option) any later version.
|
|
Packit Service |
82fcde |
#
|
|
Packit Service |
82fcde |
# The GNU C Library is distributed in the hope that it will be useful,
|
|
Packit Service |
82fcde |
# but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
82fcde |
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Packit Service |
82fcde |
# Lesser General Public License for more details.
|
|
Packit Service |
82fcde |
#
|
|
Packit Service |
82fcde |
# You should have received a copy of the GNU Lesser General Public
|
|
Packit Service |
82fcde |
# License along with the GNU C Library; if not, see
|
|
Packit Service |
82fcde |
# <http://www.gnu.org/licenses/>.
|
|
Packit Service |
82fcde |
"""Functions to import benchmark data and process it"""
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
import json
|
|
Packit Service |
82fcde |
try:
|
|
Packit Service |
82fcde |
import jsonschema as validator
|
|
Packit Service |
82fcde |
except ImportError:
|
|
Packit Service |
82fcde |
print('Could not find jsonschema module.')
|
|
Packit Service |
82fcde |
raise
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
def mean(lst):
|
|
Packit Service |
82fcde |
"""Compute and return mean of numbers in a list
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
The numpy average function has horrible performance, so implement our
|
|
Packit Service |
82fcde |
own mean function.
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
Args:
|
|
Packit Service |
82fcde |
lst: The list of numbers to average.
|
|
Packit Service |
82fcde |
Return:
|
|
Packit Service |
82fcde |
The mean of members in the list.
|
|
Packit Service |
82fcde |
"""
|
|
Packit Service |
82fcde |
return sum(lst) / len(lst)
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
def split_list(bench, func, var):
|
|
Packit Service |
82fcde |
""" Split the list into a smaller set of more distinct points
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
Group together points such that the difference between the smallest
|
|
Packit Service |
82fcde |
point and the mean is less than 1/3rd of the mean. This means that
|
|
Packit Service |
82fcde |
the mean is at most 1.5x the smallest member of that group.
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
mean - xmin < mean / 3
|
|
Packit Service |
82fcde |
i.e. 2 * mean / 3 < xmin
|
|
Packit Service |
82fcde |
i.e. mean < 3 * xmin / 2
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
For an evenly distributed group, the largest member will be less than
|
|
Packit Service |
82fcde |
twice the smallest member of the group.
|
|
Packit Service |
82fcde |
Derivation:
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
An evenly distributed series would be xmin, xmin + d, xmin + 2d...
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
mean = (2 * n * xmin + n * (n - 1) * d) / 2 * n
|
|
Packit Service |
82fcde |
and max element is xmin + (n - 1) * d
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
Now, mean < 3 * xmin / 2
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
3 * xmin > 2 * mean
|
|
Packit Service |
82fcde |
3 * xmin > (2 * n * xmin + n * (n - 1) * d) / n
|
|
Packit Service |
82fcde |
3 * n * xmin > 2 * n * xmin + n * (n - 1) * d
|
|
Packit Service |
82fcde |
n * xmin > n * (n - 1) * d
|
|
Packit Service |
82fcde |
xmin > (n - 1) * d
|
|
Packit Service |
82fcde |
2 * xmin > xmin + (n-1) * d
|
|
Packit Service |
82fcde |
2 * xmin > xmax
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
Hence, proved.
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
Similarly, it is trivial to prove that for a similar aggregation by using
|
|
Packit Service |
82fcde |
the maximum element, the maximum element in the group must be at most 4/3
|
|
Packit Service |
82fcde |
times the mean.
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
Args:
|
|
Packit Service |
82fcde |
bench: The benchmark object
|
|
Packit Service |
82fcde |
func: The function name
|
|
Packit Service |
82fcde |
var: The function variant name
|
|
Packit Service |
82fcde |
"""
|
|
Packit Service |
82fcde |
means = []
|
|
Packit Service |
82fcde |
lst = bench['functions'][func][var]['timings']
|
|
Packit Service |
82fcde |
last = len(lst) - 1
|
|
Packit Service |
82fcde |
while lst:
|
|
Packit Service |
82fcde |
for i in range(last + 1):
|
|
Packit Service |
82fcde |
avg = mean(lst[i:])
|
|
Packit Service |
82fcde |
if avg > 0.75 * lst[last]:
|
|
Packit Service |
82fcde |
means.insert(0, avg)
|
|
Packit Service |
82fcde |
lst = lst[:i]
|
|
Packit Service |
82fcde |
last = i - 1
|
|
Packit Service |
82fcde |
break
|
|
Packit Service |
82fcde |
bench['functions'][func][var]['timings'] = means
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
def do_for_all_timings(bench, callback):
|
|
Packit Service |
82fcde |
"""Call a function for all timing objects for each function and its
|
|
Packit Service |
82fcde |
variants.
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
Args:
|
|
Packit Service |
82fcde |
bench: The benchmark object
|
|
Packit Service |
82fcde |
callback: The callback function
|
|
Packit Service |
82fcde |
"""
|
|
Packit Service |
82fcde |
for func in bench['functions'].keys():
|
|
Packit Service |
82fcde |
for k in bench['functions'][func].keys():
|
|
Packit Service |
82fcde |
if 'timings' not in bench['functions'][func][k].keys():
|
|
Packit Service |
82fcde |
continue
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
callback(bench, func, k)
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
def compress_timings(points):
|
|
Packit Service |
82fcde |
"""Club points with close enough values into a single mean value
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
See split_list for details on how the clubbing is done.
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
Args:
|
|
Packit Service |
82fcde |
points: The set of points.
|
|
Packit Service |
82fcde |
"""
|
|
Packit Service |
82fcde |
do_for_all_timings(points, split_list)
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
def parse_bench(filename, schema_filename):
|
|
Packit Service |
82fcde |
"""Parse the input file
|
|
Packit Service |
82fcde |
|
|
Packit Service |
82fcde |
Parse and validate the json file containing the benchmark outputs. Return
|
|
Packit Service |
82fcde |
the resulting object.
|
|
Packit Service |
82fcde |
Args:
|
|
Packit Service |
82fcde |
filename: Name of the benchmark output file.
|
|
Packit Service |
82fcde |
Return:
|
|
Packit Service |
82fcde |
The bench dictionary.
|
|
Packit Service |
82fcde |
"""
|
|
Packit Service |
82fcde |
with open(schema_filename, 'r') as schemafile:
|
|
Packit Service |
82fcde |
schema = json.load(schemafile)
|
|
Packit Service |
82fcde |
with open(filename, 'r') as benchfile:
|
|
Packit Service |
82fcde |
bench = json.load(benchfile)
|
|
Packit Service |
82fcde |
validator.validate(bench, schema)
|
|
Packit Service |
82fcde |
do_for_all_timings(bench, lambda b, f, v:
|
|
Packit Service |
82fcde |
b['functions'][f][v]['timings'].sort())
|
|
Packit Service |
82fcde |
return bench
|