tree_insert.cpp 6.8 KB
Newer Older
1
/*
2
 * Copyright (C) 2017-2020 DBIS Group - TU Ilmenau, All Rights Reserved.
3
4
5
 *
 * This file is part of our NVM-based Data Structures repository.
 *
6
7
8
9
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
10
 *
11
12
13
14
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
15
 *
16
17
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
18
19
20
21
22
 */

#include <libpmemobj++/container/array.hpp>
#include "common.hpp"
#include "utils/PersistEmulation.hpp"
23
24
25
#ifdef ENABLE_PCM
#include <cpucounters.h>
#endif
26
27
28

void prepare(const persistent_ptr<TreeType> tree);

29
30
31
32
33
uint64_t pmmwrites = 0;
uint64_t pmmreads = 0;
uint64_t modBytes = 0;  ///< modified Bytes
constexpr auto ArraySize = 4 * L3 / 256;

34
35
/* Get benchmarks on Tree */
static void BM_TreeInsert(benchmark::State &state) {
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
  #ifdef ENABLE_PCM
    PCM *pcm_ = PCM::getInstance();
    auto s = pcm_->program();
    if (s != PCM::Success) {
      std::cerr << "Error creating PCM instance: " << s << std::endl;
      if (s == PCM::PMUBusy)
        pcm_->resetPMU();
      else
        exit(0);
    }
  #endif

  std::cout << "BRANCHKEYS: " << BRANCHKEYS << " -> "
            << sizeof(TreeType::BranchNode) << "\nLEAFKEYS: " << LEAFKEYS
            << " -> " << sizeof(TreeType::LeafNode) << "\n";
51
52

  struct root {
53
    pptr<TreeType> tree;
54
55
56
57
58
59
60
  };

  pool<root> pop;

  pobj_alloc_class_desc alloc_class;
  if (access(path.c_str(), F_OK) != 0) {
    pop = pool<root>::create(path, LAYOUT, POOL_SIZE);
61
62
63
64
65
    alloc_class = pop.ctl_set<struct pobj_alloc_class_desc>(
        "heap.alloc_class.new.desc", TreeType::AllocClass);
    transaction::run(pop, [&] {
      pop.root()->tree = make_persistent<TreeType>(alloc_class);
    });
66
67
68
69
  } else {
    LOG("Warning: " << path << " already exists");
    pmempool_rm(path.c_str(), 0);
    pop = pool<root>::create(path, LAYOUT, POOL_SIZE);
70
71
72
73
74
    alloc_class = pop.ctl_set<struct pobj_alloc_class_desc>(
        "heap.alloc_class.new.desc", TreeType::AllocClass);
    transaction::run(pop, [&] {
      pop.root()->tree = make_persistent<TreeType>(alloc_class);
    });
75
  }
76
  auto tree = pop.root()->tree;
77
78
  prepare(tree);
  auto &treeRef = *tree;
79
  tree.flush(pop);
80
  auto leaf = treeRef.rootNode.leaf;
81
  leaf.flush(pop);
82
83
84
85
86
87

  pptr<pmem::obj::array<pptr<TreeType::LeafNode>, ArraySize>> leafArray;
  transaction::run(pop, [&] {
    leafArray = make_persistent<pmem::obj::array<pptr<TreeType::LeafNode>, ArraySize>>();
    for (int i = 0; i < ArraySize; ++i) {
      auto &a = *leafArray;
88
89
      a[i] = make_persistent<TreeType::LeafNode>(
          allocation_flag::class_id(alloc_class.class_id), *leaf);
90
91
92
93
94
    }
  });
  pop.drain();

  const auto reqTup = MyTuple(KEYPOS, KEYPOS * 100, KEYPOS * 1.0);
95
96
  const auto pos = treeRef.lookupPositionInLeafNode(leaf, KEYPOS);
  //const auto pos = dbis::BitOperations::getFreeZero(leaf->bits.get_ro());
97

98
99
100
101
102
103
104
105
#ifdef ENABLE_PCM
  SocketCounterState before_sstate;
  SocketCounterState after_sstate;
#endif

  /// Lambda function for measured part (needed twice)
  auto benchmark = [&pop, &treeRef, &reqTup, &pos](
                       const pptr<TreeType::LeafNode> &leafNode) {
106
107
108
109
110
111
112
    auto &leafRef = *leafNode;
    benchmark::DoNotOptimize(*leafNode);
    // transaction::run(pop, [&] {
    treeRef.insertInLeafNodeAtPosition(leafNode, pos, KEYPOS, reqTup);
    //});
    pop.flush(leafRef.numKeys);
    // pop.flush(leafRef.bits);
113
114
    // pop.flush(&leafRef.bits.get_ro(),
    //           sizeof(leafRef.bits.get_ro()) + sizeof(leafRef.fp.get_ro()));
115
    // pop.flush(&leafRef.slot.get_ro(),
116
117
118
119
120
    //           sizeof(leafRef.slot.get_ro()) + sizeof(leafRef.bits.get_ro()));
    // pop.flush(&leafRef.keys.get_ro()[LEAFKEYS-1], sizeof(MyKey));
    // pop.flush(&leafRef.values.get_ro()[LEAFKEYS-1], sizeof(MyTuple));
    pop.flush(&leafRef.keys.get_ro()[pos], sizeof(MyKey) * (ELEMENTS - pos));
    pop.flush(&leafRef.values.get_ro()[pos], sizeof(MyTuple) * (ELEMENTS - pos));
121
122
123
124
    pop.drain();
    // leafNode.persist(pop);

    benchmark::DoNotOptimize(*leafNode);
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
    benchmark::ClobberMemory();
  };

  /// BENCHMARK Writes
  if (pmmwrites == 0) {
    auto &leafNode = (*leafArray)[0];

    dbis::PersistEmulation::getBytesWritten();
#ifdef ENABLE_PCM
    before_sstate = getSocketCounterState(1);
#endif
    benchmark(leafNode);
#ifdef ENABLE_PCM
    after_sstate = getSocketCounterState(1);
    pmmreads = getBytesReadFromPMM(before_sstate, after_sstate);
    pmmwrites = getBytesWrittenToPMM(before_sstate, after_sstate);
#endif
    modBytes = dbis::PersistEmulation::getBytesWritten();
143
    *leafNode = *leaf;  ///< reset the modified node
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
    leafNode.flush(pop);
    // pop.flush((char *)((uintptr_t)&*leafNode - 64), 64); //< flush header
    pop.drain();
  }

  /// BENCHMARK Timing
  /// avoid output to stdout during benchmark
  std::cout.setstate(std::ios_base::failbit);
  std::srand(std::time(nullptr));
  for (auto _ : state) {
    const auto leafNodePos = std::rand() % ArraySize;
    auto leafNode = (*leafArray)[leafNodePos];
    auto &leafRef = *leafNode;

    auto start = std::chrono::high_resolution_clock::now();
    benchmark(leafNode);
    auto end = std::chrono::high_resolution_clock::now();

    leafRef = *leaf;  ///< reset the modified node
    leafNode.flush(pop);
    // pop.flush((char *)((uintptr_t)&*leafNode - 64), 64); //< flush header
165
    pop.drain();
166
167
168
    auto elapsed_seconds =
        std::chrono::duration_cast<std::chrono::duration<double>>(end - start);
    state.SetIterationTime(elapsed_seconds.count());
169
170
  }

171
  /// Evaluation & cleanup
172
173
  // treeRef.printLeafNode(0, leafNode);
  std::cout.clear();
174
175
176
177
  std::cout << "Iterations:" << state.iterations() << '\n';
  std::cout << "PMM Reads:" << pmmreads << '\n';
  std::cout << "Writes:" << modBytes << '\n';
  std::cout << "PMM Writes:" << pmmwrites << '\n';
178
179
180
181
182
183
  std::cout << "Elements:" << ELEMENTS << '\n';

  pop.close();
  pmempool_rm(path.c_str(), 0);
}

184
BENCHMARK(BM_TreeInsert)->UseManualTime();
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
BENCHMARK_MAIN();

/* preparing inserts */
void prepare(const persistent_ptr<TreeType> tree) {
  auto &treeRef = *tree;
  auto insertLoop = [&treeRef](const auto start, const auto end) {
    for (auto j = start; j < end + 1; ++j) {
      auto tup = MyTuple(j, j * 100, j * 1.0);
      treeRef.insert(j, tup);
    }
  };
  switch (KEYPOS) {
    case 1 /*first*/:
      insertLoop(2, LEAFKEYS);
      break;
    case ELEMENTS /*last*/:
      insertLoop(1, LEAFKEYS - 1);
      break;
    case (ELEMENTS + 1) / 2 /*middle*/: {
      insertLoop(1, KEYPOS - 1);
      insertLoop(KEYPOS + 1, LEAFKEYS);
    }
  }
}