assorted-commits

[Assorted-commits] SF.net SVN: assorted:[1277] ydb/trunk

[<yan...@us...>]

Revision: 1277
          http://assorted.svn.sourceforge.net/assorted/?rev=1277&view=rev
Author:   yangzhang
Date:     2009-03-09 22:59:57 +0000 (Mon, 09 Mar 2009)

Log Message:
-----------
- fast memcpy recovery serialization with direct access to fast_map table
- using recovery_t = array<entry> instead of Recovery
- using c++0x unique_ptr/move instead of c++03/boost
- using raw_reader/raw_writer
- added line-counts to test.bash
- adde/updated notes/todos

Modified Paths:
--------------
    ydb/trunk/README
    ydb/trunk/src/main.lzz.clamp
    ydb/trunk/tools/test.bash

Modified: ydb/trunk/README
===================================================================
--- ydb/trunk/README	2009-03-09 22:59:33 UTC (rev 1276)
+++ ydb/trunk/README	2009-03-09 22:59:57 UTC (rev 1277)
@@ -518,18 +518,16 @@
   containers
   - built something really fast, faster than even google dense_hash_map
 
-- TODO experiment with large pages
+- DONE use rb instead of pb for recovery state
 
-- TODO use rb instead of pb for recovery state
-
 - TODO test out recovery mode more thoroughly, make sure progress is being
   made, see how fast it is
 
-- TODO fix multi-recovery if necessary
+- DONE fix multi-recovery if necessary
 
-- TODO speed up map dump; don't use range partitioning, but hash partitioning
+- DONE speed up map dump; don't use range partitioning, but hash partitioning
 
-- TODO refactor st_reader, etc. to be generic opportunistic buffered readers
+- DONE refactor st_reader, etc. to be generic opportunistic buffered readers
 - TODO see how streambuf read/write is actually implemented (whether it's too
   slow)
 - TODO try making a streambuf for st_write, then try it in conj with
@@ -538,12 +536,12 @@
 - TODO async (threaded) wal
 - TODO 0-node 0-copy (don't need to use threads, just process each batch immed)
 
-- TODO batch up the responses until they make large-enough buffer in pb mode
-
 - TODO show aries-write
 - TODO checkpointing + replaying log from replicas (not from disk)
 - TODO scale-up on multicore
 
+- TODO experiment with libhugetlbfs
+
 - TODO remove extraneous copies; use custom buffer-backed data structures
   designed for serialization/deserialization
 - TODO flushing

Modified: ydb/trunk/src/main.lzz.clamp
===================================================================
--- ydb/trunk/src/main.lzz.clamp	2009-03-09 22:59:33 UTC (rev 1276)
+++ ydb/trunk/src/main.lzz.clamp	2009-03-09 22:59:57 UTC (rev 1277)
@@ -8,12 +8,13 @@
 #include <boost/scoped_array.hpp>
 #include <boost/shared_ptr.hpp>
 #include <boost/tuple/tuple.hpp>
-#include <boost/unique_ptr.hpp>
 #include <commons/fast_map.h>
+#include <commons/memory.h>
 #include <commons/nullptr.h>
 #include <commons/rand.h>
 #include <commons/st/st.h>
 #include <commons/time.h>
+#include <commons/unique_ptr.h>
 #include <csignal> // sigaction etc.
 #include <cstdio>
 #include <cstring> // strsignal
@@ -57,10 +58,13 @@
 //#define map_t dense_hash_map
 #define map_t fast_map
 typedef map_t<int, int> mii;
-typedef pair<int, int> pii;
+typedef mii::value_type entry;
 
 typedef tuple<sized_array<char>, char*, char*> chunk;
 
+//typedef unique_ptr<Recovery> recovery_t;
+typedef commons::array<char> recovery_t;
+
 template<typename T> void init_map(T &map) {}
 template<> void init_map(dense_hash_map<int, int> &map) {
   map.set_empty_key(-1);
@@ -637,7 +641,7 @@
 
     // Generate some random transactions.
     start_txn(batch);
-    for (int t = 0; t < batch_size; ++t) {
+    for (int t = 0; t < batch_size && !stop_hub; ++t) {
       char *txn_start = w.cur();
       Txn &txn = *batch.add_txn();
       txn.set_seqno(seqno);
@@ -856,7 +860,7 @@
 template<typename Types, typename RTypes>
 void
 process_txns(st_netfd_t leader, mii &map, int &seqno,
-             st_channel<unique_ptr<Recovery> > &send_states,
+             st_channel<recovery_t> &send_states,
              /* XXX st_channel<shared_ptr<pb::Txn> > &backlog */
              st_channel<chunk> &backlog, int init_seqno,
              int mypos, int nnodes)
@@ -896,7 +900,7 @@
       showtput("live-processed", now, __ref(time_caught_up), __ref(seqno),
                __ref(seqno_caught_up));
     }
-    __ref(send_states).push(unique_ptr<Recovery>());
+    __ref(send_states).push(recovery_t());
     __ref(w).mark_and_flush();
     st_sleep(1);
   });
@@ -971,9 +975,10 @@
           if (reader.unread() + reader.rem() < prefix + sizeof(uint32_t) - headerlen) {
             // Move current partial message to new buffer.
             sized_array<char> tmp(new char[read_buf_size], read_buf_size);
-            *reinterpret_cast<uint32_t*>(tmp.get()) = prefix;
-            *reinterpret_cast<short*>(tmp.get() + sizeof(uint32_t)) = short(batch.txn_size());
-            *reinterpret_cast<int*>(tmp.get() + sizeof(uint32_t) + sizeof(short)) = first_txn.seqno();
+            raw_writer ser(tmp.get());
+            ser.write(prefix);
+            ser.write(short(batch.txn_size()));
+            ser.write(first_txn.seqno());
             memcpy(tmp.get() + headerlen, reader.start(), reader.unread());
 
             // Swap the buffers.
@@ -1028,9 +1033,7 @@
         }
       } else if (multirecover || mypos == 0) {
         // Empty (default) TxnBatch means "generate a snapshot."
-        unique_ptr<Recovery> recovery(make_recovery(map, mypos, nnodes));
-        recovery->set_seqno(seqno);
-        send_states.push(boost::move(recovery));
+        send_states.push(make_recovery(map, mypos, nnodes, seqno));
       }
     }
   } catch (break_exception &ex) {
@@ -1038,8 +1041,11 @@
 
 }
 
+#if 0
 template<typename mii>
-unique_ptr<Recovery> make_recovery(const mii &map, int mypos, int nnodes) {
+unique_ptr<Recovery>
+make_recovery(const mii &map, int mypos, int nnodes, int &seqno)
+{
   // TODO make this faster
   cout << "generating recovery..." << endl;
   unique_ptr<Recovery> recovery(new Recovery);
@@ -1062,9 +1068,55 @@
   }
   cout << "generating recovery took "
        << current_time_millis() - start_snap << " ms" << endl;
-  return boost::move(recovery);
+  recovery->set_seqno(seqno);
+  return move(recovery);
 }
+#endif
 
+template<typename mii>
+recovery_t
+make_recovery(const mii &map, int mypos, int nnodes, int &seqno)
+{
+  return recovery_t();
+}
+
+struct recovery_header
+{
+  int seqno;
+  size_t count;
+  size_t total;
+  size_t size;
+};
+
+pair<size_t, size_t>
+recovery_range(size_t size, int mypos, int nnodes)
+{
+  return make_pair(multirecover ? size *  mypos      / size_t(nnodes) : 0,
+                   multirecover ? size * (mypos + 1) / size_t(nnodes) : size);
+}
+
+template<>
+recovery_t
+make_recovery(const fast_map<int, int> &map, int mypos, int nnodes, int &seqno)
+{
+  const commons::array<entry> &src = map.get_table();
+  pair<size_t, size_t> range = recovery_range(src.size(), mypos, nnodes);
+  size_t begin = range.first, end = range.second;
+  assert(end > begin);
+  recovery_header hdr = { seqno, end - begin, src.size(), map.size() };
+  size_t bodylen = sizeof(entry) * hdr.count;
+  cout << "generating recovery of " << hdr.size << " records in "
+       << hdr.count << " slots ("
+       << bodylen << " bytes); range is ["
+       << begin << ".." << end << "]; seqno is " << hdr.seqno << endl;
+  commons::array<char> recovery(sizeof(size_t) + sizeof hdr + bodylen);
+  raw_writer ser(recovery.begin());
+  ser.write(recovery.size());
+  ser.write(hdr);
+  memcpy(ser.ptr(), src.begin() + begin, bodylen);
+  return recovery;
+}
+
 class response_handler
 {
 public:
@@ -1254,10 +1306,10 @@
  */
 void
 recover_joiner(st_netfd_t listener,
-               st_channel<unique_ptr<Recovery> > &send_states)
+               st_channel<recovery_t> &send_states)
 {
   st_netfd_t joiner;
-  unique_ptr<Recovery> recovery;
+  recovery_t recovery;
   {
     st_intr intr(stop_hub);
     // Wait for the snapshot.
@@ -1272,9 +1324,16 @@
 
   st_closing closing(joiner);
   cout << "got joiner's connection, sending recovery of "
-       << recovery->pair_size() << " records" << endl;
+       << recovery.size() << " bytes" << endl;
+  long long start_time = current_time_millis();
+  checkeqnneg(st_write(joiner, recovery.get(), recovery.size(),
+                       ST_UTIME_NO_TIMEOUT),
+              ssize_t(recovery.size()));
+  long long diff = current_time_millis() - start_time;
+#if 0
   sendmsg(joiner, *recovery);
-  cout << "sent recovery" << endl;
+#endif
+  cout << "sent recovery in " << diff << " ms" << endl;
 }
 
 void
@@ -1353,7 +1412,7 @@
       cout << "- dumping to " << fname << endl;
       ofstream of(fname.c_str());
       of << "seqno: " << __ref(seqno) << endl;
-      foreach (const pii &p, g_map) {
+      foreach (const entry &p, g_map) {
         of << p.first << ": " << p.second << endl;
       }
     }
@@ -1432,12 +1491,12 @@
       cout << "- dumping to " << fname << endl;
       ofstream of(fname.c_str());
       of << "seqno: " << __ref(seqno) << endl;
-      foreach (const pii &p, __ref(map)) {
+      foreach (const entry &p, __ref(map)) {
         of << p.first << ": " << p.second << endl;
       }
     }
   });
-  st_channel<unique_ptr<Recovery> > send_states;
+  st_channel<recovery_t> send_states;
 
   cout << "starting as replica on port " << listen_port << endl;
 
@@ -1502,9 +1561,61 @@
 
       vector<st_thread_t> recovery_builders;
       assert(seqno == -1);
+      bool first = true;
       for (int i = 0; i < (multirecover ? init.node_size() : 1); ++i) {
         recovery_builders.push_back(my_spawn(lambda() {
-          // Read the recovery message.
+          // Read the recovery message length and header.
+          size_t len;
+          recovery_header hdr;
+          char buf[sizeof len + sizeof hdr];
+          //try {
+            checkeqnneg(st_read_fully(__ref(replicas[i]),
+                                      buf, sizeof len + sizeof hdr,
+                                      ST_UTIME_NO_TIMEOUT),
+                        ssize_t(sizeof len + sizeof hdr));
+          //} catch (...) { // TODO just catch "Connection reset by peer"
+            //return;
+          //}
+          raw_reader rdr(buf);
+          rdr.read(len);
+          rdr.read(hdr);
+          check(hdr.seqno >= 0);
+
+          // Resize the table if necessary.
+          commons::array<entry> &table = __ref(map).get_table();
+          if (!__ref(first)) {
+            checkeq(table.size(), hdr.total);
+            checkeq(__ref(map).size(), hdr.size);
+          } else {
+            __ref(map).set_size(hdr.size);
+            if (table.size() != hdr.total) {
+              table.reset(new entry[hdr.total], hdr.total);
+            }
+          }
+
+          // Receive straight into the table.
+          pair<size_t, size_t> range =
+            recovery_range(table.size(), __ctx(i), __ref(init).node_size());
+          // Check that we agree on the number of entries.
+          checkeq(range.second - range.first, hdr.count);
+          // Check that the count is a power of two.
+          checkeq(hdr.count & (hdr.count - 1), size_t(0));
+          size_t rangelen = sizeof(entry) * hdr.count;
+          // Read an extra char to ensure that we're at the EOF.
+          checkeqnneg(st_read_fully(__ref(replicas[i]),
+                                    table.begin() + range.first, rangelen + 1,
+                                    ST_UTIME_NO_TIMEOUT),
+                      ssize_t(rangelen));
+
+          long long tm = current_time_millis();
+          if (__ref(seqno) != -1)
+            checkeq(__ref(seqno), hdr.seqno);
+          __ref(seqno) = hdr.seqno;
+          cout << "got recovery message of " << len << " bytes ("
+               << hdr.size << " records in " << hdr.count << " slots) in "
+               << tm - __ref(before_recv) << " ms; now at seqno "
+               << hdr.seqno << endl;
+#if 0
           Recovery recovery;
           long long receive_start = 0, receive_end = 0;
           size_t len = 0;
@@ -1533,6 +1644,7 @@
                << " ms; built up map of " << recovery.pair_size()
                << " records in " << build_end - build_start
                << " ms; now at seqno " << seqno << endl;
+#endif
         }, "recovery_builder" + lexical_cast<string>(i)));
       }
       foreach (st_thread_t t, recovery_builders) {

Modified: ydb/trunk/tools/test.bash
===================================================================
--- ydb/trunk/tools/test.bash	2009-03-09 22:59:33 UTC (rev 1276)
+++ ydb/trunk/tools/test.bash	2009-03-09 22:59:57 UTC (rev 1277)
@@ -527,6 +527,11 @@
   hostargs p2-helper
 }
 
+line-counts() {
+  wc -l "$(dirname "$0")/../src/"{main.lzz.clamp,ser.{h,cc},p2.cc,ydb.proto,Makefile,serperf.cc} \
+        ~/ccom/src/{commons/{,st/}*.h,test/{*.*,Makefile}}
+}
+
 #
 # Main
 #


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1276] cpp-commons/trunk/src/test

[<yan...@us...>]

Revision: 1276
          http://assorted.svn.sourceforge.net/assorted/?rev=1276&view=rev
Author:   yangzhang
Date:     2009-03-09 22:59:33 +0000 (Mon, 09 Mar 2009)

Log Message:
-----------
added tests for array, st

Modified Paths:
--------------
    cpp-commons/trunk/src/test/Makefile

Added Paths:
-----------
    cpp-commons/trunk/src/test/array.cc
    cpp-commons/trunk/src/test/st.cc

Modified: cpp-commons/trunk/src/test/Makefile
===================================================================
--- cpp-commons/trunk/src/test/Makefile	2009-03-09 22:56:37 UTC (rev 1275)
+++ cpp-commons/trunk/src/test/Makefile	2009-03-09 22:59:33 UTC (rev 1276)
@@ -42,4 +42,7 @@
 clean:
 	rm -f $(BINS)
 
+st: st.cc
+	$(LINK.cc) $^ $(LOADLIBES) $(LDLIBS) -lst -lstx -lresolv -o $@
+
 .PHONY: all build clean

Added: cpp-commons/trunk/src/test/array.cc
===================================================================
--- cpp-commons/trunk/src/test/array.cc	                        (rev 0)
+++ cpp-commons/trunk/src/test/array.cc	2009-03-09 22:59:33 UTC (rev 1276)
@@ -0,0 +1,17 @@
+#include <commons/array.h>
+#include "test.h"
+
+static const int size = 4096;
+
+TEST(array, array) {
+  array<char> xs(size);
+  EXPECT_EQ(size, xs.size());
+}
+
+TEST(array, sized_array) {
+  char *p = new char[size];
+  sized_array<char> xs(p, size);
+  EXPECT_EQ(size, xs.size());
+  EXPECT_EQ(p, xs.get());
+  EXPECT_EQ(p, xs.begin());
+}

Added: cpp-commons/trunk/src/test/st.cc
===================================================================
--- cpp-commons/trunk/src/test/st.cc	                        (rev 0)
+++ cpp-commons/trunk/src/test/st.cc	2009-03-09 22:59:33 UTC (rev 1276)
@@ -0,0 +1,9 @@
+#include <commons/st/st.h>
+#include <commons/unique_ptr.h>
+#include "test.h"
+
+TEST(st, channel) {
+  st_channel<unique_ptr<int> > ch;
+  ch.push(unique_ptr<int>(new int(0)));
+  unique_ptr<int> p = ch.take();
+}


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1275] cpp-commons/trunk/src/commons

[<yan...@us...>]

Revision: 1275
          http://assorted.svn.sourceforge.net/assorted/?rev=1275&view=rev
Author:   yangzhang
Date:     2009-03-09 22:56:37 +0000 (Mon, 09 Mar 2009)

Log Message:
-----------
- added fast_map::set_size
- added c++0x unique_ptr
- added memory.h with memput, memget, raw_reader, raw_writer
- use proper moving/forwarding in st_channel
- made array moveable, non-copyable

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/array.h
    cpp-commons/trunk/src/commons/fast_map.h
    cpp-commons/trunk/src/commons/st/st.h

Added Paths:
-----------
    cpp-commons/trunk/src/commons/memory.h
    cpp-commons/trunk/src/commons/unique_ptr.h

Modified: cpp-commons/trunk/src/commons/array.h
===================================================================
--- cpp-commons/trunk/src/commons/array.h	2009-03-09 22:55:47 UTC (rev 1274)
+++ cpp-commons/trunk/src/commons/array.h	2009-03-09 22:56:37 UTC (rev 1275)
@@ -2,15 +2,14 @@
 #define COMMONS_ARRAY_H
 
 #include <algorithm>
-#include <boost/unique_ptr.hpp>
 #include <commons/algo.h>
 #include <commons/check.h>
 #include <commons/nullptr.h>
+#include <commons/unique_ptr.h>
 #include <commons/utility.h>
 
 namespace commons {
 
-  using namespace boost;
   using namespace std;
 
   template<typename T> class array;
@@ -48,9 +47,26 @@
   template<typename T>
     class array {
       EXPAND(unique_ptr<T[]>)
+      NONCOPYABLE(array)
       friend void swap<>(array<T> &a, array<T> &b);
       public:
         explicit array(size_t n) : p_(new T[n]), n_(n) {}
+        array() : p_(), n_(0) {}
+        array(array<T> &&src) : p_(src.release()), n_(src.n_) {}
+#if 0
+        array(array<T> src) : p_(new T[src.size()]), n_(src.size()) {
+          memcpy(p_.get(), src.get(), size());
+        }
+#endif
+        array<T> &operator=(array<T> &&src) {
+          if (this != &src) {
+            p_.reset(src.release());
+            n_ = src.n_;
+          }
+          return *this;
+        }
+        operator const T*() const { return p_.get(); }
+        operator T*() { return p_.get(); }
         size_t size() const { return n_; }
         T *get() const { return p_.get(); }
         T *release() { return p_.release(); }
@@ -71,7 +87,7 @@
   void
   swap(array<T> &a, array<T> &b)
   {
-    boost::swap(a.p_, b.p_);
+    std::swap(a.p_, b.p_);
     swap(a.n_, b.n_);
   }
 
@@ -95,9 +111,7 @@
       NONCOPYABLE(managed_array)
       public:
         managed_array(T *p, bool scoped) : p_(p), scoped_(scoped) {}
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
         managed_array(managed_array<T> &&a) : p_(a.p_), scoped_(a.scoped_) { a.release(); }
-#endif
         ~managed_array() { if (scoped_) delete [] p_; }
         T *release() { T *p = p_; p_ = nullptr; scoped_ = false; return p; }
         T *get() { return p_; }

Modified: cpp-commons/trunk/src/commons/fast_map.h
===================================================================
--- cpp-commons/trunk/src/commons/fast_map.h	2009-03-09 22:55:47 UTC (rev 1274)
+++ cpp-commons/trunk/src/commons/fast_map.h	2009-03-09 22:56:37 UTC (rev 1275)
@@ -193,6 +193,7 @@
         resize(initsize);
       }
       size_t size() const { return count; }
+      void set_size(size_t size) { count = size; }
       void erase(iterator) { throw_not_implemented(); }
       array<value_type> &get_table() { return table; }
       const array<value_type> &get_table() const { return table; }
@@ -225,6 +226,7 @@
           if (table[pos].first == empty_key) return end();
           if (table[pos].first == k) return const_iterator(*this, &table[pos]);
           pos = (pos + ++probe) & mask;
+          assert(probe < table.size());
         }
       }
 
@@ -235,6 +237,7 @@
           if (table[pos].first == empty_key) return end();
           if (table[pos].first == k) return iterator(*this, &table[pos]);
           pos = (pos + ++probe) & mask;
+          assert(probe < table.size());
         }
 #if 0
         for (;

Added: cpp-commons/trunk/src/commons/memory.h
===================================================================
--- cpp-commons/trunk/src/commons/memory.h	                        (rev 0)
+++ cpp-commons/trunk/src/commons/memory.h	2009-03-09 22:56:37 UTC (rev 1275)
@@ -0,0 +1,57 @@
+#ifndef COMMONS_MEMORY_H
+#define COMMONS_MEMORY_H
+
+namespace commons
+{
+
+  /**
+   * Copy a datum directly to a memory location.  Useful for serializing small
+   * data (e.g. ints).  Faster than memcpy.
+   */
+  template<typename T>
+  void memput(void *dst, const T &src) {
+    *reinterpret_cast<T*>(dst) = src;
+  }
+
+  template<typename T>
+  void memget(void *src, T &dst) {
+    dst = *reinterpret_cast<T*>(src);
+  }
+
+  template<typename T>
+  T &memget(void *src) {
+    return *reinterpret_cast<T*>(src);
+  }
+
+  /**
+   * Lets you write a bunch of values to a buffer.
+   */
+  class raw_writer
+  {
+  private:
+    char *p_;
+  public:
+    /** Initialize the pointer to point to p. */
+    raw_writer(void *p) : p_(reinterpret_cast<char*>(p)) {}
+    /** Write a datum to the buffer, advancing the pointer. */
+    template<typename T>
+      void write(const T &x) { memput(p_, x); p_ += sizeof(T); }
+    /** Get the current value of the pointer.  */
+    void *ptr() const { return p_; }
+  };
+
+  class raw_reader
+  {
+  private:
+    char *p_;
+  public:
+    raw_reader(void *p) : p_(reinterpret_cast<char*>(p)) {}
+    template<typename T>
+      void read(T& x) { memget(p_, x); p_ += sizeof(T); }
+    template<typename T>
+      T &read() { void *p = p_; p_ += sizeof(T); return memget<T>(p_); }
+  };
+
+}
+
+#endif

Modified: cpp-commons/trunk/src/commons/st/st.h
===================================================================
--- cpp-commons/trunk/src/commons/st/st.h	2009-03-09 22:55:47 UTC (rev 1274)
+++ cpp-commons/trunk/src/commons/st/st.h	2009-03-09 22:56:37 UTC (rev 1275)
@@ -18,6 +18,7 @@
 #include <sstream>
 #include <st.h>
 #include <stx.h>
+#include <utility>
 
 #define foreach BOOST_FOREACH
 #define shared_ptr boost::shared_ptr
@@ -196,21 +197,17 @@
   class st_channel
   {
     public:
-      void push(T &&x) {
-        q_.push(boost::move(x));
+      template<typename U> void push(U &&x) {
+        q_.push(forward<U>(x));
         empty_.signal();
       }
-      void push(const T &x) {
-        q_.push(x);
-        empty_.signal();
-      }
       T take() {
         while (q_.empty()) {
           empty_.wait();
         }
-        T x = boost::move(front());
+        T x = move(front());
         q_.pop();
-        return boost::move(x);
+        return x;
       }
       const T& front() const { return q_.front(); }
       T& front() { return q_.front(); }

Added: cpp-commons/trunk/src/commons/unique_ptr.h
===================================================================
--- cpp-commons/trunk/src/commons/unique_ptr.h	                        (rev 0)
+++ cpp-commons/trunk/src/commons/unique_ptr.h	2009-03-09 22:56:37 UTC (rev 1275)
@@ -0,0 +1,459 @@
+// unique_ptr implementation -*- C++ -*-
+
+// Copyright (C) 2008, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING.  If not, write to
+// the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+// Boston, MA 02110-1301, USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+/** @file unique_ptr.h
+ *  This is an internal header file, included by other library headers.
+ *  You should not attempt to use it directly.
+ */
+
+#ifndef _UNIQUE_PTR_H
+#define _UNIQUE_PTR_H 1
+
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+# include <c++0x_warning.h>
+#endif
+
+#include <bits/c++config.h>
+#include <debug/debug.h>
+#include <type_traits>
+#include <utility>
+#include <tuple>
+
+_GLIBCXX_BEGIN_NAMESPACE(std)
+
+  /**
+   * @addtogroup pointer_abstractions
+   * @{
+   */
+
+  /// Primary template, default_delete.
+  template<typename _Tp> 
+    struct default_delete
+      {
+	default_delete() { }
+
+	template<typename _Up>
+	  default_delete(const default_delete<_Up>&) { }
+
+	void
+	operator()(_Tp* __ptr) const
+	{
+	  static_assert(sizeof(_Tp)>0,
+			"can't delete pointer to incomplete type");
+	  delete __ptr;
+	}
+    };
+
+  // _GLIBCXX_RESOLVE_LIB_DEFECTS
+  // DR 740 - omit specialization for array objects with a compile time length
+  /// Specialization, default_delete.
+  template<typename _Tp> 
+    struct default_delete<_Tp[]>
+    {
+      void
+      operator()(_Tp* __ptr) const
+      {
+	static_assert(sizeof(_Tp)>0,
+		      "can't delete pointer to incomplete type");
+	delete [] __ptr;
+      }
+    };
+
+  /// 20.7.12.2 unique_ptr for single objects.
+  template <typename _Tp, typename _Tp_Deleter = default_delete<_Tp> > 
+    class unique_ptr
+    {
+      typedef std::tuple<_Tp*, _Tp_Deleter>  __tuple_type;
+      typedef __tuple_type unique_ptr::*     __unspecified_bool_type;
+      typedef _Tp* unique_ptr::*             __unspecified_pointer_type;
+
+    public:
+      typedef _Tp*               pointer;
+      typedef _Tp                element_type;      
+      typedef _Tp_Deleter        deleter_type;
+
+      // Constructors.
+      unique_ptr()
+      : _M_t(pointer(), deleter_type())
+      { static_assert(!std::is_pointer<deleter_type>::value,
+		      "constructed with null function pointer deleter"); }
+
+      explicit
+      unique_ptr(pointer __p)
+      : _M_t(__p, deleter_type())
+      { static_assert(!std::is_pointer<deleter_type>::value,
+		     "constructed with null function pointer deleter"); }
+
+      unique_ptr(pointer __p,
+          typename std::conditional<std::is_reference<deleter_type>::value, 
+            deleter_type, const deleter_type&>::type __d)
+      : _M_t(__p, __d) { }
+
+      unique_ptr(pointer __p,
+          typename std::remove_reference<deleter_type>::type&& __d)
+      : _M_t(std::move(__p), std::move(__d))
+      { static_assert(!std::is_reference<deleter_type>::value, 
+		      "rvalue deleter bound to reference"); }
+
+      // Move constructors.
+      unique_ptr(unique_ptr&& __u) 
+      : _M_t(__u.release(), std::forward<deleter_type>(__u.get_deleter())) { }
+
+      template<typename _Up, typename _Up_Deleter> 
+        unique_ptr(unique_ptr<_Up, _Up_Deleter>&& __u) 
+        : _M_t(__u.release(), std::forward<deleter_type>(__u.get_deleter()))
+	{ }
+
+      // Destructor.
+      ~unique_ptr() { reset(); }
+    
+      // Assignment.
+      unique_ptr&
+      operator=(unique_ptr&& __u)
+      { 
+        reset(__u.release()); 
+        get_deleter() = std::move(__u.get_deleter()); 
+        return *this;
+      }
+
+      template<typename _Up, typename _Up_Deleter> 
+        unique_ptr&
+        operator=(unique_ptr<_Up, _Up_Deleter>&& __u)
+	{
+          reset(__u.release()); 
+          get_deleter() = std::move(__u.get_deleter()); 
+          return *this;
+        }
+
+      unique_ptr&
+      operator=(__unspecified_pointer_type) 
+      {
+	reset();
+	return *this;
+      }
+
+      // Observers.
+      typename std::add_lvalue_reference<element_type>::type operator*() const
+      {
+	_GLIBCXX_DEBUG_ASSERT(get() != 0);
+	return *get();
+      }
+
+      pointer
+      operator->() const
+      {
+	_GLIBCXX_DEBUG_ASSERT(get() != 0);
+	return get();
+      }
+
+      pointer
+      get() const
+      { return std::get<0>(_M_t); }
+
+      typename std::add_lvalue_reference<deleter_type>::type
+      get_deleter()
+      { return std::get<1>(_M_t); }
+
+      typename std::add_lvalue_reference<
+          typename std::add_const<deleter_type>::type
+              >::type
+      get_deleter() const
+      { return std::get<1>(_M_t); }
+
+      operator __unspecified_bool_type () const
+      { return get() == 0 ? 0 : &unique_ptr::_M_t; }
+
+      // Modifiers.
+      pointer
+      release() 
+      {
+	pointer __p = get();
+	std::get<0>(_M_t) = 0;
+	return __p;
+      }
+
+      void
+      reset(pointer __p = pointer())
+      {
+	if (__p != get())
+	  {
+	    get_deleter()(get());
+	    std::get<0>(_M_t) = __p;
+	  }
+      }
+
+      void
+      swap(unique_ptr&& __u)
+      {
+	using std::swap;
+	swap(_M_t, __u._M_t);
+      }
+
+    private:
+      // Disable copy from lvalue.
+      unique_ptr(const unique_ptr&);
+
+      template<typename _Up, typename _Up_Deleter> 
+        unique_ptr(const unique_ptr<_Up, _Up_Deleter>&);
+
+      unique_ptr& operator=(const unique_ptr&);
+
+      template<typename _Up, typename _Up_Deleter> 
+        unique_ptr& operator=(const unique_ptr<_Up, _Up_Deleter>&);
+
+    private:
+      __tuple_type _M_t;
+  };
+ 
+  /// 20.7.12.3 unique_ptr for array objects with a runtime length
+  // [unique.ptr.runtime]
+  // _GLIBCXX_RESOLVE_LIB_DEFECTS
+  // DR 740 - omit specialization for array objects with a compile time length
+  template<typename _Tp, typename _Tp_Deleter> 
+    class unique_ptr<_Tp[], _Tp_Deleter>
+    {
+      typedef std::tuple<_Tp*, _Tp_Deleter>  __tuple_type;
+      typedef __tuple_type unique_ptr::*     __unspecified_bool_type;
+      typedef _Tp* unique_ptr::*             __unspecified_pointer_type;
+
+    public:
+      typedef _Tp*               pointer;
+      typedef _Tp                element_type;      
+      typedef _Tp_Deleter        deleter_type;
+
+      // Constructors.
+      unique_ptr()
+      : _M_t(pointer(), deleter_type())
+      { static_assert(!std::is_pointer<deleter_type>::value,
+		      "constructed with null function pointer deleter"); }
+
+      explicit
+      unique_ptr(pointer __p)
+      : _M_t(__p, deleter_type())
+      { static_assert(!std::is_pointer<deleter_type>::value,
+		      "constructed with null function pointer deleter"); }
+
+      unique_ptr(pointer __p,
+          typename std::conditional<std::is_reference<deleter_type>::value, 
+              deleter_type, const deleter_type&>::type __d) 
+      : _M_t(__p, __d) { }
+
+      unique_ptr(pointer __p,
+		 typename std::remove_reference<deleter_type>::type && __d)
+      : _M_t(std::move(__p), std::move(__d))
+      { static_assert(!std::is_reference<deleter_type>::value, 
+		      "rvalue deleter bound to reference"); }
+
+      // Move constructors.
+      unique_ptr(unique_ptr&& __u) 
+      : _M_t(__u.release(), std::forward<deleter_type>(__u.get_deleter())) { }
+
+      template<typename _Up, typename _Up_Deleter> 
+        unique_ptr(unique_ptr<_Up, _Up_Deleter>&& __u) 
+	: _M_t(__u.release(), std::forward<deleter_type>(__u.get_deleter()))
+	{ }
+
+      // Destructor.
+      ~unique_ptr() { reset(); }
+
+      // Assignment.
+      unique_ptr&
+      operator=(unique_ptr&& __u)
+      {
+	reset(__u.release());
+	get_deleter() = std::move(__u.get_deleter()); 
+	return *this; 
+      }
+
+      template<typename _Up, typename _Up_Deleter> 
+        unique_ptr&
+        operator=(unique_ptr<_Up, _Up_Deleter>&& __u)
+	{
+          reset(__u.release());
+          get_deleter() = std::move(__u.get_deleter()); 
+          return *this;
+        }
+
+      unique_ptr&
+      operator=(__unspecified_pointer_type)
+      {
+	reset();
+	return *this;
+      }
+
+      // Observers.
+      typename std::add_lvalue_reference<element_type>::type 
+      operator[](size_t __i) const 
+      {
+	_GLIBCXX_DEBUG_ASSERT(get() != 0);
+	return get()[__i];
+      }
+
+      pointer
+      get() const
+      { return std::get<0>(_M_t); }
+
+      typename std::add_lvalue_reference<deleter_type>::type 
+      get_deleter()
+      { return std::get<1>(_M_t); }
+
+      typename std::add_lvalue_reference<
+          typename std::add_const<deleter_type>::type
+              >::type 
+      get_deleter() const
+      { return std::get<1>(_M_t); }    
+
+      operator __unspecified_bool_type () const 
+      { return get() == 0 ? 0 : &unique_ptr::_M_t; }
+    
+      // Modifiers.
+      pointer
+      release() 
+      {
+	pointer __p = get();
+	std::get<0>(_M_t) = 0;
+	return __p;
+      }
+
+      void
+      reset(pointer __p = pointer()) 
+      {
+	if (__p != get())
+	{
+	  get_deleter()(get());
+	  std::get<0>(_M_t) = __p;
+	}
+      }
+
+    private:
+      // DR 821.
+      template<typename _Up>
+        void reset(_Up);
+
+    public:
+      void
+      swap(unique_ptr&& __u)
+      {
+	using std::swap;
+	swap(_M_t, __u._M_t);
+      }
+
+    private:
+      // Disable copy from lvalue.
+      unique_ptr(const unique_ptr&);
+      unique_ptr& operator=(const unique_ptr&);
+
+      // Disable construction from convertible pointer types.
+      // (N2315 - 20.6.5.3.1)
+      template<typename _Up>
+        unique_ptr(_Up*, typename
+		   std::conditional<std::is_reference<deleter_type>::value,
+		   deleter_type, const deleter_type&>::type,
+		   typename std::enable_if<std::is_convertible<_Up*, 
+		   pointer>::value>::type* = 0);
+
+      template<typename _Up>
+        unique_ptr(_Up*, typename std::remove_reference<deleter_type>::type&&,
+		   typename std::enable_if<std::is_convertible<_Up*, 
+		   pointer>::value>::type* = 0);
+
+      template<typename _Up>
+        explicit
+        unique_ptr(_Up*, typename std::enable_if<std::is_convertible<_Up*, 
+		   pointer>::value>::type* = 0);
+
+    private:
+      __tuple_type _M_t;
+  };
+  
+  template<typename _Tp, typename _Tp_Deleter> 
+    inline void
+    swap(unique_ptr<_Tp, _Tp_Deleter>& __x,
+	 unique_ptr<_Tp, _Tp_Deleter>& __y)
+    { __x.swap(__y); }
+
+  template<typename _Tp, typename _Tp_Deleter> 
+    inline void
+    swap(unique_ptr<_Tp, _Tp_Deleter>&& __x,
+	 unique_ptr<_Tp, _Tp_Deleter>& __y)
+    { __x.swap(__y); }
+
+  template<typename _Tp, typename _Tp_Deleter> 
+    inline void
+    swap(unique_ptr<_Tp, _Tp_Deleter>& __x,
+	 unique_ptr<_Tp, _Tp_Deleter>&& __y)
+    { __x.swap(__y); }
+  
+  template<typename _Tp, typename _Tp_Deleter,
+	   typename _Up, typename _Up_Deleter>
+    inline bool
+    operator==(const unique_ptr<_Tp, _Tp_Deleter>& __x,
+	       const unique_ptr<_Up, _Up_Deleter>& __y)
+    { return __x.get() == __y.get(); }
+
+  template<typename _Tp, typename _Tp_Deleter,
+	   typename _Up, typename _Up_Deleter>
+    inline bool
+    operator!=(const unique_ptr<_Tp, _Tp_Deleter>& __x,
+	       const unique_ptr<_Up, _Up_Deleter>& __y)
+    { return !(__x.get() == __y.get()); }
+
+  template<typename _Tp, typename _Tp_Deleter,
+	   typename _Up, typename _Up_Deleter>
+    inline bool
+    operator<(const unique_ptr<_Tp, _Tp_Deleter>& __x,
+	      const unique_ptr<_Up, _Up_Deleter>& __y)
+    { return __x.get() < __y.get(); }
+
+  template<typename _Tp, typename _Tp_Deleter,
+	   typename _Up, typename _Up_Deleter>
+    inline bool
+    operator<=(const unique_ptr<_Tp, _Tp_Deleter>& __x,
+	       const unique_ptr<_Up, _Up_Deleter>& __y)
+    { return !(__y.get() < __x.get()); }
+
+  template<typename _Tp, typename _Tp_Deleter,
+	   typename _Up, typename _Up_Deleter>
+    inline bool
+    operator>(const unique_ptr<_Tp, _Tp_Deleter>& __x,
+	      const unique_ptr<_Up, _Up_Deleter>& __y)
+    { return __y.get() < __x.get(); }
+
+  template<typename _Tp, typename _Tp_Deleter,
+	   typename _Up, typename _Up_Deleter>
+    inline bool
+    operator>=(const unique_ptr<_Tp, _Tp_Deleter>& __x,
+	       const unique_ptr<_Up, _Up_Deleter>& __y)
+    { return !(__x.get() < __y.get()); }
+
+  // @} group pointer_abstractions
+
+_GLIBCXX_END_NAMESPACE
+
+#endif /* _UNIQUE_PTR_H */


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1274] sandbox/trunk/src/cc/forward.cc

[<yan...@us...>]

Revision: 1274
          http://assorted.svn.sourceforge.net/assorted/?rev=1274&view=rev
Author:   yangzhang
Date:     2009-03-09 22:55:47 +0000 (Mon, 09 Mar 2009)

Log Message:
-----------
added demo of forwarding

Added Paths:
-----------
    sandbox/trunk/src/cc/forward.cc

Added: sandbox/trunk/src/cc/forward.cc
===================================================================
--- sandbox/trunk/src/cc/forward.cc	                        (rev 0)
+++ sandbox/trunk/src/cc/forward.cc	2009-03-09 22:55:47 UTC (rev 1274)
@@ -0,0 +1,36 @@
+// Based on the examples given in this (excellent) blog post:
+//
+// <http://blogs.msdn.com/vcblog/archive/2009/02/03/rvalue-references-c-0x-features-in-vc10-part-2.aspx>
+
+#include <iostream>
+#include <string>
+#include <utility>
+using namespace std;
+
+#define mkinner(type) void inner(type x) { cout << #type ": " << x << endl; }
+mkinner(string &)
+mkinner(const string &)
+mkinner(string &&)
+mkinner(const string &&)
+
+template<typename T> void outer(T &&x) { inner(forward<T>(x)); }
+
+string rvalue() { return "rvalue"; }
+const string crvalue() { return "const rvalue"; }
+string lvalue("lvalue");
+const string clvalue("const lvalue");
+
+int main() {
+  outer(lvalue);
+  outer(clvalue);
+  outer(rvalue());
+  outer(crvalue());
+  return 0;
+}
+
+// Output:
+//
+// string &: lvalue
+// string &: const lvalue
+// string &&: rvalue
+// const string &&: const rvalue


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1273] cpp-commons/trunk/tools/check.bash

[<yan...@us...>]

Revision: 1273
          http://assorted.svn.sourceforge.net/assorted/?rev=1273&view=rev
Author:   yangzhang
Date:     2009-03-09 22:05:23 +0000 (Mon, 09 Mar 2009)

Log Message:
-----------
prevent all.cc from being unnecessarily rebuilt

Modified Paths:
--------------
    cpp-commons/trunk/tools/check.bash

Modified: cpp-commons/trunk/tools/check.bash
===================================================================
--- cpp-commons/trunk/tools/check.bash	2009-03-09 01:50:24 UTC (rev 1272)
+++ cpp-commons/trunk/tools/check.bash	2009-03-09 22:05:23 UTC (rev 1273)
@@ -26,7 +26,7 @@
 
 build-tests() {
   mkdir -p test/build/
-  my-srcs | sed 's/^/#include </; s/$/>/' > test/build/all.cc
+  my-srcs | sed 's/^/#include </; s/$/>/' | clobber-if-diff test/build/all.cc
   for i in $(my-srcs)
   do echo "#include <$i>" | clobber-if-diff test/build/$(basename ${i%.h}).cc
   done


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1272] sandbox/trunk/src/cc

[<yan...@us...>]

Revision: 1272
          http://assorted.svn.sourceforge.net/assorted/?rev=1272&view=rev
Author:   yangzhang
Date:     2009-03-09 01:50:24 +0000 (Mon, 09 Mar 2009)

Log Message:
-----------
added unique_ptr demos

Added Paths:
-----------
    sandbox/trunk/src/cc/unique_ptr03_test.cc
    sandbox/trunk/src/cc/unique_ptr_test.cc

Added: sandbox/trunk/src/cc/unique_ptr03_test.cc
===================================================================
--- sandbox/trunk/src/cc/unique_ptr03_test.cc	                        (rev 0)
+++ sandbox/trunk/src/cc/unique_ptr03_test.cc	2009-03-09 01:50:24 UTC (rev 1272)
@@ -0,0 +1,66 @@
+#include <boost/unique_ptr.hpp>
+#include <vector>
+using namespace boost;
+using namespace std;
+typedef unique_ptr<int> ptr;
+
+ptr mkptr() { return ptr(new int(0)); }
+// Note that we need a move here.
+ptr getptr() { ptr p = mkptr(); return boost::move(p); }
+
+// This just doesn't work.  const is a no-go.
+#if 0
+void eatptr(const ptr &x) {
+  vector<ptr> xs;
+  xs.push_back(boost::move(x));
+}
+void putptr(const ptr &x) { eatptr(x); }
+#endif
+
+namespace copies {
+void eatptr(ptr x) {
+  vector<ptr> xs;
+  xs.push_back(boost::move(x));
+}
+void putptr(ptr x) { eatptr(boost::move(x)); }
+}
+
+namespace lvalrefs {
+void eatptr(ptr &x) {
+  vector<ptr> xs;
+  xs.push_back(boost::move(x));
+}
+void putptr(ptr &x) { eatptr(x); }
+}
+
+namespace rvalrefs {
+void eatptr(ptr &&x) {
+  vector<ptr> xs;
+  xs.push_back(boost::move(x));
+}
+void putptr(ptr &&x) { eatptr(x); }
+}
+
+int main() {
+  ptr q = getptr();
+
+  {
+    using namespace copies;
+    putptr(boost::move(q));
+    putptr(getptr());
+  }
+
+  {
+    using namespace lvalrefs;
+    putptr(q);
+    // Nope: putptr(getptr());
+  }
+
+  {
+    using namespace rvalrefs;
+    putptr(q);
+    putptr(getptr());
+  }
+
+  return 0;
+}

Added: sandbox/trunk/src/cc/unique_ptr_test.cc
===================================================================
--- sandbox/trunk/src/cc/unique_ptr_test.cc	                        (rev 0)
+++ sandbox/trunk/src/cc/unique_ptr_test.cc	2009-03-09 01:50:24 UTC (rev 1272)
@@ -0,0 +1,65 @@
+#include <commons/unique_ptr.h>
+#include <vector>
+using namespace std;
+typedef unique_ptr<int> ptr;
+
+ptr mkptr() { return ptr(new int(0)); }
+// Note that we need a move here.
+ptr getptr() { ptr p = mkptr(); return move(p); }
+
+// This just doesn't work.  const is a no-go.
+#if 0
+void eatptr(const ptr &x) {
+  vector<ptr> xs;
+  xs.push_back(move(x));
+}
+void putptr(const ptr &x) { eatptr(x); }
+#endif
+
+namespace copies {
+  void eatptr(ptr x) {
+    vector<ptr> xs;
+    xs.push_back(move(x));
+  }
+  void putptr(ptr x) { eatptr(move(x)); }
+}
+
+namespace lvalrefs {
+  void eatptr(ptr &x) {
+    vector<ptr> xs;
+    xs.push_back(move(x));
+  }
+  void putptr(ptr &x) { eatptr(x); }
+}
+
+namespace rvalrefs {
+  void eatptr(ptr &&x) {
+    vector<ptr> xs;
+    xs.push_back(move(x));
+  }
+  void putptr(ptr &&x) { eatptr(x); }
+}
+
+int main() {
+  ptr q = getptr();
+
+  {
+    using namespace copies;
+    putptr(move(q));
+    putptr(getptr());
+  }
+
+  {
+    using namespace lvalrefs;
+    putptr(q);
+    // Nope: putptr(getptr());
+  }
+
+  {
+    using namespace rvalrefs;
+    putptr(q);
+    putptr(getptr());
+  }
+
+  return 0;
+}


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1271] sandbox/trunk/src/cc/rvaluerefs.cc

[<yan...@us...>]

Revision: 1271
          http://assorted.svn.sourceforge.net/assorted/?rev=1271&view=rev
Author:   yangzhang
Date:     2009-03-09 00:27:31 +0000 (Mon, 09 Mar 2009)

Log Message:
-----------
added rvalue ref demo

Added Paths:
-----------
    sandbox/trunk/src/cc/rvaluerefs.cc

Added: sandbox/trunk/src/cc/rvaluerefs.cc
===================================================================
--- sandbox/trunk/src/cc/rvaluerefs.cc	                        (rev 0)
+++ sandbox/trunk/src/cc/rvaluerefs.cc	2009-03-09 00:27:31 UTC (rev 1271)
@@ -0,0 +1,29 @@
+// Demo that in gcc 4.3 rvalue references are not quite up to spec.  In
+// particular, move() doesn't seem to be required anywhere.
+
+struct A {};
+void bar(A &&) {}
+void foo(A &&a) { bar(a); }
+
+struct B {
+  B() : p(0) {}
+  B(B &&b) : p(b.p) {}
+private:
+  void *p;
+  B(const B&);
+};
+
+int main() {
+  {
+    A a;
+    A &&b = a;
+    foo(a);
+    foo(b);
+  }
+  {
+    B a;
+    B b;
+    b = a;
+  }
+  return 0;
+}


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1270] cpp-commons/trunk/src/commons

[<yan...@us...>]

Revision: 1270
          http://assorted.svn.sourceforge.net/assorted/?rev=1270&view=rev
Author:   yangzhang
Date:     2009-03-08 09:40:09 +0000 (Sun, 08 Mar 2009)

Log Message:
-----------
tweaks to get unique_ptr to work; still need to fully understand things

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/fast_map.h
    cpp-commons/trunk/src/commons/st/st.h

Modified: cpp-commons/trunk/src/commons/fast_map.h
===================================================================
--- cpp-commons/trunk/src/commons/fast_map.h	2009-03-08 09:39:11 UTC (rev 1269)
+++ cpp-commons/trunk/src/commons/fast_map.h	2009-03-08 09:40:09 UTC (rev 1270)
@@ -125,8 +125,7 @@
    * the application, but more importantly, the interface required the ability
    * to serialize the map, and partially.  The internals have to be exposed in
    * order for fast serialization (i.e. memcpy) to be possible; also, the
-   * ability to serialize just a certain range of the fast_map is also
-   * important.
+   * ability to serialize just a certain range of the fast_map was required.
    */
   template <typename Key, typename Data>
   class fast_map

Modified: cpp-commons/trunk/src/commons/st/st.h
===================================================================
--- cpp-commons/trunk/src/commons/st/st.h	2009-03-08 09:39:11 UTC (rev 1269)
+++ cpp-commons/trunk/src/commons/st/st.h	2009-03-08 09:40:09 UTC (rev 1270)
@@ -196,6 +196,10 @@
   class st_channel
   {
     public:
+      void push(T &&x) {
+        q_.push(boost::move(x));
+        empty_.signal();
+      }
       void push(const T &x) {
         q_.push(x);
         empty_.signal();
@@ -204,11 +208,12 @@
         while (q_.empty()) {
           empty_.wait();
         }
-        T x = front();
+        T x = boost::move(front());
         q_.pop();
-        return x;
+        return boost::move(x);
       }
       const T& front() const { return q_.front(); }
+      T& front() { return q_.front(); }
       bool empty() const { return q_.empty(); }
       void pop() { q_.pop(); }
       void clear() { while (!q_.empty()) q_.pop(); }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1269] ydb/trunk

[<yan...@us...>]

Revision: 1269
          http://assorted.svn.sourceforge.net/assorted/?rev=1269&view=rev
Author:   yangzhang
Date:     2009-03-08 09:39:11 +0000 (Sun, 08 Mar 2009)

Log Message:
-----------
- cleanup
- using fast_map
- added -DNDEBUG to optimized build
- specialized recovery message generation
- using unique_ptr instead of shared_ptr for Recovery channel
- added some more notes/todos
- added ghash to setup

Modified Paths:
--------------
    ydb/trunk/README
    ydb/trunk/src/Makefile
    ydb/trunk/src/main.lzz.clamp
    ydb/trunk/src/ser.h
    ydb/trunk/tools/test.bash

Modified: ydb/trunk/README
===================================================================
--- ydb/trunk/README	2009-03-07 21:30:30 UTC (rev 1268)
+++ ydb/trunk/README	2009-03-08 09:39:11 UTC (rev 1269)
@@ -473,8 +473,58 @@
   - abysmal perf; long wait at the map dump + almost never catch up, but at
     least it works
 
-- TODO speed up backlogging; don't create pb objects, just take buffers
+- report for sam
+  - got the speed up to as fast as it'll go before 1000
+  - added disk logging for workers; still need to grab numbers for the
+    single-node ('no replica') case
+  - added physical logging: slower
+  - adding log transfer vs. state transfer
 
+- DONE added byte length prefixes for faster backlogging
+- DONE speed up backlogging; don't create pb objects, just take buffers
+
+  pseudocode (out of date/buggy)
+    r.setanchor
+    first_start = r.start
+    while true
+      start = r.start
+      headerlen = sizeof([prefix, ntxns, seqno])
+      if r.unread + r.rem < headerlen
+        buf = new buf
+        buf.write([r.start..r.end])
+        swap(r.buf, buf)
+        backlog.push(buf, first_start, start)
+        r.reset
+        first_start = r.start
+      prefix = r.read
+      ntxns = r.read
+      seqno = r.read
+      if ...seqno...
+        if r.rem < prefix - headerlen
+          buf = new buf
+          buf.write([prefix, ntxns, seqno] + [r.start..r.end])
+          swap(r.buf, buf)
+          backlog.push(buf, first_start, start)
+          r.reset
+          first_start = r.start
+          assert r.rem >= prefix - headerlen
+        check0 r.accum(prefix - headerlen)
+
+- DONE notify process_txns to "flush" to backlog (caught up)
+
+- DONE pb_types -> pb_traits, etc.
+
+- DONE try building and using your own map type; compare against other
+  containers
+  - built something really fast, faster than even google dense_hash_map
+
+- TODO experiment with large pages
+
+- TODO use rb instead of pb for recovery state
+
+- TODO test out recovery mode more thoroughly, make sure progress is being
+  made, see how fast it is
+
 - TODO fix multi-recovery if necessary
 
 - TODO speed up map dump; don't use range partitioning, but hash partitioning

Modified: ydb/trunk/src/Makefile
===================================================================
--- ydb/trunk/src/Makefile	2009-03-07 21:30:30 UTC (rev 1268)
+++ ydb/trunk/src/Makefile	2009-03-08 09:39:11 UTC (rev 1269)
@@ -29,7 +29,7 @@
 	PPROF  := -lprofiler
 endif
 ifneq ($(OPT),)
-	OPT    := -O3 -Wdisabled-optimization
+	OPT    := -O3 -Wdisabled-optimization -DNDEBUG
 else
 	OPT    := -g3
 endif

Modified: ydb/trunk/src/main.lzz.clamp
===================================================================
--- ydb/trunk/src/main.lzz.clamp	2009-03-07 21:30:30 UTC (rev 1268)
+++ ydb/trunk/src/main.lzz.clamp	2009-03-08 09:39:11 UTC (rev 1269)
@@ -8,6 +8,8 @@
 #include <boost/scoped_array.hpp>
 #include <boost/shared_ptr.hpp>
 #include <boost/tuple/tuple.hpp>
+#include <boost/unique_ptr.hpp>
+#include <commons/fast_map.h>
 #include <commons/nullptr.h>
 #include <commons/rand.h>
 #include <commons/st/st.h>
@@ -52,9 +54,10 @@
 
 //#define map_t unordered_map
 //#define map_t map
-#define map_t dense_hash_map
-typedef pair<int, int> pii;
+//#define map_t dense_hash_map
+#define map_t fast_map
 typedef map_t<int, int> mii;
+typedef pair<int, int> pii;
 
 typedef tuple<sized_array<char>, char*, char*> chunk;
 
@@ -63,6 +66,10 @@
   map.set_empty_key(-1);
   map.set_deleted_key(-2);
 }
+template<> void init_map(fast_map<int, int> &map) {
+  map.set_empty_key(-1);
+  map.set_deleted_key(-2);
+}
 
 // Configuration.
 st_utime_t timeout;
@@ -731,7 +738,7 @@
  */
 template<typename Types, typename RTypes>
 void
-process_txn(mii&map, const typename Types::Txn &txn, int &seqno,
+process_txn(mii &map, const typename Types::Txn &txn, int &seqno,
             typename RTypes::Response *res)
 {
   typedef typename Types::Txn Txn;
@@ -821,23 +828,6 @@
 }
 #end
 
-template<typename Txn> inline shared_ptr<pb::Txn> to_pb_Txn(Txn txn);
-template<> inline shared_ptr<pb::Txn> to_pb_Txn(pb::Txn txn) {
-  return shared_ptr<pb::Txn>(new pb::Txn(txn));
-}
-template<> inline shared_ptr<pb::Txn> to_pb_Txn(msg::Txn txn) {
-  shared_ptr<pb::Txn> ptxn(new pb::Txn());
-  ptxn->set_seqno(txn.seqno());
-  for (int o = 0; o < txn.op_size(); ++o) {
-    pb::Op *pop = ptxn->add_op();
-    const msg::Op &op = txn.op(o);
-    pop->set_type(static_cast<Op_OpType>(op.type()));
-    pop->set_key(op.key());
-    pop->set_value(op.value());
-  }
-  return ptxn;
-}
-
 /**
  * Actually do the work of executing a transaction and sending back the reply.
  *
@@ -866,7 +856,7 @@
 template<typename Types, typename RTypes>
 void
 process_txns(st_netfd_t leader, mii &map, int &seqno,
-             st_channel<shared_ptr<Recovery> > &send_states,
+             st_channel<unique_ptr<Recovery> > &send_states,
              /* XXX st_channel<shared_ptr<pb::Txn> > &backlog */
              st_channel<chunk> &backlog, int init_seqno,
              int mypos, int nnodes)
@@ -906,7 +896,7 @@
       showtput("live-processed", now, __ref(time_caught_up), __ref(seqno),
                __ref(seqno_caught_up));
     }
-    __ref(send_states).push(shared_ptr<Recovery>());
+    __ref(send_states).push(unique_ptr<Recovery>());
     __ref(w).mark_and_flush();
     st_sleep(1);
   });
@@ -1038,30 +1028,9 @@
         }
       } else if (multirecover || mypos == 0) {
         // Empty (default) TxnBatch means "generate a snapshot."
-        // TODO make this faster
-        cout << "generating recovery..." << endl;
-        shared_ptr<Recovery> recovery(new Recovery);
-        typedef ::map<int, int> mii_;
-        mii_ map_(map.begin(), map.end());
-        mii_::const_iterator begin =
-          map_.lower_bound(multirecover ? interp(RAND_MAX, mypos, nnodes) : 0);
-        mii_::const_iterator end = multirecover && mypos < nnodes - 1 ?
-          map_.lower_bound(interp(RAND_MAX, mypos + 1, nnodes)) : map_.end();
-        cout << "generating recovery over " << begin->first << ".."
-             << (end == map_.end() ? "end" : lexical_cast<string>(end->first));
-        if (multirecover)
-          cout << " (node " << mypos << " of " << nnodes << ")";
-        cout << endl;
-        long long start_snap = current_time_millis();
-        foreach (const pii &p, make_iterator_range(begin, end)) {
-          Recovery_Pair *pair = recovery->add_pair();
-          pair->set_key(p.first);
-          pair->set_value(p.second);
-        }
-        cout << "generating recovery took "
-             << current_time_millis() - start_snap << " ms" << endl;
+        unique_ptr<Recovery> recovery(make_recovery(map, mypos, nnodes));
         recovery->set_seqno(seqno);
-        send_states.push(recovery);
+        send_states.push(boost::move(recovery));
       }
     }
   } catch (break_exception &ex) {
@@ -1069,6 +1038,33 @@
 
 }
 
+template<typename mii>
+unique_ptr<Recovery> make_recovery(const mii &map, int mypos, int nnodes) {
+  // TODO make this faster
+  cout << "generating recovery..." << endl;
+  unique_ptr<Recovery> recovery(new Recovery);
+  typedef ::map<int, int> mii_;
+  mii_ map_(map.begin(), map.end());
+  mii_::const_iterator begin =
+    map_.lower_bound(multirecover ? interp(RAND_MAX, mypos, nnodes) : 0);
+  mii_::const_iterator end = multirecover && mypos < nnodes - 1 ?
+    map_.lower_bound(interp(RAND_MAX, mypos + 1, nnodes)) : map_.end();
+  cout << "generating recovery over " << begin->first << ".."
+       << (end == map_.end() ? "end" : lexical_cast<string>(end->first));
+  if (multirecover)
+    cout << " (node " << mypos << " of " << nnodes << ")";
+  cout << endl;
+  long long start_snap = current_time_millis();
+  foreach (const pii &p, make_iterator_range(begin, end)) {
+    Recovery_Pair *pair = recovery->add_pair();
+    pair->set_key(p.first);
+    pair->set_value(p.second);
+  }
+  cout << "generating recovery took "
+       << current_time_millis() - start_snap << " ms" << endl;
+  return boost::move(recovery);
+}
+
 class response_handler
 {
 public:
@@ -1100,7 +1096,7 @@
     commons::array<char> rbuf(read_buf_size), wbuf(buf_size);
     st_reader reader(replica, rbuf.get(), rbuf.size());
     writer w(lambda(const void*, size_t) {
-      throw operation_not_supported("response handler should not be writing");
+      throw not_supported_exception("response handler should not be writing");
     }, wbuf.get(), wbuf.size());
     stream s(reader,w);
 
@@ -1258,10 +1254,10 @@
  */
 void
 recover_joiner(st_netfd_t listener,
-               st_channel<shared_ptr<Recovery> > &send_states)
+               st_channel<unique_ptr<Recovery> > &send_states)
 {
   st_netfd_t joiner;
-  shared_ptr<Recovery> recovery;
+  unique_ptr<Recovery> recovery;
   {
     st_intr intr(stop_hub);
     // Wait for the snapshot.
@@ -1441,7 +1437,7 @@
       }
     }
   });
-  st_channel<shared_ptr<Recovery> > send_states;
+  st_channel<unique_ptr<Recovery> > send_states;
 
   cout << "starting as replica on port " << listen_port << endl;
 
@@ -1551,7 +1547,7 @@
       commons::array<char> rbuf(0), wbuf(buf_size);
       reader reader(nullptr, rbuf.get(), rbuf.size());
       writer writer(lambda(const void*, size_t) {
-       throw operation_not_supported("should not be writing responses during catch-up phase");
+       throw not_supported_exception("should not be writing responses during catch-up phase");
       }, wbuf.get(), wbuf.size());
       stream s(reader, writer);
       TxnBatch batch(s);

Modified: ydb/trunk/src/ser.h
===================================================================
--- ydb/trunk/src/ser.h	2009-03-07 21:30:30 UTC (rev 1268)
+++ ydb/trunk/src/ser.h	2009-03-08 09:39:11 UTC (rev 1269)
@@ -34,13 +34,13 @@
   }
 
 #define EXPAND_PB \
-    bool AppendToString(string*) const { throw_operation_not_supported(); } \
-    bool SerializeToArray(void*, int) const { throw_operation_not_supported(); } \
-    bool SerializeToString(string*) const { throw_operation_not_supported(); } \
-    bool SerializeToOstream(ostream*) const { throw_operation_not_supported(); } \
-    bool ParseFromArray(void*, int) { throw_operation_not_supported(); } \
-    int GetCachedSize() const { throw_operation_not_supported(); } \
-    int ByteSize() const { throw_operation_not_supported(); } \
+    bool AppendToString(string*) const { throw_not_supported(); } \
+    bool SerializeToArray(void*, int) const { throw_not_supported(); } \
+    bool SerializeToString(string*) const { throw_not_supported(); } \
+    bool SerializeToOstream(ostream*) const { throw_not_supported(); } \
+    bool ParseFromArray(void*, int) { throw_not_supported(); } \
+    int GetCachedSize() const { throw_not_supported(); } \
+    int ByteSize() const { throw_not_supported(); } \
 
 #define MAKE_TYPE_BATCH(name, ns, b) \
   struct name##_traits { \

Modified: ydb/trunk/tools/test.bash
===================================================================
--- ydb/trunk/tools/test.bash	2009-03-07 21:30:30 UTC (rev 1268)
+++ ydb/trunk/tools/test.bash	2009-03-08 09:39:11 UTC (rev 1269)
@@ -225,6 +225,7 @@
   parremote node-setup-bison
   parremote node-setup-clamp
   parremote node-setup-gtest
+  parremote node-setup-ghash
 }
 
 setup-ydb() {


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1268] cpp-commons/trunk/src

[<yan...@us...>]

Revision: 1268
          http://assorted.svn.sourceforge.net/assorted/?rev=1268&view=rev
Author:   yangzhang
Date:     2009-03-07 21:30:30 +0000 (Sat, 07 Mar 2009)

Log Message:
-----------
- added some load tests for fast_map
- fixed an index-out-of-bounds bug, using incorrect index into old table when growing

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/fast_map.h
    cpp-commons/trunk/src/test/fast_map.cc

Modified: cpp-commons/trunk/src/commons/fast_map.h
===================================================================
--- cpp-commons/trunk/src/commons/fast_map.h	2009-03-07 21:18:08 UTC (rev 1267)
+++ cpp-commons/trunk/src/commons/fast_map.h	2009-03-07 21:30:30 UTC (rev 1268)
@@ -169,7 +169,7 @@
                  pos = (pos + ++probe) & mask) {
               assert(probe < newtab.size());
             }
-            newtab[pos] = table[pos];
+            newtab[pos] = table[i];
           }
         }
         swap(newtab, table);

Modified: cpp-commons/trunk/src/test/fast_map.cc
===================================================================
--- cpp-commons/trunk/src/test/fast_map.cc	2009-03-07 21:18:08 UTC (rev 1267)
+++ cpp-commons/trunk/src/test/fast_map.cc	2009-03-07 21:30:30 UTC (rev 1268)
@@ -1,8 +1,13 @@
 #include <commons/fast_map.h>
+#include <commons/rand.h>
 #include <boost/foreach.hpp>
+#include <map>
 #include "test.h"
+using namespace std;
 
 static const char *unset_key_string = "Assertion `has_empty_key && has_deleted_key' failed.";
+typedef fast_map<int, int> map_t;
+typedef pair<int, int> pii;
 
 template<typename T>
 void const_uninit_tests(T &fm) {
@@ -36,7 +41,6 @@
   EXPECT_TRUE(fm.begin() == fm.find(0));
   EXPECT_TRUE(fm.end() == fm.find(1));
 
-  typedef pair<int, int> pii;
   size_t counter = 0;
   vector<int> xs(20);
   for (typeof(fm.begin()) it = fm.begin();
@@ -53,7 +57,6 @@
 }
 
 TEST(fast_map, basics) {
-  typedef fast_map<int, int> map_t;
   map_t fm;
 
   // Uninitialized tests.
@@ -81,3 +84,31 @@
     EXPECT_EQ(4*i, fm[2*i]);
   }
 }
+
+TEST(fast_map, randload) {
+  map_t fm;
+  map<int, int> m;
+  fm.set_empty_key(-1);
+  fm.set_deleted_key(-2);
+  for (int i = 0; i < 1<<22; ++i) {
+    int k = randint();
+    if (fm.find(k) == fm.end()) {
+      int v = randint();
+      fm[k] = v;
+      m[k] = v;
+    }
+  }
+  foreach (const pii &p, m) {
+    EXPECT_EQ(p.second, fm[p.first]);
+  }
+}
+
+TEST(fast_map, load) {
+  map_t m;
+  m.set_empty_key(-1);
+  m.set_deleted_key(-2);
+  for (int i = 0; i < 1<<22; ++i)
+    m[i] = i<<1;
+  for (int i = 0; i < 1<<22; ++i)
+    EXPECT_EQ(i<<1, m[i]);
+}


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1267] cpp-commons/trunk/src

[<yan...@us...>]

Revision: 1267
          http://assorted.svn.sourceforge.net/assorted/?rev=1267&view=rev
Author:   yangzhang
Date:     2009-03-07 21:18:08 +0000 (Sat, 07 Mar 2009)

Log Message:
-----------
- added iterators and a bunch of other standards-conforming features to
  fast_map
- added fast_map tests

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/fast_map.h

Added Paths:
-----------
    cpp-commons/trunk/src/test/fast_map.cc

Modified: cpp-commons/trunk/src/commons/fast_map.h
===================================================================
--- cpp-commons/trunk/src/commons/fast_map.h	2009-03-07 21:15:20 UTC (rev 1266)
+++ cpp-commons/trunk/src/commons/fast_map.h	2009-03-07 21:18:08 UTC (rev 1267)
@@ -1,16 +1,120 @@
 #ifndef COMMONS_DENSE_HASH_MAP_H
 #define COMMONS_DENSE_HASH_MAP_H
 
-#include <backward/hash_fun.h>
+#include <boost/functional/hash.hpp>
 #include <cassert>
 #include <commons/array.h>
+#include <commons/exceptions.h>
 #include <utility>
 
 namespace commons {
 
+  using namespace boost;
   using namespace std;
-  using namespace __gnu_cxx;
 
+  // TODO write unit tests
+
+  template<typename Key, typename Data> class fast_map;
+  template<typename map_traits> class fast_map_iterator;
+  template<typename map_traits> class fast_map_const_iterator;
+
+  template<typename Key, typename Data>
+  struct fast_map_traits
+  {
+    typedef fast_map<Key, Data> map_type;
+    typedef Key key_type;
+    typedef Data data_type;
+    typedef pair<key_type, data_type> value_type;
+    typedef fast_map_traits<Key, Data> traits;
+
+    typedef value_type &reference;
+    typedef const value_type &const_reference;
+    typedef value_type *pointer;
+    typedef const value_type *const_pointer;
+    typedef fast_map_iterator<traits> iterator;
+    typedef fast_map_const_iterator<traits> const_iterator;
+    typedef size_t size_type;
+    typedef ptrdiff_t difference_type;
+  };
+
+  template<typename map_traits>
+  class fast_map_const_iterator
+  {
+  public:
+    typedef typename map_traits::map_type map_type;
+    typedef typename map_traits::iterator iterator;
+    typedef typename map_traits::const_iterator const_iterator;
+    typedef typename map_traits::value_type value_type;
+    typedef typename map_traits::reference reference;
+    typedef typename map_traits::const_reference const_reference;
+    typedef typename map_traits::pointer pointer;
+    typedef typename map_traits::const_pointer const_pointer;
+    typedef typename map_traits::size_type size_type;
+    typedef typename map_traits::difference_type difference_type;
+    typedef forward_iterator_tag iterator_category;
+  private:
+    const map_type &m;
+    const value_type *p;
+    const value_type *end;
+  public:
+    fast_map_const_iterator(const map_type &m, const value_type *p)
+      : m(m), p(p), end(m.get_table().end()) { increment(); }
+    void increment() { for (; p != end && m.empty_or_deleted(p->first); ++p) {} }
+    const_iterator &operator++() {
+      ++p;
+      increment();
+      return *this;
+    }
+    const_iterator operator++(int) {
+      fast_map_const_iterator copy = *this;
+      ++*this;
+      return copy;
+    }
+    const_reference operator*() const { return *p; }
+    const_pointer operator->() const { return p; }
+    bool operator==(const const_iterator &it) const { return p == it.p; }
+    bool operator!=(const const_iterator &it) const { return p != it.p; }
+  };
+
+  template<typename map_traits>
+  class fast_map_iterator
+  {
+  public:
+    typedef typename map_traits::map_type map_type;
+    typedef typename map_traits::iterator iterator;
+    typedef typename map_traits::const_iterator const_iterator;
+    typedef typename map_traits::value_type value_type;
+    typedef typename map_traits::reference reference;
+    typedef typename map_traits::const_reference const_reference;
+    typedef typename map_traits::pointer pointer;
+    typedef typename map_traits::const_pointer const_pointer;
+    typedef typename map_traits::size_type size_type;
+    typedef typename map_traits::difference_type difference_type;
+    typedef forward_iterator_tag iterator_category;
+  private:
+    map_type &m;
+    value_type *p;
+    value_type *end;
+  public:
+    fast_map_iterator(map_type &m, value_type *p)
+      : m(m), p(p), end(m.get_table().end()) { increment(); }
+    void increment() { for (; p != end && m.empty_or_deleted(p->first); ++p) {} }
+    iterator &operator++() {
+      ++p;
+      increment();
+      return *this;
+    }
+    iterator operator++(int) {
+      fast_map_iterator copy = *this;
+      ++*this;
+      return copy;
+    }
+    reference operator*() const { return *p; }
+    pointer operator->() const { return p; }
+    bool operator==(const iterator &it) const { return p == it.p; }
+    bool operator!=(const iterator &it) const { return p != it.p; }
+  };
+
   /**
    * Quadratic internal probing with triangular numbers, a la
    * google::dense_hash_map.  Took the overall design from
@@ -24,66 +128,147 @@
    * ability to serialize just a certain range of the fast_map is also
    * important.
    */
-  // TODO someday: template <typename K, typename V>
+  template <typename Key, typename Data>
   class fast_map
   {
+    public:
+      typedef fast_map_traits<Key, Data> traits;
+      typedef typename traits::map_type map_type;
+      typedef typename traits::iterator iterator;
+      typedef typename traits::const_iterator const_iterator;
+      typedef typename traits::key_type key_type;
+      typedef typename traits::data_type data_type;
+      typedef typename traits::value_type value_type;
+      typedef typename traits::reference reference;
+      typedef typename traits::const_reference const_reference;
+      typedef typename traits::pointer pointer;
+      typedef typename traits::const_pointer const_pointer;
+
     private:
-      static const size_t initsize = 1<<20;
-      typedef pair<int, int> entry;
-      commons::array<entry> table;
-      int empty_key, deleted_key;
+      static const size_t initsize = 1 << 20;
+      commons::array<value_type> table;
+      key_type empty_key, deleted_key;
       size_t count;
-      hash<int> hasher;
+      boost::hash<key_type> hasher;
+      bool has_empty_key, has_deleted_key;
+
       void resize(size_t size) {
-        commons::array<entry> tmp(size);
-        // TODO faster?
+        commons::array<value_type> newtab(0);
+        newtab.reset(reinterpret_cast<value_type*>(new char[size * sizeof(value_type)]), size);
         for (size_t i = 0; i < size; ++i)
-          tmp[i].first = empty_key;
-        swap(table, tmp);
+          newtab[i].first = empty_key;
         // 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) {
+        size_t mask = newtab.size() - 1;
+        for (size_t i = 0; i < table.size(); ++i) {
+          if (table[i].first != empty_key && table[i].first != deleted_key) {
             // 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;
+            size_t pos = hasher(table[i].first) & mask;
             for (size_t probe = 0;
-                 table[pos].first != empty_key;
-                 ++probe, pos = (pos + probe) & mask) {
-              assert(probe < table.size());
+                 newtab[pos].first != empty_key;
+                 pos = (pos + ++probe) & mask) {
+              assert(probe < newtab.size());
             }
-            table[pos] = tmp[pos];
+            newtab[pos] = table[pos];
           }
         }
+        swap(newtab, table);
       }
+
       void grow() { resize(table.size() << 1); }
       void shrink() { resize(table.size() >> 1); }
+      void assert_init() const { assert(has_empty_key && has_deleted_key); }
+
     public:
-      fast_map() : 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); }
+      fast_map() :
+        table(0), empty_key(0), deleted_key(0), count(0), has_empty_key(false),
+        has_deleted_key(false) {}
+      void set_empty_key(key_type k) {
+        has_empty_key = true;
+        empty_key = k;
+        resize(initsize);
+      }
+      void set_deleted_key(key_type k) {
+        has_deleted_key = true;
+        deleted_key = k;
+        resize(initsize);
+      }
       size_t size() const { return count; }
-      int &operator[](int k) {
-        size_t mask = table.size() - 1;
-        size_t probe, pos = hasher(k) & mask; // , unset = -1, first_deleted = unset;
+      void erase(iterator) { throw_not_implemented(); }
+      array<value_type> &get_table() { return table; }
+      const array<value_type> &get_table() const { return table; }
+      bool empty_or_deleted(key_type k) const { return k == empty_key || k == deleted_key; }
+
+      iterator begin() {
+        assert_init();
+        if (count == 0) return end();
+        else return iterator(*this, table.begin());
+      }
+      const_iterator begin() const {
+        assert_init();
+        if (count == 0) return end();
+        else return const_iterator(*this, table.begin());
+      }
+
+      iterator end() {
+        assert_init();
+        return iterator(*this, table.end());
+      }
+      const_iterator end() const {
+        assert_init();
+        return const_iterator(*this, table.end());
+      }
+
+      const_iterator find(key_type k) const {
+        assert_init();
+        size_t probe = 0, mask = table.size() - 1, pos = hasher(k) & mask;
+        while (true) {
+          if (table[pos].first == empty_key) return end();
+          if (table[pos].first == k) return const_iterator(*this, &table[pos]);
+          pos = (pos + ++probe) & mask;
+        }
+      }
+
+      iterator find(key_type k) {
+        assert_init();
+        size_t probe = 0, mask = table.size() - 1, pos = hasher(k) & mask;
+        while (true) {
+          if (table[pos].first == empty_key) return end();
+          if (table[pos].first == k) return iterator(*this, &table[pos]);
+          pos = (pos + ++probe) & mask;
+        }
+#if 0
+        for (;
+             table[pos].first != empty_key && table[pos].first != k;
+             pos = (pos + ++probe) & mask) {
+          assert(probe < table.size());
+        }
+        if (table[pos].first == empty_key) return end();
+        else return &table[pos];
+#endif
+      }
+
+      data_type &operator[](key_type k) {
+        assert_init();
+        size_t probe = 0, 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;
+        for (;
              table[pos].first != deleted_key && table[pos].first != empty_key && table[pos].first != k;
-             ++probe, pos = (pos + probe) & mask) {
+             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) {
+               pos = (pos + ++probe) & mask) {
             assert(probe < table.size());
           }
           if (table[pos].first == empty_key) {
-            // Inserting new entry.  Grow table if necessary.
+            // Inserting new value_type.  Grow table if necessary.
             if (++count > table.size() * 3 / 4) {
               --count;
               grow();
@@ -93,7 +278,7 @@
             table[pos].first = k;
           }
         } else if (table[pos].first == empty_key) {
-          // Inserting new entry.  Grow table if necessary.
+          // Inserting new value_type.  Grow table if necessary.
           if (++count > table.size() * 3 / 4) {
             --count;
             grow();

Added: cpp-commons/trunk/src/test/fast_map.cc
===================================================================
--- cpp-commons/trunk/src/test/fast_map.cc	                        (rev 0)
+++ cpp-commons/trunk/src/test/fast_map.cc	2009-03-07 21:18:08 UTC (rev 1267)
@@ -0,0 +1,83 @@
+#include <commons/fast_map.h>
+#include <boost/foreach.hpp>
+#include "test.h"
+
+static const char *unset_key_string = "Assertion `has_empty_key && has_deleted_key' failed.";
+
+template<typename T>
+void const_uninit_tests(T &fm) {
+  ASSERT_DEATH(fm.begin(), unset_key_string);
+  ASSERT_DEATH(fm.end(), unset_key_string);
+  ASSERT_DEATH(fm.find(0), unset_key_string);
+}
+
+template<typename T>
+void const_empty_tests(T &fm) {
+  EXPECT_EQ(0, fm.size());
+  EXPECT_TRUE(fm.begin() == fm.end());
+  EXPECT_TRUE(fm.find(0) == fm.end());
+  EXPECT_FALSE(fm.begin() != fm.end());
+  EXPECT_FALSE(fm.find(0) != fm.end());
+}
+
+template<typename T>
+void const_nonempty_tests(T &fm) {
+  EXPECT_EQ(10, fm.size());
+  EXPECT_TRUE(fm.begin() != fm.end());
+  EXPECT_TRUE(fm.find(0) != fm.end());
+  EXPECT_FALSE(fm.begin() == fm.end());
+  EXPECT_FALSE(fm.find(0) == fm.end());
+  for (int i = 0; i < 10; ++i) {
+    EXPECT_EQ(2*i, fm.find(2*i)->first);
+    EXPECT_EQ(2*i, (*fm.find(2*i)).first);
+    EXPECT_EQ(4*i, fm.find(2*i)->second);
+    EXPECT_EQ(4*i, (*fm.find(2*i)).second);
+  }
+  EXPECT_TRUE(fm.begin() == fm.find(0));
+  EXPECT_TRUE(fm.end() == fm.find(1));
+
+  typedef pair<int, int> pii;
+  size_t counter = 0;
+  vector<int> xs(20);
+  for (typeof(fm.begin()) it = fm.begin();
+       it != fm.end();
+       ++it) {
+    const pii &p = *it;
+    ++counter;
+    xs[p.first] = p.second;
+  }
+  for (int i = 0; i < 10; ++i) {
+    EXPECT_EQ(4 * i, xs[2 * i]);
+  }
+  EXPECT_EQ(10, counter);
+}
+
+TEST(fast_map, basics) {
+  typedef fast_map<int, int> map_t;
+  map_t fm;
+
+  // Uninitialized tests.
+  const_uninit_tests(fm);
+  const_uninit_tests<const map_t>(fm);
+  ASSERT_DEATH(fm[0], unset_key_string);
+
+  // Initialize, leave empty.
+  fm.set_empty_key(-1);
+  fm.set_deleted_key(-2);
+
+  // Empty tests.
+  const_empty_tests(fm);
+  const_empty_tests<const map_t>(fm);
+
+  // Fill.
+  for (int i = 0; i < 10; ++i) {
+    fm[2*i] = 4*i;
+  }
+
+  // Filled tests.
+  const_nonempty_tests(fm);
+  const_nonempty_tests<const map_t>(fm);
+  for (int i = 0; i < 10; ++i) {
+    EXPECT_EQ(4*i, fm[2*i]);
+  }
+}


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1266] cpp-commons/trunk/src/test

[<yan...@us...>]

Revision: 1266
          http://assorted.svn.sourceforge.net/assorted/?rev=1266&view=rev
Author:   yangzhang
Date:     2009-03-07 21:15:20 +0000 (Sat, 07 Mar 2009)

Log Message:
-----------
added test.h, refactoring out common test code

Modified Paths:
--------------
    cpp-commons/trunk/src/test/streamreader.cc
    cpp-commons/trunk/src/test/streamwriter.cc

Added Paths:
-----------
    cpp-commons/trunk/src/test/test.h

Modified: cpp-commons/trunk/src/test/streamreader.cc
===================================================================
--- cpp-commons/trunk/src/test/streamreader.cc	2009-03-06 21:17:27 UTC (rev 1265)
+++ cpp-commons/trunk/src/test/streamreader.cc	2009-03-07 21:15:20 UTC (rev 1266)
@@ -1,8 +1,6 @@
 #include <commons/array.h>
 #include <commons/streamreader.h>
-#include <gtest/gtest.h>
-using namespace commons;
-using namespace testing;
+#include "test.h"
 
 struct rfn {
   size_t chunklen_;
@@ -62,8 +60,3 @@
     }
   }
 }
-
-int main(int argc, char **argv) {
-  InitGoogleTest(&argc, argv);
-  return RUN_ALL_TESTS();
-}

Modified: cpp-commons/trunk/src/test/streamwriter.cc
===================================================================
--- cpp-commons/trunk/src/test/streamwriter.cc	2009-03-06 21:17:27 UTC (rev 1265)
+++ cpp-commons/trunk/src/test/streamwriter.cc	2009-03-07 21:15:20 UTC (rev 1266)
@@ -1,8 +1,6 @@
 #include <commons/array.h>
 #include <commons/streamwriter.h>
-#include <gtest/gtest.h>
-using namespace commons;
-using namespace testing;
+#include "test.h"
 
 struct wfn {
   array<char> &dst_;
@@ -27,8 +25,3 @@
       EXPECT_EQ(i, *(reinterpret_cast<int*>(dst.get()) + i + 1));
   }
 }
-
-int main(int argc, char **argv) {
-  InitGoogleTest(&argc, argv);
-  return RUN_ALL_TESTS();
-}

Added: cpp-commons/trunk/src/test/test.h
===================================================================
--- cpp-commons/trunk/src/test/test.h	                        (rev 0)
+++ cpp-commons/trunk/src/test/test.h	2009-03-07 21:15:20 UTC (rev 1266)
@@ -0,0 +1,14 @@
+#ifndef COMMONS_TEST_H
+#define COMMONS_TEST_H
+
+#include <gtest/gtest.h>
+#define foreach BOOST_FOREACH
+using namespace commons;
+using namespace testing;
+
+int main(int argc, char **argv) {
+  InitGoogleTest(&argc, argv);
+  return RUN_ALL_TESTS();
+}
+
+#endif


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1265] cpp-commons/trunk/src/commons/array.h

[<yan...@us...>]

Revision: 1265
          http://assorted.svn.sourceforge.net/assorted/?rev=1265&view=rev
Author:   yangzhang
Date:     2009-03-06 21:17:27 +0000 (Fri, 06 Mar 2009)

Log Message:
-----------
added begin to array and sized_array

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/array.h

Modified: cpp-commons/trunk/src/commons/array.h
===================================================================
--- cpp-commons/trunk/src/commons/array.h	2009-03-06 21:17:18 UTC (rev 1264)
+++ cpp-commons/trunk/src/commons/array.h	2009-03-06 21:17:27 UTC (rev 1265)
@@ -30,6 +30,7 @@
         explicit sized_array(char *p, size_t n) : p_(p), n_(n) {}
         size_t size() const { return n_; }
         T *get() const { return p_; }
+        T *begin() const { return p_; }
         T *end() const { return p_ + n_; }
         const T &operator[](size_t i) const { return p_[i]; }
         T &operator[](size_t i) { return p_[i]; }
@@ -53,6 +54,7 @@
         size_t size() const { return n_; }
         T *get() const { return p_.get(); }
         T *release() { return p_.release(); }
+        T *begin() const { return p_.get(); }
         T *end() const { return this->get() + n_; }
         const T &operator[](size_t i) const { return p_[i]; }
         T &operator[](size_t i) { return p_[i]; }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1264] cpp-commons/trunk/src/commons/exceptions.h

[<yan...@us...>]

Revision: 1264
          http://assorted.svn.sourceforge.net/assorted/?rev=1264&view=rev
Author:   yangzhang
Date:     2009-03-06 21:17:18 +0000 (Fri, 06 Mar 2009)

Log Message:
-----------
added not_implemented_exception; renamed operation_not_supported -> not_supported_exception

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/exceptions.h

Modified: cpp-commons/trunk/src/commons/exceptions.h
===================================================================
--- cpp-commons/trunk/src/commons/exceptions.h	2009-03-06 21:16:17 UTC (rev 1263)
+++ cpp-commons/trunk/src/commons/exceptions.h	2009-03-06 21:17:18 UTC (rev 1264)
@@ -9,16 +9,26 @@
 
   using namespace std;
 
-  class operation_not_supported : public std::exception
+  class not_implemented_exception : public std::exception
   {
     public:
-      operation_not_supported(const string &op) : msg("operation not supported: " + op) {}
-      ~operation_not_supported() throw() {}
+      not_implemented_exception(const string &op) : msg("operation not implemented: " + op) {}
+      ~not_implemented_exception() throw() {}
       const char *what() const throw() { return msg.c_str(); }
     private:
       const string msg;
   };
 
+  class not_supported_exception : public std::exception
+  {
+    public:
+      not_supported_exception(const string &op) : msg("operation not supported: " + op) {}
+      ~not_supported_exception() throw() {}
+      const char *what() const throw() { return msg.c_str(); }
+    private:
+      const string msg;
+  };
+
   class msg_exception : public std::exception
   {
     public:
@@ -29,7 +39,8 @@
       const string msg_;
   };
 
-#define throw_operation_not_supported() throw operation_not_supported(__PRETTY_FUNCTION__)
+#define throw_not_supported() throw not_supported_exception(__PRETTY_FUNCTION__)
+#define throw_not_implemented() throw not_implemented_exception(__PRETTY_FUNCTION__)
 
 }
 


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1263] cpp-commons/trunk/src/boost/unique_ptr.hpp

[<yan...@us...>]

Revision: 1263
          http://assorted.svn.sourceforge.net/assorted/?rev=1263&view=rev
Author:   yangzhang
Date:     2009-03-06 21:16:17 +0000 (Fri, 06 Mar 2009)

Log Message:
-----------
resolved ambiguous move() between std and boost

Modified Paths:
--------------
    cpp-commons/trunk/src/boost/unique_ptr.hpp

Modified: cpp-commons/trunk/src/boost/unique_ptr.hpp
===================================================================
--- cpp-commons/trunk/src/boost/unique_ptr.hpp	2009-03-06 20:54:16 UTC (rev 1262)
+++ cpp-commons/trunk/src/boost/unique_ptr.hpp	2009-03-06 21:16:17 UTC (rev 1263)
@@ -132,7 +132,7 @@
 >::type
 forward(typename detail_unique_ptr::identity<T>::type& t)
 {
-    return move(t);
+    return boost::move(t);
 }
 
 template <class T>
@@ -144,7 +144,7 @@
 >::type
 forward(const typename detail_unique_ptr::identity<T>::type& t)
 {
-    return move(const_cast<T&>(t));
+    return boost::move(const_cast<T&>(t));
 }
 
 namespace detail_unique_ptr {
@@ -167,10 +167,10 @@
     unique_ptr_storage() : t1_(), t2_() {}
 
     explicit unique_ptr_storage(T1 t1)
-        : t1_(move(t1)), t2_() {}
+        : t1_(boost::move(t1)), t2_() {}
 
     unique_ptr_storage(T1 t1, T2 t2)
-        : t1_(move(t1)), t2_(forward<T2>(t2)) {}
+        : t1_(boost::move(t1)), t2_(forward<T2>(t2)) {}
 
           T1& first()       {return t1_;}
     const T1& first() const {return t1_;}
@@ -194,10 +194,10 @@
     unique_ptr_storage() : t1_() {}
 
     explicit unique_ptr_storage(T1 t1)
-        : t1_(move(t1)) {}
+        : t1_(boost::move(t1)) {}
 
     unique_ptr_storage(T1 t1, T2 t2)
-        : t2_(move(t2)), t1_(move(t1)) {}
+        : t2_(boost::move(t2)), t1_(boost::move(t1)) {}
 
           T1& first()       {return t1_;}
     const T1& first() const {return t1_;}
@@ -316,7 +316,7 @@
     unique_ptr& operator=(detail_unique_ptr::rv<unique_ptr> r)
     {
         reset(r->release());
-        ptr_.second() = move(r->get_deleter());
+        ptr_.second() = boost::move(r->get_deleter());
         return *this;
     }
 
@@ -335,7 +335,7 @@
 
     unique_ptr(pointer p, typename mpl::if_<is_reference<D>,
                           volatile typename remove_reference<D>::type&, D>::type d)
-        : ptr_(move(p), forward<D>(const_cast<typename add_reference<D>::type>(d))) {}
+        : ptr_(boost::move(p), forward<D>(const_cast<typename add_reference<D>::type>(d))) {}
 
     template <class U, class E>
         unique_ptr(unique_ptr<U, E> u,
@@ -364,7 +364,7 @@
         operator=(unique_ptr<U, E> u)
         {
             reset(u.release());
-            ptr_.second() = move(u.get_deleter());
+            ptr_.second() = boost::move(u.get_deleter());
             return *this;
         }
 
@@ -418,7 +418,7 @@
     unique_ptr& operator=(detail_unique_ptr::rv<unique_ptr> r)
     {
         reset(r->release());
-        ptr_.second() = move(r->get_deleter());
+        ptr_.second() = boost::move(r->get_deleter());
         return *this;
     }
 
@@ -437,7 +437,7 @@
 
     unique_ptr(pointer p, typename mpl::if_<is_reference<D>,
                           volatile typename remove_reference<D>::type&, D>::type d)
-        : ptr_(move(p), forward<D>(const_cast<typename add_reference<D>::type>(d))) {}
+        : ptr_(boost::move(p), forward<D>(const_cast<typename add_reference<D>::type>(d))) {}
 
     ~unique_ptr() {reset();}
 


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1262] sandbox/trunk/src/cc/fwd.cc

[<yan...@us...>]

Revision: 1262
          http://assorted.svn.sourceforge.net/assorted/?rev=1262&view=rev
Author:   yangzhang
Date:     2009-03-06 20:54:16 +0000 (Fri, 06 Mar 2009)

Log Message:
-----------
added demo of using templates to circumvent forward declarations

Added Paths:
-----------
    sandbox/trunk/src/cc/fwd.cc

Added: sandbox/trunk/src/cc/fwd.cc
===================================================================
--- sandbox/trunk/src/cc/fwd.cc	                        (rev 0)
+++ sandbox/trunk/src/cc/fwd.cc	2009-03-06 20:54:16 UTC (rev 1262)
@@ -0,0 +1,57 @@
+// This doesn't work: invalid use of incomplete type.
+#if 0
+struct container;
+struct iter {
+  container &c;
+  int *p;
+  iter(container &c) : c(c), p(&c.value()) {}
+};
+struct container {
+  int x;
+  int &value() { return x; }
+  iter begin() { return iter(*this); }
+};
+int main() {
+  container c;
+  c.begin();
+  return 0;
+}
+#endif
+
+// This *does* work.
+template<typename T> struct container;
+template<typename T> struct iter {
+  container<T> &c;
+  T *p;
+  iter(container<T> &c) : c(c), p(&c.value()) {}
+};
+template<typename T> struct container {
+  T x;
+  T &value() { return x; }
+  iter<T> begin() { return iter<T>(*this); }
+};
+int main() {
+  container<int> c;
+  c.begin();
+  return 0;
+};
+
+// This doesn't work either.
+#if 0
+template<typename T> struct container;
+template<typename T> struct iter {
+  container<int> &c;
+  int *p;
+  iter(container<int> &c) : c(c), p(&c.value()) {}
+};
+template<typename T> struct container {
+  int x;
+  int &value() { return x; }
+  iter<int> begin() { return iter<int>(*this); }
+};
+int main() {
+  container<int> c;
+  c.begin();
+  return 0;
+}
+#endif


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1261] cpp-commons/trunk/src/commons/fast_map.h

[<yan...@us...>]

Revision: 1261
          http://assorted.svn.sourceforge.net/assorted/?rev=1261&view=rev
Author:   yangzhang
Date:     2009-03-06 07:27:49 +0000 (Fri, 06 Mar 2009)

Log Message:
-----------
added some documentation; cleaned up/removed commented code (moved to the "journey" in the sandbox)

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/fast_map.h

Modified: cpp-commons/trunk/src/commons/fast_map.h
===================================================================
--- cpp-commons/trunk/src/commons/fast_map.h	2009-03-06 07:24:20 UTC (rev 1260)
+++ cpp-commons/trunk/src/commons/fast_map.h	2009-03-06 07:27:49 UTC (rev 1261)
@@ -11,11 +11,20 @@
   using namespace std;
   using namespace __gnu_cxx;
 
-  // TODO template <typename K, typename V>
   /**
    * Quadratic internal probing with triangular numbers, a la
-   * google::dense_hash_map.
+   * google::dense_hash_map.  Took the overall design from
+   * google::dense_hash_map, and also a few speed-up techniques from peeking at
+   * their source.
+   *
+   * This was originally written for ydb, where the map was the bottleneck in
+   * the application, but more importantly, the interface required the ability
+   * to serialize the map, and partially.  The internals have to be exposed in
+   * order for fast serialization (i.e. memcpy) to be possible; also, the
+   * ability to serialize just a certain range of the fast_map is also
+   * important.
    */
+  // TODO someday: template <typename K, typename V>
   class fast_map
   {
     private:
@@ -35,8 +44,6 @@
         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;
@@ -95,31 +102,6 @@
           table[pos].first = k;
         }
         return table[pos].second;
-#if 0
-        for (probe = 0; ; ++probe) {
-          assert(probe < 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) grow();
-
-            // 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(i < table.size());
-        assert(table[pos].first == k);
-        return table[pos].second;
-#endif
       }
   };
 


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1260] sandbox/trunk/src/cc

[<yan...@us...>]

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.

[Assorted-commits] SF.net SVN: assorted:[1259] container-bench/trunk/src

[<yan...@us...>]

Revision: 1259
          http://assorted.svn.sourceforge.net/assorted/?rev=1259&view=rev
Author:   yangzhang
Date:     2009-03-06 07:22:58 +0000 (Fri, 06 Mar 2009)

Log Message:
-----------
reorganized; added fast_map

Modified Paths:
--------------
    container-bench/trunk/src/Makefile
    container-bench/trunk/src/bench.cc

Modified: container-bench/trunk/src/Makefile
===================================================================
--- container-bench/trunk/src/Makefile	2009-03-06 07:22:51 UTC (rev 1258)
+++ container-bench/trunk/src/Makefile	2009-03-06 07:22:58 UTC (rev 1259)
@@ -1,4 +1,5 @@
-CXXFLAGS += -O3 -Wall
+CXXFLAGS += -O3 -Wall -DNDEBUG
+#CXXFLAGS += -g3 -Wall
 BINS := bench
 
 all: $(BINS)

Modified: container-bench/trunk/src/bench.cc
===================================================================
--- container-bench/trunk/src/bench.cc	2009-03-06 07:22:51 UTC (rev 1258)
+++ container-bench/trunk/src/bench.cc	2009-03-06 07:22:58 UTC (rev 1259)
@@ -1,30 +1,38 @@
 #include <map>
 #include <iostream>
-#include <vector>
+#include <vector> // TODO
+#include <commons/fast_map.h>
 #include <commons/rand.h>
 #include <commons/time.h>
 #include <stx/btree_map.h>
 #include <boost/foreach.hpp>
 #include <tr1/unordered_map>
+#include <google/dense_hash_map>
 #define foreach BOOST_FOREACH
 using namespace std;
 using namespace commons;
 using namespace stx;
 using namespace tr1;
+using namespace google;
 
-enum { len = 1000000 };
+enum { len = 20000000 };
 int *xs;
 
 template<typename T>
 inline void
 load(T &m, const string &label)
 {
+  size_t slen = len / 10;
+  size_t i, j;
   long long start = current_time_millis();
-  for (int i = 0; i < len; i++) {
-    m[i] = xs[i];
+  for (j = 0; j < 10; ++j) {
+    for (i = 0; i < slen; ++i)
+      m[i] = xs[i];
+    if (current_time_millis() > start + 1000)
+      break;
   }
-  long long end = current_time_millis();
-  cout << label << ": " << end - start << " ms" << endl;
+  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>
@@ -36,22 +44,29 @@
   foreach (pii p, m) {
     xs[p.first] = p.second;
   }
-  long long end = current_time_millis();
-  cout << label << ": " << end - start << " ms" << endl;
+  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)
+index(T &m, const string &label, size_t len)
 {
   long long start = current_time_millis();
-  for (int i = 0; i < len; i++) {
+  for (size_t i = 0; i < len; i++) {
     xs[i] = m[i];
   }
-  long long end = current_time_millis();
-  cout << label << ": " << end - start << " ms" << endl;
+  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 argc, char **argv) {
   int mode = atoi(argv[1]);
   int nreps = 2;
@@ -88,8 +103,27 @@
       int *m = new int[len];
       load(m, "arr init");
       load(m, "arr reload");
-      index(m, "arr index");
+      index(m, "arr index", len);
     }
+    if (mode & 0x10) {
+      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");
+    }
+    if (mode & 0x20) {
+      fast_map m;
+      m.set_empty_key(-1);
+      m.set_deleted_key(-2);
+      load(m, "fmap init");
+      load(m, "fmap reload");
+      //iter(m, "fmap iter");
+      index(m, "fmap index");
+    }
+    cout << endl;
   }
   return 0;
 }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1258] cpp-commons/trunk/src/commons/fast_map.h

[<yan...@us...>]

Revision: 1258
          http://assorted.svn.sourceforge.net/assorted/?rev=1258&view=rev
Author:   yangzhang
Date:     2009-03-06 07:22:51 +0000 (Fri, 06 Mar 2009)

Log Message:
-----------
added fast_map

Added Paths:
-----------
    cpp-commons/trunk/src/commons/fast_map.h

Added: cpp-commons/trunk/src/commons/fast_map.h
===================================================================
--- cpp-commons/trunk/src/commons/fast_map.h	                        (rev 0)
+++ cpp-commons/trunk/src/commons/fast_map.h	2009-03-06 07:22:51 UTC (rev 1258)
@@ -0,0 +1,128 @@
+#ifndef COMMONS_DENSE_HASH_MAP_H
+#define COMMONS_DENSE_HASH_MAP_H
+
+#include <backward/hash_fun.h>
+#include <cassert>
+#include <commons/array.h>
+#include <utility>
+
+namespace commons {
+
+  using namespace std;
+  using namespace __gnu_cxx;
+
+  // TODO template <typename K, typename V>
+  /**
+   * Quadratic internal probing with triangular numbers, a la
+   * google::dense_hash_map.
+   */
+  class fast_map
+  {
+    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);
+        // TODO faster?
+        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_map() : 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 mask = table.size() - 1;
+        size_t probe, 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;
+             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
+        for (probe = 0; ; ++probe) {
+          assert(probe < 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) grow();
+
+            // 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(i < table.size());
+        assert(table[pos].first == k);
+        return table[pos].second;
+#endif
+      }
+  };
+
+}
+
+#endif


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1257] cpp-commons/trunk/src/commons/array.h

[<yan...@us...>]

Revision: 1257
          http://assorted.svn.sourceforge.net/assorted/?rev=1257&view=rev
Author:   yangzhang
Date:     2009-03-06 07:22:46 +0000 (Fri, 06 Mar 2009)

Log Message:
-----------
added proper operator[] for array

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/array.h

Modified: cpp-commons/trunk/src/commons/array.h
===================================================================
--- cpp-commons/trunk/src/commons/array.h	2009-03-06 02:32:19 UTC (rev 1256)
+++ cpp-commons/trunk/src/commons/array.h	2009-03-06 07:22:46 UTC (rev 1257)
@@ -31,7 +31,8 @@
         size_t size() const { return n_; }
         T *get() const { return p_; }
         T *end() const { return p_ + n_; }
-        T operator[](size_t i) const { return p_[i]; }
+        const T &operator[](size_t i) const { return p_[i]; }
+        T &operator[](size_t i) { return p_[i]; }
         void reset(T *p, size_t n) { p_ = p; n_ = n; }
       private:
         T *p_;
@@ -53,7 +54,8 @@
         T *get() const { return p_.get(); }
         T *release() { return p_.release(); }
         T *end() const { return this->get() + n_; }
-        T operator[](size_t i) const { return p_[i]; }
+        const T &operator[](size_t i) const { return p_[i]; }
+        T &operator[](size_t i) { return p_[i]; }
         void reset(T *p, size_t n) { p_.reset(p); n_ = n; }
       private:
         unique_ptr<T[]> p_;
@@ -67,7 +69,7 @@
   void
   swap(array<T> &a, array<T> &b)
   {
-    std::swap(a.p_, b.p_);
+    boost::swap(a.p_, b.p_);
     swap(a.n_, b.n_);
   }
 


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1256] ydb/trunk/src

[<yan...@us...>]

Revision: 1256
          http://assorted.svn.sourceforge.net/assorted/?rev=1256&view=rev
Author:   yangzhang
Date:     2009-03-06 02:32:19 +0000 (Fri, 06 Mar 2009)

Log Message:
-----------
pb_types -> pb_traits, rb_types -> rb_traits

Modified Paths:
--------------
    ydb/trunk/src/main.lzz.clamp
    ydb/trunk/src/ser.cc
    ydb/trunk/src/ser.h

Modified: ydb/trunk/src/main.lzz.clamp
===================================================================
--- ydb/trunk/src/main.lzz.clamp	2009-03-05 23:16:46 UTC (rev 1255)
+++ ydb/trunk/src/main.lzz.clamp	2009-03-06 02:32:19 UTC (rev 1256)
@@ -652,7 +652,7 @@
         --seqno;
         r.reset_range(txn_start, w.cur());
         if (!Types::is_pb()) txn.Clear();
-        process_txn<Types, pb_types>(g_map, txn, seqno, nullptr);
+        process_txn<Types, pb_traits>(g_map, txn, seqno, nullptr);
       }
 
       // Checkpoint.
@@ -1571,7 +1571,7 @@
           batch.Clear();
           for (int t = 0; t < batch.txn_size(); ++t) {
             const Txn &txn = batch.txn(t);
-            process_txn<rb_types, rb_types>(map, txn, seqno, nullptr);
+            process_txn<rb_traits, rb_traits>(map, txn, seqno, nullptr);
             if (fake_exec && !Types::is_pb()) {
               reader.skip(txn.op_size() * Op_Size);
             }
@@ -1592,7 +1592,7 @@
       while (!backlog.empty()) {
         using pb::Txn;
         shared_ptr<Txn> p = backlog.take();
-        process_txn<pb_types, pb_types>(map, *p, seqno, nullptr);
+        process_txn<pb_traits, pb_traits>(map, *p, seqno, nullptr);
         if (check_interval(p->seqno(), catch_up_display)) {
           cout << "processed txn " << p->seqno() << " off the backlog; "
                << "backlog.size = " << backlog.queue().size() << endl;
@@ -1885,29 +1885,29 @@
     if (is_leader) {
       if (use_pb) {
         if (use_pb_res) {
-          run_leader<pb_types, pb_types>(minreps, leader_port);
+          run_leader<pb_traits, pb_traits>(minreps, leader_port);
         } else {
-          run_leader<pb_types, rb_types>(minreps, leader_port);
+          run_leader<pb_traits, rb_traits>(minreps, leader_port);
         }
       } else {
         if (use_pb_res) {
-          run_leader<rb_types, pb_types>(minreps, leader_port);
+          run_leader<rb_traits, pb_traits>(minreps, leader_port);
         } else {
-          run_leader<rb_types, rb_types>(minreps, leader_port);
+          run_leader<rb_traits, rb_traits>(minreps, leader_port);
         }
       }
     } else {
       if (use_pb) {
         if (use_pb_res) {
-          run_replica<pb_types, pb_types>(leader_host, leader_port, listen_port);
+          run_replica<pb_traits, pb_traits>(leader_host, leader_port, listen_port);
         } else {
-          run_replica<pb_types, rb_types>(leader_host, leader_port, listen_port);
+          run_replica<pb_traits, rb_traits>(leader_host, leader_port, listen_port);
         }
       } else {
         if (use_pb_res) {
-          run_replica<rb_types, pb_types>(leader_host, leader_port, listen_port);
+          run_replica<rb_traits, pb_traits>(leader_host, leader_port, listen_port);
         } else {
-          run_replica<rb_types, rb_types>(leader_host, leader_port, listen_port);
+          run_replica<rb_traits, rb_traits>(leader_host, leader_port, listen_port);
         }
       }
     }

Modified: ydb/trunk/src/ser.cc
===================================================================
--- ydb/trunk/src/ser.cc	2009-03-05 23:16:46 UTC (rev 1255)
+++ ydb/trunk/src/ser.cc	2009-03-06 02:32:19 UTC (rev 1256)
@@ -138,15 +138,15 @@
     st_netfd_t dst = checkerr(st_accept(listener, nullptr, nullptr,
                                         ST_UTIME_NO_TIMEOUT));
     if (use_pb)
-      producer<pb_types>(dst);
+      producer<pb_traits>(dst);
     else
-      producer<rb_types>(dst);
+      producer<rb_traits>(dst);
   } else {
     st_netfd_t src = st_tcp_connect(argv[use_pb ? 2 : 1], 7654, ST_UTIME_NO_TIMEOUT);
     if (use_pb)
-      consumer<pb_types>(src);
+      consumer<pb_traits>(src);
     else
-      consumer<rb_types>(src);
+      consumer<rb_traits>(src);
   }
   return 0;
 }

Modified: ydb/trunk/src/ser.h
===================================================================
--- ydb/trunk/src/ser.h	2009-03-05 23:16:46 UTC (rev 1255)
+++ ydb/trunk/src/ser.h	2009-03-06 02:32:19 UTC (rev 1256)
@@ -43,7 +43,7 @@
     int ByteSize() const { throw_operation_not_supported(); } \
 
 #define MAKE_TYPE_BATCH(name, ns, b) \
-  struct name##_types { \
+  struct name##_traits { \
     typedef ydb::ns::TxnBatch TxnBatch; \
     typedef ydb::ns::Txn Txn; \
     typedef ydb::ns::Op Op; \


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1255] ydb/trunk/src/main.lzz.clamp

[<yan...@us...>]

Revision: 1255
          http://assorted.svn.sourceforge.net/assorted/?rev=1255&view=rev
Author:   yangzhang
Date:     2009-03-05 23:16:46 +0000 (Thu, 05 Mar 2009)

Log Message:
-----------
added fast rb backlogging/catch-up

Modified Paths:
--------------
    ydb/trunk/src/main.lzz.clamp

Modified: ydb/trunk/src/main.lzz.clamp
===================================================================
--- ydb/trunk/src/main.lzz.clamp	2009-03-05 23:15:25 UTC (rev 1254)
+++ ydb/trunk/src/main.lzz.clamp	2009-03-05 23:16:46 UTC (rev 1255)
@@ -7,6 +7,7 @@
 #include <boost/range/iterator_range.hpp>
 #include <boost/scoped_array.hpp>
 #include <boost/shared_ptr.hpp>
+#include <boost/tuple/tuple.hpp>
 #include <commons/nullptr.h>
 #include <commons/rand.h>
 #include <commons/st/st.h>
@@ -27,13 +28,15 @@
 #include <tr1/unordered_map>
 #include <unistd.h> // pipe, write
 #include <vector>
+#include "ser.h"
 #include "ydb.pb.h"
-#include "ser.h"
 
 #define function boost::function
 #define foreach BOOST_FOREACH
 #define shared_ptr boost::shared_ptr
 #define ref boost::ref
+#define tuple boost::tuple
+#define make_tuple boost::make_tuple
 
 using namespace boost;
 using namespace boost::archive;
@@ -53,6 +56,8 @@
 typedef pair<int, int> pii;
 typedef map_t<int, int> mii;
 
+typedef tuple<sized_array<char>, char*, char*> chunk;
+
 template<typename T> void init_map(T &map) {}
 template<> void init_map(dense_hash_map<int, int> &map) {
   map.set_empty_key(-1);
@@ -69,7 +74,7 @@
 bool yield_during_build_up, yield_during_catch_up, dump, show_updates,
      count_updates, stop_on_recovery, general_txns, profile_threads,
      debug_threads, multirecover, disk, debug_memory, use_pwal, use_twal,
-     use_pb, use_pb_res,
+     use_pb, use_pb_res, g_caught_up,
      suppress_txn_msgs, fake_bcast, force_ser, fake_exec;
 long long timelim, read_thresh, write_thresh;
 
@@ -862,7 +867,8 @@
 void
 process_txns(st_netfd_t leader, mii &map, int &seqno,
              st_channel<shared_ptr<Recovery> > &send_states,
-             st_channel<shared_ptr<pb::Txn> > &backlog, int init_seqno,
+             /* XXX st_channel<shared_ptr<pb::Txn> > &backlog */
+             st_channel<chunk> &backlog, int init_seqno,
              int mypos, int nnodes)
 {
   typedef typename Types::TxnBatch TxnBatch;
@@ -880,7 +886,8 @@
   // issued more since the Init message).
   int first_seqno = -1;
 
-  commons::array<char> rbuf(read_buf_size), wbuf(buf_size);
+  sized_array<char> rbuf(new char[read_buf_size], read_buf_size);
+  commons::array<char> wbuf(buf_size);
   st_reader reader(leader, rbuf.get(), rbuf.size());
   vector<st_netfd_t> leader_v(1, leader);
   writer w(lambda(const void *buf, size_t len) {
@@ -910,85 +917,125 @@
     scoped_ptr<ResponseBatch> presbatch(new_ResponseBatch<ResponseBatch>(s));
     ResponseBatch &resbatch = *presbatch;
     ser_t serbuf;
+    char *first_start = reader.start();
+    assert(first_start == rbuf.get());
+    const size_t headerlen = sizeof(uint32_t) + sizeof(short) + sizeof(int);
     while (true) {
       uint32_t prefix = 0;
-      long long before_read = -1;
-      if (read_thresh > 0) {
-        before_read = current_time_millis();
+      char *start = reader.start();
+
+      // Will overflow on next few reads ("header")?
+      if (reader.unread() + reader.rem() < headerlen) {
+        sized_array<char> buf(new char[read_buf_size], read_buf_size);
+        memcpy(buf.get(), reader.start(), reader.unread());
+        swap(buf, reader.buf());
+        reader.reset_range(reader.buf().get(), reader.buf().get() + reader.unread());
+        backlog.push(make_tuple(buf, first_start, start));
+        first_start = reader.start();
       }
-      {
+
+      if (Types::is_pb()) {
+        long long before_read = -1;
+        if (read_thresh > 0) {
+          before_read = current_time_millis();
+        }
+        {
+          st_intr intr(stop_hub);
+          readmsg(reader, batch);
+        }
+        if (read_thresh > 0) {
+          long long read_time = current_time_millis() - before_read;
+          if (read_time > read_thresh) {
+            cout << "thread " << threadname()
+                 << ": read took " << read_time << " ms" << endl;
+          }
+        }
+      } else {
         st_intr intr(stop_hub);
-        if (Types::is_pb()) readmsg(reader, batch);
-        else { prefix = reader.read<uint32_t>(); batch.Clear(); }
+        prefix = reader.read<uint32_t>();
+        check(prefix < 10000);
+        batch.Clear();
       }
-      if (read_thresh > 0) {
-        long long read_time = current_time_millis() - before_read;
-        if (read_time > read_thresh) {
-          cout << "thread " << threadname()
-               << ": read took " << read_time << " ms" << endl;
-        }
-      }
+
       if (batch.txn_size() > 0) {
-        w.mark();
-        resbatch.Clear();
-        start_res(resbatch);
-        // XXX
-        //char *start = reader.start();
-        //const Txn &first_txn = batch.txn(0);
-        //if (txn.seqno() < 0) {
-        //} else if (txn.seqno() == seqno + 1) {
-        //} else {
-        //  // Skip entire message.
-        //  reader.
-        //}
-        for (int t = 0; t < batch.txn_size(); ++t) {
-          // XXX const Txn &txn = t == 0 ? first_txn : batch.txn(t);
-          const Txn &txn = batch.txn(t);
-          // Regular transaction.
-          const char *action;
-          if (txn.seqno() < 0) {
-            throw break_exception();
-          } else if (txn.seqno() == seqno + 1) {
-            if (!caught_up) {
-              time_caught_up = current_time_millis();
-              seqno_caught_up = seqno;
-              showtput("process_txns caught up; backlogged",
-                       time_caught_up, start_time, seqno_caught_up,
-                       first_seqno == -1 ? init_seqno - 1 : first_seqno);
-              caught_up = true;
-            }
+        const Txn &first_txn = batch.txn(0);
+        if (first_txn.seqno() < 0) {
+          break;
+        } else if (first_txn.seqno() > seqno + 1) {
+          // In backlogging mode?
+
+          // Skip entire message, pushing it to the thread that's handling
+          // recovery for later processing once snapshot is received.
+          // TODO: implement and use anchors instead?
+          if (first_seqno == -1)
+            cout << "first seqno: " << (first_seqno = first_txn.seqno()) << endl;
+
+          // Caught up?
+          if (first_seqno == seqno + 1) {
+            // Rewind so we process accumulated messages.
+            reader.reset_range(first_start, reader.end());
+            continue;
+          }
+
+          // About to overflow?
+          if (reader.unread() + reader.rem() < prefix + sizeof(uint32_t) - headerlen) {
+            // Move current partial message to new buffer.
+            sized_array<char> tmp(new char[read_buf_size], read_buf_size);
+            *reinterpret_cast<uint32_t*>(tmp.get()) = prefix;
+            *reinterpret_cast<short*>(tmp.get() + sizeof(uint32_t)) = short(batch.txn_size());
+            *reinterpret_cast<int*>(tmp.get() + sizeof(uint32_t) + sizeof(short)) = first_txn.seqno();
+            memcpy(tmp.get() + headerlen, reader.start(), reader.unread());
+
+            // Swap the buffers.
+            swap(tmp, reader.buf());
+            reader.reset_range(reader.buf().get() + headerlen, reader.buf().get() + headerlen + reader.unread());
+            assert(tmp.get() <= first_start && first_start < tmp.end());
+            assert(tmp.get() < start && start < tmp.end());
+            assert(first_start < start);
+            backlog.push(make_tuple(tmp, first_start, start));
+            first_start = reader.buf().get();
+            first_seqno = first_txn.seqno();
+          }
+
+          // Fill up rest of the message
+          assert(reader.unread() + reader.rem() >= prefix + sizeof(uint32_t) - headerlen);
+          check0x(reader.accum(prefix + sizeof(uint32_t) - headerlen));
+        } else {
+          // Regular transaction batch.
+          if (!caught_up) {
+            time_caught_up = current_time_millis();
+            seqno_caught_up = seqno;
+            showtput("process_txns caught up; backlogged",
+                     time_caught_up, start_time, seqno_caught_up,
+                     first_seqno == -1 ? init_seqno - 1 : first_seqno);
+            caught_up = true;
+          }
+          w.mark();
+          resbatch.Clear();
+          start_res(resbatch);
+          for (int t = 0; t < batch.txn_size(); ++t) {
+            const Txn &txn = t == 0 ? first_txn : batch.txn(t);
             Response *res = resbatch.add_res();
             process_txn<Types, RTypes>(map, txn, seqno, res);
             if (fake_exec && !Types::is_pb()) {
               reader.skip(txn.op_size() * Op_Size);
             }
-            action = "processed";
-          } else {
-            if (first_seqno == -1)
-              first_seqno = txn.seqno();
-            // Queue up entire buffer for later processing once a snapshot has
-            // been received.
-            // XXX backlog.push(array());
-            // Stop the loop.
-            // XXX t = batch.txn_size();
-            backlog.push(to_pb_Txn(txn));
-            action = "backlogged";
-          }
 
-          if (check_interval(txn.seqno(), yield_interval)) st_sleep(0);
-          if (check_interval(txn.seqno(), process_display)) {
-            cout << action << " txn " << txn.seqno()
-              << "; db size = " << map.size()
-              << "; seqno = " << seqno
-              << "; backlog.size = " << backlog.queue().size() << endl;
+            if (check_interval(txn.seqno(), yield_interval)) st_sleep(0);
+            if (check_interval(txn.seqno(), process_display)) {
+              cout << "processed txn " << txn.seqno()
+                << "; db size = " << map.size()
+                << "; seqno = " << seqno
+                << "; backlog.size = " << backlog.queue().size() << endl;
+            }
           }
+          fin_res(resbatch);
+          if (RTypes::is_pb() && resbatch.res_size() > 0) {
+            serbuf.clear();
+            ser(serbuf, resbatch);
+            sendbuf(leader, serbuf);
+          }
         }
-        fin_res(resbatch);
-        if (RTypes::is_pb() && resbatch.res_size() > 0) {
-          serbuf.clear();
-          ser(serbuf, resbatch);
-          sendbuf(leader, serbuf);
-        }
       } else if (multirecover || mypos == 0) {
         // Empty (default) TxnBatch means "generate a snapshot."
         // TODO make this faster
@@ -1439,7 +1486,8 @@
   }
 
   // Process txns.
-  st_channel<shared_ptr<pb::Txn> > backlog;
+  // XXX st_channel<shared_ptr<pb::Txn> > backlog;
+  st_channel<chunk> backlog;
   const function<void()> process_fn =
     bind(process_txns<Types, RTypes>, leader, ref(map), ref(seqno),
          ref(send_states), ref(backlog), init.txnseqno(), mypos,
@@ -1497,7 +1545,51 @@
       long long mid_time = current_time_millis();
 
       int mid_seqno = seqno;
+      // XXX
+      using msg::TxnBatch;
+      using msg::Txn;
+      commons::array<char> rbuf(0), wbuf(buf_size);
+      reader reader(nullptr, rbuf.get(), rbuf.size());
+      writer writer(lambda(const void*, size_t) {
+       throw operation_not_supported("should not be writing responses during catch-up phase");
+      }, wbuf.get(), wbuf.size());
+      stream s(reader, writer);
+      TxnBatch batch(s);
       while (!backlog.empty()) {
+        chunk chunk = backlog.take();
+        sized_array<char> &buf = chunk.get<0>();
+        assert(buf.get() <= chunk.get<1>() && chunk.get<1>() < buf.end());
+        assert(buf.get() < chunk.get<2>() && chunk.get<2>() < buf.end());
+        assert(chunk.get<1>() < chunk.get<2>());
+        swap(buf, reader.buf());
+        reader.reset_range(chunk.get<1>(), chunk.get<2>());
+        while (reader.start() < reader.end()) {
+          char *start = reader.start();
+          uint32_t prefix = reader.read<uint32_t>();
+          assert(prefix < 10000);
+          assert(start + sizeof(uint32_t) + prefix <= reader.end());
+          batch.Clear();
+          for (int t = 0; t < batch.txn_size(); ++t) {
+            const Txn &txn = batch.txn(t);
+            process_txn<rb_types, rb_types>(map, txn, seqno, nullptr);
+            if (fake_exec && !Types::is_pb()) {
+              reader.skip(txn.op_size() * Op_Size);
+            }
+
+            if (check_interval(txn.seqno(), yield_interval)) st_sleep(0);
+            if (check_interval(txn.seqno(), process_display)) {
+              cout << "caught up txn " << txn.seqno()
+                << "; db size = " << map.size()
+                << "; seqno = " << seqno
+                << "; backlog.size = " << backlog.queue().size() << endl;
+            }
+          }
+          assert(start + sizeof(uint32_t) + prefix == reader.start());
+        }
+      }
+      g_caught_up = true;
+#if 0
+      while (!backlog.empty()) {
         using pb::Txn;
         shared_ptr<Txn> p = backlog.take();
         process_txn<pb_types, pb_types>(map, *p, seqno, nullptr);
@@ -1511,6 +1603,7 @@
           st_sleep(0);
         }
       }
+#endif
       showtput("replayer caught up; from backlog replayed",
                current_time_millis(), mid_time, seqno, mid_seqno);
     }
@@ -1786,6 +1879,8 @@
     // Initialize the map.
     init_map(g_map);
 
+    cout << "pid " << getpid() << endl;
+
     // Which role are we?
     if (is_leader) {
       if (use_pb) {


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1254] cpp-commons/trunk/src/commons/array.h

[<yan...@us...>]

Revision: 1254
          http://assorted.svn.sourceforge.net/assorted/?rev=1254&view=rev
Author:   yangzhang
Date:     2009-03-05 23:15:25 +0000 (Thu, 05 Mar 2009)

Log Message:
-----------
- fixed swap

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/array.h

Modified: cpp-commons/trunk/src/commons/array.h
===================================================================
--- cpp-commons/trunk/src/commons/array.h	2009-03-05 23:15:15 UTC (rev 1253)
+++ cpp-commons/trunk/src/commons/array.h	2009-03-05 23:15:25 UTC (rev 1254)
@@ -1,6 +1,7 @@
 #ifndef COMMONS_ARRAY_H
 #define COMMONS_ARRAY_H
 
+#include <algorithm>
 #include <boost/unique_ptr.hpp>
 #include <commons/algo.h>
 #include <commons/check.h>
@@ -10,6 +11,7 @@
 namespace commons {
 
   using namespace boost;
+  using namespace std;
 
   template<typename T> class array;
   template<typename T> class sized_array;
@@ -65,7 +67,7 @@
   void
   swap(array<T> &a, array<T> &b)
   {
-    swap(a.p_, b.p_);
+    std::swap(a.p_, b.p_);
     swap(a.n_, b.n_);
   }
 
@@ -77,7 +79,7 @@
   void
   swap(sized_array<T> &a, sized_array<T> &b)
   {
-    swap(a.p_, b.p_);
+    std::swap(a.p_, b.p_);
     swap(a.n_, b.n_);
   }
 


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.

[Assorted-commits] SF.net SVN: assorted:[1253] cpp-commons/trunk/src/commons/st/st.h

[<yan...@us...>]

Revision: 1253
          http://assorted.svn.sourceforge.net/assorted/?rev=1253&view=rev
Author:   yangzhang
Date:     2009-03-05 23:15:15 +0000 (Thu, 05 Mar 2009)

Log Message:
-----------
- added rem, unread, reset to st_reader

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/st/st.h

Modified: cpp-commons/trunk/src/commons/st/st.h
===================================================================
--- cpp-commons/trunk/src/commons/st/st.h	2009-03-05 23:14:45 UTC (rev 1252)
+++ cpp-commons/trunk/src/commons/st/st.h	2009-03-05 23:15:15 UTC (rev 1253)
@@ -407,8 +407,11 @@
   public:
     st_reader(st_netfd_t fd, char *buf, size_t len) :
       r_(st_read_fn(fd), st_read_fully_fn(fd), buf, len) {}
+    size_t unread() { return r_.unread(); }
+    size_t rem() { return r_.rem(); }
     sized_array<char> &buf() { return r_.buf(); }
     void reset_range(char *start, char *end) { r_.reset_range(start, end); }
+    void reset() { r_.reset(); }
     char *start() { return r_.start(); }
     char *end() { return r_.end(); }
     bool accum(size_t req) { return r_.accum(req); }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.