From 224e702d1f879a9ecd784289b42720a278ee3e01 Mon Sep 17 00:00:00 2001
From: Arseny Kapoulkine <arseny.kapoulkine@gmail.com>
Date: Wed, 8 Oct 2014 20:09:29 -0700
Subject: Change compact_pointer_parent to use 2 bytes
Parent pointers need to be able to reach everywhere within a page to
minimize shared parent pointer reuse unless it's absolutely necessary.
This reduces parent hash utilization on all test cases to <1%.
Rename compact_parent to compact_shared_parent.
---
src/pugixml.cpp | 57 ++++++++++++++++++++++++++++++++++-----------------------
1 file changed, 34 insertions(+), 23 deletions(-)
diff --git a/src/pugixml.cpp b/src/pugixml.cpp
index 1694a68..0853776 100644
--- a/src/pugixml.cpp
+++ b/src/pugixml.cpp
@@ -297,7 +297,7 @@ PUGI__NS_BEGIN
#ifdef PUGIXML_COMPACT
result->compact_string_base = 0;
- result->compact_parent = 0;
+ result->compact_shared_parent = 0;
#endif
return result;
@@ -313,7 +313,7 @@ PUGI__NS_BEGIN
#ifdef PUGIXML_COMPACT
char_t* compact_string_base;
- void* compact_parent;
+ void* compact_shared_parent;
#endif
};
@@ -759,7 +759,7 @@ PUGI__NS_BEGIN
template <typename T, int header_offset, int tag> class compact_pointer_parent
{
public:
- compact_pointer_parent(): _data(0)
+ compact_pointer_parent(): _data0(0), _data1(0)
{
}
@@ -772,43 +772,55 @@ PUGI__NS_BEGIN
{
if (value)
{
- ptrdiff_t offset = ((reinterpret_cast<char*>(value) - reinterpret_cast<char*>(this) + int(compact_alignment - 1)) >> compact_alignment_log2) + 253;
+ ptrdiff_t offset = ((reinterpret_cast<char*>(value) - reinterpret_cast<char*>(this) + int(compact_alignment - 1)) >> compact_alignment_log2) + 65533;
- if (static_cast<uintptr_t>(offset) <= 253)
- _data = static_cast<unsigned char>(offset + 1);
+ if (static_cast<uintptr_t>(offset) <= 65533)
+ {
+ _data0 = static_cast<unsigned char>(offset + 1);
+ _data1 = static_cast<unsigned char>((offset + 1) >> 8);
+ }
else
{
xml_memory_page* page = compact_get_page(this, header_offset);
- if (page->compact_parent == 0)
- page->compact_parent = value;
+ if (page->compact_shared_parent == 0)
+ page->compact_shared_parent = value;
- if (page->compact_parent == value)
- _data = 254;
+ if (page->compact_shared_parent == value)
+ {
+ _data0 = 254;
+ _data1 = 255;
+ }
else
{
compact_set_value<header_offset, tag>(this, value);
- _data = 255;
+ _data0 = 255;
+ _data1 = 255;
}
}
}
else
- _data = 0;
+ {
+ _data0 = 0;
+ _data1 = 0;
+ }
}
operator T* const() const
{
- if (_data)
+ unsigned int data = _data0 + (_data1 << 8);
+
+ if (data)
{
- if (_data < 254)
+ if (data < 65534)
{
uintptr_t base = reinterpret_cast<uintptr_t>(this) & ~(compact_alignment - 1);
- return reinterpret_cast<T*>(base + ((_data - (1 + 253)) << compact_alignment_log2));
+ return reinterpret_cast<T*>(base + ((data - (1 + 65533)) << compact_alignment_log2));
}
- else if (_data == 254)
- return static_cast<T*>(compact_get_page(this, header_offset)->compact_parent);
+ else if (data == 65534)
+ return static_cast<T*>(compact_get_page(this, header_offset)->compact_shared_parent);
else
return compact_get_value<header_offset, T>(this);
}
@@ -822,7 +834,8 @@ PUGI__NS_BEGIN
}
private:
- unsigned char _data;
+ unsigned char _data0;
+ unsigned char _data1;
};
template <int header_offset, int tag> class compact_string
@@ -932,15 +945,13 @@ namespace pugi
impl::compact_header header;
- unsigned char padding;
-
- impl::compact_string<4, /*tag*/21> contents; ///< Pointer to element name.
+ impl::compact_string<3, /*tag*/21> contents; ///< Pointer to element name.
- impl::compact_pointer_parent<xml_node_struct, 7, /*tag*/22> parent; ///< Pointer to parent
+ impl::compact_pointer_parent<xml_node_struct, 6, /*tag*/22> parent; ///< Pointer to parent
impl::compact_pointer<xml_node_struct, 8, /*tag*/23, 0> first_child; ///< First child
- impl::compact_pointer<xml_node_struct, 9, /*tag*/24> prev_sibling_c; ///< Left brother (cyclic list)
+ impl::compact_pointer<xml_node_struct, 9, /*tag*/24> prev_sibling_c; ///< Left brother (cyclic list)
impl::compact_pointer<xml_node_struct, 10, /*tag*/25, 0> next_sibling; ///< Right brother
impl::compact_pointer<xml_attribute_struct, 11, /*tag*/26, 0> first_attribute; ///< First attribute
--
cgit v1.2.3