在上一节 从汇编的角度理解程序（一）—— 操作数据的指令流 中提到，程序其实就是按顺序执行的操作寄存器数据的指令流。
不过，按顺序执行的指令流是如何实现程序中常见的分支和循环功能的呢？
简单地说，就是有条件的跳转 —— 依据条件寄存器和跳转指令实现，非常类似 C 语言里面的 goto 。

Read More

我打算就汇编程序写一个系列博客。不过，其目的不是为了弄明白怎么写汇编语言，甚至不是为了弄明白如何读懂汇编程序。
它的目的只是为了揭秘黑魔法，披露计算机程序更深层本质：

• 程序其实就是对数据进行操作的有序指令流
• 有序的指令流能通过跳转实现程序分支和循环
• 还能通过跳转和 stack 内存模式实现函数调用
• 通过规范的内存布局和读写操作实现复杂的数据结构

Read More

有时候你可能想用 Docker 作为 C++ 项目的开发环境，就像 Python 用 Pyenv 作为开发环境一样。
本文就介绍了 Clion 的实现方式，实际体验效果非常令人满意，除了 Debug 的时候稍微麻烦一点(要多敲一个命令)。

Read More

ANS 算法来自于 Jagiellonian University 的 Jarek Duda 在 2014 年发表的一篇论文：Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding。
从标题来看，ANS 算法是一个既有 AC 算法的压缩率又有 Huffman 算法的压缩速度的无损压缩算法。我最近一直在研究怎么优化用户在移动端加载 3D 模型的体验。如果 ANS 算法所言非虚，那么我就可以通过不多的 CPU 资源(解压时间)来换大量的流量资源(下载时间)，从而降低用户在手机端加载模型的时间。
事实证明 ANS 算法确实很厉害，在权衡流量和 CPU 资源后，我们使用 ANS 把模型体积压缩到了上一代模型格式的 25%。20 万面的模型体积从 4 M(gzip后) 降低到了 1 M，在高通 610 CPU 的手机上，用微信浏览器解压大概需要 1.5~2 秒( 660 为 1秒)。也就是用 6 秒 的下载时间(根据我们的统计用户手机普遍下载速度为 500k/s) 换取了 2 秒的解压时间。而这只是非常低配的 610 处理器上面的表现。而且 CPU 性能的稳定性比网络性能的稳定性高得多。
在体验到 ANS 的巨大威力后，我实在按捺不住自己的好奇心，想去探究一下它的基本原理。

Read More

STL、PLY、AMF、3MF、OBJ、FBX、DAE、VRML、X3D、IEGS、STEP、JT…… 目前已发布的 3D 格式文件数量，往少了说至少有二三十种。
通过对十多种最流行的 3D 格式做了一些调查，我发现大量规范和特性各异的 3D 格式共存的原因可以归纳于三点：

1. 不同的应用领域孵化了少数简单但是理念各异的初始 3D 格式
2. 不断产生的新需求导致了基于几种初始格式的衍变格式
3. 组织之间的博弈造成解决同种需求的多种“竞争”格式共存

Read More

在之前的示例中我们使用了大量的 Py_INCREF 和 Py_DECREF 来管理 Python Object 的引用计数。 Empty 的 value_setter 里也使用了一种非常啰嗦的语法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

static int record_object_set_value(record_object *self, PyObject *value, void *closure) {
  PyObject *tmp;
  if (value == NULL) {
    PyErr_SetString(PyExc_TypeError, "Cannot delete value");
    return -1;
  }

  // 使用了一个非常啰嗦的临时变量
  tmp = self->value;
  Py_INCREF(value);
  self->value = value;
  Py_DECREF(tmp);

  return 0;
}

这一切都是为了内存管理。
本章我们将回顾 Python 的垃圾回收机制，包括引用计数、循环检测和弱引用这些概念；
在这个基础上，我们再来讨论在设计我们的类的时候要如何做才能避免内存泄漏；
接着，我们给类添加继承和被继承的功能，并展示如何复写特定的属性和函数；
最后，我们给类添加那些锦上添花的高级功能，比如静态属性、静态方法、类方法，以及一些 __magic_function__。

Read More

我们将用两章探索如何实现内置的 Python 类，并尝试去了解一些 Python 编程语言的底层实现。
和之前一样，我们先从一个简单的例子开始，再逐步添加更多的特性。
我们要实现的第一个类为 Empty，就像它的名字一样，这个类没有任何 member 和 method。在实现这个类的过程中我们将学习到创建一个类的基本流程。
我们要实现的第二个类为 Record, 它有两个成员属性 name(公开，string) 和 __value(私有，任意值), 以及 print 和 set_value 两个成员方法，并且有一个 value property。
由于 Record 的 value 可以设置为任意值(包括自己)，我们就得再深入考虑一下引用计数、dealloc 和 weak refrence 这些涉及到内存管理的问题。
接着我们给 Record 添加类方法(class method) get_count、静态方法(static method) get_purpose 以及 __repr__, __str__ 和 __eq__。
最后，我们创建一个 StringRecord 类，它是 Record 的子类，但是它的 value 只能是 str 类型的数据。

本章我们先掌握类的基本属性。

Read More

我们把用 C/C++ 实现的 Python 函数统称为 PyCFunction。
上一章 mymath 模块的 sum 函数能接受两个 int 参数并对它们求和。然而靠这样的功能还不能写出真正可用的 Python Module。
在本章我们将实现一个更复杂的PyCFunction以掌握更多必要的细节。

Read More

在本章我们会用 C 实现一个简单的的 Python 内置模块， 以了解用 C/C++ 拓展 Python 时的核心的组件和基本流程。
假设这个模块叫 mymath ， 其中有一个sum 函数:

1
2
3

import mymath
number = mymath.sum(1, 2)
print(number) # 3

Read More

一、红黑树是什么

红黑树是允许节点里包含最多两个 Node 的二叉树。

二、红黑树要解决什么问题

普通二叉树最大的问题在于，插入有序的序列会使二叉树会成为 N 的深度。
红黑树允许每个节点上最多挂两个 Node， 每当第三个 Node 插入的时候， 把中间值的 Node 往上冒泡。
如果在 root 上有三个 Node， 把中间的 Node 上冒做为新的 root。
由此可见，红黑树的深度是通过 root 往上冒增加的， 从而保证了每条路径到 root 的深度一致为 lg N (黑 Node 数量一致)。

Read More