8000 use unordered_set for speed ups · Z80coder/datalog-cpp@38aee16 · GitHub
[go: up one dir, main page]
Skip to content

Commit 38aee16

Browse files
ianpaulwrightianpaulwright
committed
use unordered_set for speed ups
1 parent c26c7ec commit 38aee16

File tree

2 files changed

+103
-57
lines changed

2 files changed

+103
-57
lines changed

‎src/Datalog.h

Lines changed: 47 additions & 57 deletions
Original file line numberDiff line numberDiff line change
@@ -3,13 +3,15 @@
33

44
#include <tuple>
55
#include <set>
6+
#include <unordered_set>
67
#include <numeric>
78
#include <optional>
89
#include <limits>
910
#include <functional>
1011
#include <cassert>
1112
#include <iostream>
12-
#include <memory>
13+
14+
#include " 10000 tuple_hash.h"
1315

1416
namespace datalog
1517
{
@@ -41,28 +43,30 @@ struct Variable : optional<T>
4143
}
4244
};
4345

46+
// TODO: use auto more for return type of functions
47+
4448
template<typename T>
45-
T val(unique_ptr<Variable<T>>& var) {
46-
return var->value();
49+
Variable<T>* var() {
50+
return new Variable<T>();
4751
}
4852

4953
template<typename T>
50-
unique_ptr<Variable<T>> var() {
51-
return make_unique<Variable<T>>();
54+
T val(Variable<T>* t) {
55+
return t->value();
5256
}
5357

54-
template <typename T>
55-
static void unbind(Variable<T>* t) {
56-
t->unbind();
58+
template<typename T>
59+
void deleteVar(Variable<T>* v) {
60+
delete v;
5761
}
5862

5963
template <typename T>
60-
static void unbind(unique_ptr<Variable<T>>& t) {
61-
unbind(t.get());
62-
}
64+
static void unbind(const T& t) {}
6365

6466
template <typename T>
65-
static void unbind(const T& t) {}
67+
static void unbind(Variable<T>* t) {
68+
t->unbind();
69+
}
6670

6771
template <typename... Ts>
6872
static void unbind(const tuple<Ts...> &tuple)
@@ -84,11 +88,6 @@ static bool bind(const T& a, Variable<T>* b) { 8000
8488
return true;
8589
}
8690

87-
template <typename T>
88-
static bool bind(const T& a, unique_ptr<Variable<T>>& b) {
89-
return bind(a, b.get());
90-
}
91-
9291
template <typename GROUND_TYPE, typename ... Ts, size_t... Is>
9392
static bool bind(const GROUND_TYPE &fact, tuple<Ts...> &atom, index_sequence<Is...>)
9493
{
@@ -108,12 +107,6 @@ static void ground(const Variable<T>* s, T &v)
108107
v = s->value();
109108
}
110109

111-
template <typename T>
112-
static void ground(const unique_ptr<Variable<T>>& s, T &v)
113-
{
114-
ground(s.get(), v);
115-
}
116-
117110
template <typename T>
118111
static void ground(const T &s, T &v)
119112
{
@@ -137,7 +130,6 @@ static typename RELATION_TYPE::Ground ground(const tuple<Ts...> &atom)
137130
template<typename RELATION_TYPE, typename ... Ts>
138131
struct AtomTypeSpecifier {
139132
typedef RELATION_TYPE RelationType;
140-
// TODO: why not references?
141133
typedef tuple<Ts...> AtomType;
142134
AtomType atom;
143135
};
@@ -156,18 +148,34 @@ template <typename... Ts>
156148
struct Relation
157149
{
158150
typedef tuple<Ts...> Ground;
159-
// TODO: this should be an unordered_set
151+
#if 1
152+
// set seems faster than unordered_set
160153
typedef set<Ground> Set;
154+
#else
155+
typedef unordered_set<Ground> Set;
156+
#endif
157+
161158
typedef pair<size_t, Ground> TrackedGround;
162-
// TODO: this should be an unordered_set
159+
#if 0
163160
struct compare {
164161
bool operator() (const TrackedGround& lhs, const TrackedGround& rhs) const {
165162
// ignore tracking number
166163
return lhs.second < rhs.second;
167164
}
168165
};
169-
170166
typedef set<TrackedGround, compare> TrackedSet;
167+
#else
168+
// unordered set seems faster than set
169+
struct key_hash : public std::unary_function<TrackedGround, std::size_t>
170+
{
171+
size_t operator()(const TrackedGround& k) const
172+
{
173+
hash<decltype(k.second)> h;
174+
return k.first ^ h.operator()(k.second);
175+
}
176+
};
177+
typedef unordered_set<TrackedGround, key_hash> TrackedSet;
178+
#endif
171179

172180
};
173181

@@ -182,8 +190,6 @@ struct Rule
182190

183191
template<typename ... EXTERNAL_TYPEs>
184192
struct Externals {
185-
// N.B. We need to store the ExternalFunctions
186-
//typedef tuple<const EXTERNAL_TYPEs&...> ExternalsTupleType;
187193
typedef tuple<const EXTERNAL_TYPEs...> ExternalsTupleType;
188194
ExternalsTupleType externals;
189195
};
@@ -193,8 +199,6 @@ struct BodyAtoms {
193199
tuple<typename BODY_ATOM_SPECIFIERs::AtomType...> body;
194200
};
195201

196-
// Note that RuleInstances store atoms (and therefore atoms specified during construction are copied).
197-
// This is OK since all copies of atoms still refer to the same shared variables
198202
template <typename HEAD_ATOM_SPECIFIER, typename... BODY_ATOM_SPECIFIERs>
199203
struct RuleInstance {
200204
typedef Rule<typename HEAD_ATOM_SPECIFIER::RelationType, typename BODY_ATOM_SPECIFIERs::RelationType...> RuleType;
@@ -204,22 +208,15 @@ struct RuleInstance {
204208
BodyType body;
205209
};
206210

207-
#if 0
208-
template <typename EXTERNALS_TYPE, typename HEAD_ATOM_SPECIFIER, typename... BODY_ATOM_SPECIFIERs>
209-
struct ExternalRuleInstance : RuleInstance<HEAD_ATOM_SPECIFIER, BODY_ATOM_SPECIFIERs...> {
210-
const EXTERNALS_TYPE& externals;
211-
};
212-
#else
213211
template <typename EXTERNALS_TYPE, typename HEAD_ATOM_SPECIFIER, typename... BODY_ATOM_SPECIFIERs>
214212
struct ExternalRuleInstance {
215213
typedef Rule<typename HEAD_ATOM_SPECIFIER::RelationType, typename BODY_ATOM_SPECIFIERs::RelationType...> RuleType;
216214
typedef typename HEAD_ATOM_SPECIFIER::AtomType HeadType;
217215
const HeadType head;
218216
typedef tuple<typename BODY_ATOM_SPECIFIERs::AtomType...> BodyType;
219217
BodyType body;
220-
const EXTERNALS_TYPE& externals;
218+
const EXTERNALS_TYPE externals;
221219
};
222-
#endif
223220

224221
template <typename HEAD_ATOM_SPECIFIER, typename... BODY_ATOM_SPECIFIERs>
225222
static RuleInstance<HEAD_ATOM_SPECIFIER, BODY_ATOM_SPECIFIERs...> rule(
@@ -246,35 +243,23 @@ static RuleInstance<HEAD_ATOM_SPECIFIER, BODY_ATOM_SPECIFIERs...> rule(
246243

247244
template<typename T>
248245
struct ExternalFunction {
249-
Variable<T>& bindVariable;
246< 10000 code class="diff-text syntax-highlighted-line addition">+
Variable<T>* bindVariable;
250247
typedef function<T()> ExternalFunctionType;
251248
ExternalFunctionType externalFunction;
252249
};
253250

254251
template<typename T>
255252
static ExternalFunction<T> lambda(
256-
unique_ptr<Variable<T>>& bindVariable,
253+
Variable<T>* bindVariable,
257254
typename ExternalFunction<T>::ExternalFunctionType externalFunction) {
258-
return ExternalFunction<T> {*bindVariable, externalFunction};
255+
return ExternalFunction<T> {bindVariable, externalFunction};
259256
}
260257

261-
#if 0
262258
template<typename ... BODY_ATOM_SPECIFIERs>
263259
static BodyAtoms<BODY_ATOM_SPECIFIERs...> body(BODY_ATOM_SPECIFIERs&&... bodyAtoms) {
264260
return BodyAtoms<BODY_ATOM_SPECIFIERs...>{{bodyAtoms.atom...}};
265261
}
266262

267-
template<typename ... BODY_ATOM_SPECIFIERs>
268-
static BodyAtoms<BODY_ATOM_SPECIFIERs...> body(BODY_ATOM_SPECIFIERs&... bodyAtoms) {
269-
return BodyAtoms<BODY_ATOM_SPECIFIERs...>{{bodyAtoms.atom...}};
270-
}
271-
#else
272-
template<typename ... BODY_ATOM_SPECIFIERs>
273-
static BodyAtoms<BODY_ATOM_SPECIFIERs...> body(BODY_ATOM_SPECIFIERs... bodyAtoms) {
274-
return BodyAtoms<BODY_ATOM_SPECIFIERs...>{{bodyAtoms.atom...}};
275-
}
276-
#endif
277-
278263
template <typename HEAD_ATOM_SPECIFIER, typename... BODY_ATOM_SPECIFIERs, typename... EXTERNAL_TYPEs>
279264
static ExternalRuleInstance<Externals<EXTERNAL_TYPEs...>, HEAD_ATOM_SPECIFIER, BODY_ATOM_SPECIFIERs...> rule(
280265
const HEAD_ATOM_SPECIFIER& h,
@@ -315,7 +300,7 @@ static ostream & operator<<(ostream &out, const RelationSet<RELATION_TYPE>& rela
315300
{
316301
out << "\"" << typeid(relationSet).name() << "\"" << endl;
317302
for (const auto& tuple : relationSet.set) {
318-
operator<< <RELATION_TYPE>(out, tuple.second);
303+
datalog::operator<< <RELATION_TYPE>(out, tuple.second);
319304
out << endl;
320305
}
321306
return out;
@@ -664,7 +649,7 @@ static bool bindExternal(const ExternalRuleInstance<Externals<Ts...>, HEAD_ATOM_
664649
auto value = external.externalFunction();
665650
//cout << "external function returned " << value << endl;
666651
auto& bindVariable = external.bindVariable;
667-
return datalog::bind(value, &bindVariable);
652+
return datalog::bind(value, bindVariable);
668653
}
669654

670655
template <typename... Ts, typename HEAD_ATOM_SPECIFIER, typename... BODY_ATOM_SPECIFIERs, size_t ... Is>
@@ -684,7 +669,7 @@ template<size_t I, typename... Ts, typename HEAD_ATOM_SPECIFIER, typename... BOD
684669
static void unbindExternal(const ExternalRuleInstance<Externals<Ts...>, HEAD_ATOM_SPECIFIER, BODY_ATOM_SPECIFIERs...>& rule) {
685670
auto& external = get<I>(rule.externals.externals);
686671
auto& bindVariable = external.bindVariable;
687-
bindVariable.unbind();
672+
bindVariable->unbind();
688673
}
689674

690675
template <typename... Ts, typename HEAD_ATOM_SPECIFIER, typename... BODY_ATOM_SPECIFIERs, size_t ... Is>
@@ -769,6 +754,11 @@ struct RuleSet {
769754
tuple<RULE_TYPEs...> rules;
770755
};
771756

757+
template <typename ... RULE_TYPEs>
758+
RuleSet<RULE_TYPEs...> ruleset(RULE_TYPEs&&... r) {
759+
return RuleSet<RULE_TYPEs...>{{r...}};
760+
}
761+
772762
template <typename ... RULE_TYPEs, typename... RELATIONs>
773763
static void applyRuleSet(
774764
size_t iteration,

‎src/tuple_hash.h

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
#ifndef TUPLE_HASH_H
2+
#define TUPLE_HASH_H
3+
4+
// function has to live in the std namespace
5+
// so that it is picked up by argument-dependent name lookup (ADL).
6+
namespace std{
7+
namespace
8+
{
9+
// Code from boost
10+
// Reciprocal of the golden ratio helps spread entropy
11+
// and handles duplicates.
12+
// See Mike Seymour in magic-numbers-in-boosthash-combine:
13+
// https://stackoverflow.com/questions/4948780
14+
15+
template <class T>
16+
inline void hash_combine(std::size_t& seed, T const& v)
17+
{
18+
seed ^= hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
19+
}
20+
21+
// Recursive template code derived from Matthieu M.
22+
template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
23+
struct HashValueImpl
24+
{
25+
static void apply(size_t& seed, Tuple const& tuple)
26+
{
27+
HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
28+
hash_combine(seed, get<Index>(tuple));
29+
}
30+
};
31+
32+
template <class Tuple>
33+
struct HashValueImpl<Tuple,0>
34+
{
35+
static void apply(size_t& seed, Tuple const& tuple)
36+
{
37+
hash_combine(seed, get<0>(tuple));
38+
}
39+
};
40+
}
41+
42+
template <typename ... TT>
43+
struct hash<std::tuple<TT...>>
44+
{
45+
size_t
46+
operator()(std::tuple<TT...> const& tt) const
47+
{
48+
size_t seed = 0;
49+
HashValueImpl<std::tuple<TT...> >::apply(seed, tt);
50+
return seed;
51+
}
52+
53+
};
54+
}
55+
56+
#endif

0 commit comments

Comments
 (0)
0