5

我想要做什么：我需要以块形式存储单元格数据，即

*cell_member1[cell0] .. cell_member1[cellN] ... cell_memberM[cell0] .. cell_memberM[cellN]*

然后我需要有效地访问这些数据，如果可能的话，使用一个好的语法。如果我可以轻松地定义要存储的数据，那就太好了，即通过将具有成员的对象定义为我想要存储的数据并将其传递给为我做所有事情的“魔法”。

动机：为什么我需要这样做？缓存垃圾。在某些内部循环中，仅访问对象的某些成员。用未使用的内存浪费一半的缓存行不是我的应用程序的选择。我可以将指针存储在指向某个顺序内存区域的对象中。这会浪费内存并迫使我在该区域使用不同的语法。

我目前是如何做的：我有一个表格的容器：

template<class T> struct Container {
  char* data;
  Container(const int n) {
    data = new char[n*T::spaceRequirements()]; //< Data stored "block-wise"
    new(data) typename T::Flags[n]; //< Flags stored "cell-wise"
  }
  /// Destructor ommited for briefness.
};

我在其中存储 T 类型的某些单元格的数据。每个单元格需要一些标志，现在我正在使用 std::bitset 来存储它们，这意味着我需要以单元格形式存储这些位集：

*cell_member1[cell0] ... cell_memberM[cell0] ... cell_member1[cellN] .. cell_memberM[cellN]*

我正在描述每个单元格需要在以下类中存储多少数据，该类还提供对数据的访问：

template<int nd> struct CellAccessor {
  /// Cell flags are stored cell-wise:
  typedef std::bitset<64> Flags;
  enum { DELETE = 0, ///< Cell marked for deletion
         REFINE = 1 ///< Cell marked for refinement
         //...
  }; ///< Enum for the flags.
  static inline Flags& flags(const int cellId) {
    return *reinterpret_cast<Flags*>(data + sizeof(Flags)*cellId); }
  template<int pId> static inline Flags::reference flags(const int cellId) {
    return flags(cellId)[pId]; } //< Cell-wise access to the properties

  /// The rest of the data is stored block-wise:
  static inline int& order(const int cellId) { ///< One int field.
    return *reinterpret_cast<int*>
        (data + maxNoCells*sizeof(Flags) + sizeof(int)*cellId);}

  /// Coordinate vector with nd components:
  static inline double& coordinates(const int cellId, const int i) {
    return *reinterpret_cast<double*>
        (data + maxNoCells*(sizeof(Flags)+sizeof(int))
         + maxNoCells*i*sizeof(double) + sizeof(double)*cellId); }
  template<int i> static inline double& coordinates(const int cellId) {
    return *reinterpret_cast<double*>
        (data +maxNoCells*(sizeof(Flags)+sizeof(int)+i*sizeof(double))
         + sizeof(double)*cellId); }

  /// Total amount of memory to allocate per cell: (used by Container)
  static inline int spaceRequirements() { return
        sizeof(Flags) // Flags
        + sizeof(int) // order
        + nd*sizeof(double) // coordinates
        ;}

  /// Constructor gets pointer to the beginning of the container 
  /// and the offset for the member variables:
  CellAccessor(char* d, int n){data = d; maxNoCells = n;}
 private:
  static char* data;  ///< Pointer to the beginning of the container.
  static int maxNoCells;  ///< Cell offset for the member variables.
};
template<int nd> char* CellAccessor<nd>::data = nullptr;
template<int nd> int CellAccessor<nd>::maxNoCells = 0;

我像这样使用它：

int main() {
  int maxNoCells = 10000;   ///< Maximum number of cells (=cell offset).
  typedef CellAccessor<2> A;
  Container< A > cellData(maxNoCells);  ///< Allocate cell data.
  A cells(cellData.data,maxNoCells);  ///< Provides access to cell data.

  for(int i = 0; i < maxNoCells; ++i){
    cells.flags<A::DELETE>(i) = i%2==0 ? true : false;
    cells.flags<A::REFINE>(i) = i%2==0 ? false : true;
    cells.coordinates(i,0) = i;
    cells.coordinates<1>(i) = -((double)i);
    cells.order(i) = 2;
  }
}

优点：

  • 数据是逐块形式的，这正是我所需要的。

  • 语法没问题。

问题：

  • 我的课程做的太多了：为用户提供对数据的访问，提供需要为容器存储多少数据，提供数据应该如何移动/复制/交换我的数据结构（它们是树...... )...

  • 我不能使用没有迭代器的 STL 算法。我通过让迭代器存储单元索引并在其中重新实现 CellAccessor 类来实现迭代器（糟糕！干！）。

  • Bitset 仍以单元格形式存储。我可以为我的块数据结构重新实现位集......

  • data 和 maxNoCells 是静态变量，但如果需要，我可以将它们设为普通成员变量。

问题：是否有任何有效的方法以块形式存储“对象”（或我们在概念上理解的对象）并访问它们，就好像它们存储在诸如向量之类的标准容器中一样？

4

3 回答 3

3

你想要的是一种“基于列”的内存访问风格

您可以使用自己的列类型轻松实现它std::vector，或者使用自己的底层内存管理创建自己的“列”类型 - 但std::vector应该可以正常工作

现在，一旦您有了列类型，就可以创建“TABLE”类型。

在某种程度上，您的表 cab 只是向量的向量。您当然可以将其包装起来以获得更好看的访问器（如果您想先按行（对象）访问，然后按列（属性）访问。

这是我认为最好的通用方法。

即使在您的特定情况下-由于您想使用位长标志来节省内存，正如 Bart van Ingen Schenau 所提到的，您可以使用 avector<bool>所以一般方法是

于 2012-11-09T19:50:00.933 回答
0

不确定是否正确理解了这个问题。看起来您正在尝试在顺序字节数组中分配数据。为什么？但无论如何你都可以通过使用数组来做到这一点：

class Cell {
   std::bitset<64> flags;
   int order;
   double coordinates[2];
}

int main() {
   const int maxNoCells = 10000;
   Cell cells[maxNoCells];

   for(int i = 0; i < maxNoCells; i++) {
       cells[i].flags = ...;
       cells[i].coordinates[0] = i;
       cells[i].coordinates[1] = -i;
       cells[i].order=2;
   }
}

如果需要，然后将其转换为 (char *) 单元格。您的类将在连续的内存条中以分段方式分配。您可以将其用于读/写/网络。唯一的问题是您必须注意 32/64 位对齐，特别是如果它在不同架构之间共享。

这是另一个版本，如果您坚持在单独的循环中使用不同的字段，它会更好地进行缓存：

template<int size>
class CellAccessor {
    std::bitset<64> flags[size];
    int order[size];
    double coordinates[size][2];
 public:
    std::bitset<64> &getFlags(int id) {
        return flags[id];
    }
    int &getOrder(int id) {
        return order[id];
    }
    ...
 }


main() {

    CellAccessor<10000> ca;

    for(...i++) {
        ca.getOrder(i) = 2;
        ca.getCoordinates(i)[0] = i;
        ...
    }
 }
于 2012-11-08T20:43:53.250 回答
0

我会使用并行数组来满足要求：

template <int nd>
class CellAccessor {
public:
    enum { DELETE = 0, ///< Cell marked for deletion
           REFINE = 1, ///< Cell marked for refinement
           //...
           NUM_FLAGS
    }; ///< Enum for the flags.
    CellAccessor(int numCells) {
        for (int i=0; i<NUM_FLAGS; i++) { m_flags[i] = new bool[numCells]; }
        m_order = new int[numCells];
        for (int i=0; i<nd; i++) { m_coordinates[i] = new double[numCells]; }
    }
    // Destructor, copy-constructor & assignment operator omitted for brevity

    template<int F> inline bool& flags(const int cellId) {
        return m_flags[F][cellId]; }
    inline bool& flags(const int cellId, int flag) {
        return m_flags[flag][cellId]; }
    inline int& order(const int cellId) {
        return m_order[cellId]; }
    template<int i> inline double& coordinates(const int cellId) {
        return m_coordinates[i][cellId]; }
    inline double& coordinates(const int cellId, int i) {
        return m_coordinates[i][cellId]; }

private:
    bool* m_flags[NUM_FLAGS];
    int*  m_order;
    double* m_coordinates[nd];
};
于 2012-11-08T22:00:51.890 回答