Added qpid::InlineVector - std::vector with inline storage to avoid

heap allocation for small vectors.

Made SequenceNumberSet : public InlineVector<SequenceNumber, 2>

In 100k perftest reduces heap allocation in client by  40%, broker 9%.
.


git-svn-id: https://svn.apache.org/repos/asf/incubator/qpid/trunk@595808 13f79535-47bb-0310-9956-ffa450edef68

10 files changed, 246 insertions, 13 deletions

diff --git a/qpid/cpp/src/qpid/InlineAllocator.h b/qpid/cpp/src/qpid/InlineAllocator.h
new file mode 100644
index 0000000000..06f79c95e3
--- /dev/null
+++ b/qpid/cpp/src/qpid/InlineAllocator.h
@@ -0,0 +1,74 @@
+#ifndef QPID_INLINEALLOCATOR_H
+#define QPID_INLINEALLOCATOR_H
+
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ * 
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include <memory>
+
+namespace qpid {
+
+/**
+ * An allocator that has inline storage for up to Max objects
+ * of type BaseAllocator::value_type.
+ * Store small requests inline, uses BaseAllocator::allocate otherwise.
+ */
+template <class BaseAllocator, size_t Max> 
+class InlineAllocator : public BaseAllocator {
+  public:
+    typedef typename BaseAllocator::pointer pointer;
+    typedef typename BaseAllocator::size_type size_type;
+    typedef typename BaseAllocator::value_type value_type;
+
+    InlineAllocator() : allocated(false) {}
+    
+    pointer allocate(size_type n) {
+        if (n <= Max && !allocated) {
+            allocated=true;
+            return data();
+        }
+        else 
+            return BaseAllocator::allocate(n, 0);
+    }
+
+    void deallocate(pointer p, size_type n) {
+        if (p == data()) allocated=false;
+        else BaseAllocator::deallocate(p, n);
+    }
+
+    template<typename T1>
+    struct rebind {
+        typedef typename BaseAllocator::template rebind<T1>::other BaseOther;
+        typedef InlineAllocator<BaseOther, Max> other;
+    };
+
+  private:
+    value_type* data() {
+        return reinterpret_cast<value_type*>(store);
+    }
+
+    char store[Max * sizeof(value_type)];
+    bool allocated;
+};
+
+} // namespace qpid
+
+#endif  /*!QPID_INLINEALLOCATOR_H*/
diff --git a/qpid/cpp/src/qpid/InlineVector.h b/qpid/cpp/src/qpid/InlineVector.h
new file mode 100644
index 0000000000..551b9912e7
--- /dev/null
+++ b/qpid/cpp/src/qpid/InlineVector.h
@@ -0,0 +1,68 @@
+#ifndef QPID_INLINEVECTOR_H
+#define QPID_INLINEVECTOR_H
+
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ * 
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "InlineAllocator.h"
+#include <vector>
+
+namespace qpid {
+
+/**
+ * A vector that stores up to Max elements in inline storage,
+ * otherwise uses normal vector allocation.
+ *
+ * NOTE: depends on some non-standard but highly probably assumptions
+ * about how std::vector uses its allocator, they are true for g++.
+ *  - default constructor does not allocate.
+ *  - reserve(N) does not allocate more than N elements.
+ *  - vector never re-allocates when size() < capacity()
+ */
+template <class T, size_t Max, class Alloc=std::allocator<T> >
+class InlineVector : public std::vector<T, InlineAllocator<Alloc, Max> >
+{
+    typedef std::vector<T, InlineAllocator<Alloc, Max> > Base;
+  public:
+    typedef typename Base::allocator_type allocator_type;
+    typedef typename Base::value_type value_type;
+    typedef typename Base::size_type size_type;
+    
+    explicit InlineVector(const allocator_type& a=allocator_type()) : Base(a) {
+        this->reserve(Max);
+    }
+
+    explicit InlineVector(size_type n, const value_type& x = value_type(),
+                          const allocator_type& a=allocator_type()) : Base(a)
+    {
+        this->reserve(std::max(n, Max));
+        this->insert(this->end(), n, x);
+    }
+
+    InlineVector(const InlineVector& x) : Base() {
+        this->reserve(std::max(x.size(), Max));
+        *this = x;
+    }
+};
+
+} // namespace qpid
+
+#endif  /*!QPID_INLINEVECTOR_H*/
diff --git a/qpid/cpp/src/qpid/broker/DeliveryId.h b/qpid/cpp/src/qpid/broker/DeliveryId.h
index 6cec05ed2c..05b19f032e 100644
--- a/qpid/cpp/src/qpid/broker/DeliveryId.h
+++ b/qpid/cpp/src/qpid/broker/DeliveryId.h
@@ -22,12 +22,13 @@
 #define _DeliveryId_
 
 #include "qpid/framing/SequenceNumber.h"
+#include "qpid/framing/SequenceNumberSet.h"
 
 namespace qpid {
 namespace broker {
 
     typedef framing::SequenceNumber DeliveryId;
-
+    typedef framing::SequenceNumberSet DeliveryIds;
 }}
 
 
diff --git a/qpid/cpp/src/qpid/broker/DeliveryRecord.cpp b/qpid/cpp/src/qpid/broker/DeliveryRecord.cpp
index f20aff1f23..2e7c126162 100644
--- a/qpid/cpp/src/qpid/broker/DeliveryRecord.cpp
+++ b/qpid/cpp/src/qpid/broker/DeliveryRecord.cpp
@@ -148,7 +148,7 @@ void DeliveryRecord::subtractFrom(Prefetch& prefetch) const{
     }
 }
 
-void DeliveryRecord::acquire(std::vector<DeliveryId>& results) {
+void DeliveryRecord::acquire(DeliveryIds& results) {
     if (queue->acquire(msg)) {
         acquired = true;
         results.push_back(id);
diff --git a/qpid/cpp/src/qpid/broker/DeliveryRecord.h b/qpid/cpp/src/qpid/broker/DeliveryRecord.h
index d2a9e38a7c..eeb363bcfc 100644
--- a/qpid/cpp/src/qpid/broker/DeliveryRecord.h
+++ b/qpid/cpp/src/qpid/broker/DeliveryRecord.h
@@ -72,7 +72,7 @@ class DeliveryRecord{
     const std::string& getTag() const { return tag; } 
     bool isPull() const { return pull; }
     bool isAcquired() const { return acquired; }
-    void acquire(std::vector<DeliveryId>& results);
+    void acquire(DeliveryIds& results);
     friend bool operator<(const DeliveryRecord&, const DeliveryRecord&);         
     friend std::ostream& operator<<(std::ostream&, const DeliveryRecord&);
 };
@@ -89,9 +89,9 @@ struct AckRange
 
 struct AcquireFunctor
 {
-    std::vector<DeliveryId>& results;
+    DeliveryIds& results;
 
-    AcquireFunctor(std::vector<DeliveryId>& _results) : results(_results) {}
+    AcquireFunctor(DeliveryIds& _results) : results(_results) {}
 
     void operator()(DeliveryRecord& record)
     {
diff --git a/qpid/cpp/src/qpid/broker/SemanticState.cpp b/qpid/cpp/src/qpid/broker/SemanticState.cpp
index 270cdca731..e790e087f0 100644
--- a/qpid/cpp/src/qpid/broker/SemanticState.cpp
+++ b/qpid/cpp/src/qpid/broker/SemanticState.cpp
@@ -616,7 +616,7 @@ AckRange SemanticState::findRange(DeliveryId first, DeliveryId last)
     return AckRange(start, end);
 }
 
-void SemanticState::acquire(DeliveryId first, DeliveryId last, std::vector<DeliveryId>& acquired)
+void SemanticState::acquire(DeliveryId first, DeliveryId last, DeliveryIds& acquired)
 {
     Mutex::ScopedLock locker(deliveryLock);
     AckRange range = findRange(first, last);
diff --git a/qpid/cpp/src/qpid/broker/SemanticState.h b/qpid/cpp/src/qpid/broker/SemanticState.h
index ea58a74f45..8e039d554b 100644
--- a/qpid/cpp/src/qpid/broker/SemanticState.h
+++ b/qpid/cpp/src/qpid/broker/SemanticState.h
@@ -184,7 +184,7 @@ class SemanticState : public framing::FrameHandler::Chains,
     void recover(bool requeue);
     void flow(bool active);
     DeliveryId redeliver(QueuedMessage& msg, DeliveryToken::shared_ptr token);            
-    void acquire(DeliveryId first, DeliveryId last, std::vector<DeliveryId>& acquired);
+    void acquire(DeliveryId first, DeliveryId last, DeliveryIds& acquired);
     void release(DeliveryId first, DeliveryId last);
     void reject(DeliveryId first, DeliveryId last);
     void handle(intrusive_ptr<Message> msg);
diff --git a/qpid/cpp/src/qpid/framing/SequenceNumberSet.h b/qpid/cpp/src/qpid/framing/SequenceNumberSet.h
index 9091e7142e..666307f9d9 100644
--- a/qpid/cpp/src/qpid/framing/SequenceNumberSet.h
+++ b/qpid/cpp/src/qpid/framing/SequenceNumberSet.h
@@ -22,20 +22,21 @@
 #define _framing_SequenceNumberSet_h
 
 #include <ostream>
-#include <vector>
 #include "amqp_types.h"
 #include "Buffer.h"
 #include "SequenceNumber.h"
 #include "qpid/framing/reply_exceptions.h"
+#include "qpid/InlineVector.h"
 
 namespace qpid {
 namespace framing {
 
-class SequenceNumberSet : public std::vector<SequenceNumber>
-{   
+class SequenceNumberSet : public InlineVector<SequenceNumber, 2>
+{
+    typedef InlineVector<SequenceNumber, 2> Base;
 public:
-    typedef std::vector<SequenceNumber>::const_iterator const_iterator;
-    typedef std::vector<SequenceNumber>::iterator iterator;
+    typedef Base::const_iterator const_iterator;
+    typedef Base::iterator iterator;
 
     void encode(Buffer& buffer) const;
     void decode(Buffer& buffer);
diff --git a/qpid/cpp/src/tests/InlineVector.cpp b/qpid/cpp/src/tests/InlineVector.cpp
new file mode 100644
index 0000000000..a213f24809
--- /dev/null
+++ b/qpid/cpp/src/tests/InlineVector.cpp
@@ -0,0 +1,88 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ * 
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+
+#include "qpid/InlineVector.h"
+#include <boost/test/auto_unit_test.hpp>
+BOOST_AUTO_TEST_SUITE(InlineVector);
+
+using namespace qpid;
+using namespace std;
+
+typedef InlineVector<int, 3> Vec;
+
+bool isInline(const Vec& v) {
+    return (char*)&v <= (char*)v.data() &&
+        (char*)v.data() < (char*)&v+sizeof(v);
+}
+
+BOOST_AUTO_TEST_CASE(testCtor) {
+    {
+        Vec v;
+        BOOST_CHECK(isInline(v));
+        BOOST_CHECK(v.empty());
+    }
+    {
+        Vec v(3, 42);
+        BOOST_CHECK(isInline(v));
+        BOOST_CHECK_EQUAL(3u, v.size());
+        BOOST_CHECK_EQUAL(v[0], 42);
+        BOOST_CHECK_EQUAL(v[2], 42);
+
+        Vec u(v);
+        BOOST_CHECK(isInline(u));
+        BOOST_CHECK_EQUAL(3u, u.size());
+        BOOST_CHECK_EQUAL(u[0], 42);
+        BOOST_CHECK_EQUAL(u[2], 42);
+    }
+
+    {
+        Vec v(4, 42);
+
+        BOOST_CHECK_EQUAL(v.size(), 4u);
+        BOOST_CHECK(!isInline(v));
+        Vec u(v);
+        BOOST_CHECK_EQUAL(u.size(), 4u);
+        BOOST_CHECK(!isInline(u));
+    }
+}
+
+BOOST_AUTO_TEST_CASE(testInsert) {
+    Vec v;
+    v.push_back(1);
+    BOOST_CHECK_EQUAL(v.size(), 1u);
+    BOOST_CHECK_EQUAL(v.back(), 1);
+    BOOST_CHECK(isInline(v));
+
+    v.insert(v.begin(), 2);
+    BOOST_CHECK_EQUAL(v.size(), 2u);
+    BOOST_CHECK_EQUAL(v.back(), 1);
+    BOOST_CHECK(isInline(v));
+
+    v.push_back(3);
+    BOOST_CHECK(isInline(v));
+
+    v.push_back(4);
+    BOOST_CHECK_EQUAL(v.size(), 4u);
+    BOOST_CHECK(!isInline(v));
+}
+
+
+BOOST_AUTO_TEST_SUITE_END();
diff --git a/qpid/cpp/src/tests/Makefile.am b/qpid/cpp/src/tests/Makefile.am
index b4944c1294..4dbc37d42a 100644
--- a/qpid/cpp/src/tests/Makefile.am
+++ b/qpid/cpp/src/tests/Makefile.am
@@ -31,7 +31,8 @@ unit_test_SOURCES= unit_test.cpp \
 	RefCounted.cpp RefCountedMap.cpp \
 	SessionState.cpp Blob.cpp logging.cpp \
 	Url.cpp Uuid.cpp \
-	Shlib.cpp FieldValue.cpp FieldTable.cpp Array.cpp
+	Shlib.cpp FieldValue.cpp FieldTable.cpp Array.cpp \
+	InlineVector.cpp
 
 check_LTLIBRARIES += libshlibtest.la
 libshlibtest_la_LDFLAGS = -module -rpath $(abs_builddir)