[Assorted-commits] SF.net SVN: assorted:[1260] sandbox/trunk/src/cc
Brought to you by:
yangzhang
Menu
▾
▴
[Assorted-commits] SF.net SVN: assorted:[1260] sandbox/trunk/src/cc
|
From: <yan...@us...> - 2009-03-06 07:24:21
|
Revision: 1260
http://assorted.svn.sourceforge.net/assorted/?rev=1260&view=rev
Author: yangzhang
Date: 2009-03-06 07:24:20 +0000 (Fri, 06 Mar 2009)
Log Message:
-----------
added a journey exploring optimization of a commons::fast_map
Added Paths:
-----------
sandbox/trunk/src/cc/fast_map/
sandbox/trunk/src/cc/fast_map/Makefile
sandbox/trunk/src/cc/fast_map/README
sandbox/trunk/src/cc/fast_map/fm0.h
sandbox/trunk/src/cc/fast_map/fm1.h
sandbox/trunk/src/cc/fast_map/fm2.h
sandbox/trunk/src/cc/fast_map/fm3.h
sandbox/trunk/src/cc/fast_map/main.cc
Added: sandbox/trunk/src/cc/fast_map/Makefile
===================================================================
--- sandbox/trunk/src/cc/fast_map/Makefile (rev 0)
+++ sandbox/trunk/src/cc/fast_map/Makefile 2009-03-06 07:24:20 UTC (rev 1260)
@@ -0,0 +1,6 @@
+CXXFLAGS = -Wall -Wextra -Wconversion -Wpointer-arith -Wcast-qual -Wcast-align -Wwrite-strings -Winit-self -Wno-unused-parameter -Wparentheses -Wmissing-format-attribute -Wfloat-equal -Woverloaded-virtual -Wsign-promo -Wc++0x-compat -Wsynth -Wall -Werror -Wextra -Wstrict-null-sentinel -Wold-style-cast -Woverloaded-virtual -Wsign-promo -Wformat=2 -Winit-self -Wswitch-enum -Wunused -Wfloat-equal -Wundef -Wunsafe-loop-optimizations -Wpointer-arith -Wcast-qual -Wcast-align -Wwrite-strings -Wconversion -Wlogical-op -Wno-aggregate-return -Wno-missing-declarations -Wno-missing-field-initializers -Wmissing-format-attribute -Wpacked -Wredundant-decls -Winvalid-pch -Wlong-long -Wvolatile-register-var -O3 -DNDEBUG
+all: main
+main: fm0.h fm1.h fm2.h fm3.h
+clean:
+ rm -f main
+.PHONY: clean
Added: sandbox/trunk/src/cc/fast_map/README
===================================================================
--- sandbox/trunk/src/cc/fast_map/README (rev 0)
+++ sandbox/trunk/src/cc/fast_map/README 2009-03-06 07:24:20 UTC (rev 1260)
@@ -0,0 +1,6 @@
+This is a journey from a slow-performing hash map to a fast one, picking up
+things I learned from peeking at the google::dense_hash_map source.
+
+fm0 is the slowest
+fm3 is the fastest
+diff them to see the evolution
Added: sandbox/trunk/src/cc/fast_map/fm0.h
===================================================================
--- sandbox/trunk/src/cc/fast_map/fm0.h (rev 0)
+++ sandbox/trunk/src/cc/fast_map/fm0.h 2009-03-06 07:24:20 UTC (rev 1260)
@@ -0,0 +1,71 @@
+#include <backward/hash_fun.h>
+#include <cassert>
+#include <commons/array.h>
+#include <utility>
+
+using namespace std;
+using namespace __gnu_cxx;
+
+class fast_map0
+{
+ private:
+ static const size_t initsize = 1<<20;
+ typedef pair<int, int> entry;
+ commons::array<entry> table;
+ int empty_key, deleted_key;
+ size_t count;
+ hash<int> hasher;
+ void resize(size_t size) {
+ commons::array<entry> tmp(size);
+ for (size_t i = 0; i < size; ++i)
+ tmp[i].first = empty_key;
+ swap(table, tmp);
+ // Rehash old values over into new table.
+ for (size_t i = 0; i < tmp.size(); ++i) {
+ if (tmp[i].first != empty_key && tmp[i].first != deleted_key) {
+ (*this)[tmp[i].first] = tmp[i].second;
+ }
+ }
+ }
+ void grow() { resize(table.size() << 1); }
+ void shrink() { resize(table.size() >> 1); }
+ public:
+ fast_map0() : table(0), empty_key(0), deleted_key(0), count(0) {}
+ void set_empty_key(int k) { empty_key = k; resize(initsize); }
+ void set_deleted_key(int k) { deleted_key = k; resize(initsize); }
+ size_t size() const { return count; }
+ int &operator[](int k) {
+ size_t probe, pos = hasher(k) % table.size(), unset = -1, first_deleted = unset;
+ // Lookup. Skip over deleted entries (but remembering the first one
+ // seen as an open slot if we later decide to insert). If we find an
+ // empty spot, try returning the earlier deleted spot first. If we
+ // find the key, return that.
+ for (probe = 0; ; ++probe) {
+ assert(probe < table.size());
+ pos = (pos + probe) % table.size();
+ int &key = table[pos].first;
+ if (key == deleted_key && first_deleted == unset) {
+ first_deleted = pos;
+ } else if (key == empty_key) {
+ // Inserting new entry. Grow table if necessary.
+ ++count;
+ if (count > table.size() * 3 / 4) {
+ --count;
+ grow();
+ return (*this)[k];
+ }
+
+ // Try using an earlier-encountered deleted spot, if any.
+ if (first_deleted != unset) pos = first_deleted;
+
+ table[pos].first = k;
+ break;
+ } else if (key == k) {
+ break;
+ }
+ }
+ assert(probe < table.size());
+ assert(table[pos].first == k);
+ return table[pos].second;
+ }
+};
Added: sandbox/trunk/src/cc/fast_map/fm1.h
===================================================================
--- sandbox/trunk/src/cc/fast_map/fm1.h (rev 0)
+++ sandbox/trunk/src/cc/fast_map/fm1.h 2009-03-06 07:24:20 UTC (rev 1260)
@@ -0,0 +1,72 @@
+#include <backward/hash_fun.h>
+#include <cassert>
+#include <commons/array.h>
+#include <utility>
+
+using namespace std;
+using namespace __gnu_cxx;
+
+class fast_map1
+{
+ private:
+ static const size_t initsize = 1<<20;
+ typedef pair<int, int> entry;
+ commons::array<entry> table;
+ int empty_key, deleted_key;
+ size_t count;
+ hash<int> hasher;
+ void resize(size_t size) {
+ commons::array<entry> tmp(size);
+ for (size_t i = 0; i < size; ++i)
+ tmp[i].first = empty_key;
+ swap(table, tmp);
+ // Rehash old values over into new table.
+ for (size_t i = 0; i < tmp.size(); ++i) {
+ if (tmp[i].first != empty_key && tmp[i].first != deleted_key) {
+ (*this)[tmp[i].first] = tmp[i].second;
+ }
+ }
+ }
+ void grow() { resize(table.size() << 1); }
+ void shrink() { resize(table.size() >> 1); }
+ public:
+ fast_map1() : table(0), empty_key(0), deleted_key(0), count(0) {}
+ void set_empty_key(int k) { empty_key = k; resize(initsize); }
+ void set_deleted_key(int k) { deleted_key = k; resize(initsize); }
+ size_t size() const { return count; }
+ int &operator[](int k) {
+ size_t probe, mask = table.size() - 1, pos = hasher(k) & mask, unset = -1, first_deleted = unset;
+ // Lookup. Skip over deleted entries (but remembering the first one
+ // seen as an open slot if we later decide to insert). If we find an
+ // empty spot, try returning the earlier deleted spot first. If we
+ // find the key, return that.
+ for (probe = 0; ; ++probe) {
+ assert(probe < table.size());
+ // NOTE: using & mask instead of % table.size()
+ pos = (pos + probe) & mask;
+ int &key = table[pos].first;
+ if (key == deleted_key && first_deleted == unset) {
+ first_deleted = pos;
+ } else if (key == empty_key) {
+ // Inserting new entry. Grow table if necessary.
+ ++count;
+ if (count > table.size() * 3 / 4) {
+ --count;
+ grow();
+ return (*this)[k];
+ }
+
+ // Try using an earlier-encountered deleted spot, if any.
+ if (first_deleted != unset) pos = first_deleted;
+
+ table[pos].first = k;
+ break;
+ } else if (key == k) {
+ break;
+ }
+ }
+ assert(probe < table.size());
+ assert(table[pos].first == k);
+ return table[pos].second;
+ }
+};
Added: sandbox/trunk/src/cc/fast_map/fm2.h
===================================================================
--- sandbox/trunk/src/cc/fast_map/fm2.h (rev 0)
+++ sandbox/trunk/src/cc/fast_map/fm2.h 2009-03-06 07:24:20 UTC (rev 1260)
@@ -0,0 +1,83 @@
+#include <backward/hash_fun.h>
+#include <cassert>
+#include <commons/array.h>
+#include <utility>
+
+using namespace std;
+using namespace __gnu_cxx;
+
+class fast_map2
+{
+ private:
+ static const size_t initsize = 1<<20;
+ typedef pair<int, int> entry;
+ commons::array<entry> table;
+ int empty_key, deleted_key;
+ size_t count;
+ hash<int> hasher;
+ void resize(size_t size) {
+ commons::array<entry> tmp(size);
+ for (size_t i = 0; i < size; ++i)
+ tmp[i].first = empty_key;
+ swap(table, tmp);
+ // Rehash old values over into new table.
+ size_t mask = table.size() - 1;
+ for (size_t i = 0; i < tmp.size(); ++i) {
+ if (tmp[i].first != empty_key && tmp[i].first != deleted_key) {
+ // NOTE: second major speedup, originally:
+ // (*this)[tmp[i].first] = tmp[i].second;
+ // Don't want to simply reuse the general lookup, since we know
+ // we're starting with a blank slate.
+ size_t pos = hasher(tmp[i].first) & mask;
+ for (size_t probe = 0;
+ table[pos].first != empty_key;
+ ++probe, pos = (pos + probe) & mask) {
+ assert(probe < table.size());
+ }
+ table[pos] = tmp[pos];
+ }
+ }
+ }
+ void grow() { resize(table.size() << 1); }
+ void shrink() { resize(table.size() >> 1); }
+ public:
+ fast_map2() : table(0), empty_key(0), deleted_key(0), count(0) {}
+ void set_empty_key(int k) { empty_key = k; resize(initsize); }
+ void set_deleted_key(int k) { deleted_key = k; resize(initsize); }
+ size_t size() const { return count; }
+ int &operator[](int k) {
+ size_t probe, mask = table.size() - 1, pos = hasher(k) & mask, unset = -1, first_deleted = unset;
+ // Lookup. Skip over deleted entries (but remembering the first one
+ // seen as an open slot if we later decide to insert). If we find an
+ // empty spot, try returning the earlier deleted spot first. If we
+ // find the key, return that.
+ for (probe = 0; ; ++probe) {
+ assert(probe < table.size());
+ // NOTE: using & mask instead of % table.size()
+ pos = (pos + probe) & mask;
+ int &key = table[pos].first;
+ if (key == deleted_key && first_deleted == unset) {
+ first_deleted = pos;
+ } else if (key == empty_key) {
+ // Inserting new entry. Grow table if necessary.
+ ++count;
+ if (count > table.size() * 3 / 4) {
+ --count;
+ grow();
+ return (*this)[k];
+ }
+
+ // Try using an earlier-encountered deleted spot, if any.
+ if (first_deleted != unset) pos = first_deleted;
+
+ table[pos].first = k;
+ break;
+ } else if (key == k) {
+ break;
+ }
+ }
+ assert(probe < table.size());
+ assert(table[pos].first == k);
+ return table[pos].second;
+ }
+};
Added: sandbox/trunk/src/cc/fast_map/fm3.h
===================================================================
--- sandbox/trunk/src/cc/fast_map/fm3.h (rev 0)
+++ sandbox/trunk/src/cc/fast_map/fm3.h 2009-03-06 07:24:20 UTC (rev 1260)
@@ -0,0 +1,122 @@
+#include <backward/hash_fun.h>
+#include <cassert>
+#include <commons/array.h>
+#include <utility>
+
+using namespace std;
+using namespace __gnu_cxx;
+
+class fast_map3
+{
+ private:
+ static const size_t initsize = 1<<20;
+ typedef pair<int, int> entry;
+ commons::array<entry> table;
+ int empty_key, deleted_key;
+ size_t count;
+ hash<int> hasher;
+ void resize(size_t size) {
+ commons::array<entry> tmp(size);
+ for (size_t i = 0; i < size; ++i)
+ tmp[i].first = empty_key;
+ swap(table, tmp);
+ // Rehash old values over into new table.
+ size_t mask = table.size() - 1;
+ for (size_t i = 0; i < tmp.size(); ++i) {
+ if (tmp[i].first != empty_key && tmp[i].first != deleted_key) {
+ // NOTE: second major speedup, originally:
+ // (*this)[tmp[i].first] = tmp[i].second;
+ // Don't want to simply reuse the general lookup, since we know
+ // we're starting with a blank slate.
+ size_t pos = hasher(tmp[i].first) & mask;
+ for (size_t probe = 0;
+ table[pos].first != empty_key;
+ ++probe, pos = (pos + probe) & mask) {
+ assert(probe < table.size());
+ }
+ table[pos] = tmp[pos];
+ }
+ }
+ }
+ void grow() { resize(table.size() << 1); }
+ void shrink() { resize(table.size() >> 1); }
+ public:
+ fast_map3() : table(0), empty_key(0), deleted_key(0), count(0) {}
+ void set_empty_key(int k) { empty_key = k; resize(initsize); }
+ void set_deleted_key(int k) { deleted_key = k; resize(initsize); }
+ size_t size() const { return count; }
+ int &operator[](int k) {
+ size_t probe, mask = table.size() - 1, pos = hasher(k) & mask;
+ // Lookup. Skip over deleted entries (but remembering the first one
+ // seen as an open slot if we later decide to insert). If we find an
+ // empty spot, try returning the earlier deleted spot first. If we
+ // find the key, return that.
+ for (probe = 0;
+ table[pos].first != deleted_key && table[pos].first != empty_key && table[pos].first != k;
+ ++probe, pos = (pos + probe) & mask) {
+ assert(probe < table.size());
+ }
+ if (table[pos].first == deleted_key) {
+ size_t first_deleted = pos;
+ for (;
+ table[pos].first != empty_key && table[pos].first != k;
+ ++probe, pos = (pos + probe) & mask) {
+ assert(probe < table.size());
+ }
+ if (table[pos].first == empty_key) {
+ // Inserting new entry. Grow table if necessary.
+ if (++count > table.size() * 3 / 4) {
+ --count;
+ grow();
+ return (*this)[k];
+ }
+ pos = first_deleted;
+ table[pos].first = k;
+ }
+ } else if (table[pos].first == empty_key) {
+ // Inserting new entry. Grow table if necessary.
+ if (++count > table.size() * 3 / 4) {
+ --count;
+ grow();
+ return (*this)[k];
+ }
+ table[pos].first = k;
+ }
+ return table[pos].second;
+#if 0
+ size_t probe, mask = table.size() - 1, pos = hasher(k) & mask, unset = -1, first_deleted = unset;
+ // Lookup. Skip over deleted entries (but remembering the first one
+ // seen as an open slot if we later decide to insert). If we find an
+ // empty spot, try returning the earlier deleted spot first. If we
+ // find the key, return that.
+ for (probe = 0; ; ++probe) {
+ assert(probe < table.size());
+ // NOTE: using & mask instead of % table.size()
+ pos = (pos + probe) & mask;
+ int &key = table[pos].first;
+ if (key == deleted_key && first_deleted == unset) {
+ first_deleted = pos;
+ } else if (key == empty_key) {
+ // Inserting new entry. Grow table if necessary.
+ ++count;
+ if (count > table.size() * 3 / 4) {
+ --count;
+ grow();
+ return (*this)[k];
+ }
+
+ // Try using an earlier-encountered deleted spot, if any.
+ if (first_deleted != unset) pos = first_deleted;
+
+ table[pos].first = k;
+ break;
+ } else if (key == k) {
+ break;
+ }
+ }
+ assert(probe < table.size());
+ assert(table[pos].first == k);
+ return table[pos].second;
+#endif
+ }
+};
Added: sandbox/trunk/src/cc/fast_map/main.cc
===================================================================
--- sandbox/trunk/src/cc/fast_map/main.cc (rev 0)
+++ sandbox/trunk/src/cc/fast_map/main.cc 2009-03-06 07:24:20 UTC (rev 1260)
@@ -0,0 +1,119 @@
+#include "fm0.h"
+#include "fm1.h"
+#include "fm2.h"
+#include "fm3.h"
+#include <commons/rand.h>
+#include <commons/time.h>
+#include <boost/foreach.hpp>
+#include <google/dense_hash_map>
+#define foreach BOOST_FOREACH
+using namespace std;
+using namespace commons;
+using namespace google;
+
+enum { len = 20000000 };
+int *xs;
+
+template<typename T>
+inline void
+load(T &m, const string &label)
+{
+ size_t slen = len / 10;
+ int i, j;
+ long long start = current_time_millis();
+ for (j = 0; j < 10; ++j) {
+ for (i = 0; size_t(i) < slen; ++i)
+ m[i] = xs[i];
+ if (current_time_millis() > start + 1000)
+ break;
+ }
+ long long diff = current_time_millis() - start;
+ cout << label << ": " << j * slen + i << " ops in " << diff << " ms, or " << double(j * slen + i) / double(diff) * 1000 << " ops/s" << endl;
+}
+
+template<typename T>
+inline void
+iter(T &m, const string &label)
+{
+ long long start = current_time_millis();
+ typedef pair<int, int> pii;
+ foreach (pii p, m) {
+ xs[p.first] = p.second;
+ }
+ long long diff = current_time_millis() - start;
+ cout << label << ": " << m.size() << " ops in " << diff << " ms, or " << double(m.size()) / double(diff) * 1000 << " ops/s" << endl;
+}
+
+template<typename T>
+inline void
+index(T &m, const string &label, size_t len)
+{
+ long long start = current_time_millis();
+ for (int i = 0; size_t(i) < len; i++) {
+ xs[i] = m[i];
+ }
+ long long diff = current_time_millis() - start;
+ cout << label << ": " << len << " ops in " << diff << " ms, or " << double(len) / double(diff) * 1000 << " ops/s" << endl;
+}
+
+template<typename T>
+inline void
+index(T &m, const string &label)
+{
+ index(m, label, m.size());
+}
+
+int main() {
+ int nreps = 2;
+
+ xs = new int[len];
+ for (int i = 0; i < len; i++) {
+ xs[i] = rand();
+ }
+
+ for (int r = 0; r < nreps; r++) {
+ {
+ dense_hash_map<int, int> m;
+ m.set_empty_key(-1);
+ m.set_deleted_key(-2);
+ load(m, "gmap init");
+ load(m, "gmap reload");
+ iter(m, "gmap iter");
+ index(m, "gmap index");
+ }
+ {
+ fast_map0 m;
+ m.set_empty_key(-1);
+ m.set_deleted_key(-2);
+ load(m, "fmap0 init");
+ load(m, "fmap0 reload");
+ index(m, "fmap0 index");
+ }
+ {
+ fast_map1 m;
+ m.set_empty_key(-1);
+ m.set_deleted_key(-2);
+ load(m, "fmap1 init");
+ load(m, "fmap1 reload");
+ index(m, "fmap1 index");
+ }
+ {
+ fast_map2 m;
+ m.set_empty_key(-1);
+ m.set_deleted_key(-2);
+ load(m, "fmap2 init");
+ load(m, "fmap2 reload");
+ index(m, "fmap2 index");
+ }
+ {
+ fast_map3 m;
+ m.set_empty_key(-1);
+ m.set_deleted_key(-2);
+ load(m, "fmap3 init");
+ load(m, "fmap3 reload");
+ index(m, "fmap3 index");
+ }
+ cout << endl;
+ }
+ return 0;
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
