From d484433d9ad566076b7d078c77443ce7841f4f3e Mon Sep 17 00:00:00 2001 From: graehl Date: Fri, 16 Jul 2010 22:08:37 +0000 Subject: smallvector template git-svn-id: https://ws10smt.googlecode.com/svn/trunk@302 ec762483-ff6d-05da-a07a-a48fb63a330f --- decoder/apply_models.cc | 2 +- decoder/hg.h | 2 +- decoder/hg_io.cc | 8 +++--- decoder/kbest.h | 12 ++++---- decoder/maxtrans_blunsom.cc | 4 +-- decoder/small_vector.h | 65 +++++++++++++++++++++++--------------------- decoder/small_vector_test.cc | 28 +++++++++---------- 7 files changed, 62 insertions(+), 59 deletions(-) diff --git a/decoder/apply_models.cc b/decoder/apply_models.cc index 240bd12b..ba573984 100644 --- a/decoder/apply_models.cc +++ b/decoder/apply_models.cc @@ -18,7 +18,7 @@ using namespace std; using namespace std::tr1; struct Candidate; -typedef SmallVector JVector; +typedef SmallVectorInt JVector; typedef vector CandidateHeap; typedef vector CandidateList; diff --git a/decoder/hg.h b/decoder/hg.h index a21a7acf..53b5a53d 100644 --- a/decoder/hg.h +++ b/decoder/hg.h @@ -22,7 +22,7 @@ class Hypergraph { Hypergraph() : is_linear_chain_(false) {} // SmallVector is a fast, small vector implementation for sizes <= 2 - typedef SmallVector TailNodeVector; + typedef SmallVectorInt TailNodeVector; // TODO get rid of cat_? // TODO keep cat_ and add span and/or state? :) diff --git a/decoder/hg_io.cc b/decoder/hg_io.cc index 6a5561e6..d6e73b8a 100644 --- a/decoder/hg_io.cc +++ b/decoder/hg_io.cc @@ -27,7 +27,7 @@ struct HGReader : public JSONParser { hg.ConnectEdgeToHeadNode(&hg.edges_[in_edges[i]], node); } } - void CreateEdge(const TRulePtr& rule, SparseVector* feats, const SmallVector& tail) { + void CreateEdge(const TRulePtr& rule, FeatureVector* feats, const SmallVectorInt& tail) { Hypergraph::Edge* edge = hg.AddEdge(rule, tail); feats->swap(edge->feature_values_); edge->i_ = spans[0]; @@ -228,7 +228,7 @@ struct HGReader : public JSONParser { } string rp; string cat; - SmallVector tail; + SmallVectorInt tail; vector in_edges; TRulePtr cur_rule; map rules; @@ -524,7 +524,7 @@ void ReadPLFNode(const std::string& in, int &c, int cur_node, int line, Hypergra } } -} // namespace PLF +} // namespace PLF void HypergraphIO::ReadFromPLF(const std::string& in, Hypergraph* hg, int line) { hg->clear(); @@ -644,7 +644,7 @@ void b64encode(const char* data, const size_t size, ostream* out) { } } -static void decodeblock(const unsigned char* in, unsigned char* out) { +static void decodeblock(const unsigned char* in, unsigned char* out) { out[0] = (unsigned char ) (in[0] << 2 | in[1] >> 4); out[1] = (unsigned char ) (in[1] << 4 | in[2] >> 2); out[2] = (unsigned char ) (((in[2] << 6) & 0xc0) | in[3]); diff --git a/decoder/kbest.h b/decoder/kbest.h index fcd40fcd..35e79bcc 100644 --- a/decoder/kbest.h +++ b/decoder/kbest.h @@ -49,7 +49,7 @@ namespace KBest { struct Derivation { Derivation(const Hypergraph::Edge& e, - const SmallVector& jv, + const SmallVectorInt& jv, const WeightType& w, const SparseVector& f) : edge(&e), @@ -59,11 +59,11 @@ namespace KBest { // dummy constructor, just for query Derivation(const Hypergraph::Edge& e, - const SmallVector& jv) : edge(&e), j(jv) {} + const SmallVectorInt& jv) : edge(&e), j(jv) {} T yield; const Hypergraph::Edge* const edge; - const SmallVector j; + const SmallVectorInt j; const WeightType score; const SparseVector feature_values; }; @@ -141,7 +141,7 @@ namespace KBest { // the yield is computed in LazyKthBest before the derivation is added to D // returns NULL if j refers to derivation numbers larger than the // antecedent structure define - Derivation* CreateDerivation(const Hypergraph::Edge& e, const SmallVector& j) { + Derivation* CreateDerivation(const Hypergraph::Edge& e, const SmallVectorInt& j) { WeightType score = w(e); SparseVector feats = e.feature_values_; for (int i = 0; i < e.Arity(); ++i) { @@ -161,7 +161,7 @@ namespace KBest { const Hypergraph::Node& node = g.nodes_[v]; for (int i = 0; i < node.in_edges_.size(); ++i) { const Hypergraph::Edge& edge = g.edges_[node.in_edges_[i]]; - SmallVector jv(edge.Arity(), 0); + SmallVectorInt jv(edge.Arity(), 0); Derivation* d = CreateDerivation(edge, jv); assert(d); s.cand.push_back(d); @@ -178,7 +178,7 @@ namespace KBest { void LazyNext(const Derivation* d, CandidateHeap* cand, UniqueDerivationSet* ds) { for (int i = 0; i < d->j.size(); ++i) { - SmallVector j = d->j; + SmallVectorInt j = d->j; ++j[i]; const Derivation* ant = LazyKthBest(d->edge->tail_nodes_[i], j[i]); if (ant) { diff --git a/decoder/maxtrans_blunsom.cc b/decoder/maxtrans_blunsom.cc index 34e175db..6efab454 100644 --- a/decoder/maxtrans_blunsom.cc +++ b/decoder/maxtrans_blunsom.cc @@ -19,7 +19,7 @@ using namespace std::tr1; namespace Hack { struct Candidate; -typedef SmallVector JVector; +typedef SmallVectorInt JVector; typedef vector CandidateHeap; typedef vector CandidateList; @@ -188,7 +188,7 @@ public: new_edge->edge_prob_ = item->out_edge_.edge_prob_; Candidate*& o_item = (*s2n)[item->state_]; if (!o_item) o_item = item; - + int& node_id = o_item->node_index_; if (node_id < 0) { Hypergraph::Node* new_node = out.AddNode(in.nodes_[item->in_edge_->head_node_].cat_); diff --git a/decoder/small_vector.h b/decoder/small_vector.h index 2c61ab3a..e5c314de 100644 --- a/decoder/small_vector.h +++ b/decoder/small_vector.h @@ -5,16 +5,17 @@ #include #include -#define __SV_MAX_STATIC 2 - +//sizeof(T)/sizeof(T*)>1?sizeof(T)/sizeof(T*):1 +template class SmallVector { - + typedef unsigned short uint16_t; public: + typedef SmallVector Self; SmallVector() : size_(0) {} explicit SmallVector(size_t s, int v = 0) : size_(s) { assert(s < 0x80); - if (s <= __SV_MAX_STATIC) { + if (s <= SV_MAX) { for (int i = 0; i < s; ++i) data_.vals[i] = v; } else { capacity_ = s; @@ -24,9 +25,9 @@ class SmallVector { } } - SmallVector(const SmallVector& o) : size_(o.size_) { - if (size_ <= __SV_MAX_STATIC) { - for (int i = 0; i < __SV_MAX_STATIC; ++i) data_.vals[i] = o.data_.vals[i]; + SmallVector(const Self& o) : size_(o.size_) { + if (size_ <= SV_MAX) { + for (int i = 0; i < SV_MAX; ++i) data_.vals[i] = o.data_.vals[i]; } else { capacity_ = size_ = o.size_; data_.ptr = new int[capacity_]; @@ -34,18 +35,18 @@ class SmallVector { } } - const SmallVector& operator=(const SmallVector& o) { - if (size_ <= __SV_MAX_STATIC) { - if (o.size_ <= __SV_MAX_STATIC) { + const Self& operator=(const Self& o) { + if (size_ <= SV_MAX) { + if (o.size_ <= SV_MAX) { size_ = o.size_; - for (int i = 0; i < __SV_MAX_STATIC; ++i) data_.vals[i] = o.data_.vals[i]; + for (int i = 0; i < SV_MAX; ++i) data_.vals[i] = o.data_.vals[i]; } else { capacity_ = size_ = o.size_; data_.ptr = new int[capacity_]; std::memcpy(data_.ptr, o.data_.ptr, size_ * sizeof(int)); } } else { - if (o.size_ <= __SV_MAX_STATIC) { + if (o.size_ <= SV_MAX) { delete[] data_.ptr; size_ = o.size_; for (int i = 0; i < size_; ++i) data_.vals[i] = o.data_.vals[i]; @@ -64,12 +65,12 @@ class SmallVector { } ~SmallVector() { - if (size_ <= __SV_MAX_STATIC) return; + if (size_ <= SV_MAX) return; delete[] data_.ptr; } void clear() { - if (size_ > __SV_MAX_STATIC) { + if (size_ > SV_MAX) { delete[] data_.ptr; } size_ = 0; @@ -79,7 +80,7 @@ class SmallVector { size_t size() const { return size_; } inline void ensure_capacity(uint16_t min_size) { - assert(min_size > __SV_MAX_STATIC); + assert(min_size > SV_MAX); if (min_size < capacity_) return; uint16_t new_cap = std::max(static_cast(capacity_ << 1), min_size); int* tmp = new int[new_cap]; @@ -90,18 +91,18 @@ class SmallVector { } inline void copy_vals_to_ptr() { - capacity_ = __SV_MAX_STATIC * 2; + capacity_ = SV_MAX * 2; int* tmp = new int[capacity_]; - for (int i = 0; i < __SV_MAX_STATIC; ++i) tmp[i] = data_.vals[i]; + for (int i = 0; i < SV_MAX; ++i) tmp[i] = data_.vals[i]; data_.ptr = tmp; } inline void push_back(int v) { - if (size_ < __SV_MAX_STATIC) { + if (size_ < SV_MAX) { data_.vals[size_] = v; ++size_; return; - } else if (size_ == __SV_MAX_STATIC) { + } else if (size_ == SV_MAX) { copy_vals_to_ptr(); } else if (size_ == capacity_) { ensure_capacity(size_ + 1); @@ -116,9 +117,9 @@ class SmallVector { const int& front() const { return this->operator[](0); } void resize(size_t s, int v = 0) { - if (s <= __SV_MAX_STATIC) { - if (size_ > __SV_MAX_STATIC) { - int tmp[__SV_MAX_STATIC]; + if (s <= SV_MAX) { + if (size_ > SV_MAX) { + int tmp[SV_MAX]; for (int i = 0; i < s; ++i) tmp[i] = data_.ptr[i]; delete[] data_.ptr; for (int i = 0; i < s; ++i) data_.vals[i] = tmp[i]; @@ -135,7 +136,7 @@ class SmallVector { return; } } else { - if (size_ <= __SV_MAX_STATIC) + if (size_ <= SV_MAX) copy_vals_to_ptr(); if (s > capacity_) ensure_capacity(s); @@ -148,18 +149,18 @@ class SmallVector { } int& operator[](size_t i) { - if (size_ <= __SV_MAX_STATIC) return data_.vals[i]; + if (size_ <= SV_MAX) return data_.vals[i]; return data_.ptr[i]; } const int& operator[](size_t i) const { - if (size_ <= __SV_MAX_STATIC) return data_.vals[i]; + if (size_ <= SV_MAX) return data_.vals[i]; return data_.ptr[i]; } - bool operator==(const SmallVector& o) const { + bool operator==(const Self& o) const { if (size_ != o.size_) return false; - if (size_ <= __SV_MAX_STATIC) { + if (size_ <= SV_MAX) { for (size_t i = 0; i < size_; ++i) if (data_.vals[i] != o.data_.vals[i]) return false; return true; @@ -170,9 +171,13 @@ class SmallVector { } } + friend bool operator!=(const Self& a, const Self& b) { + return !(a==b); + } + private: union StorageType { - int vals[__SV_MAX_STATIC]; + int vals[SV_MAX]; int* ptr; }; StorageType data_; @@ -180,8 +185,6 @@ class SmallVector { uint16_t capacity_; // only defined when size_ >= __SV_MAX_STATIC }; -inline bool operator!=(const SmallVector& a, const SmallVector& b) { - return !(a==b); -} +typedef SmallVector SmallVectorInt; #endif diff --git a/decoder/small_vector_test.cc b/decoder/small_vector_test.cc index 84237791..d1d8dcab 100644 --- a/decoder/small_vector_test.cc +++ b/decoder/small_vector_test.cc @@ -12,10 +12,10 @@ class SVTest : public testing::Test { virtual void SetUp() { } virtual void TearDown() { } }; - + TEST_F(SVTest, LargerThan2) { - SmallVector v; - SmallVector v2; + SmallVectorInt v; + SmallVectorInt v2; v.push_back(0); v.push_back(1); v.push_back(2); @@ -24,7 +24,7 @@ TEST_F(SVTest, LargerThan2) { assert(v[1] == 1); assert(v[0] == 0); v2 = v; - SmallVector copy(v); + SmallVectorInt copy(v); assert(copy.size() == 3); assert(copy[0] == 0); assert(copy[1] == 1); @@ -42,12 +42,12 @@ TEST_F(SVTest, LargerThan2) { assert(v2[2] == 0); assert(v2[1] == -1); assert(v2[0] == -2); - SmallVector v3(1,1); + SmallVectorInt v3(1,1); assert(v3[0] == 1); v2 = v3; assert(v2.size() == 1); assert(v2[0] == 1); - SmallVector v4(10, 1); + SmallVectorInt v4(10, 1); assert(v4.size() == 10); assert(v4[5] == 1); assert(v4[9] == 1); @@ -56,7 +56,7 @@ TEST_F(SVTest, LargerThan2) { assert(v4[2] == 2); assert(v4[1] == 1); assert(v4[0] == 0); - SmallVector v5(10, 2); + SmallVectorInt v5(10, 2); assert(v5.size() == 10); assert(v5[7] == 2); assert(v5[0] == 2); @@ -65,7 +65,7 @@ TEST_F(SVTest, LargerThan2) { assert(v.size() == 10); assert(v[2] == 2); assert(v[9] == 2); - SmallVector cc; + SmallVectorInt cc; for (int i = 0; i < 33; ++i) cc.push_back(i); for (int i = 0; i < 33; ++i) @@ -88,10 +88,10 @@ TEST_F(SVTest, LargerThan2) { } TEST_F(SVTest, Small) { - SmallVector v; - SmallVector v1(1,0); - SmallVector v2(2,10); - SmallVector v1a(2,0); + SmallVectorInt v; + SmallVectorInt v1(1,0); + SmallVectorInt v2(2,10); + SmallVectorInt v1a(2,0); EXPECT_TRUE(v1 != v1a); EXPECT_TRUE(v1 == v1); EXPECT_EQ(v1[0], 0); @@ -101,7 +101,7 @@ TEST_F(SVTest, Small) { --v2[0]; EXPECT_EQ(v2[0], 9); EXPECT_EQ(v2[1], 11); - SmallVector v3(v2); + SmallVectorInt v3(v2); assert(v3[0] == 9); assert(v3[1] == 11); assert(!v3.empty()); @@ -118,7 +118,7 @@ TEST_F(SVTest, Small) { assert(v3[1] == 11); assert(!v3.empty()); assert(v3.size() == 2); - cerr << sizeof(SmallVector) << endl; + cerr << sizeof(SmallVectorInt) << endl; cerr << sizeof(vector) << endl; } -- cgit v1.2.3