// Copyright 2017 The Abseil Authors.
//
// 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 "absl/container/inlined_vector.h"

#include <string>
#include <vector>

#include "benchmark/benchmark.h"
#include "absl/base/internal/raw_logging.h"
#include "absl/strings/str_cat.h"

namespace {

using IntVec = absl::InlinedVector<int, 8>;

void BM_InlinedVectorFill(benchmark::State& state) {
  const int len = state.range(0);
  for (auto _ : state) {
    IntVec v;
    for (int i = 0; i < len; i++) {
      v.push_back(i);
    }
  }
  state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
}
BENCHMARK(BM_InlinedVectorFill)->Range(0, 1024);

void BM_InlinedVectorFillRange(benchmark::State& state) {
  const int len = state.range(0);
  std::unique_ptr<int[]> ia(new int[len]);
  for (int i = 0; i < len; i++) {
    ia[i] = i;
  }
  for (auto _ : state) {
    IntVec v(ia.get(), ia.get() + len);
    benchmark::DoNotOptimize(v);
  }
  state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
}
BENCHMARK(BM_InlinedVectorFillRange)->Range(0, 1024);

void BM_StdVectorFill(benchmark::State& state) {
  const int len = state.range(0);
  for (auto _ : state) {
    std::vector<int> v;
    for (int i = 0; i < len; i++) {
      v.push_back(i);
    }
  }
  state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
}
BENCHMARK(BM_StdVectorFill)->Range(0, 1024);

// The purpose of the next two benchmarks is to verify that
// absl::InlinedVector is efficient when moving is more efficent than
// copying. To do so, we use strings that are larger than the short
// std::string optimization.
bool StringRepresentedInline(std::string s) {
  const char* chars = s.data();
  std::string s1 = std::move(s);
  return s1.data() != chars;
}

int GetNonShortStringOptimizationSize() {
  for (int i = 24; i <= 192; i *= 2) {
    if (!StringRepresentedInline(std::string(i, 'A'))) {
      return i;
    }
  }
  ABSL_RAW_LOG(
      FATAL,
      "Failed to find a std::string larger than the short std::string optimization");
  return -1;
}

void BM_InlinedVectorFillString(benchmark::State& state) {
  const int len = state.range(0);
  const int no_sso = GetNonShortStringOptimizationSize();
  std::string strings[4] = {std::string(no_sso, 'A'), std::string(no_sso, 'B'),
                       std::string(no_sso, 'C'), std::string(no_sso, 'D')};

  for (auto _ : state) {
    absl::InlinedVector<std::string, 8> v;
    for (int i = 0; i < len; i++) {
      v.push_back(strings[i & 3]);
    }
  }
  state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
}
BENCHMARK(BM_InlinedVectorFillString)->Range(0, 1024);

void BM_StdVectorFillString(benchmark::State& state) {
  const int len = state.range(0);
  const int no_sso = GetNonShortStringOptimizationSize();
  std::string strings[4] = {std::string(no_sso, 'A'), std::string(no_sso, 'B'),
                       std::string(no_sso, 'C'), std::string(no_sso, 'D')};

  for (auto _ : state) {
    std::vector<std::string> v;
    for (int i = 0; i < len; i++) {
      v.push_back(strings[i & 3]);
    }
  }
  state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
}
BENCHMARK(BM_StdVectorFillString)->Range(0, 1024);

struct Buffer {  // some arbitrary structure for benchmarking.
  char* base;
  int length;
  int capacity;
  void* user_data;
};

void BM_InlinedVectorTenAssignments(benchmark::State& state) {
  const int len = state.range(0);
  using BufferVec = absl::InlinedVector<Buffer, 2>;

  BufferVec src;
  src.resize(len);

  BufferVec dst;
  for (auto _ : state) {
    for (int i = 0; i < 10; ++i) {
      dst = src;
    }
  }
}
BENCHMARK(BM_InlinedVectorTenAssignments)
    ->Arg(0)->Arg(1)->Arg(2)->Arg(3)->Arg(4)->Arg(20);

void BM_CreateFromContainer(benchmark::State& state) {
  for (auto _ : state) {
    absl::InlinedVector<int, 4> x(absl::InlinedVector<int, 4>{1, 2, 3});
    benchmark::DoNotOptimize(x);
  }
}
BENCHMARK(BM_CreateFromContainer);

struct LargeCopyableOnly {
  LargeCopyableOnly() : d(1024, 17) {}
  LargeCopyableOnly(const LargeCopyableOnly& o) = default;
  LargeCopyableOnly& operator=(const LargeCopyableOnly& o) = default;

  std::vector<int> d;
};

struct LargeCopyableSwappable {
  LargeCopyableSwappable() : d(1024, 17) {}
  LargeCopyableSwappable(const LargeCopyableSwappable& o) = default;
  LargeCopyableSwappable(LargeCopyableSwappable&& o) = delete;

  LargeCopyableSwappable& operator=(LargeCopyableSwappable o) {
    using std::swap;
    swap(*this, o);
    return *this;
  }
  LargeCopyableSwappable& operator=(LargeCopyableSwappable&& o) = delete;

  friend void swap(LargeCopyableSwappable& a, LargeCopyableSwappable& b) {
    using std::swap;
    swap(a.d, b.d);
  }

  std::vector<int> d;
};

struct LargeCopyableMovable {
  LargeCopyableMovable() : d(1024, 17) {}
  // Use implicitly defined copy and move.

  std::vector<int> d;
};

struct LargeCopyableMovableSwappable {
  LargeCopyableMovableSwappable() : d(1024, 17) {}
  LargeCopyableMovableSwappable(const LargeCopyableMovableSwappable& o) =
      default;
  LargeCopyableMovableSwappable(LargeCopyableMovableSwappable&& o) = default;

  LargeCopyableMovableSwappable& operator=(LargeCopyableMovableSwappable o) {
    using std::swap;
    swap(*this, o);
    return *this;
  }
  LargeCopyableMovableSwappable& operator=(LargeCopyableMovableSwappable&& o) =
      default;

  friend void swap(LargeCopyableMovableSwappable& a,
                   LargeCopyableMovableSwappable& b) {
    using std::swap;
    swap(a.d, b.d);
  }

  std::vector<int> d;
};

template <typename ElementType>
void BM_SwapElements(benchmark::State& state) {
  const int len = state.range(0);
  using Vec = absl::InlinedVector<ElementType, 32>;
  Vec a(len);
  Vec b;
  for (auto _ : state) {
    using std::swap;
    swap(a, b);
  }
}
BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableOnly)->Range(0, 1024);
BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableSwappable)->Range(0, 1024);
BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableMovable)->Range(0, 1024);
BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableMovableSwappable)
    ->Range(0, 1024);

// The following benchmark is meant to track the efficiency of the vector size
// as a function of stored type via the benchmark label. It is not meant to
// output useful sizeof operator performance. The loop is a dummy operation
// to fulfill the requirement of running the benchmark.
template <typename VecType>
void BM_Sizeof(benchmark::State& state) {
  int size = 0;
  for (auto _ : state) {
    VecType vec;
    size = sizeof(vec);
  }
  state.SetLabel(absl::StrCat("sz=", size));
}
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 1>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 4>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 7>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 8>);

BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 1>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 4>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 7>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 8>);

BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 1>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 4>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 7>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 8>);

BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 1>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 4>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 7>);
BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 8>);

void BM_InlinedVectorIndexInlined(benchmark::State& state) {
  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
  for (auto _ : state) {
    for (int i = 0; i < 1000; ++i) {
      benchmark::DoNotOptimize(v);
      benchmark::DoNotOptimize(v[4]);
    }
  }
  state.SetItemsProcessed(1000 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorIndexInlined);

void BM_InlinedVectorIndexExternal(benchmark::State& state) {
  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  for (auto _ : state) {
    for (int i = 0; i < 1000; ++i) {
      benchmark::DoNotOptimize(v);
      benchmark::DoNotOptimize(v[4]);
    }
  }
  state.SetItemsProcessed(1000 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorIndexExternal);

void BM_StdVectorIndex(benchmark::State& state) {
  std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  for (auto _ : state) {
    for (int i = 0; i < 1000; ++i) {
      benchmark::DoNotOptimize(v);
      benchmark::DoNotOptimize(v[4]);
    }
  }
  state.SetItemsProcessed(1000 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_StdVectorIndex);

#define UNROLL_2(x)            \
  benchmark::DoNotOptimize(x); \
  benchmark::DoNotOptimize(x);

#define UNROLL_4(x) UNROLL_2(x) UNROLL_2(x)
#define UNROLL_8(x) UNROLL_4(x) UNROLL_4(x)
#define UNROLL_16(x) UNROLL_8(x) UNROLL_8(x);

void BM_InlinedVectorDataInlined(benchmark::State& state) {
  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
  for (auto _ : state) {
    UNROLL_16(v.data());
  }
  state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorDataInlined);

void BM_InlinedVectorDataExternal(benchmark::State& state) {
  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  for (auto _ : state) {
    UNROLL_16(v.data());
  }
  state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorDataExternal);

void BM_StdVectorData(benchmark::State& state) {
  std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  for (auto _ : state) {
    UNROLL_16(v.data());
  }
  state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_StdVectorData);

void BM_InlinedVectorSizeInlined(benchmark::State& state) {
  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
  for (auto _ : state) {
    UNROLL_16(v.size());
  }
  state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorSizeInlined);

void BM_InlinedVectorSizeExternal(benchmark::State& state) {
  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  for (auto _ : state) {
    UNROLL_16(v.size());
  }
  state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorSizeExternal);

void BM_StdVectorSize(benchmark::State& state) {
  std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  for (auto _ : state) {
    UNROLL_16(v.size());
  }
  state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_StdVectorSize);

void BM_InlinedVectorEmptyInlined(benchmark::State& state) {
  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
  for (auto _ : state) {
    UNROLL_16(v.empty());
  }
  state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorEmptyInlined);

void BM_InlinedVectorEmptyExternal(benchmark::State& state) {
  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  for (auto _ : state) {
    UNROLL_16(v.empty());
  }
  state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_InlinedVectorEmptyExternal);

void BM_StdVectorEmpty(benchmark::State& state) {
  std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  for (auto _ : state) {
    UNROLL_16(v.empty());
  }
  state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
}
BENCHMARK(BM_StdVectorEmpty);

}  // namespace