Get rid of array::m_tss_used #28

Closed
Mortal opened this Issue Aug 27, 2012 · 4 comments

Comments

Projects
None yet
3 participants
Collaborator

Mortal commented Aug 27, 2012

We should get rid of the m_tss_used flag in array, as it seems like an unnecessary complexity. I have pushed commit 566e5a5 to a temporary branch. Is this the fix we want to use?

Collaborator

antialize commented Aug 27, 2012

It looks good, have you timed resize, with a non trivial copy constructor, in the two versions?

Collaborator

Mortal commented Aug 28, 2012

I discussed this issue with Jakob, and we conclude that m_tss_used is an acceptable complexity in the code. (Using Boost type traits and SFINAE is an added complexity in itself.)

We experimented with "placement new[]" in place of the default_initialize() for-loop, and indeed it is as fast as the current code that uses m_tss_used, but it turns out that placement new[] is flawed in its design, see http://stackoverflow.com/a/15948/1570972

Since the naïve for-loop makes array::resize(memory_size_type) around 10% slower than the code using the m_tss_used flag, we choose to trade complexity for a speed-up and do not merge the patch in this issue.

Mortal closed this Aug 28, 2012

Collaborator

Mortal commented Aug 28, 2012

For future reference (since I'm deleting the branch), the suggested patch (566e5a5) was the following:

commit 566e5a5ab8beed0d9961ceaea8ec7399fb32badb
Parent: 9496caa4cbd4cf8ad40e3ed21a5a1cdbc4388c4c
Author: Mathias Rav <rav@cs.au.dk>
Date:   Mon Aug 27 11:13:32 2012 +0200

    Always allocate array::m_elements using tpie::trivially_same_size

diff --git 9496caa/tpie/array.h 566e5a5/tpie/array.h
index 5604bbb..7c35c11 100644
--- 9496caa/tpie/array.h
+++ 566e5a5/tpie/array.h
@@ -29,6 +29,8 @@
 #include <boost/utility/enable_if.hpp>
 #include <tpie/memory.h>
 #include <tpie/array_view_base.h>
+#include <boost/type_traits.hpp>
+#include <tpie/tpie_log.h>

 namespace tpie {

@@ -349,14 +351,14 @@ public:
    /// \param s The number of elements in the array.
    /// \param value Each entry of the array is initialized with this value.
    ///////////////////////////////////////////////////////////////////////////
-   array_base(size_type s, const T & value): m_elements(0), m_size(0), m_tss_used(false) {resize(s, value);}
+   array_base(size_type s, const T & value): m_elements(0), m_size(0) {resize(s, value);}

    ///////////////////////////////////////////////////////////////////////////
    /// \brief Construct array of given size.
    ///
    /// \param s The number of elements in the array.
    ///////////////////////////////////////////////////////////////////////////
-   array_base(size_type s=0): m_elements(0), m_size(0), m_tss_used(false) {resize(s);}
+   array_base(size_type s=0): m_elements(0), m_size(0) {resize(s);}

    /////////////////////////////////////////////////////////
    /// \brief Construct a copy of another array.
@@ -365,7 +367,6 @@ public:
    array_base(const array_base & other): m_elements(0), m_size(other.m_size) {
        if (other.size() == 0) return;
        m_elements = m_size ? reinterpret_cast<T*>(tpie_new_array<trivial_same_size<T> >(m_size)) : 0;
-       m_tss_used = true;
        std::uninitialized_copy(other.m_elements+0, other.m_elements+m_size, m_elements+0);
    }   

@@ -390,7 +391,6 @@ public:
            m_size = size;

            m_elements = size ? reinterpret_cast<T*>(tpie_new_array<trivial_same_size<T> >(m_size)) : 0;
-           m_tss_used = true;

            // call copy constructors manually
            std::uninitialized_fill(m_elements+0, m_elements+m_size, elm);
@@ -405,7 +405,6 @@ public:
    void swap(array_base & other) {
        std::swap(m_elements, other.m_elements);
        std::swap(m_size, other.m_size);
-       std::swap(m_tss_used, other.m_tss_used);
    }

    ///////////////////////////////////////////////////////////////////////////
@@ -420,8 +419,8 @@ public:
    void resize(size_t s) {
        destruct_and_dealloc();
        m_size = s;
-       m_elements = m_size ? tpie_new_array<T>(m_size) : 0;
-       m_tss_used = false;
+       m_elements = m_size ? reinterpret_cast<T*>(tpie_new_array<trivial_same_size<T> >(m_size)) : 0;
+       default_initialize(m_elements);
    }

    ///////////////////////////////////////////////////////////////////////////
@@ -447,12 +446,6 @@ protected:

 private:
    inline void destruct_and_dealloc() {
-       if (!m_tss_used) {
-           // calls destructors
-           tpie_delete_array(m_elements, m_size);
-           return;
-       }
-
        // call destructors manually
        for (size_t i = 0; i < m_size; ++i) {
            m_elements[i].~T();
@@ -460,8 +453,22 @@ private:
        tpie_delete_array(reinterpret_cast<trivial_same_size<T>*>(m_elements), m_size);
    }

-   // did we allocate m_elements as a trivial_same_size<T> *?
-   bool m_tss_used;
+   template <typename U>
+   inline void
+   default_initialize(U *,
+                      typename boost::enable_if<boost::has_trivial_constructor<U> >::type * dummy = 0) {
+       unused(dummy);
+   }
+
+   template <typename U>
+   inline void
+   default_initialize(U * m_elements,
+                      typename boost::disable_if<boost::has_trivial_constructor<U> >::type * dummy = 0) {
+       unused(dummy);
+       for (memory_size_type i = 0; i < m_size; ++i) {
+           new (m_elements+i) T();
+       }
+   }
 };

 ///////////////////////////////////////////////////////////////////////////////
Owner

thomasmoelhave commented Aug 28, 2012

If there is a decent speed increase I guess it makes sense to keep it.
However, maybe you could put a bit about the rationale behind using it in
the comments? The file is already pretty well documented on the
interface-level but the actual implementation can be a bit hard to parse -
especially with this added complication.

On Tue, Aug 28, 2012 at 4:43 AM, Mathias Rav notifications@github.comwrote:

For future reference (since I'm deleting the branch), the suggested patch (
566e5a5 566e5a5) was the
following:

commit 566e5a5ab8beed0d9961ceaea8ec7399fb32badb
Parent: 9496caa
Author: Mathias Rav rav@cs.au.dk
Date: Mon Aug 27 11:13:32 2012 +0200

Always allocate array::m_elements using tpie::trivially_same_size

diff --git 9496caa/tpie/array.h 566e5a5/tpie/array.hindex 5604bbb..7c35c11 100644--- 9496caa/tpie/array.h+++ 566e5a5/tpie/array.h@@ -29,6 +29,8 @@
#include <boost/utility/enable_if.hpp>
#include <tpie/memory.h>
#include <tpie/array_view_base.h>+#include <boost/type_traits.hpp>+#include <tpie/tpie_log.h>

namespace tpie {
@@ -349,14 +351,14 @@ public:
/// \param s The number of elements in the array.
/// \param value Each entry of the array is initialized with this value.
///////////////////////////////////////////////////////////////////////////- array_base(size_type s, const T & value): m_elements(0), m_size(0), m_tss_used(false) {resize(s, value);}+ array_base(size_type s, const T & value): m_elements(0), m_size(0) {resize(s, value);}

///////////////////////////////////////////////////////////////////////////
/// \brief Construct array of given size.
///
/// \param s The number of elements in the array.
///////////////////////////////////////////////////////////////////////////-   array_base(size_type s=0): m_elements(0), m_size(0), m_tss_used(false) {resize(s);}+   array_base(size_type s=0): m_elements(0), m_size(0) {resize(s);}

/////////////////////////////////////////////////////////
/// \brief Construct a copy of another array.@@ -365,7 +367,6 @@ public:
array_base(const array_base & other): m_elements(0), m_size(other.m_size) {
    if (other.size() == 0) return;
    m_elements = m_size ? reinterpret_cast<T*>(tpie_new_array<trivial_same_size<T> >(m_size)) : 0;-       m_tss_used = true;
    std::uninitialized_copy(other.m_elements+0, other.m_elements+m_size, m_elements+0);
}

@@ -390,7 +391,6 @@ public:
m_size = size;

        m_elements = size ? reinterpret_cast<T*>(tpie_new_array<trivial_same_size<T> >(m_size)) : 0;-           m_tss_used = true;

        // call copy constructors manually
        std::uninitialized_fill(m_elements+0, m_elements+m_size, elm);@@ -405,7 +405,6 @@ public:
void swap(array_base & other) {
    std::swap(m_elements, other.m_elements);
    std::swap(m_size, other.m_size);-       std::swap(m_tss_used, other.m_tss_used);
}

///////////////////////////////////////////////////////////////////////////@@ -420,8 +419,8 @@ public:
void resize(size_t s) {
    destruct_and_dealloc();
    m_size = s;-       m_elements = m_size ? tpie_new_array<T>(m_size) : 0;-       m_tss_used = false;+       m_elements = m_size ? reinterpret_cast<T*>(tpie_new_array<trivial_same_size<T> >(m_size)) : 0;+       default_initialize(m_elements);
}

///////////////////////////////////////////////////////////////////////////@@ -447,12 +446,6 @@ protected:

private:
inline void destruct_and_dealloc() {- if (!m_tss_used) {- // calls destructors- tpie_delete_array(m_elements, m_size);- return;- }-
// call destructors manually
for (size_t i = 0; i < m_size; ++i) {
m_elements[i].~T();@@ -460,8 +453,22 @@ private:
tpie_delete_array(reinterpret_cast<trivial_same_size*>(m_elements), m_size);
}

  • // did we allocate m_elements as a trivial_same_size *?- bool m_tss_used;+ template + inline void+ default_initialize(U *,+ typename boost::enable_ifboost::has_trivial_constructor::type * dummy = 0) {+ unused(dummy);+ }++ template + inline void+ default_initialize(U * m_elements,+ typename boost::disable_ifboost::has_trivial_constructor::type * dummy = 0) {+ unused(dummy);+ for (memory_size_type i = 0; i < m_size; ++i) {+ new (m_elements+i) T();+ }+ }
    };

///////////////////////////////////////////////////////////////////////////////


Reply to this email directly or view it on GitHubhttps://github.com/thomasmoelhave/tpie/issues/28#issuecomment-8085041.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment