分享
 
 
 

CUJ:普及知识:typeint

王朝vc·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

普及知识: typeint

Stephen C. Dewhurst

(WQ注:这是比Loki还令我震惊的东西,实在难以译好。先放出来让大家都震惊一下,以后我会修订的。)

--------------------------------------------------------------------------------

在最近的系列文章中,我们为 C++语言设计和实现了一个typeof功能[注1]。 实现中要求在编译期将表达式的类型转换为一定结构的整型值,而这个整型值在以后还可以解码回原始的类型。我们遇到的问题是编码受到了整型值的长度限制,因为为了达到必须的编译期性能,算法将限定在整型的精度范围(32或64bits)内。而许多“合理的” 类型,编码需要数百bits长度的整型值。 (“不合理的” 类型可能需要极大的整型值)。

因为通常使用的数据抽象技术在编译期不是可用的,我们无法实现一个扩展精度的整型类型;我们被限定于可以使用在整型常量表达式上的那些操作上。我们的方法是实现一个编译期算术运算,操纵预定义的整型数集合。比如,左移一个4元组整型值(由4个常量表达式c1-c4组合而成),我们可以使用类似于下面的代码:

typedef ShiftLeft<c4,c3,c2,c1,ModLen> SL;

enum {

code1 = SL::code1,

code2 = SL::code2,

code3 = SL::code3,

code4 = SL::code4

};

这是可行的,但很难看。 我们也不得不选择预定义最大精度(4,对于本例), 而不让编码的复杂度在暗中受精度的影响。

如我们上面所提到的,编译器的强项和弱处都是受被它们编译的语言所提的需求决定的。一个C++语言编译器只需要最基本的编译期算术的能力,但是需要广泛的操纵繁杂的类型的能力。 事实上,多数设计良好的编译器都一个“类型的数学”的概念,于是,类型在编译期被用各种不同的“类型的数学”的运算来操纵。举例来说,当解析一个名称的声明时,编译器从声明的限定符和声明符中组合出名称的类型。当名称在表达式中被操纵时,它的类型将会同时被其它的“类型的数学”的运算所被操纵。

这暗示了可能可以这样做:用整型值表示类型,将类型的操纵运算映射为编译期数学运算,以扩大编译器在这个领域的广泛能力。我们然后应该能够将扩展精度的编译期算法施加在这个“整型/类型”的抽象上。 如果需要,扩展精度的结果的一部分可以被映射回相应的完整类型上。

映射整型值到类型

定义一个从C++的类型到无符号二进制整型的简单映射:为0的位表示一个指针,为1的位表示const的指针。 指针的基础类型无关紧要的,因此,我们选择char来示意。没有任何限定/修饰的基础类型将会表现为数值零点。 为了支持变长的typeint,我们不允许在这个类型表示法中出现前导的0位(即没有const限定的普通指针符) (WQ注:也就是说,01011100会自动滤除前导0而成1011100)。

举例来说,藉由这个简单的编码法则,我们能用无符号二进制整数1011100(十进制是92) 表示类型char *const * *const *const *const * *。让我们把这个类似于整型的类型叫做typeint。

很容易将一个小的整型值转换为一个typeint[注2]:

template <int n>

struct TypeInt {

typedef typename Select<

n&1,

typename TypeInt<(n>>1)>::R *const,

typename TypeInt<(n>>1)>::R *

>::R R;

};

template <>

struct TypeInt<0>

{ typedef char R; };

TypeInt模板主体通过递归决定整型值n的高位的编码结果,然后追加上一个* const(如果低位为1)或*(如果低位为0)。 递归结束于TypeInt对0的特化。

将typeint转换成一个整数也很直观,如果它对应的整型值能够对应到一个预定义的整数上的话:

template <typename T>

struct Value

{ enum { r = 0 }; };

template <typename T>

struct Value<T *>

{ enum { r = Value<T>::r*2 }; };

template <typename T>

struct Value<T * const>

{ enum { r = Value<T>::r*2 + 1 }; };

在这里,模板的主体用于结束递归,此时所有的“位”(指针指示符) 都已从 typeint上分离。 偏特化将递归计算从typeint上反引用得到的整数的等价物,然后根据最远的指针指示符追加一个0或1的位。

cout << Value< TypeInt<92>::R >::r << endl; // 92

对typeint进行移位

左移应该补零,因此我们只须附加正确数目的0:

template <typename T, int n>

struct LShift

{ typedef typename LShift<T,n-1>::R *R; };

template <typename T>

struct LShift<T,0>

{ typedef T R; };

然而,我们的typeint 表示法不允许前导的0, 因此我们必须特别处理可能发生的为0(char)的typeint的移位:

template <int n>

struct LShift<char,n>

{ typedef char R; };

最后,我们必须提供一个特化以消除为0的typeint左移0位时的歧义。否则的话,将会在偏特化间发生二义性。

template <>

struct LShift<char,0>

{ typedef char R; };

在这个实现上,右移总是补0。因为基于这个实现,传入的参数上是没有前导的0的,这意谓着只需简单地反引用typeint适当的次数[注3]:

template <typename T, int n>

struct RShift {

typedef typename Deref<typename RShift<T,n-1>::R>::R R;

};

template <typename T>

struct RShift<T,0> {

typedef T R;

};

位运算

让我们看一下“位或”运算的实现。“位加”和其它位运算是类似的。 在这个实现中,我们使用一个编译期的switch...case来区分一个或两个参数都是0的情况:

template <typename A, typename B>

struct Or {

enum { switchval = IsPtr<A>::r*2 + IsPtr<B>::r };

typedef typename OrImpl<switchval,A,B>::R R;

};

既然一个为零的typeint表示无修饰的char基础类型,我们能构造一个switch...case表达式,以判断参数的位值是否都为0(都是指针时,值为3),或者只第一个参数非0(2),或者只第二个参数是非0(1)(WQ注,原文为only the second argument is zero ,应笔误),或者两个参数都是0(0)。 你可能会料到,一个或两个参数为0的情况很简单:

template <typename A, typename B>

struct OrImpl<0,A,B> {

typedef char R; // 0 | 0 == 0

};

template <typename A, typename B>

struct OrImpl<2,A,B> {

typedef A R; // A | 0 == A

};

template <typename A, typename B>

struct OrImpl<1,A,B> {

typedef B R; // 0 | B == B

};

当两个参数都非0时,就比较有趣了:

template <typename A, typename B>

struct OrImpl<3,A,B> {

typedef typename Deref<A>::R DA;

typedef typename Deref<B>::R DB;

typedef typename Or<DA,DB>::R Temp;

typedef

typename Select<

// either A or B has a 1 bit

IsConst<A>::r || IsConst<B>::r,

Temp * const,

Temp *

>::R R;

};

首先, 我们反引用两个参数,以移除它们的低位,并递归计算已被缩短的typeint的“位或”结果。 然后追加上被较早移除的低位的“位或”结果。

编译期的switch...case看起来是不必要的复杂。另一个解决方法是使用彻底的特化。有九种情况需要考虑,列于下表。

First Argument

Second Argument

Char

char

Char

B *

Char

B * const

A *

char

A *

B *

A *

B * const

A * const

char

A * const

B *

A * const

B * const

根据上表,模板主体和8个偏特化如下:

template <typename A, typename B>

struct Or { typedef char R; };

template <typename A, typename B>

struct Or<A *,B *> { typedef typename Or<A,B>::R *R; };

template <typename A, typename B>

struct Or<A *const,B *> {

typedef typename Or<A,B>::R *const R;

};

// 5 more cases...

template <typename A, typename B>

struct Or<A *const,B> { typedef A *const R; };

在“位或”的实现中,两个实现半斤八两。在“位与”的实现中,可以合并一些情况,所以实现彻底的特化将更容易些。

template <typename A, typename B>

struct And // at least one of A or B is 0

{ typedef char R; };

template <typename A, typename B>

struct And<A *,B *>

{ typedef typename And<A,B>::R *R; };

template <typename A, typename B>

struct And<A *const,B *>

{ typedef typename And<A,B>::R *R; };

template <typename A, typename B>

struct And<A *,B *const>

{ typedef typename And<A,B>::R *R; };

template <typename A, typename B>

struct And<A *const,B *const>

{ typedef typename And<A,B>::R *const R; };

使用和限制

用typeint扩展编译期算法比我们的较早的机制占优势。 最初的机制是罗嗦的,并且固定在一个给定的精度上:

typedef ShiftLeft<c4,c3,c2,c1,ModLen> SL;

enum {

code1 = SL::code1,

code2 = SL::code2,

code3 = SL::code3,

code4 = SL::code4

};

typeint用起来比较简洁,而且不需要事先指定结果的精度。typeint 会在需要时扩展自己的精度,直到编译器的能力极限:

typedef LShift<aCode, ModLen>::R Code;

不幸地是,存在一个问题。typeint的实现是基于深度递归的,而很多编译器不能对递归的模板实例化到足够的深度。这严重限制了typeint的最大位长。虽然 C++语言标准建议的最小实例化深度只有17层 (在标准的 Annex B),但大多数编译器看起来都能够处理至少60层,而有些还有编译选项以允许高达600-700层,更有一些则可一直实例化到资源耗尽(通常结果是达到几千层)。 我们将在以后的专栏文章中寻找方法来处理递归模板实例化深度的限制。

复杂的乘法

在结束前,让我们瞄一下typeint的乘法的实现。我们用传统的移位相加的方法来实现它:

1 1 0 1 // A

x 1 0 0 1 // B

------------

1 1 0 1

0 0 0 0

0 0 0 0

1 1 0 1

---------------

1 1 1 0 1 0 1 // A * B

typeints 的计算的本质上是上面是相同的,但是可读性比较差:

char *const *const * *const

x char *const * * *const

---------------------------------------

char *const *const * *const

char

char

char *const *const * *const * * *

-------------------------------------------

char *const *const *const * *const * *const

移位相加乘法的直接实现却还简洁得令人有些心慰:

template <typename A, typename B>

struct Mul; // no definition of primary

template <typename A>

struct Mul<A,char> // A * 0 == 0

{ typedef char R; };

template <typename A, typename B>

struct Mul<A,B *> // 0 digit, just shift

牋牋牋牋牋牋牋牋 // A*B0 == (A*B)<<1

{ typedef typename Mul<A,B>::R *R; };

template <typename A, typename B>

struct Mul<A,B *const> { // 1 digit, shift and add

牋牋牋牋牋牋牋牋牋? // A*B1 == ((A*B)<<1)+A

typedef typename Mul<A,B>::R *Tmp;

typedef typename Add<Tmp,A>::R R;

};

template <typename A>

struct Mul<A,char *const> // to avoid a char * typeint

{ typedef A R; }; // no leading zeros!

不幸地是,这个算法有二次方的(编译期!) 复杂度,而不是其它运算的线性复杂度。结果,当对35位的typeint进行乘法时,在典型的工作站上,有一个引人注目的编译延迟,而且对200位的typeint进行乘法时至少需要一个午休时间。

预告

下次,我们将会详细查看乘法的实现,并考察许多template metaprogramming 技术,它们能戏剧性地提高性能。再下次,将探索解决模板实例化深度限制的方法。

[1] S.C. Dewhurst, "Common Knowledge: A Bitwise typeof Operator, Parts 1-3," C/C++ Users Journal, August, October, and December 2002.

[2] The full implementation of this preliminary typeint facility is available on the author's website: <www.semantics.org/code.html>. The reader may find in the same location a reimplementation of the typeof facility that employs typeints for extended-precision compile-time arithmetic. The Select template is borrowed (in modified form) from Andrei Alexandrescu's Loki library. It performs a compile-time if statement, selecting its second argument if the first argument is true, and its third argument if the first argument is false.

[3] Description of utilities like Select, IsPtr, and Deref are omitted for reasons of space. Their implementations are available as described in the previous note.

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有