作业 6：堆分配器#

迄今为止，我们都以用户身份使用堆内存管理函数，现在是时候深入了解并实现自己版本的 malloc、realloc 和 free 了！堆分配器的主要目标是：

  • 正确性：为格式正确的任意“请求组合”提供服务

  • 高利用率：内存使用上满足更紧凑、更低开销、重复利用等要求

  • 快速：快速响应请求

有多种设计可以满足这些目标，但需要考虑各种权衡。正确性固然重要，但紧接着的优先事项是：节省空间还是提高速度？示例中的 Bump Allocator 可以非常快地响应请求，但却会持续地消耗内存。另一种设计是，堆分配器可以积极的回收内存，通过打包压缩来降低内存空间占用，但这样的处理又会降低请求响应的速度。工业界的实现是在不牺牲任何一个目标的情况下，找到一个最佳的平衡点。

在本次作业中，你将实现两种不同的堆分配器：隐式空闲链表分配器（implicit free list allocator）和显式空闲链表分配器（explicit free list allocator）。本次作业为你提供了足够的自由度，让你可以尝试并决定如何实现这些分配器，体会不同的设计策略以平衡各种利弊——除了作业中列出的要求之外，你还可以自由地选择你认为合适的策略来设计分配器！完成本次作业将帮助你：

  • 了解实现堆分配器的复杂性以及工程上的权衡

  • 进一步提高你的指针使用和代码调试技能

  • 分析你的代码，找出效率低下的部分并尽力优化

  • 总结本课程中掌握的所有技能和知识点

为了帮助你评估学习进度，对于每个作业/实验，我们罗列了一些要点，并提供了一些思考问题。在完成作业后，可以使用这些问题进行自我检查。如果你不能很好地回答这些问题，那么还需要进一步努力。

  • 提高 malloc 效率的主要挑战是什么？什么原因让 free 操作如此高效？

  • 解释内部碎片（internal fragmentation）和外部碎片（external fragmentation）之间的区别。哪个对利用率的威胁更大？

  • 如果你已经创建了高效的 malloc 和 free，那么基于这些接口实现的 realloc 是否也一样高效？

  • 吞吐量（throughput）和利用率（utilization）常常被视为是对立的。提高吞吐量会以降低利用率为代价，反之亦然。是否有一些方法可以让二者达到平衡？

初始项目#

你的个人用户目录下应该已经有 cs102 这个文件夹了，通过下面的命令拷贝初始代码到该目录中：

cp -r /home/cs102-shared/assignments/final-project ~/cs102

重要提示#

  • 阅读教科书。 在 CSAPP 第 9.9 节包含了堆分配器的背景知识，包括示例代码。你可以查看这些代码，但请注意，其结构框架与本次作业不兼容，代码可读性也较差，还使用了风格较差的预处理器宏定义。你可以以此为起点，尝试获取一些灵感，然后编写自己的实现。

  • 遵循设计-编码-测试工作流。尝试先勾勒出你的设计，思考各个重要的因素，然后再分解为一个个可管理的小块代码片来实现，并在每次实现完成后进行彻底的测试。建议你先阅读初始项目代码，了解测试工具的工作原理，然后尝试完成隐式空闲链表分配器的实现。最后，再将所有内容移植到高吞吐量、高利用率的显式空闲链表分配器中——你应该基于隐式空闲链表分配器的代码来实现显式空闲链表分配器，这样做可以先保证通过所有测试，然后再将注意力集中到添加显式空闲链表分配器功能上。

  • 同时运行多个测试脚本。你可以使用正则表达式来指定多个测试文件，并与测试工具一起运行。例如，你可以使用 samples/example*.script（注意星号）作为文件名，运行 samples 文件夹中以 example 开头的所有测试文件。

  • 编写辅助函数。对于一些重复操作的任务，例如在有效负载指针与其标头之间来回移动或从一个标头前进到下一个标头。尽管这些任务可能只是单行语句，但它们却是复杂、密集的指针操作。将这些任务封装成独立的辅助函数，只需要正确编写一次就可以放心调用！

  • 警惕指针类型。如果你知道指针的类型，请使用其特定类型来声明它。仅当指针类型未知或可能变化时才使用 void*。另外，不要将特定类型的指针声明为 void*，这会误导读者和编译器。

  • 善用结构体和 typedef。在适当的时候，使用结构体封装数据可以让代码更清晰、更易于阅读。另外，涉及到结构体类型转换时，也可以更轻松地操作数据。此外，你还可以使用 typedef 利用现有类型来自定义合适的类型名称，例如，typedef int custom_type; 声明了一个 custom_type 类型，但本质上仍然是 int。

  • 警惕类型转换。不能随意地进行类型转换。类型转换会破坏类型系统，编译器不再提供相关的警告信息。在转换之前，请考虑一下：为什么需要这个转换？如果不转换，会发生什么？有没有更安全的方式来实现我的目的？如何尽可能地利用类型系统？

  • 逐步求精。实现 malloc 或 realloc 需要编写大量代码，超长的代码行可能会让你感到非常难受。可以尝试将其分解为一个个小任务：寻找区块、更新内部状态等。

  • 有意义的命名。为字段和函数名选择一个好名称。例如 size_t 之类的名称意义不够明确，无法让你区分它是有效负载大小还是总块大小（包括标头），也无法区分它使用的是什么单位（字节还是字？）。牢记，始终使用描述性变量名称！

  • 避免混用有符号/无符号类型。标准 malloc 接口将其参数视为 size_t，这是一个无符号长整型 unsigned long。混用有符号和无符号类型以及对位宽的疏忽，都可能会导致意想不到的错误，因此要深思熟虑并保持一致。

  • 代码效率。本课程不强调效率，而是更多地关注算法、降低代码重复、有效分解任务等。当以效率为目标时，优先事项将会有所变化。所以理想情况是，尽可能精简你的代码，这也是代码整洁和高质量的表现。只有当效率相对更重要，并且没有更优雅的方式实现时，我们再考虑牺牲代码质量来换取效率。

任务 1：测试工具#

为了让堆分配器通过其测试，我们需要一个良好的测试方案。项目中的 test_harness.c 测试工具和分配器脚本可以提供帮助！

分配器脚本#

分配器脚本包含一系列按照紧凑文本格式编写的请求。三种请求类型分别是 a（分配）r（重新分配）和 f（释放）。每个请求都有一个 ID 号，用于后续重新分配或释放时进行引用。编写格式如下所示：

a id-number size
r id-number size
f id-number

以下是一个脚本示例：

a 0 24
a 1 100
f 0
r 1 300
f 1

上述脚本将被转换为如下的函数调用：

void* ptr0 = mymalloc(24);
void* ptr1 = mymalloc(100);
myfree(ptr0);
ptr1 = myrealloc(ptr1, 300);
myfree(ptr1);

我们在 samples 文件夹中提供了多种不同的测试脚本，可以根据命名来推断其测试目的：

  • example 脚本用于测试分配器的特定功能。这些脚本非常小（少于 10 个请求），易于跟踪，对于早期开发和调试特别有用。但也因为太小，所以无法用于性能测试。

  • pattern 脚本是根据各种模式模板机械构建的（例如 500 个 malloc 后跟 500 个 free 或 500 个 malloc/free 配对）。这些脚本可以生成足够多的请求（大约 1000 个），尽管是人为生成的，但它们对于性能测试来说非常有用。

  • trace 脚本包含了实际程序的工作负载。这些脚本很大（> 5,000 个请求），表现出了不同的行为，并且对于全面正确性测试很有用。它们还提供了你可能期望的“真实环境中”的性能测试。

最后，强烈鼓励你创建自己的脚本！

测试工具#

test_harness.c 是作业提供的测试程序，可以检查这些脚本文件的正确性。该工具将解析脚本文件并将其转换为请求。执行脚本时，它会尝试验证每个请求是否成功响应。使用 make 进行编译时，构建工具将创建该程序的 3 个不同编译版本进行测试，每一个版本对应不同类型的堆分配器：test_bump、test_implicit 和 test_explicit。你可以指定一个或多个脚本文件作为 test_harness 的命令行参数，它将运行每个脚本文件并进行评估。

仔细阅读 test_harness.c，了解其运行方式，以便充分利用它。不需要深入研究文件末尾的解析脚本文件的代码，但需要你仔细检查文件开头的部分，了解其如何执行每个脚本并检查其正确性。

以下问题可以用来验证自己的理解：

  • 当发出 malloc 请求时，test_harness 会执行哪些检查来验证该请求是否得到了正确响应？对 free 执行了哪些检查？realloc 又如何？

  • test_harness 如何验证内存块之间没有发生重叠？

  • test_harness 向已分配内存块的有效负载字节写入了什么值？写入有效负载的目的是什么？

  • test_harness 如何计算分配器的平均利用率？

  • 除了执行自有检查，该工具还会调用 validate_heap，从外部验证分配器的正确性。validate_heap 是你将在每个分配器中编写的一个函数，它会扫描内部堆数据结构（稍后将详细介绍如何实现这一点）。test_harness 什么时候调用 validate_heap？当 validate_heap 返回 false 时，test_harness 如何响应？哪个命令行标志可以让 test_harness 跳过 validate_heap 的调用？

  • test_harness 在执行每个脚本之前调用分配器的 myinit 函数。该函数会将分配器的记录清理干净并重新开始。如果 myinit 没有完成其工作，上一个脚本留下的垃圾值可能会引起错误。在堆分配器中实现 myinit 时，请记住这一点！

  • myinit 的参数是堆内存区段的边界。尝试在 GDB 下运行 test_bump 并打印出这些边界。堆内存从什么地址开始？堆内存大小是多少？记住这些值，你将在该区域看到很多活动。

  • 调试 test_harness 时，可以在执行测试脚本中的某个特定行号时设置断点。如何使用“条件断点”来实现这个操作？哪一行是触发条件断点的合适位置？

希望你可以很好地理解此代码的运行方式，以便在测试分配器时可以有效地使用它。

任务 2：探究 Bump 分配器#

文件 bump.c 包含 Bump 分配器的实现。我们在课程中讨论了这一策略，这是最简单的实现方法之一；其速度非常快，但内存利用率非常低。我们提供的实现并不适合所有边界情况，而且不会执行所有必需的错误检查，提供该实现的目的是为了让你了解如何实现堆分配器。以下是一些实验，用于观察其性能：

  • 阅读 bump.c 的代码。反汇编 mymalloc 和 myfree 函数并计算其汇编指令的数量。这是静态指令计数。

  • 打开分配器脚本 samples/pattern-repeat.script 并仔细阅读其内容。该脚本发出 1000 个请求：500 次重复调用 mymalloc，然后调用 myfree。

  • 使用实验 6 中讨论的 Callgrind 分析器，检查运行此脚本时，Bump 分配器的动态指令计数：

    valgrind --tool=callgrind --toggle-collect=mymalloc --toggle-collect=myrealloc --toggle-collect=myfree ./test_bump samples/pattern-repeat.script

    静态指令数和动态指令数之间有什么关系？它们之间是如何匹配的？

  • 在此输出文件上运行实验 6 中提到的注释器，查看标有指令计数的 C 源代码。

    callgrind_annotate --auto=yes callgrind.out.[pid]

    Bump 分配器代码的任何部分都没有成为特定的“热点”，所有操作都非常精简。

  • 查看 myrealloc 的 C 代码及其生成的汇编指令。分配器脚本 samples/pattern-realloc.script 发出 1000 个请求：100 个对 mymalloc 的调用和 900 个对 myrealloc 的调用。对此脚本执行相同的分析器和注释器。该注释将报告一个明确的“热点”，需要大量的指令。这么耗时的操作是什么？是什么让它如此低效？

  • Bump 分配器没有每个内存块的开销，但无法回收内存意味着它的利用率将会很糟。分析上述脚本时，测试工具报告的利用率是多少？

  • Bump 分配器包含一个 dump_heap 函数，该函数以文本形式打印出堆的内容。但是这个函数没有在代码中的任何地方被调用，那么它的作用是什么？我们可以使用 call 命令在 gdb 中暂停时调用函数。这意味着，如果我们在调试时，想要打印出堆内容的文本表示，我们可以使用 dump_heap 函数轻松地做到这一点。查看后续的 dump_heap 部分，了解更多信息以及如何将其添加到自己的分配器中。

Bump 分配器只需少量指令就可以为 malloc/free 提供服务，但其利用率极低。在你自己的分配器中，你的目标是在利用率和速度方面取得良好的平衡，而不是为了某一个而牺牲另一个。

任务 3：实现自己的分配器#

现在轮到你了！在本次作业中，你将实现自己的隐式/显式空闲链表分配器。

一般要求#

以下要求适用于两个分配器：

  • 该接口应与标准 libc 分配器匹配。仔细阅读 malloc 手册，了解分配器必须遵守的正确请求格式是什么以及所需的处理。请注意，有一些奇怪的问题需要考虑，例如 malloc(0) 等）。忽略手册“注释”部分中的深奥细节。

  • 对于如何处理不当请求没有要求。例如，客户重新分配栈地址、释放已释放的指针、超出分配块的末尾或其他错误的使用方式，你的响应可以是任意内容，包括崩溃或破坏堆内存。我们不会对这些情况进行测试。

  • 分配的块必须与请求的大小至少一样大，但不需要恰好是该大小。你的设计必须满足的最大内存大小请求在 allocator.h 中指定为常量。如果请求的块大于最大值，则分配器可以返回 NULL。不应假设该常量的值不会超过 size_t 的最大值。每个分配的块必须对齐到一个地址，该地址是 ALIGNMENT 常量的倍数，也在 allocator.h 中定义。可以假设该值为 8，并且你的代码仅适用于 8 对齐。但是你仍应使用该常量而不是对该值进行硬编码。这种对齐方式仅适用于返回给客户端的有效负载，而不适用于内部堆数据（例如标头）。你可以选择将较小请求四舍五入到某个最小值。

  • myinit 的工作是正确初始化分配器的状态。如果初始化成功，则返回 true；如果参数无效/分配器无法初始化，则返回 false。对于传入的参数，可以假设堆起始地址是与 ALIGNMENT 常量对齐的非 NULL 值，并且堆大小是 ALIGNMENT 的倍数。不应假设有关参数的任何其他内容，例如堆大小足以供堆分配器使用。

  • 你的分配器不可以调用任何内存管理函数。我们所说的“内存管理”特指那些分配或释放内存的操作，因此不会调用 malloc、realloc、free、calloc、sbrk、brk、mmap 或相关变体。使用其他库函数也可以，例如 memmove 和 memset 可以使用，因为它们不分配或释放内存。

  • 你的分配器可能会使用少量静态全局数据，最多 500 字节。此限制规定堆内存的大部分内务处理必须存储在堆段本身内。

  • 测试工具将寻找各种外部可见的问题（未对齐/重叠/外部段的块、未能保留有效负载数据等）；你的分配器在任何示例脚本上都不应出现操作或执行错误。

  • 你必须实现一个 validate_heap 函数，该函数可以彻底检查堆内部数据结构和状态，并确认是否发现问题。

validate_heap#

测试工具定期调用 validate_heap 来检查问题。该函数可以可靠地区分有效和无效的堆配置，并查明堆发生故障的确切时刻。有了该工具，你就不必尝试手动追溯损坏的堆是如何发生的，而是直接跟踪上下文中的关键调用，准确地观察错误是如何以及何时发生的。实现 validate_heap 时，不要重复测试工具已经为你执行的检查，而是通过检查堆的内部一致性来增强它们。你应该在实现每个分配器时，编写 validate_heap 的实现——不应该在实现分配器后才开始添加它！随着堆数据结构变得复杂，validate_heap 也会变得更加复杂。

dump_heap#

函数 dump_heap 不会在代码中的任何地方调用，但在 GDB 内调试时，如果你想打印堆的当前内容，可以调用这个函数。与 validate_heap 一样，它是一个非常有用的工具，可以收集信息、区分有效和无效的堆配置以及查明堆发生故障的确切位置。Bump 分配器提供了一个实现示例——对于你的分配器，你应该实现自己的 dump_heap 函数，例如遍历堆并打印出每个块相关的信息（例如，标头中的信息，显式空闲链表分配器中下一个/上一个空闲块，等等）。这可以向你展示堆结构的整体情况、哪些块是已分配的、哪些块是空闲的、不同块的大小等。

隐式空闲链表分配器#

现在你已准备好实现你的第一个堆分配器设计。你的隐式空闲链表分配器必须支持的特定功能是：

  • 跟踪块的标头信息，例如大小、状态（使用中或空闲）——你必须采用 8 字节大小的标头设计，使用 3 个最低有效位来存储状态

  • 如果可能的话，回收空闲块并重新用于后续 malloc 请求的

  • 通过隐式空闲链表（即逐块遍历）在堆中搜索空闲块的一种 malloc 实现

你的隐式空闲链表分配器不需要实现以下要求：

  • 实现任何已释放块的合并（显式分配器将执行此操作）

  • 支持就地重新分配（显式分配器将执行此操作）；对于重新分配请求，你可以重新选择另一个位置的内存来满足请求

  • 使用页脚/标尾（footer），如 CSAPP 中介绍的那样

  • 内存不足时调整堆大小。如果内存不足，你的分配器应该向客户端报告这一点。

该分配器的执行速度不会很快，但回收空闲节点的特性，肯定会比 Bump 分配器的利用率更高。

以上要求是你需要实现的最低规范。我们有意未指定更多细节，因为我们将这些设计决策留给你；这意味着你可以选择是否使用 first-fit/next-fit/best-fit/worst-fit 等进行搜索。尝试这些不同设计，来观察各种效果是很有趣的。对于作业来说，任何合理的选择和设计都是可以接受的。鼓励你进行更多的尝试！

显式空闲链表分配器#

基于隐式版本中学到的知识，使用文件 explicit.c 开发一个高性能分配器，该分配器采用显式空闲链表实现，并支持合并、就地重新分配。

你的显式空闲链表分配器必须支持的特定功能：

  • 隐式版本实现的块标头以及回收释放的节点（你可以从隐式版本中拷贝）

  • 显式空闲链表采用双向链表管理，每个空闲块有效负载的前 16 个字节作为下一个/上一个指针 请注意，不应扩大标头来添加指针字段。由于该链表仅包含空闲块，因此经济的方法是将这些指针存储在其他未使用的有效负载中。

  • malloc 应搜索显式链表的空闲块

  • 如果释放的块也是空闲的，则应与其右侧的相邻块合并。合并必须在 \(O(1)\) 时间内完成。你应该在释放块时执行此合并。

  • realloc 应尽可能调整块的大小，例如，客户端正在调整大小，或者其右侧的相邻块是空闲的并且可以被吸收。即使无法就地重新分配，你仍然应该尽可能多地吸收相邻的空闲块，直到可以就地重新分配为止，或者直到不能继续吸收而必须在其他地方重新分配为止。

你的显式空闲链表分配器非必须（但可以选择）的功能：

  • 将空闲块合并到左侧相邻块或以其他方式合并到左侧相邻块

  • 多次合并以获得一个空闲块。换句话说，如果你释放一个块并且其右侧有多个空闲块，则只需为前两个块合并一次。但是，对于 realloc，你应该支持就地重新分配，此时可能需要吸收其右侧的多个块。

  • 内存不足时调整堆大小。如果内存不足，你的分配器应该向客户端报告这一点。

与隐式版本相比，该分配器应该会进一步提高利用率并大幅提高速度。你最终将得到一个非常灵活的分配器，而且利用率也很高——这是一个令人印象深刻的成就！

以上要求是你需要实现的最低规范。我们有意未指定更多细节，因为我们将这些设计决策留给你；这意味着你可以选择是否使用 first-fit/next-fit/best-fit/worst-fit 等进行搜索。尝试这些不同设计，来观察各种效果是很有趣的。对于作业来说，任何合理的选择和设计都是可以接受的。鼓励你进行更多的尝试！

性能和效率#

注意，不要在此作业中使用 Valgrind memtool，该工具仅适用于标准分配器。但是，你可以在 Valgrind callgrind（分析工具）下运行测试工具来测量指令计数。

利用率#

你可以通过更有效地将内存块打包到堆段中，来实现更高的利用率，从而容纳更多的有效负载数据并相应地减少开销/碎片。测试工具可以计算单个脚本的利用率，以及一组脚本的平均利用率。单个脚本的利用率 = 峰值有效负载 ÷ 用于容纳该有效负载的总段空间。利用率范围从 0% 到 100%。具体的利用率取决于每个脚本；某个糟糕的脚本利用率可能会下降近 30%，而另一个脚本可能会达到近乎完美的 95%。如果整体平均利用率 >50%，那么你的实现就很好！

指令计数#

分配器的另一个重要目标是快速响应请求。 Callgrind 正是达成这一目标的工具——可以用来计算执行的指令数量，越低越好。

要获取分配器的测量结果，请在 Callgrind 下运行测试工具，并使用特殊参数将结果限制为分配器函数，如下所示：

valgrind --tool=callgrind --toggle-collect=mymalloc --toggle-collect=myrealloc --toggle-collect=myfree ./test_bump samples/pattern-mixed.script

上面的命令在指定脚本上运行 Bump 分配器，并要求 Callgrind 计算 my- 开头的三个函数中执行的指令总数。它将生成一个 callgrind.out.pid（pid 是进程号）文件。搭配 callgrind_annotate 一起使用，可以获取每个函数和每行代码完成的工作的详细信息。

callgrind_annotate --auto=yes callgrind.out.pid

性能#

对不同分配器的性能有哪些期望？

Bump 分配器。由于其处理请求的工作没有变化，malloc 和 free 的时间复杂度都是 O(1)。使用 -O0 编译，处理每个 malloc 请求，大约需要 35 条指令（使用 -O2 编译时，指令减少到不到 10 条）。这些计数表明其速度快得难以企及，但其快速响应的后果是利用率极低。

隐式空闲链表分配器。为了响应 malloc 请求，该分配器需要搜索隐式链表。指令计数将根据堆的使用情况以及空闲块的位置而变化。在最好的情况下（立即找到空闲块），一个 malloc 请求大约需要 40 条指令来处理。在最坏的情况下（搜索堆的大部分甚至全部），计数相对于堆中的块数呈线性增长，搜索 1000 个块的堆可能需要数千条指令——相当糟糕！free 是一个快速的、恒定时间的操作，每次调用大约需要 10 条指令。隐式空闲链表可以在 pattern/trace 脚本上实现令人满意的 60% 左右的平均利用率，这得益于隐式的回收。对于任何一个分配器来说，利用率达到 50% 以上都是一项非常值得骄傲的成就！

显式空闲链表分配器。在最好的情况下（立即找到空闲块），malloc 大约需要 50 条指令。在最坏的情况下，搜索会下降到 O(N)，但这只与空闲块的数量呈线性关系，而不是块的总数。合并一对块的时间复杂度应为 O(1)，可能约为 30 条指令。根据你的设计，这些指令可能会计入你的 free/malloc/realloc 中。对于某些工作负载，更积极的回收策略会使得显式利用率比隐式利用率更高，但就平均而言，二者差别不会太大。

realloc 是一个难以衡量的操作。如果就地调整块的大小，则可以快速提供服务（大约 30 条指令），否则将会达到 malloc+memcpy+free 的计数总和。拷贝有效负载可能在总成本中占具主导地位，因此指令数量根据块的大小而发生变化。

以上分析只是让你大致了解可能发生的情况，但并不意味着这些是绝对要求。这些计数选取自最低要求的简单实现，除了使用 -O2 进行编译之外，几乎没有进行任何优化。你的指令计数可能会更高一点，这没有问题。如果你努力降低计数，那就更好了！

注意：不要沉迷于绝对数字，而要把注意力集中在“从这些相对的比较中，可以学到什么技能”。例如，比较相同工作负载上两个不同分配器的性能，可以让你观察两种方法之间的区别。在设计、重构的前后，将分配器与其自身进行比较，可以让你衡量修改产生的影响。在各种工作负载上将分配器与其自身进行比较，可以观察其在不同场景中的优势/劣势。

编译器优化#

一旦完成并彻底测试了你的实现，请随意更改 Makefile 的顶部配置，尝试让 GCC 进行更积极地优化。虽然在活跃的开发阶段，使用 -O0 生成的代码更容易调试，但一旦致力于性能优化，请尝试更激进的优化级别和选项，例如 -O2。但请注意，优化后的汇编指令不再是 C 代码的简单转换，因此单步执行时，它可能会跳过某些代码，显示意想不到的情况。

测试与提交#

默认的 sanitycheck 的配置是收集指令计数并统计数据。它在 callgrind 下运行分配器来获取总指令数，并除以请求数来计算每个请求的平均指令数。在你的 custom_tests 文件中，每一行都应该是基于脚本的测试。例如：

test_implicit samples/pattern-recycle.script 
test_explicit samples/pattern-recycle.script

运行 sanitycheck custom_tests 将报告 custom_tests 文件中列出的每个此类测试的平均指令数。

作业提交方式参考作业 0，可以使用 submit 提交你的代码。为了追求完美，一些加分项值得你去注意：

  • 编译是否干净，有无警告等编译错误？

  • 默认测试是否全部通过？

  • 自定义测试案例是否全面？

对于代码实现部分：

  • 算法是否高效？还记得如何分析算法复杂度吗？

  • 代码风格及可读性是否注意过？有没有进行函数拆分，提取出一些更通用的代码？

  • 有没有尝试编写文档？一份好的代码就如同一篇优美的散文，不多一字，也不少一字。加油！