Merge pull request #27167 from vespa-engine/balder/pack-nodeelement-in-8-bytes

Balder/pack nodeelement in 8 bytes

6 files changed, 100 insertions, 92 deletions

diff --git a/vespalib/src/tests/btree/btree_test.cpp b/vespalib/src/tests/btree/btree_test.cpp
index 6305eca41ac..b2f9f01e517 100644
--- a/vespalib/src/tests/btree/btree_test.cpp
+++ b/vespalib/src/tests/btree/btree_test.cpp
@@ -297,9 +297,9 @@ BTreeTest::assertMemoryUsage(const vespalib::MemoryUsage & exp, const vespalib::
 }
 
 TEST_F(BTreeTest, control_iterator_size) {
-    EXPECT_EQ(208u,  sizeof(BTreeIteratorBase<uint32_t, uint32_t, NoAggregated>));
-    EXPECT_EQ(208u,  sizeof(BTreeIteratorBase<uint32_t, BTreeNoLeafData, NoAggregated>));
-    EXPECT_EQ(544u, sizeof(MyTree::Iterator));
+    EXPECT_EQ(120u,  sizeof(BTreeIteratorBase<uint32_t, uint32_t, NoAggregated>));
+    EXPECT_EQ(120u,  sizeof(BTreeIteratorBase<uint32_t, BTreeNoLeafData, NoAggregated>));
+    EXPECT_EQ(288u, sizeof(MyTree::Iterator));
 }
 
 TEST_F(BTreeTest, require_that_node_insert_works)
diff --git a/vespalib/src/vespa/vespalib/btree/btreeiterator.h b/vespalib/src/vespa/vespalib/btree/btreeiterator.h
index 5e18eb0a5de..14143836c22 100644
--- a/vespalib/src/vespa/vespalib/btree/btreeiterator.h
+++ b/vespalib/src/vespa/vespalib/btree/btreeiterator.h
@@ -35,64 +35,73 @@ class NodeElement
     using NodeType = NodeT;
     using KeyType = typename NodeType::KeyType;
     using DataType = typename NodeType::DataType;
-    const NodeType *_node;
-    uint32_t        _idx;
+    uint64_t _nodeAndIdx;
+
+    NodeType * getWNode() const { return const_cast<NodeType *>(getNode()); }
+    static constexpr uint8_t NODE_BITS = 57;
+    static constexpr uint8_t IDX_BITS = 64 - NODE_BITS;
+    static constexpr uint64_t NODE_MASK = (1ul << NODE_BITS) - 1ul;
+    static constexpr uint64_t IDX_MASK = (1ul << IDX_BITS) - 1ul;
+    static constexpr uint8_t IDX_SHIFT = NODE_BITS;
 
-    NodeType * getWNode() const { return const_cast<NodeType *>(_node); }
 public:
-    NodeElement() : _node(nullptr), _idx(0u) { }
-    NodeElement(const NodeType *node, uint32_t idx) : _node(node), _idx(idx) { }
-
-    void invalidate() { _node = nullptr; _idx = 0; }
-    void setNode(const NodeType *node) { _node = node; }
-    const NodeType * getNode() const { return _node; }
-    void setIdx(uint32_t idx) { _idx = idx; }
-    uint32_t getIdx() const { return _idx; }
-    void incIdx() { ++_idx; }
-    void decIdx() { --_idx; }
-
-    void setNodeAndIdx(const NodeType *node, uint32_t idx) {
-        _node = node;
-        _idx = idx;
+    NodeElement() noexcept : _nodeAndIdx(0ul) { }
+    NodeElement(const NodeType *node, uint32_t idx) noexcept : _nodeAndIdx(uint64_t(node) | uint64_t(idx) << IDX_SHIFT) {
+        assert((uint64_t(node) & ~NODE_MASK) == 0ul);
+        assert(idx <= IDX_MASK);
     }
 
-    const KeyType & getKey() const { return _node->getKey(_idx); }
-    const DataType & getData() const { return _node->getData(_idx); }
+    void invalidate() noexcept { _nodeAndIdx = 0; }
+    void setNode(const NodeType *node) noexcept {
+        assert((uint64_t(node) & ~NODE_MASK) == 0ul);
+        _nodeAndIdx = (_nodeAndIdx & ~NODE_MASK) | uint64_t(node);
+    }
+    const NodeType * getNode() const noexcept { return reinterpret_cast<const NodeType *>(_nodeAndIdx & NODE_MASK); }
+    void setIdx(uint32_t idx) noexcept {
+        assert(idx <= IDX_MASK);
+        _nodeAndIdx = (_nodeAndIdx & NODE_MASK) | (uint64_t(idx) << IDX_SHIFT);
+    }
+    uint32_t getIdx() const noexcept { return _nodeAndIdx >> IDX_SHIFT; }
+    void incIdx() noexcept { setIdx(getIdx() + 1); }
+    void decIdx() noexcept { setIdx(getIdx() - 1); }
+
+    void setNodeAndIdx(const NodeType *node, uint32_t idx) noexcept {
+        assert((uint64_t(node) & ~NODE_MASK) == 0ul);
+        assert(idx <= IDX_MASK);
+        _nodeAndIdx = uint64_t(node) | uint64_t(idx) << IDX_SHIFT;
+    }
+
+    const KeyType & getKey() const noexcept { return getNode()->getKey(getIdx()); }
+    const DataType & getData() const noexcept { return getNode()->getData(getIdx()); }
     // Only use during compaction when changing reference to moved value
-    DataType &getWData() { return getWNode()->getWData(_idx); }
-    bool valid() const { return _node != nullptr; }
-    void adjustLeftVictimKilled() {
-        assert(_idx > 0);
-        --_idx;
+    DataType &getWData() noexcept { return getWNode()->getWData(getIdx()); }
+    bool valid() const noexcept { return _nodeAndIdx != 0; }
+    void adjustLeftVictimKilled() noexcept {
+        assert(getIdx() > 0);
+        decIdx();
     }
 
-    void adjustSteal(uint32_t stolen) {
-        assert(_idx + stolen < _node->validSlots());
-        _idx += stolen;
+    void adjustSteal(uint32_t stolen) noexcept {
+        assert(getIdx() + stolen < getNode()->validSlots());
+        setIdx(getIdx() + stolen);
     }
 
-    void adjustSplit(bool inRightSplit) {
+    void adjustSplit(bool inRightSplit) noexcept {
         if (inRightSplit)
-            ++_idx;
+            incIdx();
     }
 
-    bool adjustSplit(bool inRightSplit, const NodeType *splitNode) {
+    bool adjustSplit(bool inRightSplit, const NodeType *splitNode) noexcept {
         adjustSplit(inRightSplit);
-        if (_idx >= _node->validSlots()) {
-            _idx -= _node->validSlots();
-            _node = splitNode;
+        if (getIdx() >= getNode()->validSlots()) {
+            setNodeAndIdx(splitNode, getIdx() - getNode()->validSlots());
             return true;
         }
         return false;
     }
 
-    void swap(NodeElement &rhs) {
-        std::swap(_node, rhs._node);
-        std::swap(_idx, rhs._idx);
-    }
-
-    bool operator!=(const NodeElement &rhs) const {
-        return (_node != rhs._node) || (_idx != rhs._idx);
+    bool operator!=(const NodeElement &rhs) const noexcept {
+        return _nodeAndIdx != rhs._nodeAndIdx;
     }
 };
 
@@ -194,7 +203,7 @@ protected:
     /**
      * Default constructor.  Iterator is not associated with a tree.
      */
-    BTreeIteratorBase();
+    BTreeIteratorBase() noexcept;
 
     /**
      * Step iterator forwards. If at end then leave it at end.
@@ -523,7 +532,7 @@ public:
     /**
      * Default constructor.  Iterator is not associated with a tree.
      */
-    BTreeConstIterator() : ParentType() { }
+    BTreeConstIterator() noexcept : ParentType() { }
 
     /**
      * Step iterator forwards. If at end then leave it at end.
diff --git a/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp b/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp
index a94bac8a67e..5884bb2849b 100644
--- a/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp
+++ b/vespalib/src/vespa/vespalib/btree/btreeiterator.hpp
@@ -22,8 +22,8 @@ BTreeIteratorBase(const BTreeIteratorBase &other)
     for (size_t i = 0; i < _pathSize; ++i) {
         _path[i] = other._path[i];
     }
-    if (other._compatLeafNode.get()) {
-        _compatLeafNode.reset( new LeafNodeTempType(*other._compatLeafNode));
+    if (other._compatLeafNode) {
+        _compatLeafNode = std::make_unique<LeafNodeTempType>(*other._compatLeafNode);
     }
     if (other._leaf.getNode() == other._compatLeafNode.get()) {
         _leaf.setNode(_compatLeafNode.get());
@@ -435,8 +435,8 @@ BTreeIteratorBase(const KeyDataType *shortArray,
       _leafRoot(nullptr),
       _compatLeafNode()
 {
-    if(arraySize > 0) {
-        _compatLeafNode.reset(new LeafNodeTempType(shortArray, arraySize));
+    if (arraySize > 0) {
+        _compatLeafNode = std::make_unique<LeafNodeTempType>(shortArray, arraySize);
         _leaf.setNode(_compatLeafNode.get());
         _leafRoot = _leaf.getNode();
         if constexpr (AggrCalcT::hasAggregated()) {
@@ -450,7 +450,7 @@ BTreeIteratorBase(const KeyDataType *shortArray,
 template <typename KeyT, typename DataT, typename AggrT,
           uint32_t INTERNAL_SLOTS, uint32_t LEAF_SLOTS, uint32_t PATH_SIZE>
 BTreeIteratorBase<KeyT, DataT, AggrT, INTERNAL_SLOTS, LEAF_SLOTS, PATH_SIZE>::
-BTreeIteratorBase()
+BTreeIteratorBase() noexcept
     : _leaf(nullptr, 0u),
       _path(),
       _pathSize(0),
diff --git a/vespalib/src/vespa/vespalib/btree/btreenode.h b/vespalib/src/vespa/vespalib/btree/btreenode.h
index 1196b172d1f..cda088556de 100644
--- a/vespalib/src/vespa/vespalib/btree/btreenode.h
+++ b/vespalib/src/vespa/vespalib/btree/btreenode.h
@@ -39,20 +39,20 @@ public:
     static constexpr uint8_t LEAF_LEVEL = 0;
 protected:
     uint16_t _validSlots;
-    BTreeNode(uint8_t level)
+    BTreeNode(uint8_t level) noexcept
         : _level(level),
           _isFrozen(false),
           _validSlots(0)
     {}
 
-    BTreeNode(const BTreeNode &rhs)
+    BTreeNode(const BTreeNode &rhs) noexcept
         : _level(rhs._level),
           _isFrozen(rhs._isFrozen),
           _validSlots(rhs._validSlots)
     {}
 
     BTreeNode &
-    operator=(const BTreeNode &rhs)
+    operator=(const BTreeNode &rhs) noexcept
     {
         assert(!_isFrozen);
         _level = rhs._level;
@@ -89,8 +89,8 @@ class BTreeNodeDataWrap
 public:
     DataT _data[NumSlots];
 
-    BTreeNodeDataWrap() : _data() {}
-    ~BTreeNodeDataWrap() { }
+    BTreeNodeDataWrap() noexcept : _data() {}
+    ~BTreeNodeDataWrap() = default;
 
     void copyData(const BTreeNodeDataWrap &rhs, uint32_t validSlots) {
         const DataT *rdata = rhs._data;
@@ -100,11 +100,11 @@ public:
             *ldata = *rdata;
     }
 
-    const DataT &getData(uint32_t idx) const { return _data[idx]; }
+    const DataT &getData(uint32_t idx) const noexcept { return _data[idx]; }
     // Only use during compaction when changing reference to moved value
-    DataT &getWData(uint32_t idx) { return _data[idx]; }
-    void setData(uint32_t idx, const DataT &data) { _data[idx] = data; }
-    static bool hasData() { return true; }
+    DataT &getWData(uint32_t idx) noexcept { return _data[idx]; }
+    void setData(uint32_t idx, const DataT &data) noexcept { _data[idx] = data; }
+    static bool hasData() noexcept { return true; }
 };
 
 
@@ -112,7 +112,7 @@ template <uint32_t NumSlots>
 class BTreeNodeDataWrap<BTreeNoLeafData, NumSlots>
 {
 public:
-    BTreeNodeDataWrap() {}
+    BTreeNodeDataWrap() noexcept {}
 
     void copyData(const BTreeNodeDataWrap &rhs, uint32_t validSlots) {
         (void) rhs;
@@ -145,7 +145,7 @@ class BTreeNodeAggregatedWrap
     static AggrT _instance;
 
 public:
-    BTreeNodeAggregatedWrap()
+    BTreeNodeAggregatedWrap() noexcept
         : _aggr()
     {}
     AggrT &getAggregated() { return _aggr; }
@@ -161,7 +161,7 @@ class BTreeNodeAggregatedWrap<NoAggregated>
 
     static NoAggregated _instance;
 public:
-    BTreeNodeAggregatedWrap() {}
+    BTreeNodeAggregatedWrap() noexcept {}
 
     NoAggregated &getAggregated() { return _instance; }
     const NoAggregated &getAggregated() const { return _instance; }
@@ -174,14 +174,14 @@ template <typename KeyT, uint32_t NumSlots>
 class BTreeNodeT : public BTreeNode {
 protected:
     KeyT _keys[NumSlots];
-    BTreeNodeT(uint8_t level)
+    BTreeNodeT(uint8_t level) noexcept
         : BTreeNode(level),
           _keys()
     {}
 
     ~BTreeNodeT() = default;
 
-    BTreeNodeT(const BTreeNodeT &rhs)
+    BTreeNodeT(const BTreeNodeT &rhs) noexcept
         : BTreeNode(rhs)
     {
         const KeyT *rkeys = rhs._keys;
@@ -192,7 +192,7 @@ protected:
     }
 
     BTreeNodeT &
-    operator=(const BTreeNodeT &rhs)
+    operator=(const BTreeNodeT &rhs) noexcept
     {
         BTreeNode::operator=(rhs);
         const KeyT *rkeys = rhs._keys;
@@ -204,16 +204,16 @@ protected:
     }
 
 public:
-    const KeyT & getKey(uint32_t idx) const { return _keys[idx]; }
-    const KeyT & getLastKey() const { return _keys[validSlots() - 1]; }
-    void writeKey(uint32_t idx, const KeyT & key) {
+    const KeyT & getKey(uint32_t idx) const noexcept { return _keys[idx]; }
+    const KeyT & getLastKey() const noexcept { return _keys[validSlots() - 1]; }
+    void writeKey(uint32_t idx, const KeyT & key) noexcept {
         if constexpr (std::is_same_v<KeyT, vespalib::datastore::AtomicEntryRef>) {
             _keys[idx].store_release(key.load_relaxed());
         } else {
             _keys[idx] = key;
         }
     }
-    void write_key_relaxed(uint32_t idx, const KeyT & key) { _keys[idx] = key; }
+    void write_key_relaxed(uint32_t idx, const KeyT & key) noexcept { _keys[idx] = key; }
 
     template <typename CompareT>
     uint32_t lower_bound(uint32_t sidx, const KeyT & key, CompareT comp) const;
@@ -224,10 +224,10 @@ public:
     template <typename CompareT>
     uint32_t upper_bound(uint32_t sidx, const KeyT & key, CompareT comp) const;
 
-    bool isFull() const { return validSlots() == NumSlots; }
-    bool isAtLeastHalfFull() const { return validSlots() >= minSlots(); }
-    static uint32_t maxSlots() { return NumSlots; }
-    static uint32_t minSlots() { return NumSlots / 2; }
+    bool isFull() const noexcept { return validSlots() == NumSlots; }
+    bool isAtLeastHalfFull() const noexcept { return validSlots() >= minSlots(); }
+    static uint32_t maxSlots() noexcept { return NumSlots; }
+    static uint32_t minSlots() noexcept { return NumSlots / 2; }
 };
 
 template <typename KeyT, typename DataT, typename AggrT, uint32_t NumSlots>
@@ -247,14 +247,14 @@ public:
     using DataWrapType::setData;
     using DataWrapType::copyData;
 protected:
-    BTreeNodeTT(uint8_t level)
+    BTreeNodeTT(uint8_t level) noexcept
         : ParentType(level),
           DataWrapType()
     {}
 
-    ~BTreeNodeTT() {}
+    ~BTreeNodeTT() = default;
 
-    BTreeNodeTT(const BTreeNodeTT &rhs)
+    BTreeNodeTT(const BTreeNodeTT &rhs) noexcept
         : ParentType(rhs),
           DataWrapType(rhs),
           AggrWrapType(rhs)
@@ -262,7 +262,7 @@ protected:
         copyData(rhs, _validSlots);
     }
 
-    BTreeNodeTT &operator=(const BTreeNodeTT &rhs) {
+    BTreeNodeTT &operator=(const BTreeNodeTT &rhs) noexcept {
         ParentType::operator=(rhs);
         AggrWrapType::operator=(rhs);
         copyData(rhs, _validSlots);
@@ -325,19 +325,19 @@ public:
 private:
     uint32_t _validLeaves;
 protected:
-    BTreeInternalNode()
+    BTreeInternalNode() noexcept
         : ParentType(EMPTY_LEVEL),
           _validLeaves(0u)
     {}
 
-    BTreeInternalNode(const BTreeInternalNode &rhs)
+    BTreeInternalNode(const BTreeInternalNode &rhs) noexcept
         : ParentType(rhs),
           _validLeaves(rhs._validLeaves)
     {}
 
-    ~BTreeInternalNode() {}
+    ~BTreeInternalNode() = default;
 
-    BTreeInternalNode &operator=(const BTreeInternalNode &rhs) {
+    BTreeInternalNode &operator=(const BTreeInternalNode &rhs) noexcept {
         ParentType::operator=(rhs);
         _validLeaves = rhs._validLeaves;
         return *this;
@@ -460,17 +460,17 @@ public:
     using KeyType = KeyT;
     using DataType = DataT;
 protected:
-    BTreeLeafNode() : ParentType(LEAF_LEVEL) {}
+    BTreeLeafNode() noexcept : ParentType(LEAF_LEVEL) {}
 
-    BTreeLeafNode(const BTreeLeafNode &rhs)
+    BTreeLeafNode(const BTreeLeafNode &rhs) noexcept
         : ParentType(rhs)
     {}
 
-    BTreeLeafNode(const KeyDataType *smallArray, uint32_t arraySize);
+    BTreeLeafNode(const KeyDataType *smallArray, uint32_t arraySize) noexcept;
 
     ~BTreeLeafNode() = default;
 
-    BTreeLeafNode &operator=(const BTreeLeafNode &rhs) {
+    BTreeLeafNode &operator=(const BTreeLeafNode &rhs) noexcept {
         ParentType::operator=(rhs);
         return *this;
     }
@@ -535,8 +535,7 @@ public:
     using ParentType = BTreeLeafNode<KeyT, DataT, AggrT, NumSlots>;
     using KeyDataType = typename ParentType::KeyDataType;
 
-    BTreeLeafNodeTemp(const KeyDataType *smallArray,
-                      uint32_t arraySize)
+    BTreeLeafNodeTemp(const KeyDataType *smallArray, uint32_t arraySize) noexcept
         : ParentType(smallArray, arraySize)
     {}
 
diff --git a/vespalib/src/vespa/vespalib/btree/btreenode.hpp b/vespalib/src/vespa/vespalib/btree/btreenode.hpp
index c8bc4ec614c..90f4c9a9cc5 100644
--- a/vespalib/src/vespa/vespalib/btree/btreenode.hpp
+++ b/vespalib/src/vespa/vespalib/btree/btreenode.hpp
@@ -366,7 +366,7 @@ BTreeInternalNode<KeyT, AggrT, NumSlots>::cleanFrozen()
 
 template <typename KeyT, typename DataT, typename AggrT, uint32_t NumSlots>
 BTreeLeafNode<KeyT, DataT, AggrT, NumSlots>::
-BTreeLeafNode(const KeyDataType *smallArray, uint32_t arraySize)
+BTreeLeafNode(const KeyDataType *smallArray, uint32_t arraySize) noexcept
     : ParentType(LEAF_LEVEL)
 {
     assert(arraySize <= BTreeLeafNode::maxSlots());
diff --git a/vespalib/src/vespa/vespalib/btree/btreeroot.h b/vespalib/src/vespa/vespalib/btree/btreeroot.h
index c23cf900367..f3e60f91f36 100644
--- a/vespalib/src/vespa/vespalib/btree/btreeroot.h
+++ b/vespalib/src/vespa/vespalib/btree/btreeroot.h
@@ -13,10 +13,10 @@ namespace vespalib::btree {
 
 template <typename, typename, typename, size_t, size_t>
 class BTreeNodeAllocator;
-template <typename, typename, typename, size_t, size_t, class> class
-BTreeBuilder;
-template <typename, typename, typename, size_t, size_t, class> class
-BTreeAggregator;
+template <typename, typename, typename, size_t, size_t, class>
+class BTreeBuilder;
+template <typename, typename, typename, size_t, size_t, class>
+class BTreeAggregator;
 
 template <typename KeyT,
           typename DataT,