注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

yeye55的博客

编程就象品一杯清茶,清淡却又深厚。

 
 
 

日志

 
 
关于我

宅男一只,喜欢编程。没事的时候就喜欢抱着电脑看看电影、看看动漫、听听音乐、打打网游、逛逛论坛。清静的时候喜欢专研编程技术,但是发现自己至今仍然只是一只三脚猫。

网易考拉推荐

PPM压缩算法的分析与实现 - 第四章 内存管理  

2011-11-08 10:26:56|  分类: 数据压缩算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

  本论文题目:PPM压缩算法的分析与实现,作者:叶叶,于2011年11月8日在网易博客上发表。页面地址:http://yeye55blog.blog.163.com/blog/static/197241021201110715759577/ 。本论文全文及相关配套程序可以在上述页面中下载。请尊重他人劳动成果,转载或引用时请注明出处。

第四章 内存管理

4.1 前言

  从算法结构的角度来讲,内存管理不属于PPM算法的一部份。但是在PPM算法实现的时候通常都涉及了内存管理的实现。所以本章将介绍与PPM算法相关的内存管理器的实现。

  PPM算法建模的时候需要大量的使用到动态内存。动态内存就是指在程序的运行过程中,可以动态分配、动态回收的内存块。动态内存的四种操作分别为分配(Allocate)、释放(Deallocate)、扩展(Expand)和收缩(Shrink)。也有资料将后面的两种动态内存操作统称为重分配(Reallocate)。例如对于Delphi 7.0可以使用GetMem函数分配内存块,可以使用FreeMem函数释放内存块,还可以使用ReallocMem函数对已分配的内存块进行扩展或收缩。像Delphi 7.0中这一类的内存管理函数都是以字节为单位进行内存分配的。最少1个字节,最多数兆字节,只要在进程中还有空余的虚拟内存都可以进行分配。通常将这样的内存管理程序称为通用内存管理器(Universal Memory Manager)。通用内存管理器针对一般的程序应用而设计。只要程序需要使用到动态内存,都可以利用通用内存管理器来实现。通用内存管理器的缺点是性能相对较低,无法完成一些特殊的应用。与通用内存管理器相对应的是专用内存管理器(Dedicated Memory Manager)。专用内存管理器专门针对某项应用而设计,所以在性能上可以做到最好。专用内存管理器的缺点是不具备通用性。如果修改了程序的应用,就有可能需要修改对应的专用内存管理器。

  本文第二章中的方案2.1就是使用Delphi 7.0中的上述3个内存管理函数来进行内存管理的。通过表3.1中的数据可以发现,方案2.1在建模时生成了大量的上下文节点。这些上下文节点占用的内存都很“零碎”。使用通用内存管理器分配和回收大量零碎的内存效率并不是很高。而且当编码结束时,需要对所有分配的内存进行释放。Trie结构是一个树结构,释放时需要对树结构中的所有节点进行遍历,逐一释放这些节点。这个释放过程将十分耗时。为了说明这一点,现在使用5阶的方案2.1对语料库[14]中的18个文件进行压缩。计算压缩过程中所使用的耗时,同时计算编码结束后释放模型的耗时。测试结果如表4.1所示。

文件 压缩耗时
(毫秒)
释放模型耗时
(毫秒)
释放模型耗时
所占比例
(%)
Bib 141    47    33.33
book1 844 172 20.38
book2 625 141 22.56
geo 484 156 32.23
news 562 171 30.43
obj1 94 16 17.02
obj2 437 141 32.27
paper1 94 16 17.02
paper2 125 31 24.80
paper3 94 31 32.98
paper4 47 0 00.00
paper5 46 0 00.00
paper6 78 32 41.03
pic 344 63 18.31
progc 78 31 39.74
progl 78 16 20.51
progp 79 15 18.99
trans 94 16 17.02
总计 4344 1095 25.21

表4.1 方案2.1的压缩耗时和比例

  从表4.1的总计数据上来看,编码结束时释放模型的耗时占到整个算法耗时的25.21%。这是一个很高的比例。不仅如此,测试表明随着阶数的提高这一比例还会成倍的提高。另外,考虑到PPM算法建模时需要管理大量的零碎内存。所以为PPM算法量身定做一款专用内存管理器是十分必要的。这个专用内存管理器必需符合PPM算法建模的特点。可以快速的分配和释放零碎的内存。同时在编码结束时,还可以快速的释放整个模型。

  当使用CT结构建模时需要分配三种类型的内存。第一种就是符号列表。符号列表实际上是一个字节数组。最小的单位是字节。在初始化模型时就需要分配符号列表。然后随着编码的进行,符号列表会逐步扩展。每次扩展1个字节。符号列表在内存中的位置最好不要随便修改,因为有很多指针正指向符号列表的不同位置。

  第二种是上下文节点(TNode)。一个上下文节点占用12个字节的内存。上下文节点不需要扩展,也不需要收缩。一旦分配只有等到编码结束时才进行释放。上下文节点在内存中的位置同样不能随便修改。因为上下文节点之间彼此使用指针相连。

  第三种是节点项(TItem)。节点项实际上是按节点项数组(TItemAry)进行分配的。分配节点项数组时,是以节点项的个数为单位进行分配的。一个节点项占用6个字节的内存。但是我们不分配1个单位长度的节点项数组,因为我们使用了内存共用方案。所以分配节点项数组时,最少分配2个单位长度,最多分配256个单位长度。当把一个符号添加到上下文节点中时。如果当前的上下文为二元上下文,那么需要分配2个单位长度的节点项数组。如果当前的上下文为多元上下文,那么需要对当前的节点项数组进行扩展。每次扩展节点项数组时,总是扩展一个单位,即,6个字节。在最高阶上下文中削减频度时。如果出现了零频符号,那么需要对当前的节点项数组进行收缩。收缩多少个单位,视零频符号的个数而定。如果在削减后只剩下了一个非零频符号,那么需要释放当前的节点项数组。最后,在编码全部结束时还需要释放所有分配的节点项数组。可以看出节点项的内存管理是最复杂的。

  针对PPM算法使用的专用内存管理器将根据模型的上述特点而进行设计。本章将会介绍这个专用内存管理器是如何设计和实现的。

4.2 定量内存

  在PPM算法实现的时候,随着阶数的提高以及数据长度的增加,模型占用的内存会越来越大。模型占用的内存越大生成的节点也越多,逐一释放这些节点的耗时也越长。解决这些问题的方法是使用定量内存(Ration Memory)。使用定量内存时需要指定一个定量,在初始化模型前根据这个定量的大小来分配一块内存。这块内存就被称为定量内存。在随后建立模型的过程中,只能从定量内存中分配内存。如果定量内存出现溢出(Overflow),没有足够的剩余空间来完成分配。那么就对模型进行重置(Restart),重置后的模型将返回到初始状态。由于构成模型的内存都是从定量内存中分配的,在编码结束时只需要直接释放掉定量内存即可,没必要对模型中的节点进行遍历。使用定量内存时,相当于将模型占用的内存空间限制在定量内存的空间内。这样一方面可以限制模型的内存使用,另一方面可以“瞬间”释放掉模型占用的内存。

  定量内存本身可以像普通的内存块一样,从系统中进行分配和释放。比如在Delphi 7.0下,在编码开始前我们可以调用GetMem函数来分配定量内存,在编码结束后我们可以调用FreeMem函数来释放定量内存。从定量内存中分配的内存块,相互之间有着复杂的指针关系。所以,在编码过程中不能重分配定量内存,否则就会出现指针错误。这就意味着,在编码前就要确定好定量内存的大小,并且在编码过程中保持不变。如果出现内存溢出,只能通过重置定量内存来解决。

  从定量内存中分配内存时。根据模型的特点,我们可以将符号列表安排在定量内存的首部。而上下文节点和节点项数组从定量内存的尾部向前分配。这样我们需要使用两个指针来指向定量内存。指针SymPos指向符号列表最末尾的空位,指针AllocPos指向当前分配内存块的位置。一个定量大小为Max的定量内存如图4.1所示。

图4.1 定量内存中的内存分配

  当我们进行初始化的时候,指针SymPos指向定量内存的起始位置,指针AllocPos指向定量内存的末尾位置。如果需要对符号列表进行扩展,只需要将SymPos增加1个字节。如果需要从定量内存中分配上下文节点或节点项数组,只需要将AllocPos减少相应的字节。从定量内存中分配内存时,需要时刻检查SymPos与AllocPos之间的位置关系。在分配内存后,如果出现SymPos ≥ AllocPos的情况,那么说明定量内存出现了溢出。此时需要对定量内存进行重置。重置定量内存实际上很简单,只需要将指针SymPos重新指向定量内存的起始位置,同时将指针AllocPos重新指向定量内存的末尾位置即可。

  从上面可以看出定量内存的操作十分便捷。不仅如此,定量内存还有助于判断指针的指向。对一个匹配上下文进行更新的时候,需要判断当前符号对应的TItem.Link成员是否指向符号列表。在定量内存中,符号列表分配在定量内存的首部,而上下文节点分配在定量内存的尾部。所以当出现Link ≤ SymPos的情况时,我们可以确定Link成员指向的是符号列表。如果情况相反,可以确定Link成员指向的是上下文节点。

  使用定量内存时必需注意一点。在编码和解码的时候必需使用相同大小的定量内存。因为一旦定量内存溢出就需要重置模型。如果在编码和解码的时候使用不同大小的定量内存,就有可能造成在不同的时刻进行重置模型,从而出现解码错误。在具体实现的时候,一般将当前使用的定量内存的大小保存到输出数据中。在解码的时候,从输入数据中提取定量内存大小的设置信息。这样可以确保在编码和解码的时候使用相同大小的定量内存。

  使用定量内存也存在着一些缺点。当定量内存溢出并重置模型时,模型中所有的统计信息都会丢失。重置模型后,会从一个没有包含统计信息的初始模型开始编码。模型中累积的频度统计信息对于PPM算法的压缩率至关重要。如果频繁的出现重置模型,会严重的影响PPM算法的压缩率。最好的办法是使用一个足够大的定量内存,使得在编码过程中不会出现重置模型的情况。但是在编码前通常很难判断出模型占用内存的大小。在具体应用的时候,一般根据经验使用数兆至数十兆大小的定量内存。当然这也带来了另外一个问题,如果编码长度较小的数据通常不需要这么大的定量内存,这会造成内存资源的浪费。虽然使用通用内存管理器可以做到使用多少内存就分配多少内存,但是通用内存管理器的性能太低。所以在PPM算法实现的时候,通常使用基于定量内存的专用内存管理器。

4.3 预分配

  使用了定量内存之后,符号列表的扩展操作变得十分简单,只需要将指针SymPos增加1个字节即可。其它需要进行扩展操作的内存块就只剩下了节点项数组。在进行内存块的扩展操作时,通常无法在“原地”进行扩展。因为内存块后面的内存可能已经被分配出去了。所以进行内存块的扩展操作通常需要三个步骤。第一步,分配一个所需大小的新内存块。第二步,将原内存块中的数据拷贝到新内存块中。第三步,释放原内存块。可以看出每次进行扩展操作都涉及到数据的拷贝。如果频繁的进行扩展操作或者原内存块中的数据量较大,这都会影响到算法的性能。解决这个问题的方法是使用预分配。预分配就是在每次分配内存块时,预先多分配一些内存空间。下次如果需要对内存块进行扩展。只要扩展的大小在多分配内存的大小的范围内,就不需要再分配内存,拷贝数据,而是直接返回原内存块即可。如果扩展的大小超过了多分配内存的大小,再进行真正的扩展操作。

  预分配方案实际上是用空间交换时间。多分配出去的内存对于调用程序来说是透明的。调用程序并不知道内存管理器多分配了多少内存。多分配的内存对于内存管理器来说是已经分配出去的内存,内存管理器不能再将它分配给其它程序。但是调用程序又不知道这些内存的存在。我们将那些多分配出去的,后来又没有使用到的内存称为空占内存。在程序结束的时候多分配的内存恰好全部用完的可能性几乎没有。所以说,只要进行预分配就会出现空占内存。此时选择适合的预分配的策略就显得非常的重要。预分配的策略必需能够在空间上和时间上达到平衡。

  节点项数组的分配是以节点项的个数为单位的,多分配内存时也要满足这个要求。分配节点项数组时,最少分配2个单位,最多分配256个单位。这样一共有255种等级的内存块。一种比较简单的策略就是只分配偶数个单位的内存块。当需要分配奇数个单位的内存块时,就多分配1个单位的内存空间。当然还可以对这个策略进行优化。观察PPM算法的模型可以发现,包含较少符号的上下文数量较多,包含较多符号的上下文数量较少。这就意味着,拥有较多单位的节点项数组占有较少的比例。那么在分配的时候,对于拥有较多单位的节点项数组多分配较多的内存。之所以这样做是因为。一方面,这一类的节点项数组出现的数量较少。有可能造成的空占内存也较小。另一方面,拥有较多单位的节点项数组扩展时,需要拷贝的数据也较多。按照这样的策略,我们可以把内存块划分成37种等级。并对这些等级的内存块从0到36进行编号。内存块的划分情况如表4.2所示。

编号 范围 编号 范围 编号 范围 编号 范围
0 2, 10 21, 22, 20 41, 42, 30 103, …, 118,
1 3, 4, 11 23, 24, 21 43, 44, 31 119, …, 136,
2 5, 6, 12 25, 26, 22 45, 46, 32 137, …, 156,
3 7, 8, 13 27, 28, 23 47, 48, 33 157, …, 178,
4 9, 10, 14 29, 30, 24 49, …, 52, 34 179, …, 202,
5 11, 12, 15 31, 32, 25 53, …, 58, 35 203, …, 228,
6 13, 14, 16 33, 34, 26 59, …, 66, 36 229, …, 256,
7 15, 16, 17 35, 36, 27 67, …, 76,
8 17, 18, 18 37, 38, 28 77, …, 88,
9 19, 20, 19 39, 40, 29 89, …, 102,

表4.2 内存块的划分

  从表4.2的数据中可以看出,分配时总是分配偶数个单位的节点项数组。同时对于拥有较多单位的节点项数组多分配较多的内存。测试表明,除了二元上下文以外,模型中出现数量最多的就是包含了2个符号的上下文。所以在分配时,对于2个单位的内存块不多分配内存。以防止出现过多的空占内存。2个单位的内存块编号为0。另外从1号到23号的内存块,对于奇数单位总是多分配1个单位的内存。例如,需要分配15个单位的内存块时。查表4.2可得,这个内存块是7号内存块。那么我们实际分配16个单位的内存块。对于24号到36号的内存块,其多分配的内存逐步增加。例如,对于27号内存块,只要需要分配的单位在67至76的范围内。那么都分配76个单位的内存。如果此时需要分配67个单位的内存块,那么将多分配9个单位的内存。

  还有一点需要说明,在内存管理的过程中通常需要分割(Split)内存块。即,将大块的内存块分割成小块的内存块。在拟定预分配策略的时候,必需保证划分出来的内存块是可以被完整分割的。一块大块的内存块分割出一块小块的内存块后,其剩余部份必需可以分割成完整的内存块。否则就会出现无法使用的内存碎片。表4.2中的策略就可以满足这个要求。例如,33号内存块有178个单位大小。从中分割出一个更小的内存块。比如26号内存块有66个单位大小。那么剩余的部份有112个单位大小。可以分割成4号10个单位和29号102个单位两个内存块。如果使用了错误的策略,例如分割后出现1个单位的内存块。我们不分配这么小的内存块,那么这个内存块就会被浪费。形成无法使用的碎片。

  在实现预分配方案的时候,一般需要两张查询表。一张查询表根据单位个数查询对应的内存块编号。例如,在表4.2中根据59个单位可以查询到编号为26的内存块。另外一张查询表根据内存块编号查询对应的单位个数。例如,在表4.2中根据编号26可以查询到对应的内存块需要分配66个单位的内存。查询表反应出内存块的划分情况。在操作过程中,需要频繁的访问查询表。所以查询表可以设置为常量数组。这个常量数组如何生成,请参考本文的附录A,这里不再详述。

  在进行扩展操作的时候,需要查询扩展前单位的个数和扩展后单位的个数。如果它们被划分到了同一等级,那么就不需要进行扩展操作直接返回原内存块即可。反之,如果没有划分在同一等级,再进行扩展操作。扩展节点项数组时总是扩展1个单位,即6个字节。根据我们的划分策略可以发现。需要扩展内存块时,原内存块总是偶数个单位。1个单位等于6个字节,偶数个单位的字节数据量正好可以被4整除。所以拷贝数据时可以一次拷贝4个字节,没必要一个字节一个字节的拷贝。这样做可以提高算法的速度。

  节点项数组除了需要进行扩展操作还需要进行收缩操作。收缩操作与扩展操作类似,同样需要查询收缩前单位的个数和收缩后单位的个数。如果它们被划分到了同一等级,那么不需要进行收缩操作直接返回原内存块即可。反之,如果没有划分在同一等级,那么可以直接对原内存块进行分割。将原内存块中空余的部份分割出来,并释放掉。这样做可以避免进行拷贝操作,有助于提高算法的速度。

4.4 回收池

  除了扩展操作与收缩操作以外,节点项数组还需要进行释放操作。在削减频度时有可能需要释放节点项数组。另外,在扩展节点项数组时还需要释放掉原内存块。当前释放的内存块在下次分配时就有可能使用到。所以可以将已经回收的相同大小的内存块用指针链接起来,形成一个链表。这样的链表被称为内存池。在我们实现的内存管理器中,把内存块分成了37个等级。那么我们需要使用37个内存池,放置不同等级的内存块。我们将这个结构称为回收池。每次释放内存块时,就直接将内存块放入到回收池中。在具体实现的时候,可以使用一个单向链表来链接内存块。同时使用一个数组来保存这些链表的首节点指针。回收池的内存结构如图4.2所示。实现图4.2中的内存结构的定义如代码4.1所示。

图4.2 回收池的内存结构

01 type
02     //链表节点
03     PMemNode = ^TMemNode;
04     TMemNode = record
05         Next : PMemNode; //下一个链表节点
06     end;
07
08 var
09     Pools : array [0..36] of PMemNode; //回收池,放置空闲内存块

代码4.1 回收池结构的定义

  在代码4.1中的链表节点TMemNode虽然只有4个字节,但是它对应的内存块的大小可不止这些。TMemNode对应的内存块的大小根据它在哪个内存池中来判断。比如在0号内存池中的内存块的大小都是12个字节。一条链表对应着一个内存池。数组Pools中的每个元素按照其编号指向对应的链表首节点。如果数组Pools中的某个元素为nil,那么表示对应的内存池不存在。初始时,回收池为空,所以数组Pools中的所有元素都为nil。另外,在重置定量内存的时候,需要回收所有的内存块。此时需要将数组Pools中的所有元素都设置为nil。

  释放一个内存块时,需要根据这个内存块的单位个数查询它的编号。根据编号确定这个内存块属于哪个内存池。然后将内存块链接到对应的链表中。这样一个释放操作就完成了,对应的内存块就被我们给回收了。可以看得出来,释放一个内存块还是很简单的。

  但是,分配一个内存块就没有这么简单了。分配一个内存块时,同样需要根据这个内存块的单位个数查询它的编号。并根据编号确定这个内存块属于哪个内存池。如果回收池数组中对应的元素不为nil,表明有对应的内存池存在。那么从对应的链表中摘取一个节点并返回,这就完成了分配操作。但是,如果对应的内存池不存在。那么我们需要顺着回收池数组向下查找可用的内存池。如果可以找的到,那么同样摘取一个节点出来。注意,此时的内存块比我们需要分配的内存块更大。我们需要对这个内存块进行分割。分割出我们需要分配的部份,然后将剩余的部份重新放回到回收池中。另外,如果没有找到可用的内存池,说明回收池中没有合适的内存块。这时,需要从定量内存中分配内存块。分配时,将指针AllocPos减去相应的字节数,然后返回AllocPos指向的内存块。进行这个操作时,还必需检查指针SymPos与指针AllocPos之间的位置关系。如果出现溢出,需要将信息反馈给调用程序。告知调用程序:定量内存溢出需要进行重置。可以看得出来,分配一个内存块比释放一个内存块更为复杂。

  注意一点,上面有一个步骤。如果从回收池中取出一个更大的内存块,那么需要对这个内存块进行分割。分割后剩余的部份需要被重新放回到回收池中。在将剩余部份放入到回收池之前,必需对其进行检查。因为剩余的内存块可能不是一个完整的内存块。如果不是,那么需要进行再次分割。最后才能将分割后的完整的内存块放入到回收池中。举例说明。假设我们要分配一个24号52个单位的内存块。但是我们只找到26号66个单位的内存块。分割后剩余内存块的大小是14个单位。查表4.2可得,14个单位的内存块编号为6。那么这个剩余的内存块可以直接放入到6号内存池内。再假设,我们要分配一个34号202个单位的内存块。但是我们只找到36号256个单位的内存块。分割后剩余内存块的大小是54个单位。查表4.2可以发现,没有与54个单位对应的内存块。那么这个内存块需要再次分割。54个单位可以分割成0号2个单位和24号52个单位两个内存块。分割后再将这两个内存块分别放入到回收池中。观察表4.2中的内存块划分情况可以发现。如果需要对剩余内存块进行再次分割,最多只要分割成2个内存块就可以满足要求。根据这个规律,在分割剩余内存块的时候。应该尽量让一个内存块尽可能的小,而让另一个内存块尽可能的大。尽量避免把内存块分割的太零碎。从这里也可以看出,在拟定内存块的划分策略的时候。必需保证内存块都是可以被完整分割的。否则内存块的分配操作会变得很麻烦。

  除了节点项数组以外,另外一个需要分配的内存块是上下文节点。一个上下文节点为12个字节。我们注意到,2个单位的节点项数组也是12个字节。而且分配2个单位的节点项数组时不会多分配内存。也就是说不会产生空占内存。那么分配一个上下文节点时,可以把它当成分配2个单位的节点项数组来处理。这样做可以简化操作,同时也有助于提高回收池中内存块的使用率。

4.5 碎片整理

  首先让我们来看一个例子。假设现在要分配2个单位的内存块A。在回收池中没有可用的内存块,于是我们从定量内存中分配内存块A。紧接着,又要分配2个单位的内存块B。于是内存块B同样从定量内存中分配。注意,此时内存块A和内存块B在定量内存中是相互连续的。假设在随后的使用中,内存块A和内存块B被释放了。于是它们被放入到回收池中。其内存分布如图4.3所示。如果回收池中只有这两块内存,而现在要分配4个单位的内存块C。那么我们仍然需要从定量内存中分配。因为内存块A和内存块B的大小无法满足要求。不过我们注意到,如果能把内存块A和内存块B合并起来,那么内存块C完全可以从回收池中分配。但是,在回收池中内存块A和内存块B是相互独立的。它们被看成是2块2个单位的内存块,被放置在0号内存池中。而不是被看成1块4个单位的内存块。那么内存块A和内存块B就成为了内存碎片。注意一点,在不同的内存管理器中,对于内存碎片的定义也是不同的。在我们设计的这个内存管理器中,将那些在内存空间中相互连续的,但是在回收池中却相互独立的内存块称为内存碎片。另外,所谓的碎片整理,就是将内存碎片从回收池中取出来并进行合并(Glue),然后再将合并后的内存块重新放回到回收池中的操作过程。

图4.3 内存块A和内存块B

  注意,回收池中的内存碎片仍然是可以使用的。在上面的例子中,如果要分配2个单位的内存块。那么内存块A和内存块B都是可以满足要求的。不过,内存碎片的存在会使回收池中内存块的使用率下降。回收池中内存的大小明明可以满足分配的需要,但是由于碎片的存在只能从定量内存中分配。所以进行碎片整理还是很有必要的。在进行碎片整理的时候,有一个原则必需遵守。那就是,不能移动已经分配出去的内存块。这些内存块通常有复杂的指针关系。如果移动内存块的位置,会使指针作废从而出现程序错误。

  在进行碎片整理的时候,我们需要区分哪些内存块是已经分配出去的内存块,哪些内存块是放置在回收池中的空闲内存块。分析模型的结构与数据可以发现。我们分配出去的内存块有两种,上下文节点和节点项数组。上下文节点的头2个字节对应于TNode.Count成员。由于在模型中不存在空上下文节点,所以Count成员不会为0。另外,节点项数组的头2个字节对应于第1个节点项的TItem.Symbol成员和TItem.Freq成员。由于在模型中不存在零频符号,所以Freq成员同样不会为0。由此我们可以得出这样一个结论:如果一个内存块被分配出去并正在使用,那么这个内存块的头2个字节肯定不会为0。我们可以将空闲内存块的头2个字节设置为0,以此来区分空闲内存块与正在使用的内存块。在进行碎片整理的时候,所使用到的内存块节点的定义如代码4.2所示。

01 type
02     //内存块节点(双向循环链表节点,该节点大小必需等于12字节)
03     PBlock = ^TBlock;
04     TBlock = record
05         Flag : Word; //标记,固定为0,与正在使用的内存块相区别
06         Count : Word; //内存块的大小(个)
07         Prev : PBlock; //上一个内存块
08         Next : PBlock; //下一个内存块
09     end;

代码4.2 内存块节点的定义

  首先注意一点,我们分配出去的内存块最小为2个单位,即12个字节。所以,内存块节点的大小不能超过12个字节。另外注意一点,在回收池结构中我们仍然使用代码4.1中的链表节点TMemNode来链接内存块,因为它比较简单。而代码4.2中的内存块节点TBlock仅在碎片整理时使用。观察代码4.2可以发现,内存块节点TBlock的头2个字节对应于TBlock.Flag成员。实现时需要将这个成员设置为0。另外,在进行碎片整理的时候,需要将回收池中所有的内存块全部都取出来,并链接成一个双向循环链表。所以TBlock.Count成员用来保存对应内存块的大小。内存块都是以节点项的个数为单位进行分配的,所以Count成员的单位是个。

  碎片整理的过程主要分为三步。第一步,将回收池中所有的内存块都取出来,并放入到一个双向循环链表中。由于我们不知道哪些内存块是内存碎片,所以我们需要对回收池中的所有内存块进行操作。在将内存块放入到双向循环链表中时,需要进行一些设置。内存块在回收池中是以TMemNode的格式进行链接的,放入到双向循环链表中时需要设置成TBlock格式。其中TBlock.Flag成员必需设置成0,而TBlock.Count成员需要设置成内存块的大小。

  第二步,对双向循环链表中的内存块进行遍历,合并连续的内存块。当遍历到一个内存块时,我们可以得到一个指向这个内存块的指针。我们将这个内存块称为首个内存块。将指向首个内存块的指针加上首个内存块的字节大小,就可以得到指向下一个连续的内存块的指针。我们将这个内存块称为连续内存块。我们使用TBlock的格式来访问连续内存块。一个连续内存块可能是一个空闲的内存块,也有可能是一个正在使用的内存块。如果对应的TBlock.Flag成员为0,那么这个连续内存块就是一个空闲的内存块。同时我们可以确定这个连续内存块肯定在当前的双向循环链表中。于是我们可以将首个内存块的大小加上连续内存块的大小,并将这个连续内存块从双向循环链表中删除。这样就完成了一次合并操作。合并操作需要不断的进行,直到遇到正在使用的内存块为止。例如在本节开始的例子中,假设内存块A和内存块B都被放入到双向循环链表当中。如果当前遍历到内存块B。由指向内存块B的指针加上内存块B的大小12个字节,就可以得到指向内存块A的指针。内存块B就是首个内存块,内存块A就是连续内存块。显然,内存块A是一个空闲的内存块。将内存块B的大小加上内存块A的大小,那么现在内存块B的大小为4个单位。然后,可以将内存块A从双向循环链表中删除。由指向内存块A的指针加上内存块A的大小,我们可以得到指向下一个连续内存块的指针。从图4.3中可以看出,下一个连续内存块是一个正在使用的内存块。于是,这一轮的合并操作结束,开始遍历双向循环链表中的下一个内存块。

  第三步,再次对双向循环链表中的内存块进行遍历,将内存块放回到回收池中。经过第二步的操作,可以确定双向循环链表中的所有内存块在空间上都是相互不连续的。在将内存块放回到回收池中的时候,需要检查内存块的大小。因为合并后的内存块有很多都是不完整的。对于过大的或者不完整的内存块都需要进行分割。如果一个内存块的大小大于256个单位,那么需要不断的对内存块进行分割。每次分割出256个单位的内存块,不断的进行分割直到内存块的大小小于256个单位。然后还要再次检查内存块是否完整。内存块的划分策略可以保证这些内存块都是可以被完整的分割的。只有完整的内存块才能被放入到回收池中。

  在解决了如何进行碎片整理的问题之后,紧接而来的一个问题就是何时进行碎片整理。这是一个麻烦的问题。从空间性能的角度来说,最好的方案是:每当有内存块被放入到回收池中时,就进行碎片整理。但是这种方案在时间性能上并不理想。从时间性能的角度来说,最好的方案是:永远都不要进行碎片整理。但是这种方案在空间性能上并不理想。所以我们需要一个折中的方案。当回收池中没有可用的内存块时,需要从定量内存中进行分配,我们称之为回收池查找失败。我们可以设定一个阀值,当回收池查找失败的次数达到这个阀值的时候就进行碎片整理。但是,回收池查找失败的原因有很多。有可能是回收池中的碎片较多,也有可能是回收池中的内存块较少。所以可以设置一个限制值,当回收池中的内存块数量低于限制值的时候不进行碎片整理。内存块较少进行碎片整理的效率也不高。综上所述,我们可以确定这样一个方案:当回收池查找失败的次数达到了一个阀值的时候,同时回收池中内存块的数量超过了一个限制值,那么此时将进行碎片整理的操作。

4.6 测试与分析

  将第二章、第三章和本章中介绍的各种方案全部整合起来,我们可以确定一套新的PPM算法的实现方案。这套方案命名为方案4.1(PPMD)。对于方案4.1的描述如下所示。

方案4.1 使用CT结构(Context Trie)进行建模;使用定量内存,并使用自行设计的专用内存管理器对定量内存进行管理;构建模型时使用内存共用方案;削减频度时使用区分削减方案;更新时使用排除更新方案;编码时使用排除符号方案;逃逸估计使用方法D(PPMD)。

  在本节测试中,将对方案4.1中所使用的专用内存管理器的性能进行测试。同时还会进行方案2.1与方案4.1的对比测试。对比测试将在空间、时间、压缩率三个方面上进行。在本节的测试中,统一使用最高5阶的上下文对语料库[14]中的18个文件进行压缩。在使用方案4.1进行测试的时候,设置定量内存的大小为4兆字节(MB)。使用这个定量值可以保证在压缩语料库[14]中的18个文件时,不会出现重置定量内存的情况。

  首先我们对专用内存管理器的性能进行测试。我们设计的这个内存管理器只能分配两种类型的内存,从定量内存首部开始分配的符号列表,以及从定量内存尾部开始分配的内存块。在这里,我们将2个单位的内存块称为小内存块,将大于2个单位的内存块称为大内存块。上下文节点也是按照小内存块来分配。分配小内存块时不会多分配内存,这意味着只有在分配大内存块时才会出现空占内存。另外,在编码完成的时候,在回收池中一般都会留有还未分配出去的内存块。我们称这些内存块为空闲内存。在测试时,我们将统计内存管理器分配的所有内存块的总计字节大小,以及大内存块和空占内存的比例,还有碎片整理的次数和空闲内存的总计字节大小。其测试结果如表4.3所示。

文件 内存块
总计大小
(字节)
大内存块 空占内存 碎片整理
次数
(次)
空闲内存
大小
(字节)
大小
(字节)
比例
(%)
大小
(字节)
比例
(%)
bib 669192 246840 36.89 24312  9.85 0 240
book1 3200064 1570536 49.08 147216  9.37 1 336
book2 2521776 1093908 43.38 104982  9.60 1 228
geo 1294596 565296 43.67 42972  7.60 28 528
news 2599248 1039740 40.00 100338  9.65 0 0
obj1 203292 88812 43.69 7164  8.07 2 408
obj2 1808400 655260 36.23 62160  9.49 6 408
paper1 472248 169272 35.84 17520 10.35 0 0
paper2 623724 248616 39.86 25356 10.20 0 120
paper3 446520 171720 38.46 18276 10.64 0 528
paper4 161724 56340 34.84 6174 10.96 0 168
paper5 148980 50964 34.21 5574 10.94 0 216
paper6 361824 124368 34.37 12816 10.30 0 12
pic 803724 387204 48.18 34524  8.92 5 384
progc 364212 126552 34.75 12882 10.18 0 456
progl 410280 133380 32.51 14166 10.62 0 144
progp 315276 94464 29.96 9942 10.52 0 444
trans 514452 139704 27.16 14460 10.35 1 36
总计 16919532 6962976 41.15 660834  9.49 44 4656

表4.3 内存管理器测试结果

  对于表4.3中的数据,空占内存的比例(以下简称“空占比例”)是根据大内存块的大小计算出来的。空占比例9.49%意味着,每分配100个单位的大内存块,其中就会产生9.49个单位的空占内存。合理的空占比例是很重要的。空占比例越高分配速度越快,但内存浪费严重。空占比例越低分配速度越慢,但更节约内存。从表4.3的数据中可以看出,空占内存的大小都达到了数千字节(KB)。其中,文件“book1”的空占内存最多达到了143.77KB。但是我们仍然可以注意到,数据中的空占比例都保持在9.00%至10.00%左右。考虑到大内存块占所有内存块的比例只有40.00%左右。如果将分配的小内存块计算在内,那么空占比例只有3.00%至4.00%左右。这样的空占比例还是可以接受的。

  相对于空占内存,空闲内存要小了很多。空闲内存的大小都在数百字节以内。注意两个文件“news”和“paper1”。这两个文件在编码结束时,其空闲内存恰好全部用完。这是我们最希望看到的情况,但是这种情况出现的概率比较小。影响空闲内存大小的是碎片整理的次数。频繁的进行碎片整理可以把空闲内存控制到最小,但是这样做的耗时较大。从表4.3的数据中可以看出,当前使用的方案还是可行的。

  内存管理器分配的所有内存块的总计字节大小加上空闲内存的字节大小,再加上符号列表的长度,这就是定量内存的使用量。如果没有出现重置定量内存的情况,那么将定量内存的使用量减去空占内存的字节大小,再减去空闲内存的字节大小,得到的就是模型结构实际占用内存的字节大小。定量内存的使用量,以及空占内存、空闲内存、模型结构三者所占的比例如表4.4所示。

文件 定量内存
使用量
(字节)
空占内存
所占比例
(%)
空闲内存
所占比例
(%)
模型结构
所占比例
(%)
bib 704580 3.45 0.03 96.52
book1 3375661 4.36 0.01 95.63
book2 2659380 3.95 0.01 96.04
geo 1390240 3.09 0.04 96.87
news 2743617 3.66 0.00 96.34
obj1 217743 3.29 0.19 96.52
obj2 1908140 3.26 0.02 96.72
paper1 496884 3.53 0.00 96.47
paper2 657680 3.86 0.02 96.13
paper3 471465 3.88 0.11 96.01
paper4 170456 3.62 0.10 96.28
paper5 157005 3.55 0.14 96.31
paper6 380402 3.37 0.00 96.63
pic 860810 4.01 0.04 95.94
progc 383637 3.36 0.12 96.52
progl 430033 3.29 0.03 96.67
progp 330027 3.01 0.13 96.85
trans 535694 2.70 0.01 97.29
总计 17873454 3.70 0.03 96.28

表4.4 定量内存的使用量和相关比例

  从表4.4的数据中可以看出,模型结构占用内存的比例都在96.00%左右。剩下的4.00%左右的内存都是空占内存和空闲内存。其中,空占内存的比例较大。在测试的18个文件当中,文件“book1”的内存使用量最大,达到了3.22MB。当然这个文件的数据量也是最大的。从表4.4的数据中还可以看出,我们使用4MB大小的定量内存可以保证在压缩这18个文件时不会出现重置定量内存的情况。这也从一个侧面证明了定量内存的一个缺点。在使用定量内存时,必需在编码前确定定量内存的大小。例如,在本次测试中的文件“paper5”。它的内存使用量最少,只有153.33KB。但是在压缩文件“pager5”的过程中仍然需要分配4MB大小的定量内存,虽然大多数的内存它都没有使用到。除非对数据压缩一遍,否则无法知道压缩时内存的使用量。如果定量内存太小,就会降低算法的压缩率。如果定量内存太大,就会造成内存资源的浪费。在具体实现的时候,一般倾向于使用较大的定量内存。

  现在对方案2.1和方案4.1进行比对测试。方案2.1和方案4.1使用了不同的建模结构。其中,模型中的节点的数量和比例的对比测试已经在第三章中完成了。详细的说明与介绍请参考3.4节,这里不再重复。现在我们首先对方案2.1和方案4.1所建模型的内存占用情况进行对比测试。这两套方案的模型的内存占用的对比测试结果如表4.5所示。

文件 方案2.1
(字节)
方案4.1
(字节)
减少比例
(%)
bib 1147736 680028 40.75
book1 4396702 3228109 26.58
book2 3779486 2554170 32.42
geo 4003892 1346740 66.36
news 4418470 2643279 40.18
obj1 706526 210171 70.25
obj2 3685366 1845572 49.92
paper1 804532 479364 40.42
paper2 999606 632204 36.75
paper3 771968 452661 41.36
paper4 318048 164114 48.40
paper5 305694 151215 50.53
paper6 638288 367574 42.41
pic 2066746 825902 60.04
progc 675602 370299 45.19
progl 643846 415723 35.43
progp 517706 319641 38.26
trans 766108 521198 31.97
总计 30646322 17207964 43.85

表4.5 模型的内存占用的对比测试结果

  从表4.5的数据中可以看出,与方案2.1相比,方案4.1的模型占用的内存大幅减少。这主要得益于CT结构和内存共用方案。虽然说方案2.1的上下文节点只有10个字节,而方案4.1的上下文节点有12个字节,而且方案4.1还增加了一个符号列表。但是,在方案4.1的模型中可以生成更少的上下文节点。所以从结果上看,方案4.1更加优秀。另一方面。虽然从表面上看,方案4.1需要增加额外的内存使用,如空占内存和空闲内存。可是,方案2.1同样也会出现这一类的内存使用。只不过这些内存存在于Delphi 7.0的内存管理器之中,我们无法测试其大小。不过,在一般情况下专用内存管理器的性能肯定会高于通用内存管理器的性能。现在对这两套方案进行压缩耗时和解压缩耗时的对比测试,其测试结果如表4.6所示。

文件 方案2.1 方案4.1
压缩耗时 解压缩耗时 压缩耗时 解压缩耗时
bib 109 125 47 47
book1 828 844 500 516
book2 593 609 328 344
geo 469 468 172 187
news 531 563 234 265
obj1 63 63 15 31
obj2 406 406 172 172
paper1 78 78 16 31
paper2 94 109 31 47
paper3 63 62 32 16
paper4 15 31 0 15
paper5 16 15 0 15
paper6 46 63 16 16
pic 297 344 109 125
progc 63 47 16 15
progl 62 62 16 31
progp 32 47 15 15
trans 63 63 15 31

表4.6 算法耗时对比测试结果(单位毫秒)

  从表4.6的数据中可以看出,方案4.1的算法耗时大幅减少。虽然方案4.1的代码复杂度比方案2.1有所增加,但是方案4.1只需要处理更少的上下文节点。不仅如此,使用了专用内存管理器之后,分配或释放内存的速度都会变得更快。而且在算法结束时,还可以快速的释放掉模型占用的内存。所以,方案4.1的算法耗时比方案2.1减少了很多。测试表明,如果继续提高最高阶数,两者之间的差距还会进一步的加大。现在对这两套方案进行压缩率的对比测试,其测试结果如表4.7所示。

文件 输入大小
(字节)
方案2.1 方案4.1
输出大小
(字节)
压缩率
(bpc)
输出大小
(字节)
压缩率
(bpc)
bib 111261 26087 1.876 26089 1.876
book1 768771 220762 2.297 220763 2.297
book2 610856 150270 1.968 150272 1.968
geo 102400 60291 4.710 60303 4.711
news 377109 111438 2.364 111441 2.364
obj1 21504 10083 3.751 10081 3.750
obj2 246814 74618 2.419 74620 2.419
paper1 53161 15531 2.337 15533 2.338
paper2 82199 23787 2.315 23789 2.315
paper3 46526 14997 2.579 14999 2.579
paper4 13286 4803 2.892 4805 2.893
paper5 11954 4466 2.989 4468 2.990
paper6 38105 11525 2.420 11527 2.420
pic 513216 51675 0.806 51682 0.806
progc 39611 11779 2.379 11781 2.379
progl 71646 15177 1.695 15179 1.695
progp 49379 10588 1.715 10590 1.716
trans 93695 17512 1.495 17512 1.495
总计 3251493 835389 2.055 835434 2.056

表4.7 压缩率对比测试结果

  从表4.7的数据中可以看出,方案2.1和方案4.1的压缩率只有轻微的差别。不管使用Trie结构进行建模,还是使用CT结构进行建模,对于压缩率是没有影响的。这一点可以从第三章介绍的内容中得到确认。使压缩率出现轻微差别的原因有两点。第一点,在使用定量内存的时候,编码程序和解码程序必需使用同样大小的定量内存。所以,在方案4.1输出数据的头部比方案2.1增加了一个字节。这个字节用来保存当前使用的定量内存的大小。另外一点,使用了区分削减方案以后,对于压缩率也会有轻微的影响。在表4.7的数据中,除了文件“geo”和文件“pic”以外,其它文件的输出大小只相差1至3个字节。文件“geo”相差12个字节。文件“pic”相差7个字节。从这里可以看出,区分削减方案对于压缩率的影响不大。

  当定量内存的大小不足以容纳模型结构的时候,需要对定量内存进行重置。这时,相当于对输入数据的不同部份使用不同的模型进行压缩。这样会降低算法的压缩率。现在仍然使用5阶的方案4.1进行测试,但是将定量内存的大小调整到1MB。其测试结果如表4.8所示。

文件 重置
次数
(次)
输出大小
(字节)
压缩率
(bpc)
输出大小
增加比例
(%)
bib 0 26089 1.876 0.00
book1 6 256488 2.669 16.18
book2 4 165892 2.173 10.39
geo 1 61389 4.796 1.80
news 3 125841 2.670 12.92
obj1 0 10081 3.750 0.00
obj2 2 76041 2.465 1.90
paper1 0 15533 2.338 0.00
paper2 0 23789 2.315 0.00
paper3 0 14999 2.579 0.00
paper4 0 4805 2.893 0.00
paper5 0 4468 2.990 0.00
paper6 0 11527 2.420 0.00
pic 0 51682 0.806 0.00
progc 0 11781 2.379 0.00
progl 0 15179 1.695 0.00
progp 0 10590 1.716 0.00
trans 0 17512 1.495 0.00
总计 16 903686 2.223 8.17

表4.8 定量内存不足的测试结果

  表4.8中的输出大小增加比例是根据表4.7中的数据计算得到的。将表4.8中的数据与表4.4和表4.7中的数据进行对比可以发现。定量内存使用量低于1MB的文件明显没有受到影响。定量内存使用量最大的文件“book1”受到的影响也最大,出现了6次定量内存重置。输出数据的大小也增加了16.18%。一般来说,定量内存的重置次数越多,对于压缩率的影响也越大。所以,在实现的时候,一般使用较大的定量内存。尽量保证不要出现定量内存的重置。

  经过本节的测试与分析我们可以发现,方案4.1的性能要比方案2.1优秀很多。无论是从内存占用方面来讲,还是从算法耗时方面来说,方案4.1都要比方案2.1更为优秀。从下一章起,本文将开始介绍PPM算法的变体方案。这些变体方案的实现都将以方案4.1为基础进行修改。

  在本章的最后,本人需要声明一点。本人不保证本章介绍的专用内存管理器就是性能最好的内存管理器。内存管理器的设计是一个技术要求很高的研发过程。本人技术水平一般,所以感兴趣的读者可以深入研究,并自行设计一套专用内存管理器。也许会比本人设计的性能更好。

  评论这张
 
阅读(1191)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017