DOP理解

[BruceChen7]

参考资料

• data oriented programming book
• https://gist.github.com/BruceChen7/a31263d26c8722edfc3238363229e91c
• Andrew Kelley - Practical DOD on Vimeo
• bitsquid: development blog
• Relational Databases
• Handles are the better pointers
• https://dpc.pw/the-faster-you-unlearn-oop-the-better-for-you-and-your-software
• Object-Oriented Programming is Garbage: 3800 SLOC example - YouTube
• Arguments Against Oop

(usage:: 什么是 data oriented design )

• https://spacetimedb.com/blog/databases-and-data-oriented-design
• 面向数据的设计（DOD）一种编程范式，其重点是高效、灵活地组织、处理和存储数据。
• 任何程序的最终目的都是将数据从一种形式转换为另一种形式，而应尽可能以最有效的方式完成这种转换
  • 正在编写图形程序，需要将数据从场景表示转换为图形缓冲区，然后发送到 GPU
  • 编写编译器，则需要将程序从文本转换为结构化的二进制可执行文件
• DOD 的一个主要组成部分是考虑计算机组件的物理实现，以确定执行这些转换的最有效机制。
• DOD 强调内存中的高效数据布局，旨在最大限度地减少缓存丢失，确保数据连续存储

data oriented programming vs data oriented design

• Data Oriented Programming is more about Data-Oriented side of Functional Programming
• Data-Oriented Design is more about thinking deeply about your data and its structure and how it's applied in specific scenarios

什么是 ECS

• 一个数据模型，允许复杂的数据交互，同时允许未来的功能添加或重构
• 提供在内存中安排数据的有效方法，以充分利用 CPU 缓存。
• 在 ECS 模式中，这些目标是通过创建一个唯一的标识符来实现的，该标识符代表游戏中的 entity。
• 通过将称为 component 的数据片段与这些标识符关联起来，这些标识符就变得有意义了。
• 一个 entity 由 components 组成，以创建复杂的数据表示
• ECS 是为游戏而构建的，有一个隐含的假设，即程序会在 "帧 "内执行数据转换。
• 帧是一个固定长度的持续时间，在这段时间内，每个系统都会在其匹配的每个实体上执行。

ECS 数据模型的强大之处

• entity 的行为不是由为特定类型实体编写的代码决定的，
• 由 systems（又称 transforms）决定的，这些系统会对match与之相关的组件集的实体进行操作。
• 只需添加或删除 components，就能改变实体的行为，从而改变实体受影响的变换。
• 行为的改变是通过组件组合而不是继承实现的。
• 一个 system match 一组组件的行为，被认为是该系统 querying 程序中的所有数据，并在所有与该查询相匹配的实体上运行，
• ECS 通过在内存中连续存储 components，并将其与其他 components 集群在一起（这些组件也是一起被查询的），
• 从而在系统处理一个实体时，预取下一个实体的组件，或将其加载到缓存中，从而使 ECS 在现代 CPU 上具有相当高的性能。

ecs 是弱关系模型

• ECS 虽然在游戏数据模拟方面表现出色，但在处理某些数据关系和约束时存在局限性，它实际上是关系型数据模型的一个子集
• 如何在游戏中模拟聊天信息？可能把它作为游戏中的一个实体来表示。
• 将如何表示一种约束，以防止错误地将 health 组件添加到聊天信息中？
• ECS 中，创建一个单独处理聊天信息的系统非常简单，
  • 如何查询聊天信息以便按顺序显示呢？
  • 如何为拥有多个相同组件实例的实体建模？
• 在好友列表中，所有玩家都有许多同为玩家的好友，我该如何为好友列表建模？
• ECS 数据模型在对某些类型的数据（如游戏世界中的实体）进行建模时非常强大，
• 但在对所有类型的应用数据进行建模时还不够通用
• 无法在你的数据中表示某些约束或关系，或者对某些类型的数据进行建模会感到别扭，或者硬塞进数据模型中。

关系模型实现数据模型

CREATE TABLE Entity (
    id SERIAL PRIMARY KEY
);

CREATE TABLE Position (
    entity_id INT PRIMARY KEY,
    x FLOAT,
    y FLOAT,
    z FLOAT,
    FOREIGN KEY (entity_id) REFERENCES Entity(id)
);

CREATE TABLE Velocity (
    entity_id INT PRIMARY KEY,
    x FLOAT,
    y FLOAT,
    z FLOAT,
    FOREIGN KEY (entity_id) REFERENCES Entity(id)
);

CREATE TABLE Player (
    entity_id INT PRIMARY KEY,
    username TEXT,
    FOREIGN KEY (entity_id) REFERENCES Entity(id)
);

CREATE TABLE Enemy (
    entity_id INT PRIMARY KEY,
    target_entity_id INT,
    FOREIGN KEY (entity_id) REFERENCES Entity(id),
    FOREIGN KEY (target_entity_id) REFERENCES Entity(id)
);

• 有一个实体表，其中有一个唯一的 id 列。
• 所有其他表都必须有一个指向实体 id 的唯一外键引用。
• 系统（又称查询）必须在其匹配的每个实体、每个 "帧 "上执行。
• 只能在实体 id 上执行和操作 INNER JOIN 查询。

为什么采用 ECS 这种弱关系模型而不是关系模型

• 只是在关系模型中实施的常规 ECS
• 数据库速度慢，并不是因为数据库速度慢，而是因为在与数据库交互时，往往是通过网络将数据持久化到磁盘上，
• 来回传递必须解析、编译和执行的字符串。

作者的观点

• 程序视为数据库可提供了一个结构化的框架来评估它们。
• 它提供了一种通用且结构化的方式来表示和转换的应用数据，
• 一个框架，在其中挑选哪些特性和性能权衡对的特定应用最有意义，
• 以及一个框架，通过它能根据标准指标评估系统的性能。

OOP 已死

• 类和对象过于细粒度化，而关注隔离、API 等的正确位置是模块/组件/库的边
  • 在没有使用模块/库的代码库中通常会出现 OOP（Java / Scala）代码。
  • 开发人员专注于将每个类放入边界中，很少考虑哪些类组成一个独立的、可重用的、一致的逻辑单元。
• 面向对象编程需要一种不可变的数据组织方式
  • 将其分割成许多逻辑对象，
  • 定义了一个数据架构：带有关联行为（方法）的对象图。
  • 有多种逻辑表达数据操作的方式是很有用的。
    • 如果程序数据以表格化、面向数据的形式存储，那么就能有两个或更多模块分别以不同方式操作相同的数据结构。
    • 如果将数据拆分为带有方法的对象，则不再可能这样做
• 数据分散在许多小对象之间，大量使用间接和指针，并且一开始缺乏正确的数据架构会导致运行时性能差。

如何处理

• 数据考虑放在第一位。分析输入和输出、它们的格式、体积等。
• 运行时应该如何存储数据以及持久化：需要支持哪些操作，速度有多快（吞吐量、延迟）等。

对于任何有重要数据量的数据，设计都会类似于数据库。

• 会有一些对象（例如 DataStore），其 API 公开了所有必要的操作以进行查询和存储数据。
• 数据本身将采用 ADT/PoD 结构形式，并且记录之间的任何引用都将采用 ID（数字、uuid 或确定性哈希）的形式。
• 类似于或实际上由关系型数据库支持：
  • vector 或哈希映射通过索引或 ID 存储大部分数据，其他一些索引所需快速查找等等。
  • 还放置了其他像 LRU 缓存等的数据结构。
• 程序逻辑的大部分都需要引用这些 DataStores，并对其执行必要的操作。
  • 为了并发，通常通过消息传递、Actor 模式将不同的逻辑组件粘合在一起。
  • 例如：标准输入读取器、输入数据处理器、信任管理器、游戏状态等等。
  • 这样的actors能作为线程池、管道元素等来实现。
  • 当需要时，它们能拥有自己的 DataStore 或与其他actors共享一个。
• 仅仅因为软件在一个包含客户和订单等概念的领域中运行，并不意味着有任何与之相关联的 client 类或方法。
• 相反，Customer Concept 只是一个以表格形式存在于一个或多个数据存储中的一堆数据，
• 业务逻辑代码直接操作这些数据。

basic data operation 基本原则

• 使用通用的数据结构来代表数据结构
• 将 key 的类型为 string 的 map 称之为 string map
• Representing data as data means representing records with string maps.
• By positional collection , we mean a collection where the elements are in order (like a list positional collection or an array).
• string 的数组称之为[String]
• 通过索引，能说元素是通过 key 来访问玩儿的 (like a hash index map, or a dictionary).
• 在数据模型中，索引 key 都是 strings.
• 数据记录 (record) 是一种数据结构，其把相关的数据保存到一起。It’s a collection of record fields, possibly of different data types.
• A homogeneous map is a map where all the values are of the same type.
• A heterogeneous map is a map where the values are of different types.
• In DOP, we represent a record as a heterogeneous string map.
• A data entity diagram consists of records whose values are either primitives, positional collections or indexes.
• The relation between records in a data entity diagram is either composition or association.
• The data part of a DOP system is flexible, and each piece of information is accessible via its information path.
• 在数据模型中，灵活性和安全性是要妥协的
• DOP，牺牲 data safety 来获取 flexibility 和 genericity.
• DOP 中，数据模型是动态的，能随时动态的添加，删除和重命名 record fields.
• 使用通用的函数来操作数据
• Generic functions are provided either by the language itself or by third-party libraries like Lodash.
• JSON serialization is implemented in terms of generic function.
• On the one hand, we’ve lost the safety of accessing record fields via members defined at compile time.
• On the other hand, we’ve liberated data from the limitation of classes and objects. Data is represented as data!
• The weak dependency between code and data makes it is easier to adapt to changing requirements.
• When data is represented as data, it is straightforward to visualize system data.
• 通常不需要 a record 的类型
• In statically-typed languages, we sometimes need to statically cast the field values.
• Instead of maintaining type information about a record, use a feature field.
• 比起通过 class member 获取一个数据来，通过 map 来访问数据没有特别大的性能损失。
• 在 DOP 中，获取数据通过 path 和 通用的 function 来获取数据
• 在 DOP 中，很多代码都是简单的操作数据，没有任何抽象。

statement managment

• DOP 原则：数据是不可变的
• mutation 是改变系统数据的操作
• 所有的数据操作，都是通过 immutable functions，禁止使用 native hashmap，就是你直接底层的数据
• 在多版本来管理状态的方式中，mutation 分为两个步骤，一个是计算（calculation），另一个是提交（commit）

basic concurrent control

• 计算阶段只会进行计算，好像只有一个 mutations 在运行
• 在更新数据的时候，需要协调可能的并发修改的冲突
• 协商冲突的方式有点像 git 的方式，要么使用 fast-forward 方式，要么是 3-way merge
• 协调算法 是通用的 it can be used in any system where the system data is represented as an immutable hash map
• 提交阶段只用来协调并发改变的读写
• Our structural diff algorithm supports replacements and additions but not deletions
• 当数据是通用的，能通过引用来比较。速度会非常快。如果引用相同，意味着两者的数据相同。
• There are three kinds of of structural differences between two nested hash maps: replacement, addition and deletion.
• 结构化 diff 的方法支持 替换和添加，但不支持删除。

(usage:: zig 作者 dop 观点 )

• 
• 
• 
• 
• Make the size of each object smaller

memory layout

• every type has a natural alignment of size
• 避免空间的浪费

use indexes instead of pointers

// x86-64 为 16
const Monster = struct {
    anim: *Animation,
    hp: u32,
    y: u32,
};
var alive_monster: ArrayList(Monster) = .{};
var dead_monster: ArrayList(Monster) = .{};
//  为 12 字节
const Monster = struct {
    anim: u32,
    hp: u32,
    y: u32,
}

store boolean out-of-band

const Monster = struct {
    anim:  *Animation,
    hp: u32,
    y: u32,
    is_alive: bool // 浪费
};
// 大量的浪费
var alive_monster: ArrayList(Monster) = .{}

// 换成
var alive_monster: ArrayList(Monster) = {};
var dead_monster: ArrayList(Monster) = {};

eliminate padding with struct of arrays

const Monster = struct {
    anim: *Animation,
    kind: Kind,
    const Kind = enum {
        snake, bat, wolf, human
    };
};
var monster: ArrayList(Monster) = .{};

• 想象其对齐，改成 MultiArrayList
• 上面中间有很多的 padding，将其改成一个 MultiArrayList, bool 放在了一起，不会有 padding 的 7 个字节

  var monster: MultiArrayList(Monster) = .{};

Store sparse data in hash map

const Monster = struct {
    hp:  u32,
    x: u32;
    y: u32,
    held_items: [4]u32,
};
var monster: ArrayList(Monster) = .{}

• with 10000 monsters this uses 366 kb including ArrayList capacity overhead
• 观察到 held_items 只有 10% 才会有
• 把这个成员剔出来
• 根据观察到的数据，把有数据的一部分踢出来，单独存储，而不是直接放到整个成员里面
• 改成下面的那种

      const Monster = struct {
          hp:  u32,
          x: u32;
          y: u32,
      };
      var monsters: ArrayList(Monster) = .{}
      var held_items: AutoHashMap<u32, [4]u32> = .{}

• 只有 198KB 大小，包含 ArrayList and HashMap

encoding approaches

const Monster = struct {
    tag:  Tag,
    common: Common,
    const Tag = enum {
        bee_yellow,
        bee_black,
        bee_red,
        human_naked
    };
    const Common = struct {
        x: u32,
        y: u32,
        extra_index: u32, // 指向了下面的 index
    };
    const HumanClothed = struct {
        hat: u32,
        shoes: u32,
        shirt: u32,
        pants: u32,
    };

    // 有 extra_index 指定
    var clothed_human: ArrayList(Monster.HumanClothed) = .{};
}

• choose encodings according to your actual distribution
• 避免在结构体中使用额外的布尔值。
  • 能使用 enum Creature { AliveElf, DeadElf, AliveOrc, DeadOrc } 代替 enum Creature { Elf, Orc } 和布尔值 isAlive，
  • 就能有效地将数据位移到枚举使用的字节中。
  • 甚至能保留两个数组 dead_creatures 和 living_creatures 来完全避免使用该位。
• 如果重组你的代码，计算每个字节并优化缓存的使用。
• 这么做的关键词重组。
• 当知道数据是如何使用的，以及将如何继续使用时，这样编写代码才有意义。
• 要从一开始就做到这一点非常困难，因为你仍在围绕问题空间进行迭代。
• 一旦你知道了程序的典型行为，就能重新修改数据，使之与之相匹配。
• 这样做很可能会提高性能，但往往需要付出可维护性方面的代价：结构的改变会如何改变使用它的客户端代码？
• 如果基础假设发生变化，
  • 使用模式发生变化，
  • 如果将其移植过来而架构发生变化，
  • 需要在该结构中添加其他数据，那么重新更改它有多难

handlers are the better pointers

• 作者有相当大的 C++ 代码库（0.5 到 1mloc 左右）搏斗的经验，
  • 这些代码中，内存通常是通过智能指针管理的。
  • 几万到几十万个小的 C++ 对象，每个都在自己的堆分配中，通过智能指针相互指向对方。
  • 这样的代码在内存损坏方面是相当健壮的（segfaults 和损坏很少发生，因为大多数尝试都是在取消引用智能指针时被断言抓住的），
  • 但这种类型的 对象蜘蛛网代码也是很慢的，没有明显的优化起点，因为整个代码都是缓存未命中。
  • 其他典型的问题是内存碎片和 假内存泄漏，因为被遗忘的智能指针阻止了释放底层内存
  • 称它们为 "假泄漏"，因为这种类型的泄漏不能被内存调试工具发现
• 在现有的大型 OOP 代码库中实现这些想法也是相当棘手的，在这些代码中，对象的创建和销毁都是分散进行的。
• 这里描述的方法在面向数据的架构（DOP）中非常有效，
• central systems work on arrays of data items packed tightly in memory.

要点

• 将所有的内存管理转移到集中式系统中（如渲染、物理、动画......），这些系统是其内存分配的唯一所有者。
• 将相同类型的项目归入数组，并将数组的基本指针作为系统私有的。
• 当创建一个 item，只向外界返回一个 "索引柄"，而不是一个**指向项目的指针 **。
• 在索引句柄中，只使用数组索引所需的位，并将剩余的位用于额外的内存安全检查
• 只有在绝对需要时才将句柄转换为指针，并且不要将指针存储在任何地方。
• 这个想法基本上，
  • 普通的 "用户级代码不直接调用内存分配函数如 (malloc、new 或 make_shared/make_unique），
  • 并将指针的使用减少到绝对的最低限度只在绝对需要直接访问某项内存时作为短暂的引用。
  • 指针从来不是一个项目的底层内存的 "所有者"。
  • 直接的内存操作尽可能多地发生在少数集中式系统内，在那里与内存有关的问题更容易调试和优化。

Move memory management into central systems

• 系统 (central system) 是代码库中的一个部分，它负责一些相关的任务，如 "渲染"、"物理"、"AI"、"角色动画 "等等。
• 这样的系统通过明确定义的函数 API 与其他系统和 "用户代码 "分离，
• 发生在系统数据上的工作在紧密的中心循环中进行，而不是分散在代码库中。
• system 在用户代码的控制下对 item 进行创建和销毁（item 的创建和销毁与分配和释放这些 item 所使用的内存是不同的）。
  • 一个渲染系统可能要处理顶点缓冲区、纹理、着色器和管道状态对象。
  • 物理系统处理刚体、关节和碰撞基元，而动画系统处理动画键和曲线。
• 将这些项目的内存管理转移到系统本身是有意义的，
• 因为一般的内存分配器并不具备系统特定的领域知识，即如何处理 data items 和 data items 之间的关系。
• 这使得系统能够优化内存分配，在创建和销毁项目时执行额外的验证检查，并在内存中 arrange items，以充分利用 CPU 的数据缓存。
• 很好的例子是用现代 3D API 销毁渲染资源对象：
  • 当用户代码说要销毁时，不能简单地立即销毁资源对象，因为该资源可能仍然中等待被 GPU 消耗的命令列表所引用。
  • 渲染系统只会在用户代码要求销毁资源对象时将其标记为销毁，但实际的销毁是在后来 GPU 不再使用该资源时发生的。

Group items of the same type into arrays

• 一旦所有的内存管理都转移到系统中，系统就能利用其关于 item 如何被使用的额外知识来优化内存分配和内存布局。
• 一个明显的优化是通过将相同类型的 item 归入数组来减少一般内存分配的数量，并在系统启动时分配这些数组。
• 系统不会在每次创建新项目时进行内存分配，而是跟踪空闲的数组插槽，并挑选下一个空闲的插槽。
• 当用户代码不再需要该项目时，系统只是将该插槽再次标记为空闲，而不是执行去分配（与典型的池分配器没有区别）。
• 这种池分配很可能比对每个 item 进行内存分配要快一点，但这不是将 item 保存在数组中的主要原因（现代的一般分配器对于小的分配也相当快）。

额外的优点是

• item 被保证在内存中被紧密地包装起来，一般分配器有时需要在实际的item 内存旁边保留一些 housekeeping 数据
• 更容易将 hot item保持在连续的内存范围内，这样 CPU 能更好地利用其数据缓存
• 也能将一个 item 的数据分割成不同数组中的几个子项目，以实现更紧密的包装和更好的数据缓存使用
  • AoS 与 SoA 以及两者之间的一切
• 而且所有这些数据布局细节对系统来说都是私有的，在不影响 "外部代码 "的情况下进行改变是很简单的。
• 只要系统不需要重新分配数组，就能保证没有内存碎片（尽管在 64 位地址空间中这个问题不大）。
• 更容易及早发现内存泄漏，并提供更有用的错误信息：
  • 当一个新项目被创建时，系统能简单地检查当前项目的数量和预期的上限
  • 一个游戏可能知道在同一时间活着的纹理不应该超过 1024 个，
  • 由于所有的纹理是通过渲染系统创建的，当超过这个数字时，系统能打印出一个更有用的警告信息。

public index-handles 而不是指针

好处

• 能通过数组索引来识别一个 item，而不是需要一个完整的指针
• 系统能将数组的基本指针视为私人知识，而只向公众提供数组索引，而不是将内存指针交给外部世界。
• 如果没有基指针来计算一个项目的内存位置，外面的代码就不能访问这个项目的内存。

优点

• 系统外的代码甚至从来不需要直接访问一个项目的内存，只有系统需要。
• 在这样一个 "理想 "的情况下，用户代码永远不会通过指针访问内存，也永远不会造成内存损坏。
• 由于只有系统知道数组的基础指针，它能自由地移动或重新分配项目数组，而不会使现有的索引柄失效。
• array 索引比全指针需要更少的比特，而且能为它们挑选更小的数据类型，
• 反过来又允许更紧密地包装数据结构和更好地使用数据缓存
• 即能使用额外的句柄比特来增加内存安全
• 如果用户代码需要直接访问一个项目的内存，它需要通过一个 "查找函数 "获得一个指针，该函数将句柄作为输入并返回一个指针。
• 一旦有了这样的查找函数，上面概述的相当严密的内存安全方案就不再有保证，用户代码应该遵守一些规则。
  • 指针不应该存储在任何地方，因为下次使用指针时，它可能不再指向同一个项目，甚至不再指向有效的内存，
  • 指针应该只在一个简单的代码块中使用，而不是跨函数调用。
• 每次句柄被转换为指针时，系统能保证返回的指针仍然指向句柄最初创建的同一个 item
• 但是这种保证会随着**时间的推移而衰减，**因为指针下的项目可能已经被销毁，或者底层内存可能已经被重新分配到不同的位置（这与 C++ 中的迭代器无效问题相同）。
• 在完全不向用户代码暴露指针和为每一个内存访问进行句柄到指针的转换（有点昂贵）之间的一个很好的折中。

内存安全考虑

• 每种类型的句柄都应该有自己的 C/C++ 类型，试图将错误的句柄类型传递给一个函数的行为在编译时就已经被发现了
  • 句柄必须被包装成它自己的结构或类
  • 这能被限制在调试编译模式中。
• 运行时内存安全检查都发生在将句柄转换为指针的函数中。
• 如果句柄只是一个数组索引，那么它看起来就像这样。
  • 根据当前 item 数组大小对索引进行范围检查，这能防止 segment 和读写已分配但不相关的内存区域
  • 需要检查被索引的数组项目槽是否包含一个 active 的项目（当前不是一个 "空闲槽"），这能防止 "空闲后使用 "的简单变体
  • 最后，item 指针是由私有数组基指针和 public item index 计算出来的。
• 只要满足以下条件，得到的指针能安全使用，
  • 项目数组没有被重新分配
  • 被索引的项目没有被销毁
• 这两种情况只能在系统的一个函数中发生，这就是为什么存在两个指针使用规则
  • **不要存储指针，
  • 不要在函数调用之间保留指针。
• 如果只检查一个索引柄后面的数组槽是否包含一个有效的项目**，并不能保证它是该柄最初创建的同一个项目。
• 可能发生的情况是，原来的项目被销毁了，而同一个数组槽被重新用于一个新的项目。
• 这就是句柄中的 **自由位 (free bits)**的作用。
• 假设句柄是 16 位的，但是只需要 1024 个项目同时存在。
• 只需要 10 个索引位来寻址 1024 个项目，这样就有 6 个位能用来做其他事情。
• 如果这 6 位包含某种独特模式，就有可能检测到悬空访问。
• 当一个 item 被创建时，一个空闲的数组 item 被挑选出来，它的索引被放入较低的 10 个处理位中。
• 上面的 6 位被设置为独特的位模式。
• 由此产生的 16 位句柄（10 位索引 +6 位 "唯一模式"）被返回给外部世界，并同时存储到数组槽中。
  • 当一个 item 被 i 销毁时，存储在数组槽中的 item 句柄被设置为无效句柄值能是 0，只要 0 永远不会作为有效句柄返回给外部世界）。
  • 当句柄被转换为指针时，低 10 位被用作数组索引来查找数组槽，整个 16 位的句柄被与当前存储在数组槽中的句柄进行比较。
  • 如果两个句柄相等，那么这个指针是有效的，并且指向句柄所创建的同一个 item
  • 否则这是一个悬空访问，槽项要么已经被销毁
  • 在这种情况下，存储的句柄会有 无效句柄的值
  • 要么已经被销毁并重新用于一个新项，在这种情况下，前 6 个唯一模式位不匹配
• 在将句柄转换为指针时，这种句柄比较检查对于检测悬空访问非常有效，但是它并不完全可靠，因为相同的数组索引和'唯一模式'组合迟早会被创建。
• 但是它仍然比没有任何悬空保护（比如原始指针），或者在智能指针的类似情况下发生的假内存泄漏要好。
• 当然，找到好的策略来创建尽可能少发生碰撞的 unqiue handler 是最重要的部分。
• 显然，尽可能多地使用 unique 分配的模式是很好的，自由数组槽的重用方式也是很重要的（例如，后进先出与先进先出）。
• 写一个小的创建/销毁压力测试可能也很好，它能检查 handle 的碰撞，并能用来调整特定用例的唯一模式的创建。
• 一个 item 以非常高的频率被创建和销毁的系统比 item 的创建和销毁很少发生的系统需要更多的努力或者干脆是更多的 handle bits

优化的地方

• 每个数组插槽都有自己的生成计数器，在释放句柄时增加计数器（也能在创建句柄时增加，但在释放时增加意味着不需要为空闲插槽保留值来检测无效句柄）。
• 要检查句柄是否有效，只需将其唯一标签与其插槽中的当前生成计数器进行比较。
• 一旦生成计数器“溢出”，就禁用该数组插槽，以便不会为此插槽返回新的句柄。
• 是避免句柄冲突的完美解决方案，但句柄最终会用尽，因为所有数组插槽最终都将被禁用。
• 但是，由于每个插槽都有自己的计数器，因此只有在用尽所有句柄位而不仅仅是少数唯一标签位时，才会发生这种情况。
• 使用 32 位句柄，始终能创建 40 亿个项目，同时最多有 2^(32-num_counter_bits) 个项目处于活动状态。
• 这意味着能减少唯一标签的位数，而不会影响句柄安全性。
• 一旦能保证该插槽没有更多的句柄在使用（例如在代码的特殊位置，如进入或退出级别），也可能重新激活已禁用的插槽。

存在性处理

• https://www.dataorienteddesign.com/dodbook/node4.html
• 存在处理试图提供一种方法来消除关于是否处理数据的不必要查询。
• 软件中，都有 NULL 检查和查询，以确保对象在工作开始前处于有效状态。
• 通过使用数据结构（如数组）和避免使用 NULL 指针，能显著减少控制流程的数量。

复杂度

• 循环复杂度，这是衡量程序复杂性的一个指标。
• 分析系统中存在的条件数。这意味着对任何系统，它都从一开始，对于每个 if、while、for 和 do-while，都添加一
• 这种复杂性被称为控制流复杂性。软件固有的复杂性还有另一种形式，那就是状态的复杂
• 控制复杂性本身通常分为两种形式。
• 第一种形式是结构化的，例如支持编程范式、提供性能改进或驱动算法
• 第二种形式是防御性编程或开发人员助手，例如引用计数或垃圾回收机制。
• 当对数据进行操作的函数不确定数据是否存在或确保边界得到遵守时，这些技术会增加复杂性
• 第二种控制复杂性，控制流将以边界检查的形式出现，并确保数据没有超出范围。垃圾收集增加了复杂性。
• 垃圾收集增加了复杂性。多个语言没有关于它将如何以及何时发生的保证。意味着很难推理对象的生命周期

为什么要使用 if

• 在进行防御性编程时，许多 if 语句只是为了阻止崩溃。
• 有越界访问的 fault，防止指针为 NULL，以及防止其他异常情况导致程序停止的防御。
• 最后一个流程控制来自多态调用，主要是为了娱乐 do-more-with-less-code 开发模型，部分实施了面向对象的游戏编写方法
• 如果决定消除控制流是一个值得考虑的目标，那么必须开始理解消除哪些控制流操作。
• 如果尝试通过查看 defensiveprogramming 来消除控制流，尝试将的工作数据集保持为数组的集合。
• 这样就保证数据都不会为 NULL
• 进一步就消除许多流控制语句

处理类型

• 归结为三种操作类型之一：过滤器、变位或发射。
• 突变是对数据的一对一操作，它获取传入数据和转换前设置的一些常量，并为每个输入元素生成一个且仅生成一个元素。
• 过滤器获取传入数据，同样在转换前设置一些常量，并为每个输入元素生成一个元素或零元素。
• 发射是对产生多个输出元素的传入数据的管理。
  • 就像其他两个变换一样，发射使用常量，但输出表的大小没有保证；
  • 它产生零和无穷大元素之间的任何地方
• 区分这些类别能帮助决定使用什么数据结构来存储数组中的元素，以及是否需要 struct
• 或者应该将数据从一个阶段传送到另一个阶段，而不会触及中间缓冲区

不要使用 bool 值

• 学习压缩技术时，必须理解的最重要的方面之一是数据和信息之间的区别
• 在系统中存储信息，解析以声明某些东西存在的文字字符串，直到比如一个单一的位标志，以表明一个东西可能有一个属性。
• 通过使用算术编码等高级算法或利用领域知识来存储比位更少的信息。
• 真正编码的是概率

一个例子

• 如果你完全健康，那么你就不需要再生

• 一旦你中枪，你需要一段时间才能开始再生

• 一旦死亡就无法再生

• 一旦死了就没有健康可言了

  struct Entity {
      float timeofLastDemage;
      float health;
      // other
  };
  list <Entity> entities;
  void UpdatHealth(Entity* e) {
      TimeType timeSinceLastShot = e->timeofLastDemage - currentTime;
      bool isHurt = e->health  < MAX_HEALTH;
      bool regenCanStart = timeSinceLastShot > TIME_BEFORE_REGEN;
      if (!isDead && isHurt && regenCanStart) {
          e->health += min(MAX_HEALTH,  e->health+REGEN_PER_SECOND * timeSinceLastShot);
      }
  }

• 数据可能导致缓存行利用问题的常见问题

查看流控制语句来改善这一点

• 如果运行状况达到最大值，该函数将不会运行。
• 如果实体死亡，它将不会运行。
• 只有在上次造成伤害后足够长的时间内，重新生成函数才需要运行。
• 考虑到所有这些因素，重新生成不是常见的情况。
• 为常见情况组织数据布局

  struct Entity {
  };
  struct EntityDamage {
      float timeofLastDemage;
      float health;
  };
  list <Entity> entities;
  map<EntityRef, EntityDamage> entityDamages;
  
  void UpdateHealth(Entity* e) {
      for (edIter = entityDamages.begin(); edIter != entityDamages.end(); edIter++) {
          EntityDamage &ed = edIter->second;
          if (ed.health < 0) {
              deadEntities.push_back(edIter->first);
              discard(ed);
          } else {
              TimeType timeSinceLastShot = ed.timeofLastDemage - currentTime;
              bool regenCanStart = timeSinceLastShot > TIME_BEFORE_REGEN;
              if (regenCanStart) {
                  ed->health += min(MAX_HEALTH,  ed->health+REGEN_PER_SECOND * timeSinceLastShot);
              }
              if (ed->health >= MAX_HEALTH) {
                  discard(ed);
              }
          }
      }
  }

• 一个实体在表中现有的行中一个包含了布尔值。
• entityDamages 表，包含布尔值是第一个函数的 isHurt 变量。
• deadiEntitie 表，isDead 的布尔值现在是隐式的，也意味着健康值为 0，能减少许多其他系统的处理。
  • 不必加载一个浮点数并检查它是否小于 0，那么就节省了一个浮点比较或将其转换为布尔值。

不要经常使用枚举

• 枚举用于定义状态集。
• 上面的例子可定义的状态变量，它 influllhealth，ishurt，isDead 的三个状态。
• 然而，使用表来提供所需的所有信息，因为只有两个表
• 任何枚举都能用各种表来模拟。
• 只需要每个枚举值一个表。设置枚举是插入表或从一个表迁移到另一个表
• 缺点
  • 在实体中查找枚举的值很困难，因为它需要检查代表该实体状态的所有表。
  • 获取枚举值的主要原么要么是基于外部状态进行操作, 要么是确定一个实体是否处于适合进行操作的正确状态。
• 这在大多数情况下是不允许和不必要的，因为访问外部状态在纯函数中无效，
• 其次，任何依赖的数据都应该已经是表元素的一部分
• 如果枚举是以前由 switch 或虚拟调用处理过的状态或类型枚举，那么就不需要查找值 (look up the value)，而是改变思考问题的方式。
• 解决办法是运行转换，将每个 switch 或虚拟方法的内容作为操作应用到相应的表，即与原始枚举值相对应的表。
• 如果枚举用于确定一个实体是否被操作，例如出于兼容性原因，那么考虑一个辅助表来表示处于兼容状态。
• 将枚举以表形式呈现的原因是为了减少控制流的影响。，不使用枚举来控制指令流时，不处理它们是行的。
• 另一种可能性是当枚举的值频繁变化时，因为在表之间移动对象也是有成本的。
• 有意义的枚举示例包括键绑定、颜色枚举或小有限值集的好名称。
• 返回枚举的函数，例如碰撞响应（无、穿透、通过）。
• 任何实际上是对另一种形式数据的查找的枚举都是好的，其中枚举用于使对那些更大或更难记住的数据表的访问合理化。
• 对于某些枚举还有一个好处，即它们将帮助您在开关中捕获未处理的情况，并且在某种程度上，

多态的实现

• 不必使用虚表指针；能使用枚举作为类型变量。
• 该变量是结构的成员，在运行时定义该结构能够做什么以及它应该如何反应。
• 将用于在对象上调用方法时指导所调用函数的选择。
• 该变量是成员类型变量定义时，通常将虚函数实现为基于该类型的开关，或者作为函数数组。
• 如果要允许运行时加载库，那么将需要一个系统来更新调用哪些函数。。

运行时多态

• 多态性是程序中的实例仅由于实例的性质而以不同方式对public interface 做出反应的能力。
• C++ 中，编译时多态性通过模板和重载来实现。
• 运行时多态性是类在编译时类类型未知的情况下为公共基本操作提供不同实现的能力。
• C++ 通过虚表处理此问题，根据在由 this 指针指向的内存开头的虚表指针中的类型在运行时调用正确的函数。
• 动态运行时多态性是当一个类能根据其类型以不同方式对公共调用签名做出反应，但其类型能在运行时更改。
• Cpp 没有明确实现这一点，但如果一个类允许使用一个或多个内部状态变量，它能根据状态以及核心语言运行时虚表查找提供不同的反应。
• 其他更灵活地定义其类的语言，例如 Python，允许每个实例更新其对消息的响应方式，但由于调度机制建立在动态查找之上，
• 这些语言中的大多数总体性能都很差。

例子

// OOP
include <iostream>
#include <memory>

// 基类
class Shape {
public:
    virtual ~Shape () {}
    virtual double area () const = 0; // 纯虚函数，定义接口
};

// 派生类：圆形
class Circle : public Shape {
private:
    double radius;
public:
    Circle (double r) : radius (r) {}
    double area () const override { // 重写基类的 area 函数
        return 3.14159 * radius * radius;
    }
};

// 派生类：矩形
class Rectangle : public Shape {
private:
    double width;
    double height;
public:
    Rectangle (double w, double h) : width (w), height (h) {}
    double area () const override { // 重写基类的 area 函数
        return width * height;
    }
};

// 函数，接受 Shape 类型的指针，并调用 area 函数
void printArea (const Shape* shape) {
    std::cout << "Area:" << shape->area () << std::endl;
}

int main () {
    std::unique_ptr<Shape> circle = std::make_unique<Circle>(5.0);
    std::unique_ptr<Shape> rectangle = std::make_unique<Rectangle>(4.0, 6.0);

    printArea (circle.get ()); // 输出圆形的面积
    printArea (rectangle.get ()); // 输出矩形的面积

    return 0;
}

// DOP
#include <iostream>
#include <vector>
#include <functional>

// 定义一个结构体来表示形状的属性
struct ShapeAttributes {
    std::string name;
    double value1;
    double value2;
};

// 定义一个函数来计算圆形的面积
double calculateCircleArea (const ShapeAttributes& attributes) {
    double radius = attributes.value1;
    return 3.14159 * radius * radius;
}

// 定义一个函数来计算矩形的面积
double calculateRectangleArea (const ShapeAttributes& attributes) {
    double width = attributes.value1;
    double height = attributes.value2;
    return width * height;
}

// 定义一个函数指针类型，用于存储不同形状的面积计算函数
using AreaCalculator = double (*)(const ShapeAttributes&);

// 定义一个表格，将形状类型和对应的面积计算函数关联起来
std::vector<std::pair<std::string, AreaCalculator>> shapeCalculators = {
    {"Circle", calculateCircleArea},
    {"Rectangle", calculateRectangleArea}
};

// 函数，根据形状的类型调用相应的面积计算函数
void printArea (const ShapeAttributes& attributes) {
    for (const auto& pair : shapeCalculators) {
        if (pair.first == attributes.name) {
            std::cout << "Area:" << pair.second (attributes) << std::endl;
            break;
        }
    }
}

int main () {
    ShapeAttributes circleAttributes = {"Circle", 5.0, 0.0};
    ShapeAttributes rectangleAttributes = {"Rectangle", 4.0, 6.0};

    printArea (circleAttributes); // 输出圆形的面积
    printArea (rectangleAttributes); // 输出矩形的面积

    return 0;
}

事件处理

• 将自身在表中的存在作为注册技术，使得操作更简便，订阅变为插入，取消订阅变为删除，
• 还可能存在全局表用于订阅全局事件以及具名表，具名表能让订阅者在发布者存在之前进行订阅。
• 在触发事件方面，有立即触发转换或先排队新事件直至整个转换完成再一次性分发的选择。

componet based objects

• 组件化开发能避免不必要的概念链接，使对象更易于处理和分析，同时也更易于进行快速设计更改和避免陷入单对象的困境。
• 组件化对象按类型而非实例进行处理
• 组件化开发有多种不同的方式，如复合对象、基于组件的实体系统等，每种方式都有其特点和适用场景。
• 真正基于组件的对象不过是各部分的总和。意味着，基于组件的对象的定义也不过是一个带有一些构造参数的清单。
• 

there is no entity

• 当完全删除 Player 类时会发生什么？如果一个实体用它的组件集合来表示，它是否需要比那些自身相同的组件更进一步的身份？
• 就像表格行中的值一样，组件描述了一个单一的实例，但也像表格中的行一样，表格也是一个集合。
• 在组件组合的可能性宇宙中，构成实体的组件不是关于实体的事实，而是实体，并且是实体需要的唯一身份。
• 由于实体是其当前配置的组件，因此有可能完全删除核心 Player 类。
• 删除这个类可能意味着不再认为玩家是游戏的中心，但是因为类不再存在，这意味着代码不再绑定到特定的奇异实体。
• 

数据和意义的分离

• 数据是原始的，意义是问题领域的一部分。组件化方法允许在需要时才添加意义。
• 一个类或一个对象的功能来自于如何解释内部状态，以及如何解释随着时间的推移对状态的变化。
• 事实之间的关系是问题领域的一部分，称为意义，但事实只是原始数据。
• 事实与意义的分离在面向对象的方法中是不可能的，这就是为什么每次事实获得新的意义时，意义都必须作为包含事实的类的一部分来实现。
• 解散类，提取事实并将它们作为单独的组件保留，让有机会摆脱灌输永久意义的类，代价是偶尔不得不通过不太直接的方法查找事实。
• 选择只在必要时添加意义，而不是按意义存储所有可能相关的数据。
• 当它是试图解决的紧迫问题的一部分时，就增加了意义。

搜索

索引

• 在游戏中实现一个即时索引系统，以提供相同类型的性能改进。
• 在 SQL，每次想找出一个元素是否存在，甚至只是生成一个子集，就像需要找到某个范围内的所有实体一样，都必须将其构建为查询。
• 创建行或表生成的查询能被认为是一个对象，再次使用的情况下挂起，并且根据随着时间的推移如何使用来转换自己
• 从一个简单的线性搜索查询开始（如果数据还没有排序），该过程通过内部遥测发现它经常被使用，并且能够发现它通常返回一组简单可调的结果，
• 例如排序列表中的前 N 个项目。
• 在一些预定义的操作阈值数量、生命周期或其他指标之后，查询对象将 hook 它引用的表中是有价值的。
• hook 到插入、修改和删除将允许查询更新其答案，而不是每次被请求时再次运行完整的查询。
• 这种智能对象是 OOP 能为 dop 带来的。在某些情况下，这可能是一个显著的节省，但由于它的可选性，它也可能是安全的。
• 如果构建通用后端来处理在这些表中构建查询，它们提供多种好处。
• 不仅能期待没有使用的索引的垃圾回收机制，还能通过某种方式使程序自记录和自分析。
• 如果研究为构建查询索引而推送的表的日志，那么看到数据热点以及哪些地方有改进的空间。
• 甚至让代码自记录应该采取的优化步骤。

data-oriented lookup

• 第一步是了解搜索条件和搜索条件的数据依赖关系之间的区别。
• OOP 搜索解决方案通常会询问对象是否满足某些条件。
• 因为对象被问到一个问题，所以可能需要大量代码、间接访问内存以及填充但几乎没有使用的缓存行。
• 即使在 OOP 的代码库之外，内存带宽的利用率仍然很低。
• #

例子

• 通过了解流程对生产者和消费者的依赖来快速改进这一点。
• 通过迁移到部分 struct of arrays approach来节省大量的内存请求。
• 数据布局源于识别需要哪些数据来满足程序的要求
• 
• 考虑必须使用什么作为输入，然后需要提供什么作为输出。
• 唯一的输入是浮点形式的时间值，在这种情况下，需要返回的唯一值是动画 key。
• 需要返回的动画键取决于系统内部的数据，允许自己有机会以任何喜欢的方式重新排列数据。
• 输入将与 key 时间进行比较，但不是任何其他关键数据，将 key 时间提取到一个单独的数组中。
• 当找到要返回的动画 key 时，不需要只访问动画键的一部分，而是，想返回整个键。
• 将动画键数据保留为一个结构数组是有意义的，这样在返回最终值时访问的缓存行就更少了。

考虑的角度

• 一个算法的两种不同数据布局可能比使用的算法产生更大的影响。
• 

  i5-4430 @ 3.00GHz
  Average 13.71ms [Full anim key - linear search]
  Average 11.13ms [Full anim key - binary search]
  Average  8.23ms [Data only key - linear search]
  Average  7.79ms [Data only key - binary search]
  Average  1.63ms [Pre-indexed - binary search]
  Average  1.45ms [Pre-indexed - linear search]

finding lowest or highest is o sorting problem

• 在某些情况下，甚至不需要搜索。
• 如果搜索的原因是在一个范围内找到一些东西，比如找到最近的食物、住所或掩护，那么问题实际上不是搜索，而是排序。
• 在查询的前几次运行中，搜索可能会进行真正的搜索来找到结果，但是如果它运行得足够频繁，就没有理由不将查询提升到其他一些表数据的运行时更新排序子集。
• 如果需要最近的三个元素，那么保留最近三个元素的排序列表，当一个元素有更新、插入或删除时，使用该信息更新排序后的三个元素。
• 对于使不在集合中的元素更接近的插入或修改，在将新元素添加到排序后的最佳元素之前，检查元素是否更接近并弹出最低值。
• 如果有删除或修改使排序集中的一个成为消除的竞争者，可能需要快速检查其余元素以找到新的最佳集。

性能

• https://www.dataorienteddesign.com/dodbook/node9.html

耗时最多的地方

• 数据移动才是 cost 大的原因。
• 在游戏开发之初就将数据组织到数组中，就会有很多优化的机会
• 许多项目的弊端和延误的原因都在于坚持不过早地进行优化
• 后期阶段的优化之所以如此困难是因为许多软件在构建时到处都是对象实例，即使在不需要的时候也是如此。
• OOP 许多问题都是由 "实例是处理单元 "这一想法造成的。
• OOP 实践倾向于假设 instance 是代码工作的单元，并且实践技术和标准将对象的集合视为个体集合

什么时候开始优化

• 优化应在明确知道需要改进的地方后进行。
• 没有数据支持的优化是不成熟的
• 开发者需要即时反馈来改进代码。

#type/system #keyword/dop #public