flatk

Flat layout abstraction toolkit.

此库定义了组织扁平有序数据集合（如 Vec 和 slice）到有意义结构的低级原语，而无需克隆数据。

更具体地说，flatk 提供了一些核心的可组合类型，旨在从现有数据构建更复杂的数据结构

• UniChunked：将集合细分为若干个大小均匀（在编译时或运行时）的连续组。例如，如果我们有一个表示3D位置的浮点数的 Vec，我们可能希望将它们解释为三元组

  use flatk::Chunked3;
  
  let pos_data = vec![0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 1.0, 0.0];
  
  let pos = Chunked3::from_flat(pos_data);
  
  assert_eq!(pos[0], [0.0; 3]);
  assert_eq!(pos[1], [1.0; 3]);
  assert_eq!(pos[2], [0.0, 1.0, 0.0]);
  

• Chunked：将集合细分为若干个非结构化（非均匀）的组。例如，我们可能有一个存储在 Vec 中的非均匀节点分组，它可以表示一个有向图

  use flatk::Chunked;
  
  let neighbours = vec![1, 2, 0, 1, 0, 1, 2];
  
  let neigh = Chunked::from_sizes(vec![1,2,1,3], neighbours);
  
  assert_eq!(&neigh[0][..], &[1][..]);
  assert_eq!(&neigh[1][..], &[2, 0][..]);
  assert_eq!(&neigh[2][..], &[1][..]);
  assert_eq!(&neigh[3][..], &[0, 1, 2][..]);
  

  在这里，neigh 定义了以下图

  0<--->1<--->2
  ^     ^     ^
   \    |    /
    \   |   /
     \  |  /
      \ | /
       \|/
        3
  

• Select：从给定的随机访问集合中按顺序选择（可替换）的元素。这通常通过表示原始数据集合索引的 Vec<usize> 实现。

  例如，一个人可能希望从棋盘游戏中选择棋子

  use flatk::Select;
  
  let pieces = vec!["Pawn", "Knight", "Bishop", "Rook", "Queen", "King"];
  
  let white_pieces = Select::new(vec![3, 1, 2, 5, 4, 2, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0], pieces.as_slice());
  let black_pieces = Select::new(vec![0, 0, 0, 0, 0, 0, 0, 0, 3, 1, 2, 5, 4, 2, 1, 3], pieces.as_slice());
  
  assert_eq!(white_pieces[0], "Rook");
  assert_eq!(white_pieces[4], "Queen");
  assert_eq!(black_pieces[0], "Pawn");
  assert_eq!(black_pieces[11], "King");
  

• Subset：类似于 Select，但 Subset 强制无序选择且不替换。

  例如，我们可以从一副牌中抽取一手牌

  use flatk::{Subset, Get, View};
  
  let rank = vec!["Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King"];
  let suit = vec!["Clubs", "Diamonds", "Hearts", "Spades"];
  
  // Natural handling of structure of arrays (SoA) style data.
  let deck: (Vec<_>, Vec<_>) = (
      rank.into_iter().cycle().take(52).collect(),
      suit.into_iter().cycle().take(52).collect()
  );
  
  let hand = Subset::from_indices(vec![4, 19, 23, 1, 0, 5], deck);
  let hand_view = hand.view();
  assert_eq!(hand_view.at(0), (&"Ace", &"Clubs"));
  assert_eq!(hand_view.at(1), (&"2", &"Diamonds"));
  assert_eq!(hand_view.at(2), (&"5", &"Clubs"));
  assert_eq!(hand_view.at(3), (&"6", &"Diamonds"));
  assert_eq!(hand_view.at(4), (&"7", &"Spades"));
  assert_eq!(hand_view.at(5), (&"Jack", &"Spades"));
  

• Sparse：将稀疏数据分配到另一个集合。实际上，此类型将另一个数据集附加到 Select 项。

  例如，我们可以通过将值分配给一组索引来表示稀疏向量

  use flatk::{Sparse, Get, View};
  
  let values = vec![1.0, 2.0, 3.0, 4.0];
  let sparse_vector = Sparse::from_dim(vec![0,5,10,100], 1000, values);
  let sparse_vector_view = sparse_vector.view();
  
  assert_eq!(sparse_vector_view.at(0), (0, &1.0));
  assert_eq!(sparse_vector_view.at(1), (5, &2.0));
  assert_eq!(sparse_vector_view.at(2), (10, &3.0));
  assert_eq!(sparse_vector_view.at(3), (100, &4.0));
  assert_eq!(sparse_vector_view.selection.target, ..1000);
  

  在这种情况下，目标集合只是范围 0..1000，然而在一般情况下，这可以是任何数据集，这使得 Sparse 成为一种一对一映射或无交源和目标节点集的有向图的实现。

目标

目前，这个库的目标是提供用于组织大型数据数组的实用原语，具有以下功能

• 组合性，
• 迭代，
• 随机访问（索引）

一个激励示例

假设我们想构建一个3x3密集块矩阵的稀疏矩阵。为了激励我们为什么可能想要这样做，我们可以评估一个常见的替代方法。一个人可能会选择使用现成的稀疏矩阵，如压缩稀疏行（CSR）矩阵，这会将3x3块的价值重新分配到值数组中的非本地位置。这可能会带来性能影响，例如，在计算矩阵乘法时。此外，标准CSR矩阵将需要比等效块CSR（BCSR）矩阵多迭代9倍。因此，让我们通过使用传统的Rust和我们的原语类型来定义BCSR矩阵的过程来进行说明。

压缩稀疏行结构由一个动态大小的行数组和一个动态大小的行元素数组组成，以及相应的列索引。在传统的Rust中，我们可能写成 Vec<Vec<(usize, T)>>，其中 usize 是列索引，T 是一个元素类型，如 f32。这种类型在行之间失去了局部性，并为每一行引入了额外的间接引用，以及数组或结构（AoS）类型（例如，缺乏自动SIMD优化）的其他问题。为了解决这个问题，通常会使用类似以下类型的SoA类型：

struct CSR<T> {
    column_indices: Vec<usize>,
    offsets: Vec<usize>,
    data: Vec<T>,
}

其中，offsets 表示每一行的开始和结束位置，column_indices 和 data 是每一行中存储连续的列索引和元素值。这也意味着我们必须编写额外的代码来确保 offsets 是有效的（边界和单调性检查），并且在构建算法时，我们必须有意识地维护这些不变性。要构建等效的BCSR矩阵，可以将 T 替换为一个矩阵类型。

在几何处理管道中，维护偏移的模式对于实际上是两个嵌套的Vec来说非常常见。这种机制由Chunked提供。向一组索引（例如从0到#列的范围）提供稀疏值由Sparse提供。因此，CSR矩阵可以简单地写成Chunked<Sparse<Vec<T>>, Vec<usize>>, RangeTo<usize>, Vec<usize>>。注意，所有必要的Vec都是类型的一部分。为了方便，默认类型参数允许用户简单地写出Chunked<Sparse<Vec<T>>>。对于BCSR矩阵，将使用Chunked<Sparse<Chunked3<Chunked3<Vec<T>>>>>（或者也可以像之前那样将T替换为矩阵类型，如果底层数据永远不会被解释为数字的连续数组）。

动机

这个库是对在几何处理应用程序中重复编写相同的簿记代码来管理数据数组感到沮丧的回应。在这个环境中，所有数据通常都是事先知道的（与处理数据流相反），因此可以使用简单的动态大小数组（Rust中的Vec）有效地处理浮点数或整数数据（通常以数组结构形式）。然而，数据往往具有内在的复杂结构（例如，在刚体或软体动画代码中，属于不同对象的多个多边形网格顶点的3D位置子集）。这导致在实现围绕此类数据的算法时，需要额外的认知负荷来整理索引并确保数据完整性。这个库的目标是减少这种认知负荷，并使用户能够专注于数据结构和算法，而无需任何额外的性能损失。

不同的应用程序有不同的性能特征。这个库的目标不是规定数据类型的具体用法。相反，flatk旨在提供适用于数据处理应用程序中常见的代码模式的无域抽象。例如，当子集足够大时，通过Subset处理数据可能比克隆更快，但如果子集很小，则可能会更慢，因为克隆的子集可以提供更好的数据局部性。

这是一个探索性的项目，旨在确定这种类型的抽象是否可以简化数据处理代码并使其更可重用。

可组合性和自定义结构体

为了实现可组合性，标准库中连续集合（如 Vec 和 slice）的许多行为已经被提取到微特征（例如 SplitAt）中，这些特征需要为每个新组合类型实现。这意味着，为了将自定义 struct 包裹在此库提供类型内部，这些结构必须实现我们的特征。例如，如果一个粒子的集合具有位置和速度属性，将这些属性存储在结构体中可能是有意义的：

struct Particles {
    pos: Vec<[f32; 3]>,
    vel: Vec<[f32; 3]>,
}

然而，为了将 Particles 与 Chunked 等组合，需要实现 SplitAt、Set 和 Dummy 特征以启用迭代。我们提供了一个组件宏，它会自动为每个新结构体实现我们的特征。因此，为了让 Particles 可用于 Chunked，我们应该为 ParticleComponent 结构体推导 Component，并使每个可能分块的字段泛型，单独将 Particles 定义为类型别名，指向具有指定存储类型（Vec）的 ParticleComponent

#[derive(Component)]
struct ParticleComponent<X, V> {
    pos: X,
    vel: V,
}
type Particles = Chunked3<ParticleComponent<Vec<f32>, Vec<f32>>>;

然后我们可以将 Particles 作为单个集合使用，这将产生我们的粒子作为 ParticleComponent<[f32; 3], [f32; 3]> 类型

for ParticleComponent { pos, vel } in particles.iter() {
    // pos and vel are [f32; 3] arrays.
}

为了组合多个结构体，有一个 #[component] 属性可用。例如，如果我们可以创建一个使用 ParticleComponent 进行线性运动的 RigidComponent 组件

#[derive(Component)]
struct RigidComponent<X, V, O, W> {
    #[component]
    linear: Particle<X, V>,
    orientation: O,
    angular_velocity: W
}

注意事项和限制

由于缺少一些功能（如 GAT（用于更便捷的索引）、specialization（用于优化）和 const generics（用于与数组的更好互操作性）），组合性在稳定版 Rust（v1.41）中支持得不好。这些限制使得所提出的抽象难以实现、优化和在某些情况下使用。因此，这个库可能将在这些功能稳定之前保持实验性质。

状态

目前，这个库处于原型阶段（正在积极开发中），根本不适合生产使用。它已被用于设计一个实验性 tensor 库 的底层数据结构，该库被用于开发一个能够处理刚体、布料、软体以及它们之间摩擦接触的 有限元方法 模拟器（待公布）。

许可证

此存储库的许可证可以是以下之一：

• Apache 许可证第 2 版（LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT 许可证（LICENSE-MIT 或 https://opensource.org/licenses/MIT）

任选其一。