Utilities/interface/SoATuple.h

0001 #ifndef FWCore_Utilities_SoATuple_h
0002 #define FWCore_Utilities_SoATuple_h
0003 // -*- C++ -*-
0004 //
0005 // Package:     FWCore/Utilities
0006 // Class  :     SoATuple
0007 //
0008 /**\class SoATuple SoATuple.h "FWCore/Utilities/interface/SoATuple.h"
0009
0010  Description: Structure of Arrays Tuple
0011
0012  Usage:
0013     Often we want to group data which are related to one item and then group related items.
0014  This is often done by making a structure,Foo, to hold the data related to one item and then place
0015  the structure into a container (e.g. std::vector<Foo>). This is referred to as an 'Array of Structures'.
0016  However, this grouping can be inefficient if not all of the data about one item are used at the same
0017  time. So to access one data for one item will cause the CPU to retrieve nearby memory which is then
0018  not used. If the code is looking at the same data for multiple items this will lead to many data cache
0019  misses in the CPU.
0020
0021  A different grouping is to place the first data element for all items into one array, the second data
0022  element for all items into a second array, then so on. This is referred to as a 'Structure of Arrays'.
0023
0024  This class will take an arbitrary number of template arguments and it will group data of that argument
0025  type together in memory.
0026
0027 Example: Data about one item is represented by a double, int and bool
0028 \code
0029     edm::SoATuple<double,int, bool> s;
0030 \endcode
0031
0032 One can then push data into the collection. You must insert all data for each item.
0033 \code
0034     s.push_back(std::make_tuple(double{3.14},int{5},false));
0035     s.emplace_back(double{90.},int{0},true);
0036 \endcode
0037 It is best if you call 'reserve' before pushing or emplacing items into the container in order to
0038 minimize memory allocations.
0039
0040
0041 You get the data out by specify the 'ordinal' of the data element as well as the index
0042 \code
0043     double v = s.get<0>(1); //this return 90.
0044 \encode
0045
0046 It is possible to loop over a data element for all items in the collection
0047 \code
0048     for(auto it = s.begin<1>(), itEnd=s.end<1>(); it != itEnd; ++it) {
0049       std::cout<<*it<<" ";
0050     }
0051     //This returns '5 0 '
0052 \encode
0053
0054 This template arguments for this class are not limited to simple builtins, any type can be used:
0055 \code
0056     edm::SoATuple<std::string, ThreeVector> sComplex;
0057 \endcode
0058
0059 To help keep track of the purpose of the template arguments, we suggest using an enum to denote each one:
0060 \code
0061     enum {kPx,kPy,kPz};
0062     edm::SoATuple<double,double,double> s3Vecs;
0063     ...
0064     if(s.3Vecs.get<kPx>(i) > s.3Vecs.get<kPy>(i)) { ... }
0065 \endcode
0066
0067 A non-default alignment for a stored type can be specified by using the edm::Aligned<T,I> where I is an
0068  unsigned int value denoting the requested byte alignment. There is also a specialized version, edm::AlignedVec
0069  which has the proper alignment for SSE operations (16 byte aligned).
0070 \code
0071     edm::SoATuple<edm::Aligned<float,16>,edm::Aligned<float,16>,edm::Aligned<float,16>> vFloats;
0072 \endcode
0073 which is equivalent to
0074 \code
0075     edm::SoATuple<edm::AlignedVec<float>,edm::AlignedVec<float>,edm::AlignedVec<float>> vFloats;
0076 \endcode
0077
0078 Explicitly aligned types and defaultly aligned types can be freely mixed in any order within the template arguments.
0079
0080 */
0081 //
0082 // Original Author:  Chris Jones
0083 //         Created:  Tue, 16 Apr 2013 20:34:31 GMT
0084 //
0085
0086 // system include files
0087 #include <algorithm>
0088 #include <tuple>
0089 #include <cassert>
0090 #include <utility>
0091
0092 // user include files
0093 #include "FWCore/Utilities/interface/SoATupleHelper.h"
0094 #include "FWCore/Utilities/interface/GCCPrerequisite.h"
0095
0096 // forward declarations
0097
0098 namespace edm {
0099
0100   //The class Aligned is used to specify a non-default alignment for a class
0101   using edm::soahelper::Aligned;
0102
0103   //Proper alignment for doing vectorized operations on CPU
0104   template <typename T>
0105   using AlignedVec = Aligned<T, 16>;
0106
0107   template <typename... Args>
0108   class SoATuple {
0109   public:
0110     typedef typename std::tuple<Args...> element;
0111
0112     SoATuple() : m_size(0), m_reserved(0) {
0113       for (auto& v : m_values) {
0114         v = nullptr;
0115       }
0116     }
0117     SoATuple(const SoATuple<Args...>& iOther) : m_size(0), m_reserved(0) {
0118       for (auto& v : m_values) {
0119         v = nullptr;
0120       }
0121       reserve(iOther.m_size);
0122       soahelper::SoATupleHelper<sizeof...(Args), Args...>::copyToNew(
0123           static_cast<char*>(m_values[0]), iOther.m_size, m_reserved, iOther.m_values, m_values);
0124       m_size = iOther.m_size;
0125     }
0126
0127     SoATuple(SoATuple<Args...>&& iOther) : m_size(0), m_reserved(0) {
0128       for (auto& v : m_values) {
0129         v = nullptr;
0130       }
0131       this->swap(iOther);
0132     }
0133
0134     const SoATuple<Args...>& operator=(const SoATuple<Args...>& iRHS) {
0135       SoATuple<Args...> temp(iRHS);
0136       this->swap(temp);
0137       return *this;
0138     }
0139
0140     SoATuple<Args...>& operator=(SoATuple<Args...>&& iRHS) {
0141       SoATuple<Args...> temp(std::move(iRHS));
0142       this->swap(temp);
0143       return *this;
0144     }
0145
0146     ~SoATuple() {
0147       soahelper::SoATupleHelper<sizeof...(Args), Args...>::destroy(m_values, m_size);
0148       typedef std::aligned_storage<soahelper::SoATupleHelper<sizeof...(Args), Args...>::max_alignment,
0149                                    soahelper::SoATupleHelper<sizeof...(Args), Args...>::max_alignment>
0150           AlignedType;
0151
0152       delete[] static_cast<AlignedType*>(m_values[0]);
0153     }
0154
0155     // ---------- const member functions ---------------------
0156     size_t size() const { return m_size; }
0157     size_t capacity() const { return m_reserved; }
0158
0159     /** Returns const access to data element I of item iIndex */
0160     template <unsigned int I>
0161     typename soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type>::Type const& get(
0162         unsigned int iIndex) const {
0163       typedef typename soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type>::Type
0164           ReturnType;
0165       return *(static_cast<ReturnType const*>(m_values[I]) + iIndex);
0166     }
0167
0168     /** Returns the beginning of the container holding all Ith data elements*/
0169     template <unsigned int I>
0170     typename soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type>::Type const* begin()
0171         const {
0172       typedef soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type> Helper;
0173       typedef typename Helper::Type ReturnType;
0174 #if GCC_PREREQUISITE(4, 7, 0)
0175       return static_cast<ReturnType const*>(__builtin_assume_aligned(m_values[I], Helper::kAlignment));
0176 #else
0177       return static_cast<ReturnType const*>(m_values[I]);
0178 #endif
0179     }
0180     /** Returns the end of the container holding all Ith data elements*/
0181     template <unsigned int I>
0182     typename soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type>::Type const* end()
0183         const {
0184       typedef typename soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type>::Type
0185           ReturnType;
0186       return static_cast<ReturnType const*>(m_values[I]) + m_size;
0187     }
0188
0189     // ---------- member functions ---------------------------
0190     /** Makes sure to hold enough memory to contain at least iToSize entries. */
0191     void reserve(unsigned int iToSize) {
0192       if (iToSize > m_reserved) {
0193         changeSize(iToSize);
0194       }
0195     }
0196
0197     /** Shrinks the amount of memory used so as to only have just enough to hold all entries.*/
0198     void shrink_to_fit() {
0199       if (m_reserved > m_size) {
0200         changeSize(m_size);
0201       }
0202     }
0203
0204     /** Adds one entry to the end of the list. Memory grows as needed.*/
0205     void push_back(element const& values) {
0206       if (size() + 1 > capacity()) {
0207         reserve(size() * 2 + 1);
0208       }
0209       soahelper::SoATupleHelper<sizeof...(Args), Args...>::push_back(m_values, m_size, values);
0210       ++m_size;
0211     }
0212
0213     /** Adds one entry to the end of the list. The arguments are used to instantiate each data element in the order defined in the template arguments.*/
0214     template <typename... FArgs>
0215     void emplace_back(FArgs&&... values) {
0216       if (size() + 1 > capacity()) {
0217         reserve(size() * 2 + 1);
0218       }
0219       soahelper::SoATupleHelper<sizeof...(Args), Args...>::emplace_back(
0220           m_values, m_size, std::forward<FArgs>(values)...);
0221       ++m_size;
0222     }
0223
0224     /** Returns access to data element I of item iIndex */
0225     template <unsigned int I>
0226     typename soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type>::Type& get(
0227         unsigned int iIndex) {
0228       typedef typename soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type>::Type
0229           ReturnType;
0230       return *(static_cast<ReturnType*>(m_values[I]) + iIndex);
0231     }
0232
0233     /** Returns the beginning of the container holding all Ith data elements*/
0234     template <unsigned int I>
0235     typename soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type>::Type* begin() {
0236       typedef soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type> Helper;
0237       typedef typename Helper::Type ReturnType;
0238 #if GCC_PREREQUISITE(4, 7, 0)
0239       return static_cast<ReturnType*>(__builtin_assume_aligned(m_values[I], Helper::kAlignment));
0240 #else
0241       return static_cast<ReturnType*>(m_values[I]);
0242 #endif
0243     }
0244     /** Returns the end of the container holding all Ith data elements*/
0245     template <unsigned int I>
0246     typename soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type>::Type* end() {
0247       typedef typename soahelper::AlignmentHelper<typename std::tuple_element<I, std::tuple<Args...>>::type>::Type
0248           ReturnType;
0249       return static_cast<ReturnType*>(m_values[I]) + m_size;
0250     }
0251
0252     void swap(SoATuple<Args...>& iOther) {
0253       std::swap(m_size, iOther.m_size);
0254       std::swap(m_reserved, iOther.m_reserved);
0255       for (unsigned int i = 0; i < sizeof...(Args); ++i) {
0256         std::swap(m_values[i], iOther.m_values[i]);
0257       }
0258     }
0259
0260   private:
0261     void changeSize(unsigned int iToSize) {
0262       assert(m_size <= iToSize);
0263       const size_t memoryNeededInBytes = soahelper::SoATupleHelper<sizeof...(Args), Args...>::spaceNeededFor(iToSize);
0264       //align memory of the array to be on the strictest alignment boundary for any type in the Tuple
0265       // This is done by creating an array of a type that has that same alignment restriction and minimum size.
0266       // This has the draw back of possibly padding the array by one extra element if the memoryNeededInBytes is not
0267       // a strict multiple of max_alignment.
0268       // NOTE: using new char[...] would likely cause more padding based on C++11 5.3.4 paragraph 10 where it
0269       // says the alignment will be for the strictest requirement for an object whose size < size of array. So
0270       // if the array were for 64 bytes and the strictest requirement of any object was 8 bytes then the entire
0271       // char array would be aligned on an 8 byte boundary. However, if the SoATuple<char,char> only 1 byte alignment
0272       // is needed. The following algorithm would require only 1 byte alignment
0273       const std::size_t max_alignment = soahelper::SoATupleHelper<sizeof...(Args), Args...>::max_alignment;
0274       typedef std::aligned_storage<soahelper::SoATupleHelper<sizeof...(Args), Args...>::max_alignment,
0275                                    soahelper::SoATupleHelper<sizeof...(Args), Args...>::max_alignment>
0276           AlignedType;
0277       //If needed, pad the number of items by 1
0278       const size_t itemsNeeded = (memoryNeededInBytes + max_alignment - 1) / sizeof(AlignedType);
0279       char* newMemory = static_cast<char*>(static_cast<void*>(new AlignedType[itemsNeeded]));
0280       void* oldMemory = m_values[0];
0281       soahelper::SoATupleHelper<sizeof...(Args), Args...>::moveToNew(newMemory, m_size, iToSize, m_values);
0282       m_reserved = iToSize;
0283       delete[] static_cast<AlignedType*>(oldMemory);
0284     }
0285     // ---------- member data --------------------------------
0286     //Pointers to where each column starts in the shared memory array
0287     //m_values[0] also points to the beginning of the shared memory area
0288     void* m_values[sizeof...(Args)];
0289     size_t m_size;
0290     size_t m_reserved;
0291   };
0292 }  // namespace edm
0293
0294 #endif