Reference documentation for deal.II version 9.1.1
\(\newcommand{\dealcoloneq}{\mathrel{\vcenter{:}}=}\)
aligned_vector.h
1 // ---------------------------------------------------------------------
2 //
3 // Copyright (C) 2011 - 2019 by the deal.II authors
4 //
5 // This file is part of the deal.II library.
6 //
7 // The deal.II library is free software; you can use it, redistribute
8 // it, and/or modify it under the terms of the GNU Lesser General
9 // Public License as published by the Free Software Foundation; either
10 // version 2.1 of the License, or (at your option) any later version.
11 // The full text of the license can be found in the file LICENSE.md at
12 // the top level directory of deal.II.
13 //
14 // ---------------------------------------------------------------------
15 
16 
17 #ifndef dealii_aligned_vector_h
18 #define dealii_aligned_vector_h
19 
20 #include <deal.II/base/config.h>
21 
22 #include <deal.II/base/exceptions.h>
23 #include <deal.II/base/memory_consumption.h>
24 #include <deal.II/base/parallel.h>
25 #include <deal.II/base/utilities.h>
26 
27 // boost::serialization::make_array used to be in array.hpp, but was
28 // moved to a different file in BOOST 1.64
29 #include <boost/version.hpp>
30 #if BOOST_VERSION >= 106400
31 # include <boost/serialization/array_wrapper.hpp>
32 #else
33 # include <boost/serialization/array.hpp>
34 #endif
35 #include <boost/serialization/split_member.hpp>
36 
37 #include <cstring>
38 #include <type_traits>
39 
40 
41 
42 DEAL_II_NAMESPACE_OPEN
43 
44 
60 template <class T>
62 {
63 public:
68  using value_type = T;
69  using pointer = value_type *;
70  using const_pointer = const value_type *;
71  using iterator = value_type *;
72  using const_iterator = const value_type *;
73  using reference = value_type &;
74  using const_reference = const value_type &;
75  using size_type = std::size_t;
76 
80  AlignedVector();
81 
88  AlignedVector(const size_type size, const T &init = T());
89 
94 
100  AlignedVector(const AlignedVector<T> &vec);
101 
106  AlignedVector(AlignedVector<T> &&vec) noexcept;
107 
113  AlignedVector &
114  operator=(const AlignedVector<T> &vec);
115 
119  AlignedVector &
120  operator=(AlignedVector<T> &&vec) noexcept;
121 
130  void
131  resize_fast(const size_type size);
132 
145  void
146  resize(const size_type size_in);
147 
163  void
164  resize(const size_type size_in, const T &init);
165 
174  void
175  reserve(const size_type size_alloc);
176 
181  void
182  clear();
183 
189  void
190  push_back(const T in_data);
191 
195  reference
196  back();
197 
201  const_reference
202  back() const;
203 
208  template <typename ForwardIterator>
209  void
210  insert_back(ForwardIterator begin, ForwardIterator end);
211 
221  void
222  fill();
223 
232  void
233  fill(const T &element);
234 
238  void
239  swap(AlignedVector<T> &vec);
240 
244  bool
245  empty() const;
246 
250  size_type
251  size() const;
252 
257  size_type
258  capacity() const;
259 
263  reference operator[](const size_type index);
264 
268  const_reference operator[](const size_type index) const;
269 
273  pointer
274  data();
275 
279  const_pointer
280  data() const;
281 
285  iterator
286  begin();
287 
291  iterator
292  end();
293 
297  const_iterator
298  begin() const;
299 
303  const_iterator
304  end() const;
305 
311  size_type
312  memory_consumption() const;
313 
318  template <class Archive>
319  void
320  save(Archive &ar, const unsigned int version) const;
321 
326  template <class Archive>
327  void
328  load(Archive &ar, const unsigned int version);
329 
330  BOOST_SERIALIZATION_SPLIT_MEMBER()
331 
332 private:
337 
342 
347 };
348 
349 
350 // ------------------------------- inline functions --------------------------
351 
357 namespace internal
358 {
374  template <typename T>
376  {
377  static const std::size_t minimum_parallel_grain_size =
378  160000 / sizeof(T) + 1;
379 
380  public:
390  AlignedVectorCopy(const T *const source_begin,
391  const T *const source_end,
392  T *const destination)
393  : source_(source_begin)
394  , destination_(destination)
395  {
396  Assert(source_end >= source_begin, ExcInternalError());
397  Assert(source_end == source_begin || destination != nullptr,
398  ExcInternalError());
399  const std::size_t size = source_end - source_begin;
400  if (size < minimum_parallel_grain_size)
401  AlignedVectorCopy::apply_to_subrange(0, size);
402  else
403  apply_parallel(0, size, minimum_parallel_grain_size);
404  }
405 
410  virtual void
411  apply_to_subrange(const std::size_t begin,
412  const std::size_t end) const override
413  {
414  if (end == begin)
415  return;
416 
417  // for classes trivial assignment can use memcpy. cast element to
418  // (void*) to silence compiler warning for virtual classes (they will
419  // never arrive here because they are non-trivial).
420 
421  if (std::is_trivial<T>::value == true)
422  std::memcpy(static_cast<void *>(destination_ + begin),
423  static_cast<const void *>(source_ + begin),
424  (end - begin) * sizeof(T));
425  else
426  for (std::size_t i = begin; i < end; ++i)
427  new (&destination_[i]) T(source_[i]);
428  }
429 
430  private:
431  const T *const source_;
432  T *const destination_;
433  };
434 
435 
441  template <typename T>
443  {
444  static const std::size_t minimum_parallel_grain_size =
445  160000 / sizeof(T) + 1;
446 
447  public:
457  AlignedVectorMove(T *const source_begin,
458  T *const source_end,
459  T *const destination)
460  : source_(source_begin)
461  , destination_(destination)
462  {
463  Assert(source_end >= source_begin, ExcInternalError());
464  Assert(source_end == source_begin || destination != nullptr,
465  ExcInternalError());
466  const std::size_t size = source_end - source_begin;
467  if (size < minimum_parallel_grain_size)
468  apply_to_subrange(0, size);
469  else
470  apply_parallel(0, size, minimum_parallel_grain_size);
471  }
472 
477  virtual void
478  apply_to_subrange(const std::size_t begin,
479  const std::size_t end) const override
480  {
481  if (end == begin)
482  return;
483 
484  // for classes trivial assignment can use memcpy. cast element to
485  // (void*) to silence compiler warning for virtual classes (they will
486  // never arrive here because they are non-trivial).
487 
488  if (std::is_trivial<T>::value == true)
489  std::memcpy(static_cast<void *>(destination_ + begin),
490  static_cast<void *>(source_ + begin),
491  (end - begin) * sizeof(T));
492  else
493  for (std::size_t i = begin; i < end; ++i)
494  {
495  // initialize memory (copy construct by placement new), and
496  // destruct the source
497  new (&destination_[i]) T(std::move(source_[i]));
498  source_[i].~T();
499  }
500  }
501 
502  private:
503  T *const source_;
504  T *const destination_;
505  };
506 
507 
519  template <typename T, bool initialize_memory>
521  {
522  static const std::size_t minimum_parallel_grain_size =
523  160000 / sizeof(T) + 1;
524 
525  public:
530  AlignedVectorSet(const std::size_t size,
531  const T & element,
532  T *const destination)
533  : element_(element)
534  , destination_(destination)
535  , trivial_element(false)
536  {
537  if (size == 0)
538  return;
539  Assert(destination != nullptr, ExcInternalError());
540 
541  // do not use memcmp for long double because on some systems it does not
542  // completely fill its memory and may lead to false positives in
543  // e.g. valgrind
544  if (std::is_trivial<T>::value == true &&
545  std::is_same<T, long double>::value == false)
546  {
547  const unsigned char zero[sizeof(T)] = {};
548  // cast element to (void*) to silence compiler warning for virtual
549  // classes (they will never arrive here because they are
550  // non-trivial).
551  if (std::memcmp(zero,
552  static_cast<const void *>(&element),
553  sizeof(T)) == 0)
554  trivial_element = true;
555  }
556  if (size < minimum_parallel_grain_size)
557  apply_to_subrange(0, size);
558  else
559  apply_parallel(0, size, minimum_parallel_grain_size);
560  }
561 
565  virtual void
566  apply_to_subrange(const std::size_t begin,
567  const std::size_t end) const override
568  {
569  // for classes with trivial assignment of zero can use memset. cast
570  // element to (void*) to silence compiler warning for virtual
571  // classes (they will never arrive here because they are
572  // non-trivial).
573  if (std::is_trivial<T>::value == true && trivial_element)
574  std::memset(static_cast<void *>(destination_ + begin),
575  0,
576  (end - begin) * sizeof(T));
577  else
578  copy_construct_or_assign(
579  begin, end, std::integral_constant<bool, initialize_memory>());
580  }
581 
582  private:
583  const T & element_;
584  mutable T *destination_;
585  bool trivial_element;
586 
587  // copy assignment operation
588  void
589  copy_construct_or_assign(const std::size_t begin,
590  const std::size_t end,
591  std::integral_constant<bool, false>) const
592  {
593  for (std::size_t i = begin; i < end; ++i)
594  destination_[i] = element_;
595  }
596 
597  // copy constructor (memory initialization)
598  void
599  copy_construct_or_assign(const std::size_t begin,
600  const std::size_t end,
601  std::integral_constant<bool, true>) const
602  {
603  for (std::size_t i = begin; i < end; ++i)
604  new (&destination_[i]) T(element_);
605  }
606  };
607 
608 
609 
621  template <typename T, bool initialize_memory>
623  {
624  static const std::size_t minimum_parallel_grain_size =
625  160000 / sizeof(T) + 1;
626 
627  public:
632  AlignedVectorDefaultInitialize(const std::size_t size, T *const destination)
633  : destination_(destination)
634  {
635  if (size == 0)
636  return;
637  Assert(destination != nullptr, ExcInternalError());
638 
639  if (size < minimum_parallel_grain_size)
640  apply_to_subrange(0, size);
641  else
642  apply_parallel(0, size, minimum_parallel_grain_size);
643  }
644 
648  virtual void
649  apply_to_subrange(const std::size_t begin,
650  const std::size_t end) const override
651  {
652  // for classes with trivial assignment of zero can use memset. cast
653  // element to (void*) to silence compiler warning for virtual
654  // classes (they will never arrive here because they are
655  // non-trivial).
656  if (std::is_trivial<T>::value == true)
657  std::memset(static_cast<void *>(destination_ + begin),
658  0,
659  (end - begin) * sizeof(T));
660  else
661  default_construct_or_assign(
662  begin, end, std::integral_constant<bool, initialize_memory>());
663  }
664 
665  private:
666  mutable T *destination_;
667 
668  // copy assignment operation
669  void
670  default_construct_or_assign(const std::size_t begin,
671  const std::size_t end,
672  std::integral_constant<bool, false>) const
673  {
674  for (std::size_t i = begin; i < end; ++i)
675  destination_[i] = std::move(T());
676  }
677 
678  // copy constructor (memory initialization)
679  void
680  default_construct_or_assign(const std::size_t begin,
681  const std::size_t end,
682  std::integral_constant<bool, true>) const
683  {
684  for (std::size_t i = begin; i < end; ++i)
685  new (&destination_[i]) T;
686  }
687  };
688 
689 } // end of namespace internal
690 
691 
692 #ifndef DOXYGEN
693 
694 
695 template <class T>
697  : data_begin(nullptr)
698  , data_end(nullptr)
699  , allocated_end(nullptr)
700 {}
701 
702 
703 
704 template <class T>
705 inline AlignedVector<T>::AlignedVector(const size_type size, const T &init)
706  : data_begin(nullptr)
707  , data_end(nullptr)
708  , allocated_end(nullptr)
709 {
710  if (size > 0)
711  resize(size, init);
712 }
713 
714 
715 
716 template <class T>
718 {
719  clear();
720 }
721 
722 
723 
724 template <class T>
726  : data_begin(nullptr)
727  , data_end(nullptr)
728  , allocated_end(nullptr)
729 {
730  // copy the data from vec
731  reserve(vec.data_end - vec.data_begin);
732  data_end = allocated_end;
733  internal::AlignedVectorCopy<T>(vec.data_begin, vec.data_end, data_begin);
734 }
735 
736 
737 
738 template <class T>
740  : data_begin(vec.data_begin)
741  , data_end(vec.data_end)
742  , allocated_end(vec.allocated_end)
743 {
744  vec.data_begin = nullptr;
745  vec.data_end = nullptr;
746  vec.allocated_end = nullptr;
747 }
748 
749 
750 
751 template <class T>
752 inline AlignedVector<T> &
754 {
755  resize(0);
756  resize_fast(vec.data_end - vec.data_begin);
757  internal::AlignedVectorCopy<T>(vec.data_begin, vec.data_end, data_begin);
758  return *this;
759 }
760 
761 
762 
763 template <class T>
764 inline AlignedVector<T> &
766 {
767  clear();
768 
769  data_begin = vec.data_begin;
770  data_end = vec.data_end;
771  allocated_end = vec.allocated_end;
772 
773  vec.data_begin = nullptr;
774  vec.data_end = nullptr;
775  vec.allocated_end = nullptr;
776 
777  return *this;
778 }
779 
780 
781 
782 template <class T>
783 inline void
784 AlignedVector<T>::resize_fast(const size_type size_in)
785 {
786  const size_type old_size = size();
787  if (std::is_trivial<T>::value == false && size_in < old_size)
788  {
789  // call destructor on fields that are released. doing it backward
790  // releases the elements in reverse order as compared to how they were
791  // created
792  while (data_end != data_begin + size_in)
793  (--data_end)->~T();
794  }
795  reserve(size_in);
796  data_end = data_begin + size_in;
797 
798  // need to still set the values in case the class is non-trivial because
799  // virtual classes etc. need to run their (default) constructor
800  if (std::is_trivial<T>::value == false && size_in > old_size)
802  size_in - old_size, data_begin + old_size);
803 }
804 
805 
806 
807 template <class T>
808 inline void
809 AlignedVector<T>::resize(const size_type size_in)
810 {
811  const size_type old_size = size();
812  if (std::is_trivial<T>::value == false && size_in < old_size)
813  {
814  // call destructor on fields that are released. doing it backward
815  // releases the elements in reverse order as compared to how they were
816  // created
817  while (data_end != data_begin + size_in)
818  (--data_end)->~T();
819  }
820  reserve(size_in);
821  data_end = data_begin + size_in;
822 
823  // finally set the desired init values
824  if (size_in > old_size)
826  size_in - old_size, data_begin + old_size);
827 }
828 
829 
830 
831 template <class T>
832 inline void
833 AlignedVector<T>::resize(const size_type size_in, const T &init)
834 {
835  const size_type old_size = size();
836  if (std::is_trivial<T>::value == false && size_in < old_size)
837  {
838  // call destructor on fields that are released. doing it backward
839  // releases the elements in reverse order as compared to how they were
840  // created
841  while (data_end != data_begin + size_in)
842  (--data_end)->~T();
843  }
844  reserve(size_in);
845  data_end = data_begin + size_in;
846 
847  // finally set the desired init values
848  if (size_in > old_size)
849  ::internal::AlignedVectorSet<T, true>(size_in - old_size,
850  init,
851  data_begin + old_size);
852 }
853 
854 
855 
856 template <class T>
857 inline void
858 AlignedVector<T>::reserve(const size_type size_alloc)
859 {
860  const size_type old_size = data_end - data_begin;
861  const size_type allocated_size = allocated_end - data_begin;
862  if (size_alloc > allocated_size)
863  {
864  // if we continuously increase the size of the vector, we might be
865  // reallocating a lot of times. therefore, try to increase the size more
866  // aggressively
867  size_type new_size = size_alloc;
868  if (size_alloc < (2 * allocated_size))
869  new_size = 2 * allocated_size;
870 
871  const size_type size_actual_allocate = new_size * sizeof(T);
872 
873  // allocate and align along 64-byte boundaries (this is enough for all
874  // levels of vectorization currently supported by deal.II)
875  T *new_data;
876  Utilities::System::posix_memalign(reinterpret_cast<void **>(&new_data),
877  64,
878  size_actual_allocate);
879 
880  // copy data in case there was some content before and release the old
881  // memory with the function corresponding to the one used for allocating
882  std::swap(data_begin, new_data);
883  data_end = data_begin + old_size;
884  allocated_end = data_begin + new_size;
885  if (data_end != data_begin)
886  {
888  new_data + old_size,
889  data_begin);
890  free(new_data);
891  }
892  else
893  Assert(new_data == nullptr, ExcInternalError());
894  }
895  else if (size_alloc == 0)
896  clear();
897 }
898 
899 
900 
901 template <class T>
902 inline void
904 {
905  if (data_begin != nullptr)
906  {
907  if (std::is_trivial<T>::value == false)
908  while (data_end != data_begin)
909  (--data_end)->~T();
910 
911  free(data_begin);
912  }
913  data_begin = nullptr;
914  data_end = nullptr;
915  allocated_end = nullptr;
916 }
917 
918 
919 
920 template <class T>
921 inline void
922 AlignedVector<T>::push_back(const T in_data)
923 {
924  Assert(data_end <= allocated_end, ExcInternalError());
925  if (data_end == allocated_end)
926  reserve(std::max(2 * capacity(), static_cast<size_type>(16)));
927  if (std::is_trivial<T>::value == false)
928  new (data_end++) T(in_data);
929  else
930  *data_end++ = in_data;
931 }
932 
933 
934 
935 template <class T>
936 inline typename AlignedVector<T>::reference
938 {
939  AssertIndexRange(0, size());
940  T *field = data_end - 1;
941  return *field;
942 }
943 
944 
945 
946 template <class T>
947 inline typename AlignedVector<T>::const_reference
949 {
950  AssertIndexRange(0, size());
951  const T *field = data_end - 1;
952  return *field;
953 }
954 
955 
956 
957 template <class T>
958 template <typename ForwardIterator>
959 inline void
960 AlignedVector<T>::insert_back(ForwardIterator begin, ForwardIterator end)
961 {
962  const unsigned int old_size = size();
963  reserve(old_size + (end - begin));
964  for (; begin != end; ++begin, ++data_end)
965  {
966  if (std::is_trivial<T>::value == false)
967  new (data_end) T;
968  *data_end = *begin;
969  }
970 }
971 
972 
973 
974 template <class T>
975 inline void
977 {
979  data_begin);
980 }
981 
982 
983 
984 template <class T>
985 inline void
986 AlignedVector<T>::fill(const T &value)
987 {
988  ::internal::AlignedVectorSet<T, false>(size(), value, data_begin);
989 }
990 
991 
992 
993 template <class T>
994 inline void
996 {
997  std::swap(data_begin, vec.data_begin);
998  std::swap(data_end, vec.data_end);
999  std::swap(allocated_end, vec.allocated_end);
1000 }
1001 
1002 
1003 
1004 template <class T>
1005 inline bool
1007 {
1008  return data_end == data_begin;
1009 }
1010 
1011 
1012 
1013 template <class T>
1014 inline typename AlignedVector<T>::size_type
1015 AlignedVector<T>::size() const
1016 {
1017  return data_end - data_begin;
1018 }
1019 
1020 
1021 
1022 template <class T>
1023 inline typename AlignedVector<T>::size_type
1025 {
1026  return allocated_end - data_begin;
1027 }
1028 
1029 
1030 
1031 template <class T>
1032 inline typename AlignedVector<T>::reference AlignedVector<T>::
1033  operator[](const size_type index)
1034 {
1035  AssertIndexRange(index, size());
1036  return data_begin[index];
1037 }
1038 
1039 
1040 
1041 template <class T>
1042 inline typename AlignedVector<T>::const_reference AlignedVector<T>::
1043  operator[](const size_type index) const
1044 {
1045  AssertIndexRange(index, size());
1046  return data_begin[index];
1047 }
1048 
1049 
1050 
1051 template <typename T>
1052 inline typename AlignedVector<T>::pointer
1054 {
1055  return data_begin;
1056 }
1057 
1058 
1059 
1060 template <typename T>
1061 inline typename AlignedVector<T>::const_pointer
1062 AlignedVector<T>::data() const
1063 {
1064  return data_begin;
1065 }
1066 
1067 
1068 
1069 template <class T>
1070 inline typename AlignedVector<T>::iterator
1072 {
1073  return data_begin;
1074 }
1075 
1076 
1077 
1078 template <class T>
1079 inline typename AlignedVector<T>::iterator
1081 {
1082  return data_end;
1083 }
1084 
1085 
1086 
1087 template <class T>
1088 inline typename AlignedVector<T>::const_iterator
1090 {
1091  return data_begin;
1092 }
1093 
1094 
1095 
1096 template <class T>
1097 inline typename AlignedVector<T>::const_iterator
1098 AlignedVector<T>::end() const
1099 {
1100  return data_end;
1101 }
1102 
1103 
1104 
1105 template <class T>
1106 template <class Archive>
1107 inline void
1108 AlignedVector<T>::save(Archive &ar, const unsigned int) const
1109 {
1110  size_type vec_size(size());
1111  ar & vec_size;
1112  if (vec_size > 0)
1113  ar &boost::serialization::make_array(data_begin, vec_size);
1114 }
1115 
1116 
1117 
1118 template <class T>
1119 template <class Archive>
1120 inline void
1121 AlignedVector<T>::load(Archive &ar, const unsigned int)
1122 {
1123  size_type vec_size = 0;
1124  ar & vec_size;
1125 
1126  if (vec_size > 0)
1127  {
1128  reserve(vec_size);
1129  ar &boost::serialization::make_array(data_begin, vec_size);
1130  data_end = data_begin + vec_size;
1131  }
1132 }
1133 
1134 
1135 
1136 template <class T>
1137 inline typename AlignedVector<T>::size_type
1139 {
1140  size_type memory = sizeof(*this);
1141  for (const T *t = data_begin; t != data_end; ++t)
1142  memory += ::MemoryConsumption::memory_consumption(*t);
1143  memory += sizeof(T) * (allocated_end - data_end);
1144  return memory;
1145 }
1146 
1147 
1148 #endif // ifndef DOXYGEN
1149 
1150 
1156 template <class T>
1157 bool
1159 {
1160  if (lhs.size() != rhs.size())
1161  return false;
1162  for (typename AlignedVector<T>::const_iterator lit = lhs.begin(),
1163  rit = rhs.begin();
1164  lit != lhs.end();
1165  ++lit, ++rit)
1166  if (*lit != *rit)
1167  return false;
1168  return true;
1169 }
1170 
1171 
1172 
1178 template <class T>
1179 bool
1181 {
1182  return !(operator==(lhs, rhs));
1183 }
1184 
1185 
1186 DEAL_II_NAMESPACE_CLOSE
1187 
1188 #endif
void posix_memalign(void **memptr, std::size_t alignment, std::size_t size)
Definition: utilities.cc:1023
virtual void apply_to_subrange(const std::size_t begin, const std::size_t end) const override
virtual void apply_to_subrange(const std::size_t begin, const std::size_t end) const override
#define AssertIndexRange(index, range)
Definition: exceptions.h:1637
pointer data()
void load(Archive &ar, const unsigned int version)
AlignedVector & operator=(const AlignedVector< T > &vec)
virtual void apply_to_subrange(const std::size_t begin, const std::size_t end) const override
void reserve(const size_type size_alloc)
void push_back(const T in_data)
void resize(const size_type size_in)
reference operator[](const size_type index)
typename VectorType::value_type value_type
bool operator==(const AlignedVector< T > &lhs, const AlignedVector< T > &rhs)
#define Assert(cond, exc)
Definition: exceptions.h:1407
void insert_back(ForwardIterator begin, ForwardIterator end)
size_type memory_consumption() const
void swap(Vector< Number > &u, Vector< Number > &v)
Definition: vector.h:1376
void swap(AlignedVector< T > &vec)
void resize_fast(const size_type size)
void save(Archive &ar, const unsigned int version) const
virtual void apply_to_subrange(const std::size_t begin, const std::size_t end) const override
iterator end()
AlignedVectorMove(T *const source_begin, T *const source_end, T *const destination)
AlignedVectorCopy(const T *const source_begin, const T *const source_end, T *const destination)
iterator begin()
AlignedVectorSet(const std::size_t size, const T &element, T *const destination)
size_type size() const
bool operator!=(const AlignedVector< T > &lhs, const AlignedVector< T > &rhs)
AlignedVectorDefaultInitialize(const std::size_t size, T *const destination)
void free(T *&pointer)
Definition: cuda.h:96
bool empty() const
size_type capacity() const
std::enable_if< std::is_fundamental< T >::value, std::size_t >::type memory_consumption(const T &t)
reference back()
static ::ExceptionBase & ExcInternalError()