高性能Java解析器实现过程详解

澳门新葡亰网站注册 8

在某些情况下,你可能需要在Java中实现你自己的数据或语言解析器,也许是这种数据格式或语言缺乏标准的Java或开源解析器可以使用。或者虽然有现成的解析器实现,但它们要么太慢,要么太占内存,要么就是没有符合你所需要的特性。又或者是某个开源的解析器存在缺陷,要么是某个开源解析器的项目中止了,原因不一而足。不过无论原因是什么,总之事实就是你必须要自己去实现这个解析器。

如果你没有指定数据或语言标准的或开源的Java解析器,
可能经常要用Java实现你自己的数据或语言解析器。或者,可能有很多解析器可选,但是要么太慢,要么太耗内存,或者没有你需要的特定功能。或者开源解析器存在缺陷,或者开源解析器项目被取消诸如此类原因。上述原因都没有你将需要实现你自己的解析器的事实重要。

当你必须自己实现一个解析器时,你对它的期望会有很多,包括性能良好、灵活、特性丰富、方便使用,以及便于维护等等。说到底,这也是你自己的代码。在本文中,我将为你介绍在Java中实现高性能解析器的一种方式,这种方法并且独一无二,但难度适中,不仅实现了高性能,而且它的模块化设计方式也比较合理。这种设计是受到了VTD-XML的设计方式的启发,后者是我所见过的最快的Java
XML解析器,比起StAX和SAX这两种标准的Java XML解析器都要快上许多。

当你必需实现自己的解析器时,你会希望它有良好表现,灵活,功能丰富,易于使用,最后但更重要是易于实现,毕竟你的名字会出现在代码中。本文中,我将介绍一种用Java实现高性能解析器的方式。该方法不具排他性,它是简约的,并实现了高性能和合理的模块化设计。该设计灵感来源于VTD-XML
,我所见到的最快的java XML解析器,比StAX和SAX Java标准XML解析器更快。

两种基本的解析器类型

为解析器进行分类的方式有好几种,在这里我将解析器分为两种基础类型:

  • 顺序访问解析器
  • 随机访问解析器

顺序访问是指解析器对进行数据进行解析,在数据解析完成后将其转交给数据处理器(processor)的过程。数据处理器只能访问当前正在进行解析的数据,它既不能访问已解析过的数据,也不能访问等待解析的数据。这种解析器也被称为基于事件的解析器,例如SAX和StAX解析器。

而随机访问解析器是指解析器允许数据处理代码可以随意访问正在进行解析的数据之前和之后的任意数据(随机访问)。这种解析器的例子有XML
DOM解析器。

下图展示了顺序访问解析器与随机访问解析器的不同之处:

澳门新葡亰网站注册 1

顺序访问解析器只能让你访问当前正在解析的“视窗”或“事件”,而随机访问解析器允许你任意地浏览所有已解析数据。

两个基本解析器类型

解析器有多种分类方式。在这里,我只比较两个基本解析器类型的区别:

  • 顺序访问解析器(Sequential access parser)
  • 随机访问解析器(Random access parser)

顺序访问意思是解析器解析数据,解析完毕后将解析数据移交给数据处理器。数据处理器只访问当前已解析过的数据;它不能回头处理先前的数据和处理前面的数据。顺序访问解析器已经很常见,甚至作为基准解析器,SAX和StAX解析器就是最知名的例子。

随机访问解析器是可以在已解析的数据上或让数据处理代码向前和向后(随机访问)。随机访问解析器例子见XML
DOM解析器。

澳门新葡亰网站注册 2

顺序访问解析器只能让你在文档流中访问刚解析过的“窗口”或“事件”,而随机访问解析器允许你按照想要的方式访问遍历。

设计概况

我在这里所介绍的解析器设计属于随机访问解析器。

随机访问解析器的实现通常会慢于顺序访问解析器,因为它们一般都会为已解析数据创建某种对象树,数据处理代码将通过这棵树对数据进行访问。创建这种对象树不仅要花费较长的CPU时间,消耗的内存也很大。

相对于从已解析数据中创建一棵对象树的方式,另一种性能更佳的方式是为原来的数据缓冲区建立一个对应的索引缓冲区,这些索引会指向在已解析数据中找到的元素的起点与终点。数据处理代码此时不再通过对象树访问数据,而是直接在包括了原始数据的缓冲区中访问已解析数据。以下是对这两种处理方式的图示:

澳门新葡亰网站注册 3

由于我找不到一个更好的名字,因此我将这种方式简单地命名为“索引覆盖解析器”(Index
Overlay
Parser)。该解析器为原始数据创建了一个覆盖于其上的索引。这种方式让人联想起数据库索引将数据保存在磁盘的方式,它为原始的、未处理的数据创建了一个索引,以实现更快地浏览和搜索数据的目的。

如同我之前所说的,这种设计方式是受到了VTD-XML(VTD是指虚拟令牌描述符)的启发,因此你也可以把这种解析器称为虚拟令牌描述符解析器。但我还是倾向于索引覆盖这个名字,因为它表现了虚拟令牌描述符的本质,即对原始数据建立的索引。

设计概要

我这里介绍的解析器设计属于随机访问变种。

随机访问解析器实现总是比顺序访问解析器慢一些,这是因为它们一般建立在某种已解析数据对象树上,数据处理器能访问上述数据。创建对象树实际上在CPU时钟上是慢的,并且耗费大量内存。

代替在解析数据上构建对象树,更高性能的方式是建立指向原始数据缓存的索引缓存。索引指向已解析数据的元素起始点和终点。代替通过对象树访问数据,数据处理代码直接在含有原始数据的缓存中访问已解析数据。如下是两种方法的示意图:

澳门新葡亰网站注册 4

因为没找到更好的名字,我就叫该解析器为“索引叠加解析器”。该解析器在原始数据上新建了一个索引叠加层。这个让人想起数据库构建存储在硬盘上的数据索引的方式。它在原始未处理的数据上创建了指针,让浏览和搜索数据更快。

如前所说,该设计受VTD-XML的启发, VTD是虚拟令牌描述符(Virtual Token
Descriptor)的英文缩写。因此,你可以叫它虚拟令牌描述符解析器。不过,我更喜欢索引叠加的命名,因为这是虚拟令牌描述符代表,在原始数据上的索引。

解析器设计概要

一种常规的解析器设计方式将解析过程分为两步。第一步是将数据分解为内聚的令牌,一个令牌是已解析数据中的一个或多个字节或字符。第二步是对令牌进行解释,并根据这些令牌构建更大的元素。以下是这两个步骤的图示:

澳门新葡亰网站注册 5

这里的元素并不一定是指XML元素(虽然XML元素也是解析器元素),而是指构成解析数据的更大的“数据元素”。比如说,在一个XML文档中元素代表了XML元素,而在一个JSON文档中元素则代表了JSON对象,等等。

举例来说,<myelement>这个字符串可以被分解为以下几个令牌:

  • <
  • myelement
  • >

一旦数据被分解为令牌,解析器就能够相对容易地了解它的意义,并且决定这些令牌构成的更大的元素。解析器就能够理解一个XML元素是由一个’<’令牌开始,随后是一个字符串(即元素名称),随后有可能是一些属性,最后以一个’>’令牌结尾。

常规解析器设计

一般解析器设计会将解析过程分为两步。第一步将数据分解为内聚的令牌,令牌是一个或多个已解析数据的字节或字符。第二步解释这些令牌并基于这些令牌构建更大的元素。两步示意图如下:

澳门新葡亰网站注册 6

图中元素并不是指XML元素(尽管XML元素也解析元素),而更大“数据元素”构造了已解析数据。在我XML文档中表示XML元素,而在JSON
文档中则表示JSON对象,诸如此类。

举例说明,字符串将被分解为如下令牌:

<
myelement
>

一旦数据分解为多个令牌,解析器更容易理解它们和判断这些令牌构造的大元素。解析器将会识别XML元素以
‘<’令牌开头后面是字符串令牌(元素名称),然后是一系列可选的属性,最后是‘>’令牌。

索引覆盖解析器设计

在这种解析器的设计方式中也包含了两个步骤:输入数据首先被一个令牌生成器(tokenizer)组件分解为令牌,解析器随后将对令牌进行解析,以决定输入数据的一个更大的元素边界。

你也可以为解析过程加入一个可选的“元素浏览步骤”。如果解析器从解析数据中构建出一棵对象树,它通常会包含在整棵树中进行浏览的链接。如果我们不选择对象树,而是构建出一个元素索引缓冲区,我们也许需要另一个组件以帮助数据处理代码在元素索引缓冲区中进行浏览。

以下是我们的解析器设计的概要:

澳门新葡亰网站注册 7

我们首先将所有数据读入一个数据缓冲区中,为了能够通过在解析过程中创建的索引对原始数据进行随机访问,所有的原始数据必须已经存在于内存中。

第二步,令牌生成器会将数据分解为令牌。令牌生成器内部的某个令牌缓冲区会将该令牌的起点索引、终点索引和令牌类型都保留下来。使用令牌缓冲区使你能够查找之前或之后的令牌,在这种设计中解析器会利用到这一项特性。

第三步,解析器获取了令牌生成器所产生的令牌,根据上下文对其进行验证,并决定它所表示的元素。随后解析器会根据从令牌生成器处获取的令牌构建一个元素索引(即索引覆盖)。解析器会从令牌生成器中一个接一个地获取令牌。因此令牌生成器不必立即将所有数据都分解为令牌,它只需要每次找到一个令牌就行了。

数据处理代码将浏览整个元素缓冲区,利用它访问原始数据。你也可以选择用一个元素浏览组件将元素缓冲区包装起来,使浏览元素缓冲区的工作更加简单。

这种设计不会从解析数据中生成一棵对象树,但它确实生成了一个可浏览的结构,即元素缓冲区,索引(即整数数组)将指向包含了原始数据的数据缓冲区。你可以使用这些索引浏览原始数据缓冲区中的所有数据。

本文的以下部分将分析这种设计的各方面细节。

索引叠加解析器设计

两步方法也将用于我们的解析器设计。输入数据首先由分析器组件分解为多个令牌。
然后解析器解析这些令牌识别输入数据的大元素边界。

你也可以增加可选的第三步骤—“元素导航步骤”到解析过程中。
若解析器从已解析数据中构造对象树,那么对象树一般会包含对象树导航的链接。当我们构建元素索引缓存代替对象树时,我们需要一个独立组件帮助数据处理代码导航元素索引缓存。

我们解析器设计概览参见如下示意图:

澳门新葡亰网站注册 8

我们首先将所有数据读到数据缓存内。为了保证可以通过解析中创建的索引随机访问原始数据,所有原始数据必需放到内存中。

接着,分析器将数据分解为多个令牌。开始索引,结束索引和令牌类型都会保存于分析器中一个内部令牌缓存。使用令牌缓存使其向前和向后访问成为可能,上述情况下解析器需要令牌缓存。

第三步,解析器查找从分析器获取的令牌,在上下文中校验它们,并判断它们表示的元素。然后,解析器基于分析器获取的令牌构造元素索引(索引叠加)。解析器逐一获得来自分析器的令牌。因此,分析器实际上不需要马上将所有数据分解成令牌。而仅仅是在特定时间点找到一个令牌。

数据处理代码能访问元素缓存,并用它访问原始数据。或者,你可能会将数据缓存封装到元素访问组件中,让访问元素缓存更容易。

该设计基于已解析数据构建对象树,但它需建立访问结构—元素缓存,由索引(整型数组)指向含有原始数据的数据缓存。我们能使用这些索引访问存于原始数据缓存的数据。

下面小节将从设计的不同方面更详细地进行介绍。

数据缓冲区

数据缓冲区是一个包括了原始数据的字节字符缓冲区,而令牌缓冲区和元素缓冲区则包含了指向数据缓冲区的索引。

为了实现对解析数据的随机访问,必须以某种形式将它保留在内存中。我们在这里没有选择对象树,而是选择了包含未处理数据本身的数据缓冲区。

将所有数据全部保留在内存中可能会导致对内存的大量消耗。如果你的数据包含了互相独立的元素,例如日志记录,那么将整个日志文件导入内存很可能会造成崩溃。你应该采取的方式是只导入日志文件的一部分,其中至少包含一条完整的日志记录。由于每一条日志记录都可以不依赖于其它日志记录进行解析和处理,你就不需要将整个日志文件在同一时刻加载到内存里了。我在我的文章《使用缓冲区对流进行迭代处理》中描述了如何对一块数据流进行迭代的方式。

数据缓存

数据缓存是含有原始数据的一种字节或字符缓存。令牌缓存和元素缓存持有数据缓存的索引。

为了随机访问解析过了的数据,内存表示上述信息的机制是必要的。我们不使用对象树而是用包含原始数据的数据缓存。

将所有数据放在内存中需消耗大块的内存。若数据含有的元素是相互独立的,如日志记录,将整个日志文件放在内存中将是矫枉过正了。相反,你可以拉大块的日志文件,该文件存有完整的日志记录。因为每个日志记录可完全解析,并且独立于其它日志记录的处理,所以我们不需要在同一时间将整个日志文件放到内存中。在我的文章—“使用缓存迭代访问数据流”中,我已经描述了如何遍历块中的数据流。

令牌生成器与令牌缓冲区

令牌生成器将数据缓冲区分解为令牌,令牌的信息会保存在令牌缓冲区中,包括以下信息:

  • 令牌的位置(起始位置的索引)
  • 令牌长度
  • 令牌类型(可选信息)

以上信息都保存在数组中,这里是一段示例代码:

   public class IndexBuffer {
       public int[]  position = null;
       public int[]  length   = null;
       public byte[] type     = null; 
     /* assuming a max of 256 types (1 byte / type) */
   }

当令牌生成器在数据缓冲区中找到令牌之后,它会将该位置(起始位置的索引)插入position数组、将令牌长度插入length数组,并将令牌类型插入type数组。

如果你不使用这个可选的令牌类型数组,你也可以在需要的时候通过令牌中的数据得出令牌的类型。这是一种性能与内存占用之间的权衡。

标记分析器和标记缓存

分析器将数据缓分解为多个令牌。令牌信息存储在令牌缓存中,包含如下内容:

  • 令牌定位(起始索引)
  • 令牌长度
  • 令牌类型 (可选)

上述信息放在数组中。如下实例说明处理逻辑:

public class IndexBuffer {
    public int[] position = null;
    public int[] length = null;
    public byte[] type = null; 
/* assuming a max of 256 types (1 byte / type) */
}

当分析器找到数据缓存中令牌时,它将构建位置数组的起始索引位置,长度数组的令牌长度和类型数组的令牌类型。

若不使用可选的令牌类型数组,你仍能通过查看令牌数据来区分令牌类型。这是性能和内存消耗的权衡。

解析器

解析器本质上与令牌生成器非常类似,不同的是它将令牌作为输入,而将元素索引作为输出。和令牌类似,每个元素由它的位置(起始位置的索引)、长度和可选的元素类型几部分组成。用以保存这些数字的结构与保存令牌的结构是完全一样的。

在这里type数组仍然是可选的。如果你能够从元素的首个字节或字符中很容易地判断元素的类型,那就无需特意保存元素的类型信息。

在元素缓冲区中所包含的元素的精确粒度取决于被解析的数据,以及之后将对数据进行处理的代码段。举例来说,如果你要实现一个XML解析器,你可能会选择将每个开始标签、属性和结束标签作为独立的“解析元素”。

解析器

解析器是在性质上与分析器类似,只不过它采用令牌作为输入和输出的元素索引。如同使用令牌,一个元素由它的位置(起始索引),长度,以及可选的元素类型来决定。这些数字存储在与存储令牌相同的结构中。

再者,类型数组是可选的。若你很容易基于元素的第一个字节或字符确定元素类型,你不必存储元素类型。

澳门新葡亰网站注册,元素缓存中标记的要素精确粒度取决于数据被解析,以及需要后面数据处理的代码。例如,如果你实现一个XML解析器,你可能会标记为每个“解析器元素”的开始标签,
属性和结束标签。

元素缓冲区(索引)

解析器所生成的元素缓冲区包含了引向原始数据的索引。这些索引会记录解析器在数据中所找到的元素的位置(起始位置的索引)、长度和类型信息。你可以利用这些索引实现在原始数据的任意浏览。

从之前的IndexBuffer代码段中,你可以看到元素缓冲区为每个元素保留了9个字节的缓冲区,4个字节用于保存位置、另4个字节用于保存令牌长度,最后1个字节用于保存令牌类型。

你或许能够通过某些手段来减少IndexBuffer的内存占用。举例来说,如果你确认其中的元素不超过65535个字节,你就可以选择使用short短整数,而不是常规的int整数来保存令牌长度信息,这样每个元素都可以节省两个字节,将整个内存占用减少至每个元素七个字节。

此外,如果你确认被解析文件的大小不会超过16,777,216个字节,那你只需要三个字节来保存位置信息(起始位置的索引)。那么在position数组中的每个整数的第四个字节就可以用来保存元素类型,这样就可以完全不用使用单独的type数组了。如果你的令牌类型不超过128种,你就可以使用七个字节、而不是八个字节来保存令牌类型,这样一来你就可以使用25个比特来保存位置,使得最大的位置可以达到33,554,432。如果你的令牌类型少于64种,你还可以空出一个比特以保存位置信息。

VTD-XML实际上将所有这些信息都保存在一个长整数类型中,以达到节省空间的目的。为了将几个分离的字段加载成为一个单独的整数或者长整数,需要进行一些比特操作,也因此会降低一些速度,但好处是节省了部分内存,这就是一种资源的权衡。

元素缓存(索引)

解析器生成带有指向元数据的索引的元素缓存。该索引标记解析器从数据中获取的元素的位置(起始索引),长度和类型。你可以使用这些索引来访问原始数据。

看一看上文的IndexBuffer代码,你就知道元素缓存每个元素使用9字节;四个字节标记位置,四个自己是令牌长度,一个字节是令牌类型。

你可以减少IndexBuffer
的内存消耗。例如,如果你知道元素从不会超过65,536字节,那么你可以用短整型数组代替整型来存令牌长度。这将每个元素节省两个字节,使内存消耗降低为每个元素7个字节。

此外,如果知道将解析这些文件长度从不会超过16,777,216字节,你只需要三个字节标识位置(起始索引)。在位置数组中,每一整型第四字节可以保存元素类型,省去了一个类型数组。如果您有少于128的令牌类型,您可以使用7位的令牌类型而不是八个。这使您可以花25位在位置上,这增加了位置范围最大到33,554,432。如果您令牌类型少于64,您可以安排另一个位给位置,诸如此类。

VTD-XML实际上会将所有这些信息压缩成一个Long型,以节省空间。处理速度会有损失,因为额外的位操作收拾单独字段到单个整型或long型中,不过你可以节省一些内存。总而言之,这是一个权衡。