diff options
Diffstat (limited to 'vdslib')
17 files changed, 250 insertions, 1171 deletions
diff --git a/vdslib/src/main/java/com/yahoo/vdslib/state/ClusterState.java b/vdslib/src/main/java/com/yahoo/vdslib/state/ClusterState.java index b3d572e48ae..d70b55c66a2 100644 --- a/vdslib/src/main/java/com/yahoo/vdslib/state/ClusterState.java +++ b/vdslib/src/main/java/com/yahoo/vdslib/state/ClusterState.java @@ -11,6 +11,9 @@ import java.util.*; */ public class ClusterState implements Cloneable { + private static final NodeState DEFAULT_STORAGE_UP_NODE_STATE = new NodeState(NodeType.STORAGE, State.UP); + private static final NodeState DEFAULT_DISTRIBUTOR_UP_NODE_STATE = new NodeState(NodeType.DISTRIBUTOR, State.UP); + private int version = 0; private State state = State.DOWN; // nodeStates maps each of the non-up nodes that have an index <= the node count for its type. @@ -30,6 +33,22 @@ public class ClusterState implements Cloneable { deserialize(serialized); } + /** + * Parse a given cluster state string into a returned ClusterState instance, wrapping any + * parse exceptions in a RuntimeException. + */ + public static ClusterState stateFromString(final String stateStr) { + try { + return new ClusterState(stateStr); + } catch (Exception e) { + throw new RuntimeException(e); + } + } + + public static ClusterState emptyState() { + return stateFromString(""); + } + public ClusterState clone() { try{ ClusterState state = (ClusterState) super.clone(); @@ -61,22 +80,81 @@ public class ClusterState implements Cloneable { return true; } + @FunctionalInterface + private interface NodeStateCmp { + boolean similar(NodeType nodeType, NodeState lhs, NodeState rhs); + } + public boolean similarTo(Object o) { if (!(o instanceof ClusterState)) { return false; } - ClusterState other = (ClusterState) o; + final ClusterState other = (ClusterState) o; - if (state.equals(State.DOWN) && other.state.equals(State.DOWN)) return true; // both down, means equal (why??) - if (version != other.version || !state.equals(other.state)) return false; - if (distributionBits != other.distributionBits) return false; - if ( ! nodeCount.equals(other.nodeCount)) return false; + return similarToImpl(other, this::normalizedNodeStateSimilarTo); + } + + public boolean similarToIgnoringInitProgress(final ClusterState other) { + return similarToImpl(other, this::normalizedNodeStateSimilarToIgnoringInitProgress); + } - for (Map.Entry<Node, NodeState> nodeStateEntry : nodeStates.entrySet()) { - NodeState otherNodeState = other.nodeStates.get(nodeStateEntry.getKey()); - if (otherNodeState == null || ! otherNodeState.similarTo(nodeStateEntry.getValue())) return false; + private boolean similarToImpl(final ClusterState other, final NodeStateCmp nodeStateCmp) { + // Two cluster states are considered similar if they are both down. When clusters + // are down, their individual node states do not matter to ideal state computations + // and content nodes therefore do not need to observe them. + if (state.equals(State.DOWN) && other.state.equals(State.DOWN)) { + return true; + } + if (!metaInformationSimilarTo(other)) { + return false; + } + // TODO verify behavior of C++ impl against this + for (Node node : unionNodeSetWith(other.nodeStates.keySet())) { + final NodeState lhs = nodeStates.get(node); + final NodeState rhs = other.nodeStates.get(node); + if (!nodeStateCmp.similar(node.getType(), lhs, rhs)) { + return false; + } } return true; } + private Set<Node> unionNodeSetWith(final Set<Node> otherNodes) { + final Set<Node> unionNodeSet = new TreeSet<Node>(nodeStates.keySet()); + unionNodeSet.addAll(otherNodes); + return unionNodeSet; + } + + private boolean metaInformationSimilarTo(final ClusterState other) { + if (version != other.version || !state.equals(other.state)) { + return false; + } + if (distributionBits != other.distributionBits) { + return false; + } + return nodeCount.equals(other.nodeCount); + } + + private boolean normalizedNodeStateSimilarTo(final NodeType nodeType, final NodeState lhs, final NodeState rhs) { + final NodeState lhsNormalized = (lhs != null ? lhs : defaultUpNodeState(nodeType)); + final NodeState rhsNormalized = (rhs != null ? rhs : defaultUpNodeState(nodeType)); + + return lhsNormalized.similarTo(rhsNormalized); + } + + private boolean normalizedNodeStateSimilarToIgnoringInitProgress( + final NodeType nodeType, final NodeState lhs, final NodeState rhs) + { + final NodeState lhsNormalized = (lhs != null ? lhs : defaultUpNodeState(nodeType)); + final NodeState rhsNormalized = (rhs != null ? rhs : defaultUpNodeState(nodeType)); + + return lhsNormalized.similarToIgnoringInitProgress(rhsNormalized); + } + + private static NodeState defaultUpNodeState(final NodeType nodeType) { + return nodeType == NodeType.STORAGE + ? DEFAULT_STORAGE_UP_NODE_STATE + : DEFAULT_DISTRIBUTOR_UP_NODE_STATE; + } + /** * Fleet controller marks states that are actually sent out to nodes as official states. Only fleetcontroller * should set this to official, and only just before sending it out. This state is currently not serialized with @@ -97,7 +175,7 @@ public class ClusterState implements Cloneable { public void addNodeState() throws ParseException { if (!empty) { NodeState ns = NodeState.deserialize(node.getType(), sb.toString()); - if (!ns.equals(new NodeState(node.getType(), State.UP))) { + if (!ns.equals(defaultUpNodeState(node.getType()))) { nodeStates.put(node, ns); } if (nodeCount.get(node.getType().ordinal()) <= node.getIndex()) { diff --git a/vdslib/src/main/java/com/yahoo/vdslib/state/NodeState.java b/vdslib/src/main/java/com/yahoo/vdslib/state/NodeState.java index 8c31938dfaf..15c929fe49d 100644 --- a/vdslib/src/main/java/com/yahoo/vdslib/state/NodeState.java +++ b/vdslib/src/main/java/com/yahoo/vdslib/state/NodeState.java @@ -112,17 +112,27 @@ public class NodeState implements Cloneable { * Cluster state will check for that. */ public boolean similarTo(Object o) { - if (!(o instanceof NodeState)) { return false; } - NodeState other = (NodeState) o; + if (!(o instanceof NodeState)) { + return false; + } + return similarToImpl((NodeState)o, true); + } + + public boolean similarToIgnoringInitProgress(final NodeState other) { + return similarToImpl(other, false); + } + private boolean similarToImpl(final NodeState other, boolean considerInitProgress) { if (state != other.state) return false; if (Math.abs(capacity - other.capacity) > 0.0000000001) return false; if (Math.abs(reliability - other.reliability) > 0.0000000001) return false; if (startTimestamp != other.startTimestamp) return false; // Init progress on different sides of the init progress limit boundary is not similar. - if (type.equals(NodeType.STORAGE) - && initProgress < getListingBucketsInitProgressLimit() ^ other.initProgress < getListingBucketsInitProgressLimit()) + if (considerInitProgress + && type.equals(NodeType.STORAGE) + && (initProgress < getListingBucketsInitProgressLimit() + ^ other.initProgress < getListingBucketsInitProgressLimit())) { return false; } diff --git a/vdslib/src/test/java/com/yahoo/vdslib/state/ClusterStateTestCase.java b/vdslib/src/test/java/com/yahoo/vdslib/state/ClusterStateTestCase.java index c058a7c9919..0d06fcc6faa 100644 --- a/vdslib/src/test/java/com/yahoo/vdslib/state/ClusterStateTestCase.java +++ b/vdslib/src/test/java/com/yahoo/vdslib/state/ClusterStateTestCase.java @@ -1,10 +1,18 @@ // Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. package com.yahoo.vdslib.state; +import org.junit.Test; + import java.text.ParseException; +import java.util.function.BiFunction; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; -public class ClusterStateTestCase extends junit.framework.TestCase { +public class ClusterStateTestCase{ + @Test public void testSetNodeState() throws ParseException { ClusterState state = new ClusterState(""); assertEquals("", state.toString()); @@ -22,6 +30,7 @@ public class ClusterStateTestCase extends junit.framework.TestCase { assertEquals("distributor:5 .0.s:d .2.s:d .3.s:d storage:1 .0.d:4 .0.d.1.s:d", state.toString()); } + @Test public void testClone() throws ParseException { ClusterState state = new ClusterState(""); state.setNodeState(new Node(NodeType.DISTRIBUTOR, 1), new NodeState(NodeType.DISTRIBUTOR, State.UP).setDescription("available")); @@ -31,8 +40,9 @@ public class ClusterStateTestCase extends junit.framework.TestCase { assertEquals(state.toString(true), other.toString(true)); assertEquals(state.toString(false), other.toString(false)); assertEquals(state, other); - } + } + @Test public void testEquals() throws ParseException { ClusterState state = new ClusterState(""); @@ -55,6 +65,7 @@ public class ClusterStateTestCase extends junit.framework.TestCase { ClusterState state2 = new ClusterState("distributor:3 .1.s:d .2.s:m storage:3 .1.s:i .2.s:m"); assertFalse(state1.equals(state2)); assertFalse(state1.similarTo(state2)); + assertFalse(state1.similarToIgnoringInitProgress(state2)); } { @@ -62,6 +73,7 @@ public class ClusterStateTestCase extends junit.framework.TestCase { ClusterState state2 = new ClusterState("cluster:d version:1 bits:20 distributor:1 storage:1 .0.s:d"); assertFalse(state1.equals(state2)); assertTrue(state1.similarTo(state2)); + assertTrue(state1.similarToIgnoringInitProgress(state2)); } { @@ -69,6 +81,7 @@ public class ClusterStateTestCase extends junit.framework.TestCase { ClusterState state2 = new ClusterState("distributor:3 storage:3"); assertFalse(state1.equals(state2)); assertFalse(state1.similarTo(state2)); + assertFalse(state1.similarToIgnoringInitProgress(state2)); } assertFalse(state.equals("class not instance of ClusterState")); @@ -78,6 +91,92 @@ public class ClusterStateTestCase extends junit.framework.TestCase { assertTrue(state.similarTo(state)); } + private static ClusterState stateFromString(final String stateStr) { + try { + return new ClusterState(stateStr); + } catch (ParseException e) { + throw new RuntimeException(e); + } + } + + private void do_test_differing_storage_node_sets(BiFunction<ClusterState, ClusterState, Boolean> cmp) { + final ClusterState a = stateFromString("distributor:3 storage:3 .0.s:d"); + final ClusterState b = stateFromString("distributor:3 storage:3"); + assertFalse(cmp.apply(a, b)); + assertFalse(cmp.apply(b, a)); + assertTrue(cmp.apply(a, a)); + assertTrue(cmp.apply(b, b)); + } + + private void do_test_differing_distributor_node_sets(BiFunction<ClusterState, ClusterState, Boolean> cmp) { + final ClusterState a = stateFromString("distributor:3 .0.s:d storage:3"); + final ClusterState b = stateFromString("distributor:3 storage:3"); + assertFalse(cmp.apply(a, b)); + assertFalse(cmp.apply(b, a)); + assertTrue(cmp.apply(a, a)); + assertTrue(cmp.apply(b, b)); + } + + @Test + public void similarity_check_considers_differing_distributor_node_state_sets() { + do_test_differing_distributor_node_sets((a, b) -> a.similarTo(b)); + } + + @Test + public void similarity_check_considers_differing_storage_node_state_sets() { + do_test_differing_storage_node_sets((a, b) -> a.similarTo(b)); + } + + @Test + public void structural_similarity_check_considers_differing_distributor_node_state_sets() { + do_test_differing_distributor_node_sets((a, b) -> a.similarToIgnoringInitProgress(b)); + } + + @Test + public void init_progress_ignoring_similarity_check_considers_differing_storage_node_state_sets() { + do_test_differing_storage_node_sets((a, b) -> a.similarToIgnoringInitProgress(b)); + } + + private void do_test_similarity_for_down_cluster_state(BiFunction<ClusterState, ClusterState, Boolean> cmp) { + final ClusterState a = stateFromString("cluster:d distributor:3 .0.s:d storage:3 .2:s:d"); + final ClusterState b = stateFromString("cluster:d distributor:3 storage:3 .1:s:d"); + assertTrue(cmp.apply(a, b)); + assertTrue(cmp.apply(b, a)); + } + + @Test + public void similarity_check_considers_differing_down_cluster_states_similar() { + do_test_similarity_for_down_cluster_state((a, b) -> a.similarTo(b)); + } + + @Test + public void init_progress_ignoring__similarity_check_considers_differing_down_cluster_states_similar() { + do_test_similarity_for_down_cluster_state((a, b) -> a.similarToIgnoringInitProgress(b)); + } + + // If we naively only look at the NodeState sets in the ClusterState instances to be + // compared, we might get false positives. If state A has a NodeState(Up, minBits 15) + // while state B has NodeState(Up, minBits 16), the latter will be pruned away from the + // NodeState set because it's got a "default" Up state. The two states are still semantically + // similar, and should be returned as such. But their state sets technically differ. + @Test + public void similarity_check_does_not_consider_per_storage_node_min_bits() { + final ClusterState a = stateFromString("distributor:4 storage:4"); + final ClusterState b = stateFromString("distributor:4 storage:4"); + b.setNodeState(new Node(NodeType.STORAGE, 1), new NodeState(NodeType.STORAGE, State.UP).setMinUsedBits(15)); + assertTrue(a.similarTo(b)); + assertTrue(b.similarTo(a)); + } + + @Test + public void init_progress_ignoring_similarity_check_does_in_fact_ignore_init_progress() { + final ClusterState a = stateFromString("distributor:3 storage:3 .0.i:0.01 .1.i:0.1 .2.i:0.9"); + final ClusterState b = stateFromString("distributor:3 storage:3 .0.i:0.2 .1.i:0.5 .2.i:0.99"); + assertTrue(a.similarToIgnoringInitProgress(b)); + assertTrue(b.similarToIgnoringInitProgress(a)); + } + + @Test public void testTextDiff() throws ParseException { ClusterState state1 = new ClusterState("distributor:9 storage:4"); ClusterState state2 = new ClusterState("distributor:7 storage:6"); @@ -94,6 +193,7 @@ public class ClusterStateTestCase extends junit.framework.TestCase { assertEquals("version: 123 => 0, bits: 16 => 21, official: false => true, storage: [2: [Initializing => Up, disks: 2 => 0, description: Booting => ], 4: Down => Up, 5: Down => Up], distributor: [7: Up => Down, 8: Up => Down]", state1.getTextualDifference(state2)); } + @Test public void testHtmlDiff() throws ParseException { ClusterState state1 = new ClusterState("distributor:9 storage:4"); ClusterState state2 = new ClusterState("distributor:7 storage:6"); @@ -133,7 +233,7 @@ public class ClusterStateTestCase extends junit.framework.TestCase { "]", state1.getHtmlDifference(state2)); } - + @Test public void testParser() throws ParseException { ClusterState state = new ClusterState("distributor:2 storage:17 .2.s:d .13.s:r m:cluster\\x20message"); assertEquals("cluster message", state.getDescription()); @@ -191,17 +291,20 @@ public class ClusterStateTestCase extends junit.framework.TestCase { } catch (Exception e) {} } + @Test public void testCapacityExponential() throws ParseException { ClusterState state = new ClusterState("distributor:27 storage:170 .2.s:d .13.c:3E-8 .13.s:r"); - assertEquals(3E-8, state.getNodeState(new Node(NodeType.STORAGE, 13)).getCapacity()); + assertEquals(3E-8, state.getNodeState(new Node(NodeType.STORAGE, 13)).getCapacity(), 1E-8); } + @Test public void testCapacityExponentialCpp() throws ParseException { ClusterState state = new ClusterState("distributor:27 storage:170 .2.s:d .13.c:3e-08 .13.s:r"); - assertEquals(3E-8, state.getNodeState(new Node(NodeType.STORAGE, 13)).getCapacity()); + assertEquals(3E-8, state.getNodeState(new Node(NodeType.STORAGE, 13)).getCapacity(), 1E-8); } + @Test public void testSetState() throws ParseException { ClusterState state = new ClusterState("distributor:2 storage:2"); state.setNodeState(new Node(NodeType.DISTRIBUTOR, 0), new NodeState(NodeType.DISTRIBUTOR, State.DOWN)); @@ -209,6 +312,7 @@ public class ClusterStateTestCase extends junit.framework.TestCase { assertEquals("distributor:2 .0.s:d storage:2", state.toString()); } + @Test public void testVersionAndClusterStates() throws ParseException { ClusterState state = new ClusterState("version:4 cluster:i distributor:2 .1.s:i storage:2 .0.s:i .0.i:0.345"); assertEquals(4, state.getVersion()); @@ -220,6 +324,7 @@ public class ClusterStateTestCase extends junit.framework.TestCase { assertEquals("version:5 cluster:d bits:12 distributor:2 .1.s:i .1.i:1.0 storage:2 .0.s:i .0.i:0.345", state.toString()); } + @Test public void testNotRemovingCommentedDownNodesAtEnd() throws ParseException { ClusterState state = new ClusterState(""); state.setNodeState(new Node(NodeType.DISTRIBUTOR, 0), new NodeState(NodeType.DISTRIBUTOR, State.UP)); @@ -234,6 +339,7 @@ public class ClusterStateTestCase extends junit.framework.TestCase { assertEquals("distributor:1 storage:2", state.toString(false)); } + @Test public void testWhitespace() throws ParseException { ClusterState state = new ClusterState("distributor:2\n .1.t:3\nstorage:2\n\t.0.s:i \r\f.1.s:m"); assertEquals(2, state.getNodeCount(NodeType.DISTRIBUTOR)); @@ -243,4 +349,22 @@ public class ClusterStateTestCase extends junit.framework.TestCase { assertEquals(new NodeState(NodeType.STORAGE, State.INITIALIZING), state.getNodeState(new Node(NodeType.STORAGE, 0))); assertEquals(new NodeState(NodeType.STORAGE, State.MAINTENANCE), state.getNodeState(new Node(NodeType.STORAGE, 1))); } + + @Test + public void empty_state_factory_method_returns_empty_state() { + final ClusterState state = ClusterState.emptyState(); + assertEquals("", state.toString()); + } + + @Test + public void state_from_string_factory_method_returns_cluster_state_constructed_from_input() { + final String stateStr = "version:123 distributor:2 storage:2"; + final ClusterState state = ClusterState.stateFromString(stateStr); + assertEquals(stateStr, state.toString()); + } + + @Test(expected=RuntimeException.class) + public void state_from_string_factory_method_throws_runtime_exception_on_parse_failure() { + ClusterState.stateFromString("fraggle rock"); + } } diff --git a/vdslib/src/test/java/com/yahoo/vdslib/state/NodeStateTestCase.java b/vdslib/src/test/java/com/yahoo/vdslib/state/NodeStateTestCase.java index 63137a92c7b..9362838b63c 100644 --- a/vdslib/src/test/java/com/yahoo/vdslib/state/NodeStateTestCase.java +++ b/vdslib/src/test/java/com/yahoo/vdslib/state/NodeStateTestCase.java @@ -165,6 +165,12 @@ public class NodeStateTestCase extends junit.framework.TestCase { assertFalse(ns2.similarTo(ns3)); assertTrue(ns3.similarTo(ns4)); + assertTrue(ns1.similarToIgnoringInitProgress(ns2)); + assertTrue(ns1.similarToIgnoringInitProgress(ns3)); + assertTrue(ns3.similarToIgnoringInitProgress(ns1)); + assertTrue(ns1.similarToIgnoringInitProgress(ns4)); + assertTrue(ns2.similarToIgnoringInitProgress(ns4)); + assertFalse(ns1.equals(ns2)); assertFalse(ns2.equals(ns3)); assertFalse(ns3.equals(ns4)); @@ -176,6 +182,7 @@ public class NodeStateTestCase extends junit.framework.TestCase { NodeState ns1 = new NodeState(NodeType.STORAGE, State.UP).setMinUsedBits(16); NodeState ns2 = new NodeState(NodeType.STORAGE, State.UP).setMinUsedBits(18); assertTrue(ns1.similarTo(ns2)); + assertTrue(ns1.similarToIgnoringInitProgress(ns2)); assertFalse(ns1.equals(ns2)); } { @@ -184,12 +191,14 @@ public class NodeStateTestCase extends junit.framework.TestCase { assertEquals(ns, ns2Disks); assertEquals(ns2Disks, ns); assertTrue(ns.similarTo(ns2Disks)); + assertTrue(ns.similarToIgnoringInitProgress(ns2Disks)); assertTrue(ns2Disks.similarTo(ns)); ns2Disks.getDiskState(0).setState(State.DOWN); assertFalse(ns.equals(ns2Disks)); assertFalse(ns2Disks.equals(ns)); assertFalse(ns.similarTo(ns2Disks)); + assertFalse(ns.similarToIgnoringInitProgress(ns2Disks)); assertFalse(ns2Disks.similarTo(ns)); } } diff --git a/vdslib/src/tests/container/CMakeLists.txt b/vdslib/src/tests/container/CMakeLists.txt index 99717430c28..a869d0fd40b 100644 --- a/vdslib/src/tests/container/CMakeLists.txt +++ b/vdslib/src/tests/container/CMakeLists.txt @@ -5,9 +5,7 @@ vespa_add_library(vdslib_containertest parameterstest.cpp searchresulttest.cpp documentsummarytest.cpp - smallvectortest.cpp lruordertest.cpp - indexedcontaineriteratortest.cpp DEPENDS vdslib ) diff --git a/vdslib/src/tests/container/indexedcontaineriteratortest.cpp b/vdslib/src/tests/container/indexedcontaineriteratortest.cpp deleted file mode 100644 index a7697116a15..00000000000 --- a/vdslib/src/tests/container/indexedcontaineriteratortest.cpp +++ /dev/null @@ -1,61 +0,0 @@ -// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. - -#include <cppunit/extensions/HelperMacros.h> -#include <vespa/vdslib/container/smallvector.h> -#include <sys/time.h> - -namespace storage { -namespace lib { - -struct IndexedContainerIteratorTest : public CppUnit::TestFixture { - - void testNormalUsage(); - void testSorting(); - - CPPUNIT_TEST_SUITE(IndexedContainerIteratorTest); - CPPUNIT_TEST(testNormalUsage); - CPPUNIT_TEST(testSorting); - CPPUNIT_TEST_SUITE_END(); -}; - -CPPUNIT_TEST_SUITE_REGISTRATION(IndexedContainerIteratorTest); - -void -IndexedContainerIteratorTest::testNormalUsage() -{ - typedef IndexedContainerIterator<std::vector<int>, int> Iterator; - { - std::vector<int> v; - Iterator begin = Iterator(v, 0); - Iterator end = Iterator(v, 0); - CPPUNIT_ASSERT_EQUAL(begin, Iterator(v, 0)); - CPPUNIT_ASSERT_EQUAL(end, Iterator(v, 0)); - CPPUNIT_ASSERT(begin == end); - } - { - std::vector<int> v; - v.push_back(5); - Iterator begin = Iterator(v, 0); - Iterator end = Iterator(v, 1); - CPPUNIT_ASSERT_EQUAL(begin, Iterator(v, 0)); - CPPUNIT_ASSERT_EQUAL(end, Iterator(v, 1)); - CPPUNIT_ASSERT(begin != end); - } -} - -void -IndexedContainerIteratorTest::testSorting() -{ - typedef IndexedContainerIterator<std::vector<int>, int> Iterator; - std::vector<int> v; - v.push_back(5); - v.push_back(9); - v.push_back(2); - std::sort(Iterator(v, 0), Iterator(v, 3)); - CPPUNIT_ASSERT_EQUAL(2, v[0]); - CPPUNIT_ASSERT_EQUAL(5, v[1]); - CPPUNIT_ASSERT_EQUAL(9, v[2]); -} - -} // lib -} // storage diff --git a/vdslib/src/tests/container/smallvectortest.cpp b/vdslib/src/tests/container/smallvectortest.cpp deleted file mode 100644 index ac046f80caa..00000000000 --- a/vdslib/src/tests/container/smallvectortest.cpp +++ /dev/null @@ -1,274 +0,0 @@ -// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. - -#include <cppunit/extensions/HelperMacros.h> -#include <vespa/vdslib/container/smallvector.h> -#include <sys/time.h> - -namespace storage { -namespace lib { - -struct SmallVectorTest : public CppUnit::TestFixture { - - void testNormalUsage(); - void testPerformance(); - void testSwapVectorContents(); - void testErase(); - void testCopy(); - - CPPUNIT_TEST_SUITE(SmallVectorTest); - CPPUNIT_TEST(testNormalUsage); - CPPUNIT_TEST(testPerformance); - CPPUNIT_TEST(testSwapVectorContents); - CPPUNIT_TEST(testErase); - CPPUNIT_TEST(testCopy); - CPPUNIT_TEST_SUITE_END(); -}; - -CPPUNIT_TEST_SUITE_REGISTRATION(SmallVectorTest); - -namespace { - template<typename T> - inline std::ostream& operator<<(std::ostream& out, - const std::vector<T>& v) - { - out << "["; - for (size_t i=0; i<v.size(); ++i) { - out << "\n " << v[i]; - } - if (!v.empty()) out << "\n"; - out << "]"; - return out; - } - - template<typename T, size_t S> - void assertEqual(const SmallVector<T, S>& sv, const std::vector<T>& v) { - if (!(sv == v)) { - std::ostringstream ost; - ost << "Small vector " << sv << " is not equal to vector " << v; - CPPUNIT_FAIL(ost.str()); - } - } -} - -void -SmallVectorTest::testNormalUsage() -{ - std::vector<uint16_t> expected; - SmallVector<uint16_t, 8> actual; - for (uint16_t i=0; i<16; ++i) { - expected.push_back(i); - actual.push_back(i); - assertEqual(actual, expected); - } - - SmallVector<uint16_t, 8> copy(actual); - SmallVector<uint16_t, 16> copy2(actual); -} - -namespace { - - uint64_t getCurrentTimeInMicros() { - struct timeval mytime; - gettimeofday(&mytime, 0); - return mytime.tv_sec * 1000000llu + mytime.tv_usec; - } - - template<typename IntContainer> - struct PerformanceTestClass { - uint32_t count; - - PerformanceTestClass(int c) : count(c) {} - - IntContainer getContainer(int minVal) { - IntContainer result; - for (uint32_t i=0; i<count; ++i) { - result.push_back(minVal + i); - } - return result; - } - }; - - template<typename IntContainer> - uint64_t getPerformance(int containerSize) { - uint64_t start = getCurrentTimeInMicros(); - int value = 0; - PerformanceTestClass<IntContainer> foo(containerSize); - for (uint32_t i=0, n=10 * 1024; i<n; ++i) { - IntContainer ic(foo.getContainer(start)); - value += ic[0] + ic[1] - ic[2]; - } - uint64_t stop = getCurrentTimeInMicros(); - return (stop - start); - } - - struct ArgumentTestClass { - uint32_t count; - - ArgumentTestClass(int c) : count(c) {} - - void getContainer(int minVal, std::vector<int>& result) { - for (uint32_t i=0; i<count; ++i) { - result.push_back(minVal + i); - } - } - }; - - uint64_t getPerformance2(int containerSize) { - uint64_t start = getCurrentTimeInMicros(); - int value = 0; - ArgumentTestClass foo(containerSize); - for (uint32_t i=0, n=10 * 1024; i<n; ++i) { - std::vector<int> ic; - foo.getContainer(start, ic); - value += ic[0] + ic[1] - ic[2]; - } - uint64_t stop = getCurrentTimeInMicros(); - return (stop - start); - } -} - -void -SmallVectorTest::testPerformance() -{ - size_t low = 3; - size_t high = 16; - SmallVector<int> sv; - - CPPUNIT_ASSERT(low <= sv.getEfficientSizeLimit()); - CPPUNIT_ASSERT(high > sv.getEfficientSizeLimit()); - - uint64_t vectorTime1 = getPerformance<std::vector<int> >(low); - uint64_t smallVectorTime1 = getPerformance<SmallVector<int> >(low); - uint64_t asArgTime1 = getPerformance2(low); - - uint64_t vectorTime2 = getPerformance<std::vector<int> >(high); - uint64_t smallVectorTime2 = getPerformance<SmallVector<int> >(high); - uint64_t asArgTime2 = getPerformance2(high); - - double factor1 = static_cast<double>(vectorTime1) / smallVectorTime1; - double factor2 = static_cast<double>(vectorTime2) / smallVectorTime2; - - double factor3 = static_cast<double>(asArgTime1) / smallVectorTime1; - double factor4 = static_cast<double>(asArgTime2) / smallVectorTime2; - - std::cerr << "\n" - << " Small vector is " << factor1 - << " x faster than std::vector with few elements\n" - << " Small vector is " << factor2 - << " x faster than std::vector with many elements\n" - << " Small vector is " << factor3 - << " x faster than std::vector as arg with few elements\n" - << " Small vector is " << factor4 - << " x faster than std::vector as arg with many elements\n"; - - // At time of test writing, vector is ~43 times faster with small data, and - // ~0.9 times as fast on bigger. (Without vespa malloc) - // With vespa malloc it is about ~14 times faster. - - /* Cannot run on factory as too much other runs in parallel. - CPPUNIT_ASSERT(factor1 > 25); - CPPUNIT_ASSERT(factor2 > 0.5); - // */ -} - -void -SmallVectorTest::testSwapVectorContents() -{ - SmallVector<uint16_t, 8> v1; - SmallVector<uint16_t, 8> v2; - - // v1 small enough to be contained in fixed array. - for (uint16_t i = 0; i < 6; ++i) { - v1.push_back(i); - } - - // v2 big enough that it needs heap backed storage. - for (uint16_t i = 10; i < 30; ++i) { - v2.push_back(i); - } - - vespalib::string expectedSmall("[0, 1, 2, 3, 4, 5]"); - vespalib::string expectedBig("[10, 11, 12, 13, 14, 15, 16, 17, 18, 19, " - "20, 21, 22, 23, 24, 25, 26, 27, 28, 29]"); - - v1.swap(v2); - - CPPUNIT_ASSERT_EQUAL(expectedSmall, v2.toString()); - CPPUNIT_ASSERT_EQUAL(expectedBig, v1.toString()); - - swap(v1, v2); - CPPUNIT_ASSERT_EQUAL(expectedBig, v2.toString()); - CPPUNIT_ASSERT_EQUAL(expectedSmall, v1.toString()); -} - -void -SmallVectorTest::testErase() -{ - // Delete in small part of small array - { - SmallVector<uint16_t, 4> v = {3, 6, 5}; - v.erase(v.begin()); - CPPUNIT_ASSERT_EQUAL((SmallVector<uint16_t, 4>{6, 5}), v); - } - { - SmallVector<uint16_t, 4> v = {3, 6, 5}; - v.erase(v.begin() + 1); - CPPUNIT_ASSERT_EQUAL((SmallVector<uint16_t, 4>{3, 5}), v); - } - { - SmallVector<uint16_t, 4> v = {3, 6, 5}; - v.erase(v.begin() + 2); - CPPUNIT_ASSERT_EQUAL((SmallVector<uint16_t, 4>{3, 6}), v); - } - - // Delete in small part of large array - { - SmallVector<uint16_t, 4> v = {3, 6, 5, 7, 8}; - v.erase(v.begin()); - CPPUNIT_ASSERT_EQUAL((SmallVector<uint16_t, 4>{6, 5, 7, 8}), v); - } - { - SmallVector<uint16_t, 4> v = {3, 6, 5, 7, 8}; - v.erase(v.begin() + 1); - CPPUNIT_ASSERT_EQUAL((SmallVector<uint16_t, 4>{3, 5, 7, 8}), v); - } - { - SmallVector<uint16_t, 4> v = {3, 6, 5, 7, 8}; - v.erase(v.begin() + 2); - CPPUNIT_ASSERT_EQUAL((SmallVector<uint16_t, 4>{3, 6, 7, 8}), v); - } - - // Delete in extended part of small array - { - SmallVector<uint16_t, 1> v = {3, 6, 5}; - v.erase(v.begin()); - CPPUNIT_ASSERT_EQUAL((SmallVector<uint16_t, 1>{6, 5}), v); - } - { - SmallVector<uint16_t, 1> v = {3, 6, 5}; - v.erase(v.begin() + 1); - CPPUNIT_ASSERT_EQUAL((SmallVector<uint16_t, 1>{3, 5}), v); - } - { - SmallVector<uint16_t, 1> v = {3, 6, 5}; - v.erase(v.begin() + 2); - CPPUNIT_ASSERT_EQUAL((SmallVector<uint16_t, 1>{3, 6}), v); - } -} - -namespace { - void foo(const SmallVector<uint16_t, 4>&) { - } -} - -void -SmallVectorTest::testCopy() -{ - foo(SmallVector<uint16_t, 4>{3, 2}); - SmallVector<uint16_t, 4> v{1, 2, 3}; - foo(v); - foo({}); -} - -} // lib -} // storage diff --git a/vdslib/src/tests/distribution/CMakeLists.txt b/vdslib/src/tests/distribution/CMakeLists.txt index a82cb3ddec1..e4197920add 100644 --- a/vdslib/src/tests/distribution/CMakeLists.txt +++ b/vdslib/src/tests/distribution/CMakeLists.txt @@ -4,7 +4,6 @@ vespa_add_library(vdslib_testdistribution distributiontest.cpp grouptest.cpp idealnodecalculatorimpltest.cpp - idealnodecalculatorcachetest.cpp DEPENDS vdslib ) diff --git a/vdslib/src/tests/distribution/distributiontest.cpp b/vdslib/src/tests/distribution/distributiontest.cpp index 664c50a3fc9..be93ec614cf 100644 --- a/vdslib/src/tests/distribution/distributiontest.cpp +++ b/vdslib/src/tests/distribution/distributiontest.cpp @@ -3,7 +3,6 @@ #include <vespa/fastos/fastos.h> #include <vespa/vdslib/distribution/distribution.h> #include <vespa/vdslib/distribution/idealnodecalculator.h> -#include <boost/assign.hpp> #include <vespa/config/helper/configfetcher.h> #include <cmath> #include <chrono> @@ -1453,38 +1452,28 @@ DistributionTest::testActivePerGroup() void DistributionTest::testHierarchicalDistributeLessThanRedundancy() { - using namespace boost::assign; - Distribution distr("redundancy 4\n" - "active_per_leaf_group true\n" + groupConfig); + Distribution distr("redundancy 4\nactive_per_leaf_group true\n" + groupConfig); ClusterState state("storage:6"); std::vector<uint16_t> actual; { - distr.getIdealNodes(NodeType::STORAGE, state, document::BucketId(16, 0), - actual, "uim", 4); - std::vector<uint16_t> expected; - expected += 3, 5, 1, 2; + distr.getIdealNodes(NodeType::STORAGE, state, document::BucketId(16, 0), actual, "uim", 4); + std::vector<uint16_t> expected({3, 5, 1, 2}); CPPUNIT_ASSERT_EQUAL(expected, actual); } { - distr.getIdealNodes(NodeType::STORAGE, state, document::BucketId(16, 0), - actual, "uim", 3); - std::vector<uint16_t> expected; - expected += 3, 5, 1; + distr.getIdealNodes(NodeType::STORAGE, state, document::BucketId(16, 0), actual, "uim", 3); + std::vector<uint16_t> expected({3, 5, 1}); CPPUNIT_ASSERT_EQUAL(expected, actual); } { - distr.getIdealNodes(NodeType::STORAGE, state, document::BucketId(16, 0), - actual, "uim", 2); - std::vector<uint16_t> expected; - expected += 3, 1; + distr.getIdealNodes(NodeType::STORAGE, state, document::BucketId(16, 0), actual, "uim", 2); + std::vector<uint16_t> expected({3, 1}); CPPUNIT_ASSERT_EQUAL(expected, actual); } { - distr.getIdealNodes(NodeType::STORAGE, state, document::BucketId(16, 0), - actual, "uim", 1); - std::vector<uint16_t> expected; - expected += 3; + distr.getIdealNodes(NodeType::STORAGE, state, document::BucketId(16, 0), actual, "uim", 1); + std::vector<uint16_t> expected({3}); CPPUNIT_ASSERT_EQUAL(expected, actual); } } diff --git a/vdslib/src/tests/distribution/grouptest.cpp b/vdslib/src/tests/distribution/grouptest.cpp index 828a00ff7d0..b182c19d072 100644 --- a/vdslib/src/tests/distribution/grouptest.cpp +++ b/vdslib/src/tests/distribution/grouptest.cpp @@ -3,7 +3,6 @@ #include <vespa/fastos/fastos.h> #include <vespa/vdslib/distribution/group.h> -#include <boost/assign.hpp> #include <vespa/vespalib/text/stringtokenizer.h> #include <vespa/vdstestlib/cppunit/macros.h> diff --git a/vdslib/src/tests/distribution/idealnodecalculatorcachetest.cpp b/vdslib/src/tests/distribution/idealnodecalculatorcachetest.cpp deleted file mode 100644 index 8195d6dd070..00000000000 --- a/vdslib/src/tests/distribution/idealnodecalculatorcachetest.cpp +++ /dev/null @@ -1,331 +0,0 @@ -// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. - -#include <vespa/vdslib/distribution/idealnodecalculatorcache.h> -#include <vespa/vdslib/distribution/idealnodecalculatorimpl.h> -#include <vespa/vdstestlib/cppunit/macros.h> - -namespace storage { -namespace lib { - -struct IdealNodeCalculatorCacheTest : public CppUnit::TestFixture { - - /** Test that you get a correct result forwarded through simple. */ - void testSimple(); - /** Test that similar buckets use different cache slots. */ - void testLocalityCached(); - /** Test that buckets using same cache slot invalidates each other. */ - void testBucketsSameCacheSlot(); - /** Test that cache is invalidated on changes. */ - void testCacheInvalidationOnChanges(); - /** Test that values for different upstates are kept for themselves. */ - void testDifferentUpStates(); - /** Test that values for different node types are kept for themselves. */ - void testDifferentNodeTypes(); - /** - * Do a performance test, verifying that cache actually significantly - * increase performance. - */ - void testPerformance(); - - CPPUNIT_TEST_SUITE(IdealNodeCalculatorCacheTest); - CPPUNIT_TEST(testSimple); - CPPUNIT_TEST(testLocalityCached); - CPPUNIT_TEST(testBucketsSameCacheSlot); - CPPUNIT_TEST(testCacheInvalidationOnChanges); - CPPUNIT_TEST(testDifferentUpStates); - CPPUNIT_TEST(testDifferentNodeTypes); - CPPUNIT_TEST(testPerformance); - CPPUNIT_TEST_SUITE_END(); -}; - -CPPUNIT_TEST_SUITE_REGISTRATION(IdealNodeCalculatorCacheTest); - -void -IdealNodeCalculatorCacheTest::testSimple() -{ - ClusterState state("storage:10"); - Distribution distr(Distribution::getDefaultDistributionConfig(3, 10)); - IdealNodeCalculatorImpl::SP impl(new IdealNodeCalculatorImpl); - IdealNodeCalculatorCache cache(impl, 4); - - IdealNodeCalculatorConfigurable& configurable(cache); - IdealNodeCalculator& calc(cache); - configurable.setDistribution(distr); - configurable.setClusterState(state); - - std::string expected("[storage.8, storage.9, storage.6]"); - CPPUNIT_ASSERT_EQUAL( - expected, - calc.getIdealStorageNodes(document::BucketId(16, 5)).toString()); -} - -void -IdealNodeCalculatorCacheTest::testLocalityCached() -{ - ClusterState state("bits:6 storage:10"); - Distribution distr(Distribution::getDefaultDistributionConfig(3, 10)); - IdealNodeCalculatorImpl::SP impl(new IdealNodeCalculatorImpl); - IdealNodeCalculatorCache cache(impl, 1024); - - IdealNodeCalculatorConfigurable& configurable(cache); - IdealNodeCalculator& calc(cache); - configurable.setDistribution(distr); - configurable.setClusterState(state); - - std::vector<document::BucketId> local; - local.push_back(document::BucketId(15, 134)); - local.push_back(document::BucketId(16, 134)); - local.push_back(document::BucketId(17, 134)); - local.push_back(document::BucketId(17, 134 | (1 << 16))); - - for (uint32_t i=0; i<local.size(); ++i) { - calc.getIdealStorageNodes(local[i]); - } - - CPPUNIT_ASSERT_EQUAL(4u, cache.getMissCount()); - CPPUNIT_ASSERT_EQUAL(0u, cache.getHitCount()); - - for (uint32_t i=0; i<local.size(); ++i) { - calc.getIdealStorageNodes(local[i]); - } - - CPPUNIT_ASSERT_EQUAL(4u, cache.getMissCount()); - CPPUNIT_ASSERT_EQUAL(4u, cache.getHitCount()); -} - -void -IdealNodeCalculatorCacheTest::testBucketsSameCacheSlot() -{ - ClusterState state("bits:6 storage:10"); - Distribution distr(Distribution::getDefaultDistributionConfig(3, 10)); - IdealNodeCalculatorImpl::SP impl(new IdealNodeCalculatorImpl); - IdealNodeCalculatorCache cache(impl, 1); // Only one slot available - - IdealNodeCalculatorConfigurable& configurable(cache); - IdealNodeCalculator& calc(cache); - configurable.setDistribution(distr); - configurable.setClusterState(state); - - // See that you don't get same result as last one - std::string expected("[storage.8, storage.9, storage.6]"); - CPPUNIT_ASSERT_EQUAL( - expected, - calc.getIdealStorageNodes(document::BucketId(16, 5)).toString()); - expected = "[storage.8, storage.6, storage.1]"; - CPPUNIT_ASSERT_EQUAL( - expected, - calc.getIdealStorageNodes(document::BucketId(16, 6)).toString()); -} - -void -IdealNodeCalculatorCacheTest::testCacheInvalidationOnChanges() -{ - ClusterState state("bits:6 storage:10"); - Distribution distr(Distribution::getDefaultDistributionConfig(3, 10)); - IdealNodeCalculatorImpl::SP impl(new IdealNodeCalculatorImpl); - IdealNodeCalculatorCache cache(impl, 1); // Only one slot available - - IdealNodeCalculatorConfigurable& configurable(cache); - IdealNodeCalculator& calc(cache); - configurable.setDistribution(distr); - configurable.setClusterState(state); - - // See that you don't get same result as last one - std::string expected("[storage.8, storage.9, storage.6]"); - CPPUNIT_ASSERT_EQUAL( - expected, - calc.getIdealStorageNodes(document::BucketId(16, 5)).toString()); - - CPPUNIT_ASSERT_EQUAL(1u, cache.getMissCount()); - CPPUNIT_ASSERT_EQUAL(0u, cache.getHitCount()); - - configurable.setClusterState(state); - - CPPUNIT_ASSERT_EQUAL( - expected, - calc.getIdealStorageNodes(document::BucketId(16, 5)).toString()); - - CPPUNIT_ASSERT_EQUAL(2u, cache.getMissCount()); - CPPUNIT_ASSERT_EQUAL(0u, cache.getHitCount()); - - configurable.setDistribution(distr); - - CPPUNIT_ASSERT_EQUAL( - expected, - calc.getIdealStorageNodes(document::BucketId(16, 5)).toString()); - - CPPUNIT_ASSERT_EQUAL(3u, cache.getMissCount()); - CPPUNIT_ASSERT_EQUAL(0u, cache.getHitCount()); -} - -void -IdealNodeCalculatorCacheTest::testDifferentUpStates() -{ - ClusterState state("bits:6 storage:10 .6.s:m .8.s:r"); - Distribution distr(Distribution::getDefaultDistributionConfig(3, 10)); - IdealNodeCalculatorImpl::SP impl(new IdealNodeCalculatorImpl); - IdealNodeCalculatorCache cache(impl, 4); - - IdealNodeCalculatorConfigurable& configurable(cache); - IdealNodeCalculator& calc(cache); - configurable.setDistribution(distr); - configurable.setClusterState(state); - - std::string expected("[storage.9, storage.4, storage.1]"); - CPPUNIT_ASSERT_EQUAL( - expected, - calc.getIdealStorageNodes(document::BucketId(16, 5), - IdealNodeCalculator::UpInit).toString()); - - expected = "[storage.9, storage.6, storage.4]"; - CPPUNIT_ASSERT_EQUAL( - expected, - calc.getIdealStorageNodes( - document::BucketId(16, 5), - IdealNodeCalculator::UpInitMaintenance).toString()); -} - -void -IdealNodeCalculatorCacheTest::testDifferentNodeTypes() -{ - ClusterState state("bits:6 distributor:10 storage:10 .6.s:m .8.s:r"); - Distribution distr(Distribution::getDefaultDistributionConfig(3, 10)); - IdealNodeCalculatorImpl::SP impl(new IdealNodeCalculatorImpl); - IdealNodeCalculatorCache cache(impl, 4); - - IdealNodeCalculatorConfigurable& configurable(cache); - IdealNodeCalculator& calc(cache); - configurable.setDistribution(distr); - configurable.setClusterState(state); - - std::string expected("[storage.9, storage.4, storage.1]"); - CPPUNIT_ASSERT_EQUAL( - expected, - calc.getIdealStorageNodes(document::BucketId(16, 5)).toString()); - - expected = "[distributor.8]"; - CPPUNIT_ASSERT_EQUAL( - expected, - calc.getIdealDistributorNodes( - document::BucketId(16, 5)).toString()); -} - -namespace { - - uint64_t getCurrentTimeInMicros() { - struct timeval mytime; - gettimeofday(&mytime, 0); - return mytime.tv_sec * 1000000llu + mytime.tv_usec; - } - - void addBucketTree(std::vector<document::BucketId>& v, - uint64_t location, - uint32_t currentUsedBits, - uint32_t maxUsedBits) - { - document::BucketId id(currentUsedBits, location); - v.push_back(id); - if (currentUsedBits < maxUsedBits) { - addBucketTree(v, location, - currentUsedBits + 1, maxUsedBits); - addBucketTree(v, location | (uint64_t(1) << currentUsedBits), - currentUsedBits + 1, maxUsedBits); - } - } - - uint64_t runPerformanceTest(IdealNodeCalculator& calc) { - std::vector<document::BucketId> buckets; - - // Addvarious location split levels for a user - addBucketTree(buckets, 123, 20, 22); - // Add various gid bit split levels for a user - addBucketTree(buckets, 123, 40, 42); - - { - std::set<document::BucketId> uniqueBuckets; - for (uint32_t i=0; i<buckets.size(); ++i) { - uniqueBuckets.insert(buckets[i]); - calc.getIdealStorageNodes(buckets[i]); - } - CPPUNIT_ASSERT_EQUAL(buckets.size(), uniqueBuckets.size()); - CPPUNIT_ASSERT_EQUAL(size_t(14), buckets.size()); - } - IdealNodeCalculatorCache* cache(dynamic_cast<IdealNodeCalculatorCache*>( - &calc)); - if (cache != 0) cache->clearCounts(); - uint32_t value; - uint64_t start = getCurrentTimeInMicros(); - for (uint32_t j=0; j<1024; ++j) { - for (uint32_t i=0; i<buckets.size(); ++i) { - IdealNodeList result(calc.getIdealStorageNodes(buckets[i])); - value += (result[0].getIndex() + result[1].getIndex()) - / result[2].getIndex(); - } - } - uint64_t stop = getCurrentTimeInMicros(); - return (stop - start); - } - - struct MapIdealNodeCalculator : public IdealNodeCalculator { - mutable std::map<document::BucketId, IdealNodeList> values; - const IdealNodeCalculator& calc; - - MapIdealNodeCalculator(const IdealNodeCalculator& c) : calc(c) {} - - virtual IdealNodeList getIdealNodes(const NodeType& nodeType, - const document::BucketId& bucketId, - UpStates upStates) const - { - std::map<document::BucketId, IdealNodeList>::const_iterator it( - values.find(bucketId)); - if (it != values.end()) return it->second; - IdealNodeList result( - calc.getIdealNodes(nodeType, bucketId, upStates)); - values[bucketId] = result; - return result; - } - }; -} - -void -IdealNodeCalculatorCacheTest::testPerformance() -{ - ClusterState state("bits:18 distributor:100 storage:100 .6.s:m .8.s:r"); - Distribution distr(Distribution::getDefaultDistributionConfig(3, 100)); - IdealNodeCalculatorImpl::SP impl(new IdealNodeCalculatorImpl); - impl->setDistribution(distr); - impl->setClusterState(state); - - uint64_t rawPerformance = runPerformanceTest(*impl); - - IdealNodeCalculatorCache cache(impl, 14); - - uint64_t cachePerformance = runPerformanceTest(cache); - double hitrate = (100.0 * cache.getHitCount() - / (cache.getHitCount() + cache.getMissCount())); - CPPUNIT_ASSERT(hitrate > 99.99); - - MapIdealNodeCalculator mapCalc(*impl); - - uint64_t mapPerformance = runPerformanceTest(mapCalc); - - IdealNodeCalculatorCache cache2(impl, 13); - uint64_t cacheMissPerformance = runPerformanceTest(cache2); - double hitrate2 = (100.0 * cache2.getHitCount() - / (cache2.getHitCount() + cache2.getMissCount())); - CPPUNIT_ASSERT(hitrate2 < 0.01); - - std::cerr << "\n" - << " Cache is " - << (static_cast<double>(rawPerformance) / cachePerformance) - << " x faster than skipping cache with 100% hitrate\n" - << " Cache is " - << (static_cast<double>(mapPerformance) / cachePerformance) - << " x faster than std::map cache with all data\n" - << " Cache is " - << (static_cast<double>(rawPerformance) / cacheMissPerformance) - << " x faster than skipping cache with 0% hitrate\n"; -} - -} // lib -} // storage diff --git a/vdslib/src/vespa/vdslib/container/smallvector.h b/vdslib/src/vespa/vdslib/container/smallvector.h deleted file mode 100644 index cd6636536c7..00000000000 --- a/vdslib/src/vespa/vdslib/container/smallvector.h +++ /dev/null @@ -1,294 +0,0 @@ -// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -/** - * A vector type implementation that is optimized for keeping a small amount of - * elements. If a small amount is kept, no malloc will be done within the - * vector implementation. - */ - -#pragma once - -#include <boost/array.hpp> -#include <vespa/fastos/fastos.h> -#include <iterator> -#include <memory> -#include <vector> -#include <vespa/vespalib/util/printable.h> - -namespace storage { -namespace lib { - -/** - * A generic iterator implementation using size() and operator[] to access - * elements. - */ -template<typename Container, typename T> -class IndexedContainerIterator - : public std::iterator<std::random_access_iterator_tag, T>, - public vespalib::AsciiPrintable -{ - Container* _container; - uint64_t _index; - -public: - typedef IndexedContainerIterator<Container, T> Iterator; - typedef typename std::iterator<std::random_access_iterator_tag, T>::difference_type difference_type; - // Required to be possible to default construct iterators - IndexedContainerIterator() : _container(0), _index(-1) {} - IndexedContainerIterator(Container& c, uint64_t index) - : _container(&c), _index(index) {} - - T& operator*() { return (*_container)[_index]; } - T* operator->() { return &(*_container)[_index]; } - bool operator==(const Iterator& o) const { - return (_index == o._index); - } - bool operator!=(const Iterator& o) const { - return (_index != o._index); - } - bool operator<(const Iterator& o) const { - return (_index < o._index); - } - - Iterator& operator++() { - ++_index; - return *this; - } - Iterator operator++(int) { - return Iterator(*_container, _index++); - } - Iterator& operator--() { - --_index; - return *this; - } - Iterator operator--(int) { - return Iterator(*_container, _index--); - } - - Iterator operator+(const difference_type& v) { - return Iterator(*_container, _index + v); - } - difference_type operator+(const Iterator& o) { - return _index + o._index; - } - Iterator operator-(const difference_type& v) { - return Iterator(*_container, _index - v); - } - difference_type operator-(const Iterator& o) { - return _index - o._index; - } - - void print(vespalib::asciistream& out, const PrintProperties& p) const - { - out << "Iterator."; - if (_index >= _container->size()) { - out << "end"; - } else { - out << _index; - if (p.verbose()) { - out << "(" << (*_container)[_index] << ")"; - } - } - } -}; - -template <typename T, size_t S = 8> -class SmallVector : public vespalib::AsciiPrintable { - size_t _size; - boost::array<T, S> _smallVector; - mutable std::unique_ptr< std::vector<T> > _bigVector; - -public: - typedef IndexedContainerIterator<SmallVector<T, S>, T> iterator; - typedef IndexedContainerIterator<const SmallVector<T, S>, const T> - const_iterator; - typedef T value_type; - typedef T& reference; - typedef const T& const_reference; - typedef size_t difference_type; - typedef size_t size_type; - - iterator begin() { return iterator(*this, 0); } - iterator end() { return iterator(*this, _size); } - const_iterator begin() const { return const_iterator(*this, 0); } - const_iterator end() const { return const_iterator(*this, _size); } - - SmallVector() : _size(0) {} - - SmallVector(std::initializer_list<T> elems) - : _size(0) - { - for (auto it=elems.begin(); it != elems.end(); ++it) { - push_back(*it); - } - } - - /** Copy needs to be efficient. That's the whole basis for this class. */ - SmallVector(const SmallVector<T, S>& other) { - operator=(other); - } - SmallVector<T, S>& operator=(const SmallVector<T, S>& other) { - _size = other.size(); - _smallVector = other._smallVector; - if (other._bigVector.get() != 0) { - _bigVector.reset(new std::vector<T>()); - *_bigVector = *other._bigVector; - } else { - _bigVector.reset(); - } - return *this; - } - - template<size_t S2> - SmallVector(const SmallVector<T, S2>& other) { - operator=(other); - } - template<size_t S2> - SmallVector<T, S>& operator=(const SmallVector<T, S2>& other) { - clear(); - for (uint32_t i=0, n=other.size(); i<n; ++i) { - push_back(other[i]); - } - return *this; - } - - size_t getEfficientSizeLimit() const { return S; } - - void push_back(const T& t) { - if (_size < S) { - _smallVector[_size] = t; - ++_size; - } else { - if (_size == S && _bigVector.get() == 0) { - populateVector(); - } - _bigVector->push_back(t); - ++_size; - } - } - void pop_back() { - if (_size <= S) { - --_size; - } else { - if (--_size == S) { - _bigVector.reset(); - } else { - _bigVector->pop_back(); - } - } - } - const T& back() const { return operator[](_size - 1); } - T& back() { return operator[](_size - 1); } - const T& front() const { return operator[](0); } - T& front() { return operator[](0); } - void clear() { - _size = 0; - _bigVector.reset(0); - } - const T& operator[](size_t i) const { - if (i < S) { - return _smallVector[i]; - } else { - return (*_bigVector)[i]; - } - } - T& operator[](size_t i) { - if (i < S) { - return _smallVector[i]; - } else { - return (*_bigVector)[i]; - } - } - bool empty() const { return (_size == 0); } - size_t size() const { return _size; } - - std::vector<T> getVector() const { - std::vector<T> result; - if (_bigVector.get() == 0) { - for (size_t i=0; i<_size; ++i) { - result.push_back(_smallVector[i]); - } - } else { - result = *_bigVector; - } - return *_bigVector; - } - - template<typename O> - bool operator==(const O& o) const { - if (size() != o.size()) return false; - for (size_t i=0; i<_size; ++i) { - if ((*this)[i] != o[i]) return false; - } - return true; - } - template<typename O> - bool operator!=(const O& o) const { - return !(operator==(o)); - } - - void swap(SmallVector<T, S>& other) { - // Move current into temporaries - size_t copySize(_size); - boost::array<T, S> copySmall(_smallVector); - std::unique_ptr< std::vector<T> > copyBig(std::move(_bigVector)); - // Overwrite current with other - _size = other._size; - _smallVector = other._smallVector; - _bigVector = std::move(other._bigVector); - // Overwrite other with temporaries - other._size = copySize; - other._smallVector = copySmall; - other._bigVector = std::move(copyBig); - } - - void print(vespalib::asciistream& out, const PrintProperties& p) const { - if (_size == 0) { - out << "[]"; - return; - } - vespalib::asciistream ost; - ost << operator[](0); - bool newLineBetweenEntries = (ost.str().size() > 15); - out << "["; - for (size_t i=0; i<_size; ++i) { - if (i != 0) out << ","; - if (newLineBetweenEntries) { - out << "\n" << p.indent(1); - } else { - if (i != 0) { out << " "; } - } - out << operator[](i); - } - if (newLineBetweenEntries) { - out << "\n" << p.indent(); - } - out << "]"; - } - void erase(iterator eraseIt) { - SmallVector<T, S> copy; - for (auto it = begin(); it != end(); ++it) { - if (it != eraseIt) { - copy.push_back(*it); - } - } - copy.swap(*this); - } - -private: - void populateVector() const { - assert(_bigVector.get() == 0 && _size == S); - _bigVector.reset(new std::vector<T>()); - for (size_t i=0; i<S; ++i) { - _bigVector->push_back(_smallVector[i]); - } - } -}; - -template <typename T, size_t S> -void -swap(SmallVector<T, S>& v1, SmallVector<T, S>& v2) { - v1.swap(v2); -} - -} // lib -} // storage diff --git a/vdslib/src/vespa/vdslib/distribution/group.cpp b/vdslib/src/vespa/vdslib/distribution/group.cpp index f4f94fefe0b..0ffe937a949 100644 --- a/vdslib/src/vespa/vdslib/distribution/group.cpp +++ b/vdslib/src/vespa/vdslib/distribution/group.cpp @@ -5,7 +5,6 @@ #include <vespa/vdslib/state/random.h> #include <vespa/vespalib/util/exceptions.h> -#include <boost/lexical_cast.hpp> #include <algorithm> namespace storage { diff --git a/vdslib/src/vespa/vdslib/distribution/group.h b/vdslib/src/vespa/vdslib/distribution/group.h index 138a466a856..d4952941dbd 100644 --- a/vdslib/src/vespa/vdslib/distribution/group.h +++ b/vdslib/src/vespa/vdslib/distribution/group.h @@ -11,7 +11,6 @@ */ #pragma once -#include <boost/operators.hpp> #include <map> #include <vector> #include <vespa/vespalib/objects/floatingpointtype.h> @@ -26,7 +25,7 @@ namespace lib { class IdealGroup; class SystemState; -class Group : public document::Printable, public boost::operators<Group> +class Group : public document::Printable { public: typedef std::unique_ptr<Group> UP; diff --git a/vdslib/src/vespa/vdslib/distribution/idealnodecalculator.h b/vdslib/src/vespa/vdslib/distribution/idealnodecalculator.h index 7bab3ff4af4..2f43907801e 100644 --- a/vdslib/src/vespa/vdslib/distribution/idealnodecalculator.h +++ b/vdslib/src/vespa/vdslib/distribution/idealnodecalculator.h @@ -7,7 +7,6 @@ #pragma once #include <vespa/document/bucket/bucketid.h> -#include <vespa/vdslib/container/smallvector.h> #include <vespa/vdslib/state/clusterstate.h> #include <vespa/vdslib/distribution/distribution.h> #include <vespa/vdslib/state/nodetype.h> @@ -20,7 +19,7 @@ namespace lib { * unneeded details, and make it easily printable. */ class IdealNodeList : public document::Printable { - SmallVector<Node> _idealNodes; + std::vector<Node> _idealNodes; public: IdealNodeList() : _idealNodes() {} diff --git a/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorcache.h b/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorcache.h deleted file mode 100644 index 54ffba869bd..00000000000 --- a/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorcache.h +++ /dev/null @@ -1,162 +0,0 @@ -// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -/** - * A cache for an ideal nodes implementation. - * - * The cache is localized for quick, localized access. - * - There is only one spot one request can be cached, so one can quickly - * look whether there is a cache entry on that spot. - * - Use LSB bits of bucket to lookup entry such that localized entries use - * separate cache spots. - * - * - * Making it cheap for localized - * access, regardless of real implementation. Basically, uses LSB bits for - * buckets, as these are the bits that differ on localized access. - */ -#pragma once - -#include <vespa/vdslib/container/lruorder.h> -#include <vespa/vdslib/distribution/idealnodecalculator.h> -#include <vespa/vespalib/stllike/hash_map.h> -#include <vespa/vespalib/util/linkedptr.h> - -namespace storage { -namespace lib { - -class IdealNodeCalculatorCache : public IdealNodeCalculatorConfigurable { - typedef document::BucketId BucketId; - - /** Cache for all buckets for one given type (same upstate and nodetypes) */ - class TypeCache { - struct Entry { - IdealNodeList _result; - LruOrder<BucketId, TypeCache>::EntryRef _order; - }; - typedef vespalib::hash_map<BucketId, Entry, BucketId::hash> EntryMap; - - const IdealNodeCalculator& _calc; - const NodeType& _nodeType; - UpStates _upStates; - LruOrder<BucketId, TypeCache> _order; - EntryMap _entries; - uint32_t _hitCount; - uint32_t _missCount; - public: - typedef vespalib::LinkedPtr<TypeCache> LP; - - TypeCache(const IdealNodeCalculator& c, const NodeType& t, - UpStates us, uint32_t size) - : _calc(c), _nodeType(t), _upStates(us), _order(size, *this), - _hitCount(0), _missCount(0) {} - - IdealNodeList get(const document::BucketId& bucket) { - EntryMap::const_iterator it(_entries.find(bucket)); - if (it == _entries.end()) { - ++_missCount; - Entry& newEntry(_entries[bucket]); - newEntry._result = _calc.getIdealNodes( - _nodeType, bucket, _upStates); - newEntry._order = _order.add(bucket); - return newEntry._result; - } else { - ++_hitCount; - _order.moveToStart(it->second._order); - return it->second._result; - } - } - - void removedFromOrder(const BucketId& bucket) { - _entries.erase(bucket); - } - - void clearCache() { - _entries.clear(); - _order.clear(); - } - - uint32_t getHitCount() const { return _hitCount; } - uint32_t getMissCount() const { return _missCount; } - void clearCounts() { - _hitCount = 0; - _missCount = 0; - } - }; - IdealNodeCalculatorConfigurable::SP _calculator; - std::vector<TypeCache::LP> _cache; - -public: - IdealNodeCalculatorCache(IdealNodeCalculatorConfigurable::SP calc, - uint32_t cacheSizePerUpTypeCache) - : _calculator(calc) - { - initCache(cacheSizePerUpTypeCache, *calc); - } - - virtual void setDistribution(const Distribution& d) { - clearCache(); - _calculator->setDistribution(d); - } - - virtual void setClusterState(const ClusterState& cs) { - clearCache(); - _calculator->setClusterState(cs); - } - - virtual IdealNodeList getIdealNodes(const NodeType& nodeType, - const document::BucketId& bucket, - UpStates upStates) const - { - uint16_t requestType(getCacheType(nodeType, upStates)); - return _cache[requestType]->get(bucket); - } - - uint32_t getHitCount() const { - uint32_t count = 0; - for (uint32_t i=0; i<_cache.size(); ++i) { - count += _cache[i]->getHitCount(); - } - return count; - } - - uint32_t getMissCount() const { - uint32_t count = 0; - for (uint32_t i=0; i<_cache.size(); ++i) { - count += _cache[i]->getMissCount(); - } - return count; - } - - void clearCounts() { - for (uint32_t i=0; i<_cache.size(); ++i) { - _cache[i]->clearCounts(); - } - } - -private: - void clearCache() { - for (size_t i=0; i<_cache.size(); ++i) { - _cache[i]->clearCache(); - } - } - - void initCache(uint32_t size, IdealNodeCalculator& calc) { - _cache.resize(2 * UP_STATE_COUNT); - for (uint32_t i=0; i<2; ++i) { - const NodeType& nt(i == 0 ? NodeType::DISTRIBUTOR - : NodeType::STORAGE); - for (uint32_t j=0; j<UP_STATE_COUNT; ++j) { - UpStates upStates = (UpStates) j; - uint16_t type = getCacheType(nt, upStates); - _cache[type].reset(new TypeCache(calc, nt, upStates, size)); - } - } - } - - static uint16_t getCacheType(const NodeType& nt, UpStates s) { - uint16_t typeEnum = nt; - return (s << 1) | typeEnum; - } -}; - -} // lib -} // storage diff --git a/vdslib/src/vespa/vdslib/state/clusterstate.cpp b/vdslib/src/vespa/vdslib/state/clusterstate.cpp index 0c65d22cfab..ce3dffbfb82 100644 --- a/vdslib/src/vespa/vdslib/state/clusterstate.cpp +++ b/vdslib/src/vespa/vdslib/state/clusterstate.cpp @@ -2,8 +2,6 @@ #include <vespa/fastos/fastos.h> #include <vespa/vdslib/state/clusterstate.h> -#include <boost/cast.hpp> -#include <boost/lexical_cast.hpp> #include <vespa/vespalib/text/stringtokenizer.h> #include <vespa/document/util/stringutil.h> #include <vespa/log/log.h> |