From e949e9c29de82ee7c32692e7b65da05dd22bdc9d Mon Sep 17 00:00:00 2001 From: couriersud Date: Sat, 13 Jun 2020 15:49:35 +0200 Subject: netlist: Performance improvement and refactoring. [Couriersud] Kidniki now achieves up to 910% when run with static solvers and with nltool. That is significant better than the 860% we have seen previously. This increase is driven by using a global memory pool in the solver code. In addition the following refactoring and code maintenance work is included. Please excuse the large commit, some of this took interfered with other work and the detail development steps were ugly. - gsl support: This commit adds pgsl.h which implements a very limited number of the functionality of the gsl header described in the c++ core guidelines. - clang-tidy fixes - A significant refactoring of palloc.h. Aligned hints were removed, they added complexity without a significant performance gain. Vector operations should better be done on special spans/views. The code has been tested on linux with g++-7, g++-9, clang-11. On Windows mingw-10 and VS2019, OSX clang-11. --- src/lib/netlist/plib/palloc.h | 424 +++++++++++++++++++++++------------------- 1 file changed, 237 insertions(+), 187 deletions(-) (limited to 'src/lib/netlist/plib/palloc.h') diff --git a/src/lib/netlist/plib/palloc.h b/src/lib/netlist/plib/palloc.h index 045461c8418..b3ebcbc52e5 100644 --- a/src/lib/netlist/plib/palloc.h +++ b/src/lib/netlist/plib/palloc.h @@ -9,6 +9,7 @@ /// #include "pconfig.h" +#include "pgsl.h" #include "pmath.h" #include "pstring.h" #include "ptypes.h" @@ -26,28 +27,52 @@ namespace plib { + //============================================================ + // aligned types + //============================================================ + +#if 0 +#if (PUSE_ALIGNED_HINTS) + template + using aligned_type __attribute__((aligned(A))) = T; +#else + template + using aligned_type = T; +#endif + + template + using aligned_pointer = aligned_type *; + + template + using const_aligned_pointer = const aligned_type *; + + template + using aligned_reference = aligned_type &; + + template + using const_aligned_reference = const aligned_type &; +#endif //============================================================ // Standard arena_deleter //============================================================ - template - struct arena_deleter + template + struct arena_deleter_base { - }; template - struct arena_deleter> + struct arena_deleter_base { using arena_storage_type = P; - constexpr arena_deleter(arena_storage_type *a = nullptr) noexcept + constexpr arena_deleter_base(arena_storage_type *a = nullptr) noexcept : m_a(a) { } template::value>> - arena_deleter(const arena_deleter &rhs) noexcept + arena_deleter_base(const arena_deleter_base &rhs) noexcept : m_a(rhs.m_a) { } void operator()(T *p) noexcept @@ -61,18 +86,18 @@ namespace plib { }; template - struct arena_deleter> + struct arena_deleter_base { using arena_storage_type = P; - constexpr arena_deleter(arena_storage_type *a = nullptr) noexcept + constexpr arena_deleter_base(arena_storage_type *a = nullptr) noexcept { plib::unused_var(a); } template::value>::type> - arena_deleter(const arena_deleter &rhs) noexcept + arena_deleter_base(const arena_deleter_base &rhs) noexcept { plib::unused_var(rhs); } @@ -85,6 +110,13 @@ namespace plib { } }; + template + struct arena_deleter : public arena_deleter_base + { + using base_type = arena_deleter_base; + using base_type::base_type; + }; + //============================================================ // owned_ptr: smart pointer with ownership information //============================================================ @@ -209,7 +241,8 @@ namespace plib { { public: using value_type = T; - static constexpr const std::size_t align_size = ALIGN; + using pointer = T *; + static /*constexpr*/ const std::size_t align_size = ALIGN; using arena_type = ARENA; static_assert(align_size >= alignof(T) && (align_size % alignof(T)) == 0, @@ -237,14 +270,14 @@ namespace plib { using other = arena_allocator; }; - T* allocate(std::size_t n) + pointer allocate(std::size_t n) { return reinterpret_cast(m_a.allocate(ALIGN, sizeof(T) * n)); //NOLINT } - void deallocate(T* p, std::size_t n) noexcept + void deallocate(pointer p, std::size_t n) noexcept { - m_a.deallocate(p, n); + m_a.deallocate(p, sizeof(T) * n); } template @@ -296,171 +329,88 @@ namespace plib { // The previous code compiled with gcc and clang on all platforms and // compilers apart from MSVC. - template + template + struct arena_base; + + template struct arena_core { static constexpr const bool has_static_deallocator = HSD; + static constexpr const bool has_static_allocator = HSA; using size_type = std::size_t; template using allocator_type = arena_allocator; + template + using deleter_type = arena_deleter; + + template + using unique_ptr = std::unique_ptr>; + + template + using owned_ptr = plib::owned_ptr>; + static inline P &instance() noexcept { static P s_arena; return s_arena; } - size_type cur_alloc() const noexcept { return m_stat_cur_alloc(); } // NOLINT(readability-convert-member-functions-to-static) - size_type max_alloc() const noexcept { return m_stat_max_alloc(); } // NOLINT(readability-convert-member-functions-to-static) - protected: - static size_t &m_stat_cur_alloc() noexcept { static size_t val = 0; return val; } - static size_t &m_stat_max_alloc() noexcept { static size_t val = 0; return val; } - - }; - - template - struct arena_hsd : public arena_core - { - template - inline void free(T *ptr) noexcept - { - ptr->~T(); - static_cast

(this)->deallocate(ptr, sizeof(T)); - } - }; + friend struct arena_base; + private: + size_t m_stat_cur_alloc = 0; + size_t m_stat_max_alloc = 0; - template - struct arena_hsd : public arena_core - { - template - static inline void free(T *ptr) noexcept - { - ptr->~T(); - P::deallocate(ptr, sizeof(T)); - } }; - template - struct arena_base : public arena_hsd + struct arena_base : public arena_core { - template - using deleter_type = arena_deleter; + using base_type = arena_core; + using size_type = typename base_type::size_type; - template - using unique_ptr = std::unique_ptr>; - - template - using owned_ptr = plib::owned_ptr>; + static size_type cur_alloc() noexcept { return base_type::instance().m_stat_cur_alloc; } + static size_type max_alloc() noexcept { return base_type::instance().m_stat_max_alloc; } - template - inline unique_ptr make_unique(Args&&... args) + static inline void inc_alloc_stat(size_type size) { - auto *mem = static_cast

(this)->allocate(alignof(T), sizeof(T)); - try - { - // NOLINTNEXTLINE(cppcoreguidelines-owning-memory) - auto *mema = new (mem) T(std::forward(args)...); - return unique_ptr(mema, deleter_type()); - } - catch (...) - { - static_cast

(this)->deallocate(mem, sizeof(T)); - throw; - } + auto &i = base_type::instance(); + i.m_stat_cur_alloc += size; + if (i.m_stat_max_alloc - inline owned_ptr make_owned(Args&&... args) + static inline void dec_alloc_stat(size_type size) { - auto *mem = static_cast

(this)->allocate(alignof(T), sizeof(T)); - try - { - // NOLINTNEXTLINE(cppcoreguidelines-owning-memory) - auto *mema = new (mem) T(std::forward(args)...); - return owned_ptr(mema, true, deleter_type()); - } - catch (...) - { - static_cast

(this)->deallocate(mem, sizeof(T)); - throw; - } + base_type::instance().m_stat_cur_alloc -= size; } - - template - inline T * alloc(Args&&... args) - { - auto *p = static_cast

(this)->allocate(alignof(T), sizeof(T)); - // NOLINTNEXTLINE(cppcoreguidelines-owning-memory) - return new(p) T(std::forward(args)...); - } - }; - template - struct arena_base : public arena_hsd + template + struct arena_base : public arena_core { - template - using deleter_type = arena_deleter; + using size_type = typename arena_core::size_type; - template - using unique_ptr = std::unique_ptr>; - - template - using owned_ptr = plib::owned_ptr>; + size_type cur_alloc() const noexcept { return this->m_stat_cur_alloc; } + size_type max_alloc() const noexcept { return this->m_stat_max_alloc; } - template - static inline unique_ptr make_unique(Args&&... args) + inline void inc_alloc_stat(size_type size) { - auto *mem = P::allocate(alignof(T), sizeof(T)); - try - { - // NOLINTNEXTLINE(cppcoreguidelines-owning-memory) - auto *mema = new (mem) T(std::forward(args)...); - return unique_ptr(mema, deleter_type()); - } - catch (...) - { - P::deallocate(mem, sizeof(T)); - throw; - } + this->m_stat_cur_alloc += size; + if (this->m_stat_max_alloc < this->m_stat_cur_alloc) + this->m_stat_max_alloc = this->m_stat_cur_alloc; } - - template - static inline owned_ptr make_owned(Args&&... args) + inline void dec_alloc_stat(size_type size) { - auto *mem = P::allocate(alignof(T), sizeof(T)); - try - { - // NOLINTNEXTLINE(cppcoreguidelines-owning-memory) - auto *mema = new (mem) T(std::forward(args)...); - return owned_ptr(mema, true, deleter_type()); - } - catch (...) - { - P::deallocate(mem, sizeof(T)); - throw; - } - } - - template - static inline T * alloc(Args&&... args) - { - auto *p = P::allocate(alignof(T), sizeof(T)); - // NOLINTNEXTLINE(cppcoreguidelines-owning-memory) - return new(p) T(std::forward(args)...); + this->m_stat_cur_alloc -= size; } }; - struct aligned_arena : public arena_base { - static inline void *allocate( size_t alignment, size_t size ) + static inline gsl::owner allocate( size_t alignment, size_t size ) { - m_stat_cur_alloc() += size; - if (m_stat_max_alloc() < m_stat_cur_alloc()) - m_stat_max_alloc() = m_stat_cur_alloc(); + inc_alloc_stat(size); #if (PUSE_ALIGNED_ALLOCATION) #if defined(_WIN32) || defined(_WIN64) || defined(_MSC_VER) @@ -472,7 +422,7 @@ namespace plib { } return p; #else - return aligned_alloc(alignment, size); + return static_cast>(aligned_alloc(alignment, size)); #endif #else unused_var(alignment); @@ -480,10 +430,10 @@ namespace plib { #endif } - static inline void deallocate( void *ptr, size_t size ) noexcept + static inline void deallocate(gsl::owner ptr, size_t size ) noexcept { //unused_var(size); - m_stat_cur_alloc() -= size; + dec_alloc_stat(size); #if (PUSE_ALIGNED_ALLOCATION) // NOLINTNEXTLINE(cppcoreguidelines-no-malloc) ::free(ptr); @@ -504,14 +454,14 @@ namespace plib { { static inline void *allocate( size_t alignment, size_t size ) { - m_stat_cur_alloc() += size; + inc_alloc_stat(size); unused_var(alignment); return ::operator new(size); } static inline void deallocate( void *ptr, size_t size ) noexcept { - m_stat_cur_alloc() -= size; + dec_alloc_stat(size); ::operator delete(ptr); } @@ -522,31 +472,116 @@ namespace plib { } }; - template - constexpr T *assume_aligned_ptr(T *p) noexcept + namespace detail { - static_assert(ALIGN >= alignof(T), "Alignment must be greater or equal to alignof(T)"); - static_assert(is_pow2(ALIGN), "Alignment must be a power of 2"); + template + static inline T * alloc(Args&&... args) + { + auto *mem = ARENA::allocate(alignof(T), sizeof(T)); + try + { + // NOLINTNEXTLINE(cppcoreguidelines-owning-memory) + return new (mem) T(std::forward(args)...); + } + catch (...) + { + ARENA::deallocate(mem, sizeof(T)); + throw; + } + } -#if (PUSE_ALIGNED_HINTS) - return reinterpret_cast(__builtin_assume_aligned(p, ALIGN)); -#else - return p; -#endif + template + static inline void free(T *ptr) noexcept + { + ptr->~T(); + ARENA::deallocate(ptr, sizeof(T)); + } + + template + static inline T * alloc(ARENA &arena, Args&&... args) + { + auto *mem = arena.allocate(alignof(T), sizeof(T)); + try + { + // NOLINTNEXTLINE(cppcoreguidelines-owning-memory) + return new (mem) T(std::forward(args)...); + } + catch (...) + { + arena.deallocate(mem, sizeof(T)); + throw; + } + } + + template + static inline void free(ARENA &arena, T *ptr) noexcept + { + ptr->~T(); + arena.deallocate(ptr, sizeof(T)); + } + } // namespace detail + + + + template + static inline + std::enable_if_t> + make_unique(Args&&... args) + { + using up_type = typename ARENA::template unique_ptr; + using deleter_type = typename ARENA::template deleter_type; + auto *mem = detail::alloc(std::forward(args)...); + return up_type(mem, deleter_type()); } - template - constexpr const T *assume_aligned_ptr(const T *p) noexcept + template + static inline + std::enable_if_t> + make_unique(Args&&... args) { - static_assert(ALIGN >= alignof(T), "Alignment must be greater or equal to alignof(T)"); - static_assert(is_pow2(ALIGN), "Alignment must be a power of 2"); -#if (PUSE_ALIGNED_HINTS) - return reinterpret_cast(__builtin_assume_aligned(p, ALIGN)); -#else - return p; -#endif + return make_unique(ARENA::instance(), std::forward(args)...); } + template + static inline + typename ARENA::template unique_ptr + make_unique(ARENA &arena, Args&&... args) + { + using up_type = typename ARENA::template unique_ptr; + using deleter_type = typename ARENA::template deleter_type; + auto *mem = detail::alloc(arena, std::forward(args)...); + return up_type(mem, deleter_type(&arena)); + } + + template + static inline + std::enable_if_t> + make_owned(Args&&... args) + { + using op_type = typename ARENA::template owned_ptr; + using deleter_type = typename ARENA::template deleter_type; + auto *mem = detail::alloc(std::forward(args)...); + return op_type(mem, true, deleter_type()); + } + + template + static inline + std::enable_if_t> + make_owned(Args&&... args) + { + return make_owned(ARENA::instance(), std::forward(args)...); + } + + template + static inline typename ARENA::template owned_ptr make_owned(ARENA &arena, Args&&... args) + { + using op_type = typename ARENA::template owned_ptr; + using deleter_type = typename ARENA::template deleter_type; + auto *mem = detail::alloc(arena, std::forward(args)...); + return op_type(mem, true, deleter_type(&arena)); + } + + template using aligned_allocator = aligned_arena::allocator_type; @@ -557,56 +592,71 @@ namespace plib { PDEFINE_HAS_MEMBER(has_align, align_size); - template - struct align_traits + template + struct align_traits_base { + static_assert(!has_align::value, "no align"); static constexpr const std::size_t align_size = alignof(std::max_align_t); static constexpr const std::size_t value_size = sizeof(typename T::value_type); static constexpr const std::size_t stride_size = lcm(align_size, value_size) / value_size; }; template - struct align_traits::value, void>> + struct align_traits_base { + static_assert(has_align::value, "no align"); static constexpr const std::size_t align_size = T::align_size; static constexpr const std::size_t value_size = sizeof(typename T::value_type); static constexpr const std::size_t stride_size = lcm(align_size, value_size) / value_size; }; - //============================================================ - // Aligned vector - //============================================================ + template + struct align_traits : public align_traits_base::value> + {}; - // FIXME: needs a separate file - template > - class aligned_vector : public std::vector + template + class paged_arena : public arena_base, true, true> { public: - using base = std::vector; - - using reference = typename base::reference; - using const_reference = typename base::const_reference; - using pointer = typename base::pointer; - using const_pointer = typename base::const_pointer; - using size_type = typename base::size_type; + paged_arena() + { + } - using base::base; + PCOPYASSIGNMOVE(paged_arena, delete) - base & as_base() noexcept { return *this; } - const base & as_base() const noexcept { return *this; } + ~paged_arena() = default; - constexpr reference operator[](size_type i) noexcept + static void *allocate(size_t align, size_t size) { - return assume_aligned_ptr(&(base::operator[](0)))[i]; + plib::unused_var(align); + //size = ((size + PAGESIZE - 1) / PAGESIZE) * PAGESIZE; + return arena().allocate(PAGESIZE, size); } - constexpr const_reference operator[](size_type i) const noexcept + static void deallocate(void *ptr, size_t size) noexcept { - return assume_aligned_ptr(&(base::operator[](0)))[i]; + //size = ((size + PAGESIZE - 1) / PAGESIZE) * PAGESIZE; + arena().deallocate(ptr, size); } - pointer data() noexcept { return assume_aligned_ptr(base::data()); } - const_pointer data() const noexcept { return assume_aligned_ptr(base::data()); } + bool operator ==(const paged_arena &rhs) const noexcept { return this == &rhs; } + + static BASEARENA &arena() noexcept { static BASEARENA m_arena; return m_arena; } + private: + }; + + //============================================================ + // Aligned vector + //============================================================ + + // FIXME: needs a separate file + template >//aligned_arena> + class aligned_vector : public std::vector> + { + public: + using base = std::vector>; + + using base::base; }; -- cgit v1.2.3