kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

内核抢占与中断返回

1、上下文

一般来说,CPU在任何时刻都处于以下三种情况之一:
(1)运行于用户空间,执行用户进程;
(2)运行于内核空间,处于进程上下文;
(3)运行于内核空间,处于中断上下文。
应用程序通过系统调用陷入内核,此时处于进程上下文。现代几乎所有的CPU体系结构都支持中断。当外部设备产生中断,向CPU发送一个异步信号,CPU调用相应的中断处理程序来处理该中断,此时CPU处于中断上下文。

在进程上下文中,可以通过current关联相应的任务。进程以进程上下文的形式运行在内核空间,可以发生睡眠,所以在进程上下文中,可以使作信号量(semaphore)。实际上,内核经常在进程上下文中使用信号量来完成任务之间的同步,当然也可以使用锁。

中断上下文不属于任何进程,它与current没有任何关系(尽管此时current指向被中断的进程)。由于没有进程背景,在中断上下文中不能发生睡眠,否则又如何对它进行调度。所以在中断上下文中只能使用锁进行同步,正是因为这个原因,中断上下文也叫做原子上下文(atomic context)(关于同步以后再详细讨论)。在中断处理程序中,通常会禁止同一中断,甚至会禁止整个本地中断,所以中断处理程序应该尽可能迅速,所以又把中断处理分成上部和下部(关于中断以后再详细讨论)。

2、上下文切换

上下文切换,也就是从一个可执行进程切换到另一个可执行进程。上下文切换由函数context_switch()函数完成,该函数位于kernel/sched.c中,它由进程调度函数schedule()调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static inline
task_t * context_switch(runqueue_t *rq, task_t *prev, task_t *next)
{
	struct mm_struct *mm = next->mm;
	struct mm_struct *oldmm = prev->active_mm;

	if (unlikely(!mm)) {
		next->active_mm = oldmm;
		atomic_inc(&oldmm->mm_count);
		enter_lazy_tlb(oldmm, next);
	} else
		switch_mm(oldmm, mm, next);

	if (unlikely(!prev->mm)) {
		prev->active_mm = NULL;
		WARN_ON(rq->prev_mm);
		rq->prev_mm = oldmm;
	}

	/* Here we just switch the register state and the stack. */
	switch_to(prev, next, prev);

	return prev;
}

其中,switch_mm()将虚拟内存映射到新的进程;switch_to完成最终的进程切换,它保存原进程的所有寄存器信息,恢复新进程的所有寄存器信息,并执行新的进程。无论何时,内核想要进行任务切换,都通过调用schedule()完成任务切换。

2.2、用户抢占

当内核即将返回用户空间时,内核会检查need_resched是否设置,如果设置,则调用schedule(),此时,发生用户抢占。一般来说,用户抢占发生几下情况:
(1)从系统调用返回用户空间;
(2)从中断(异常)处理程序返回用户空间。

2.3、内核抢占

内核从2.6开始就支持内核抢占,对于非内核抢占系统,内核代码可以一直执行,直到完成,也就是说当进程处于内核态时,是不能被抢占的(当然,运行于内核态的进程可以主动放弃CPU,比如,在系统调用服务例程中,由于内核代码由于等待资源而放弃CPU,这种情况叫做计划性进程切换(planned process switch))。但是,对于由异步事件(比如中断)引起的进程切换,抢占式内核与非抢占式是有区别的,对于前者叫做强制性进程切换(forced process switch)。

为了支持内核抢占,内核引入了preempt_count字段,该计数初始值为0,每当使用锁时加1,释放锁时减1。当preempt_count为0时,表示内核可以被安全的抢占,大于0时,则禁止内核抢占。该字段对应三个不同的计数器(见软中断一节),也就是说在以下三种任何一种情况,该字段的值都会大于0。

(1) 内核执行中断处理程序时,通过irq_enter增加中断计数器的值;
#define irq_enter() (preempt_count() += HARDIRQ_OFFSET)
(2) 可延迟函数被禁止(执行软中断和tasklet时经常如此,由local_bh_disable完成;
(3) 通过把抢占计数器设置为正而显式禁止内核抢占,由preempt_disable完成。

当从中断返回内核空间时,内核会检preempt_count和need_resched的值(返回用户空间时只需要检查need_resched),如查preempt_count为0且need_resched设置,则调用schedule(),完成任务抢占。一般来说,内核抢占发生以下情况:
(1) 从中断(异常)返回时,preempt_count为0且need_resched置位(见从中断返回);
(2) 在异常处理程序中(特别是系统调用)调用preempt_enable()来允许内核抢占发生;

1
2
3
4
5
6
7
8
//incude/linux/preempt.h
#define preempt_enable() \
do { \
	//抢占计数器值减1
	preempt_enable_no_resched(); \
	//检查是否需要进行内核抢占调度,见(3)
	preempt_check_resched(); \
} while (0)

(3) 启用可延迟函数时,即调用local_bh_enable()时发生;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//kernel/softirq.c
void local_bh_enable(void)
{
	WARN_ON(irqs_disabled());
	/*
	 * Keep preemption disabled until we are done with
	 * softirq processing:
	 */
	//软中断计数器值减1
	preempt_count() -= SOFTIRQ_OFFSET - 1;

	if (unlikely(!in_interrupt() && local_softirq_pending()))
		do_softirq(); //软中断处理
	//抢占计数据器值减1
	dec_preempt_count();
	
	//检查是否需要进行内核抢占调度
	preempt_check_resched();
}

//include/linux/preempt.h
#define preempt_check_resched() \
do { \
	//检查need_resched
	if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) \
		//抢占调度
		preempt_schedule(); \
} while (0)

//kernel/sched.c
asmlinkage void __sched preempt_schedule(void)
{
	struct thread_info *ti = current_thread_info();

	/*
	 * If there is a non-zero preempt_count or interrupts are disabled,
	 * we do not want to preempt the current task.  Just return..
	 */
	 //检查是否允许抢占,本地中断关闭,或者抢占计数器值不为0时不允许抢占
	if (unlikely(ti->preempt_count || irqs_disabled()))
		return;

need_resched:
	ti->preempt_count = PREEMPT_ACTIVE;
	//发生调度
	schedule();
	ti->preempt_count = 0;

	/* we could miss a preemption opportunity between schedule and now */
	barrier();
	if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
		goto need_resched;
}

(4) 内核任务显示调用schedule(),例如内核任务阻塞时,就会显示调用schedule(),该情况属于内核自动放弃CPU。

5、从中断返回

当内核从中断返回时,应当考虑以下几种情况:
(1) 内核控制路径并发执行的数量:如果为1,则CPU返回用户态。
(2) 挂起进程的切换请求:如果有挂起请求,则进行进程调度;否则,返回被中断的进程。
(3) 待处理信号:如果有信号发送给当前进程,则必须进行信号处理。
(4) 单步调试模式:如果调试器正在跟踪当前进程,在返回用户态时必须恢复单步模式。
(5) Virtual-8086模式:如果中断时CPU处于虚拟8086模式,则进行特殊的处理。

4.1从中断返回

中断返回点为ret_from-intr: // 从中断返回

1
2
3
4
5
6
7
ret_from_intr:
	GET_THREAD_INFO(%ebp)
	movl EFLAGS(%esp), %eax        # mix EFLAGS and CS
	movb CS(%esp), %al
	testl $(VM_MASK | 3), %eax #是否运行在VM86模式或者用户态
	/*中断或异常发生时,处于内核空间,则返回内核空间;否则返回用户空间*/
	jz resume_kernel        # returning to kernel or vm86-space

从中断返回时,有两种情况,一是返回内核态,二是返回用户态。

5.1.1、返回内核态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifdef CONFIG_PREEMPT 
/*返回内核空间,先检查preempt_count,再检查need_resched*/
ENTRY(resume_kernel)
	/*是否可以抢占,即preempt_count是否为0*/
	cmpl $0,TI_preempt_count(%ebp)    # non-zero preempt_count ?
	jnz restore_all #不能抢占,则恢复被中断时处理器状态
	
need_resched:
	movl TI_flags(%ebp), %ecx    # need_resched set ?
	testb $_TIF_NEED_RESCHED, %cl #是否需要重新调度
	jz restore_all #不需要重新调度
	testl $IF_MASK,EFLAGS(%esp)     # 发生异常则不调度
	jz restore_all
	#将最大值赋值给preempt_count,表示不允许再次被抢占
	movl $PREEMPT_ACTIVE,TI_preempt_count(%ebp)
	sti
	call schedule #调度函数
	cli
	movl $0,TI_preempt_count(%ebp) #preempt_count还原为0
	#跳转到need_resched,判断是否又需要发生被调度
	jmp need_resched
#endif
5.1.2、返回用户态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*返回用户空间,只需要检查need_resched*/
ENTRY(resume_userspace)  #返回用户空间,中断或异常发生时,任务处于用户空间
	 cli                # make sure we don't miss an interrupt
		            # setting need_resched or sigpending
		            # between sampling and the iret
	movl TI_flags(%ebp), %ecx
	andl $_TIF_WORK_MASK, %ecx    # is there any work to be done on
		            # int/exception return?
	jne work_pending #还有其它工作要做
	jmp restore_all #所有工作都做完,则恢复处理器状态

#恢复处理器状态
restore_all:
	RESTORE_ALL

	# perform work that needs to be done immediately before resumption
	ALIGN
	
	#完成其它工作
work_pending:
	testb $_TIF_NEED_RESCHED, %cl #检查是否需要重新调度
	jz work_notifysig #不需要重新调度
 #需要重新调度
work_resched:
	call schedule #调度进程
	cli                # make sure we don't miss an interrupt
		            # setting need_resched or sigpending
		            # between sampling and the iret
	movl TI_flags(%ebp), %ecx
	/*检查是否还有其它的事要做*/
	andl $_TIF_WORK_MASK, %ecx    # is there any work to be done other
		            # than syscall tracing?
	jz restore_all #没有其它的事,则恢复处理器状态
	testb $_TIF_NEED_RESCHED, %cl
	jnz work_resched #如果need_resched再次置位,则继续调度
#VM和信号检测
work_notifysig:                # deal with pending signals and
		            # notify-resume requests
	testl $VM_MASK, EFLAGS(%esp) #检查是否是VM模式
	movl %esp, %eax
	jne work_notifysig_v86        # returning to kernel-space or
		            # vm86-space
	xorl %edx, %edx
	#进行信号处理
	call do_notify_resume
	jmp restore_all

	ALIGN
work_notifysig_v86:
	pushl %ecx            # save ti_flags for do_notify_resume
	call save_v86_state        # %eax contains pt_regs pointer
	popl %ecx
	movl %eax, %esp
	xorl %edx, %edx
	call do_notify_resume #信号处理
	jmp restore_all
5.2、从异常返回

异常返回点为ret_from_exception: #从异常返回
ALIGN
ret_from_exception:
preempt_stop /相当于cli,从中断返回时,在handle_IRQ_event已经关中断,不需要这步/

6、从系统调用返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
	#系统调用入口
ENTRY(system_call)
	pushl %eax            # save orig_eax
	SAVE_ALL
	GET_THREAD_INFO(%ebp)
		            # system call tracing in operation
	testb $(_TIF_SYSCALL_TRACE|_TIF_SYSCALL_AUDIT),TI_flags(%ebp)
	jnz syscall_trace_entry
	cmpl $(nr_syscalls), %eax
	jae syscall_badsys
syscall_call:
	#调用相应的函数
	call *sys_call_table(,%eax,4)
	movl %eax,EAX(%esp)        # store the return value,返回值保存到eax
#系统调用返回
syscall_exit:
	cli                # make sure we don't miss an interrupt
		            # setting need_resched or sigpending
		            # between sampling and the iret
	movl TI_flags(%ebp), %ecx
	testw $_TIF_ALLWORK_MASK, %cx    # current->work,检查是否还有其它工作要完成
	jne syscall_exit_work
#恢复处理器状态
restore_all:
	RESTORE_ALL

#做其它工作
syscall_exit_work:
	 #检查是否系统调用跟踪,审计,单步执行,不需要则跳到work_pending(进行调度,信号处理)
	testb $(_TIF_SYSCALL_TRACE|_TIF_SYSCALL_AUDIT|_TIF_SINGLESTEP), %cl
	jz work_pending
	sti                # could let do_syscall_trace() call
		            # schedule() instead
	movl %esp, %eax
	movl $1, %edx
	#系统调用跟踪
	call do_syscall_trace
	#返回用户空间
	jmp resume_userspace

整个中断、异常和系统调用返回流程如下:

kmalloc 函数详解

1
2
#include <linux/slab.h>
void *kmalloc(size_t size, int flags);

给 kmalloc 的第一个参数是要分配的块的大小. 第 2 个参数, 分配标志, 非常有趣, 因为它以几个方式控制 kmalloc 的行为.

最一般使用的标志, GFP_KERNEL, 意思是这个分配((内部最终通过调用 _get_free_pages 来进行, 它是 GFP 前缀的来源) 代表运行在内核空间的进程而进行的. 换句话说, 这意味着调用函数是代表一个进程在执行一个系统调用. 使用 GFP_KENRL 意味着 kmalloc 能够使当前进程在少内存的情况下睡眠来等待一页.

一个使用 GFP_KERNEL 来分配内存的函数必须, 因此, 是可重入的并且不能在原子上下文中运行. 当当前进程睡眠, 内核采取正确的动作来定位一些空闲内存, 或者通过刷新缓存到磁盘或者交换出去一个用户进程的内存.

GFP_KERNEL 不一直是使用的正确分配标志; 有时 kmalloc 从一个进程的上下文的外部调用. 例如, 这类的调用可能发生在中断处理, tasklet, 和内核定时器中. 在这个情况下, 当前进程不应当被置为睡眠, 并且驱动应当使用一个 GFP_ATOMIC 标志来代替. 内核正常地试图保持一些空闲页以便来满足原子的分配. 当使用 GFP_ATOMIC 时, kmalloc 能够使用甚至最后一个空闲页. 如果这最后一个空闲页不存在, 但是, 分配失败.

其他用来代替或者增添 GFP_KERNEL 和 GFP_ATOMIC 的标志, 尽管它们 2 个涵盖大部分设备驱动的需要. 所有的标志定义在 <linux/gfp.h>, 并且每个标志用一个双下划线做前缀, 例如 __GFP_DMA. 另外, 有符号代表常常使用的标志组合; 这些缺乏前缀并且有时被称为分配优先级. 后者包括:

1
2
3
4
5
6
7
GFP_ATOMIC   用来从中断处理和进程上下文之外的其他代码中分配内存. 从不睡眠.  
GFP_KERNEL    内核内存的正常分配. 可能睡眠.  
GFP_USER  用来为用户空间页来分配内存; 它可能睡眠.  
GFP_HIGHUSER  如同 GFP_USER, 但是从高端内存分配, 如果有. 高端内存在下一个子节描述.  
GFP_NOIO  
GFP_NOFS  
这个标志功能如同 GFP_KERNEL, 但是它们增加限制到内核能做的来满足请求. 一个 GFP_NOFS 分配不允许进行任何文件系统调用, 而 GFP_NOIO 根本不允许任何 I/O 初始化. 它们主要地用在文件系统和虚拟内存代码, 那里允许一个分配睡眠, 但是递归的文件系统调用会是一个坏注意.
上面列出的这些分配标志可以是下列标志的相或来作为参数, 这些标志改变这些分配如何进行:
1
2
3
4
5
6
7
8
9
__GFP_DMA    这个标志要求分配在能够 DMA 的内存区. 确切的含义是平台依赖的并且在下面章节来解释.  
__GFP_HIGHMEM 这个标志指示分配的内存可以位于高端内存.  
__GFP_COLD    正常地, 内存分配器尽力返回"缓冲热"的页 -- 可能在处理器缓冲中找到的页. 相反, 这个标志请求一个"冷"页, 它在一段时间没被使用. 它对分配页作 DMA 读是有用的, 此时在处理器缓冲中出现是无用的.  
__GFP_NOWARN  这个很少用到的标志阻止内核来发出警告(使用 printk ), 当一个分配无法满足.  
__GFP_HIGH    这个标志标识了一个高优先级请求, 它被允许来消耗甚至被内核保留给紧急状况的最后的内存页.  
__GFP_REPEAT  
__GFP_NOFAIL  
__GFP_NORETRY  
这些标志修改分配器如何动作, 当它有困难满足一个分配. __GFP_REPEAT 意思是" 更尽力些尝试" 通过重复尝试 -- 但是分配可能仍然失败. __GFP_NOFAIL 标志告诉分配器不要失败; 它尽最大努力来满足要求. 使用 __GFP_NOFAIL 是强烈不推荐的; 可能从不会有有效的理由在一个设备驱动中使用它. 最后, __GFP_NORETRY 告知分配器立即放弃如果得不到请求的内存.

kmalloc 能够分配的内存块的大小有一个上限. 这个限制随着体系和内核配置选项而变化. 如果你的代码是要完全可移植, 它不能指望可以分配任何大于 128 KB. 如果你需要多于几个 KB

这方面的原因:
kmalloc并不直接从分页机制中获得空闲页面而是从slab页面分配器那儿获得需要的页面,slab的实现代码限制了最大分配的大小为128k,即 131072bytes,理论上你可以通过更改slab.c中的 cache_sizes数组中的最大值使得kmalloc可以获得更大的页面数,不知道有没有甚么副效应或者没有必要这样做,因为获取较大内存的方法有很 多,想必128k是经验总结后的合适值。

alloc_page( )可以分配的最大连续页面是4K

1
2
3
4
5
6
7
8
9
static inline struct page * alloc_pages(unsigned int gfp_mask, unsigned int order) 
{ 
	/*
	 * Gets optimized away by the compiler. 
	 */ 
	if (order >= MAX_ORDER) 
	return NULL; 
	return _alloc_pages(gfp_mask, order); 
} 

alloc_pages最大分配页面数为512个,则可用内存数最大为29*4K=2M

[大牛的]后缀数组总结

双关键字的基数排序

先对关键字2进行排序,然后再对关键字1进行稳定排序。 后缀数组中用到了这点。


大牛在这里

后缀数组是处理字符串的有力工具。后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也并不逊色,而且它比后缀树所占用的内存空间小很多。可以说,后缀数组比后缀树要更为实用。自从拜读了罗穗骞大牛的WC2009论文《后缀数组——处理字符串的有力工具》后,经过若干星期的努力(中间有因某些原因而缓下来),终于把论文上面的练习题全部完成了,现在写写自己对后缀数组的理解和感悟。在看本笔记时,请不要忘记了,这是笔记,而教材是《后缀数组——处理字符串的有力工具》。

一:后缀数组的实现

  1. 定义:Suffix Array数组(SA数组)用于保存从小到大排好序之后的后缀。RANK名次数组用来保存后缀S[i..n]在所有后缀中是第几小的后缀。简单来说,SA数组表示的是“排第几的是谁”,RANK数组表示的是“你的排名是多少”。
  2. 求SA数组以及RANK数组的方法:详细的请转到罗穗骞大牛的论文,我的学习笔记重点不是要介绍这个。
  3. 对DA(倍增算法)的一些个人理解:由于我只学习了倍增算法,所以我只能谈谈我对它的理解。DC3算法我没有去研究….

DA算法我是根据罗穗骞的模板写的,根据自己的理解做了些许的小优化。我们现在来看看罗穗骞大牛的模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
	int i,j,p,*x=wa,*y=wb,*t;
	for(i=0;i<m;i++) ws[i]=0;
	for(i=0;i<n;i++) ws[x[i]=r[i]]++;
	for(i=1;i<m;i++) ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
	for(j=1,p=1;p<n;j*=2,m=p)
	{
		for(p=0,i=n-j;i<n;i++) y[p++]=i;
		for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
		for(i=0;i<n;i++) wv[i]=x[y[i]];
		for(i=0;i<m;i++) ws[i]=0;
		for(i=0;i<n;i++) ws[wv[i]]++;
		for(i=1;i<m;i++) ws[i]+=ws[i-1];
		for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
	return;
}

其实,我个人认为,对于这个算法以及代码,无需过分深入地理解,只需记忆即可,理解只是为了帮助记忆罢了。先解释变量:n为字符串长度,m为字符的取值范围,r为字符串。后面的j为每次排序时子串的长度。

1
2
3
4
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[x[i]=r[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;

这四行代码,进行的是对R中长度为1的子串进行基数排序。x数组在后面需要用到,所以先复制r数组的值。特别需要注意的是,第四行的for语句,初始化语句为i=n-1,如果写得不太熟练,很容易习惯性地写成i=0,我一开始就是。理解这是基数排序的最好方法,找个例子,自己推推….

1
2
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;

这两行代码,利用了上一次基数排序的结果,对待排序的子串的第二关键字进行了一次高效地基数排序。我们可以结合下面的图来理解:

不难发现,除了第一次基数排序以外,之后的每次双关键字排序,设此次排序子串长度为j,则从第n-j位开始的子串,其第二关键字均为0,所以得到第一个for语句:for(p=0,i=n-j;i<n;i++) y[p++]=i;使用pascal的朋友们注意了,这里之所以是n-j位,是因为c++的字符串是从第0位开始表示的。这里,p暂时成为了一个计数变量。第二个语句的意义,分析上图也不难理解,这里留给朋友们你们自行思考啦。(不如说我懒…)

1
2
3
4
5
for(i=0;i<n;i++) wv[i]=x[y[i]];
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[wv[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];

与一开始的4个for语句意义相同,基数排序。至于为什么wv[i]=x[y[i]],这个我想了蛮久没想通…硬记算了- -哪位朋友理解的希望能告诉我一声…

1
2
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
	x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;

这个for语句中的初始化语句里,完成了x数组和y数组的交换,用了指针的交换节约时间,简化代码。这里需要注意的是p和i的初始值都是1,不是0.其实如果记得后面的语句,不难看出它们的初始值不能为0,因为后面有i-1和p-1嘛。这个for语句的意义要结合cmp函数来理解。反正,你知道这里p的值表示的是此时关键字不同的串的数量就对了。当 p=n 的时候,说明所有串都已经排好序了(它们的排名都唯一确定)。所以,一开始的循环语句中,循环条件是(p<n)。

另外,在使用倍增算法前,需要保证r数组的值均大于0。然后要在原字符串后添加一个0号字符,具体原因参见罗穗骞的论文。这时候,若原串的长度为n,则实际要进行后缀数组构建的r数组的长度应该为n+1.所以调用da函数时,对应的n应为n+1.

二、后缀数组的应用–height数组

在介绍后缀数组的应用前,先介绍后缀数组的一个重要附属数组:height数组。 1、height 数组:定义height[i]=suffix(sa[i-1])和suffix(sa[i])的最长公 共前缀,也就是排名相邻的两个后缀的最长公共前缀。 height数组是应用后缀数组解题是的核心,基本上使用后缀数组解决的题目都是依赖height数组完成的。

2、height数组的求法:具体的求法参见罗穗骞的论文。对于height数组的求法,我并没有去深刻理解,单纯地记忆了而已…有兴趣的朋友可以去钻研钻研再和我交流交流 这里给出代码:

1
2
3
4
5
6
7
8
9
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
	int i,j,k=0;
	for(i=1;i<=n;i++) rank[sa[i]]=i;
	for(i=0;i<n;height[rank[i++]]=k)
	for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
	return;
}

3、一些注意事项:height数组的值应该是从height[1]开始的,而且height[1]应该是等于0的。原因是,因为我们在字符串后面添加了一个0号字符,所以它必然是最小的一个后缀。而字符串中的其他字符都应该是大于0的(前面有提到,使用倍增算法前需要确保这点),所以排名第二的字符串和0号字符的公共前缀(即height[1])应当为0.在调用calheight函数时,要注意height数组的范围应该是[1..n]。所以调用时应该是calheight(r,sa,n)而不是calheight(r,sa,n+1)。要理解清楚这里的n的含义是什么。

calheight过程中,对rank数组求值的for语句的初始语句是i=1 而不是i=0 的原因,和上面说的类似,因为sa[0]总是等于那个已经失去作用的0号字符,所以没必要求出其rank值。当然你错写成for (i=0 ..),也不会有什么问题。

三、后缀数组解题总结:

1、求单个子串的不重复子串个数。SPOJ 694、SPOJ 705.

这个问题是一个特殊求值问题。要认识到这样一个事实:一个字符串中的所有子串都必然是它的后缀的前缀。(这句话稍微有点绕…)对于每一个sa[i]后缀,它的起始位置sa[i],那么它最多能得到该后缀长度个子串(n-sa[i]个),而其中有height[i]个是与前一个后缀相同的,所以它能产生的实际后缀个数便是n-sa[i]-height[i]。遍历一次所有的后缀,将它产生的后缀数加起来便是答案。
代码及题解:http://hi.baidu.com/fhnstephen/blog/item/68f919f849748668024f56fb.html

2、后缀的最长公共前缀。(记为lcp(x,y))

这是height数组的最基本性质之一。具体的可以参看罗穗骞的论文。后缀i和后缀j的最长公共前缀的长度为它们在sa数组中所在排位之间的height值中的最小值。这个描述可能有点乱,正规的说,令x=rank[i],y=rank[j],x<y,那么lcp(i,j)=min(height[x+1],height[x+2]…height[y])。lcp(i,i)=n-sa[i]。解决这个问题,用RMQ的ST算法即可(我只会这个,或者用最近公共祖先那个转化的做法)。

3、最长重复子串(可重叠)

要看到,任何一个重复子串,都必然是某两个后缀的最长公共前缀。因为,两个后缀的公共前缀,它出现在这两个后缀中,并且起始位置时不同的,所以这个公共前缀必然重复出现两次以上(可重叠)。而任何两个后缀的最长公共前缀为某一段height值中的最小值,所以最大为height值中的最大值(即某个lcp(sa[i],sa[i+1]))。所以只要算出height数组,然后输出最大值就可以了。
一道题目和代码:http://hi.baidu.com/fhnstephen/blog/item/4ed09dffdec0a78eb801a0ba.html

4、最长重复不重叠子串 PKU1743

这个问题和3的唯一区别在于能否重叠。加上不能重叠这个限制后,直接求解比较困难,所以我们选择二分枚举答案,将问题转换为判定性问题。假设当时枚举的长度为k,那么要怎样判断是否存在长度为k的重复不重叠子串呢?

首先,根据height数组,将后缀分成若干组,使得每组后缀中,后缀之间的height值不小于k。这样分组之后,不难看出,如果某组后缀数量大于1,那么它们之中存在一个公共前缀,其长度为它们之间的height值的最小值。而我们分组之后,每组后缀之间height值的最小值大于等于k。所以,后缀数大于1的分组中,有可能存在满足题目限制条件的长度不小于k的子串。只要判断满足题目限制条件成立,那么说明存在长度至少为k的合法子串。

对于本题,限制条件是不重叠,判断的方法是,一组后缀中,起始位置最大的后缀的起始位置减去起始位置最小的后缀的起始位置>=k。满足这个条件的话,那么这两个后缀的公共前缀不但出现两次,而且出现两次的起始位置间隔大于等于k,所以不会重叠。

深刻理解这种height分组方法以及判断重叠与否的方法,在后面的问题中起到举足轻重的作用。
练习及题解:http://hi.baidu.com/fhnstephen/blog/item/85a25b208263794293580759.html

5、最长的出现k次的重复(可重叠)子串。 PKU3261

使用后缀数组解题时,遇到“最长”,除了特殊情况外(如问题3),一般需要二分答案,利用height值进行分组。本题的限制条件为出现k次。只需判断,有没有哪一组后缀数量不少于k就可以了。相信有了我前面问题的分析作为基础,这个应该不难理解。注意理解“不少于k次”而不是“等于k次”的原因。如果理解不了,可以找个具体的例子来分析分析。
题目及题解:http://hi.baidu.com/fhnstephen/blog/item/be7d15133ccbe7f0c2ce79bb.html

6、最长回文子串 ural1297

这个问题没有很直接的方法可以解决,但可以采用枚举的方法。具体的就是枚举回文子串的中心所在位置i。注意要分回文子串的长度为奇数还是偶数两种情况分析。然后,我们要做的,是要求出以i为中心的回文子串最长为多长。利用后缀数组,可以设计出这样一种求法:求i往后的后缀与i往前的前缀的最长公共前缀。我这里的表述有些问题,不过不影响理解。

要快速地求这个最长前缀,可以将原串反写之后接在原串后面。在使用后缀数组的题目中,连接两个(n个)字符串时,中间要用不可能会出现在原串中,不一样的非0号的字符将它们隔开。这样可以做到不影响后缀数组的性质。然后,问题就可以转化为求两个后缀的最长公共前缀了。具体的细节,留给大家自己思考…(懒…原谅我吧,都打这么多字了..一个多小时了啊TOT )
题目及题解:http://hi.baidu.com/fhnstephen/blog/item/68342f1d5f9e3cf81ad576ef.html

7、求一个串最多由哪个串复制若干次得到 PKU2406

具体的问题描述请参考PKU2406.这个问题可以用KMP解决,而且效率比后缀数组好。 利用后缀数组直接解决本题也很困难(主要是,就算二分答案,也难以解决转变而成的判定性问题。上题也是),但可以同过枚举模板串的长度k(模板串指被复制的那个串)将问题变成一个后缀数组可以解决的判定性问题。首先判断k能否被n整除,然后只要看lcp(1,k+1)(实际在用c写程序时是lcp(0,k))是否为n-k就可以了。

为什么这样就行了呢?这要充分考虑到后缀的性质。当lcp(1,k+1)=n-k时,后缀k+1是后缀1(即整个字符串)的一个前缀。(因为后缀k+1的长度为n-k)那么,后缀1的前k个字符必然和后缀k+1的前k个字符对应相同。而后缀1的第k+1..2k个字符,又相当于后缀k+1的前k个字符,所以与后缀1的前k个字符对应相同,且和后缀k的k+1..2k又对应相同。依次类推,只要lcp(1,k+1)=n-k,那么s[1..k]就可以通过自复制n/k次得到整个字符串。找出k的最小值,就可以得到n/k的最大值了。
题目及题解:http://hi.baidu.com/fhnstephen/blog/item/5d79f2efe1c3623127979124.html

8、求两个字符串的最长公共子串。Pku2774、Ural1517

首先区分好“最长公共子串”和“最长公共子序列”。前者的子串是连续的,后者是可以不连续的。

对于两个字符串的问题,一般情况下均将它们连起来,构造height数组。然后,最长公共子串问题等价于后缀的最长公共前缀问题。只不过,并非所有的lcp值都能作为问题的答案。只有当两个后缀分属两个字符串时,它们的lcp值才能作为答案。与问题3一样,本题的答案必然是某个height值,因为lcp值是某段height值中的最小值。当区间长度为1时,lcp值等于某个height值。所以,本题只要扫描一遍后缀,找出后缀分属两个字符串的height值中的最大值就可以了。判断方法这里就不说明了,留给大家自己思考…
题目及题解:
http://hi.baidu.com/fhnstephen/blog/item/8666a400cd949d7b3812bb44.html
http://hi.baidu.com/fhnstephen/blog/item/b5c7585600cadfc8b645aebe.html

9、重复次数最多的重复子串 SPOJ 687,Pku3693

难度比较大的一个问题,主要是罗穗骞的论文里的题解写得有点含糊不清。题目的具体含义可以去参考Pku3693.

又是一题难以通过二分枚举答案解决的问题(因为要求的是重复次数),所以选择朴素枚举的方法。先枚举重复子串的长度k,再利用后缀数组来求长度为k的子串最多重复出现多少次。注意到一点,假如一个字符串它重复出现2次(这里不讨论一次的情况,因为那是必然的),那么它必然包含s[0],s[k],s[2k]…之中的相邻的两个。所以,我们可以枚举一个数i,然后判断从ik这个位置起的长度为k的字符串能重复出现多少次。判断方法和8中的相似,lcp(ik,(i+1)k)/k+1。但是,仅仅这样会忽略点一些特殊情况,即重复子串的起点不在[ik]位置上时的情况。这种情况应该怎么求解呢?
看下面这个例子:
aabababc
当k=2,i=1时,枚举到2的位置,此时的重复子串为ba(注意第一位是0),lcp(2,4)=3,所以ba重复出现了2次。但实际上,起始位置为1的字符串ab出现次数更多,为3次。我们注意到,这种情况下,lcp(2,4)=3,3不是2的整数倍。说明当前重复子串在最后没有多重复出现一次,而重复出现了部分(这里是多重复出现了一个b)。如果我这样说你没有看懂,那么更具体地:
sa[2]=bababc
sa[4]=babc
lcp=bab
现在注意到了吧,ba重复出现了两次之后,出现了一个b,而a没有出现。那么,不难想到,可以将枚举的位置往前挪一位,这样这个最后的b就能和前面的一个a构成一个重复子串了,而假如前挪的一位正好是a,那么答案可以多1。所以,我们需要求出a=lcp(i
k,(i+1)*k)%n,然后向前挪k-a位,再用同样的方法求其重复出现的长度。这里,令b=k-a,只需要lcp(b,b+k)>=k就可以了。实际上,lcp(b,b+k)>=k时,lcp(b,b+k)必然大于等于之前求得的lcp值,而此时答案的长度只加1。没有理解的朋友细细体会下上图吧。
题目及题解:http://hi.baidu.com/fhnstephen/blog/item/870da9ee3651404379f0555f.html

10.多个串的公共子串问题 PKU3294

首先将串连接起来,然后构造height数组,然后怎么办呢?
对,二分答案再判断是否可行就行了。可行条件很直观:有一组后缀,有超过题目要求的个数个不同的字符串中的后缀存在。即,假如题目要求要出现在至少k个串中,那么就得有一组后缀,在不同字符串中的后缀数大于等于k。
题目及题解:http://hi.baidu.com/fhnstephen/blog/item/49c3b7dec79ec5e377c638f1.html

11、出现或反转后出现所有字符串中的最长子串 PKU1226

http://hi.baidu.com/fhnstephen/blog/item/7fead5020a16d2da267fb5c0.html

12、不重叠地至少两次出现在所有字符串中的最长子串

spoj220 http://hi.baidu.com/fhnstephen/blog/item/1dffe1dda1c98754cdbf1a35.html

之所以把两题一起说,因为它们大同小异,方法在前面的题目均出现过。对于多个串,连起来;反转后出现,将每个字符串反写后和原串都连起来,将反写后的串和原串看成同一个串;求最长,二分答案后height分组;出现在所有字符串中(反写后的也行),判断方法和10一样,k=n而已;不重叠见问题4,只不过这里对于每个字符串都要进行检验而已。

13、两个字符串的重复子串个数。 Pku3415

我个人觉得颇有难度的一个问题。具体的题目描述参看Pku3415。
大家可以移步到这:http://hi.baidu.com/fhnstephen/blog/item/bf06d001de30fc034afb51c1.html

14、最后的总结

用后缀数组解题有着一定的规律可循,这是后缀的性质所决定的,具体归纳如下:
1、N个字符串的问题(N>1)
方法:将它们连接起来,中间用不会出现在原串中的,互不相同的,非0号字符分隔开。

2、无限制条件下的最长公共子串(重复子串算是后缀们的最长公共前缀)
方法:height的最大值。这里的无限制条件是对子串无限制条件。最多只能是两个串的最长公共子串,才可以直接是height的最大值。

3、特殊条件下的最长子串
方法:二分答案,再根据height数组进行分组,根据条件完成判定性问题。三个或以上的字符串的公共子串问题也需要二分答案。设此时要验证的串长度为len,特殊条件有:
3.1、出现在k个串中
条件:属于不同字符串的后缀个数不小于k。(在一组后缀中,下面省略)
3.2、不重叠
条件:出现在同一字符串中的后缀中,出现位置的最大值减最小值大于等于len。
3.3、可重叠出现k次
条件:出现在同一字符串中的后缀个数大于等于k。若对于每个字符串都需要满足,需要逐个字符串进行判断。

4、特殊计数
方法:根据后缀的性质,和题目的要求,通过自己的思考,看看用后缀数组能否实现。一般和“子串”有关的题目,用后缀数组应该是可以解决的。

5、重复问题
知道一点:lcp(i,i+k)可以判断,以i为起点,长度为k的一个字符串,它向后自复制的长度为多少,再根据具体题目具体分析,得出算法即可。

memory prefetch浅析

原文地址: http://www.searchtb.com/2014/03/memory-prefetch%e6%b5%85%e6%9e%90.html , 感谢原作者分享。

最近在用vtune分析程序性能瓶颈时,发现一些内存访问的地方竟然成了cpu热点。经过仔细分析,发现这些热点主要是对大数组非连续位置的访问的引起的。比较消耗cpu的原因应该是 cache不命中。因为像这样局部性很差的内存访问逻辑,对cache是很不友好的。于是想到了prefetch……

x86(以及其他很多体系结构)的CPU提供了prefetch系列指令,用于将指定地址的内存预取到cache。如”prefetcht0 (%rax)”将以$rax所保存的值为地址的内存所在的cache line(大小一般是64byte)载入每一级cache。

在适当位置加了prefetch之后,程序里相应的cpu热点果然得以消除,程序性能得到提升。

现象

在此也写一段测试程序,体验一下 prefetch的功效,并做一些简单的分析。(注,分析硬件的行为实在是一件痛苦的事情。对于软件来说,源代码摆在那里,一是一、二是二,很多问题都是 确定的。而硬件不仅看不到它的具体实现,也鲜有文档。并且相比操作系统为软件提供的虚拟而单纯的运行环境,硬件环境复杂多变,有时候实在让人难以琢磨。所 以以下分析实在难免存在谬误。不妥之处还请包涵。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <xmmintrin.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <math.h>
void usage()
{
	printf("usage: BIN file step prefetch\n");
	exit(1);
}
inline int calcu(int input)
{
#ifdef EMPTYCALC
	return input;
#endif
	int val = (input % 99) * (input / 98);
	val = val ? val : 1;
#ifdef HEAVYCALC
	double d = (double)input / (double)val;
	return (int)pow(d, 1999.9);
#endif
	double n = sqrt(sqrt((double)(unsigned)input * 1.3));
	double m = sqrt(sqrt((double)(unsigned)val * 0.9));
	return (int)((double)input * (double)val * m / (n ? n : 1.1));
}
int run_withprefetch(const int *array, int size, int step, int prefetch)
{
	int result = 0;
	printf("run with prefetch(%d)...\n", prefetch);
	for (int i = 0; i < step; i++) {
		for (int j = i; j < size; j += step) {
			int k = j + step * prefetch;
			if (k  < size) {
				_mm_prefetch(&array[k], _MM_HINT_T0);
				//const int *addr = &array[k];
				//__asm__ __volatile__ ("mov (%0), %%eax"::"r"(addr):"eax");
				//__asm__ __volatile__ ("mov %0, %%eax"::"r"(k):"eax");
			}
			result += calcu(array[j]);
		}
	}
	return result;
}
int run(const int *array, int size, int step)
{
	int result = 0;
	printf("run...\n");
	for (int i = 0; i < step; i++) {
		for (int j = i; j < size; j += step) {
			//asm volatile("lfence");
			result += calcu(array[j]);
		}
	}
	return result;
}
int main(int argc, const char *argv[])
{
	if (argc != 4) {
		usage();
	}
	int step = atoi(argv[2]);
	int prefetch = atoi(argv[3]);
	int fd = open(argv[1], O_RDONLY);
	if (fd == -1) {
		usage();
	}
	struct stat st;
	int ret = fstat(fd, &st);
	if (ret != 0) {
		usage();
	}
	int array_size = st.st_size / sizeof(int);
	printf("array size: %d, step: %d. ", array_size, step);
	const int *array = (const int *)mmap(NULL, st.st_size, PROT_READ, MAP_POPULATE|MAP_SHARED, fd, 0);
	if (array == MAP_FAILED) {
		usage();
	}
	struct timeval tv1, tv2;
	gettimeofday(&tv1, NULL);
	int result = 0;
	if (prefetch == 0) {
		result = run(array, array_size, step);
	}
	else if (prefetch > 0) {
		result = run_withprefetch(array, array_size, step, prefetch);
	}
	gettimeofday(&tv2, NULL);
	tv2.tv_sec -= tv1.tv_sec;
	tv2.tv_usec -= tv1.tv_usec;
	if (tv2.tv_usec < 0) {
		tv2.tv_usec += 1000000;
		tv2.tv_sec--;
	}
	printf("time cost: %d.%06d, ", tv2.tv_sec, tv2.tv_usec);
	printf("result: %d\n", result);
	return result;
}

程序mmap一个大文件(由file参数指定)作为大数组,对数组中的每一个元素进行一定的变换逻辑(calc函数,通过宏定义选择三种不同复杂度的逻辑)、然后加和。

对于数组元素的访问支持顺序访问和跳跃访问(step参数,跳跃间隙)、支持预取(prefetch参数,预取提前量)。

(注意,程序最终产生的result的值只跟选择的计算逻辑和输入文件的内容相关,跟读内存的顺序无关。所以,后续不管给程序加了什么稀奇古怪的读内存逻辑,最终的result都是一致的。这就确保了我们所加的各种读内存逻辑没有引入BUG。)

一些测试结果:

1
2
3
4
5
6
7
$ ll -h test.tar.gz 
-rw-rw-r-- 1 xiangy xiangy 1.8G Jun 27 09:37 test.tar.gz
$ g++ -O2 prefetch.cpp -DHEAVYCALC -o prefetch.heavy
$ g++ -O2 prefetch.cpp -DEMPTYCALC -o prefetch.empty
$ g++ -O2 prefetch.cpp -o prefetch.normal
$ ./prefetch.normal 
usage: BIN file step prefetch

(选择不同复杂度的计算逻辑,编译成以不同后缀命名的可执行文件。)

1
2
3
[case-1]$ ./prefetch.empty test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 23.980005, result: 692002678

(空计算+跳读内存。预期内存访问基本上都是cache miss,而计算逻辑基本上又不花时间,所以最终花费的时间主要就是读内存时间。记住这个值,下面的case经常需要参考它。)

1
2
3
4
5
6
7
8
9
[case-2]$ ./prefetch.normal test.tar.gz 1 0
array size: 468787200, step: 1. run...
time cost: 22.846302, result: 1309150882
[case-3]$ ./prefetch.normal test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 66.041256, result: 1309150882
[case-4]$ ./prefetch.normal test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 28.247350, result: 1309150882

(以上是普通计算的运行情况。case-2顺序读内存预期基本上都是cache hit的,最终花费的时间主要是执行计算逻辑的时间;case-3跳读内存时间花费大量增加;case-4加了预取之后,时间花费基本上恢复到case-2的水平。)

1
2
3
4
5
6
7
8
9
[case-5]$ ./prefetch.heavy test.tar.gz 1 0
array size: 468787200, step: 1. run...
time cost: 47.386533, result: 1625037789
[case-6]$ ./prefetch.heavy test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 107.783801, result: 1625037789
[case-7]$ ./prefetch.heavy test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 51.492479, result: 1625037789

(以上是复杂计算的运行情况。跟前面的表现基本一致,跳读带来了大量的时间增长,而预取又基本恢复到顺序读时的水平。)

如果读内存开销很小、或者计算开销很小,prefetch也有用么?

1
2
3
[case-8]$ ./prefetch.empty test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 24.253892, result: 692002678

(空计算+跳读内存,预取效果跟不加预取时差不多。)

1
2
3
[case-9]$ ./prefetch.normal test.tar.gz 1 4
array size: 468787200, step: 1. run with prefetch(4)...
time cost: 22.896790, result: 1309150882

(普通计算+顺序读内存+预取,效果跟不加预取时也差不多。)

可见当读内存存在一定开销、且开销小于或相当于计算开销时,通过适当的prefetch能够将跳读内存开销隐藏掉,基本上达到顺序读内存的效果。

反过来如果计算开销不大、或者读内存本身没什么开销,单纯想通过prefetch来提升读内存的速度,效果并不明显。

prefetch原理

为什么prefetch能达到这样的效果呢?简单来说,prefetch将原本串行工作的计算过程和读内存过程并行化了。如:

1
2
3
4
load-1                            load-1  
calc-1                   =>       calc-1    load-2  
          load-2                            calc-2    load-3  
          calc-2                                      calc-3  

但是实际上却又并非如此简单。

在一个程序中,组成程序本身的指令虽然是有顺序的,但是CPU在执行指令的时候并不一定按部就班一条一条的去执行,指令之间有很多并行性可以去挖掘。(这就是所谓的ILP,Instruction Level Parallelism,指令级并行。)

两条指令想要并行执行需要满足三个条件:

1、指令之间没有数据依赖
如:a = b * 3; c = d + 5;, 就没有依赖;
如:a = b * 3; c = a + 5; ,“写后读”依赖。第二条指令需要a的值作为输入,而a的值依赖于第一条指令的计算结果;
如:a = b * 3; a = d + 5; ,“写后写”依赖。不过虽然第二条指令一定要在第一条指令修改a的值之后才能修改a的值(确保最终a的值是d + 5的结果),但是其实两条指令是可以并行执行的,最后将结果commit到a的时候再串行就OK了;
如:a = b * 3; b = d + 5;, “读后写”依赖。同样,虽然第二条指令一定不能在第一条指令读取b的值之前就将b的值修改(确保第一条指令读到的是旧值),但是只要确保第一条指令先拿到 b的旧值、或者直接跟生成b的旧值的那条指令关联上,之后两条指令还是可以并行执行的;

2、CPU功能部件充足
CPU中用来执行具体操作的功能部件是有限的,假设CPU只有一个乘法器。
如:a = b * 3; c = d + 5; ,一个使用乘法器、另一个使用加法器,互不影响就可以并行;
如:a = b * 3; c = d * 5; ,两条指令都需要使用这个仅有的乘法器,就只能串行了(当然也未必是第一条指令先占用乘法器,因为可能它所依赖的b的值尚未ready、而第二条指令所需要的d已经OK);

3、CPU已经看到这两条指令
程序执行的指令序列可能无穷无尽(考虑 到有循环),CPU为了挖掘并行性不可能一下子分析所有指令,一定会有个限度。在经典的流水线算法--tomasulo算法--中,这个限度就是 RS(reservation station,保留站)的数目。CPU取指部件按指令顺序将指令放入RS,并设置它们的依赖关系(RS提供了这样的支持)。存在于RS中的指令当输入已 经ready、且需要的功能部件有空余时,便会开始执行。

遇到分支指令时指令序列如何确定呢?分支指令在执行完成之前根本就不知道程序要往哪里走。解决办法就是分支预测,根据一些统计信息猜测程序的走向。然后无视这些分支,就跟没有分支时一样去执行。如果分支预测错了,再回滚回来,按正确的序列重新执行。

回到我们的例子,每个loop有一个 load过程+一个calc过程,calc过程依赖于load过程。但是下一次loop的load并不依赖于上一loop的calc过程,并且load和 calc使用不同的CPU功能部件,所以这两个过程是可以并行的。(for循环在经历很多次loop之后才会退出,每次分支的走向都是一样的,可以近似认 为分支预测一定成功。)

prefetch加与不加,前两个并行条件都是不会变的:prefetch既不会改变指令之间的依赖关系、也不会多占用或少占用CPU功能部件。但是为什么加上prefetch会有效果呢?

区别只在于第三个并行条件。试想当程序 执行到第N次loop时(loop-N),由于calc过程复杂,指令很多,RS一直被占满。直到计算进入尾声,loop-(N+1)的指令才进入RS, 这时CPU才知道要去load loop-(N+1)的input。而这些input在cache中不能命中,需要经历漫长的读内存过程,导致loop-(N+1)的calc指令卡在 RS中得不到执行。相当于load和calc过程被串行化了。

加了prefetch之后 呢?loop-(N+X)的prefetch指令排在loop-N的计算指令之前,早早的就能进入RS。这些load指令是计算的源头,其本身并没有依赖 别的数据,所以一旦内存通道空闲下来prefetch就可以开始工作了。于是load与calc才正真并行起来。

如下面示意:

case-2,顺序读内存,cache全命中:

1
2
3
4
5
6
7
8
9
10
11
calc-11
calc-12
calc-13    calc-21
           calc-22
           calc-23    calc-31
                      calc-32
                      calc-33    calc-41
                                 calc-42
                                 calc-43    calc-51
                                            calc-52
                                            calc-53

(每个loop约花费2个单位时间。)

case-3,跳读内存,cache全不命中:

1
2
3
4
5
6
7
8
9
10
11
12
13
load-11
load-12
calc-11
calc-12
calc-13    load-21
           load-22
           calc-21
           calc-22 
           calc-23    load-31
                      load-32
                      calc-31
                      calc-32
                      calc-33

(每个loop约花费4个单位时间。注,假设CPU执行到calc-N3的时候才看到有load-(N+1)1。)

case-4,跳读内存,加预取:

1
2
3
4
5
6
7
8
9
10
11
12
13
load-11
load-12
calc-11    prefetch-21
calc-12    prefetch-22
calc-13    calc-21    prefetch-31
           calc-22    prefetch-32
           calc-23    calc-31    prefetch-41
                      calc-32    prefetch-42
                      calc-33    calc-41    prefetch-51
                                 calc-42    prefetch-52
                                 calc-43    calc-51
                                            calc-52
                                            calc-53

(每个loop约花费2个单位时间。注,在calc-N1之前prefetch-(N+X)1就已经发起了。)

通过prefetch,使这些既耗时又 被后续指令依赖的load指令提前进入CPU的视野,让CPU可以利用可能空闲的内存带宽,提前完成读操作。另一方面,使用prefetch预取内存之 后,跟依赖于它的那些计算指令拉开了距离,使得计算指令不必等到马上就得使用load的输入时才临时抱佛脚。拉开相关依赖指令的距离正是编译器优化代码的 一种常用手段,通常通过指令重排调整无关指令的顺序来实现。

到这里prefetch的大致逻辑已经理清楚了,但是仔细想一下其实问题还很多……

例子引出的问题

第一个问题,为什么case-3(读内 存+普通计算)的执行时间(66.041256)要比case-1(单纯的读内存)时间(23.980005)+case-2(单纯的计算)时间 (22.846302)更长呢?按理说,就算load指令和calc指令完全串行,case-3的执行时间最多也就等于1、2之合吧。

这个问题应该可以用内存多通道来解释。 现在CPU访问内存的通道一般会有两个或以上。在case-1中,单纯的读内存其实并不代表串行的读内存。多个内存通道是可以让多个load指令并行工作 的,以充分利用内存带宽。而在case-3中,由于引入了一堆计算指令,导致RS被装满,CPU无法同时看到当前loop和下一个loop的load请 求,也就无法将两次load并行化。所以,更准确来说,case-3耗时这么长的原因并不是load与calc无法并行,而是load与load无法并 行。loop-N的calc过程跟loop-(N+1)的load过程是并行的,但是在loop-(N+1) load完成并进行calc之前,loop-(N+2)的load指令还未进入CPU的视野,所以无法与loop-(N+1)的load并行。

如何证实这一点呢?

我们在case-1中加一个lfence指令试试看。lfence是x86提供的内存屏障指令,作用是确保load操作的顺序:lfence之前的load操作必须先于lfence之后的load操作。如此便打破了load的并行性(如果真如刚才所说,并行性存在的话)。

修改run函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
int run(const int *array, int size, int step)
{
	int result = 0;
	printf("run...\n");
	for (int i = 0; i < step; i++) {
		for (int j = i; j < size; j += step) {
			asm volatile("lfence");
			result += calcu(array[j]);
		}
	}
	return result;
}

再次运行case-1:

1
2
3
4
[case-1.1]$ g++ -O2 prefetch.cpp -DEMPTYCALC
[case-1.1]$ ./a.out test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 63.999864, result: 692002678

(强制让load不能并行之后,case-1.1的耗时直接变成了case-3的水平。说明在原本的case-1中load是存在很大的并行度的。)

再以加lfence的代码运行一下case-6(未加prefetch、复杂计算)看看,如果在复杂计算+跳读内存的情况下,读内存的并行性已经很少的话,加了lfence之后的耗时应该跟加之前差不多:

1
2
3
4
[case-6.1]$ g++ -O2 prefetch.cpp -DHEAVYCALC
[case-6.1]$ ./a.out test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 114.787379, result: 1625037789

(果然如此。)

还可以同时运行两个程序来看看是什么情 况。两个程序同时运行时,由于kernel load balance的作用,它们会尽量运行在不同的CPU上、且尽量不共享cache。那么,如果两个进程都总是能cache hit,则运行时间应该跟单个进程运行时差不多;反之如果总是cache miss,则两个进程会争抢内存带宽,运行时间会有所增加。

1
2
3
[case-2.2]$ ./prefetch.normal test.tar.gz 1 0 | ./prefetch.normal test.tar.gz 1 0
array size: 468787200, step: 1. run...
time cost: 22.964594, result: 1309150882

(两个顺序读内存的普通计算一起运行,因为总是cache hit,所以跟单个运行的时间差不多。)

1
2
3
[case-1.2]$ ./a.out test.tar.gz 1024 0 | ./a.out test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 63.973557, result: 692002678

(两个加了lfence的进程一起运行,由于进程内的内存访问已经串行化了,两个进程可以各自使用一个内存通道,所以运行时间跟单个进程运行时差不多。)

1
2
3
4
5
6
[case-1.3]$ ./prefetch.empty test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 24.083044, result: 692002678
[case-1.4]$ ./prefetch.empty test.tar.gz 1024 0 | ./prefetch.empty test.tar.gz 1024 0
array size: 468787200, step: 1024. run...
time cost: 37.948864, result: 692002678

(而用之前没加过lfence的程序再试一下,两个进程同时运行时,由于争抢内存带宽,运行时间就会受影响。)

prefetch提前量

还有一个问题也可以用内存多通道来解释,即prefetch提前量问题。先就之前的程序继续看几个case:

1
2
3
4
5
6
7
8
9
10
11
12
13
$ for x in 1 2 4 8 16 32; do ./prefetch.normal test.tar.gz 1024 $x; done
array size: 468787200, step: 1024. run with prefetch(1)...
time cost: 36.262511, result: 1309150882
array size: 468787200, step: 1024. run with prefetch(2)...
time cost: 29.902517, result: 1309150882
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 28.052798, result: 1309150882
array size: 468787200, step: 1024. run with prefetch(8)...
time cost: 26.040215, result: 1309150882
array size: 468787200, step: 1024. run with prefetch(16)...
time cost: 26.198825, result: 1309150882
array size: 468787200, step: 1024. run with prefetch(32)...
time cost: 25.910506, result: 1309150882

prefetch提前量从1增大到32。从结果看,当提前量小的时候,prefetch效果不明显。为什么呢?

假设提前量为1,那么loop-N会为 loop-(N+1)进行预取。但是从前面普通计算的数据可以看出,就一个loop而言,load的时间是多于calc时间的(从总量上说,load并行 之后才与calc时间相当,那么单独的load就应该比calc耗时长)。所以当执行到loop-(N+1)的时候,prefetch应该尚未完成。

再假设提前量为4,loop-N会为 loop-(N+4)做预取,loop-(N+1)为loop-(N+5)预取。而在进入loop-(N+1)时,loop-(N+4)的预取尚未完成, 而此时发起的loop-(N+5)的预取就能与之并行。可见增大提前量能更好的利用内存带宽。(虽然说以N为提前量就可以充分利用N个内存通道,但是机器 上还有kernel和其他进程也在使用内存,未必就能让你独占内存带宽。所以使用大于N的提前量更能充分利用空余的内存带宽。)

当然提前量肯定不能太大,否则等真正用到数据的时候,预取好的数据可能已经被从cache中挤出去了。

用mov代替prefetch?

prefetch指令可以用来预取,难道不用prefetch就不行了么?

我们将之前的run_withprefetch函数修改一下,把prefetch替换成简单的load操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int run_withprefetch(const int *array, int size, int step, int prefetch)
{
	int result = 0;
	printf("run with prefetch(%d)...\n", prefetch);
	for (int i = 0; i < step; i++) {
		for (int j = i; j < size; j += step) {
			int k = j + step * prefetch;
			if (k  < size) {
				const int *addr = &array[k];
				asm volatile("mov (%0), %%eax"::"r"(addr):"eax");
			}
			result += calcu(array[j]);
		}
	}
	return result;
}

重跑case-4:

1
2
3
4
[case-4.1]$ g++ -O2 prefetch.cpp
[case-4.1]$ ./a.out test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 37.312423, result: 1309150882

确实比不加prefetch的情况case-3(66.041256)要好很多,但还是比不上原来的case-4(28.247350)。

那么prefetch比直接movload好在哪里呢?
1、使用mov也同样能达到让load操作提前进入CPU视野的目的
2、使用mov访问过的内存同样会被cache住
3、仅仅是因为mov操作多占用了一个寄存器么?把代码改成这样看看(使用原来的prefetch但是多占用一个寄存器):

1
2
3
4
5
6
7
8
9
if (k  < size) {
	_mm_prefetch(&array[k], _MM_HINT_T0);
	__asm__ __volatile__ ("mov %0, %%eax"::"r"(k):"eax");
}

[case-4.2]$ g++ -O2 prefetch.cpp
[case-4.2]$ ./a.out test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 28.051848, result: 1309150882

可见仅仅多占用一个寄存器,貌似并没有什么影响。(在tomasulo算法中,这里实际上并没有多占用寄存器,而是多占用了RS。)

前面提到了tomasulo算法,提到了RS,这里面还有个东西叫ROB(reorder buffer,指令重排缓存)。前面还提到过对于“写后写”依赖指令,在执行过程中是可以并行的,只要保证最后写回的顺序不变就行了。ROB就能完成这个功能。

CPU取指令之后除了将其放入RS(让 其可以乱序执行),还要按顺序将其放入ROB。执行完成后的指令最终在ROB中排队,然后按顺序提交(将结果写回寄存器或内存)。ROB还有另一个很重要 的作用,就是分支预测失败时的回滚。分支指令也跟其他指令一样要在ROB中排队。如果分支指令执行完以后发现分支预测错了,则将ROB里排在这条分支之后 的指令及其结果都清理掉就行了。因为ROB是按指令顺序排队的,由于分支预测出错而被错误执行的那些指令一定都排在分支指令之后。

回到我们的例子,”mov (addr), %eax”这条指令会一直占着ROB,直到load完成。这将导致后续的指令结果一直得不到提交,尚未被CPU取走的指令又会因为无法获得ROB而不能被 取走。这又回到了类似于case-3(未加prefetch)的情形,指令无法大量进入CPU的视野,以致于内存访问无法占满内存带宽。只不过因为ROB 的资源没有RS那么紧张,所以阻塞的情况没有case-3那么严重。

基于以上说明,我们改造case-6(未加prefetch、复杂计算)看看。对于复杂计算,calc过程的指令更多,按理说,阻塞的情况会更严重,直接load应该效果更差。

1
2
3
4
[case-6.2]$ g++ -O2 prefetch.cpp -DHEAVYCALC
[case-6.2]$ ./a.out test.tar.gz 1024 4
array size: 468787200, step: 1024. run with prefetch(4)...
time cost: 100.910547, result: 1625037789

果然,这个结果比起原本的case-6(107.783801)已经没有优势了。

那么为什么prefetch不会受 ROB的大小限制呢?因为prefetch是一个特殊指令,没有输出,对程序上下文也没有影响,甚至于分支预测失败时也不需要回滚。那么CPU完全没必要 让prefetch指令进ROB(当然RS还是要进的,因为prefetch可能依赖于前面指令的结果)。

其他问题 关于硬件prefetch

虽然CPU提供了显式prefetch指令,其实它自己暗中也会进行一些prefetch,可以称之为硬件prefetch。

硬件prefetch有这么几个要点:
1、CPU在经历连续一定次数的cache miss后触发。偶尔发生的一次cache miss是很正常的,比如访问一个不常使用的全局变量;
2、CPU有一定的模式匹配策略,能够识别顺序访问和一些固定step的跳跃访问;
3、最重要的一点,硬件 prefetch不会跨page进行。因为内存是按page管理的,跨page意味着可能触发page fault,这是CPU自己所无法handle的,得由kernel来解决。CPU暗中的prefetch动作对软件来说本来是透明的,不能让 kernel去handle可能本不应发生的page fault,甚至于这样的page fault可能导致segment fault(相反,软件prefetch是软件自己发起的,有什么后果自己承担);

基于第3点,CPU一般不会试图去识别 步长高于512字节的跳跃访问。因为要经历三次cache miss,CPU才能发现跳读内存的步长是相同的(pos2 – pos1 == pos3 – pos2),而后如果触发硬件prefetch的话,大于512字节的步长可能使得访存操作很快跨跃page边界,触发prefetch意义已经不大了。

我们可以继续用前面的程序来观察一下硬件prefetch的表现。将step从1到1024递增,不使用软件prefetch:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$ for x in 1 2 4 8 16 32 64 128 256 512 1024; do ./prefetch.normal test.tar.gz $x 0; done
array size: 468787200, step: 1. run...
time cost: 22.863716, result: 1309150882
array size: 468787200, step: 2. run...
time cost: 23.438035, result: 1309150882
array size: 468787200, step: 4. run...
time cost: 23.846166, result: 1309150882
array size: 468787200, step: 8. run...
time cost: 24.171723, result: 1309150882
array size: 468787200, step: 16. run...
time cost: 25.502980, result: 1309150882
array size: 468787200, step: 32. run...
time cost: 37.461018, result: 1309150882
array size: 468787200, step: 64. run...
time cost: 39.829086, result: 1309150882
array size: 468787200, step: 128. run...
time cost: 44.291904, result: 1309150882
array size: 468787200, step: 256. run...
time cost: 65.332225, result: 1309150882
array size: 468787200, step: 512. run...
time cost: 64.764071, result: 1309150882
array size: 468787200, step: 1024. run...
time cost: 65.952260, result: 1309150882

随着step的逐步增大,可以看出时间消耗分为三个档次:

step 1~16,cost 22~25,因为16个int是64byte,正好在一个cache line中。这么小的step再加上硬件预取基本上都能cache hit了;

step 32~128,cost 37~44,这个区间的cost跨度较大。在这些step下,单个page内读取值的个数分是32、16、8,硬件prefetch尚有一定的余地被触发、并发挥作用。然后随着可预取数目的减少,cost也不段增加;

step 256~,cost 64~65,步长超过了1024byte,硬件prefetch已经不会被触发;

关于TLB cache miss

应用程序中使用地址的都是虚拟地址,访问内存时存在虚拟地址到物理地址的转换过程。转换规则(即页表)是放在内存中的,并由TLB来cache。地址转换需要跳多级页表、多次读内存,所以如果TLB cache miss,代价是很大的。

不过在我的环境中貌似并不存在TLB cache miss的问题。继续改造程序验证一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int run(const int *array, int size, int step, int blocksize)
{
	int result = 0;
	blocksize *= 4096;
	if (blocksize == 0) {
		blocksize = size;
	}
	printf("run... (block=%d pages)\n", blocksize/4096);
	int start = 0;
	int nsize = blocksize;
	while (nsize == blocksize) {
		if (start + blocksize > size)
			nsize = size - start;
		for (int i = 0; i < step; i+=32) {
			for (int j = i; j < nsize; j += step) {
				int thissize = j + 32 < nsize ? j + 32 : nsize;
				for (int k = j; k < thissize; k++) {
					result += calcu(array[start+k]);
				}
			}
		}
		start += nsize;
	}
	return result;
}

改造run函数把整个文件按blocksize划分成若干个块,每个块单独完成跳读逻辑。

于是,当块比较小时块内跳读时所涉及的page比较少,TLB应该能将相关的页表都cache住;而当块比较大,可能就会出现TLB cache miss。

这里面还存在另一个问题,按之前的做 法,每个int跳一次。如果块比较小,第一轮跳读时可能整个块都被cache了,后续的跳读都将cache hit。而块大时又无法cache整个块,后续的跳读又将继续cache miss。这就对观察TLB cache miss产生很大影响。所以程序改成每32个int跳读一次(按前面的结果,跳读32以后性能就不好了),以忽略cache hit所带来的影响。

修改main函数,用第4个参数来传递blocksize(0值表示不分block):

1
2
3
4
5
6
7
8
9
10
11
$ for x in 128 256 512 1024 0; do ./a.out test.tar.gz 1024 $x; done
array size: 468787200, step: 1024. run... (block=128 pages)
time cost: 22.501363, result: 1309150882
array size: 468787200, step: 1024. run... (block=256 pages)
time cost: 22.627935, result: 1309150882
array size: 468787200, step: 1024. run... (block=512 pages)
time cost: 25.064514, result: 1309150882
array size: 468787200, step: 1024. run... (block=1024 pages)
time cost: 24.976720, result: 1309150882
array size: 468787200, step: 1024. run... (block=114450 pages)
time cost: 24.900870, result: 1309150882

看起来TLB cache miss所带来的影响不大。

关于L1 cache

前面一直在讲cache,并没有细分是第几级的cache。其实前面的例子对内存的使用并没有那么精细,主要利用的cache还是L2 cache。

继续用前面分块的例子来看看,因为要考查cache,所以把连读32个int的逻辑去掉。run函数改造如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int run(const int *array, int size, int step, int blocksize)
{
	int result = 0;
	blocksize *= 4096;
	if (blocksize == 0) {
		blocksize = size;
	}
	printf("run... (block=%d pages)\n", blocksize/4096);
	int start = 0;
	int nsize = blocksize;
	while (nsize == blocksize) {
		if (start + blocksize > size)
			nsize = size - start;
		for (int i = 0; i < step; i++) {
			for (int j = i; j < nsize; j += step) {
				result += calcu(array[start+j]);
			}
		}
		start += nsize;
	}
	return result;
}

在一个块内反复跳读,如果以块的大小刚好能被cache住,则程序运行时间会很短;否则又得经历漫长的读内存过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$ for x in 1 2 4 8 16 32 64 128 256 512 1024; do ./a.out test.tar.gz 1024 $x; done
array size: 468787200, step: 1024. run... (block=1 pages)
time cost: 1.614654, result: 692002678
array size: 468787200, step: 1024. run... (block=2 pages)
time cost: 1.554286, result: 692002678
array size: 468787200, step: 1024. run... (block=4 pages)
time cost: 1.625566, result: 692002678
array size: 468787200, step: 1024. run... (block=8 pages)
time cost: 2.621453, result: 692002678
array size: 468787200, step: 1024. run... (block=16 pages)
time cost: 2.697908, result: 692002678
array size: 468787200, step: 1024. run... (block=32 pages)
time cost: 2.724401, result: 692002678
array size: 468787200, step: 1024. run... (block=64 pages)
time cost: 2.710056, result: 692002678
array size: 468787200, step: 1024. run... (block=128 pages)
time cost: 3.864916, result: 692002678
array size: 468787200, step: 1024. run... (block=256 pages)
time cost: 4.241000, result: 692002678
array size: 468787200, step: 1024. run... (block=512 pages)
time cost: 20.216653, result: 692002678
array size: 468787200, step: 1024. run... (block=1024 pages)
time cost: 24.361176, result: 692002678

随着block size的逐渐增大,程序运行时间显现出三个层次。分别代表着L1 cache hit(1〜4)、L2 cache hit(8〜256)、cache miss(512〜)三种状态。看起来L1 cache在本例中影响并不大。

const的使用

1、定义常量

(1)const修饰变量

以下两种定义形式在本质上是一样的。
它的含义是:const修饰的类型为TYPE的变量value是不可变的。

1
2
TYPE const ValueName = value;
const TYPE ValueName = value;
(2)将const改为外部连接

作用于扩大至全局,编译时会分配内存,并且可以不进行初始化,仅仅作为声明,编译器认为在程序其他地方进行了定义.

1
extend const int ValueName = value;

2、指针使用CONST

(1)指针本身是常量不可变
1
2
(char*) const pContent;
const (char*) pContent;
(2)指针所指向的内容是常量不可变
1
2
const (char) *pContent;
(char) const *pContent;
(3)两者都不可变
1
const char* const pContent;
(4)还有其中区别方法,沿着*号划一条线:

如果const位于的左侧,则const就是用来修饰指针所指向的变量,即指针指向为常量;
如果const位于
的右侧,const就是修饰指针本身,即指针本身是常量。

3、函数中使用CONST

(1)const修饰函数参数
a.传递过来的参数在函数内不可以改变(无意义,因为Var本身就是形参)
1
void function(const int Var);
b.参数指针所指内容为常量不可变
1
void function(const char* Var);
c.参数指针本身为常量不可变(也无意义,因为char* Var也是形参)
1
void function(char* const Var);
d.参数为引用,为了增加效率同时防止修改。修饰引用参数时:
1
2
void function(const Class& Var);//引用参数在函数内不可以改变
void function(const TYPE& Var); //引用参数在函数内为常量不可变

这样的一个const引用传递和最普通的函数按值传递的效果是一模一样的,他禁止对引用的对象的一切修改,唯一不同的是按值传递会先建立一个类对象的副本, 然后传递过去,而它直接传递地址,所以这种传递比按值传递更有效.另外只有引用的const传递可以传递一个临时对象,因为临时对象都是const属性, 且是不可见的,他短时间存在一个局部域中,所以不能使用指针,只有引用的const传递能够捕捉到这个家伙.

(2)const 修饰函数返回值

const修饰函数返回值其实用的并不是很多,它的含义和const修饰普通变量以及指针的含义基本相同。

a.

const int fun1() // 这个其实无意义,因为参数返回本身就是赋值。

b.

const int * fun2()
//调用时 const int *pValue = fun2();
//我们可以把fun2()看作成一个变量,即指针内容不可变。

c.

int* const fun3()
//调用时 int * const pValue = fun2();
//我们可以把fun2()看作成一个变量,即指针本身不可变。

一般情况下,函数的返回值为某个对象时,如果将其声明为const时,多用于操作符的重载。
通常,不建议用const修饰函数的返回值类型为某个对象或对某个对象引用的情况。
原因如下:
如果返回值为某个对象为const(const A test = A 实例)或某个对象的引用为const(const A& test = A实例) ,
则返回值具有const属性,则返回实例只能访问类A中的公有(保护)数据成员和const成员函数,
并且不允许对其进行赋值操作,这在一般情况下很少用到。