diff options
author | Henning Baldersheim <balder@yahoo-inc.com> | 2019-10-03 13:17:54 +0000 |
---|---|---|
committer | Henning Baldersheim <balder@yahoo-inc.com> | 2019-11-01 10:47:45 +0000 |
commit | 4ca68e380802c40b328b1e7ea5cbd39650de5c1c (patch) | |
tree | 8be5174246a5d89a38e2c1ee1e8b1d9f18679ace | |
parent | 3348b25ef2831da17ce578061c85956eb9a80b5f (diff) |
Verify distance and ordering.
-rw-r--r-- | build_settings.cmake | 2 | ||||
-rw-r--r-- | staging_vespalib/CMakeLists.txt | 1 | ||||
-rw-r--r-- | staging_vespalib/src/tests/zncurve/CMakeLists.txt | 8 | ||||
-rw-r--r-- | staging_vespalib/src/tests/zncurve/zncurve_test.cpp | 48 | ||||
-rw-r--r-- | staging_vespalib/src/vespa/vespalib/util/zncurve.h | 3 | ||||
-rw-r--r-- | staging_vespalib/src/vespa/vespalib/util/zncurve.hpp | 25 | ||||
-rw-r--r-- | vespalib/src/vespa/vespalib/CMakeLists.txt | 2 |
7 files changed, 88 insertions, 1 deletions
diff --git a/build_settings.cmake b/build_settings.cmake index b1b0b065771..78afce822ed 100644 --- a/build_settings.cmake +++ b/build_settings.cmake @@ -46,7 +46,7 @@ else() endif() # C and C++ compiler flags -set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -g -O3 -fno-omit-frame-pointer ${C_WARN_OPTS} -fPIC ${VESPA_CXX_ABI_FLAGS} -DBOOST_DISABLE_ASSERTS ${VESPA_CPU_ARCH_FLAGS} -mtune=intel ${EXTRA_C_FLAGS}") +set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -g -O0 -fno-omit-frame-pointer ${C_WARN_OPTS} -fPIC ${VESPA_CXX_ABI_FLAGS} -DBOOST_DISABLE_ASSERTS ${VESPA_CPU_ARCH_FLAGS} -mtune=intel ${EXTRA_C_FLAGS}") if ("${CMAKE_CXX_COMPILER_ID}" STREQUAL "AppleClang") set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${CMAKE_C_FLAGS} ${CXX_SPECIFIC_WARN_OPTS} -std=c++1z -fdiagnostics-color=auto ${EXTRA_CXX_FLAGS}") else() diff --git a/staging_vespalib/CMakeLists.txt b/staging_vespalib/CMakeLists.txt index 095caf17a56..41dff6e1981 100644 --- a/staging_vespalib/CMakeLists.txt +++ b/staging_vespalib/CMakeLists.txt @@ -34,6 +34,7 @@ vespa_define_module( src/tests/timer src/tests/util/process_memory_stats src/tests/xmlserializable + src/tests/zncurve LIBS src/vespa/vespalib diff --git a/staging_vespalib/src/tests/zncurve/CMakeLists.txt b/staging_vespalib/src/tests/zncurve/CMakeLists.txt new file mode 100644 index 00000000000..d0d42887b17 --- /dev/null +++ b/staging_vespalib/src/tests/zncurve/CMakeLists.txt @@ -0,0 +1,8 @@ +# Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. +vespa_add_executable(staging_vespalib_zncurve_test_app TEST + SOURCES + zncurve_test.cpp + DEPENDS + staging_vespalib +) +vespa_add_test(NAME staging_vespalib_zncurve_test_app COMMAND staging_vespalib_zncurve_test_app) diff --git a/staging_vespalib/src/tests/zncurve/zncurve_test.cpp b/staging_vespalib/src/tests/zncurve/zncurve_test.cpp new file mode 100644 index 00000000000..6b0aca30dd6 --- /dev/null +++ b/staging_vespalib/src/tests/zncurve/zncurve_test.cpp @@ -0,0 +1,48 @@ +// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. + +#include <vespa/vespalib/testkit/testapp.h> +#include <vespa/vespalib/util/zncurve.h> + +using namespace vespalib; + +template <typename T> +void verifyDistance(double expected, std::vector<T> inputA, std::vector<T> inputB) { + ZNPoint a(&inputA[0], inputA.size()); + ZNPoint b(&inputB[0], inputB.size()); + ASSERT_EQUAL(0.0, a.distance(a)); + ASSERT_EQUAL(0.0, b.distance(b)); + ASSERT_EQUAL(expected, a.distance(b)); + ASSERT_EQUAL(expected, b.distance(a)); +} + +template <typename T> +void verifyOrder(std::vector<T> first_in, std::vector<T> second_in, std::vector<T> third_in) { + ZNPoint first(&first_in[0], first_in.size()); + ZNPoint second(&second_in[0], second_in.size()); + ZNPoint third(&third_in[0], third_in.size()); + ASSERT_TRUE(first < second); + ASSERT_TRUE(second < third); + ASSERT_TRUE(first < third); + ASSERT_FALSE(second < first); + ASSERT_FALSE(third < second); + ASSERT_FALSE(third < first); +} + +TEST("verify distance") { + verifyDistance<uint32_t>(5, {3,7}, {7, 10}); + verifyDistance<float>(5, {3,7}, {7, 10}); +} + +TEST("verify order") { + verifyOrder<uint32_t>({3}, {7}, {8}); + verifyOrder<uint32_t>({3,7}, {7, 10}, {8, 10}); + verifyOrder<uint32_t>({3, 2}, {3, 3}, {4, 1}); + verifyOrder<uint32_t>({3, 2, 3}, {3, 3, 2}, {3, 2, 7}); + + verifyOrder<float>({3}, {7}, {8}); + verifyOrder<float>({3,7}, {7, 10}, {8, 10}); +//TODO: Investigate below failure. +// verifyOrder<float>({3, 2}, {3, 3}, {4, 1}); +} + +TEST_MAIN() { TEST_RUN_ALL(); } diff --git a/staging_vespalib/src/vespa/vespalib/util/zncurve.h b/staging_vespalib/src/vespa/vespalib/util/zncurve.h index 392e44b5d97..d8d5954b4ad 100644 --- a/staging_vespalib/src/vespa/vespalib/util/zncurve.h +++ b/staging_vespalib/src/vespa/vespalib/util/zncurve.h @@ -11,6 +11,9 @@ template<typename T> class ZNPoint { public: ZNPoint(const T * begin, uint32_t numDim); + ZNPoint(ZNPoint && rhs) = default; + ZNPoint & operator = (ZNPoint && rhs) = default; + ~ZNPoint(); bool operator < (const ZNPoint & rhs) const; double distance(const ZNPoint & rhs) const; uint32_t numDim() const { return _vector.size(); } diff --git a/staging_vespalib/src/vespa/vespalib/util/zncurve.hpp b/staging_vespalib/src/vespa/vespalib/util/zncurve.hpp index a2c832d2bd2..1ebf98e091e 100644 --- a/staging_vespalib/src/vespa/vespalib/util/zncurve.hpp +++ b/staging_vespalib/src/vespa/vespalib/util/zncurve.hpp @@ -3,6 +3,7 @@ #pragma once #include "zncurve.h" +#include "sort.h" #include <cstring> #include <cmath> #include <cassert> @@ -23,6 +24,9 @@ double squareDistance(uint32_t a, uint32_t b) { return diff * diff; } +uint32_t byteIndex(uint32_t index) { return index >> 3; } +uint8_t mask(uint32_t index) { return 1 << (7 - (index % 8)); } + } template<typename T> @@ -30,12 +34,33 @@ ZNPoint<T>::ZNPoint(const T * begin, uint32_t numDim) : _vector(numDim), _point(numDim*sizeof(T)) { + using Converter = convertForSort<T, true>; + using ConvertedT = typename Converter::UIntType; + Converter converter; + assert(sizeof(T) == sizeof(ConvertedT)); + std::vector<ConvertedT> converted(numDim); for (uint32_t i(0); i < numDim; i++) { _vector[i] = begin[i]; + converted[i] = converter.convert(begin[i]); + } + + uint32_t bitPos = _point.size()*8; + for (uint32_t bitNum(0); bitNum < sizeof(ConvertedT)*8; bitNum++) { + for (uint32_t dim(converted.size()); dim; dim--) { + ConvertedT tmp = converted[dim - 1]; + bitPos--; + if (tmp & (1 << bitNum)) { + _point[byteIndex(bitPos)] |= mask(bitPos); + } + } } + assert(bitPos == 0); } template<typename T> +ZNPoint<T>::~ZNPoint() = default; + +template<typename T> double ZNPoint<T>::distance(const ZNPoint & rhs) const { diff --git a/vespalib/src/vespa/vespalib/CMakeLists.txt b/vespalib/src/vespa/vespalib/CMakeLists.txt index 4249f6333a4..11a3e661809 100644 --- a/vespalib/src/vespa/vespalib/CMakeLists.txt +++ b/vespalib/src/vespa/vespalib/CMakeLists.txt @@ -26,6 +26,8 @@ vespa_add_library(vespalib INSTALL lib64 DEPENDS ${VESPA_GCC_LIB} + ssl + crypto ) vespa_add_target_package_dependency(vespalib OpenSSL) |