YugabyteDB (2.13.0.0-b42, bfc6a6643e7399ac8a0e81d06a3ee6d6571b33ab)

// Licensed to the Apache Software Foundation (ASF) under one

// or more contributor license agreements.  See the NOTICE file

// distributed with this work for additional information

// regarding copyright ownership.  The ASF licenses this file

// to you 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.

//

// The following only applies to changes made to this file as part of YugaByte development.

//

// Portions Copyright (c) YugaByte, Inc.

//

// 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 <glog/logging.h>

#include <glog/stl_logging.h>

#include <gtest/gtest.h>

#include "yb/util/hexdump.h"

#include "yb/util/memcmpable_varint.h"

#include "yb/util/random.h"

#include "yb/util/stopwatch.h" // Required in NDEBUG mode

#include "yb/util/test_macros.h"

#include "yb/util/test_util.h"

namespace yb {

class TestMemcmpableVarint : public YBTest {

 protected:

  TestMemcmpableVarint() : random_(SeedRandom()) {}

  // Random number generator that generates different length integers

  // with equal probability -- i.e it is equally as likely to generate

  // a number with 8 bits as it is to generate one with 64 bits.

  // This is useful for testing varint implementations, where a uniform

  // random is skewed towards generating longer integers.

  uint64_t Rand64WithRandomBitLength() {

    return random_.Next64() >> random_.Uniform(64);

  }

  Random random_;

};

static void DoRoundTripTest(uint64_t to_encode) {

  static faststring buf;

  buf.clear();

  PutMemcmpableVarint64(&buf, to_encode);

  uint64_t decoded;

  Slice slice(buf);

  auto status = GetMemcmpableVarint64(&slice, &decoded);

  ASSERT_OK(status);

  ASSERT_EQ(to_encode, decoded);

  ASSERT_TRUE(slice.empty());

}

TEST_F(TestMemcmpableVarint, TestRoundTrip) {

  // Test the first 100K integers

  // (exercises the special cases for <= 67823 in the code)

  for (int i = 0; i < 100000; i++) {

    DoRoundTripTest(i);

  }

  // Test a bunch of random integers (which are likely to be many bytes)

  for (int i = 0; i < 100000; i++) {

    DoRoundTripTest(random_.Next64());

  }

}

// Test that a composite key can be made up of multiple memcmpable

// varints strung together, and that the resulting key compares the

// same as the original pair of integers (i.e left-to-right).

TEST_F(TestMemcmpableVarint, TestCompositeKeys) {

  faststring buf1;

  faststring buf2;

  const int n_trials = 1000;

  for (int i = 0; i < n_trials; i++) {

    buf1.clear();

    buf2.clear();

    pair<uint64_t, uint64_t> p1 =

      make_pair(Rand64WithRandomBitLength(), Rand64WithRandomBitLength());

    PutMemcmpableVarint64(&buf1, p1.first);

    PutMemcmpableVarint64(&buf1, p1.second);

    pair<uint64_t, uint64_t> p2 =

      make_pair(Rand64WithRandomBitLength(), Rand64WithRandomBitLength());

    PutMemcmpableVarint64(&buf2, p2.first);

    PutMemcmpableVarint64(&buf2, p2.second);

    SCOPED_TRACE(testing::Message() << p1 << "\n" << HexDump(Slice(buf1))

                 << "  vs\n" << p2 << "\n" << HexDump(Slice(buf2)));

    if (p1 < p2) {

      ASSERT_LT(Slice(buf1).compare(Slice(buf2)), 0);

    } else if (p1 > p2) {

      ASSERT_GT(Slice(buf1).compare(Slice(buf2)), 0);

    } else {

      ASSERT_EQ(Slice(buf1).compare(Slice(buf2)), 0);

    }

  }

}

// Similar to the above test, but instead of being randomized, specifically

// tests "interesting" values -- i.e values around the boundaries of where

// the encoding changes its number of bytes.

TEST_F(TestMemcmpableVarint, TestInterestingCompositeKeys) {

  vector<uint64_t> interesting_values = { 0, 1, 240, // 1 byte

                                          241, 2000, 2287, // 2 bytes

                                          2288, 40000, 67823, // 3 bytes

                                          67824, 1ULL << 23, (1ULL << 24) - 1, // 4 bytes

                                          1ULL << 24, 1ULL << 30, (1ULL << 32) - 1 }; // 5 bytes

  faststring buf1;

  faststring buf2;

  for (uint64_t v1 : interesting_values) {

    for (uint64_t v2 : interesting_values) {

      buf1.clear();

      pair<uint64_t, uint64_t> p1 = make_pair(v1, v2);

      PutMemcmpableVarint64(&buf1, p1.first);

      PutMemcmpableVarint64(&buf1, p1.second);

      for (uint64_t v3 : interesting_values) {

        for (uint64_t v4 : interesting_values) {

          buf2.clear();

          pair<uint64_t, uint64_t> p2 = make_pair(v3, v4);

          PutMemcmpableVarint64(&buf2, p2.first);

          PutMemcmpableVarint64(&buf2, p2.second);

          SCOPED_TRACE(testing::Message() << p1 << "\n" << HexDump(Slice(buf1))

                       << "  vs\n" << p2 << "\n" << HexDump(Slice(buf2)));

          if (p1 < p2) {

            ASSERT_LT(Slice(buf1).compare(Slice(buf2)), 0);

          } else if (p1 > p2) {

            ASSERT_GT(Slice(buf1).compare(Slice(buf2)), 0);

          } else {

            ASSERT_EQ(Slice(buf1).compare(Slice(buf2)), 0);

          }

        }

      }

    }

  }

}

////////////////////////////////////////////////////////////

// Benchmarks

////////////////////////////////////////////////////////////

#ifdef NDEBUG

TEST_F(TestMemcmpableVarint, BenchmarkEncode) {

  faststring buf;

  int sum_sizes = 0; // need to do something with results to force evaluation

  LOG_TIMING(INFO, "Encoding integers") {

    for (int trial = 0; trial < 100; trial++) {

      for (uint64_t i = 0; i < 1000000; i++) {

        buf.clear();

        PutMemcmpableVarint64(&buf, i);

        sum_sizes += buf.size();

      }

    }

  }

  ASSERT_GT(sum_sizes, 1); // use 'sum_sizes' to avoid optimizing it out.

}

TEST_F(TestMemcmpableVarint, BenchmarkDecode) {

  faststring buf;

  // Encode 1M integers into the buffer

  for (uint64_t i = 0; i < 1000000; i++) {

    PutMemcmpableVarint64(&buf, i);

  }

  // Decode the whole buffer 100 times.

  LOG_TIMING(INFO, "Decoding integers") {

    uint64_t sum_vals = 0;

    for (int trial = 0; trial < 100; trial++) {

      Slice s(buf);

      while (!s.empty()) {

        uint64_t decoded;

        CHECK(GetMemcmpableVarint64(&s, &decoded).ok());

        sum_vals += decoded;

      }

    }

    ASSERT_GT(sum_vals, 1); // use 'sum_vals' to avoid optimizing it out.

  }

}

#endif

} // namespace yb