Merge pull request #42 from zeux/compact

Implement compact mode.

This introduces a new storage mode that dramatically reduces node size at some performance cost.
The mode is enabled by defining PUGIXML_COMPACT. This does not change API/ABI - all existing functionality still works.

The pointers are stored using delta encoding and bytes, with some additional tricks to make encoding more optimal for e.g. parent pointer and string pointers. Since the node is fixed size, we have to fall back to a hash table if the pointer does not fit. Thus all DOM operations still have amortized complexity - constant number of operations if you don't need the hash table and amortized constant if you do.

Aside from some performance loss (which is inevitable since decoding takes time), the only other caveat is that we can't remove entries from the hash table - so in some edge cases with a lot of node removals the peak memory consumption can grow indefinitely. In theory we can implement this later; it's unclear that this is useful at this point.

The resulting node/attribute sizes are as follows:
non-compact node: 28b 32-bit, 56b 64-bit
compact node: 12b 32/64-bit
non-compact attribute: 20b 32-bit, 40b 64-bit
compact attribute: 8b 32/64-bit

4 files changed, 123 insertions, 24 deletions

diff --git a/tests/autotest-appveyor.ps1 b/tests/autotest-appveyor.ps1
index 8b7a24c..6b88766 100644
--- a/tests/autotest-appveyor.ps1
+++ b/tests/autotest-appveyor.ps1
@@ -21,7 +21,7 @@ foreach ($vs in 9,10,11,12)
 		Invoke-CmdScript "C:\Program Files (x86)\Microsoft Visual Studio $vs.0\VC\vcvarsall.bat" $arch
 		if (! $?) { throw "Error setting up VS$vs $arch" }
 
-		foreach ($defines in "standard", "PUGIXML_WCHAR_MODE")
+		foreach ($defines in "standard", "PUGIXML_WCHAR_MODE", "PUGIXML_COMPACT")
 		{
 			$target = "tests_vs${vs}_${arch}_${defines}"
 			$deflist = if ($defines -eq "standard") { "" } else { "/D$defines" }
diff --git a/tests/test_dom_modify.cpp b/tests/test_dom_modify.cpp
index f2877ff..365561f 100644
--- a/tests/test_dom_modify.cpp
+++ b/tests/test_dom_modify.cpp
@@ -948,6 +948,25 @@ TEST(dom_node_memory_limit)
 	}
 }
 
+TEST(dom_node_memory_limit_pi)
+{
+	const unsigned int length = 65536;
+	static char_t string[length + 1];
+
+	for (unsigned int i = 0; i < length; ++i) string[i] = 'a';
+	string[length] = 0;
+
+	test_runner::_memory_fail_threshold = 32768 * 2 + sizeof(string);
+
+	xml_document doc;
+
+	for (int j = 0; j < 32; ++j)
+	{
+		CHECK(doc.append_child(node_pi).set_value(string));
+		CHECK(doc.remove_child(doc.first_child()));
+	}
+}
+
 TEST(dom_node_doctype_top_level)
 {
 	xml_document doc;
@@ -1116,6 +1135,11 @@ TEST(dom_node_append_buffer_out_of_memory_nodes)
 
 	test_runner::_memory_fail_threshold = 32768 + 128 + data.length() * sizeof(char_t) + 32;
 
+#ifdef PUGIXML_COMPACT
+	// ... and some space for hash table
+	test_runner::_memory_fail_threshold += 2048;
+#endif
+
 	xml_document doc;
 	CHECK_ALLOC_FAIL(CHECK(doc.append_buffer(data.c_str(), data.length() * sizeof(char_t), parse_fragment).status == status_out_of_memory));
 
@@ -1132,9 +1156,9 @@ TEST(dom_node_append_buffer_out_of_memory_nodes)
 
 TEST(dom_node_append_buffer_out_of_memory_name)
 {
-	test_runner::_memory_fail_threshold = 32768 + 128;
+	test_runner::_memory_fail_threshold = 32768 + 4096;
 
-	char data[128] = {0};
+	char data[4096] = {0};
 
 	xml_document doc;
 	CHECK(doc.append_child(STR("root")));
@@ -1378,6 +1402,11 @@ TEST(dom_node_copy_copyless)
 	// the document is parsed in-place so there should only be 1 page worth of allocations
 	test_runner::_memory_fail_threshold = 32768 + 128;
 
+#ifdef PUGIXML_COMPACT
+	// ... and some space for hash table
+	test_runner::_memory_fail_threshold += 2048;
+#endif
+
 	xml_document doc;
 	CHECK(doc.load_buffer_inplace(&datacopy[0], datacopy.size() * sizeof(char_t), parse_full));
 
@@ -1455,6 +1484,11 @@ TEST(dom_node_copy_attribute_copyless)
 	// the document is parsed in-place so there should only be 1 page worth of allocations
 	test_runner::_memory_fail_threshold = 32768 + 128;
 
+#ifdef PUGIXML_COMPACT
+	// ... and some space for hash table
+	test_runner::_memory_fail_threshold += 2048;
+#endif
+
 	xml_document doc;
 	CHECK(doc.load_buffer_inplace(&datacopy[0], datacopy.size() * sizeof(char_t), parse_full));
 
diff --git a/tests/test_memory.cpp b/tests/test_memory.cpp
index bd80ca1..85d6e86 100644
--- a/tests/test_memory.cpp
+++ b/tests/test_memory.cpp
@@ -1,30 +1,38 @@
 #include "common.hpp"
 
 #include "writer_string.hpp"
+#include "allocator.hpp"
 
 #include <string>
+#include <vector>
 
 namespace
 {
-	int allocate_count = 0;
-	int deallocate_count = 0;
+	int page_allocs = 0;
+	int page_deallocs = 0;
+
+	bool is_page(size_t size)
+	{
+		return size >= 16384;
+	}
 
 	void* allocate(size_t size)
 	{
-		++allocate_count;
-		return new char[size];
+		void* ptr = memory_allocate(size);
+		page_allocs += is_page(memory_size(ptr));
+		return ptr;
 	}
 
 	void deallocate(void* ptr)
 	{
-		++deallocate_count;
-		delete[] reinterpret_cast<char*>(ptr);
+		page_deallocs += is_page(memory_size(ptr));
+		memory_deallocate(ptr);
 	}
 }
 
 TEST(memory_custom_memory_management)
 {
-	allocate_count = deallocate_count = 0;
+	page_allocs = page_deallocs = 0;
 
 	// remember old functions
 	allocation_function old_allocate = get_memory_allocation_function();
@@ -37,30 +45,30 @@ TEST(memory_custom_memory_management)
 		// parse document
 		xml_document doc;
 
-		CHECK(allocate_count == 0 && deallocate_count == 0);
+		CHECK(page_allocs == 0 && page_deallocs == 0);
 
 		CHECK(doc.load_string(STR("<node />")));
 	
-		CHECK(allocate_count == 2 && deallocate_count == 0);
+		CHECK(page_allocs == 1 && page_deallocs == 0);
 
 		// modify document (no new page)
 		CHECK(doc.first_child().set_name(STR("foobars")));
-		CHECK(allocate_count == 2 && deallocate_count == 0);
+		CHECK(page_allocs == 1 && page_deallocs == 0);
 
 		// modify document (new page)
 		std::basic_string<pugi::char_t> s(65536, 'x');
 
 		CHECK(doc.first_child().set_name(s.c_str()));
-		CHECK(allocate_count == 3 && deallocate_count == 0);
+		CHECK(page_allocs == 2 && page_deallocs == 0);
 
 		// modify document (new page, old one should die)
 		s += s;
 
 		CHECK(doc.first_child().set_name(s.c_str()));
-		CHECK(allocate_count == 4 && deallocate_count == 1);
+		CHECK(page_allocs == 3 && page_deallocs == 1);
 	}
 
-	CHECK(allocate_count == 4 && deallocate_count == 4);
+	CHECK(page_allocs == 3 && page_deallocs == 3);
 
 	// restore old functions
 	set_memory_management_functions(old_allocate, old_deallocate);
@@ -68,7 +76,7 @@ TEST(memory_custom_memory_management)
 
 TEST(memory_large_allocations)
 {
-	allocate_count = deallocate_count = 0;
+	page_allocs = page_deallocs = 0;
 
 	// remember old functions
 	allocation_function old_allocate = get_memory_allocation_function();
@@ -80,7 +88,7 @@ TEST(memory_large_allocations)
 	{
 		xml_document doc;
 
-		CHECK(allocate_count == 0 && deallocate_count == 0);
+		CHECK(page_allocs == 0 && page_deallocs == 0);
 
 		// initial fill
 		for (size_t i = 0; i < 128; ++i)
@@ -90,7 +98,7 @@ TEST(memory_large_allocations)
 			CHECK(doc.append_child(node_pcdata).set_value(s.c_str()));
 		}
 
-		CHECK(allocate_count > 0 && deallocate_count == 0);
+		CHECK(page_allocs > 0 && page_deallocs == 0);
 
 		// grow-prune loop
 		while (doc.first_child())
@@ -116,15 +124,72 @@ TEST(memory_large_allocations)
 			}
 		}
 
-		CHECK(allocate_count == deallocate_count + 1); // only one live page left (it waits for new allocations)
+		CHECK(page_allocs == page_deallocs + 1); // only one live page left (it waits for new allocations)
+
+		char buffer;
+		CHECK(doc.load_buffer_inplace(&buffer, 0, parse_fragment, get_native_encoding()));
+
+		CHECK(page_allocs == page_deallocs); // no live pages left
+	}
+
+	CHECK(page_allocs == page_deallocs); // everything is freed
+
+	// restore old functions
+	set_memory_management_functions(old_allocate, old_deallocate);
+}
+
+TEST(memory_page_management)
+{
+	page_allocs = page_deallocs = 0;
+
+	// remember old functions
+	allocation_function old_allocate = get_memory_allocation_function();
+	deallocation_function old_deallocate = get_memory_deallocation_function();
+
+	// replace functions
+	set_memory_management_functions(allocate, deallocate);
+
+	{
+		xml_document doc;
+
+		CHECK(page_allocs == 0 && page_deallocs == 0);
+
+		// initial fill
+		std::vector<xml_node> nodes;
+
+		for (size_t i = 0; i < 4000; ++i)
+		{
+			xml_node node = doc.append_child(STR("node"));
+			CHECK(node);
+
+			nodes.push_back(node);
+		}
+
+		CHECK(page_allocs > 0 && page_deallocs == 0);
+
+		// grow-prune loop
+		size_t offset = 0;
+		size_t prime = 15485863;
+
+		while (nodes.size() > 0)
+		{
+			offset = (offset + prime) % nodes.size();
+
+			doc.remove_child(nodes[offset]);
+
+			nodes[offset] = nodes.back();
+			nodes.pop_back();
+		}
+
+		CHECK(page_allocs == page_deallocs + 1); // only one live page left (it waits for new allocations)
 
 		char buffer;
 		CHECK(doc.load_buffer_inplace(&buffer, 0, parse_fragment, get_native_encoding()));
 
-		CHECK(allocate_count == deallocate_count); // no live pages left
+		CHECK(page_allocs == page_deallocs); // no live pages left
 	}
 
-	CHECK(allocate_count == deallocate_count); // everything is freed
+	CHECK(page_allocs == page_deallocs); // everything is freed
 
 	// restore old functions
 	set_memory_management_functions(old_allocate, old_deallocate);
diff --git a/tests/test_xpath_variables.cpp b/tests/test_xpath_variables.cpp
index f72d6ff..c4a3b7f 100644
--- a/tests/test_xpath_variables.cpp
+++ b/tests/test_xpath_variables.cpp
@@ -445,7 +445,7 @@ TEST_XML(xpath_variables_copy, "<node />")
 	CHECK(!set3.get(STR("a")));

 }

 

-TEST_XML(xpath_variables_copy_out_of_memory, "<node />")

+TEST_XML(xpath_variables_copy_out_of_memory, "<node1 /><node2 />")

 {

 	xpath_variable_set set1;

 	set1.set(STR("a"), true);

@@ -471,7 +471,7 @@ TEST_XML(xpath_variables_copy_out_of_memory, "<node />")
 	CHECK(set2.get(STR("a"))->get_boolean() == true);

 	CHECK(set2.get(STR("b"))->get_number() == 2.0);

 	CHECK_STRING(set2.get(STR("c"))->get_string(), STR("string"));

-	CHECK(set2.get(STR("d"))->get_node_set().size() == 1);

+	CHECK(set2.get(STR("d"))->get_node_set().size() == 2);

 }

 

 #if __cplusplus >= 201103