// Copyright (C) 2019 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include <random>

#include <benchmark/benchmark.h>

#include "src/trace_processor/tables/macros.h"

namespace perfetto {
namespace trace_processor {
namespace {

#define PERFETTO_TP_ROOT_TEST_TABLE(NAME, PARENT, C) \
  NAME(RootTestTable, "root_table")                  \
  PERFETTO_TP_ROOT_TABLE(PARENT, C)                  \
  C(uint32_t, root_sorted, Column::Flag::kSorted)    \
  C(uint32_t, root_non_null)                         \
  C(uint32_t, root_non_null_2)                       \
  C(std::optional<uint32_t>, root_nullable)

PERFETTO_TP_TABLE(PERFETTO_TP_ROOT_TEST_TABLE);

#define PERFETTO_TP_CHILD_TABLE(NAME, PARENT, C)   \
  NAME(ChildTestTable, "child_table")              \
  PARENT(PERFETTO_TP_ROOT_TEST_TABLE, C)           \
  C(uint32_t, child_sorted, Column::Flag::kSorted) \
  C(uint32_t, child_non_null)                      \
  C(std::optional<uint32_t>, child_nullable)

PERFETTO_TP_TABLE(PERFETTO_TP_CHILD_TABLE);

RootTestTable::~RootTestTable() = default;
ChildTestTable::~ChildTestTable() = default;

}  // namespace
}  // namespace trace_processor
}  // namespace perfetto

namespace {

bool IsBenchmarkFunctionalOnly() {
  return getenv("BENCHMARK_FUNCTIONAL_TEST_ONLY") != nullptr;
}

void TableFilterArgs(benchmark::internal::Benchmark* b) {
  if (IsBenchmarkFunctionalOnly()) {
    b->Arg(1024);
  } else {
    b->RangeMultiplier(8);
    b->Range(1024, 2 * 1024 * 1024);
  }
}

void TableSortArgs(benchmark::internal::Benchmark* b) {
  if (IsBenchmarkFunctionalOnly()) {
    b->Arg(64);
  } else {
    b->RangeMultiplier(8);
    b->Range(1024, 256 * 1024);
  }
}

}  // namespace

using perfetto::trace_processor::ChildTestTable;
using perfetto::trace_processor::RootTestTable;
using perfetto::trace_processor::RowMap;
using perfetto::trace_processor::SqlValue;
using perfetto::trace_processor::StringPool;
using perfetto::trace_processor::Table;

static void BM_TableInsert(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);

  for (auto _ : state) {
    benchmark::DoNotOptimize(root.Insert({}));
  }
}
BENCHMARK(BM_TableInsert);

static void BM_TableIteratorChild(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);
  ChildTestTable child(&pool, &root);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  for (uint32_t i = 0; i < size; ++i) {
    child.Insert({});
    root.Insert({});
  }

  auto it = static_cast<Table&>(child).IterateRows();
  for (auto _ : state) {
    for (uint32_t i = 0; i < child.GetColumnCount(); ++i) {
      benchmark::DoNotOptimize(it.Get(i));
    }
    it.Next();
    if (!it)
      it = static_cast<Table&>(child).IterateRows();
  }
}
BENCHMARK(BM_TableIteratorChild)->Apply(TableFilterArgs);

static void BM_TableFilterAndSortRoot(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  uint32_t partitions = 8;

  std::minstd_rand0 rnd_engine(45);
  for (uint32_t i = 0; i < size; ++i) {
    RootTestTable::Row row;
    row.root_non_null = rnd_engine() % partitions;
    row.root_non_null_2 = static_cast<uint32_t>(rnd_engine());
    root.Insert(row);
  }

  for (auto _ : state) {
    Table filtered = root.Filter({root.root_non_null().eq(5)},
                                 RowMap::OptimizeFor::kLookupSpeed);
    benchmark::DoNotOptimize(
        filtered.Sort({root.root_non_null_2().ascending()}));
  }
}
BENCHMARK(BM_TableFilterAndSortRoot)->Apply(TableFilterArgs);

static void BM_TableFilterRootId(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  for (uint32_t i = 0; i < size; ++i)
    root.Insert({});

  for (auto _ : state) {
    benchmark::DoNotOptimize(root.Filter({root.id().eq(30)}));
  }
}
BENCHMARK(BM_TableFilterRootId)->Apply(TableFilterArgs);

static void BM_TableFilterRootIdAndOther(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);

  uint32_t size = static_cast<uint32_t>(state.range(0));

  for (uint32_t i = 0; i < size; ++i) {
    RootTestTable::Row root_row;
    root_row.root_non_null = i * 4;
    root.Insert(root_row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(root.Filter(
        {root.id().eq(root.row_count() - 1), root.root_non_null().gt(100)}));
  }
}
BENCHMARK(BM_TableFilterRootIdAndOther)->Apply(TableFilterArgs);

static void BM_TableFilterChildId(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);
  ChildTestTable child(&pool, &root);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  for (uint32_t i = 0; i < size; ++i) {
    root.Insert({});
    child.Insert({});
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(child.Filter({child.id().eq(30)}));
  }
}
BENCHMARK(BM_TableFilterChildId)->Apply(TableFilterArgs);

static void BM_TableFilterChildIdAndSortedInRoot(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);
  ChildTestTable child(&pool, &root);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  for (uint32_t i = 0; i < size; ++i) {
    RootTestTable::Row root_row;
    root_row.root_sorted = i * 2;
    root.Insert(root_row);

    ChildTestTable::Row child_row;
    child_row.root_sorted = i * 2 + 1;
    child.Insert(child_row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(
        child.Filter({child.id().eq(30), child.root_sorted().gt(1024)}));
  }
}
BENCHMARK(BM_TableFilterChildIdAndSortedInRoot)->Apply(TableFilterArgs);

static void BM_TableFilterRootNonNullEqMatchMany(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  uint32_t partitions = size / 1024;

  std::minstd_rand0 rnd_engine;
  for (uint32_t i = 0; i < size; ++i) {
    RootTestTable::Row row(static_cast<uint32_t>(rnd_engine() % partitions));
    root.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(root.Filter({root.root_non_null().eq(0)}));
  }
}
BENCHMARK(BM_TableFilterRootNonNullEqMatchMany)->Apply(TableFilterArgs);

static void BM_TableFilterRootMultipleNonNull(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  uint32_t partitions = size / 512;

  std::minstd_rand0 rnd_engine;
  for (uint32_t i = 0; i < size; ++i) {
    RootTestTable::Row row;
    row.root_non_null = rnd_engine() % partitions;
    row.root_non_null_2 = rnd_engine() % partitions;
    root.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(root.Filter(
        {root.root_non_null().lt(4), root.root_non_null_2().lt(10)}));
  }
}
BENCHMARK(BM_TableFilterRootMultipleNonNull)->Apply(TableFilterArgs);

static void BM_TableFilterRootNullableEqMatchMany(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  uint32_t partitions = size / 512;

  std::minstd_rand0 rnd_engine;
  for (uint32_t i = 0; i < size; ++i) {
    uint32_t value = rnd_engine() % partitions;

    RootTestTable::Row row;
    row.root_nullable =
        value % 2 == 0 ? std::nullopt : std::make_optional(value);
    root.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(root.Filter({root.root_nullable().eq(1)}));
  }
}
BENCHMARK(BM_TableFilterRootNullableEqMatchMany)->Apply(TableFilterArgs);

static void BM_TableFilterChildNonNullEqMatchMany(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);
  ChildTestTable child(&pool, &root);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  uint32_t partitions = size / 1024;

  std::minstd_rand0 rnd_engine;
  for (uint32_t i = 0; i < size; ++i) {
    ChildTestTable::Row row;
    row.child_non_null = static_cast<uint32_t>(rnd_engine() % partitions);
    root.Insert({});
    child.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(child.Filter({child.child_non_null().eq(0)}));
  }
}
BENCHMARK(BM_TableFilterChildNonNullEqMatchMany)->Apply(TableFilterArgs);

static void BM_TableFilterChildNullableEqMatchMany(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);
  ChildTestTable child(&pool, &root);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  uint32_t partitions = size / 512;

  std::minstd_rand0 rnd_engine;
  for (uint32_t i = 0; i < size; ++i) {
    uint32_t value = rnd_engine() % partitions;

    ChildTestTable::Row row;
    row.child_nullable =
        value % 2 == 0 ? std::nullopt : std::make_optional(value);
    root.Insert({});
    child.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(child.Filter({child.child_nullable().eq(1)}));
  }
}
BENCHMARK(BM_TableFilterChildNullableEqMatchMany)->Apply(TableFilterArgs);

static void BM_TableFilterChildNonNullEqMatchManyInParent(
    benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);
  ChildTestTable child(&pool, &root);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  uint32_t partitions = size / 1024;

  std::minstd_rand0 rnd_engine;
  for (uint32_t i = 0; i < size; ++i) {
    ChildTestTable::Row row;
    row.root_non_null = static_cast<uint32_t>(rnd_engine() % partitions);
    root.Insert({});
    child.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(child.Filter({child.root_non_null().eq(0)}));
  }
}
BENCHMARK(BM_TableFilterChildNonNullEqMatchManyInParent)
    ->Apply(TableFilterArgs);

static void BM_TableFilterChildNullableEqMatchManyInParent(
    benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);
  ChildTestTable child(&pool, &root);

  uint32_t size = static_cast<uint32_t>(state.range(0));
  uint32_t partitions = size / 512;

  std::minstd_rand0 rnd_engine;
  for (uint32_t i = 0; i < size; ++i) {
    ChildTestTable::Row row;
    row.root_nullable = static_cast<uint32_t>(rnd_engine() % partitions);
    root.Insert({});
    child.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(child.Filter({child.root_nullable().eq(1)}));
  }
}
BENCHMARK(BM_TableFilterChildNullableEqMatchManyInParent)
    ->Apply(TableFilterArgs);

static void BM_TableFilterParentSortedEq(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);

  uint32_t size = static_cast<uint32_t>(state.range(0));

  for (uint32_t i = 0; i < size; ++i) {
    RootTestTable::Row row;
    row.root_sorted = i * 2;
    root.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(root.Filter({root.root_sorted().eq(22)}));
  }
}
BENCHMARK(BM_TableFilterParentSortedEq)->Apply(TableFilterArgs);

static void BM_TableFilterParentSortedAndOther(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);

  uint32_t size = static_cast<uint32_t>(state.range(0));

  for (uint32_t i = 0; i < size; ++i) {
    // Group the rows into rows of 10. This emulates the behaviour of e.g.
    // args.
    RootTestTable::Row row;
    row.root_sorted = (i / 10) * 10;
    row.root_non_null = i;
    root.Insert(row);
  }

  // We choose to search for the last group as if there is O(n^2), it will
  // be more easily visible.
  uint32_t last_group = ((size - 1) / 10) * 10;
  for (auto _ : state) {
    benchmark::DoNotOptimize(root.Filter({root.root_sorted().eq(last_group),
                                          root.root_non_null().eq(size - 1)}));
  }
}
BENCHMARK(BM_TableFilterParentSortedAndOther)->Apply(TableFilterArgs);

static void BM_TableFilterChildSortedEq(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);
  ChildTestTable child(&pool, &root);

  uint32_t size = static_cast<uint32_t>(state.range(0));

  for (uint32_t i = 0; i < size; ++i) {
    ChildTestTable::Row row;
    row.child_sorted = i * 2;
    root.Insert({});
    child.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(child.Filter({child.child_sorted().eq(22)}));
  }
}
BENCHMARK(BM_TableFilterChildSortedEq)->Apply(TableFilterArgs);

static void BM_TableFilterChildSortedEqInParent(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);
  ChildTestTable child(&pool, &root);

  uint32_t size = static_cast<uint32_t>(state.range(0));

  for (uint32_t i = 0; i < size; ++i) {
    RootTestTable::Row root_row;
    root_row.root_sorted = i * 4;
    root.Insert(root_row);

    ChildTestTable::Row row;
    row.root_sorted = i * 4 + 2;
    child.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(child.Filter({child.root_sorted().eq(22)}));
  }
}
BENCHMARK(BM_TableFilterChildSortedEqInParent)->Apply(TableFilterArgs);

static void BM_TableSortRootNonNull(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);

  uint32_t size = static_cast<uint32_t>(state.range(0));

  std::minstd_rand0 rnd_engine;
  for (uint32_t i = 0; i < size; ++i) {
    const uint32_t root_value = static_cast<uint32_t>(rnd_engine());

    RootTestTable::Row row;
    row.root_non_null = root_value;
    root.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(root.Sort({root.root_non_null().ascending()}));
  }
}
BENCHMARK(BM_TableSortRootNonNull)->Apply(TableSortArgs);

static void BM_TableSortRootNullable(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);

  uint32_t size = static_cast<uint32_t>(state.range(0));

  std::minstd_rand0 rnd_engine;
  for (uint32_t i = 0; i < size; ++i) {
    const uint32_t root_value = static_cast<uint32_t>(rnd_engine());

    RootTestTable::Row row;
    row.root_nullable =
        root_value % 2 == 0 ? std::nullopt : std::make_optional(root_value);
    root.Insert(row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(root.Sort({root.root_nullable().ascending()}));
  }
}
BENCHMARK(BM_TableSortRootNullable)->Apply(TableSortArgs);

static void BM_TableSortChildNonNullInParent(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);
  ChildTestTable child(&pool, &root);

  uint32_t size = static_cast<uint32_t>(state.range(0));

  std::minstd_rand0 rnd_engine;
  for (uint32_t i = 0; i < size; ++i) {
    const uint32_t root_value = static_cast<uint32_t>(rnd_engine());

    RootTestTable::Row root_row;
    root_row.root_non_null = root_value;
    root.Insert(root_row);

    const uint32_t child_value = static_cast<uint32_t>(rnd_engine());

    ChildTestTable::Row child_row;
    child_row.root_non_null = child_value;
    child.Insert(child_row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(child.Sort({child.root_non_null().ascending()}));
  }
}
BENCHMARK(BM_TableSortChildNonNullInParent)->Apply(TableSortArgs);

static void BM_TableSortChildNullableInParent(benchmark::State& state) {
  StringPool pool;
  RootTestTable root(&pool, nullptr);
  ChildTestTable child(&pool, &root);

  uint32_t size = static_cast<uint32_t>(state.range(0));

  std::minstd_rand0 rnd_engine;
  for (uint32_t i = 0; i < size; ++i) {
    const uint32_t root_value = static_cast<uint32_t>(rnd_engine());

    RootTestTable::Row root_row;
    root_row.root_nullable =
        root_value % 2 == 0 ? std::nullopt : std::make_optional(root_value);
    root.Insert(root_row);

    const uint32_t child_value = static_cast<uint32_t>(rnd_engine());

    ChildTestTable::Row child_row;
    child_row.root_nullable =
        child_value % 2 == 0 ? std::nullopt : std::make_optional(child_value);
    child.Insert(child_row);
  }

  for (auto _ : state) {
    benchmark::DoNotOptimize(child.Sort({child.root_nullable().ascending()}));
  }
}
BENCHMARK(BM_TableSortChildNullableInParent)->Apply(TableSortArgs);