构建快速JSON解析器和完整的JSONPath，OJ for Go的旅程

PermalLink GitHub是5000多万开发人员的家园，他们一起工作，共同托管和审查代码、管理项目和构建软件。

报名。

我做了一个梦。我将编写一个快速的JSON解析器、泛型数据和JSONPath实现，它将非常漂亮、组织良好，并且值得钦佩。嗯，现实开始发挥作用，嘲笑那些流言蜚语。Go JSON解析器和工具可能具有很高的性能，但要获得这样的性能，必须在美观上做出妥协。这是一个以解析器结束之旅的故事，解析器将Go JSONparser抛诸脑后，并产生了一些有用的工具，包括完整而高效的JSONPath实现。

公平地说，我确实是从以前的一些经验开始的。之前已经编写了两个JSON解析器。Ruby OJ和C解析器OJC都是这两种语言中表现最好的。为什么不来一杯OjGo for Go呢。

就像任何旅行一样，它从计划开始。是的，我知道，这叫做需求收集，但把它说成是计划一次旅行更有趣，而且这一切都是为了享受旅途中的发现。旅程发生在OJG的土地上，OJG代表OJ放弃。OJ或优化的JSON是我为Ruby编写的最受欢迎的宝石。

首先，JSON解析和任何频繁使用的操作(如JSONPath求值)必须比其他所有操作都要快。由于不必遵循现有的Go json包API，该API可以设计成最佳性能。

旅程将参观几个地区，每个地区都有自己的风景和需要解决的不同问题。

第一次访问是对通用数据的访问。不要与建议的围棋泛型混淆。这是一个完全不同的动物，与这里所说的通用数据没有任何关系。在用于重用的构建工具或包中，由这些工具作用的数据需要是可导航的。

可以使用反射，但是在处理私有字段或不能转换为可以写成JSON元素的字段时，这会有点棘手。其他选择通常更好。

另一种方法是使用简单的GO类型，如bool、int64、[]interface{}，以及直接映射到JSON或所有可能的GO类型的其他子集的其他类型。如果过于开放，例如使用[]接口{}，用户仍有可能将不支持的类型放入数据中。我不想特别挑出任何包，但是在API中看到接口{}的参数类型，然后没有文档描述支持的类型是令人沮丧的。

不过，还有另一种方法：定义一组可以在集合中使用的类型并使用这些类型。使用这种方法，泛型数据实现必须支持基本的JSON类型，即null、boolean、int64、float64、string、array和object。此外，还应支持时间。从JSON使用inRuby和Go的经验来看，总是需要时间的。时间在任何一组数据中都是不可忽略的一部分。

泛型数据必须是类型安全的。在数据中有一个不能编码为JSON的元素是不行的。

通用数据的一个常见操作是将该数据存储到JSON数据库或类似数据库中。这意味着将nil、bool、int64、float64、string、[]interface{}和map[string]interface{}转换为简单的go类型必须很快。

这一部分还计划使用JSONPath来支持获取、设置和删除元素的类型方法。他们希望对泛型节点采用一种基于对象的方法，可以使用类似以下内容的方法，但将泛型数据、JSONPath和解析保存在单独的包中。

不幸的是，这部分行程不得不取消，因为goTravel导游拒绝让包裹来回交谈。进口是单向的。在尝试将所有代码放在一个包中之后，它最终变得笨拙起来。函数名开始使用实际上应该是包名的前缀，因此对象和方法方法被删除。空气污染指数的变化，但旅程仍将继续。

下一站是解析器和验证器。经过深思熟虑后，似乎从验证器开始是与该领域友好相处的最佳方式。JSON解析器和验证器不必相同，每个解析器和验证器都应该尽可能高性能。解析器需要支持解析成简单的GO类型以及泛型数据类型。

在解析可能超过100 GB的文件中包含数百万或更多JSON元素的文件时，需要一个流式解析器。当然，与流解析器和字符串解析器共享一些代码会很好。当区域相似时，轻装上阵会更容易。

解析器还必须允许解析为本地GO类型。此外，即使GO解组不支持接口字段，也必须支持接口。许多数据类型使用接口，这是OjG解析器不能接受的限制。支持接口的另一种方法是可能的。

任何非常重要的JSON文档，特别是手工编辑的JSON文档，都可能在某些时候出错。解析错误必须标识错误发生在文档的哪个位置。

将旅途中最有趣的部分留到最后，JSONPath实现承诺使用降序、通配符，特别是过滤器来解决各种有趣的问题。

JSONPath用于从数据中提取元素。实施的这一部分必须是快速的。解析确实不需要很快，但如果有一种方法能够以不符合要求的方式构建一个JSONPath，那就好了，即使它不如解析字符串那么方便。

JSONPath实现必须实现Goessner文章中描述的所有功能。还有对JSONPath的其他描述，但Goessner的描述被引用得最多。由于实现已经开始，只要可以为数组索引提供与数组长度相关的类似功能，就可以省略所描述的脚本特性。从Ruby借用，使用负索引将提供该功能。

旅途按计划在一定程度上展开了。有一些错误的出发和重访，但最终到达了每个目的地，完成了旅程。

还有什么比仅仅从简单的GO类型定义泛型类型，然后在这些类型上添加方法更好的快速创建泛型类型的方法呢？一个gen.Int只是一个int64和一个gen.Array只是一个[]gen.Node。使用这种方法不会有额外的分配。

由于泛型数组和对象将每个集合中的值类型限制为gen.Node类型，因此可以保证集合只包含可以编码为JSON的元素。

如果没有导入循环，Node上的方法就无法实现，因此Node接口中的函数数量受到限制。很明显，需要一个特定于泛型数据类型的解析器，但这必须等到解析器部分完成之后。然后，可以重新访问通用数据包，并探索解析器。

展望未来，回顾一下通用数据解析器，在深入研究简单的数据解析器之后，并不是很有趣。泛型类型的解析器是OJ包解析器的副本，但是创建的不是简单类型，而是支持gen.Node接口的实例。

回过头来看，很难说这段旅程中最有趣的部分是解析器还是JSONPath。每个人都有自己独特的一套问题。不过，解析器是最好的起点，因为在努力实现高性能GO代码的过程中，我们学到了一些关于应该避免什么以及应该倾向于什么的有价值的教训。

从一开始，我就知道单遍解析器比构建令牌然后进行第二遍来确定令牌的含义更有效。至少这种方法在过去运作良好。我深入研究并使用了一个readValue函数，该函数根据读取的下一个字符进行分支。它起作用了，但比围棋平分秋色的目标慢了很多。那是要清除的障碍。第一次尝试失败了很多。当然，需要取消标记来验证这一点，因此启动了cmd/Benchmark命令。侧写并没有多大帮助。事实证明，这是因为大部分开销都在函数调用设置中，这在分析时并不明显。

我当时并不知道函数调用非常昂贵，但预料到函数调用会带来一些开销，于是将一些频繁调用的函数中的一些代码内联到调用函数中。这比我预想的要大得多。在这一点上，我查看了核心验证代码的GO代码。我很惊讶地发现它使用了很多函数，但没有附加到类型上的函数。我在解析器类型上尝试了这种方法，但带有函数。结果并不是很好。不过，只需将函数更改为将解析器作为参数，就会产生很大的不同。又学到了一课。

下一步是尽可能地删除函数调用，因为它们似乎代价很高。代码不再优雅，有许多重复的块，但运行速度要快得多。在这一点上，代码性能越来越接近于清除Go验证器栏。

在单遍解析时，通常使用概念状态机。当使用函数进行分支时，仍然有一个状态机，但是每个函数的状态都是有限的，因此更容易遵循。转移到单个功能意味着在单个状态机中跟踪更多的状态。实现是通过冗长的切换语句来实现的。不过，还有一个问题仍然存在。数组和对象必须经过测试才能知道何时允许结束]或}。由于避免了函数调用，这意味着在单个解析器函数中维护一个堆栈。这种方法效果很好，开销很小。

另一个调整是重复使用内存。在这一点上，解析器只分配了几个对象，但是如果堆栈的缓冲区可以重用，它为什么需要分配任何对象。这促使API发生了变化。最初的API是针对单个验证()函数的。如果验证器是公开的，它可以被重用。这很有意义，因为通常相同的应用程序会解析或验证相似的数据。这一更改足以将每次验证的分配减少到零，并将性能置于go json.Valid()栏之下。

在访问验证器时确定了许多最佳技术之后，下一部分旅程就是在解析器上使用这些相同的技术。

验证器和解析器之间的区别在于解析器需要构建数据元素。第一次尝试是将与值相关联的字节添加到可重用缓冲区，然后在源中值字节的末尾解析该缓冲区。它可以工作，WASA的运行速度和json一样快。解组可以工作，但这还不够，因为仍然有比看起来必要的更多的分配。

通过展开状态机，可以将NULL、TRUE和FALSE标识为值，而无需添加到缓冲区。这使情况略有改善。

数字，特别是整数，是另一种真的不需要从缓冲区解析的值类型，因此不是通过测试将其追加到缓冲区并调用strclu.ParseInt()，而是将整数值构建为int64，并随着字节的读取而增长。如果a.。如果遇到字符，则数字是一个小数，因此预期的类型会被更改，浮点数的每个部分都会被捕获为整数，最后在完成后创建afloat64。这是性能上的又一次改进。

不能做太多的事情来改进字符串解析，因为它实际上只是将字节附加到缓冲区，并使它们成为最后一个"；的字符串。不过，要追加的每个字节都需要检查。256长字节数组形式的字节映射用于该目的。

回到验证器中使用的堆栈，而不是像验证器那样在堆栈上放置一个简单的标记，当遇到对象startcharacter时，会将新的map[string]接口{}放到堆栈上。然后使用值和键来设置映射的成员。那里没什么特别的。

把最好的留到最后，数组就更难处理了。不只是将值添加到数组中，而是将其附加到数组中，然后返回相应的新数组。这不是构建切片的非常有效的方法，因为它将经过多次重新分配。取而代之的是，保留第二个切片索引堆栈。当要创建数组时，在堆栈上保留一个点，并且将该堆栈位置的索引放置在片索引堆栈上。在此之后，值被压入堆栈，直到到达数组结束字符]。然后引用切片索引，并为从堆栈上的数组索引到堆栈末尾的所有值分配一个新的[]接口{}。值被复制到新数组中，堆栈被折叠到索引中。有点复杂，但它确实保存了多个对象位置。

经过一些实验后发现，一些操作(如创建切片或添加数字)的开销在很大程度上没有通过调用函数来实现，因为它不像处理每个字节那样频繁发生。因此，一些函数的使用可以用来删除重复代码，而不会招致显著的性能影响。

解析器包之旅只剩下一站了。流媒体必须得到支持。在这一点上，已经有了如何处理流的计划，即加载一个缓冲区，并使用与解析字节完全相同的代码迭代该缓冲区，然后重复执行，直到没有剩余的内容可读。在缓冲区中使用索引似乎更容易跟踪，但是从for范围切换到for i=0；i<；size；i++{显著降低了性能。显然，继续使用射程方法更好。一旦开始工作，就可以快速返回验证器以允许它支持流。

流解析或解析中包含多个JSON文档的字符串最好使用回调函数来处理。这允许调用者处理解析的文档并继续进行操作，除非需要，否则不会招致任何额外的内存分配。

花在验证器和解析器上的时间相当长，大约一个多月的晚间编码时间。

对JSONPath的访问也将被证明是一次长时间的停留，在一些诱人的问题上有更多的创造力。

第一步是对JSONPath术语和行为进行语言和文化更新。由此决定JSONPath将由jp.Expr表示，该jp.Expr由片段或jp.Frag对象组成。遵循最小化分配的指导方针，jp.Expr只是jp.Frag的一小部分。在大多数情况下，表达式是静态定义的，因此解析器不需要很快。没有特别注意JSONPath解析器的速度。不稳定函数的使用方式更容易理解。我说更容易，不容易。有相当数量的危险曲线试图支持括号表示法和点表示法，以及如何很好地使用脚本解析器，以便一个可以调用另一个来支持嵌套过滤器。不过，看到这一切都走到一起是值得的。

如果需要在运行时创建表达式，则可以使用更容易构造它们的函数。这就形成了很多函数。我还希望能够保持代码紧凑，并配置其他代码，这样每个片段类型也可以使用单个字母函数创建。它们不一定要使用，但它们的存在是为了支持建筑表达式作为一个链。

根据数据计算表达式涉及遍历数据树以查找一个或多个元素。从概念上讲，apath的每个片段设置零个或多个路径来跟踪数据。当到达最后一个片段时，搜索就完成了。递归方法将是理想的，在这种情况下，一个片段的求值然后调用下一个片段的eval函数，并使用它匹配的尽可能多的路径。纸面上很棒，但对于像下降碎片这样的东西(..)。这是大量的函数调用。

考虑到函数调用很昂贵，而切片很便宜，所以使用了FORTH(语言)求值堆栈方法。不完全是Forth，而是一个混合了数据和运算符的类似概念。每个片段获取其匹配项和已在堆栈上的那些匹配项。然后，下一个片段依次对每个片段求值。这将继续进行，直到堆栈收缩回一个表示评估完成的元素为止。最后一个片段将所有匹配项放在返回的结果列表上，而不是放在堆栈上。

一种片段类型是类似于[？(@.x==3)]的过滤器。这需要脚本或函数评估。评估脚本时使用了类似的基于堆栈的方法。请注意，脚本可以并且几乎总是包含以@字符开头的JSONPath表达式。其中一个有趣的方面是，一个过滤器可以包含其他过滤器。OJG支持嵌套过滤器。

JSONPath旅程中最令人难忘的部分必须是求值堆栈。这样做效果很好，能够支持所有不同的片段类型。

一旦GenericData类型显然不会直接支持JSONPath，就会在旅途中添加一些额外内容。原始计划将AsInt()等函数作为Node接口的一部分。随着这一点不再合理，ALT套餐就成了旅程的一部分。它将用于转换类型以及更改现有类型。让这次旅行的最后部分更有趣的是，ALT包是编组和解组类型发挥作用的地方，但使用的名称是重组和分解，因为操作是获取GO类型并将这些对象分解成简单或通用的数据。相反的是将简单的数据库重新组合成它们的原始类型。这采用了OJ for Ruby中使用的方法，当类型名称编码在分解的数据中时。由于数据类型包含在数据本身中，因此它是自描述的，可用于重组包含接口成员的类型。

需要权衡的是，JSON不能直接解析成GO类型，必须首先通过中间数据结构。不过，这也有好的一面。现在，任何简单或通用数据都可以用于重组对象，而不仅仅是JSON字符串。

alt.GenAlter()函数很有趣，因为它可以修改片类型，然后在不进行外部分配的情况下重置成员。

基准测试有助于调整和选择最有利的实现方法。通过这些基准，我们学到了许多教训。通过运行cmd/Benchmark命令可以查看最终的基准测试结果。在Benchmark s.md上查看结果。

以下是基准测试的一个片段。注意：括号中的枚举数越高越好，括号中的数字是OjG组件与Gojson包组件的比率。

解析JSONjson.Unmarshal：7104 ns/op(1.00x)4808 B/op(1.00x)90 allocs/op(1.00x)oj.解析：4518 ns/op(1.57x)3984 B/op(1.21x)86 allocs/op(1.05x)oj.GenParse：4623 ns/op(1.54x)3984 B/op(1.21x)86 allocs/op(1.05x)。(1.00x)oj.JSON：436 ns/op(6.00x)131 B/op(7.57x)4 allocs/op(5.50x)oj.Write：455 ns/op(5.75x)131 B/op(7.57x)4 allocs/op(5.50x)。

当然，我们都知道函数调用在任何语言中都会增加一些开销。Inc.表示，使用内联函数的开销非常小或根本不存在。围棋就不是这样了。进行函数调用有相当大的开销，如果函数调用包含任何类型的上下文，比如是某一类型的函数，则开销会更高。这种观察(虽然令人失望)驱动了很多解析器和JSONPath评估代码。为了美观和组织良好的代码，强烈建议使用函数，但是要获得高性能，请找到减少函数调用的方法。

解析器的实现包含大量重复代码。

..