Skip to content

Commit 08e47eb

Browse files
twhuang-utahtwhuang-utah
committed
added object pool
1 parent 8bd08a9 commit 08e47eb

File tree

11 files changed

+865
-312
lines changed

11 files changed

+865
-312
lines changed

‎CMakeLists.txt‎

Lines changed: 10 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -259,9 +259,7 @@ add_executable(utility ${TF_UTEST_DIR}/utility.cpp)
259259
target_link_libraries(utility ${PROJECT_NAME} Threads::Threads tf::default_settings)
260260
target_include_directories(utility PRIVATE ${TF_3RD_PARTY_DIR}/doctest)
261261
add_test(passive_vector ${TF_UTEST_DIR}/utility -tc=PassiveVector)
262-
add_test(object_pool ${TF_UTEST_DIR}/utility -tc=ObjectPool)
263262
add_test(function_traits ${TF_UTEST_DIR}/utility -tc=FunctionTraits)
264-
add_test(singular_alloc ${TF_UTEST_DIR}/utility -tc=SingularAllocator)
265263

266264
# unittest for WorkStealingQueue
267265
add_executable(wsq ${TF_UTEST_DIR}/wsq.cpp)
@@ -312,8 +310,16 @@ add_test(hierarchical_cond ${TF_UTEST_DIR}/basics -tc=HierarchicalConditi
312310
add_executable(traverse ${TF_UTEST_DIR}/traverse.cpp)
313311
target_link_libraries(traverse ${PROJECT_NAME} Threads::Threads tf::default_settings)
314312
target_include_directories(traverse PRIVATE ${TF_3RD_PARTY_DIR}/doctest)
315-
add_test(static_levelize ${TF_UTEST_DIR}/traverse -tc=StaticLevelize)
316-
add_test(dynamic_levelize ${TF_UTEST_DIR}/traverse -tc=DynamicLevelize)
313+
add_test(static_traverse ${TF_UTEST_DIR}/traverse -tc=StaticTraverse)
314+
add_test(dynamic_traverse ${TF_UTEST_DIR}/traverse -tc=DynamicTraverse)
315+
add_test(parallel_traverse.1 ${TF_UTEST_DIR}/traverse -tc=ParallelTraverse.1)
316+
add_test(parallel_traverse.2 ${TF_UTEST_DIR}/traverse -tc=ParallelTraverse.2)
317+
add_test(parallel_traverse.3 ${TF_UTEST_DIR}/traverse -tc=ParallelTraverse.3)
318+
add_test(parallel_traverse.4 ${TF_UTEST_DIR}/traverse -tc=ParallelTraverse.4)
319+
add_test(parallel_traverse.5 ${TF_UTEST_DIR}/traverse -tc=ParallelTraverse.5)
320+
add_test(parallel_traverse.6 ${TF_UTEST_DIR}/traverse -tc=ParallelTraverse.6)
321+
add_test(parallel_traverse.7 ${TF_UTEST_DIR}/traverse -tc=ParallelTraverse.7)
322+
add_test(parallel_traverse.8 ${TF_UTEST_DIR}/traverse -tc=ParallelTraverse.8)
317323

318324
# unittest for sorting
319325
add_executable(sort ${TF_UTEST_DIR}/sort.cpp)

‎examples/simple.cpp‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ int main(){
2121
A.precede(C); // C runs after A // | +---+ |
2222
B.precede(D); // D runs after B // +---->| C |-----+
2323
C.precede(D); // D runs after C // +---+
24+
2425
executor.run(taskflow).wait();
2526

2627
return 0;

taskflow/utility/generic_allocator.hpp renamed to legacy/20200202/generic_allocator.hpp

File renamed without changes.

taskflow/utility/singular_allocator.hpp renamed to legacy/20200202/singular_allocator.hpp

File renamed without changes.

‎taskflow/core/executor.hpp‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -676,7 +676,7 @@ inline void Executor::_invoke(Worker& worker, Node* node) {
676676
// For storing the source nodes
677677
PassiveVector<Node*> src;
678678

679-
for(auto& n: node->_subgraph->nodes()) {
679+
for(auto n: node->_subgraph->_nodes) {
680680

681681
n->_topology = node->_topology;
682682
n->_set_up_join_counter();
@@ -688,7 +688,7 @@ inline void Executor::_invoke(Worker& worker, Node* node) {
688688
}
689689

690690
if(n->num_dependents() == 0) {
691-
src.push_back(n.get());
691+
src.push_back(n);
692692
}
693693
}
694694

@@ -820,13 +820,13 @@ inline void Executor::_set_up_topology(Topology* tpg) {
820820
tpg->_sources.clear();
821821

822822
// scan each node in the graph and build up the links
823-
for(auto& node : tpg->_taskflow._graph.nodes()) {
823+
for(auto node : tpg->_taskflow._graph._nodes) {
824824

825825
node->_topology = tpg;
826826
node->_clear_state();
827827

828828
if(node->num_dependents() == 0) {
829-
tpg->_sources.push_back(node.get());
829+
tpg->_sources.push_back(node);
830830
}
831831

832832
int join_counter = 0;
@@ -1042,14 +1042,14 @@ inline void Executor::_set_up_module_node(Node* node) {
10421042

10431043
PassiveVector<Node*> src;
10441044

1045-
for(auto& n: node->_module->_graph.nodes()) {
1045+
for(auto n: node->_module->_graph._nodes) {
10461046

10471047
n->_topology = node->_topology;
10481048
n->_parent = node;
10491049
n->_set_up_join_counter();
10501050

10511051
if(n->num_dependents() == 0) {
1052-
src.push_back(n.get());
1052+
src.push_back(n);
10531053
}
10541054
}
10551055

‎taskflow/core/flow_builder.hpp‎

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -368,7 +368,7 @@ Task FlowBuilder::emplace(C&& c) {
368368

369369
// dynamic tasking
370370
if constexpr(std::is_invocable_v<C, Subflow&>) {
371-
auto& n = _graph.emplace_back(std::in_place_type_t<Node::DynamicWork>{},
371+
auto n = _graph.emplace_back(std::in_place_type_t<Node::DynamicWork>{},
372372
[c=std::forward<C>(c)] (Subflow& fb) mutable {
373373
// first time execution
374374
if(fb._graph.empty()) {
@@ -379,21 +379,21 @@ Task FlowBuilder::emplace(C&& c) {
379379
}
380380
// condition tasking
381381
else if constexpr(std::is_same_v<typename function_traits<C>::return_type, int>) {
382-
auto& n = _graph.emplace_back(
382+
auto n = _graph.emplace_back(
383383
std::in_place_type_t<Node::ConditionWork>{}, std::forward<C>(c)
384384
);
385385
return Task(n);
386386
}
387387
// static tasking
388388
else if constexpr(std::is_same_v<typename function_traits<C>::return_type, void>) {
389-
auto& n = _graph.emplace_back(
389+
auto n = _graph.emplace_back(
390390
std::in_place_type_t<Node::StaticWork>{}, std::forward<C>(c)
391391
);
392392
return Task(n);
393393
}
394394
// placeholder
395395
else if constexpr(std::is_same_v<C, std::monostate>) {
396-
auto& n = _graph.emplace_back();
396+
auto n = _graph.emplace_back();
397397
return Task(n);
398398
}
399399
else {
@@ -403,8 +403,8 @@ Task FlowBuilder::emplace(C&& c) {
403403

404404
// Function: composed_of
405405
inline Task FlowBuilder::composed_of(Taskflow& taskflow) {
406-
auto &node = _graph.emplace_back();
407-
node._module = &taskflow;
406+
auto node = _graph.emplace_back();
407+
node->_module = &taskflow;
408408
return Task(node);
409409
}
410410

@@ -443,7 +443,7 @@ inline void FlowBuilder::gather(std::initializer_list<Task> froms, Task to) {
443443

444444
// Function: placeholder
445445
inline Task FlowBuilder::placeholder() {
446-
auto& node = _graph.emplace_back();
446+
auto node = _graph.emplace_back();
447447
return Task(node);
448448
}
449449

‎taskflow/core/graph.hpp‎

Lines changed: 46 additions & 117 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
#pragma once
22

33
#include "../error/error.hpp"
4+
#include "../utility/object_pool.hpp"
45
#include "../utility/traits.hpp"
56
#include "../utility/passive_vector.hpp"
67
#include "declarations.hpp"
@@ -11,13 +12,17 @@ namespace tf {
1112
class Graph {
1213

1314
friend class Node;
15+
friend class Taskflow;
16+
friend class Executor;
1417

1518
public:
1619

1720
Graph() = default;
1821
Graph(const Graph&) = delete;
1922
Graph(Graph&&);
2023

24+
~Graph();
25+
2126
Graph& operator = (const Graph&) = delete;
2227
Graph& operator = (Graph&&);
2328

@@ -28,17 +33,15 @@ class Graph {
2833
size_t size() const;
2934

3035
template <typename ...Args>
31-
Node& emplace_back(Args&& ...);
32-
33-
Node& emplace_back();
36+
Node* emplace_back(Args&& ...);
3437

35-
std::vector<std::unique_ptr<Node>>& nodes();
36-
37-
const std::vector<std::unique_ptr<Node>>& nodes() const;
38+
Node* emplace_back();
3839

3940
private:
41+
42+
static ObjectPool<Node>& _node_pool();
4043

41-
std::vector<std::unique_ptr<Node>> _nodes;
44+
std::vector<Node*> _nodes;
4245
};
4346

4447
// ----------------------------------------------------------------------------
@@ -86,10 +89,10 @@ class Node {
8689

8790
const std::string& name() const;
8891

89-
//std::string dump() const;
92+
ObjectPool<Node>::satellite_t satellite;
9093

9194
private:
92-
95+
9396
std::string _name;
9497
std::variant<std::monostate, StaticWork, DynamicWork, ConditionWork> _work;
9598

@@ -125,13 +128,17 @@ Node::Node(Args&&... args): _work{std::forward<Args>(args)...} {
125128
inline Node::~Node() {
126129
// this is to avoid stack overflow
127130
if(_subgraph.has_value()) {
128-
std::vector<std::unique_ptr<Node>> nodes;
131+
132+
std::vector<Node*> nodes;
133+
129134
std::move(
130135
_subgraph->_nodes.begin(), _subgraph->_nodes.end(), std::back_inserter(nodes)
131136
);
132137
_subgraph->_nodes.clear();
133138
_subgraph.reset();
139+
134140
size_t i = 0;
141+
135142
while(i < nodes.size()) {
136143
if(auto& sbg = nodes[i]->_subgraph; sbg) {
137144
std::move(
@@ -142,6 +149,11 @@ inline Node::~Node() {
142149
}
143150
++i;
144151
}
152+
153+
auto& np = Graph::_node_pool();
154+
for(i=0; i<nodes.size(); ++i) {
155+
np.destruct(nodes[i]);
156+
}
145157
}
146158
}
147159

@@ -275,97 +287,23 @@ inline bool Node::_has_state(int flag) const {
275287
}
276288

277289
// ----------------------------------------------------------------------------
278-
279-
/*// Class: NodePool
280-
class NodePool {
281-
282-
public:
283-
284-
template <typename C>
285-
std::unique_ptr<Node> acquire(C&&);
286-
287-
std::unique_ptr<Node> acquire();
288-
289-
void release(std::unique_ptr<Node>);
290-
291-
private:
290+
// Graph definition
291+
// ----------------------------------------------------------------------------
292292

293-
//std::mutex _mutex;
294-
295-
std::vector<std::unique_ptr<Node>> _nodes;
296-
297-
void _recycle(Node&);
298-
};
299-
300-
// Function: acquire
301-
template <typename C>
302-
inline std::unique_ptr<Node> NodePool::acquire(C&& c) {
303-
if(_nodes.empty()) {
304-
return std::make_unique<Node>(std::forward<C>(c));
305-
}
306-
else {
307-
auto node = std::move(_nodes.back());
308-
node->_work = std::forward<C>(c);
309-
_nodes.pop_back();
310-
return node;
311-
}
293+
// Function: _node_pool
294+
inline ObjectPool<Node>& Graph::_node_pool() {
295+
static ObjectPool<Node> pool;
296+
return pool;
312297
}
313298

314-
// Function: acquire
315-
inline std::unique_ptr<Node> NodePool::acquire() {
316-
if(_nodes.empty()) {
317-
return std::make_unique<Node>();
318-
}
319-
else {
320-
auto node = std::move(_nodes.back());
321-
_nodes.pop_back();
322-
return node;
323-
}
324-
}
325-
326-
// Procedure: release
327-
inline void NodePool::release(std::unique_ptr<Node> node) {
328-
329-
return;
330-
331-
//assert(node);
332-
if(_nodes.size() >= 65536) {
333-
return;
334-
}
335-
336-
auto children = node->_extract_children();
337-
338-
for(auto& child : children) {
339-
_recycle(*child);
299+
// Destructor
300+
inline Graph::~Graph() {
301+
auto& np = _node_pool();
302+
for(auto node : _nodes) {
303+
np.destruct(node);
340304
}
341-
_recycle(*node);
342-
343-
std::move(children.begin(), children.end(), std::back_inserter(_nodes));
344-
_nodes.push_back(std::move(node));
345-
}
346-
347-
// Procedure: _recycle
348-
inline void NodePool::_recycle(Node& node) {
349-
node._name.clear();
350-
node._work = {};
351-
node._successors.clear();
352-
node._dependents.clear();
353-
node._topology = nullptr;
354-
node._module = nullptr;
355-
node._state = 0;
356-
node._join_counter.store(0, std::memory_order_relaxed);
357-
//assert(!node._subgraph);
358305
}
359306

360-
// ----------------------------------------------------------------------------
361-
362-
namespace this_thread {
363-
inline thread_local NodePool nodepool;
364-
}
365-
*/
366-
367-
// ----------------------------------------------------------------------------
368-
369307
// Move constructor
370308
inline Graph::Graph(Graph&& other) :
371309
_nodes {std::move(other._nodes)} {
@@ -378,8 +316,11 @@ inline Graph& Graph::operator = (Graph&& other) {
378316
}
379317

380318
// Procedure: clear
381-
// clear and recycle the nodes
382319
inline void Graph::clear() {
320+
auto& np = _node_pool();
321+
for(auto node : _nodes) {
322+
np.destruct(node);
323+
}
383324
_nodes.clear();
384325
}
385326

@@ -395,33 +336,21 @@ inline bool Graph::empty() const {
395336
return _nodes.empty();
396337
}
397338

398-
// Function: nodes
399-
// return a mutable reference to the node data structure
400-
//inline std::vector<std::unique_ptr<Node>>& Graph::nodes() {
401-
inline std::vector<std::unique_ptr<Node>>& Graph::nodes() {
402-
return _nodes;
403-
}
404-
405-
// Function: nodes
406-
// returns a constant reference to the node data structure
407-
//inline const std::vector<std::unique_ptr<Node>>& Graph::nodes() const {
408-
inline const std::vector<std::unique_ptr<Node>>& Graph::nodes() const {
409-
return _nodes;
410-
}
411-
412339
// Function: emplace_back
413340
// create a node from a give argument; constructor is called if necessary
414-
template <typename ...Args>
415-
Node& Graph::emplace_back(Args&&... args) {
416-
_nodes.push_back(std::make_unique<Node>(std::forward<Args>(args)...));
417-
return *(_nodes.back());
341+
template <typename ...ArgsT>
342+
Node* Graph::emplace_back(ArgsT&&... args) {
343+
auto node = _node_pool().construct(std::forward<ArgsT>(args)...);
344+
_nodes.push_back(node);
345+
return node;
418346
}
419347

420348
// Function: emplace_back
421349
// create a node from a give argument; constructor is called if necessary
422-
inline Node& Graph::emplace_back() {
423-
_nodes.push_back(std::make_unique<Node>());
424-
return *(_nodes.back());
350+
inline Node* Graph::emplace_back() {
351+
auto node = _node_pool().construct();
352+
_nodes.push_back(node);
353+
return node;
425354
}
426355

427356

0 commit comments

Comments
 (0)