[analyzer][tests] Introduce analyzer benchmarking framework

[vsavchenko]

Summary

This commit includes a couple of changes:

• Benchmark selected projects by analyzing them multiple times
• Compare two benchmarking results and visualizing them on one chart
• Organize project build logging, so we can use the same code in benchmarks

[vsavchenko]

Rebase

[vsavchenko]

Here is an example of how benchmarking chart looks like:

It has 20 runs on each of those projects. It was the same revision of the analyzer, so it is still very sensitive to other stuff happening on the test machine.

[NoQ]

Box-and-whisker diagrams 👍

clang/utils/analyzer/SATestBenchmark.py

19

@Szelethus ???

140–141

Why shorten? It's not that we're saving a lot of typing, and i think it's easier to read when package names are recognizable.

[vsavchenko]

clang/utils/analyzer/SATestBenchmark.py

140–141

I agree with that, but python world has a few very widespread shortenings:

numpy as np
matplotlib.pyplot as plt
seaborn as sns
pandas as pd

All the tutorials, official documentation and so on include these. So they might be even more recognizable as shortenings.

clang/utils/analyzer/SATest.py

def add(parser, args):
     project = ProjectInfo(args.name[0], args.mode, args.source, args.origin,
                           args.commit)
 
     SATestAdd.add_new_project(project)
 
 
 def build(parser, args):
     import SATestBuild
-    from ProjectMap import ProjectMap
 
     SATestBuild.VERBOSE = args.verbose
 
-    project_map = ProjectMap()
-    projects = project_map.projects
-
-    if args.projects:
-        projects_arg = args.projects.split(",")
-        available_projects = [project.name
-                              for project in projects]
-
-        # validate that given projects are present in the project map file
-        for manual_project in projects_arg:
-            if manual_project not in available_projects:
-                parser.error("Project '{project}' is not found in "
-                             "the project map file. Available projects are "
-                             "{all}.".format(project=manual_project,
-                                             all=available_projects))
-
-        projects = [project.with_fields(enabled=project.name in projects_arg)
-                    for project in projects]
-
+    projects = get_projects(parser, args.projects)
     tester = SATestBuild.RegressionTester(args.jobs,
                                           projects,
                                           args.override_compiler,
                                           args.extra_analyzer_config,
                                           args.regenerate,
                                           args.strictness)
     tests_passed = tester.test_all()
 
def update(parser, args):
     import SATestUpdateDiffs
     from ProjectMap import ProjectMap
 
     project_map = ProjectMap()
     for project in project_map.projects:
         SATestUpdateDiffs.update_reference_results(project)
 
 
+def benchmark(parser, args):
+    from SATestBenchmark import Benchmark
+
+    projects = get_projects(parser, args.projects)
+    benchmark = Benchmark(projects, args.iterations, args.output)
+    benchmark.run()
+
+
+def benchmark_compare(parser, args):
+    import SATestBenchmark
+    SATestBenchmark.compare(args.old, args.new, args.output)
+
+
+def get_projects(parser, projects_str):
+    from ProjectMap import ProjectMap
+
+    project_map = ProjectMap()
+    projects = project_map.projects
+
+    if projects_str:
+        projects_arg = projects_str.split(",")
+        available_projects = [project.name
+                              for project in projects]
+
+        # validate that given projects are present in the project map file
+        for manual_project in projects_arg:
+            if manual_project not in available_projects:
+                parser.error("Project '{project}' is not found in "
+                             "the project map file. Available projects are "
+                             "{all}.".format(project=manual_project,
+                                             all=available_projects))
+
+        projects = [project.with_fields(enabled=project.name in projects_arg)
+                    for project in projects]
+
+    return projects
+
+
 def docker(parser, args):
     if len(args.rest) > 0:
         if args.rest[0] != "--":
             parser.error("REST arguments should start with '--'")
         args.rest = args.rest[1:]
 
     if args.build_image:
         docker_build_image()
dock_parser.add_argument("--build-dir", action="store", default="",
                              "build LLVM code.")
     dock_parser.add_argument("--clang-dir", action="store", default="",
                              help="Path to find/install LLVM installation.")
     dock_parser.add_argument("rest", nargs=argparse.REMAINDER, default=[],
                              help="Additionall args that will be forwarded "
                              "to the docker's entrypoint.")
     dock_parser.set_defaults(func=docker)
 
+    # benchmark subcommand
+    bench_parser = subparsers.add_parser(
+        "benchmark",
+        help="Run benchmarks by building a set of projects multiple times.")
+
+    bench_parser.add_argument("-i", "--iterations", action="store",
+                              type=int, default=20,
+                              help="Number of iterations for building each "
+                              "project.")
+    bench_parser.add_argument("-o", "--output", action="store",
+                              default="benchmark.csv",
+                              help="Output csv file for the benchmark results")
+    bench_parser.add_argument("--projects", action="store", default="",
+                              help="Comma-separated list of projects to test")
+    bench_parser.set_defaults(func=benchmark)
+
+    bench_subparsers = bench_parser.add_subparsers()
+    bench_compare_parser = bench_subparsers.add_parser(
+        "compare",
+        help="Compare benchmark runs.")
+    bench_compare_parser.add_argument("--old", action="store", required=True,
+                                      help="Benchmark reference results to "
+                                      "compare agains.")
+    bench_compare_parser.add_argument("--new", action="store", required=True,
+                                      help="New benchmark results to check.")
+    bench_compare_parser.add_argument("-o", "--output",
+                                      action="store", required=True,
+                                      help="Output file for plots.")
+    bench_compare_parser.set_defaults(func=benchmark_compare)
+
     args = parser.parse_args()
     args.func(parser, args)
 
 
 if __name__ == "__main__":
     main()

clang/utils/analyzer/SATestBenchmark.py

+"""
+Static Analyzer qualification infrastructure.
+
+This source file contains all the functionality related to benchmarking
+the analyzer on a set projects.  Right now, this includes measuring
+execution time and peak memory usage.  Benchmark runs analysis on every
+project multiple times to get a better picture about the distribution
+of measured values.
+
+Additionally, this file includes a comparison routine for two benchmarking
+results that plots the result together on one chart.
+"""
+
+import SATestUtils as utils
+from SATestBuild import ProjectTester, stdout, TestInfo
+from ProjectMap import ProjectInfo
+
+import pandas as pd
+from typing import List, Tuple
+
+
+INDEX_COLUMN = "index"
+
+
+def _save(data: pd.DataFrame, file_path: str):
+    data.to_csv(file_path, index_label=INDEX_COLUMN)
+
+
+def _load(file_path: str) -> pd.DataFrame:
+    return pd.read_csv(file_path, index_col=INDEX_COLUMN)
+
+
+class Benchmark:
+    """
+    Becnhmark class encapsulates one functionality: it runs the analysis
+    multiple times for the given set of projects and stores results in the
+    specified file.
+    """
+    def __init__(self, projects: List[ProjectInfo], iterations: int,
+                 output_path: str):
+        self.projects = projects
+        self.iterations = iterations
+        self.out = output_path
+
+    def run(self):
+        results = [self._benchmark_project(project)
+                   for project in self.projects]
+
+        data = pd.concat(results, ignore_index=True)
+        _save(data, self.out)
+
+    def _benchmark_project(self, project: ProjectInfo) -> pd.DataFrame:
+        if not project.enabled:
+            stdout(f" \n\n--- Skipping disabled project {project.name}\n")
+            return
+
+        stdout(f" \n\n--- Benchmarking project {project.name}\n")
+
+        test_info = TestInfo(project)
+        tester = ProjectTester(test_info, silent=True)
+        project_dir = tester.get_project_dir()
+        output_dir = tester.get_output_dir()
+
+        raw_data = []
+
+        for i in range(self.iterations):
+            stdout(f"Iteration #{i + 1}")
+            time, mem = tester.build(project_dir, output_dir)
+            raw_data.append({"time": time, "memory": mem,
+                             "iteration": i, "project": project.name})
+            stdout(f"time: {utils.time_to_str(time)}, "
+                   f"peak memory: {utils.memory_to_str(mem)}")
+
+        return pd.DataFrame(raw_data)
+
+
+def compare(old_path: str, new_path: str, plot_file: str):
+    """
+    Compare two benchmarking results stored as .csv files
+    and produce a plot in the specified file.
+    """
+    old = _load(old_path)
+    new = _load(new_path)
+
+    old_projects = set(old["project"])
+    new_projects = set(new["project"])
+    common_projects = old_projects & new_projects
+
+    # Leave only rows for projects common to both dataframes.
+    old = old[old["project"].isin(common_projects)]
+    new = new[new["project"].isin(common_projects)]
+
+    old, new = _normalize(old, new)
+
+    # Seaborn prefers all the data to be in one dataframe.
+    old["kind"] = "old"
+    new["kind"] = "new"
+    data = pd.concat([old, new], ignore_index=True)
+
+    # TODO: compare data in old and new dataframes using statistical tests
+    #       to check if they belong to the same distribution
+    _plot(data, plot_file)
+
+
+def _normalize(old: pd.DataFrame,
+               new: pd.DataFrame) -> Tuple[pd.DataFrame, pd.DataFrame]:
+    # This creates a dataframe with all numerical data averaged.
+    means = old.groupby("project").mean()
+    return _normalize_impl(old, means), _normalize_impl(new, means)
+
+
+def _normalize_impl(data: pd.DataFrame, means: pd.DataFrame):
+    # Right now 'means' has one row corresponding to one project,
+    # while 'data' has N rows for each project (one for each iteration).
+    #
+    # In order for us to work easier with this data, we duplicate
+    # 'means' data to match the size of the 'data' dataframe.
+    #
+    # All the columns from 'data' will maintain their names, while
+    # new columns coming from 'means' will have "_mean" suffix.
+    joined_data = data.merge(means, on="project", suffixes=("", "_mean"))
+    _normalize_key(joined_data, "time")
+    _normalize_key(joined_data, "memory")
+    return joined_data
+
+
+def _normalize_key(data: pd.DataFrame, key: str):
+    norm_key = _normalized_name(key)
+    mean_key = f"{key}_mean"
+    data[norm_key] = data[key] / data[mean_key]
+
+
+def _normalized_name(name: str) -> str:
+    return f"normalized {name}"
+
+
+def _plot(data: pd.DataFrame, plot_file: str):
+    import matplotlib
+    import seaborn as sns
+    from matplotlib import pyplot as plt
+
+    sns.set_style("whitegrid")
+    # We want to have time and memory charts one above the other.
+    figure, (ax1, ax2) = plt.subplots(2, 1, figsize=(8, 6))
+
+    def _subplot(key: str, ax: matplotlib.axes.Axes):
+        sns.boxplot(x="project", y=_normalized_name(key), hue="kind",
+                    data=data, palette=sns.color_palette("BrBG", 2), ax=ax)
+
+    _subplot("time", ax1)
+    # No need to have xlabels on both top and bottom charts.
+    ax1.set_xlabel("")
+
+    _subplot("memory", ax2)
+    # The legend on the top chart is enough.
+    ax2.get_legend().remove()
+
+    figure.savefig(plot_file)

clang/utils/analyzer/SATestBuild.py

class StreamToLogger:
 
     def flush(self):
         pass
 
     def fileno(self) -> int:
         return 0
 
 
-Logger = logging.getLogger("main")
 LOCAL = threading.local()
-LOCAL.stdout = StreamToLogger(Logger, logging.INFO)
-LOCAL.stderr = StreamToLogger(Logger, logging.ERROR)
+
+
+def init_logger(name: str):
+    # TODO: use debug levels for VERBOSE messages
+    logger = logging.getLogger(name)
+    logger.setLevel(logging.DEBUG)
+    LOCAL.stdout = StreamToLogger(logger, logging.INFO)
+    LOCAL.stderr = StreamToLogger(logger, logging.ERROR)
+
+
+init_logger("main")
 
 
 def stderr(message: str):
     LOCAL.stderr.write(message)
 
 
 def stdout(message: str):
     LOCAL.stdout.write(message)
 
 
 logging.basicConfig(
-    level=logging.DEBUG,
     format='%(asctime)s:%(levelname)s:%(name)s: %(message)s')
 
 
 ###############################################################################
 # Configuration setup.
 ###############################################################################
 
 
def _multi_threaded_test_all(self,
                 sys.exit(1)
         return not results_differ.is_set()
 
 
 class ProjectTester:
     """
     A component aggregating testing for one project.
     """
-    def __init__(self, test_info: TestInfo):
+    def __init__(self, test_info: TestInfo, silent: bool = False):
         self.project = test_info.project
         self.override_compiler = test_info.override_compiler
         self.extra_analyzer_config = test_info.extra_analyzer_config
         self.is_reference_build = test_info.is_reference_build
         self.strictness = test_info.strictness
+        self.silent = silent
 
     def test(self) -> bool:
         """
         Test a given project.
         :return tests_passed: Whether tests have passed according
         to the :param strictness: criteria.
         """
         if not self.project.enabled:
-            stdout(f" \n\n--- Skipping disabled project {self.project.name}\n")
+            self.out(
+                f" \n\n--- Skipping disabled project {self.project.name}\n")
             return True
 
-        stdout(f" \n\n--- Building project {self.project.name}\n")
+        self.out(f" \n\n--- Building project {self.project.name}\n")
 
         start_time = time.time()
 
         project_dir = self.get_project_dir()
-        if VERBOSE >= 1:
-            stdout(f"  Build directory: {project_dir}.\n")
+        self.vout(f"  Build directory: {project_dir}.\n")
 
         # Set the build results directory.
         output_dir = self.get_output_dir()
-        output_dir = os.path.join(project_dir, output_dir)
 
         self.build(project_dir, output_dir)
         check_build(output_dir)
 
         if self.is_reference_build:
             cleanup_reference_results(output_dir)
             passed = True
         else:
             passed = run_cmp_results(project_dir, self.strictness)
 
-        stdout(f"Completed tests for project {self.project.name} "
+        self.out(f"Completed tests for project {self.project.name} "
                  f"(time: {time.time() - start_time:.2f}).\n")
 
         return passed
 
     def get_project_dir(self) -> str:
         return os.path.join(os.path.abspath(os.curdir), self.project.name)
 
     def get_output_dir(self) -> str:
         if self.is_reference_build:
-            return REF_PREFIX + OUTPUT_DIR_NAME
+            dirname = REF_PREFIX + OUTPUT_DIR_NAME
         else:
-            return OUTPUT_DIR_NAME
+            dirname = OUTPUT_DIR_NAME
+
+        return os.path.join(self.get_project_dir(), dirname)
 
-    def build(self, directory: str, output_dir: str):
+    def build(self, directory: str, output_dir: str) -> Tuple[float, int]:
         build_log_path = get_build_log_path(output_dir)
 
-        stdout(f"Log file: {build_log_path}\n")
-        stdout(f"Output directory: {output_dir}\n")
+        self.out(f"Log file: {build_log_path}\n")
+        self.out(f"Output directory: {output_dir}\n")
 
         remove_log_file(output_dir)
 
         # Clean up scan build results.
         if os.path.exists(output_dir):
-            if VERBOSE >= 1:
-                stdout(f"  Removing old results: {output_dir}\n")
+            self.vout(f"  Removing old results: {output_dir}\n")
 
             shutil.rmtree(output_dir)
 
         assert(not os.path.exists(output_dir))
         os.makedirs(os.path.join(output_dir, LOG_DIR_NAME))
 
         # Build and analyze the project.
         with open(build_log_path, "w+") as build_log_file:
             if self.project.mode == 1:
                 self._download_and_patch(directory, build_log_file)
                 run_cleanup_script(directory, build_log_file)
                 build_time, memory = self.scan_build(directory, output_dir,
                                                      build_log_file)
             else:
                 build_time, memory = self.analyze_preprocessed(directory,
                                                                output_dir)
 
             if self.is_reference_build:
                 run_cleanup_script(directory, build_log_file)
                 normalize_reference_results(directory, output_dir,
                                             self.project.mode)
 
-        stdout(f"Build complete (time: {utils.time_to_str(build_time)}, "
+        self.out(f"Build complete (time: {utils.time_to_str(build_time)}, "
                  f"peak memory: {utils.memory_to_str(memory)}). "
                  f"See the log for more details: {build_log_path}\n")
 
+        return build_time, memory
+
     def scan_build(self, directory: str, output_dir: str,
                    build_log_file: IO) -> Tuple[float, int]:
         """
         Build the project with scan-build by reading in the commands and
         prefixing them with the scan-build options.
         """
         build_script_path = os.path.join(directory, BUILD_SCRIPT)
         if not os.path.exists(build_script_path):
def scan_build(self, directory: str, output_dir: str,
                 # to speed up analysis.  xcodebuild will
                 # automatically use the maximum number of cores.
                 if (command.startswith("make ") or command == "make") and \
                         "-j" not in command:
                     command += f" -j{MAX_JOBS}"
 
                 command_to_run = command_prefix + command
 
-                if VERBOSE >= 1:
-                    stdout(f"  Executing: {command_to_run}\n")
+                self.vout(f"  Executing: {command_to_run}\n")
 
                 time, mem = utils.check_and_measure_call(
                     command_to_run, cwd=cwd,
                     stderr=build_log_file,
                     stdout=build_log_file,
                     env=dict(os.environ, **extra_env),
                     shell=True)
 
def analyze_preprocessed(self, directory: str,
             # Build and call the analyzer command.
             plist_basename = os.path.join(plist_path, file_name)
             output_option = f"-o '{plist_basename}.plist' "
             command = f"{prefix}{output_option}'{file_name}'"
 
             log_path = os.path.join(fail_path, file_name + ".stderr.txt")
             with open(log_path, "w+") as log_file:
                 try:
-                    if VERBOSE >= 1:
-                        stdout(f"  Executing: {command}\n")
+                    self.vout(f"  Executing: {command}\n")
 
                     time, mem = utils.check_and_measure_call(
                         command, cwd=directory, stderr=log_file,
                         stdout=log_file, shell=True)
 
                     execution_time += time
                     peak_memory = max(peak_memory, mem)
 
def _download(self, directory: str, build_log_file: IO):
         elif self.project.source == DownloadType.SCRIPT:
             self._run_download_script(directory, build_log_file)
         else:
             raise ValueError(
                 f"Unknown source type '{self.project.source}' is found "
                 f"for the '{self.project.name}' project")
 
     def _download_from_git(self, directory: str, build_log_file: IO):
+        repo = self.project.origin
         cached_source = os.path.join(directory, CACHED_SOURCE_DIR_NAME)
-        check_call(f"git clone --recursive {self.project.origin} {cached_source}",
+
+        check_call(f"git clone --recursive {repo} {cached_source}",
                    cwd=directory, stderr=build_log_file,
                    stdout=build_log_file, shell=True)
         check_call(f"git checkout --quiet {self.project.commit}",
                    cwd=cached_source, stderr=build_log_file,
                    stdout=build_log_file, shell=True)
 
     def _unpack_zip(self, directory: str, build_log_file: IO):
         zip_files = list(glob.glob(directory + "/*.zip"))
class ProjectTester:
 
     @staticmethod
     def _run_download_script(directory: str, build_log_file: IO):
         script_path = os.path.join(directory, DOWNLOAD_SCRIPT)
         utils.run_script(script_path, build_log_file, directory,
                          out=LOCAL.stdout, err=LOCAL.stderr,
                          verbose=VERBOSE)
 
-    @staticmethod
-    def _apply_patch(directory: str, build_log_file: IO):
+    def _apply_patch(self, directory: str, build_log_file: IO):
         patchfile_path = os.path.join(directory, PATCHFILE_NAME)
         patched_source = os.path.join(directory, PATCHED_SOURCE_DIR_NAME)
 
         if not os.path.exists(patchfile_path):
-            stdout("  No local patches.\n")
+            self.out("  No local patches.\n")
             return
 
-        stdout("  Applying patch.\n")
+        self.out("  Applying patch.\n")
         try:
             check_call(f"patch -p1 < '{patchfile_path}'",
                        cwd=patched_source,
                        stderr=build_log_file,
                        stdout=build_log_file,
                        shell=True)
 
         except CalledProcessError:
             stderr(f"Error: Patch failed. "
                    f"See {build_log_file.name} for details.\n")
             sys.exit(1)
 
+    def out(self, what: str):
+        if not self.silent:
+            stdout(what)
+
+    def vout(self, what: str):
+        if VERBOSE >= 1:
+            self.out(what)
+
 
 class TestProjectThread(threading.Thread):
     def __init__(self, tasks_queue: TestQueue,
                  results_differ: threading.Event,
                  failure_flag: threading.Event):
         """
         :param results_differ: Used to signify that results differ from
                the canonical ones.
         :param failure_flag: Used to signify a failure during the run.
         """
         self.tasks_queue = tasks_queue
         self.results_differ = results_differ
         self.failure_flag = failure_flag
         super().__init__()
 
         # Needed to gracefully handle interrupts with Ctrl-C
         self.daemon = True
 
     def run(self):
         while not self.tasks_queue.empty():
             try:
                 test_info = self.tasks_queue.get()
-
-                Logger = logging.getLogger(test_info.project.name)
-                LOCAL.stdout = StreamToLogger(Logger, logging.INFO)
-                LOCAL.stderr = StreamToLogger(Logger, logging.ERROR)
+                init_logger(test_info.project.name)
 
                 tester = ProjectTester(test_info)
                 if not tester.test():
                     self.results_differ.set()
 
                 self.tasks_queue.task_done()
 
             except BaseException:

clang/utils/analyzer/SATestUpdateDiffs.py

 
 
 def update_reference_results(project: ProjectInfo):
     test_info = SATestBuild.TestInfo(project)
     tester = SATestBuild.ProjectTester(test_info)
     project_dir = tester.get_project_dir()
 
     tester.is_reference_build = True
-    ref_results_path = os.path.join(project_dir, tester.get_output_dir())
+    ref_results_path = tester.get_output_dir()
 
     tester.is_reference_build = False
-    created_results_path = os.path.join(project_dir, tester.get_output_dir())
+    created_results_path = tester.get_output_dir()
 
     if not os.path.exists(created_results_path):
         print("New results not found, was SATestBuild.py previously run?",
               file=sys.stderr)
         sys.exit(1)
 
     build_log_path = SATestBuild.get_build_log_path(ref_results_path)
     build_log_dir = os.path.dirname(os.path.abspath(build_log_path))

clang/utils/analyzer/requirements.txt

 graphviz
 humanize
 matplotlib
+pandas
 psutil
+seaborn