diff options
author | Yuri Gorshenin <y@maps.me> | 2015-02-26 18:15:15 +0300 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-23 02:37:44 +0300 |
commit | 681feb94c08f10f6ec2f70cd9056344e3c285f10 (patch) | |
tree | 0da635e58e85316053de7defd6e0d33b84d905b9 /base | |
parent | 0e5ad066dbf8b49145f381767104fbd199aa07f4 (diff) |
[search-index] Improved performance of current search index building process.
Diffstat (limited to 'base')
-rw-r--r-- | base/base.pro | 98 | ||||
-rw-r--r-- | base/base_tests/base_tests.pro | 37 | ||||
-rw-r--r-- | base/base_tests/mem_trie_test.cpp | 31 | ||||
-rw-r--r-- | base/base_tests/worker_thread_test.cpp | 31 | ||||
-rw-r--r-- | base/macros.hpp | 7 | ||||
-rw-r--r-- | base/mem_trie.hpp | 91 | ||||
-rw-r--r-- | base/worker_thread.hpp | 92 |
7 files changed, 319 insertions, 68 deletions
diff --git a/base/base.pro b/base/base.pro index 6071d8da79..005806318d 100644 --- a/base/base.pro +++ b/base/base.pro @@ -9,74 +9,76 @@ include($$ROOT_DIR/common.pri) SOURCES += \ base.cpp \ - logging.cpp \ - thread.cpp \ - string_utils.cpp \ commands_queue.cpp \ - shared_buffer_manager.cpp \ condition.cpp \ - lower_case.cpp \ - normalize_unicode.cpp \ - runner.cpp \ - timer.cpp \ - internal/message.cpp \ exception.cpp \ - threaded_container.cpp \ - resource_pool.cpp \ fence_manager.cpp \ - strings_bundle.cpp \ - string_format.cpp \ + internal/message.cpp \ + logging.cpp \ + lower_case.cpp \ + normalize_unicode.cpp \ object_tracker.cpp \ + pseudo_random.cpp \ + resource_pool.cpp \ + runner.cpp \ scheduled_task.cpp \ + shared_buffer_manager.cpp \ + src_point.cpp \ + string_format.cpp \ + string_utils.cpp \ + strings_bundle.cpp \ + thread.cpp \ thread_pool.cpp \ - pseudo_random.cpp \ - src_point.cpp + threaded_container.cpp \ + timer.cpp \ HEADERS += \ SRC_FIRST.hpp \ + array_adapters.hpp \ assert.hpp \ - const_helper.hpp \ - internal/fast_mutex.hpp \ - math.hpp \ - pseudo_random.hpp \ - scope_guard.hpp \ - macros.hpp \ base.hpp \ - src_point.hpp \ bits.hpp \ + buffer_vector.hpp \ + cache.hpp \ + commands_queue.hpp \ + condition.hpp \ + const_helper.hpp \ exception.hpp \ - internal/message.hpp \ + fence_manager.hpp \ + internal/fast_mutex.hpp \ internal/fast_mutex.hpp \ + internal/message.hpp \ + limited_priority_queue.hpp \ logging.hpp \ - swap.hpp \ - thread.hpp \ + macros.hpp \ + math.hpp \ + matrix.hpp \ + mem_trie.hpp \ + mru_cache.hpp \ mutex.hpp \ - string_utils.hpp \ + object_tracker.hpp \ + pseudo_random.hpp \ + regexp.hpp \ + resource_pool.hpp \ rolling_hash.hpp \ - stl_add.hpp \ - timer.hpp \ - cache.hpp \ - matrix.hpp \ + runner.hpp \ + scheduled_task.hpp \ + scope_guard.hpp \ set_operations.hpp \ - condition.hpp \ - commands_queue.hpp \ - stats.hpp \ shared_buffer_manager.hpp \ - buffer_vector.hpp \ - array_adapters.hpp \ - runner.hpp \ - mru_cache.hpp \ - threaded_container.hpp \ - threaded_list.hpp \ - resource_pool.hpp \ - limited_priority_queue.hpp \ - threaded_priority_queue.hpp \ + src_point.hpp \ + stats.hpp \ std_serialization.hpp \ - fence_manager.hpp \ - strings_bundle.hpp \ + stl_add.hpp \ + stl_iterator.hpp \ string_format.hpp \ - object_tracker.hpp \ - regexp.hpp \ - scheduled_task.hpp \ + string_utils.hpp \ + strings_bundle.hpp \ + swap.hpp \ + thread.hpp \ thread_pool.hpp \ - stl_iterator.hpp \ + threaded_container.hpp \ + threaded_list.hpp \ + threaded_priority_queue.hpp \ + timer.hpp \ + worker_thread.hpp \ diff --git a/base/base_tests/base_tests.pro b/base/base_tests/base_tests.pro index 25cb544cb3..b1e8ae8a89 100644 --- a/base/base_tests/base_tests.pro +++ b/base/base_tests/base_tests.pro @@ -14,32 +14,31 @@ win32-g++: LIBS += -lpthread SOURCES += \ ../../testing/testingmain.cpp \ - const_helper.cpp \ - math_test.cpp \ - scope_guard_test.cpp \ + assert_test.cpp \ bits_test.cpp \ - logging_test.cpp \ - threads_test.cpp \ - rolling_hash_test.cpp \ + buffer_vector_test.cpp \ cache_test.cpp \ - stl_add_test.cpp \ - string_utils_test.cpp \ - matrix_test.cpp \ commands_queue_test.cpp \ - buffer_vector_test.cpp \ - assert_test.cpp \ - timer_test.cpp \ - mru_cache_test.cpp \ - threaded_list_test.cpp \ condition_test.cpp \ + const_helper.cpp \ containers_test.cpp \ fence_manager_test.cpp \ - string_format_test.cpp \ + logging_test.cpp \ + math_test.cpp \ + matrix_test.cpp \ + mem_trie_test.cpp \ + mru_cache_test.cpp \ regexp_test.cpp \ + rolling_hash_test.cpp \ scheduled_task_test.cpp \ - thread_pool_tests.cpp + scope_guard_test.cpp \ + stl_add_test.cpp \ + string_format_test.cpp \ + string_utils_test.cpp \ + thread_pool_tests.cpp \ + threaded_list_test.cpp \ + threads_test.cpp \ + timer_test.cpp \ + worker_thread_test.cpp \ HEADERS += - - - diff --git a/base/base_tests/mem_trie_test.cpp b/base/base_tests/mem_trie_test.cpp new file mode 100644 index 0000000000..d4634dd950 --- /dev/null +++ b/base/base_tests/mem_trie_test.cpp @@ -0,0 +1,31 @@ +#include "../../testing/testing.hpp" + +#include "../mem_trie.hpp" + +#include "../../std/algorithm.hpp" +#include "../../std/string.hpp" +#include "../../std/utility.hpp" +#include "../../std/vector.hpp" + +UNIT_TEST(MemTrie_Basic) +{ + vector<pair<string, int>> data = {{"roger", 3}, + {"amy", 1}, + {"emma", 1}, + {"ann", 1}, + {"rob", 1}, + {"roger", 2}, + {"", 0}, + {"roger", 1}}; + my::MemTrie<string, int> trie; + for (auto const & p : data) + trie.Add(p.first, p.second); + + vector<pair<string, int>> ordered_data; + trie.ForEach([&ordered_data](string const & k, int v) + { + ordered_data.emplace_back(k, v); + }); + sort(data.begin(), data.end()); + TEST_EQUAL(data, ordered_data, ()); +} diff --git a/base/base_tests/worker_thread_test.cpp b/base/base_tests/worker_thread_test.cpp new file mode 100644 index 0000000000..51f800b21c --- /dev/null +++ b/base/base_tests/worker_thread_test.cpp @@ -0,0 +1,31 @@ +#include "../../testing/testing.hpp" + +#include "../worker_thread.hpp" + +#include "../../std/memory.hpp" +#include "../../std/vector.hpp" + +struct Task +{ + Task(vector<int> & buffer, int index) : m_buffer(buffer), m_index(index) {} + + void operator()() const { m_buffer.push_back(m_index); } + + vector<int> & m_buffer; + int m_index; +}; + +UNIT_TEST(WorkerThread_Basic) +{ + my::WorkerThread<Task> thread(5 /* maxTasks */); + + vector<int> buffer; + + for (int i = 0; i < 10; ++i) + thread.Push(make_shared<Task>(buffer, i)); + thread.RunUntilIdleAndStop(); + + TEST_EQUAL(static_cast<size_t>(10), buffer.size(), ()); + for (size_t i = 0; i < buffer.size(); ++i) + TEST_EQUAL(static_cast<int>(i), buffer[i], ()); +} diff --git a/base/macros.hpp b/base/macros.hpp index 573cae3bab..858b547c58 100644 --- a/base/macros.hpp +++ b/base/macros.hpp @@ -66,4 +66,9 @@ namespace my #define UINT64_LO(x) (static_cast<uint32_t>(x & 0xFFFFFFFF)) #define UINT64_HI(x) (static_cast<uint32_t>(x >> 32)) - +#define DISALLOW_COPY_AND_MOVE(className) \ +private: \ + className(const className &) = delete; \ + className(className &&) = delete; \ + className & operator=(const className &) = delete; \ + className & operator=(className &&) = delete; diff --git a/base/mem_trie.hpp b/base/mem_trie.hpp new file mode 100644 index 0000000000..27c3c4cc90 --- /dev/null +++ b/base/mem_trie.hpp @@ -0,0 +1,91 @@ +#pragma once + +#include "macros.hpp" + +#include "../std/map.hpp" +#include "../std/vector.hpp" + +namespace my +{ +/// This class is a simple in-memory trie which allows to add +/// key-value pairs and then traverse them in a sorted order. +template <typename StringT, typename ValueT> +class MemTrie +{ +public: + MemTrie() = default; + + /// Adds a key-value pair to the trie. + void Add(StringT const & key, ValueT const & value) + { + Node * cur = &m_root; + for (auto const & c : key) + cur = cur->GetMove(c); + cur->AddValue(value); + } + + /// Traverses all key-value pairs in the trie in a sorted order. + /// + /// \param toDo A callable object that will be called on an each + /// key-value pair. + template <typename ToDo> + void ForEach(ToDo const & toDo) + { + StringT prefix; + ForEach(&m_root, prefix, toDo); + } + +private: + struct Node + { + using CharT = typename StringT::value_type; + using MovesMap = map<CharT, Node *>; + + Node() = default; + + ~Node() + { + for (auto const & move : m_moves) + delete move.second; + } + + Node * GetMove(CharT const & c) + { + Node ** node = &m_moves[c]; + if (*node) + return *node; + *node = new Node(); + return *node; + } + + void AddValue(const ValueT & value) { m_values.push_back(value); } + + MovesMap m_moves; + vector<ValueT> m_values; + + DISALLOW_COPY_AND_MOVE(Node); + }; + + template <typename ToDo> + void ForEach(Node * root, StringT & prefix, ToDo const & toDo) + { + if (!root->m_values.empty()) + { + sort(root->m_values.begin(), root->m_values.end()); + for (auto const & value : root->m_values) + toDo(prefix, value); + } + + for (auto const & move : root->m_moves) + { + prefix.push_back(move.first); + ForEach(move.second, prefix, toDo); + prefix.pop_back(); + } + } + + Node m_root; + + DISALLOW_COPY_AND_MOVE(MemTrie); +}; // class MemTrie +} // namespace my diff --git a/base/worker_thread.hpp b/base/worker_thread.hpp new file mode 100644 index 0000000000..220d398b8a --- /dev/null +++ b/base/worker_thread.hpp @@ -0,0 +1,92 @@ +#pragma once + +#include "macros.hpp" + +#include "../std/condition_variable.hpp" +#include "../std/memory.hpp" +#include "../std/mutex.hpp" +#include "../std/queue.hpp" +#include "../std/thread.hpp" + +namespace my +{ +/// This class wraps a sequential worker thread, that performs tasks +/// one-by-one. This class is not thread-safe, so, it should be +/// instantiated, used and destroyed on the same thread. +template <typename Task> +class WorkerThread +{ +public: + WorkerThread(int maxTasks) + : m_maxTasks(maxTasks), m_shouldFinish(false), m_workerThread(&WorkerThread::Worker, this) + { + } + + ~WorkerThread() { CHECK(!m_workerThread.joinable(), ()); } + + /// Pushes new task into worker thread's queue. If the queue is + /// full, current thread is blocked. + /// + /// \param task A callable object that will be called by worker thread. + void Push(shared_ptr<Task> task) + { + CHECK(m_workerThread.joinable(), ()); + unique_lock<mutex> lock(m_mutex); + m_condNotFull.wait(lock, [this]() + { + return m_tasks.size() < m_maxTasks; + }); + m_tasks.push(task); + m_condNonEmpty.notify_one(); + } + + /// Runs worker thread until it'll become idle. After that, + /// terminates worker thread. + void RunUntilIdleAndStop() + { + { + lock_guard<mutex> lock(m_mutex); + m_shouldFinish = true; + m_condNonEmpty.notify_one(); + } + m_workerThread.join(); + } + +private: + void Worker() + { + shared_ptr<Task> task; + while (true) + { + { + unique_lock<mutex> lock(m_mutex); + m_condNonEmpty.wait(lock, [this]() + { + return m_shouldFinish || !m_tasks.empty(); + }); + if (m_shouldFinish && m_tasks.empty()) + break; + task = m_tasks.front(); + m_tasks.pop(); + m_condNotFull.notify_one(); + } + (*task)(); + } + } + + /// Maximum number of tasks in the queue. + int const m_maxTasks; + queue<shared_ptr<Task>> m_tasks; + + /// When true, worker thread should finish all tasks in the queue + /// and terminate. + bool m_shouldFinish; + + mutex m_mutex; + condition_variable m_condNotFull; + condition_variable m_condNonEmpty; + thread m_workerThread; + + DISALLOW_COPY_AND_MOVE(WorkerThread); +}; // class WorkerThread +} // namespace my |