From b6634dff2cd515d9e6f95416512db893a08bde29 Mon Sep 17 00:00:00 2001 From: Chris Dyer Date: Thu, 21 Apr 2011 18:06:31 -0400 Subject: adding functionality to fast_sparse_vector, getting ready for transition to it --- utils/fast_sparse_vector.h | 191 +++++++++++++++++++++++++++++++++++++++++---- utils/feature_vector.h | 1 - utils/sparse_vector.cc | 3 +- utils/sparse_vector.h | 9 +++ utils/ts.cc | 41 +++++++--- 5 files changed, 216 insertions(+), 29 deletions(-) diff --git a/utils/fast_sparse_vector.h b/utils/fast_sparse_vector.h index 91bf441d..c4a44b99 100644 --- a/utils/fast_sparse_vector.h +++ b/utils/fast_sparse_vector.h @@ -1,47 +1,102 @@ #ifndef _FAST_SPARSE_VECTOR_H_ #define _FAST_SPARSE_VECTOR_H_ +// FastSparseVector is a integer indexed unordered map that supports very fast +// (mathematical) vector operations when the sizes are very small, and reasonably +// fast operations when the sizes are large. +// important: indexes are integers +// important: iterators may return elements in any order + +#include +#include #include #include +#include #include -// these are architecture dependent, they should be +// this is architecture dependent, it should be // detected in some way but it's probably easiest (for me) -// to just set them +// to just set it #define L2_CACHE_LINE 128 -// this should just be a typedef to pair on the new c++ +// this should just be a typedef to pair on the new c++ template -struct PairIntFloat { +struct PairIntT { int first; T second; - const PairIntFloat& operator=(const std::pair& v) { + const PairIntT& operator=(const std::pair& v) { first = v.first; second = v.second; return *this; } - operator const std::pair&() const { - return *reinterpret_cast*>(this); + operator const std::pair&() const { + return *reinterpret_cast*>(this); } }; -BOOST_STATIC_ASSERT(sizeof(PairIntFloat) == sizeof(std::pair)); +BOOST_STATIC_ASSERT(sizeof(PairIntT) == sizeof(std::pair)); template class FastSparseVector { + public: + struct const_iterator { + const_iterator(const FastSparseVector& v, const bool is_end) : local_(v.is_local_) { + if (local_) { + local_it_ = &v.data_.local[is_end ? v.local_size_ : 0]; + } else { + if (is_end) + remote_it_ = v.data_.rbmap->end(); + else + remote_it_ = v.data_.rbmap->begin(); + } + } + const bool local_; + const PairIntT* local_it_; + typename std::map::const_iterator remote_it_; + const std::pair& operator*() const { + if (local_) + return *reinterpret_cast*>(local_it_); + else + return *remote_it_; + } + + const std::pair* operator->() const { + if (local_) + return reinterpret_cast*>(local_it_); + else + return &*remote_it_; + } + + const_iterator& operator++() { + if (local_) ++local_it_; else ++remote_it_; + return *this; + } + + inline bool operator==(const const_iterator& o) const { + if (o.local_ != local_) return false; + if (local_) { + return local_it_ == o.local_it_; + } else { + return remote_it_ == o.remote_it_; + } + } + inline bool operator!=(const const_iterator& o) const { + return !(o == *this); + } + }; public: FastSparseVector() : local_size_(0), is_local_(true) {} ~FastSparseVector() { if (!is_local_) delete data_.rbmap; } FastSparseVector(const FastSparseVector& other) { - memcpy(this, &other, sizeof(FastSparseVector)); + std::memcpy(this, &other, sizeof(FastSparseVector)); if (is_local_) return; data_.rbmap = new std::map(*data_.rbmap); } const FastSparseVector& operator=(const FastSparseVector& other) { if (!is_local_) delete data_.rbmap; - memcpy(this, &other, sizeof(FastSparseVector)); + std::memcpy(this, &other, sizeof(FastSparseVector)); if (is_local_) return *this; data_.rbmap = new std::map(*data_.rbmap); return *this; @@ -52,11 +107,11 @@ class FastSparseVector { inline T value(int k) const { if (is_local_) { for (int i = 0; i < local_size_; ++i) { - const PairIntFloat& p = data_.local[i]; + const PairIntT& p = data_.local[i]; if (p.first == k) return p.second; } } else { - std::map::const_iterator it = data_.rbmap->find(k); + typename std::map::const_iterator it = data_.rbmap->find(k); if (it != data_.rbmap->end()) return it->second; } return T(); @@ -73,13 +128,67 @@ class FastSparseVector { return size() == 0; } inline FastSparseVector& operator+=(const FastSparseVector& other) { - if (!is_local_) { - } else if (!other.is_local_) { - } else { // both local + if (empty()) { *this = other; return *this; } + const typename FastSparseVector::const_iterator end = other.end(); + for (typename FastSparseVector::const_iterator it = other.begin(); it != end; ++it) { + get_or_create_bin(it->first) += it->second; + } + return *this; + } + inline FastSparseVector& operator-=(const FastSparseVector& other) { + const typename FastSparseVector::const_iterator end = other.end(); + for (typename FastSparseVector::const_iterator it = other.begin(); it != end; ++it) { + get_or_create_bin(it->first) -= it->second; } return *this; } + inline FastSparseVector& operator*=(const T& scalar) { + if (is_local_) { + for (int i = 0; i < local_size_; ++i) + data_.local[i].second *= scalar; + } else { + const typename std::map::iterator end = data_.rbmap->end(); + for (typename std::map::iterator it = data_.rbmap->begin(); it != end; ++it) + it->second *= scalar; + } + return *this; + } + inline FastSparseVector& operator/=(const T& scalar) { + if (is_local_) { + for (int i = 0; i < local_size_; ++i) + data_.local[i].second /= scalar; + } else { + const typename std::map::iterator end = data_.rbmap->end(); + for (typename std::map::iterator it = data_.rbmap->begin(); it != end; ++it) + it->second /= scalar; + } + return *this; + } + const_iterator begin() const { + return const_iterator(*this, false); + } + const_iterator end() const { + return const_iterator(*this, true); + } + void init_vector(std::vector *vp) const { + init_vector(*vp); + } + void init_vector(std::vector &v) const { + v.clear(); + for (const_iterator i=begin(),e=end();i!=e;++i) + extend_vector(v,i->first)=i->second; + } + T dot(const std::vector& v) const { + T res = T(); + for (const_iterator it = begin(), e = end(); it != e; ++it) + if (it->first < v.size()) res += it->second * v[it->first]; + } private: + inline T& extend_vector(std::vector &v,int i) { + if (i>=v.size()) + v.resize(i+1); + return v[i]; + } inline T& get_or_create_bin(int k) { if (is_local_) { for (int i = 0; i < local_size_; ++i) @@ -90,7 +199,7 @@ class FastSparseVector { assert(is_local_); // currently local! if (local_size_ < LOCAL_MAX) { - PairIntFloat& p = data_.local[local_size_]; + PairIntT& p = data_.local[local_size_]; ++local_size_; p.first = k; return p.second; @@ -119,17 +228,65 @@ class FastSparseVector { } union { - PairIntFloat local[LOCAL_MAX]; + PairIntT local[LOCAL_MAX]; std::map* rbmap; } data_; unsigned char local_size_; bool is_local_; }; +template +const FastSparseVector operator+(const FastSparseVector& x, const FastSparseVector& y) { + if (x.size() > y.size()) { + FastSparseVector res(x); + res += y; + return res; + } else { + FastSparseVector res(y); + res += x; + return res; + } +} + +template +const FastSparseVector operator-(const FastSparseVector& x, const FastSparseVector& y) { + if (x.size() > y.size()) { + FastSparseVector res(x); + res -= y; + return res; + } else { + FastSparseVector res(y); + res -= x; + return res; + } +} + namespace performance_checks { // if you get a failure on the next line, you should adjust LOCAL_MAX for // your architecture BOOST_STATIC_ASSERT(sizeof(FastSparseVector) == L2_CACHE_LINE); }; +#include "fdict.h" + +template +inline void print(O &o,const FastSparseVector& v, const char* kvsep="=",const char* pairsep=" ",const char* pre="",const char* post="") { + o << pre; + bool first=true; + for (typename FastSparseVector::const_iterator i=v.begin(),e=v.end();i!=e;++i) { + if (first) + first=false; + else + o<first)<second; + } + o << post; +} + +template +inline std::ostream& operator<<(std::ostream& out, const FastSparseVector& v) { + print(out, v); + return out; +} + #endif diff --git a/utils/feature_vector.h b/utils/feature_vector.h index be378a6a..733aa99e 100755 --- a/utils/feature_vector.h +++ b/utils/feature_vector.h @@ -6,7 +6,6 @@ #include "fdict.h" typedef double Featval; -typedef SparseVectorList FeatureVectorList; typedef SparseVector FeatureVector; typedef SparseVector WeightVector; typedef std::vector DenseWeightVector; diff --git a/utils/sparse_vector.cc b/utils/sparse_vector.cc index 6e42a216..24da5f39 100644 --- a/utils/sparse_vector.cc +++ b/utils/sparse_vector.cc @@ -3,6 +3,7 @@ #include #include +#include "fdict.h" #include "b64tools.h" using namespace std; @@ -10,7 +11,7 @@ using namespace std; namespace B64 { void Encode(double objective, const SparseVector& v, ostream* out) { - const int num_feats = v.num_active(); + const int num_feats = v.size(); size_t tot_size = 0; const size_t off_objective = tot_size; tot_size += sizeof(double); // objective diff --git a/utils/sparse_vector.h b/utils/sparse_vector.h index 1bcb9502..de8c0291 100644 --- a/utils/sparse_vector.h +++ b/utils/sparse_vector.h @@ -1,6 +1,8 @@ #ifndef _SPARSE_VECTOR_H_ #define _SPARSE_VECTOR_H_ +#undef USE_FAST_SPARSE_VECTOR +#ifndef USE_FAST_SPARSE_VECTOR /* TODO: specialize for int value types, where it probably makes sense to check if adding/subtracting brings a value to 0, and remove it from the map (e.g. in a gibbs sampler). or add a separate policy argument for that. */ @@ -667,6 +669,13 @@ std::ostream &operator<<(std::ostream &out, const SparseVector &vec) return vec.operator<<(out); } +#else + +#include "fast_sparse_vector.h" +#define SparseVector FastSparseVector + +#endif + namespace B64 { void Encode(double objective, const SparseVector& v, std::ostream* out); // returns false if failed to decode diff --git a/utils/ts.cc b/utils/ts.cc index 1febed3c..28b5f9b1 100644 --- a/utils/ts.cc +++ b/utils/ts.cc @@ -10,25 +10,46 @@ using namespace std; +template +void Print(const T& x) { + typename T::const_iterator it = x.begin(); + for (; it != x.end(); ++it) { + cerr << it->first << ":" << it->second << " "; + } + cerr << endl; +} + +template +void test_unique() { + T x; + x.set_value(100, 1.0); + x.set_value(100, 2.0); + Print(x); + assert(x.size() == 1); + assert(x.value(100) == 2.0); +} + int main() { cerr << sizeof(prob_t) << " " << sizeof(LogVal) << endl; cerr << " sizeof(FSV) = " << sizeof(FastSparseVector) << endl; cerr << "sizeof(FSV) = " << sizeof(FastSparseVector) << endl; - sranddev(); + test_unique >(); +// sranddev(); int c = 0; + FastSparseVector p; for (int i = 0; i < 1000000; ++i) { FastSparseVector x; - //SparseVector x; - for (int j = 0; j < 15; ++j) { - const int k = rand() % 1000; - const float v = rand() / 3.14f; + for (int j = 0; j < 10; ++j) { + const int k = rand() % 200; + const float v = 1000.0f / rand(); x.set_value(k,v); } - //SparseVector y = x; - FastSparseVector y = x; - y += x; - y = x; - if (y.value(50)) { c++; } + if (x.value(50)) { c++; } + p = x; + p += p; + FastSparseVector y = p + p; + y *= 2; + y -= y; } cerr << "Counted " << c << " times\n"; return 0; -- cgit v1.2.3