From 356172042cbc96375be8d663a945879b9f10dd41 Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Wed, 7 Oct 2020 20:29:40 +0000 Subject: - GC unused code. - vespalib::Lock -> std::mutex --- vdslib/CMakeLists.txt | 1 - vdslib/src/tests/CMakeLists.txt | 1 - vdslib/src/tests/bucketdistribution/.gitignore | 3 - vdslib/src/tests/bucketdistribution/CMakeLists.txt | 8 -- .../bucketdistribution/bucketdistributiontest.cpp | 92 ---------------- vdslib/src/vespa/vdslib/CMakeLists.txt | 1 - vdslib/src/vespa/vdslib/bucketdistribution.cpp | 115 -------------------- vdslib/src/vespa/vdslib/bucketdistribution.h | 119 --------------------- 8 files changed, 340 deletions(-) delete mode 100644 vdslib/src/tests/bucketdistribution/.gitignore delete mode 100644 vdslib/src/tests/bucketdistribution/CMakeLists.txt delete mode 100644 vdslib/src/tests/bucketdistribution/bucketdistributiontest.cpp delete mode 100644 vdslib/src/vespa/vdslib/bucketdistribution.cpp delete mode 100644 vdslib/src/vespa/vdslib/bucketdistribution.h (limited to 'vdslib') diff --git a/vdslib/CMakeLists.txt b/vdslib/CMakeLists.txt index b997bf5f983..3c1ee756e56 100644 --- a/vdslib/CMakeLists.txt +++ b/vdslib/CMakeLists.txt @@ -21,7 +21,6 @@ vespa_define_module( TESTS src/tests - src/tests/bucketdistribution src/tests/container src/tests/distribution src/tests/state diff --git a/vdslib/src/tests/CMakeLists.txt b/vdslib/src/tests/CMakeLists.txt index bc230a7157b..6cf1ba5e33f 100644 --- a/vdslib/src/tests/CMakeLists.txt +++ b/vdslib/src/tests/CMakeLists.txt @@ -6,7 +6,6 @@ vespa_add_executable(vdslib_gtest_runner_app TEST SOURCES gtest_runner.cpp DEPENDS - vdslib_bucketdistributiontest vdslib_containertest vdslib_testdistribution vdslib_teststate diff --git a/vdslib/src/tests/bucketdistribution/.gitignore b/vdslib/src/tests/bucketdistribution/.gitignore deleted file mode 100644 index 583460ae288..00000000000 --- a/vdslib/src/tests/bucketdistribution/.gitignore +++ /dev/null @@ -1,3 +0,0 @@ -*.So -.depend -Makefile diff --git a/vdslib/src/tests/bucketdistribution/CMakeLists.txt b/vdslib/src/tests/bucketdistribution/CMakeLists.txt deleted file mode 100644 index 79ca63b72f2..00000000000 --- a/vdslib/src/tests/bucketdistribution/CMakeLists.txt +++ /dev/null @@ -1,8 +0,0 @@ -# Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -vespa_add_library(vdslib_bucketdistributiontest - SOURCES - bucketdistributiontest.cpp - DEPENDS - vdslib - GTest::GTest -) diff --git a/vdslib/src/tests/bucketdistribution/bucketdistributiontest.cpp b/vdslib/src/tests/bucketdistribution/bucketdistributiontest.cpp deleted file mode 100644 index 7f2b012680c..00000000000 --- a/vdslib/src/tests/bucketdistribution/bucketdistributiontest.cpp +++ /dev/null @@ -1,92 +0,0 @@ -// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. - -#include -#include - -using namespace vdslib; - -void -assertDistribution(uint32_t numColumns, uint32_t numBucketBits, const uint32_t expected[]) -{ - BucketDistribution bd(numColumns, numBucketBits); - EXPECT_EQ(numColumns, bd.getNumColumns()); - EXPECT_EQ((uint32_t)(1 << numBucketBits), bd.getNumBuckets()); - for (uint32_t i = 0; i < bd.getNumBuckets(); ++i) { - EXPECT_EQ(expected[i], bd.getColumn(document::BucketId(16, i))); - } -} - -TEST(BucketDistributionTest, testDistribution) -{ - const uint32_t expected4[] = { - 10, 11, 9, 6, 4, 8, 14, 1, 13, 2, 12, 3, 5, 7, 15, 0 }; - assertDistribution(16, 4, expected4); - - const uint32_t expected5[] = { - 11, 12, 11, 13, 8, 13, 8, 9, 4, 5, 6, 12, 10, 15, 1, 1, 7, 9, 14, 2, 2, 14, 3, 3, 4, 5, 6, 7, 10, 15, 0, 0 }; - assertDistribution(16, 5, expected5); - - const uint32_t expected6[] = { - 13, 13, 13, 13, 9, 11, 8, 9, 11, 14, 9, 11, 14, 14, 8, 10, 11, 14, 4, 5, 5, 6, 6, 7, 8, 10, 12, 15, 1, 1, 1, 1, - 6, 7, 8, 10, 12, 15, 2, 2, 2, 2, 12, 15, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 7, 7, 9, 10, 12, 15, 0, 0, 0, 0 }; - assertDistribution(16, 6, expected6); - - const uint32_t expected7[] = { - 14, 14, 14, 13, 11, 14, 14, 10, 13, 14, 10, 12, 8, 8, 9, 10, 9, 10, 11, 12, 13, 15, 11, 12, 13, 13, 15, 8, 8, 9, 10, 11, - 11, 12, 13, 15, 4, 4, 5, 5, 5, 5, 15, 6, 6, 7, 7, 7, 8, 9, 9, 10, 11, 12, 14, 15, 1, 1, 1, 1, 1, 1, 1, 1, - 6, 6, 6, 7, 7, 8, 8, 9, 10, 11, 12, 13, 15, 2, 2, 2, 2, 2, 2, 2, 2, 12, 13, 15, 3, 3, 3, 3, 3, 3, 3, 3, - 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 9, 9, 10, 11, 12, 14, 15, 0, 0, 0, 0, 0, 0, 0, 0 }; - assertDistribution(16, 7, expected7); - - const uint32_t expected8[] = { - 15, 14, 15, 15, 12, 14, 15, 12, 12, 11, 12, 13, 14, 13, 13, 13, 14, 15, 15, 9, 14, 9, 15, 10, 11, 11, 12, 8, 8, 8, 8, 9, - 9, 10, 10, 10, 11, 11, 12, 13, 13, 14, 10, 11, 11, 12, 13, 13, 14, 13, 13, 14, 15, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 11, - 10, 10, 11, 11, 12, 13, 13, 14, 15, 4, 4, 4, 4, 15, 5, 5, 5, 5, 5, 5, 5, 15, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, - 8, 8, 8, 9, 9, 9, 10, 10, 11, 11, 12, 12, 13, 14, 14, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 11, 11, 12, 12, 13, 14, 14, 15, 2, 2, 2, 2, 2, 2, - 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 12, 12, 13, 14, 14, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, - 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, - 8, 8, 8, 9, 9, 9, 10, 10, 11, 11, 12, 12, 13, 14, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; - assertDistribution(16, 8, expected8); - - const uint32_t expected9[] = { - 15, 15, 15, 15, 14, 14, 15, 13, 13, 13, 13, 13, 14, 14, 15, 12, 14, 15, 15, 11, 11, 12, 13, 13, 13, 14, 14, 15, 15, 10, 12, 12, - 12, 13, 13, 13, 14, 14, 15, 15, 9, 9, 9, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 15, 15, 8, 8, 8, 8, 9, 9, 9, - 9, 9, 9, 10, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, - 13, 13, 14, 14, 14, 15, 15, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, - 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 4, 4, 4, 4, 4, 4, 4, 15, 15, 5, 5, 5, 5, 5, - 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 14, 14, 14, 15, 15, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 15, 15, 15, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, - 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, - 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, - 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, - 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, - 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 15, 15, 15, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; - assertDistribution(16, 9, expected9); -} - -TEST(BucketDistributionTest, testNumBucketBits) -{ - BucketDistribution bd(1, 4); - for (uint32_t i = 0; i <= 0xf; ++i) { - EXPECT_EQ(0u, bd.getColumn(document::BucketId(32, (rand() << 4) & i))); - } - - bd.reset(); - bd.setNumColumns(1); - bd.setNumBucketBits(8); - for (uint32_t i = 0; i <= 0xff; ++i) { - EXPECT_EQ(0u, bd.getColumn(document::BucketId(32, (rand() << 8) & i))); - } - - bd.reset(); - bd.setNumColumns(1); - bd.setNumBucketBits(16); - for (uint32_t i = 0; i <= 0xffff; ++i) { - EXPECT_EQ(0u, bd.getColumn(document::BucketId(32, (rand() << 16) & i))); - } -} diff --git a/vdslib/src/vespa/vdslib/CMakeLists.txt b/vdslib/src/vespa/vdslib/CMakeLists.txt index ace44439a23..cf5053a5ceb 100644 --- a/vdslib/src/vespa/vdslib/CMakeLists.txt +++ b/vdslib/src/vespa/vdslib/CMakeLists.txt @@ -1,7 +1,6 @@ # Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. vespa_add_library(vdslib SOURCES - bucketdistribution.cpp $ $ $ diff --git a/vdslib/src/vespa/vdslib/bucketdistribution.cpp b/vdslib/src/vespa/vdslib/bucketdistribution.cpp deleted file mode 100644 index 15947d82fed..00000000000 --- a/vdslib/src/vespa/vdslib/bucketdistribution.cpp +++ /dev/null @@ -1,115 +0,0 @@ -// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#include "bucketdistribution.h" - -#include -LOG_SETUP(".bucketdistribution"); - -namespace vdslib { - -BucketDistribution::BucketDistribution(uint32_t numColumns, uint32_t numBucketBits) : - _numColumns(0), - _numBucketBits(numBucketBits), - _bucketToColumn(), - _lock() -{ - _bucketToColumn.resize(getNumBuckets()); - reset(); - setNumColumns(numColumns); -} - -BucketDistribution::~BucketDistribution() = default; - -void -BucketDistribution::getBucketCount(uint32_t numColumns, uint32_t numBucketBits, std::vector &ret) -{ - ret.resize(numColumns); - uint32_t cnt = getNumBuckets(numBucketBits) / numColumns; - uint32_t rst = getNumBuckets(numBucketBits) % numColumns; - for (uint32_t i = 0; i < numColumns; ++i) { - ret[i] = cnt + (i < rst ? 1 : 0); - } -} - -void -BucketDistribution::getBucketMigrateCount(uint32_t numColumns, uint32_t numBucketBits, std::vector &ret) -{ - getBucketCount(numColumns++, numBucketBits, ret); - uint32_t cnt = getNumBuckets(numBucketBits) / numColumns; - uint32_t rst = getNumBuckets(numBucketBits) % numColumns; - for (uint32_t i = 0; i < numColumns - 1; ++i) { - ret[i] -= cnt + (i < rst ? 1 : 0); - } -} - -void -BucketDistribution::reset() -{ - for (uint32_t & value : _bucketToColumn) { - value = 0; - } - _numColumns = 1; -} - -void -BucketDistribution::addColumn() -{ - uint32_t newColumns = _numColumns + 1; - std::vector migrate; - getBucketMigrateCount(_numColumns, _numBucketBits, migrate); - uint32_t numBuckets = getNumBuckets(_numBucketBits); - for (uint32_t i = 0; i < numBuckets; ++i) { - uint32_t old = _bucketToColumn[i]; - if (migrate[old] > 0) { - _bucketToColumn[i] = _numColumns; // move this bucket to the new column - migrate[old]--; - } - } - _numColumns = newColumns; -} - -void -BucketDistribution::setNumColumns(uint32_t numColumns) -{ - vespalib::LockGuard guard(_lock); - if (numColumns < _numColumns) { - reset(); - } - if (numColumns == _numColumns) { - return; - } - for (int i = numColumns - _numColumns; --i >= 0; ) { - addColumn(); - } -} - -void -BucketDistribution::setNumBucketBits(uint32_t numBucketBits) -{ - uint32_t numColumns; - { - vespalib::LockGuard guard(_lock); - if (numBucketBits == _numBucketBits) { - return; - } - _numBucketBits = numBucketBits; - _bucketToColumn.resize(getNumBuckets(numBucketBits)); - numColumns = _numColumns; - reset(); - } - setNumColumns(numColumns); -} - -uint32_t -BucketDistribution::getColumn(const document::BucketId &bucketId) const -{ - uint32_t ret = (uint32_t)(bucketId.getId() & (getNumBuckets(_numBucketBits) - 1)); - if (ret >= _bucketToColumn.size()) { - LOG(error, - "The bucket distribution map is not in sync with the number of bucket bits. " - "This should never happen! Distribution is broken!!"); - return 0; - } - return _bucketToColumn[ret]; -} - -} diff --git a/vdslib/src/vespa/vdslib/bucketdistribution.h b/vdslib/src/vespa/vdslib/bucketdistribution.h deleted file mode 100644 index 5d06be53b49..00000000000 --- a/vdslib/src/vespa/vdslib/bucketdistribution.h +++ /dev/null @@ -1,119 +0,0 @@ -// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -#pragma once - -#include -#include -#include - -namespace vdslib { - -/** - * Stable algorithmic hash distribution; this class assigns hash buckets to targets. The number of hash buckets should - * be large compared to the number of targets. The mapping from hash value to hash bucket is performed outside this - * class. - */ -class BucketDistribution { -public: - /** - * Constructs a new bucket distribution object with a given number of columns and buckets. - * - * @param numColumns The number of columns to distribute to. - * @param numBucketBits The number of bits to use for bucket id. - */ - BucketDistribution(uint32_t numColumns, uint32_t numBucketBits); - ~BucketDistribution(); - - /** - * Returns the number of buckets that the given number of bucket bits will allow. - * - * @param numBucketBits The number of bits to use for bucket id. - * @return The number of buckets allowed. - */ - static uint32_t getNumBuckets(uint32_t numBucketBits) { return 1 << numBucketBits; } - - /** - * This method returns a list that contains the distributions of the given number of buckets over the given number - * of columns. - * - * @param numColumns The number of columns to distribute to. - * @param numBucketBits The number of bits to use for bucket id. - * @param ret List to fill with the bucket distribution. - */ - static void getBucketCount(uint32_t numColumns, uint32_t numBucketBits, std::vector &ret); - - /** - * This method returns a list similar to {@link this#getBucketCount(int,int)}, except that the returned list - * contains the number of buckets that will have to be migrated from each column if an additional column was added. - * - * @param numColumns The original number of columns. - * @param numBucketBits The number of bits to use for bucket id. - * @param ret List to fill with the number of buckets to migrate, one value per column. - */ - static void getBucketMigrateCount(uint32_t numColumns, uint32_t numBucketBits, std::vector &ret); - - /** - * Sets the number of columns to distribute to to 1, and resets the content of the internal bucket-to-column map so - * that it all buckets point to that single column. - */ - void reset(); - - /** - * Sets the number of columns to use for this document distribution object. This will reset and setup this object - * from scratch. The original number of buckets is maintained. - * - * @param numColumns The new number of columns to distribute to. - */ - void setNumColumns(uint32_t numColumns); - - /** - * Returns the number of columns to distribute to. - * - * @return The number of columns. - */ - uint32_t getNumColumns() const { return _numColumns; } - - /** - * Sets the number of buckets to use for this document distribution object. This will reset and setup this object - * from scratch. The original number of columns is maintained. - * - * @param numBucketBits The new number of bits to use for bucket id. - */ - void setNumBucketBits(uint32_t numBucketBits); - - /** - * Returns the number of bits used for bucket identifiers. - * - * @return The number of bits. - */ - uint32_t getNumBucketBits() const { return _numBucketBits; } - - /** - * Returns the number of buckets available using the configured number of bucket bits. - * - * @return The number of buckets. - */ - uint32_t getNumBuckets() const { return getNumBuckets(_numBucketBits); } - - /** - * This method maps the given bucket id to its corresponding column. - * - * @param bucketId The bucket whose column to lookup. - * @return The column to distribute the bucket to. - */ - uint32_t getColumn(const document::BucketId &bucketId) const; - -private: - /** - * Adds a single column to this bucket distribution object. This will modify the internal bucket-to-column map so - * that it takes into account the new column. - */ - void addColumn(); - -private: - uint32_t _numColumns; // The number of columns to distribute to. - uint32_t _numBucketBits; // The number of bits to use for bucket identification. - std::vector _bucketToColumn; // A map from bucket id to column index. - vespalib::Lock _lock; -}; - -} -- cgit v1.2.3