<commit_before>//===-- BuildEngine.mm ---------------------------------------------------===//
//
// Copyright (c) 2014 Apple Inc. All rights reserved.
//
//===----------------------------------------------------------------------===//

#import "llbuild/Commands/Commands.h"

#import <XCTest/XCTest.h>

@interface CorePerfTests : XCTestCase

@end

@implementation CorePerfTests

- (void)testBuildEngineBasicPerf {
  // Test the timing of 'buildengine ack 3 14'.
  //
  // This test uses ~300k rules, and is a good stress test for the core engine
  // operation.
  
  [self measureBlock:^{
      llbuild::commands::ExecuteBuildEngineCommand({
          "ack", "3", "14" });
    }];
}

- (void)testBuildEngineDependencyScanningCorePerf {
  // Test the timing of 'buildengine ack 3 11', with a high recompute count.
  //
  // This test uses ~40k rules, but then recomputes the results multiple times,
  // which is a stress test of the dependency scanning performance.
    
  [self measureBlock:^{
      llbuild::commands::ExecuteBuildEngineCommand({
          "ack", "--recompute", "100", "3", "11" });
    }];
}

@end
<commit_msg>[perftests] Add more dependency scanning tests.<commit_after>//===-- BuildEngine.mm ---------------------------------------------------===//
//
// Copyright (c) 2014 Apple Inc. All rights reserved.
//
//===----------------------------------------------------------------------===//

#import "llbuild/Commands/Commands.h"

#import "llbuild/Core/BuildEngine.h"

#import <XCTest/XCTest.h>

#import <functional>

using namespace llbuild;
using namespace llbuild::core;

@interface CorePerfTests : XCTestCase

@end

#pragma mark - Support Classes

namespace {

// Simple task implementation which takes a fixed set of dependencies, evaluates
// them all, and then provides the output.
//
// FIXME: This is copied from the Core BuildEngine unittest, we should figure
// out if it should be shared in a common build engine support library at some
// point.
class SimpleTask : public Task {
public:
  typedef std::function<ValueType(const std::vector<ValueType>&)> ComputeFnType;

private:
  std::vector<KeyType> Inputs;
  std::vector<ValueType> InputValues;
  ComputeFnType Compute;

public:
  SimpleTask(const std::vector<KeyType>& Inputs, ComputeFnType Compute)
    : Task("SimpleTask"), Inputs(Inputs), Compute(Compute)
  {
    InputValues.resize(Inputs.size());
  }

  virtual void start(BuildEngine& Engine) override {
    // Request all of the inputs.
    for (int i = 0, e = Inputs.size(); i != e; ++i) {
      Engine.taskNeedsInput(this, Inputs[i], i);
    }
  }

  virtual void provideValue(BuildEngine&, uintptr_t InputID,
                            ValueType Value) override {
    // Update the input values.
    assert(InputID < InputValues.size());
    InputValues[InputID] = Value;
  }

  virtual void inputsAvailable(core::BuildEngine& Engine) override {
    Engine.taskIsComplete(this, Compute(InputValues));
  }
};

// Helper function for creating a simple action.
typedef std::function<Task*(BuildEngine&)> ActionFn;

static ActionFn simpleAction(const std::vector<KeyType>& Inputs,
                             SimpleTask::ComputeFnType Compute) {
  return [=] (BuildEngine& engine) {
    return engine.registerTask(new SimpleTask(Inputs, Compute)); };
}

}

@implementation CorePerfTests

#pragma mark - "buildengine ack" Performance Tests

- (void)testBuildEngineBasicPerf {
  // Test the timing of 'buildengine ack 3 14'.
  //
  // This test uses ~300k rules, and is a good stress test for the core engine
  // operation.

  [self measureBlock:^{
      llbuild::commands::ExecuteBuildEngineCommand({
          "ack", "3", "14" });
    }];
}

- (void)testBuildEngineDependencyScanningCorePerf {
  // Test the timing of 'buildengine ack 3 11', with a high recompute count.
  //
  // This test uses ~40k rules, but then recomputes the results multiple times,
  // which is a stress test of the dependency scanning performance.

  [self measureBlock:^{
      llbuild::commands::ExecuteBuildEngineCommand({
          "ack", "--recompute", "100", "3", "11" });
    }];
}

#pragma mark - Synthetic Graph Dependency Scanning Tests

- (void)testBuildEngineDependencyScanningOnLinearChain {
  // Test the scanning performance on a deep linear build graph of M nodes::
  //
  //   i1 -> i2 -> ... -> iM
  //
  // FIXME: We would like to drive this number higher, but can't do so until the
  // process becomes non-recursive, this is close to the max we can get to
  // before crashing.
  int M = 50000;

  // Set up the build rules.
  __block core::BuildEngine Engine;
  int LastInputValue = 0;
  for (int i = 1; i <= M; ++i) {
    char Name[32];
    sprintf(Name, "i%d", i);
    if (i != M) {
      char InputName[32];
      sprintf(InputName, "i%d", i+1);
      Engine.addRule({
          Name, simpleAction({ InputName },
                             [] (const std::vector<ValueType>& Inputs) {
                               return Inputs[0]; }) });
    } else {
      Engine.addRule({
          Name,
          simpleAction({},
                       [&] (const std::vector<ValueType>& Inputs) {
                         return LastInputValue; }),
          [&](const Rule& rule, const ValueType Value) {
            // FIXME: Once we have custom ValueType objects, we would like to
            // have timestamps on the value and just compare to a timestamp
            // (similar to what we would do for a file).
            return LastInputValue == Value;
          } });
    }
  }

  // Build the first result.
  LastInputValue = 42;
  auto Result = Engine.build("i1");
  assert(Result == LastInputValue);

  // Run a single initial null build to try and warm the timings below.
  Engine.build("i1");

  // Measure the null build time.
  [self measureBlock:^{
      auto Result = Engine.build("i1");
      assert(Result == LastInputValue);
    }];
}

static int64_t i64pow(int64_t Value, int64_t Exponent) {
  int64_t Result = 1;
  for (int64_t i = 0; i != Exponent; ++i)
    Result *= Value;
  return Result;
}

- (void)testBuildEngineDependencyScanningOnNaryTree {
  // Test the scanning performance on an M-height N-ary tree with no sharing::
  //
  //   i1,1 ---> i2,1 ... ---> iM,1
  //         \-> i2,2       ...
  //         \-> i2,N          iM,{N**(M-1)}

  int M = 13, N = 3; // Use a graph of 797,161 nodes.
  int NumTotalNodes = (i64pow(N, M) - 1) / (N - 1);
  NSLog(@"running test with %d-ary tree of depth %d (%d nodes)\n",
         N, M, NumTotalNodes);

  // Set up the build rules.
  __block core::BuildEngine Engine;
  int LastInputValue = 0;
  for (int i = 1; i <= M; ++i) {
    // Compute the total number of groups at this depth.
    int NumNodes = i64pow(N, i - 1);
    for (int j = 1; j <= NumNodes; ++j) {
      char Name[32];
      sprintf(Name, "i%d,%d", i, j);
      if (i != M) {
        std::vector<KeyType> Inputs;
        for (int k = 1; k <= N; ++k) {
          char InputName[32];
          sprintf(InputName, "i%d,%d", i+1, 1 + (j - 1)*N + (k - 1));
          Inputs.push_back(InputName);
        }
        Engine.addRule({
            Name, simpleAction(Inputs, [] (const std::vector<ValueType>& Inputs) {
                return Inputs[0]; }) });
      } else {
        Engine.addRule({
            Name,
            simpleAction({},
                         [&] (const std::vector<ValueType>& Inputs) {
                           return LastInputValue; }),
            [&](const Rule& rule, const ValueType Value) {
              // FIXME: Once we have custom ValueType objects, we would like to
              // have timestamps on the value and just compare to a timestamp
              // (similar to what we would do for a file).
              return LastInputValue == Value;
            } });
      }
    }
  }

  // Build the first result.
  LastInputValue = 42;
  auto Result = Engine.build("i1,1");
  assert(Result == LastInputValue);

  // Run a single initial null build to try and warm the timings below.
  Engine.build("i1,1");

  // Measure the null build time.
  [self measureBlock:^{
      auto Result = Engine.build("i1,1");
      assert(Result == LastInputValue);
    }];
}

- (void)testBuildEngineDependencyScanningOn2DMatrix {
  // Test the scanning performance on a 2D {M+1}x{N+1} matrix where each node
  // depends on nodes which are adjacent above or to the right::
  //
  //   i1,N --> i2,N --> ... --> iM,N
  //    ^        ^       ...      ^
  //    |        |                |
  //   i1,2 --> i2,2 --> ... --> iM,2
  //    ^        ^       ...      ^
  //    |        |                |
  //   i1,1 --> i2,1 --> ... --> iM,1
  //
  // This is an easy to construct synthetic graph which is scalable and has
  // sharing.
  int M = 1000, N = 1000; // Use a graph of 1 million nodes.

  // Set up the build rules.
  __block core::BuildEngine Engine;
  int LastInputValue = 0;
  for (int i = 1; i <= M; ++i) {
    for (int j = 1; j <= N; ++j) {
      char Name[32];
      sprintf(Name, "i%d,%d", i, j);
      if (i != M && j != N) {
        // Nodes not on an edge.
        char InputAName[32];
        sprintf(InputAName, "i%d,%d", i+1, j);
        char InputBName[32];
        sprintf(InputBName, "i%d,%d", i, j+1);
        Engine.addRule({
            Name, simpleAction({ InputAName, InputBName },
                               [] (const std::vector<ValueType>& Inputs) {
                                 return Inputs[0]; }) });
      } else if (i != M) {
        // Top edge.
        assert(j == N);
        char InputName[32];
        sprintf(InputName, "i%d,%d", i+1, j);
        Engine.addRule({
            Name, simpleAction({ InputName },
                               [] (const std::vector<ValueType>& Inputs) {
                                 return Inputs[0]; }) });
      } else if (j != N) {
        // Right edge.
        assert(i == M);
        char InputName[32];
        sprintf(InputName, "i%d,%d", i, j+1);
        Engine.addRule({
            Name, simpleAction({ InputName },
                               [] (const std::vector<ValueType>& Inputs) {
                                 return Inputs[0]; }) });
      } else {
        // Top-right corner node.
        assert(i == M && j == N);
        Engine.addRule({
            Name,
            simpleAction({},
                         [&] (const std::vector<ValueType>& Inputs) {
                           return LastInputValue; }),
            [&](const Rule& rule, const ValueType Value) {
              // FIXME: Once we have custom ValueType objects, we would like to
              // have timestamps on the value and just compare to a timestamp
              // (similar to what we would do for a file).
              return LastInputValue == Value;
            } });
      }
    }
  }

  // Build the first result.
  LastInputValue = 42;
  auto Result = Engine.build("i1,1");
  assert(Result == LastInputValue);

  // Run a single initial null build to try and warm the timings below.
  Engine.build("i1,1");

  // Measure the null build time.
  [self measureBlock:^{
      auto Result = Engine.build("i1,1");
      assert(Result == LastInputValue);
    }];
}

@end

{'fraction_non_alphanumeric': 0.15631442143945504, 'fraction_numerical': 0.01631262884287891, 'mean_word_length': 1.9858175006689858, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 38, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7138874', 'n_tokens_mistral': 3468, 'n_tokens_neox': 3327, 'n_words': 1035}