Geekly articles weekly

C ++缩写备忘单等。 第2部分：“不仅如此”

这是我的缩写备忘单的第二部分也是最后一部分，C ++开发人员应该知道。 这里提到C ++只是因为我主要为自己创建了备忘单，而且我是同一位C ++开发人员。

实际上，这部分包含的概念范围不限于C ++。 因此，更广泛的受众可能会对这种选择感兴趣。



与第一部分一样 ，如果可以的话，将缩写进行分组。 如果没有意义，则按字母顺序列出。

并发和原子操作：
• CAS
• ABA
• 美国联邦航空局
• RCU

资料储存：
• 酸
• 帽
• PACELC
• 基础

软件开发原则：
• 干
• 吻
• 亚尼
• NIH
• 富时
• GRASP
• 固体

其他：
• ABI
• 牛
• FBC，FBCP
• LRU

并发和原子操作


卡斯


比较并交换。 与交流比较。 这是一个带有三个参数的原子指令：原子变量或内存地址，期望值，新值。 当且仅当变量的值与期望值匹配时，变量才会接收新值，并且指令成功完成。 CAS要么简单地返回一个布尔值（然后可以称为“比较并设置”），要么失败，它还返回第一个参数的当前值。

伪代码
bool cas(int* addr, int& expected, int new_value) { if (*addr != expected) { expected = *addr; return false; } *addr = new_value; return true; }

在C ++中， CAS由以下方法系列表示： std::atomic<T>::compare_exchange_weak ， std::atomic<T>::compare_exchange_strong以及自由函数std::atomic_compare_exchange_weak ， std::atomic_compare_exchange_strong 。 *弱和*强之间的区别在于前者会产生错误的负面结果。 即 如果期望该值，则它们将返回false并且不会将其替换为新值。 存在弱操作的原因是，在某些体系结构上， 强操作相对昂贵。 在大多数情况下， CAS指令在一个循环中旋转（所谓的CAS循环），因此使用* strong代替* strong不会改变逻辑，但可以提高性能。

CAS指令用于实现同步原语（例如互斥量和信号量）和无锁算法。 通常会导致ABA问题。

阅读更多： 一次（俄语） ， 两次（英语）

阿巴


ABA问题。 ABA问题。 在基于与交换的比较的并行算法（请参阅CAS ）中，例如在无锁算法中，会出现此问题。 底线是线程读取原子变量的值，执行其他操作，并通过与交换进行比较来更新此变量。 即 流程逻辑如下：如果变量仍然包含先前的值，则什么都没有改变，一切都按顺序进行。 但这可能并非如此。 对问题的更正式描述：

  • 线程1读取变量的值，它等于A
  • 线程1被强制退出，线程2正在启动
  • 线程2将变量的值从A更改为B，进行了一系列更改（更改了与变量关联的某些值或只是释放了内存），然后再次将值-从B更改为A
  • 线程1恢复操作，将先前获得的值与当前值进行比较，得出结论没有任何改变

该问题的可能解决方案：

  1. 最简单，最明显的是使用锁。 这将导致通常的具有关键部分的线程安全算法。 但是它将不再没有锁。 但是，如果涉及CAS和ABA ，那么这很可能不是一种选择。
  2. 在比较的值上添加特殊标签。 例如，计数器的更改数量。 一方面，该计数器可能溢出，但另一方面，现代的x86_64处理器支持128位CAS操作。 即 在比较指向计数器的指针时，您最多可以放弃64位，并且有人认为这足以满足该算法连续运行10年的需要。
  3. 某些体系结构（例如ARM）提供LL / SC（加载链接，存储条件的）指令，这些指令不仅允许您获取内存中地址的当前值，而且还可以了解自上次读取以来该值是否已更改。

为了使用没有锁的数据结构（例如堆栈，列表或队列），通常存在悬挂指向远程节点的指针的风险，因此基于递延删除节点，可以使用ABA解决方案的一整套解决方案。 这包括垃圾收集器，危险指针和读取-修改-写入机制（请参阅RCU ）。

阅读更多： 一名（俄语） ， 两名（英语） ， 三名（英语）

联邦航空局


提取并添加。 Ahem ... get and add（似乎这个概念从来没有翻译成俄语）。 具有两个参数的原子操作：原子变量或内存中的地址，以及必须更改该变量的值。 如果体系结构允许，则该操作返回更改后的变量的先前值（自i486开始，x86允许）。 与CAS不同， FAA总是成功的。

伪代码
 int faa(int* addr, int diff) { int value = *addr; *addr = value + diff; return value; }

在C ++中，它以std::atomic<T>::fetch_add ， fetch_sub ， fetch_and ， fetch_or ， fetch_xor和相应的自由函数std::atomic_fetch_add等的方法std::atomic_fetch_add 。

作为原子指令的一种， FAA用于实现同步原语以及无锁算法和数据结构。

阅读更多： 一次（俄语） ， 两次（英语）

RCU


读取-复制-更新。 读-修改-写。 这是一种用于同步访问数据结构的非阻塞机制（当然是无锁的）。 在读取速度至关重要的情况下使用。 这是时间和内存（时空折衷）的折衷的一个示例。

RCU的思想是， 编写器流不会在适当位置更改数据，而是创建副本，对其进行必要的更改，并自动交换当前数据和更改后的副本。 同时，读取器线程可以随时访问具有新旧数据的访问权限。 如果没有读者使用过时的版本，则编写器将删除不再需要的数据，从而释放内存。

非常简化的RCU的工作方式如下：

  • 许多读者，一位作家。
  • 阅读和更改同时发生。
  • 读者使用非常轻量级的同步。 实际上，读者只需在进入关键部分时和离开关键部分时通知作者。 仅在关键部分使用同步数据。
  • 作者以原子方式用副本自动替换数据后，便宣布所谓的宽限期（宽限期）的开始。 当在此阶段开始时处于关键部分的所有读者都离开其关键部分时，宽限期结束。 现在，编写者可以安全地删除过时的数据。 暗示所有关键部分都是有限的，这保证了宽限期的有限性。

RCU非常适合经常读取而很少更新的数据。 此机制在Linux内核中得到了积极使用，在Linux内核中，确定宽限期何时结束非常简单。

缺点：

  • 同步访问频繁修改的数据很差。
  • 难以在用户空间中实现。
  • 取决于原子地更改指向内存中地址的指针的能力，但并非所有架构都提供此功能。

阅读更多： 一次（俄语） ， 两次（英语）

资料储存


酸


原子性，一致性，隔离性，耐久性。 原子度，一致性，隔离性，耐用性。 这是DBMS中的一组事务要求。 ACID即使在出现错误的情况下也可以提供可靠且可预测的DBMS操作。

  • 原子性确保事务完全完成或不执行任何操作。 中间状态是不可能的，不可能是一个事务操作成功，而另一个则不能。 全部或全无。
  • 一致性可确保在事务开始之前和完成之后，数据库中的所有数据均满足所有指定的规则和限制。 在执行交易期间，可能会破坏一致性。
  • 隔离确保并发事务不会相互影响。 没有事务可以访问另一个事务处理的不一致数据。
  • 持久性意味着成功事务的结果存储在数据库中，并且不会丢失，无论事务完成后立即对数据库进行什么处理。

所有主要的关系DBMS都完全支持ACID 。 在NoSQL世界中，这种完全支持很可能是一个例外。

阅读更多： 一次（英语） ， 两次（英语）

瓶盖


CAP定理。 CAP定理。 定理指出，任何分布式系统在列表中最多只能具有两个属性：数据一致性（ Consistency ），可用性（ Availability ），抗分离性（ Partition tolerance ）。

  • 在这种情况下， 一致性是指（简化的）一致性。 即 一旦一个节点上的数据更新操作成功完成，其他所有节点都已经具有此更新的数据。 因此，所有节点都处于一致状态。 这不是ACID要求的一致性。
  • 可用性意味着每个故障节点在合理的时间内返回对每个请求的正确答案（用于读取和写入）。 不能保证来自不同节点的响应匹配。
  • 抵抗分离意味着，如果在其节点之间丢失任意数量的消息，系统将继续正常运行。

因为 这三个属性都是无法实现的；从CAP定理的角度来看，所有分布式系统都分为三类： CA ， CP和AP 。 CA系统显然不具有抗分离性。 因为 在大多数情况下，分布意味着在真实网络上分布，并且在真实网络中，丢失数据包的机率始终为非零，因此CA系统几乎没有兴趣。

选择是在CP和AP之间，即在一致性和可用性之间。 遵循ACID原则的传统关系DBMS倾向于一致性。 尽管许多NoSQL解决方案都选择可访问性和BASE 。

在网络正常运行的情况下，即在没有网络分离的情况下， CAP定理不对一致性和可用性施加任何限制。 即 捐东西是没有必要的。

阅读更多： 一名（俄语） ， 两名（英语） ， 三名（英语）

Pacelc


PACELC定理。 PACELC定理。 这是CAP定理的扩展，它指出，在网络分区（ Partition ）的情况下，分布式系统被迫在可用性 （ Consistency ）之间进行选择，而在正常的网络操作（ Else ）的情况下，则必须在延迟（ Consistency）之间进行选择。 ）

因此，如果CAP定理区分出两类通过网络分离稳定的系统，则PACELC拥有其中的四类 ： PA / EL ， PA / EC ， PC / EL和PC / EC 。 某些NoSQL数据库可以根据设置更改其类。

阅读更多： 一次（俄语） ， 两次（英语）

基础


基本上可用，软状态，最终一致性。 基本可用性，脆弱状态，长期一致性。 根据分布式系统中的CAP定理，必须放弃某些东西。 从长远来看，通常会放弃严格的一致性，而倾向于一致性。 这意味着在没有数据更改的情况下，系统最终将有一天最终进入一致状态。

为了表明这种妥协，缩写BASE开始被使用得比较紧 ，并且出现了一些化学术语的游戏（ ACID-酸度， BASE-碱性）。

  • 基本上可用意味着系统保证数据可用性，它会响应每个请求。 但是答案可能是过时的或不一致的数据（或缺少数据）
  • 软状态意味着即使没有数据更改请求，系统的状态也可以随时间变化。 因为在任何时间点，数据都可以进入一致状态。
  • 最终的一致性意味着，如果数据停止更改，则它们最终将以一致的状态结束。 即 对不同节点的相同请求将导致相同的答案。

阅读更多： 一次（英语） ， 两次（英语）

软件开发原理


干燥


不要重复自己。 不要重复。 这是软件开发的原理，其主要思想是减少系统中的重复信息量，目标是降低系统的复杂性并提高其可管理性。

在原著（ 《实用程序员》一书， 安德鲁·亨特 （ Andrew Hunt）和戴维·托马斯 （ David Thomas ）的著作中，该原则的表述如下：“每条知识在系统中都应具有单一，一致且权威的表示形式。” 在这种情况下，知识应理解为是指主题领域或算法的任何部分：代码，数据库架构，特定的交互协议等。因此，为了对系统进行一次更改，只需在一个地方更新一个“知识”即可。

一个愚蠢的例子：客户端和服务器之间相互传输结构化数据。 因为 这些是在不同计算机上运行的不同应用程序，那么它们都必须具有自己的这些结构的实现。 如果发生变化，则必须在两个地方进行更改。 避免重复的一个明显步骤是将通用代码分配到一个单独的库中。 下一步是根据结构的描述（例如Google协议缓冲区）生成它，以免编写相同类型的代码来访问结构的字段。

代码重复只是违反DRY的特殊情况。 并非总是如此。 如果两个代码看起来相同，但是每个代码都实现自己的业务逻辑，则DRY不会中断。

像其他任何原理一样， DRY是一种工具，而不是教条。 系统越大，越容易违反该原理。 首先，理想是无法实现的。 其次，如果盲目地遵循DRY会导致代码更复杂并且难以理解，那么最好放弃它。

阅读更多： 一个（俄语） ， 两个（俄语）

吻


保持简单，愚蠢。 使其更容易（在这种情况下，愚蠢的不是电话）。 这是大多数系统如果保持简单就能更好地工作的设计原则。 该原理起源于飞机工业，并在包括软件开发在内的许多地方得到了广泛应用。

在后一种情况下， KISS在设计和直接编写代码中都很有用。 简单的体系结构和代码不仅易于理解，而且易于使用，维护和开发。 如果生产者－消费者对足够，则不应欺骗MapReduce。 如果可以使用几个普通函数并达到所需的性能水平，元编程的魔术将变得非常复杂。

综上所述，一定不要忘记，简单性不是目标，而是无功能的要求。 最主要的是要达到设计/实现目标，建议以最简单的方式做到这一点。

阅读更多： 一名（俄语） ， 两名（俄语） ， 三名（英语）

雅尼


您将不需要它。 不需要了 这是软件开发的原理，其主要思想是拒绝过多的功能，其目的是节省用于开发的资源。

YAGNI说，您不需要设计或实现目前不需要的功能。 即使您确定将来会需要它们。 无需添加不必要的抽象，其好处将在以后的某个时间出现。

问题在于人们对未来的预测并不好。 因此，很可能“储备”中完成的所有事情都将派上用场。 事实证明，在这种开发，测试和文档上花费的时间和金钱都是浪费的。 另外，该软件已变得更加复杂；必须花费更多的资源来再次支持它。 更糟的是，事实证明有必要做不同的事情。 金钱和时间也将花费在纠正上。

YAGNI原则比DRY和KISS更为激进。 如果他们将系统分解成可以理解的部分并使决策变得简单，那么YAGNI只会删除不必要的部分和解决方案。

阅读更多： 一名（俄语） ， 两名（英语） ， 三名（英语）

h


此处未发明。 在这里没有发明。 这是拒绝他人发展的综合症，这一立场实际上与自行车的发明接壤。 通常，这种综合症伴随着一种信念，即在公司内部创建技术会更快，更便宜，并且技术本身会更好地满足公司的需求。 但是，在大多数情况下并非如此， NIH是一种反模式。

以下是一些证明NIH合理的情况：

  • 第三方解决方案的质量不够高，或者价格不够低。
  • 第三方解决方案具有许可限制。
  • 使用第三方解决方案会对其供应商产生依赖性，从而威胁到业务。

阅读更多： 一名（俄语） ， 两名（英语） ， 三名（英语）

FTSE


软件工程基本定理。 软件开发的基本定理。 实际上，这不是一个定理；它没有证明。 这是安德鲁·科尼格（Andrew Koenig）的一句名言：
任何问题都可以通过添加另一层抽象来解决。
有时他们会在短语中添加“ ...，但抽象层过多的问题除外”。 通常，“定理”并不是一件严肃的事情，但是值得一读。

阅读更多： 一次（英语） ， 两次（英语）

格拉斯


一般责任分配软件模式。 一般职责分配模板。 这9种模式是Craig Larman在“ 应用UML和模式”中制定的。 每个模板都是一个（但是相当通用）软件设计问题的典型解决方案。

  1. 信息专家 。 问题：在对象之间分配职责的一般原则是什么？ 决策：将职责分配给具有履行此义务所需信息的人员。
  2. 创作者 问题：谁应该负责创建新对象？ 解决方案：如果满足以下一个或多个条件，则B类必须创建A类的实例：
    -B类汇总或包含A的实例
    -B写A
    -B积极使用A
    -B具有初始化数据A
  3. 低耦合 问题：如何减少变更带来的影响？ 如何增加重用的可能性？ 解决方案：分配责任，以降低连接性。 耦合是一种衡量元素连接刚性程度，相互依赖程度的度量。 即 建议连接对象，以便它们彼此之间仅了解必要的最低限度。
  4. 高传动比 （ 高内聚力 ）。 问题：如何管理复杂性？ 解决方案：分配责任，以保持较高的参与度。 高度参与意味着一个要素的责任集中在一个领域。
  5. 控制者 问题：谁应该负责处理输入事件？ 解决方案：指定一个负责任的类，该类可以代表整个系统或子系统（整体）（外部控制器），也可以代表一个特定的脚本（脚本或会话控制器）。 同时，控制器不执行对事件的反应；而是将其委托给相关的执行者。
  6. 多态 （ Polymorphism ）。 问题：如何根据类型处理不同的行为？ : , , , .
  7. ( Pure Fabrication ). : , ? : , .
  8. ( Indirection ). : , Low Coupling ? : .
  9. ( Protected Variations ). : , ? : , .

GRASP SOLID . , . . — .

: (.) , (.) , (.)

SOLID


SOLID. - ( ). (Robert Martin) 2000-. — , , .

  1. ( Single Responsibility Principle, SRP ). . « , ».
  2. / ( Open Closed Principle, OCP ). (, , ) , . : , .
  3. ( Liskov Substitution Principle, LSP ). , . 即 - .
  4. ( Interface Segregation Principle, ISP ). , . , . , , . , .
  5. ( Dependency Inversion Principle, DIP ). . . . . , , , , ( Java C#).

: (.) , (.) , (.)


ABI


Application Binary Interface. . , ( , , ). ABI – , (, ).

ABI ELF Linux PE Windows. , (, , etc.) . , ELF PE , .

ABI , , , , , . . . .

C++ ABI , , . . . , C++ Unix- (Linux, FreeBSD, MacOS) x86_64 System V AMD64 ABI , ARM – ARM C++ ABI . Visual C++ ABI , . System V ABI, (mangling) ( Linux 6 , Windows – 4), .

API ABI , , . C++11 ( ). - GCC 5 ( COW ), .

: (.) , (.) .

COW


Copy On Write. . , implicit sharing lazy copy. , , , . — «» — .

COW : . , , .

COW :

  • Linux. fork() , .
  • (snapshots) (Btrfs, ZFS) (MS SQL Server).
  • ++11 std::string COW . C++11 std::string (. ABI ).
  • Qt COW .

: (.) , (.)

FBC, FBCP


Fragile Base Class (Problem). . , , .

,
 struct Base { virtual void method1() { // ... } virtual void method2() { // ... method1(); // <--      } }; struct Derived : Base { void method1() override { method2(); } };

FBC , , Java ( C++ ). FBCP :

  • , ( final C++ Java).
  • , .
  • , , .

: (.) , (.) , (.)

LRU


Least Recently Used. . ( ). «-», — (hit ratio). , . , . — , , .

LRU , . , , . , . LRU — O(n), — O(1), — O(1). - .

,
 template <class K, class V> class LRU { private: using Queue = std::list<std::pair<K, V>>; using Iterator = typename Queue::iterator; using Hash = std::unordered_map<K, Iterator>; Queue queue_; Hash hash_; const size_t limit_; public: LRU(size_t limit) : limit_(limit) { } std::optional<V> get(const K& key) { const auto it = hash_.find(key); if (it == hash_.end()) { return {}; } it->second = reorder(it->second); return { it->second->second }; } void add(K&& key, V&& value) { if (hash_.size() >= limit_) { pop(); } queue_.emplace_front(std::move(key), std::move(value)); const auto it = queue_.begin(); hash_[it->first] = it; } private: Iterator reorder(Iterator it) { queue_.emplace_front(std::move(it->first), std::move(it->second)); queue_.erase(it); return queue_.begin(); } void pop() { hash_.erase(queue_.back().first); queue_.pop_back(); } };

LRU , . . n . LRU : MRU (Most Recently Used), LFU (Least Frequently Used), Segmented LRU, 2Q . .

: (.) , (.) , (.)

聚苯乙烯


- - — .

Source: https://habr.com/ru/post/zh-CN470317/

More articles:


All Articles