64位系统下的透明指针压缩技术

162 浏览量更新于2024-08-25 收藏 324KB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

"Transparent Pointer Compression for Linked Data Structures (2005-06-12)-计算机科学" 这篇论文由Chris Lattner和Vikram S. Adve在UIUC（University of Illinois at Urbana-Champaign）发表，主要探讨了64位地址空间对现代应用程序的影响以及如何通过透明指针压缩技术优化内存使用。随着计算机硬件的发展，64位系统成为主流，虽然提供了更大的寻址能力，但同时也带来了指针占用内存翻倍的问题，这会降低系统的有效缓存容量和内存带宽，相对32位系统而言。论文提出了一种复杂的自动转换方法，该方法能够将64位指针缩小到32位，从而减少内存消耗。这种技术被称为“宏观”操作，因为它在整个程序的逻辑数据结构层面上工作。这意味着它可以针对单个数据结构实例或其子集进行处理，允许它们在不超过2^32字节的大小限制内增长。这种方法的一个关键特性是选择性压缩，即它能够对某些数据结构进行指针压缩，而不适用于其他数据结构。此外，论文还讨论了一种动态版本的技术，尽管尚未实现，但理论上可以透明地扩展单个数据结构中的指针，当它超过4GB的限制时。通过这种方式，系统能够在保持高效利用64位地址空间的同时，应对大规模的数据结构。为了证明这一方法的有效性，作者们对一系列以指针密集型为特点的基准测试进行了实验，结果显示，这种转换能够提高性能。通过减少指针的大小，系统可以更有效地利用缓存和内存带宽，尤其是在处理大量链接数据结构的应用中，性能提升尤为显著。这篇论文提供了一个自动化的、有针对性的解决方案，用于解决64位系统中由于大尺寸指针带来的内存效率问题。这种透明指针压缩技术对于优化内存敏感的应用程序，尤其是那些依赖于大量链接数据结构的程序，具有重要的实际应用价值。

资源详情

资源推荐

struct list { int X; list *Next; };

list *MakeList(int N) {

list *Result = 0;

for (int i = 0; i != N; ++i) {

list *Node =

malloc(sizeof(list));

Node->Next = Result;

Node->X = i+’A’;

Result = Node; }

return Result; }

int Length(list *L) {

if (L == 0) return 0;

return Length(L->Next)+1;

}

int Testlists() {

list *A = MakeList(100);

list *B = MakeList(20);

int Sum = Length(A) + Length(B);

((char*)B)[5] = ’c’; // not type safe!

return Sum; }

(a) Original

list: HM

Result Node returning

(b) BU DS gra ph for MakeList

list: R

list: HMR

byte: AHMR

(d) BU DS gra ph for Testlists

struct list { int X; list *Next; };

list *MakeList(Pool *PD, int N) {

list *Result = 0;

for (int i = 0; i != N; ++i) {

list *Node =

poolalloc(PD, sizeof(list));

Node->Next = Result;

Node->X = i+’A’;

Result = Node; }

return Result; }

int Length(list *L) {

if (L == 0) return 0;

return Length(L->Next)+1;

}

int Testlists() {

Pool P1, P2;

poolinit(&P1, sizeof(list));

poolinit(&P2, 0 /*no size hint known*/);

list *A = MakeList(&P1, 100);

list *B = MakeList(&P2, 20);

int Sum = Length(A) + Length(B);

((char*)B)[5] = ’c’;

pooldestroy(&P1); pooldestroy(&P2);

return Sum; }

(e) After Pool Allocation

Figure 4: Simple linked list example

the objects in the lists A and B (and prove the lists are

disjoint), even though t hey are created and manipulated by

common functions. If heap objects were instead named by

allocation site, A and B would point to a single node in the

graph and objects of the two lists would not be distinguish-

able.

A second feature of DSA is that, like many other context-

sensitive p ointer analyses, e.g., [5, 4, 11, 13], it actually

computes two points-to graphs for each function in a pro-

gram - a bottom-up ( BU) graph representing a function and

its callees (but not any callers), and a ﬁnal top-down (TD)

graph representing the eﬀects of both callees and cal lers.

The TD graph is the ﬁnal result of the pointer analysis. The

BU graph, however, provides a more precise basis for both

Pool Allocation and Pointer Compression because two dis-

tinct pointer arguments in a function may be aliased (point

to the same DS graph node) in one calling context but not

in another. Using the BU graph allows the transformatio ns

to distinguish (and therefore) segregate objects in the latter

case. Therefore, pointer compression operates largely using

the BU g ra ph, except where noted, and pool allocation only

uses the BU graph [10].

The example graphs a lso illustrate o ther basic but relevant

features of DSA. The algorithm detects that the structure

is recursive (the cycle in the graph), and that the point-

ers in the functions point to the list objects. In MakeList,

DSA also detects that heap objects are allocated (H) and

returned, whereas in Length, memory is not allocated or

freed (no H ﬂag). (The M and R ﬂags shown in the ﬁgures

can be ignored for this work.)

2.2 Automatic Pool Allocation

Given a program with calls to malloc and free, Auto-

matic Pool Allocation modiﬁes the program to allocate and

free memory from p ools within the standard system heap. A

pool is represented in the program by a pool descriptor. Au-

tomatic Pool Allocation creates one dist inct pool descriptor

for each node marked H in a function’s DS graph, eﬀectively

partitioning objects in t he heap as they were partitioned in

the DS graph by pointer analysis. Calls to malloc and free

struct list_pc32 { int X; int Next; };

static int MakeList_pc32(Pool *PD, int N) {

int Result = 0;

for (int i = 0; i != N; ++i) {

int Node = poolalloc_pc(PD, 1);

int *tmp1 = PD->poolbase+Node+offsetof(list_pc32, Next);

*tmp1 = Result;

int *tmp2 = PD->poolbase+Node+offsetof(list_pc32, X);

*tmp2 = i+’A’;

Result = Node; }

return Result; }

static int Length_pc32(Pool *PD, int L) {

if (L == 0) return 0;

int *tmp = PD->poolbase+L+offsetof(list_pc32, Next);

return Length_pc32(PD, *tmp)+1;

}

int Testlists() {

Pool P1, P2;

poolinit_pc(&P1, sizeof(list_pc32));

poolinit_pc(&P2, 1);

int A = MakeList_pc32(&P1, 100);

int B = MakeList_pc64(&P2, 20);

int Sum = Length_pc32(&P1, A) + Length_pc64(&P2, B);

((char*)B)[5] = ’c’;

pooldestroy_pc(&P1); pooldestroy_pc(&P2);

return Sum; }

Figure 5: Example after static compression

are simply replaced with calls to poolalloc and poolfree,

passing i n the pool descriptor corresponding t o the DS node

poi nted to by the relevant pointer. This implies that the

lifetime of individual objects allo cated from the pool stay

exactly the same as the original program (except for some

leaked objects as explained below).

The pool runtime library provides functions poolinit

and pooldestroy to initialize and destroy a po o l descrip-

tor. pooldestroy also releases any remaining pool memory

to the system heap. (Note that this can reclaim memory fo r

objects that were never freed in the original program, i.e.,

were previously leaked.) Each pool is a fully general heap,

providing equivalents for all standard heap functions, includ-

ing poolalloc, poolfree, poolrealloc and poolmemalign.

A pool internally obtains and frees memory oﬀ the system

heap in large s labs using malloc and free.

剩余11页未读，继续阅读

weixin_38733281

粉丝: 2
资源: 953

64位系统下的透明指针压缩技术

Variable-length Codes for Data Compression.pdf

Data-Structures--Compression

---> 17 compress_gray_image('00.png', compression_level=2)---> 11 compressed_data = lzss.compress(data, compression_level)这两行代码报错TypeError: function takes at most 1 argument (2 given)

compression-webpack-plugin使用方法

Error: Cannot find module 'compression-webpack-plugin'

uniapp中如何compression-webpack-plugin插件进行打包

Cannot find module 'compression-webpack-plugin'

nuxt安装compression-webpack-plugin

While resolving: compression-webpack-plugin@3.1.0 npm ERR! Found: webpack@3.12.0

compression-webpack-plugin

springboot kafka设置压缩级别

Nuxt2项目怎么进行compression-webpack-plugin 优化

如何安装tensorflow-compression？

hive io.compression.codecs

compression-webpack-plugin minRatio 0.1

compression-webpack-plugin 版本对应

最新资源