Use a vector backed set for speed.

7 files changed, 53 insertions, 40 deletions

diff --git a/document/src/tests/fieldsettest.cpp b/document/src/tests/fieldsettest.cpp
index c94523ea23f..8a01c53c278 100644
--- a/document/src/tests/fieldsettest.cpp
+++ b/document/src/tests/fieldsettest.cpp
@@ -274,14 +274,10 @@ TEST(FieldCollectionTest, testHash ) {
     TestDocMan testDocMan;
     const DocumentTypeRepo& repo = testDocMan.getTypeRepo();
     const DocumentType & type = *repo.getDocumentType("testdoctype1");
-    Field::Set set;
-    EXPECT_EQ(0ul, FieldCollection(type, set).hash());
-    set.insert(&type.getField("headerval"));
-    EXPECT_EQ(0x548599858c77ef83ul, FieldCollection(type, set).hash());
-    set.insert(&type.getField("hstringval"));
-    EXPECT_EQ(0x4a7ff2406d36a9b0ul, FieldCollection(type, set).hash());
-    set.erase(&type.getField("headerval"));
-    EXPECT_EQ(0x1e0918531b19734ul, FieldCollection(type, set).hash());
+    EXPECT_EQ(0ul, FieldCollection(type, Field::Set::Builder().build()).hash());
+    EXPECT_EQ(0x548599858c77ef83ul, FieldCollection(type, Field::Set::Builder().insert(&type.getField("headerval")).build()).hash());
+    EXPECT_EQ(0x4a7ff2406d36a9b0ul, FieldCollection(type, Field::Set::Builder().insert(&type.getField("headerval")).insert(&type.getField("hstringval")).build()).hash());
+    EXPECT_EQ(0x1e0918531b19734ul, FieldCollection(type, Field::Set::Builder().insert(&type.getField("hstringval")).build()).hash());
 }
 
 } // document
diff --git a/document/src/vespa/document/base/field.cpp b/document/src/vespa/document/base/field.cpp
index ac195ccf7ea..7f1a598cd76 100644
--- a/document/src/vespa/document/base/field.cpp
+++ b/document/src/vespa/document/base/field.cpp
@@ -7,9 +7,21 @@
 #include <vespa/vespalib/util/exceptions.h>
 #include <vespa/vespalib/stllike/asciistream.h>
 #include <vespa/vespalib/util/bobhash.h>
+#include <algorithm>
 
 namespace document {
 
+Field::Set::Set(std::vector<CPtr> fields)
+    : _fields(std::move(fields))
+{
+    std::sort(_fields.begin(), _fields.end(), Field::FieldPtrComparator());
+}
+
+bool
+Field::Set::contains(const Field & field) const {
+    return std::binary_search(_fields.begin(), _fields.end(), &field, Field::FieldPtrComparator());
+}
+
 Field::Field() : Field("", 0, *DataType::INT) { }
 
 Field::Field(vespalib::stringref name, int fieldId, const DataType& dataType)
diff --git a/document/src/vespa/document/base/field.h b/document/src/vespa/document/base/field.h
index 3c739b2bfd3..cf876903dfa 100644
--- a/document/src/vespa/document/base/field.h
+++ b/document/src/vespa/document/base/field.h
@@ -28,16 +28,35 @@ class Field final : public vespalib::FieldBase,
     const DataType *_dataType;
     int             _fieldId;
 public:
-    typedef std::shared_ptr<const Field> CSP;
-    typedef std::shared_ptr<Field> SP;
+    using CSP = std::shared_ptr<const Field>;
+    using SP = std::shared_ptr<Field>;
+    using CPtr = const Field *;
 
     struct FieldPtrComparator {
-        bool operator()(const Field* f1, const Field* f2) const {
+        bool operator()(CPtr f1, CPtr f2) const {
             return (*f1 < *f2);
         }
     };
 
-    using Set = std::set<const Field*, FieldPtrComparator>;
+    class Set {
+    public:
+        class Builder {
+        public:
+            Builder & reserve(size_t sz) { _vector.reserve(sz); return *this; }
+            Builder & insert(CPtr field) { _vector.emplace_back(field); return *this; }
+            Set build() { return Set(std::move(_vector)); }
+        private:
+            std::vector<CPtr> _vector;
+        };
+        bool contains(const Field & field) const;
+        size_t size() const { return _fields.size(); }
+        bool empty() const { return _fields.empty(); }
+        const CPtr * begin() const { return &_fields[0]; }
+        const CPtr * end() const { return begin() + _fields.size(); }
+    private:
+        explicit Set(std::vector<CPtr> fields);
+        std::vector<CPtr> _fields;
+    };
 
     /**
      * Creates a completely specified field instance.
@@ -47,8 +66,7 @@ public:
      * @param type The datatype of the field.
      * @param headerField Whether or not this is a "header" field.
      */
-    Field(vespalib::stringref name, int fieldId,
-          const DataType &type);
+    Field(vespalib::stringref name, int fieldId, const DataType &type);
 
     Field();
 
diff --git a/document/src/vespa/document/datatype/structdatatype.cpp b/document/src/vespa/document/datatype/structdatatype.cpp
index ed17d22da59..11af020c465 100644
--- a/document/src/vespa/document/datatype/structdatatype.cpp
+++ b/document/src/vespa/document/datatype/structdatatype.cpp
@@ -164,11 +164,12 @@ bool StructDataType::hasField(int32_t fieldId) const {
 Field::Set
 StructDataType::getFieldSet() const
 {
-    Field::Set fields;
+    Field::Set::Builder builder;
+    builder.reserve(_idFieldMap.size());
     for (const auto & entry : _idFieldMap) {
-        fields.insert(entry.second.get());
+        builder.insert(entry.second.get());
     }
-    return fields;
+    return builder.build();
 }
 
 namespace {
diff --git a/document/src/vespa/document/fieldset/fieldsetrepo.cpp b/document/src/vespa/document/fieldset/fieldsetrepo.cpp
index c576624b026..5cc3e548d82 100644
--- a/document/src/vespa/document/fieldset/fieldsetrepo.cpp
+++ b/document/src/vespa/document/fieldset/fieldsetrepo.cpp
@@ -44,18 +44,18 @@ parseFieldCollection(const DocumentTypeRepo& repo,
     const DocumentType& type(*typePtr);
 
     StringTokenizer tokenizer(fieldNames, ",");
-    Field::Set fields;
+    Field::Set::Builder builder;
     for (const auto & token : tokenizer) {
         const DocumentType::FieldSet * fs = type.getFieldSet(token);
         if (fs) {
             for (const auto & fieldName : fs->getFields()) {
-                fields.insert(&type.getField(fieldName));
+                builder.insert(&type.getField(fieldName));
             }
         } else {
-            fields.insert(&type.getField(token));
+            builder.insert(&type.getField(token));
         }
     }
-    return std::make_unique<FieldCollection>(type, std::move(fields));
+    return std::make_unique<FieldCollection>(type, builder.build());
 }
 
 }
diff --git a/document/src/vespa/document/fieldset/fieldsets.cpp b/document/src/vespa/document/fieldset/fieldsets.cpp
index 586cef0e5f4..115ad37343d 100644
--- a/document/src/vespa/document/fieldset/fieldsets.cpp
+++ b/document/src/vespa/document/fieldset/fieldsets.cpp
@@ -4,6 +4,7 @@
 #include <vespa/document/fieldvalue/document.h>
 #include <vespa/document/datatype/documenttype.h>
 #include <vespa/vespalib/stllike/asciistream.h>
+#include <algorithm>
 #include <xxhash.h>
 
 namespace document {
@@ -38,25 +39,10 @@ FieldCollection::contains(const FieldSet& fields) const
 {
     switch (fields.getType()) {
         case Type::FIELD:
-            return _set.find(static_cast<const Field*>(&fields)) != _set.end();
+            return _set.contains(static_cast<const Field &>(fields));
         case Type::SET: {
             const auto & coll = static_cast<const FieldCollection&>(fields);
-
-            if (_set.size() < coll._set.size()) {
-                return false;
-            }
-
-            auto iter = coll.getFields().begin();
-
-            while (iter != coll.getFields().end()) {
-                if (_set.find(*iter) == _set.end()) {
-                    return false;
-                }
-
-                ++iter;
-            }
-
-            return true;
+            return std::includes(_set.begin(), _set.end(), coll.getFields().begin(), coll.getFields().end(), Field::FieldPtrComparator());
         }
         case Type::NONE:
         case Type::DOCID:
diff --git a/document/src/vespa/document/fieldset/fieldsets.h b/document/src/vespa/document/fieldset/fieldsets.h
index d37d72d6109..9537a5bdf61 100644
--- a/document/src/vespa/document/fieldset/fieldsets.h
+++ b/document/src/vespa/document/fieldset/fieldsets.h
@@ -65,8 +65,8 @@ public:
 
     uint64_t hash() const { return _hash; }
 private:
-    Field::Set _set;
-    uint64_t   _hash;
+    Field::Set          _set;
+    uint64_t            _hash;
     const DocumentType& _docType;
 };