From dec4267fb15c3dacb767402d5a696090dae3648d Mon Sep 17 00:00:00 2001 From: Arseny Kapoulkine Date: Sat, 2 May 2015 08:56:39 -0700 Subject: Implement efficient compact_header storage Header is now just 2 bytes, with optional additonal 4 bytes that are only allocated for every 85 nodes / 128 attributes. --- src/pugixml.cpp | 117 ++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 75 insertions(+), 42 deletions(-) diff --git a/src/pugixml.cpp b/src/pugixml.cpp index 70dd037..40e8ab8 100644 --- a/src/pugixml.cpp +++ b/src/pugixml.cpp @@ -409,8 +409,16 @@ PUGI__NS_BEGIN #endif ; +#ifdef PUGIXML_COMPACT + static const uintptr_t xml_memory_block_alignment = 4; + + static const uintptr_t xml_memory_page_alignment = sizeof(void*); +#else + static const uintptr_t xml_memory_block_alignment = sizeof(void*); + static const uintptr_t xml_memory_page_alignment = 64; static const uintptr_t xml_memory_page_pointer_mask = ~(xml_memory_page_alignment - 1); +#endif // extra metadata bits static const uintptr_t xml_memory_page_contents_shared_mask = 32; @@ -422,15 +430,6 @@ PUGI__NS_BEGIN static const uintptr_t xml_memory_page_name_allocated_or_shared_mask = xml_memory_page_name_allocated_mask | xml_memory_page_contents_shared_mask; static const uintptr_t xml_memory_page_value_allocated_or_shared_mask = xml_memory_page_value_allocated_mask | xml_memory_page_contents_shared_mask; - // all allocated blocks have a certain guaranteed alignment - static const uintptr_t xml_memory_block_alignment = - #ifdef PUGIXML_COMPACT - 4 - #else - sizeof(void*) - #endif - ; - #ifdef PUGIXML_COMPACT #define PUGI__GETPAGE_IMPL(header) (header).get_page() #else @@ -457,6 +456,7 @@ PUGI__NS_BEGIN #ifdef PUGIXML_COMPACT result->compact_string_base = 0; result->compact_shared_parent = 0; + result->compact_page_marker = 0; #endif return result; @@ -473,6 +473,7 @@ PUGI__NS_BEGIN #ifdef PUGIXML_COMPACT char_t* compact_string_base; void* compact_shared_parent; + char* compact_page_marker; #endif }; @@ -537,6 +538,35 @@ PUGI__NS_BEGIN return buf; } + void* allocate_object(size_t size, xml_memory_page*& out_page) + { + #ifdef PUGIXML_COMPACT + void* result = allocate_memory(size + sizeof(uint32_t), out_page); + if (!result) return 0; + + // adjust for marker + if (PUGI__UNLIKELY(static_cast(static_cast(result) - out_page->compact_page_marker) >= 256 * xml_memory_block_alignment)) + { + // insert new marker + uint32_t* marker = static_cast(result); + + *marker = reinterpret_cast(marker) - reinterpret_cast(out_page); + out_page->compact_page_marker = reinterpret_cast(marker); + + return marker + 1; + } + else + { + // roll back uint32_t part + _busy_size -= sizeof(uint32_t); + + return result; + } + #else + return allocate_memory(size, out_page); + #endif + } + void deallocate_memory(void* ptr, size_t size, xml_memory_page* page) { if (page == _root) page->busy_size = _busy_size; @@ -694,41 +724,39 @@ PUGI__NS_BEGIN { PUGI__STATIC_ASSERT(xml_memory_block_alignment == compact_alignment); PUGI__STATIC_ASSERT(sizeof(xml_memory_page) + xml_memory_page_size <= (1 << (16 + compact_alignment_log2))); - PUGI__STATIC_ASSERT(xml_memory_page_pointer_mask & 0xff); - ptrdiff_t page_offset = (reinterpret_cast(this) - reinterpret_cast(page)) >> compact_alignment_log2; - assert(page_offset >= 0 && page_offset < (1 << 16)); + ptrdiff_t offset = (reinterpret_cast(this) - page->compact_page_marker); + assert(offset >= 0 && offset < 256 << compact_alignment_log2); - this->page0 = static_cast(page_offset); - this->page1 = static_cast(page_offset >> 8); - this->flags = static_cast(flags); + _page = static_cast(offset >> compact_alignment_log2); + _flags = static_cast(flags); } void operator&=(uintptr_t mod) { - flags &= mod; + _flags &= mod; } void operator|=(uintptr_t mod) { - flags |= mod; + _flags |= mod; } uintptr_t operator&(uintptr_t mod) const { - return flags & mod; + return _flags & mod; } xml_memory_page* get_page() const { - unsigned int page_offset = page0 + (page1 << 8); + const char* page_marker = reinterpret_cast(this) - (_page << compact_alignment_log2); - return const_cast(reinterpret_cast(reinterpret_cast(this) - (page_offset << compact_alignment_log2))); + return const_cast(reinterpret_cast(page_marker - *reinterpret_cast(page_marker))); } private: - unsigned char page0, page1; - unsigned char flags; + unsigned char _page; + unsigned char _flags; }; PUGI__FN xml_memory_page* compact_get_page(const void* object, int header_offset) @@ -976,46 +1004,42 @@ namespace pugi { xml_attribute_struct(impl::xml_memory_page* page): header(page, 0), namevalue_base(0) { - PUGI__STATIC_ASSERT(sizeof(xml_attribute_struct) == 12); + PUGI__STATIC_ASSERT(sizeof(xml_attribute_struct) == 8); } impl::compact_header header; - unsigned char padding[3]; - uint16_t namevalue_base; - impl::compact_string<8, 2> name; - impl::compact_string<9, 3> value; + impl::compact_string<4, 2> name; + impl::compact_string<5, 3> value; - impl::compact_pointer prev_attribute_c; - impl::compact_pointer next_attribute; + impl::compact_pointer prev_attribute_c; + impl::compact_pointer next_attribute; }; struct xml_node_struct { xml_node_struct(impl::xml_memory_page* page, xml_node_type type): header(page, type - 1), namevalue_base(0) { - PUGI__STATIC_ASSERT(sizeof(xml_node_struct) == 16); + PUGI__STATIC_ASSERT(sizeof(xml_node_struct) == 12); } impl::compact_header header; - unsigned char padding[3]; - uint16_t namevalue_base; - impl::compact_string<8, 2> name; - impl::compact_string<9, 3> value; + impl::compact_string<4, 2> name; + impl::compact_string<5, 3> value; - impl::compact_pointer_parent parent; + impl::compact_pointer_parent parent; - impl::compact_pointer first_child; + impl::compact_pointer first_child; - impl::compact_pointer prev_sibling_c; - impl::compact_pointer next_sibling; + impl::compact_pointer prev_sibling_c; + impl::compact_pointer next_sibling; - impl::compact_pointer first_attribute; + impl::compact_pointer first_attribute; }; } #else @@ -1104,7 +1128,7 @@ PUGI__NS_BEGIN inline xml_attribute_struct* allocate_attribute(xml_allocator& alloc) { xml_memory_page* page; - void* memory = alloc.allocate_memory(sizeof(xml_attribute_struct), page); + void* memory = alloc.allocate_object(sizeof(xml_attribute_struct), page); return new (memory) xml_attribute_struct(page); } @@ -1112,7 +1136,7 @@ PUGI__NS_BEGIN inline xml_node_struct* allocate_node(xml_allocator& alloc, xml_node_type type) { xml_memory_page* page; - void* memory = alloc.allocate_memory(sizeof(xml_node_struct), page); + void* memory = alloc.allocate_object(sizeof(xml_node_struct), page); return new (memory) xml_node_struct(page, type); } @@ -6657,7 +6681,16 @@ namespace pugi page->busy_size = impl::xml_memory_page_size; // allocate new root - _root = new (reinterpret_cast(page) + sizeof(impl::xml_memory_page)) impl::xml_document_struct(page); + #ifdef PUGIXML_COMPACT + const size_t page_offset = sizeof(uint32_t); + + page->compact_page_marker = reinterpret_cast(page) + sizeof(impl::xml_memory_page); + *reinterpret_cast(page->compact_page_marker) = sizeof(impl::xml_memory_page); + #else + const size_t page_offset = 0; + #endif + + _root = new (reinterpret_cast(page) + sizeof(impl::xml_memory_page) + page_offset) impl::xml_document_struct(page); _root->prev_sibling_c = _root; // setup sentinel page -- cgit v1.2.3