编程迷思（二）

发表于 | 分类于

功不唐捐，玉汝于成。

1. 二分

二分法解leetcode中有序数组循环移位有感：

二分的本质在于每次以常数时间将解空间分割为两部分，并由单调性判断解一定/一定不位于其中一解空间中。给出粗体强调的意义在于，有的时候只能做出一种情况的判断，但是也能二分。

2. 最小化接口

实现Mailbox和GPU间通信的消息缓存格式Tag抽象有感:

当半结构化数据无法完美使用数据结构表示的时候。例如消息缓存，其本身长度是不确定的，同时内部的Tag长度也不确定。

可以考虑最小化导出一个虚拟结构体接口，要求用户构造该结构体以提供必需的数据。模块内部根据用户提供的数据构造最终的结构体。

3. 分发的方式

dispatch的方法有很多种，一种很自然的方法是通过例如match，switch，when之类的结构进行分发。然而当分发的级数逐渐变多的时候，这个问题会变得复杂起来：

例如最近写nes模拟器，对每一条机器指令需要

  1. 识别指令：根据opcode，知道是哪一条指令，例如是lda还是tax
  2. 识别寻址模式：根据opcode，知道是什么寻址模式，例如是立即数还是绝对内存地址

3.1. 基于opcode硬编码分发

具体而言，根据opcode进行分发，并对每一个(指令类型，寻址模式)二元组进行硬编码。

例如：对opcode = 0xA9这种情况，在处理逻辑中硬编码指令类型即调用lda处理函数，硬编码寻址模式即以对应的寻址模式作为函数参数，如下：

1
2
3
4
5
6
7
8
9
10
11
when (opcode) {
  0xA9 -> {
    lda(Immediate)
  }
  0xA5 -> {
    lda(ZeroPage)
  }
  0xB5 -> {
    lda(ZeroPageX)
  }
}

从上面的代码可以发现，即使是同一类型的指令也有多次调用。

3.2. 基于hash表分发

当指令集包含几百种不同opcode时，通过上面硬编码的方法维护opcode到寻址模式的映射较为困难。

考虑解耦opcode到寻址模式的一一对应关系，仅根据opcode进行分发，则代码应该可以简化为下面这种形式：

1
2
3
when (opcode) {
  0xA9, 0xA5, 0xB5 -> lda(addressingMode),
}

这样的话需要额外的数据结构维护opcode到寻址模式的映射，为了O(1)的获取该映射，显然哈希表是一个较好的选择。

具体来说维护一个opcode到(指令模式，其它元数据)的哈希表。分发的时候，根据opcode获取寻址模式并调用对应的指令处理函数。

这种方式可以通过表维护opcode到寻址模式的映射，更容易维护。如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
addressingMode = hashMap[opcode]
when (opcode) {
  0xAA, 0xA5, 0xB5 -> lda(addressingMode)
}

// 使用表维护
arr = arrayListOf(
  Opcode(0xAA, "LDA", 1, Immediate)
  ...
)

// 使用表初始化
hashmap = Hashmap().apply {
  for (opcode in arr) {
    this[opcode.code] = opcode
  }
}