Browse code

dense sampler appears to be working

Tom Sherman authored on 15/10/2018 20:52:28
Showing1 changed files
1 1
deleted file mode 100644
... ...
@@ -1,72 +0,0 @@
1
-#ifndef __COGAPS_ATOMIC_DOMAIN_H__
2
-#define __COGAPS_ATOMIC_DOMAIN_H__
3
-
4
-#include "AtomAllocator.h"
5
-#include "data_structures/HashSets.h"
6
-#include "math/Random.h"
7
-#include "math/SIMD.h"
8
-#include "utils/Archive.h"
9
-
10
-#include <vector>
11
-
12
-struct AtomNeighborhood
13
-{
14
-    Atom* center;
15
-    Atom* left;
16
-    Atom* right;
17
-
18
-    AtomNeighborhood();
19
-    AtomNeighborhood(Atom *l, Atom *c, Atom *r);
20
-
21
-    bool hasLeft();
22
-    bool hasRight();
23
-};
24
-
25
-class ProposalQueue; // needed for friend
26
-
27
-class AtomicDomain
28
-{
29
-public:
30
-
31
-    AtomicDomain(uint64_t nBins);
32
-
33
-    // TODO can we have internal rng since these are always called sequentially
34
-    // access atoms
35
-    Atom* front();
36
-    Atom* randomAtom(GapsRng *rng);
37
-    AtomNeighborhood randomAtomWithNeighbors(GapsRng *rng);
38
-    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng);
39
-
40
-    uint64_t randomFreePosition(GapsRng *rng) const;
41
-    uint64_t size() const;
42
-
43
-    // this needs to happen concurrently without invalidating pointers
44
-    void erase(uint64_t pos);
45
-
46
-    // serialization
47
-    friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
48
-    friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
49
-   
50
-#ifdef GAPS_DEBUG
51
-    std::vector<Atom*>::iterator begin();
52
-    std::vector<Atom*>::iterator end();
53
-    bool isSorted();
54
-#endif
55
-
56
-#ifndef GAPS_INTERNAL_TESTS
57
-private:
58
-#endif
59
-
60
-    // only the proposal queue can insert
61
-    friend class ProposalQueue;
62
-    Atom* insert(uint64_t pos, float mass);
63
-
64
-    // size of atomic domain to ensure all bins are equal length
65
-    uint64_t mDomainLength;
66
-
67
-    // domain storage, sorted vector of pointers to atoms created by allocator
68
-    std::vector<Atom*> mAtoms;
69
-    AtomAllocator mAllocator;
70
-};
71
-
72
-#endif // __COGAPS_ATOMIC_DOMAIN_H__
Browse code

no longer crashing with checkpoints; still not consistent

Tom Sherman authored on 01/10/2018 17:41:04
Showing1 changed files
... ...
@@ -30,6 +30,7 @@ public:
30 30
 
31 31
     AtomicDomain(uint64_t nBins);
32 32
 
33
+    // TODO can we have internal rng since these are always called sequentially
33 34
     // access atoms
34 35
     Atom* front();
35 36
     Atom* randomAtom(GapsRng *rng);
Browse code

simplified gibbs calculation

Tom Sherman authored on 26/09/2018 23:09:37
Showing1 changed files
... ...
@@ -47,8 +47,8 @@ public:
47 47
     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
48 48
    
49 49
 #ifdef GAPS_DEBUG
50
-    std::vector<Atom*>::iterator begin() { return mAtoms.begin(); }
51
-    std::vector<Atom*>::iterator end() { return mAtoms.end(); }
50
+    std::vector<Atom*>::iterator begin();
51
+    std::vector<Atom*>::iterator end();
52 52
     bool isSorted();
53 53
 #endif
54 54
 
Browse code

better scheme for allocating atoms

Tom Sherman authored on 19/09/2018 23:11:01
Showing1 changed files
... ...
@@ -1,26 +1,14 @@
1 1
 #ifndef __COGAPS_ATOMIC_DOMAIN_H__
2 2
 #define __COGAPS_ATOMIC_DOMAIN_H__
3 3
 
4
+#include "AtomAllocator.h"
4 5
 #include "data_structures/HashSets.h"
5 6
 #include "math/Random.h"
7
+#include "math/SIMD.h"
6 8
 #include "utils/Archive.h"
7 9
 
8 10
 #include <vector>
9 11
 
10
-struct Atom
11
-{
12
-    uint64_t pos;
13
-    float mass;
14
-
15
-    Atom();
16
-    Atom(uint64_t p, float m);
17
-
18
-    void operator=(Atom other);
19
-
20
-    friend Archive& operator<<(Archive& ar, Atom &a);
21
-    friend Archive& operator>>(Archive& ar, Atom &a);
22
-};
23
-
24 12
 struct AtomNeighborhood
25 13
 {
26 14
     Atom* center;
... ...
@@ -41,34 +29,28 @@ class AtomicDomain
41 29
 public:
42 30
 
43 31
     AtomicDomain(uint64_t nBins);
44
-    ~AtomicDomain();
45 32
 
46 33
     // access atoms
47 34
     Atom* front();
48
-    Atom* randomAtom(GapsRng *rng, const SmallPairedHashSetU64 &moves);
35
+    Atom* randomAtom(GapsRng *rng);
49 36
     AtomNeighborhood randomAtomWithNeighbors(GapsRng *rng);
50
-    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng, const SmallPairedHashSetU64 &moves);
37
+    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng);
51 38
 
52
-    Atom* getLeftNeighbor(uint64_t pos);
53
-    Atom* getRightNeighbor(uint64_t pos);
54
-
55
-    uint64_t randomFreePosition(GapsRng *rng,
56
-        const std::vector<uint64_t> &possibleDeaths) const;
39
+    uint64_t randomFreePosition(GapsRng *rng) const;
57 40
     uint64_t size() const;
58 41
 
59
-    // these need to happen concurrently without invalidating pointers
42
+    // this needs to happen concurrently without invalidating pointers
60 43
     void erase(uint64_t pos);
61
-    //void move(uint64_t src, uint64_t dest);
62
-
63
-    // iterators
64
-    std::vector<Atom*>::iterator begin() { return mAtoms.begin(); }
65
-    std::vector<Atom*>::iterator end() { return mAtoms.end(); }
66
-    
67
-    bool isSorted();
68 44
 
69 45
     // serialization
70 46
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
71 47
     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
48
+   
49
+#ifdef GAPS_DEBUG
50
+    std::vector<Atom*>::iterator begin() { return mAtoms.begin(); }
51
+    std::vector<Atom*>::iterator end() { return mAtoms.end(); }
52
+    bool isSorted();
53
+#endif
72 54
 
73 55
 #ifndef GAPS_INTERNAL_TESTS
74 56
 private:
... ...
@@ -81,8 +63,9 @@ private:
81 63
     // size of atomic domain to ensure all bins are equal length
82 64
     uint64_t mDomainLength;
83 65
 
84
-    // domain storage, sorted vector
66
+    // domain storage, sorted vector of pointers to atoms created by allocator
85 67
     std::vector<Atom*> mAtoms;
68
+    AtomAllocator mAllocator;
86 69
 };
87 70
 
88
-#endif // __COGAPS_ATOMIC_DOMAIN_H__
89 71
\ No newline at end of file
72
+#endif // __COGAPS_ATOMIC_DOMAIN_H__
Browse code

consistent with or without queue

Tom Sherman authored on 19/09/2018 17:33:40
Showing1 changed files
... ...
@@ -1,8 +1,9 @@
1 1
 #ifndef __COGAPS_ATOMIC_DOMAIN_H__
2 2
 #define __COGAPS_ATOMIC_DOMAIN_H__
3 3
 
4
-#include "utils/Archive.h"
4
+#include "data_structures/HashSets.h"
5 5
 #include "math/Random.h"
6
+#include "utils/Archive.h"
6 7
 
7 8
 #include <vector>
8 9
 
... ...
@@ -44,9 +45,9 @@ public:
44 45
 
45 46
     // access atoms
46 47
     Atom* front();
47
-    Atom* randomAtom(GapsRng *rng);
48
+    Atom* randomAtom(GapsRng *rng, const SmallPairedHashSetU64 &moves);
48 49
     AtomNeighborhood randomAtomWithNeighbors(GapsRng *rng);
49
-    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng);
50
+    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng, const SmallPairedHashSetU64 &moves);
50 51
 
51 52
     Atom* getLeftNeighbor(uint64_t pos);
52 53
     Atom* getRightNeighbor(uint64_t pos);
... ...
@@ -57,7 +58,7 @@ public:
57 58
 
58 59
     // these need to happen concurrently without invalidating pointers
59 60
     void erase(uint64_t pos);
60
-    void move(uint64_t src, uint64_t dest);
61
+    //void move(uint64_t src, uint64_t dest);
61 62
 
62 63
     // iterators
63 64
     std::vector<Atom*>::iterator begin() { return mAtoms.begin(); }
Browse code

more debugging

Tom Sherman authored on 12/09/2018 13:52:44
Showing1 changed files
... ...
@@ -59,6 +59,12 @@ public:
59 59
     void erase(uint64_t pos);
60 60
     void move(uint64_t src, uint64_t dest);
61 61
 
62
+    // iterators
63
+    std::vector<Atom*>::iterator begin() { return mAtoms.begin(); }
64
+    std::vector<Atom*>::iterator end() { return mAtoms.end(); }
65
+    
66
+    bool isSorted();
67
+
62 68
     // serialization
63 69
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
64 70
     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
Browse code

more work on consistency of queue

Tom Sherman authored on 09/09/2018 18:52:57
Showing1 changed files
... ...
@@ -33,6 +33,8 @@ struct AtomNeighborhood
33 33
     bool hasRight();
34 34
 };
35 35
 
36
+class ProposalQueue; // needed for friend
37
+
36 38
 class AtomicDomain
37 39
 {
38 40
 public:
... ...
@@ -49,12 +51,13 @@ public:
49 51
     Atom* getLeftNeighbor(uint64_t pos);
50 52
     Atom* getRightNeighbor(uint64_t pos);
51 53
 
52
-    uint64_t randomFreePosition(GapsRng *rng) const;
54
+    uint64_t randomFreePosition(GapsRng *rng,
55
+        const std::vector<uint64_t> &possibleDeaths) const;
53 56
     uint64_t size() const;
54 57
 
55 58
     // these need to happen concurrently without invalidating pointers
56 59
     void erase(uint64_t pos);
57
-    Atom* insert(uint64_t pos, float mass);
60
+    void move(uint64_t src, uint64_t dest);
58 61
 
59 62
     // serialization
60 63
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
... ...
@@ -64,6 +67,10 @@ public:
64 67
 private:
65 68
 #endif
66 69
 
70
+    // only the proposal queue can insert
71
+    friend class ProposalQueue;
72
+    Atom* insert(uint64_t pos, float mass);
73
+
67 74
     // size of atomic domain to ensure all bins are equal length
68 75
     uint64_t mDomainLength;
69 76
 
Browse code

changes

Tom Sherman authored on 07/09/2018 18:32:13
Showing1 changed files
... ...
@@ -26,6 +26,7 @@ struct AtomNeighborhood
26 26
     Atom* left;
27 27
     Atom* right;
28 28
 
29
+    AtomNeighborhood();
29 30
     AtomNeighborhood(Atom *l, Atom *c, Atom *r);
30 31
 
31 32
     bool hasLeft();
... ...
@@ -37,6 +38,7 @@ class AtomicDomain
37 38
 public:
38 39
 
39 40
     AtomicDomain(uint64_t nBins);
41
+    ~AtomicDomain();
40 42
 
41 43
     // access atoms
42 44
     Atom* front();
... ...
@@ -44,11 +46,15 @@ public:
44 46
     AtomNeighborhood randomAtomWithNeighbors(GapsRng *rng);
45 47
     AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng);
46 48
 
49
+    Atom* getLeftNeighbor(uint64_t pos);
50
+    Atom* getRightNeighbor(uint64_t pos);
51
+
47 52
     uint64_t randomFreePosition(GapsRng *rng) const;
48 53
     uint64_t size() const;
49 54
 
55
+    // these need to happen concurrently without invalidating pointers
50 56
     void erase(uint64_t pos);
51
-    void insert(uint64_t pos, float mass);
57
+    Atom* insert(uint64_t pos, float mass);
52 58
 
53 59
     // serialization
54 60
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
... ...
@@ -62,7 +68,7 @@ private:
62 68
     uint64_t mDomainLength;
63 69
 
64 70
     // domain storage, sorted vector
65
-    std::vector<Atom> mAtoms;
71
+    std::vector<Atom*> mAtoms;
66 72
 };
67 73
 
68
-#endif
69 74
\ No newline at end of file
75
+#endif // __COGAPS_ATOMIC_DOMAIN_H__
70 76
\ No newline at end of file
Browse code

basic framework in place for full async

Tom Sherman authored on 29/08/2018 21:41:05
Showing1 changed files
... ...
@@ -40,11 +40,11 @@ public:
40 40
 
41 41
     // access atoms
42 42
     Atom* front();
43
-    Atom* randomAtom();
44
-    AtomNeighborhood randomAtomWithNeighbors();
45
-    AtomNeighborhood randomAtomWithRightNeighbor();
43
+    Atom* randomAtom(GapsRng *rng);
44
+    AtomNeighborhood randomAtomWithNeighbors(GapsRng *rng);
45
+    AtomNeighborhood randomAtomWithRightNeighbor(GapsRng *rng);
46 46
 
47
-    uint64_t randomFreePosition() const;
47
+    uint64_t randomFreePosition(GapsRng *rng) const;
48 48
     uint64_t size() const;
49 49
 
50 50
     void erase(uint64_t pos);
... ...
@@ -63,9 +63,6 @@ private:
63 63
 
64 64
     // domain storage, sorted vector
65 65
     std::vector<Atom> mAtoms;
66
-
67
-    // random number generator
68
-    mutable GapsRng mRng;
69 66
 };
70 67
 
71 68
 #endif
72 69
\ No newline at end of file
Browse code

started making changes

Tom Sherman authored on 28/08/2018 19:53:08
Showing1 changed files
... ...
@@ -1,7 +1,7 @@
1 1
 #ifndef __COGAPS_ATOMIC_DOMAIN_H__
2 2
 #define __COGAPS_ATOMIC_DOMAIN_H__
3 3
 
4
-#include "Archive.h"
4
+#include "utils/Archive.h"
5 5
 #include "math/Random.h"
6 6
 
7 7
 #include <vector>
... ...
@@ -47,11 +47,8 @@ public:
47 47
     uint64_t randomFreePosition() const;
48 48
     uint64_t size() const;
49 49
 
50
-    // modify domain
51
-    void cacheInsert(uint64_t pos, float mass) const;
52
-    void cacheErase(uint64_t pos) const;
53
-    void flushCache();
54
-    void resetCache(unsigned n);
50
+    void erase(uint64_t pos);
51
+    void insert(uint64_t pos, float mass);
55 52
 
56 53
     // serialization
57 54
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
... ...
@@ -67,23 +64,8 @@ private:
67 64
     // domain storage, sorted vector
68 65
     std::vector<Atom> mAtoms;
69 66
 
70
-    // holds cache of operations
71
-    mutable std::vector<Atom> mInsertCache;
72
-    mutable std::vector<uint64_t> mEraseCache;
73
-
74
-    // current index in the operation cache
75
-    mutable unsigned mInsertCacheIndex;
76
-    mutable unsigned mEraseCacheIndex;
77
-
78 67
     // random number generator
79 68
     mutable GapsRng mRng;
80
-
81
-    void erase(uint64_t pos);
82
-    void insert(uint64_t pos, float mass);
83
-
84
-    // serialization
85
-    friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
86
-    friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
87 69
 };
88 70
 
89 71
 #endif
90 72
\ No newline at end of file
Browse code

added checkpoint versioning

Tom Sherman authored on 23/08/2018 19:29:47
Showing1 changed files
... ...
@@ -36,7 +36,7 @@ class AtomicDomain
36 36
 {
37 37
 public:
38 38
 
39
-    AtomicDomain(unsigned nBins);
39
+    AtomicDomain(uint64_t nBins);
40 40
 
41 41
     // access atoms
42 42
     Atom* front();
... ...
@@ -64,7 +64,7 @@ private:
64 64
     // size of atomic domain to ensure all bins are equal length
65 65
     uint64_t mDomainLength;
66 66
 
67
-    // domain storage, specialized hash map
67
+    // domain storage, sorted vector
68 68
     std::vector<Atom> mAtoms;
69 69
 
70 70
     // holds cache of operations
Browse code

use a sorted vector for atomic domain

Tom Sherman authored on 23/08/2018 17:53:21
Showing1 changed files
... ...
@@ -5,7 +5,6 @@
5 5
 #include "math/Random.h"
6 6
 
7 7
 #include <vector>
8
-#include <set>
9 8
 
10 9
 struct Atom
11 10
 {
... ...
@@ -33,147 +32,12 @@ struct AtomNeighborhood
33 32
     bool hasRight();
34 33
 };
35 34
 
36
-class AtomBucket
37
-{
38
-public:
39
-
40
-    AtomBucket();
41
-
42
-    unsigned size() const;
43
-    bool isEmpty() const;
44
-    bool contains(uint64_t pos) const;
45
-
46
-    Atom* front();
47
-    Atom* operator[](unsigned index);
48
-
49
-    void insert(uint64_t pos, float mass);
50
-    void erase(uint64_t pos);
51
-        
52
-    AtomNeighborhood getNeighbors(unsigned index);
53
-    AtomNeighborhood getRightNeighbor(unsigned index);
54
-
55
-    void setRightAdjacentBucket(AtomBucket *bucket);
56
-    void setLeftAdjacentBucket(AtomBucket *bucket);
57
-
58
-    Atom* getLeft(unsigned index);
59
-    Atom* getRight(unsigned index);
60
-
61
-#ifndef GAPS_INTERNAL_TESTS
62
-private:
63
-#endif
64
-
65
-    Atom mBucket[2];
66
-    uint32_t mSize;
67
-    
68
-    AtomBucket *mOverflow;
69
-    AtomBucket *mPrev;
70
-    AtomBucket *mNext;
71
-
72
-    void eraseFront();
73
-    void connectAdjacent();
74
-
75
-    Atom* back();
76
-
77
-    AtomBucket& operator=(const AtomBucket& other); // prevent copies
78
-    
79
-    friend Archive& operator<<(Archive& ar, AtomBucket &b);
80
-    friend Archive& operator>>(Archive& ar, AtomBucket &b);
81
-};
82
-
83
-struct HashMapIndex
84
-{
85
-    unsigned bucket;
86
-    unsigned index;
87
-
88
-    HashMapIndex(unsigned b, unsigned i) : bucket(b), index(i) {}
89
-};
90
-
91
-// hash map of chained AtomBuckets
92
-// data structure that holds atoms
93
-// accessing happens much more than insert/erase so more time is spent
94
-// up front (sorting) to save time on access
95
-// note that atoms can never occupy position 0
96
-class AtomHashMap
97
-{
98
-public:
99
-
100
-    // required that length is a multiple of expectedNumAtoms
101
-    AtomHashMap(unsigned expectedNumAtoms);
102
-    void setTotalLength(uint64_t length);
103
-
104
-    // TODO while moving the atoms cannot change the atom order, it can
105
-    // move an atom from one bucket to another - this moved atom must be
106
-    // the front atom moving to the back of the prev bucket or the back
107
-    // atom moving to the front of the next atom - effectively creating
108
-    // a reorder event - it may even need allocation
109
-
110
-    Atom* front();
111
-    Atom* randomAtom();
112
-    AtomNeighborhood randomAtomWithNeighbors();
113
-    AtomNeighborhood randomAtomWithRightNeighbor();
114
-
115
-    bool contains(uint64_t pos) const;
116
-    unsigned size() const;
117
-
118
-    void insert(uint64_t pos, float mass);
119
-    void erase(uint64_t pos);
120
-    void move(uint64_t src, uint64_t dest, float mass); // cannot reorder
121
-
122
-    Atom* getLeft(uint64_t pos);
123
-    Atom* getRight(uint64_t pos);
124
-
125
-    bool hasLeft(uint64_t pos);
126
-    bool hasRight(uint64_t pos);
127
-
128
-    void updateMass(uint64_t pos, float newMass);
129
-
130
-#ifndef GAPS_INTERNAL_TESTS
131
-private:
132
-#endif
133
-
134
-    unsigned mSize;
135
-    unsigned mWhichLongestBucket;
136
-    unsigned mLongestBucketSize;
137
-
138
-    unsigned mExpectedNumAtoms;
139
-
140
-    uint64_t mBucketLength;
141
-    uint64_t mTotalLength;
142
-
143
-    std::vector<AtomBucket> mHashMap;
144
-    std::set<unsigned> mFullBuckets; // TODO use IntFixedHashSet
145
-
146
-    // random number generator
147
-    mutable GapsRng mRng;
148
-
149
-    unsigned hash(uint64_t pos) const;
150
-    HashMapIndex getRandomIndex() const;
151
-
152
-    friend Archive& operator<<(Archive& ar, AtomHashMap &h);
153
-    friend Archive& operator>>(Archive& ar, AtomHashMap &h);
154
-};
155
-
156
-struct MoveOperation
157
-{
158
-    uint64_t src;
159
-    uint64_t dest;
160
-    float mass;
161
-
162
-    MoveOperation() : src(0), dest(0), mass(0.f) {}
163
-
164
-    MoveOperation(uint64_t s, uint64_t d, float m) :
165
-        src(s), dest(d), mass(m)
166
-    {}
167
-};
168
-
169 35
 class AtomicDomain
170 36
 {
171 37
 public:
172 38
 
173 39
     AtomicDomain(unsigned nBins);
174 40
 
175
-    void setDomainSize(uint64_t size);
176
-
177 41
     // access atoms
178 42
     Atom* front();
179 43
     Atom* randomAtom();
... ...
@@ -186,7 +50,6 @@ public:
186 50
     // modify domain
187 51
     void cacheInsert(uint64_t pos, float mass) const;
188 52
     void cacheErase(uint64_t pos) const;
189
-    void cacheMove(uint64_t src, uint64_t dest, float mass) const;
190 53
     void flushCache();
191 54
     void resetCache(unsigned n);
192 55
 
... ...
@@ -194,27 +57,30 @@ public:
194 57
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
195 58
     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
196 59
 
60
+#ifndef GAPS_INTERNAL_TESTS
197 61
 private:
62
+#endif
198 63
 
199 64
     // size of atomic domain to ensure all bins are equal length
200 65
     uint64_t mDomainLength;
201 66
 
202 67
     // domain storage, specialized hash map
203
-    mutable AtomHashMap mAtoms;
68
+    std::vector<Atom> mAtoms;
204 69
 
205 70
     // holds cache of operations
206 71
     mutable std::vector<Atom> mInsertCache;
207 72
     mutable std::vector<uint64_t> mEraseCache;
208
-    mutable std::vector<MoveOperation> mMoveCache;
209 73
 
210 74
     // current index in the operation cache
211 75
     mutable unsigned mInsertCacheIndex;
212 76
     mutable unsigned mEraseCacheIndex;
213
-    mutable unsigned mMoveCacheIndex;
214 77
 
215 78
     // random number generator
216 79
     mutable GapsRng mRng;
217 80
 
81
+    void erase(uint64_t pos);
82
+    void insert(uint64_t pos, float mass);
83
+
218 84
     // serialization
219 85
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
220 86
     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
Browse code

working but inconsistent and slow

Tom Sherman authored on 22/08/2018 20:02:28
Showing1 changed files
... ...
@@ -55,9 +55,6 @@ public:
55 55
     void setRightAdjacentBucket(AtomBucket *bucket);
56 56
     void setLeftAdjacentBucket(AtomBucket *bucket);
57 57
 
58
-    AtomBucket& operator=(const AtomBucket& other);
59
-
60
-    unsigned getIndex(uint64_t pos);
61 58
     Atom* getLeft(unsigned index);
62 59
     Atom* getRight(unsigned index);
63 60
 
... ...
@@ -65,8 +62,8 @@ public:
65 62
 private:
66 63
 #endif
67 64
 
68
-    Atom mBucket;
69
-    bool mFull;
65
+    Atom mBucket[2];
66
+    uint32_t mSize;
70 67
     
71 68
     AtomBucket *mOverflow;
72 69
     AtomBucket *mPrev;
... ...
@@ -76,6 +73,8 @@ private:
76 73
     void connectAdjacent();
77 74
 
78 75
     Atom* back();
76
+
77
+    AtomBucket& operator=(const AtomBucket& other); // prevent copies
79 78
     
80 79
     friend Archive& operator<<(Archive& ar, AtomBucket &b);
81 80
     friend Archive& operator>>(Archive& ar, AtomBucket &b);
Browse code

single sized buckets working

Tom Sherman authored on 22/08/2018 17:56:50
Showing1 changed files
... ...
@@ -4,109 +4,218 @@
4 4
 #include "Archive.h"
5 5
 #include "math/Random.h"
6 6
 
7
-#include <boost/unordered_map.hpp>
8
-
9
-#include <cstddef>
10
-#include <map>
11
-#include <stdint.h>
12 7
 #include <vector>
8
+#include <set>
13 9
 
14
-class AtomicDomain;
15
-
16
-// Want the neighbors to be pointers, but can't use pointers since vector
17
-// is resized, shifted integers allow for 0 to be "null" and 1 to be the
18
-// first index. AtomicDomain is responsible for managing this correctly.
19
-// TODO use get/set neighbor
20 10
 struct Atom
21 11
 {
22
-private:    
12
+    uint64_t pos;
13
+    float mass;
23 14
 
24
-    friend class AtomicDomain;
25
-    uint64_t leftNdx; // shift these up 1, 0 == no neighbor
26
-    uint64_t rightNdx;
15
+    Atom();
16
+    Atom(uint64_t p, float m);
27 17
 
28
-public:    
18
+    void operator=(Atom other);
29 19
 
30
-    uint64_t pos;
31
-    float mass;
20
+    friend Archive& operator<<(Archive& ar, Atom &a);
21
+    friend Archive& operator>>(Archive& ar, Atom &a);
22
+};
32 23
 
33
-    Atom(uint64_t p, float m)
34
-        : leftNdx(0), rightNdx(0), pos(p), mass(m)
35
-    {}
24
+struct AtomNeighborhood
25
+{
26
+    Atom* center;
27
+    Atom* left;
28
+    Atom* right;
36 29
 
37
-    bool operator==(const Atom &other) const
38
-    {
39
-        return pos == other.pos;
40
-    }
30
+    AtomNeighborhood(Atom *l, Atom *c, Atom *r);
41 31
 
42
-    bool operator!=(const Atom &other) const
43
-    {
44
-        return !(pos == other.pos);
45
-    }
32
+    bool hasLeft();
33
+    bool hasRight();
34
+};
46 35
 
47
-    // serialization
48
-    friend Archive& operator<<(Archive &ar, Atom &a);
49
-    friend Archive& operator>>(Archive &ar, Atom &a);
36
+class AtomBucket
37
+{
38
+public:
39
+
40
+    AtomBucket();
41
+
42
+    unsigned size() const;
43
+    bool isEmpty() const;
44
+    bool contains(uint64_t pos) const;
45
+
46
+    Atom* front();
47
+    Atom* operator[](unsigned index);
48
+
49
+    void insert(uint64_t pos, float mass);
50
+    void erase(uint64_t pos);
51
+        
52
+    AtomNeighborhood getNeighbors(unsigned index);
53
+    AtomNeighborhood getRightNeighbor(unsigned index);
54
+
55
+    void setRightAdjacentBucket(AtomBucket *bucket);
56
+    void setLeftAdjacentBucket(AtomBucket *bucket);
57
+
58
+    AtomBucket& operator=(const AtomBucket& other);
59
+
60
+    unsigned getIndex(uint64_t pos);
61
+    Atom* getLeft(unsigned index);
62
+    Atom* getRight(unsigned index);
63
+
64
+#ifndef GAPS_INTERNAL_TESTS
65
+private:
66
+#endif
67
+
68
+    Atom mBucket;
69
+    bool mFull;
70
+    
71
+    AtomBucket *mOverflow;
72
+    AtomBucket *mPrev;
73
+    AtomBucket *mNext;
74
+
75
+    void eraseFront();
76
+    void connectAdjacent();
77
+
78
+    Atom* back();
79
+    
80
+    friend Archive& operator<<(Archive& ar, AtomBucket &b);
81
+    friend Archive& operator>>(Archive& ar, AtomBucket &b);
50 82
 };
51 83
 
52
-struct RawAtom
84
+struct HashMapIndex
53 85
 {
54
-    uint64_t pos;
55
-    float mass;
86
+    unsigned bucket;
87
+    unsigned index;
56 88
 
57
-    RawAtom() : pos(0), mass(0.f) {}
58
-    RawAtom(uint64_t p, float m) : pos(p), mass(m) {}
89
+    HashMapIndex(unsigned b, unsigned i) : bucket(b), index(i) {}
59 90
 };
60 91
 
92
+// hash map of chained AtomBuckets
61 93
 // data structure that holds atoms
62
-class AtomicDomain
94
+// accessing happens much more than insert/erase so more time is spent
95
+// up front (sorting) to save time on access
96
+// note that atoms can never occupy position 0
97
+class AtomHashMap
63 98
 {
99
+public:
100
+
101
+    // required that length is a multiple of expectedNumAtoms
102
+    AtomHashMap(unsigned expectedNumAtoms);
103
+    void setTotalLength(uint64_t length);
104
+
105
+    // TODO while moving the atoms cannot change the atom order, it can
106
+    // move an atom from one bucket to another - this moved atom must be
107
+    // the front atom moving to the back of the prev bucket or the back
108
+    // atom moving to the front of the next atom - effectively creating
109
+    // a reorder event - it may even need allocation
110
+
111
+    Atom* front();
112
+    Atom* randomAtom();
113
+    AtomNeighborhood randomAtomWithNeighbors();
114
+    AtomNeighborhood randomAtomWithRightNeighbor();
115
+
116
+    bool contains(uint64_t pos) const;
117
+    unsigned size() const;
118
+
119
+    void insert(uint64_t pos, float mass);
120
+    void erase(uint64_t pos);
121
+    void move(uint64_t src, uint64_t dest, float mass); // cannot reorder
122
+
123
+    Atom* getLeft(uint64_t pos);
124
+    Atom* getRight(uint64_t pos);
125
+
126
+    bool hasLeft(uint64_t pos);
127
+    bool hasRight(uint64_t pos);
128
+
129
+    void updateMass(uint64_t pos, float newMass);
130
+
131
+#ifndef GAPS_INTERNAL_TESTS
64 132
 private:
133
+#endif
65 134
 
66
-    // size of atomic domain
67
-    uint64_t mDomainSize;
135
+    unsigned mSize;
136
+    unsigned mWhichLongestBucket;
137
+    unsigned mLongestBucketSize;
68 138
 
69
-    // domain storage
70
-    std::vector<Atom> mAtoms;
71
-    std::map<uint64_t, uint64_t> mAtomPositions;
72
-    boost::unordered_map<uint64_t, uint64_t> mPositionLookup;
139
+    unsigned mExpectedNumAtoms;
73 140
 
74
-    mutable std::vector<RawAtom> mInsertCache;
75
-    mutable std::vector<uint64_t> mEraseCache;
141
+    uint64_t mBucketLength;
142
+    uint64_t mTotalLength;
76 143
 
77
-    mutable unsigned mInsertCacheIndex;
78
-    mutable unsigned mEraseCacheIndex;
144
+    std::vector<AtomBucket> mHashMap;
145
+    std::set<unsigned> mFullBuckets; // TODO use IntFixedHashSet
79 146
 
147
+    // random number generator
80 148
     mutable GapsRng mRng;
81 149
 
82
-    Atom& _left(const Atom &atom);
83
-    Atom& _right(const Atom &atom);
150
+    unsigned hash(uint64_t pos) const;
151
+    HashMapIndex getRandomIndex() const;
84 152
 
85
-    void erase(uint64_t pos);
86
-    Atom insert(uint64_t pos, float mass);
153
+    friend Archive& operator<<(Archive& ar, AtomHashMap &h);
154
+    friend Archive& operator>>(Archive& ar, AtomHashMap &h);
155
+};
156
+
157
+struct MoveOperation
158
+{
159
+    uint64_t src;
160
+    uint64_t dest;
161
+    float mass;
162
+
163
+    MoveOperation() : src(0), dest(0), mass(0.f) {}
164
+
165
+    MoveOperation(uint64_t s, uint64_t d, float m) :
166
+        src(s), dest(d), mass(m)
167
+    {}
168
+};
87 169
 
170
+class AtomicDomain
171
+{
88 172
 public:
89 173
 
90
-    void setDomainSize(uint64_t size) { mDomainSize = size; }
174
+    AtomicDomain(unsigned nBins);
175
+
176
+    void setDomainSize(uint64_t size);
91 177
 
92 178
     // access atoms
93
-    Atom front() const;
94
-    Atom randomAtom() const;
179
+    Atom* front();
180
+    Atom* randomAtom();
181
+    AtomNeighborhood randomAtomWithNeighbors();
182
+    AtomNeighborhood randomAtomWithRightNeighbor();
183
+
95 184
     uint64_t randomFreePosition() const;
96 185
     uint64_t size() const;
97 186
 
98
-    const Atom& left(const Atom &atom) const;
99
-    const Atom& right(const Atom &atom) const;
100
-    bool hasLeft(const Atom &atom) const;
101
-    bool hasRight(const Atom &atom) const;
102
-
103 187
     // modify domain
104 188
     void cacheInsert(uint64_t pos, float mass) const;
105 189
     void cacheErase(uint64_t pos) const;
106
-    void updateMass(uint64_t pos, float newMass);
190
+    void cacheMove(uint64_t src, uint64_t dest, float mass) const;
107 191
     void flushCache();
108 192
     void resetCache(unsigned n);
109 193
 
194
+    // serialization
195
+    friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
196
+    friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
197
+
198
+private:
199
+
200
+    // size of atomic domain to ensure all bins are equal length
201
+    uint64_t mDomainLength;
202
+
203
+    // domain storage, specialized hash map
204
+    mutable AtomHashMap mAtoms;
205
+
206
+    // holds cache of operations
207
+    mutable std::vector<Atom> mInsertCache;
208
+    mutable std::vector<uint64_t> mEraseCache;
209
+    mutable std::vector<MoveOperation> mMoveCache;
210
+
211
+    // current index in the operation cache
212
+    mutable unsigned mInsertCacheIndex;
213
+    mutable unsigned mEraseCacheIndex;
214
+    mutable unsigned mMoveCacheIndex;
215
+
216
+    // random number generator
217
+    mutable GapsRng mRng;
218
+
110 219
     // serialization
111 220
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
112 221
     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
Browse code

lazily bundled rng

Tom Sherman authored on 15/08/2018 16:25:00
Showing1 changed files
... ...
@@ -2,6 +2,7 @@
2 2
 #define __COGAPS_ATOMIC_DOMAIN_H__
3 3
 
4 4
 #include "Archive.h"
5
+#include "math/Random.h"
5 6
 
6 7
 #include <boost/unordered_map.hpp>
7 8
 
... ...
@@ -15,6 +16,7 @@ class AtomicDomain;
15 16
 // Want the neighbors to be pointers, but can't use pointers since vector
16 17
 // is resized, shifted integers allow for 0 to be "null" and 1 to be the
17 18
 // first index. AtomicDomain is responsible for managing this correctly.
19
+// TODO use get/set neighbor
18 20
 struct Atom
19 21
 {
20 22
 private:    
... ...
@@ -75,6 +77,8 @@ private:
75 77
     mutable unsigned mInsertCacheIndex;
76 78
     mutable unsigned mEraseCacheIndex;
77 79
 
80
+    mutable GapsRng mRng;
81
+
78 82
     Atom& _left(const Atom &atom);
79 83
     Atom& _right(const Atom &atom);
80 84
 
Browse code

added lookup table for updating atom mass

Tom Sherman authored on 13/08/2018 15:18:30
Showing1 changed files
... ...
@@ -3,7 +3,7 @@
3 3
 
4 4
 #include "Archive.h"
5 5
 
6
-#include <boost/unordered_set.hpp>
6
+#include <boost/unordered_map.hpp>
7 7
 
8 8
 #include <cstddef>
9 9
 #include <map>
... ...
@@ -67,8 +67,7 @@ private:
67 67
     // domain storage
68 68
     std::vector<Atom> mAtoms;
69 69
     std::map<uint64_t, uint64_t> mAtomPositions;
70
-
71
-    boost::unordered_set<uint64_t> mUsedPositions;
70
+    boost::unordered_map<uint64_t, uint64_t> mPositionLookup;
72 71
 
73 72
     mutable std::vector<RawAtom> mInsertCache;
74 73
     mutable std::vector<uint64_t> mEraseCache;
Browse code

prevent atomic from resizing and accessing at the same time

Tom Sherman authored on 21/06/2018 21:19:37
Showing1 changed files
... ...
@@ -79,6 +79,9 @@ private:
79 79
     Atom& _left(const Atom &atom);
80 80
     Atom& _right(const Atom &atom);
81 81
 
82
+    void erase(uint64_t pos);
83
+    Atom insert(uint64_t pos, float mass);
84
+
82 85
 public:
83 86
 
84 87
     void setDomainSize(uint64_t size) { mDomainSize = size; }
... ...
@@ -95,8 +98,6 @@ public:
95 98
     bool hasRight(const Atom &atom) const;
96 99
 
97 100
     // modify domain
98
-    Atom insert(uint64_t pos, float mass);
99
-    void erase(uint64_t pos);
100 101
     void cacheInsert(uint64_t pos, float mass) const;
101 102
     void cacheErase(uint64_t pos) const;
102 103
     void updateMass(uint64_t pos, float newMass);
Browse code

added back PUMP and FixedPatterns option

Tom Sherman authored on 13/06/2018 21:35:14
Showing1 changed files
... ...
@@ -43,8 +43,8 @@ public:
43 43
     }
44 44
 
45 45
     // serialization
46
-    friend Archive& operator<<(Archive &ar, Atom &domain);
47
-    friend Archive& operator>>(Archive &ar, Atom &domain);
46
+    friend Archive& operator<<(Archive &ar, Atom &a);
47
+    friend Archive& operator>>(Archive &ar, Atom &a);
48 48
 };
49 49
 
50 50
 struct RawAtom
Browse code

restore serialization

Tom Sherman authored on 11/06/2018 23:46:44
Showing1 changed files
... ...
@@ -17,8 +17,7 @@ class AtomicDomain;
17 17
 // first index. AtomicDomain is responsible for managing this correctly.
18 18
 struct Atom
19 19
 {
20
-//private:    
21
-public: // TODO
20
+private:    
22 21
 
23 22
     friend class AtomicDomain;
24 23
     uint64_t leftNdx; // shift these up 1, 0 == no neighbor
... ...
@@ -42,6 +41,10 @@ public:
42 41
     {
43 42
         return !(pos == other.pos);
44 43
     }
44
+
45
+    // serialization
46
+    friend Archive& operator<<(Archive &ar, Atom &domain);
47
+    friend Archive& operator>>(Archive &ar, Atom &domain);
45 48
 };
46 49
 
47 50
 struct RawAtom
Browse code

constructor order

Tom Sherman authored on 11/06/2018 16:54:17
Showing1 changed files
... ...
@@ -30,7 +30,7 @@ public:
30 30
     float mass;
31 31
 
32 32
     Atom(uint64_t p, float m)
33
-        : pos(p), mass(m), leftNdx(0), rightNdx(0)
33
+        : leftNdx(0), rightNdx(0), pos(p), mass(m)
34 34
     {}
35 35
 
36 36
     bool operator==(const Atom &other) const
Browse code

added TODO

Tom Sherman authored on 05/06/2018 14:50:37
Showing1 changed files
... ...
@@ -18,7 +18,7 @@ class AtomicDomain;
18 18
 struct Atom
19 19
 {
20 20
 //private:    
21
-public:
21
+public: // TODO
22 22
 
23 23
     friend class AtomicDomain;
24 24
     uint64_t leftNdx; // shift these up 1, 0 == no neighbor
Browse code

make linter happy

Tom Sherman authored on 03/06/2018 23:57:18
Showing1 changed files
... ...
@@ -4,10 +4,11 @@
4 4
 #include "Archive.h"
5 5
 
6 6
 #include <boost/unordered_set.hpp>
7
-#include <stdint.h>
7
+
8 8
 #include <cstddef>
9
-#include <vector>
10 9
 #include <map>
10
+#include <stdint.h>
11
+#include <vector>
11 12
 
12 13
 class AtomicDomain;
13 14
 
Browse code

make lintr happy

Tom Sherman authored on 31/05/2018 21:28:52
Showing1 changed files
... ...
@@ -19,7 +19,7 @@ struct Atom
19 19
 //private:    
20 20
 public:
21 21
 
22
-    friend AtomicDomain;
22
+    friend class AtomicDomain;
23 23
     uint64_t leftNdx; // shift these up 1, 0 == no neighbor
24 24
     uint64_t rightNdx;
25 25
 
Browse code

added crude time estimate

Tom Sherman authored on 22/05/2018 15:05:30
Showing1 changed files
... ...
@@ -64,7 +64,6 @@ private:
64 64
     std::vector<Atom> mAtoms;
65 65
     std::map<uint64_t, uint64_t> mAtomPositions;
66 66
 
67
-    // TODO google_dense_set - first profile and benchmark
68 67
     boost::unordered_set<uint64_t> mUsedPositions;
69 68
 
70 69
     mutable std::vector<RawAtom> mInsertCache;
Browse code

parallel status in build report

Tom Sherman authored on 14/05/2018 18:50:26
Showing1 changed files
... ...
@@ -78,8 +78,6 @@ private:
78 78
 
79 79
 public:
80 80
 
81
-    AtomicDomain();
82
-
83 81
     void setDomainSize(uint64_t size) { mDomainSize = size; }
84 82
 
85 83
     // access atoms
Browse code

atomicdomain set up to be thread safe

Tom Sherman authored on 10/05/2018 18:51:29
Showing1 changed files
... ...
@@ -43,6 +43,15 @@ public:
43 43
     }
44 44
 };
45 45
 
46
+struct RawAtom
47
+{
48
+    uint64_t pos;
49
+    float mass;
50
+
51
+    RawAtom() : pos(0), mass(0.f) {}
52
+    RawAtom(uint64_t p, float m) : pos(p), mass(m) {}
53
+};
54
+
46 55
 // data structure that holds atoms
47 56
 class AtomicDomain
48 57
 {
... ...
@@ -58,6 +67,15 @@ private:
58 67
     // TODO google_dense_set - first profile and benchmark
59 68
     boost::unordered_set<uint64_t> mUsedPositions;
60 69
 
70
+    mutable std::vector<RawAtom> mInsertCache;
71
+    mutable std::vector<uint64_t> mEraseCache;
72
+
73
+    mutable unsigned mInsertCacheIndex;
74
+    mutable unsigned mEraseCacheIndex;
75
+
76
+    Atom& _left(const Atom &atom);
77
+    Atom& _right(const Atom &atom);
78
+
61 79
 public:
62 80
 
63 81
     AtomicDomain();
... ...
@@ -70,8 +88,6 @@ public:
70 88
     uint64_t randomFreePosition() const;
71 89
     uint64_t size() const;
72 90
 
73
-    Atom& left(const Atom &atom);
74
-    Atom& right(const Atom &atom);
75 91
     const Atom& left(const Atom &atom) const;
76 92
     const Atom& right(const Atom &atom) const;
77 93
     bool hasLeft(const Atom &atom) const;
... ...
@@ -80,11 +96,15 @@ public:
80 96
     // modify domain
81 97
     Atom insert(uint64_t pos, float mass);
82 98
     void erase(uint64_t pos);
99
+    void cacheInsert(uint64_t pos, float mass) const;
100
+    void cacheErase(uint64_t pos) const;
83 101
     void updateMass(uint64_t pos, float newMass);
102
+    void flushCache();
103
+    void resetCache(unsigned n);
84 104
 
85 105
     // serialization
86 106
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
87 107
     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
88 108
 };
89 109
 
90
-#endif
110
+#endif
91 111
\ No newline at end of file
Browse code

parallelization appears to be working

Tom Sherman authored on 09/05/2018 21:27:17
Showing1 changed files
... ...
@@ -60,6 +60,8 @@ private:
60 60
 
61 61
 public:
62 62
 
63
+    AtomicDomain();
64
+
63 65
     void setDomainSize(uint64_t size) { mDomainSize = size; }
64 66
 
65 67
     // access atoms
Browse code

full conflict checks in place; need to optimize and test

Tom Sherman authored on 07/05/2018 18:31:59
Showing1 changed files
... ...
@@ -76,7 +76,7 @@ public:
76 76
     bool hasRight(const Atom &atom) const;
77 77
 
78 78
     // modify domain
79
-    void insert(uint64_t pos, float mass);
79
+    Atom insert(uint64_t pos, float mass);
80 80
     void erase(uint64_t pos);
81 81
     void updateMass(uint64_t pos, float newMass);
82 82
 
Browse code

cleaned up - ready to parallelize

Tom Sherman authored on 04/05/2018 21:23:09
Showing1 changed files
... ...
@@ -48,6 +48,9 @@ class AtomicDomain
48 48
 {
49 49
 private:
50 50
 
51
+    // size of atomic domain
52
+    uint64_t mDomainSize;
53
+
51 54
     // domain storage
52 55
     std::vector<Atom> mAtoms;
53 56
     std::map<uint64_t, uint64_t> mAtomPositions;
... ...
@@ -57,6 +60,8 @@ private:
57 60
 
58 61
 public:
59 62
 
63
+    void setDomainSize(uint64_t size) { mDomainSize = size; }
64
+
60 65
     // access atoms
61 66
     Atom front() const;
62 67
     Atom randomAtom() const;
Browse code

removed debug asserts

Tom Sherman authored on 03/05/2018 21:10:48
Showing1 changed files
... ...
@@ -75,8 +75,6 @@ public:
75 75
     void erase(uint64_t pos);
76 76
     void updateMass(uint64_t pos, float newMass);
77 77
 
78
-    bool test(uint64_t pos) const;
79
-
80 78
     // serialization
81 79
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
82 80
     friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
Browse code

running cleanly, algo still off

sherman5 authored on 17/04/2018 21:37:06
Showing1 changed files
... ...
@@ -36,6 +36,11 @@ public:
36 36
     {
37 37
         return pos == other.pos;
38 38
     }
39
+
40
+    bool operator!=(const Atom &other) const
41
+    {
42
+        return !(pos == other.pos);
43
+    }
39 44
 };
40 45
 
41 46
 // data structure that holds atoms
... ...
@@ -67,10 +72,10 @@ public:
67 72
 
68 73
     // modify domain
69 74
     void insert(uint64_t pos, float mass);
70
-    void swap(uint64_t i1, uint64_t i2);
71
-    void erase(uint64_t pos, bool display=false);
75
+    void erase(uint64_t pos);
72 76
     void updateMass(uint64_t pos, float newMass);
73
-    void test(uint64_t pos) const;
77
+
78
+    bool test(uint64_t pos) const;
74 79
 
75 80
     // serialization
76 81
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
Browse code

debugging

sherman5 authored on 17/04/2018 18:45:37
Showing1 changed files
... ...
@@ -1,5 +1,5 @@
1
-#ifndef __GAPS_ATOMIC_DOMAIN_H__
2
-#define __GAPS_ATOMIC_DOMAIN_H__
1
+#ifndef __COGAPS_ATOMIC_DOMAIN_H__
2
+#define __COGAPS_ATOMIC_DOMAIN_H__
3 3
 
4 4
 #include "Archive.h"
5 5
 
... ...
@@ -9,16 +9,27 @@
9 9
 #include <vector>
10 10
 #include <map>
11 11
 
12
+class AtomicDomain;
13
+
14
+// Want the neighbors to be pointers, but can't use pointers since vector
15
+// is resized, shifted integers allow for 0 to be "null" and 1 to be the
16
+// first index. AtomicDomain is responsible for managing this correctly.
12 17
 struct Atom
13 18
 {
19
+//private:    
20
+public:
21
+
22
+    friend AtomicDomain;
23
+    uint64_t leftNdx; // shift these up 1, 0 == no neighbor
24
+    uint64_t rightNdx;
25
+
26
+public:    
27
+
14 28
     uint64_t pos;
15 29
     float mass;
16 30
 
17
-    Atom* left;
18
-    Atom* right;
19
-    
20 31
     Atom(uint64_t p, float m)
21
-        : pos(p), mass(m), left(NULL), right(NULL)
32
+        : pos(p), mass(m), leftNdx(0), rightNdx(0)
22 33
     {}
23 34
 
24 35
     bool operator==(const Atom &other) const
... ...
@@ -45,12 +56,21 @@ public:
45 56
     Atom front() const;
46 57
     Atom randomAtom() const;
47 58
     uint64_t randomFreePosition() const;
48
-    unsigned size() const;
59
+    uint64_t size() const;
60
+
61
+    Atom& left(const Atom &atom);
62
+    Atom& right(const Atom &atom);
63
+    const Atom& left(const Atom &atom) const;
64
+    const Atom& right(const Atom &atom) const;
65
+    bool hasLeft(const Atom &atom) const;
66
+    bool hasRight(const Atom &atom) const;
49 67
 
50 68
     // modify domain
51 69
     void insert(uint64_t pos, float mass);
52
-    void erase(uint64_t pos);
70
+    void swap(uint64_t i1, uint64_t i2);
71
+    void erase(uint64_t pos, bool display=false);
53 72
     void updateMass(uint64_t pos, float newMass);
73
+    void test(uint64_t pos) const;
54 74
 
55 75
     // serialization
56 76
     friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
Browse code

separated gibbs samplers

sherman5 authored on 07/03/2018 22:59:17
Showing1 changed files
... ...
@@ -3,6 +3,7 @@
3 3
 
4 4
 #include "Archive.h"
5 5
 
6
+#include <boost/unordered_set.hpp>
6 7
 #include <stdint.h>
7 8
 #include <cstddef>
8 9
 #include <vector>
... ...
@@ -35,11 +36,16 @@ private:
35 36
     std::vector<Atom> mAtoms;
36 37
     std::map<uint64_t, uint64_t> mAtomPositions;
37 38
 
39
+    // TODO google_dense_set - first profile and benchmark
40
+    boost::unordered_set<uint64_t> mUsedPositions;
41
+
38 42
 public:
39 43
 
44
+    // access atoms
40 45
     Atom front() const;
41 46
     Atom randomAtom() const;
42 47
     uint64_t randomFreePosition() const;
48
+    unsigned size() const;
43 49
 
44 50
     // modify domain
45 51
     void insert(uint64_t pos, float mass);
Browse code

stripped down version of async cogaps

sherman5 authored on 15/02/2018 22:10:36
Showing1 changed files
... ...
@@ -1,24 +1,12 @@
1 1
 #ifndef __GAPS_ATOMIC_DOMAIN_H__
2 2
 #define __GAPS_ATOMIC_DOMAIN_H__
3 3
 
4
-// data structure that holds atoms
5
-class AtomicDomain
6
-{
7
-private:
8
-
9
-public:
10
-
11
-    AtomicDomain();
12
-    
13
-    uint64_t randomAtomPosition();
14
-    uint64_t randomFreePosition();
15
-
16
-    float updateMass(uint64_t pos, float delta);
17
-
18
-};
19
-
20
-#endif
4
+#include "Archive.h"
21 5
 
6
+#include <stdint.h>
7
+#include <cstddef>
8
+#include <vector>
9
+#include <map>
22 10
 
23 11
 struct Atom
24 12
 {
... ...
@@ -29,32 +17,38 @@ struct Atom
29 17
     Atom* right;
30 18
     
31 19
     Atom(uint64_t p, float m)
32
-        : pos(p), mass(m), left(nullptr), right(nullptr)
20
+        : pos(p), mass(m), left(NULL), right(NULL)
33 21
     {}
34
-};
35 22
 
36
-void insertAtom(uint64_t p, float m)
37
-{
38
-    std::map<uint64_t, Atom>::const_iterator it, left, right;
39
-    it = mAtoms.insert(std::pair<uint64_t, Atom>(p, Atom(p,m))).first;
40
-    
41
-    std::map<uint64_t, Atom>::const_iterator left(it), right(it);
42
-    if (it != mAtoms.begin())
23
+    bool operator==(const Atom &other) const
43 24
     {
44
-        --left;
25
+        return pos == other.pos;
45 26
     }
46
-    if (++it != mAtoms.end())
47
-    {
48
-        ++right;
49
-    }
50
-    it->left = &left;
51
-    it->right = &right;
52
-}
27
+};
53 28
 
29
+// data structure that holds atoms
30
+class AtomicDomain
31
+{
32
+private:
54 33
 
34
+    // domain storage
35
+    std::vector<Atom> mAtoms;
36
+    std::map<uint64_t, uint64_t> mAtomPositions;
55 37
 
56
-void removeAtom(const Atom &atom)
57
-{
58
-    atom.left.right = atom.right;
59
-    atom.right.left = atom.left;
60
-}
38
+public:
39
+
40
+    Atom front() const;
41
+    Atom randomAtom() const;
42
+    uint64_t randomFreePosition() const;
43
+
44
+    // modify domain
45
+    void insert(uint64_t pos, float mass);
46
+    void erase(uint64_t pos);
47
+    void updateMass(uint64_t pos, float newMass);
48
+
49
+    // serialization
50
+    friend Archive& operator<<(Archive &ar, AtomicDomain &domain);
51
+    friend Archive& operator>>(Archive &ar, AtomicDomain &domain);
52
+};
53
+
54
+#endif
Browse code

more framework

sherman5 authored on 14/02/2018 18:44:00
Showing1 changed files
1 1
new file mode 100644
... ...
@@ -0,0 +1,60 @@
1
+#ifndef __GAPS_ATOMIC_DOMAIN_H__
2
+#define __GAPS_ATOMIC_DOMAIN_H__
3
+
4
+// data structure that holds atoms
5
+class AtomicDomain
6
+{
7
+private:
8
+
9
+public:
10
+
11
+    AtomicDomain();
12
+    
13