Trluper

1 介绍

此次project0项目是实现一个键值对存储，数据结构由写时复制的字典树构成。实现的键-值存储可以存储映射到任何类型值的字符串键。键的值存储在表示该键的最后一个字符的节点中(又称终端节点)。例如，考虑在trie中插入kv对("ab"， 1)和("ac"， "val")。

2 Task1:Copy-On-Write trie

• 在本任务中，只需要修改trie .h和trie .cpp来实现写时复制(copy-on-write) tree。在写即复制tree中，操作不会直接修改原始tree中的节点。相反，将为修改后的数据创建新节点，并为新修改的trie返回一个新根。写时复制(Copy-on-write)使我们能够在每次操作之后随时以最小的开销访问该树。考虑在上面的例子中插入("ad"， 2)。我们通过重用原始树中的两个子节点来创建一个新的Node2，并创建一个新的值节点2。(见下图)

• 插入("b"， 3)，我们将创建一个新的根，一个新的节点，并重用以前的节点。通过这种方式，我们可以在每次插入操作之前和之后获得树的内容。只要我们有根对象(Trie类)，我们就可以访问当时Trie中的数据。(见下图)

• 插入(“a”，“abc”)并删除(“ab”，1)，我们可以得到下面的trie。注意，父节点可以有值，并且在删除后需要清除所有不必要的节点。

因此，在这里你需要实现三个函数：

• Get(key):获取键对应的值。

• Put(key, value):设置键对应的值。如果键已经存在，则覆盖现有值。注意，值的类型可能是不可复制的(即std::unique_ptr<int>)。这个方法返回一个新的树。

• Delete(key):删除键的值。这个方法返回一个新的树。

这些操作都不应该直接在trie本身上执行。您应该创建新的树节点，并尽可能重用现有的树节点。 要创建一个新节点，您应该使用TrieNode类上的Clone函数。要重用新树中的现有节点，可以复制std::shared_pt<TrieNode>复制共享指针不会复制底层数据。您不应该在此项目中通过使用new和delete手动分配内存。当没有人有对底层对象的引用时，std::shared_ptr将释放对象。

分析：

• 节点类TrieNode使用map<char, std::shared_ptr<const TrieNode>>来存储这种键值结构，，在这里另一个重要的函数是Clone函数（使用了C++类的构造函数的隐式转换)，Clone函数实现新建树中现有节点
• 叶子类TrieNodeWithValue，继承于TrieNode，增加了叶子节点存值功能
• Trie类，内部声明了root（初始为NULL),三个上述待实现的功能

1 实验准备

作业地址

实验当中提供的数据库，其中表关系如下：

索引创建如下：

1
2
3
4
5
6
7
8

CREATE INDEX ix_people_name ON people (name);
CREATE INDEX ix_titles_type ON titles (type);
CREATE INDEX ix_titles_primary_title ON titles (primary_title);
CREATE INDEX ix_titles_original_title ON titles (original_title);
CREATE INDEX ix_akas_title_id ON akas (title_id);
CREATE INDEX ix_akas_title ON akas (title);
CREATE INDEX ix_crew_title_id ON crew (title_id);
CREATE INDEX ix_crew_person_id ON crew (person_id);

2 SQLite3的一些特性

• SQLite3与MySQL的一些不同是一些命另和函数，其数据库的使用直接采用：

  1 2 3

  $ ls imdb-cmudb2022.db placeholder $ sqlite3 imdb-cmudb2022.db

• 查看表：

  1 2	sqlite> .tables akas crew episodes people ratings titles

• 查看表结构

  1 2 3 4 5 6 7 8

  sqlite> .schema people CREATE TABLE people ( person_id VARCHAR PRIMARY KEY, name VARCHAR, born INTEGER, died INTEGER ); CREATE INDEX ix_people_name ON people (name);

• 更大命令使用.help

  1	sqlite> .help

注意，MySQL当中的一些函数，SQLite未必有，就如concat我就发现没有，SQLite使用||替代字符串拼接

3 实验问题

2022 #### 3.1 Q2 [5 points] (q2_sci_fi) Find the 10Sci-Fiworks with the longest runtimes. Details: Print the title of the work, the premiere date, and the runtime. The column listing the runtime should be suffixed with the string " (mins)", for example, if the runtime_mins value is12, you should output 12 (mins). Note a work is Sci-Fi even if it is categorized in multiple genres, as long as Sci-Fi is one of the genres. Your first row should look like this: Cicak-Man 2: Planet Hitam|2008|999 (mins)

找出10个运行时间最长的“科幻”作品。输出其primary_title、primiered、runtime_minutes，其中runtime_minutes后边要接(mins)。

1 2 3 4

SELECT PRIMARY_TITLE,PREMIERED,(RUNTIME_MINUTES||' (mins)' ) FROM TITLES WHERE GENRES LIKE '%Sci-Fi' order by RUNTIME_MINUTES DESC LIMIT 10;

3.2 q3_oldest_people

Determine the oldest people in the dataset who were born in or after 1900. You should assume that a person without a known death year is still alive. Details: Print the name and age of each person. People should be ordered by a compound value of their age and secondly their name in alphabetical order. Return the first 20 results.

Your output should have the format: NAME|AGE

找出出生于1900后（包含1900），年龄最大的20个人，按照年龄年龄和姓名的字母联合排序。注意没有死亡日期，证明还活着，你要能够处理这类数据

1 2 3 4 5 6 7

select name, case when died is null then 2022-born else died-born end as age from people where born>=1900 order by age desc,name limit 20;

2023

3.1 q2_not_the_same_title

Find the 10 Action movies with the newest premiere date whose original title is not the same as its primary title.

Details: Print the premiere year, followed by the two titles in a special format. The column listing the two titles should be in the format of primary_title (original_title) Note a work is Action even if it is categorized in multiple genres, as long as Action is one of the genres. Also note that it's possible for the premiered year to be in the future. If multiple movies premiered in the same year, order them alphabetically. Your first row should look like this:

1
2
3
4
5

SELECT PREMIERED,(PRIMARY_TITLE||' ('||ORIGINAL_TITLE||')') AS T 
FROM TITLES 
WHERE PRIMARY_TITLE!=ORIGINAL_TITLE 
	AND GENRES LIKE '%Action%' 
order by PREMIERED DESC,T LIMIT 10;

3.2 q3_longest_running_tv

Find the top 20 longest running tv series.

Details: Print the title and the years the series has been running for. The series must have a non NULL premiered year. If the ended date is NULL, assume it to be the current year (2023). If multiple tv series have been running the same number of years, order them alphabetically. Print the top 20 results.

Your output should have the format: TITLE|YEARS_RUNNING Your first row should look like this:Looney Tunes|93

1
2
3
4
5
6
7
8
9

SELECT PRIMARY_TITLE,
CASE 
	WHEN ENDED IS NULL THEN 2023-PREMIERED 
	ELSE ENDED-PREMIERED 
END AS YEARS_RUNNING 
FROM TITLES 
WHERE PREMIERED IS NOT NULL 
	AND TYPE='tvSeries' 
ORDER BY YEARS_RUNNING DESC,PRIMARY_TITLE LIMIT 20;

3.3 q4_directors_in_each_decade

List the number directors born in each decade since 1900.(计算自1900年以来每10年出生的导演人数)

Details: Print the decade in a fancier format by constructing a string that looks like this: 1990s. Order the results by decade.

Your output should look like this: DECADE|NUM_DIRECTORS Your first row should look like this: 1900s|376

分析：从事领域存储在crew表的category,其中人的出生时期存储在people表，两表通过person_id联结，people的为主键，crew的为外键

1
2
3
4
5
6
7
8
9
10
11
12

SELECT decade || 's',
    COUNT(*)
FROM (
        SELECT DISTINCT(people.person_id),
            FLOOR(people.born / 10) * 10 AS decade
        FROM people
            INNER JOIN crew ON crew.person_id = people.person_id
        WHERE crew.category = 'director'
            AND people.born >= 1900
    )
GROUP BY decade
ORDER BY decade;

上面的group by decade1最重要，这样count()会以decade组区分进行统计

3.4 q5_german_type_ratings

Compute statistics about different type of works that has a German title.(计算具有德语标题的不同类型作品的统计数据。) Details: Compute the average (rounded to 2 decimal places), min, and max rating for each type of work that has a German title and the akas types is either imdbDisplay or original. Sort the output by the average rating of each title type.(计算具有德语标题且akas类型为imdbDisplay或original的每种类型的作品的平均值(舍入到小数点后2位)、最小值和最大值。按每个标题类型的平均评分对输出进行排序。)

Your output should have the format: TITLE_TYPE|AVG_RATING|MIN_RATING|MAX_RATING Your first row should look like this:movie|6.65|3.4|8.2

分析：titles表、akas和ratings表通过title_id进行联结，其中titles中作为主键，akas和ratings作为外键。要求akas.types in ('imdbDisplay','original') and akas.language='de',计算平均值、最大值、最小值。为三表查询

1
2
3
4
5
6
7
8

SELECT T.TYPE, ROUND(AVG(R.RATING),2),MIN(R.RATING),MAX(R.RATING)
FROM TITLES AS T
	INNER JOIN AKAS AS A ON T.TITLE_ID=A.TITLE_ID
	INNER JOIN RATINGS AS R ON T.TITLE_ID=R.TITLE_ID
WHERE A.TYPES IN ('imdbDisplay','original')
	AND A.LANGUAGE='de'
GROUP BY T.TYPE
ORDER BY T.TYPE;

3.5 q6_who_played_a_batman

List the 10 highest rated actors who played a character named "Batman".(请列出出演过“蝙蝠侠”角色的10位评价最高的演员) Details: Calculate the actor rating by taking the average rating of all their works. Return both the name of the actor and their rating and only list the top 10 results in order from highest to lowest rating. Round average rating to the nearest hundredth.(通过取所有作品的平均评分来计算演员的评分。返回演员的名字和他们的评分，并且只按评分从高到低的顺序列出前10个结果。四舍五入平均评级到最接近的百分之一。)

Make sure your output is formatted as follows: Kayd Currier|8.05

分析：name在people表，rating在ratings表，characters在crew表，其中三者的联结依赖主外键，ratings和crew通过title_id联结，crew和people通过person_id联结，要求crew.characters like '%Batman%'。可将people和crew先用person_id进行内连接得到actor,然后利用actor与ratings连接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

WITH actors AS (
    SELECT DISTINCT(crew.person_id) AS person_id,
        people.name AS person_name
    FROM crew
        INNER JOIN people ON people.person_id = crew.person_id
    WHERE crew.characters LIKE '%"Batman"%'
        AND crew.category = "actor"
)
SELECT a.person_name,
    ROUND(AVG(rating), 2) AS average
FROM actors AS a
    INNER JOIN crew AS c ON c.person_id = a.person_id
    INNER JOIN ratings AS r ON c.title_id = r.title_id
GROUP BY a.person_id
ORDER BY average DESC
LIMIT 10;

上述等价于：

1
2
3
4
5
6
7
8
9
10
11
12

SELECT A.name,ROUND(AVG(R.rating),2) AS SCORE
FROM (SELECT DISTINCT(C.person_id),P.name,C.title_id
	FROM crew AS C
	INNER JOIN people AS P ON C.person_id=P.person_id
	WHERE C.characters LIKE '%"Batman"%'
		AND C.category = 'actor'
	) AS A
	INNER JOIN crew AS C ON C.person_id=A.person_id
	INNER JOIN ratings AS R ON C.title_id=R.title_id
GROUP BY A.person_id
ORDER BY SCORE DESC
LIMIT 10;

3.6 q7_born_with_prestige

List the number of actors or actress who were born on the year that "The Prestige" was premiered.(列出在《致命魔术》首映那一年出生的演员人数。) Details: Print only the total number of actors born that year. For this question, determine distinct people by their person_id, not their names. Do not hard code the query.(只打印当年出生的演员总数。对于这个问题，确定不同的人通过他们的person_id，而不是他们的名字。不要硬编码查询。)

分析：born在people表，primary_title在title表，因此需要将crew与people联结起来。加上条件category IN ('actor', 'actress')和primary_title = 'The Prestige'

1
2
3
4
5
6
7
8
9

SELECT COUNT(DISTINCT(p.person_id))
FROM people AS p
    INNER JOIN crew AS c ON p.person_id = c.person_id
WHERE c.category IN ('actor', 'actress')
    AND p.born IN (
        SELECT premiered
        FROM titles
        WHERE primary_title = 'The Prestige'
    );

3.7 q8_directing_rose.sql

Find all the directors who have worked with an actress with first name "Rose".(找出所有与名字为“Rose”的女演员合作过的导演。) Details: Print only the names of the directors in alphabetical order. Each name should only appear once in the output.

分析：category在表crew,name在people

1
2
3
4
5
6
7
8
9
10
11
12
13

WITH title_ids AS (
    SELECT c.title_id AS title_id
    FROM crew AS c
        INNER JOIN people AS p ON p.person_id = c.person_id
    WHERE p.name like 'Rose%'
        AND c.category = 'actress'
)
SELECT DISTINCT(p.name) AS name
FROM title_ids AS t
    INNER JOIN crew AS c ON t.title_id = c.title_id
    INNER JOIN people AS p ON p.person_id = c.person_id
WHERE c.category = 'director'
ORDER BY name;

3.8

1 虚拟内存

一个系统中的进程是与其他进程共享CPU和主存资源的。在之前我们明白一个进程会有4GB的内存，但实际中不可能为一个进程真实的分配这么多，否则对于8G的主存，只要两个进程就占满了。因此，计算机系统的设计者们引入了一中很聪明的做法——虚拟内存。

虚拟内存是硬件异常、硬件地址翻译、主存和磁盘文件和内核软件的完美交互：

1.1 虚拟寻址和地址空间

在计算机中每个字节都存在它唯一的地址，该地址就是物理地址，我们将通过真实物理地址进行寻址的方法称为物理地址。

而虚拟地址，是指由CPU生成一个虚拟地址（VA）来访问主存，如下图，这个虚拟地址在送到内存之前会经过MMU内存管理单元来翻译成物理地址，在这里会结合到后面的页表来进行翻译。通过虚拟地址寻址的方式就是虚拟寻址。现在计算绝大部分都是使用寻你寻址。

地址空间：

• 虚拟地址空间：虚拟地址空间一般以地址总线条数为基准，如32位的位\(2^{32}=4GB\)
• 物理地址空间：对应与实际内存挡住的M字节，一般来说，物理地址空间由进程运行过程中所实际使用的内存大小所决定

物理地址空间和虚拟地址空间是对应关系的，即由虚拟地址找到真实的物理地址。

1.2 虚拟内存是作为缓存的工具

在概念上，虚拟内存是指存放在磁盘上的N字节大小的内存区域，每个字节都要相应的虚拟地址，作物寻址索引。和存储结构的缓存一样，磁盘的数据也被分割成块，在这类为做区别称之为虚拟页，每个虚拟页大小由计算机系统决定为\(P=2^p\)，与之对应的是物理页，其大小也应该为P。

在任何时刻，我们都不能实际真实一股脑的为进程分配全部的存储空间，因此虚拟页面分为三个不相交的子集：

• 未分配的：VM系统还没有分配的页，此时未分配的块没有任何数据和它们管理，因此此时不会占有任何磁盘空间
• 缓存的：当前缓存的虚拟页在占有磁盘中的空间，当然由于缓存到内存。内存当中也会占有一定内存空间
• 维缓存的：在磁盘中占用空间，但并未缓存在内存中，当然不占用内存(此时当CPU要寻址该页当中一个数据时，由于未缓存在内存中，就会造成缺页异常。)

1 异常控制流

现代系统通过使控制流发生突变来对这些情况做出反应，我们把这些突变称为异常控制流(ECF)。

• 在硬件层，硬件检测到的事件会触发控制突然转移到异常处理程序；
• 在操作系统层，内核通过上下文切换将控制从一个用户进程转移到另一个用户进程；
• 在应用层，一个进程可发发送信号到另一个进程，而接受者会将控制突然转移到它的一个信号处理程序。

作为程序员，理解ECF很重要：

1 操作系统的基本概念

1. 操作系统（Operating System，简称 OS）是管理计算机硬件与软件资源的程序，是计算机的基石。
2. 操作系统本质上是一个运行在计算机上的软件程序 ，用于管理计算机硬件和软件资源。 举例：运行在你电脑上的所有应用程序都通过操作系统来调用系统内存以及磁盘等等硬件。
3. 操作系统存在屏蔽了硬件层的复杂性。 操作系统就像是硬件使用的负责人，统筹着各种相关事项。
4. 操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。 内核是连接应用程序和硬件的桥梁，决定着系统的性能和稳定性。

操作系统的内核（Kernel）

维基百科对于内核的解释： >内核（英语：Kernel，又称核心）在计算机科学中是一个用来管理软件发出的数据 I/O（输入与输出）要求的电脑程序，将这些要求转译为数据处理的指令并交由中央处理器（CPU）及电脑中其他电子组件进行处理，是现代操作系统中最基本的部分。它是为众多应用程序提供对计算机硬件的安全访问的一部分软件，这种访问是有限的，并由内核决定一个程序在什么时候对某部分硬件操作多长时间。 直接对硬件操作是非常复杂的。所以内核通常提供一种硬件抽象的方法，来完成这些操作。有了这个，通过进程间通信机制及系统调用，应用进程可间接控制所需的硬件资源（特别是处理器及 IO 设备）。

早期计算机系统的设计中，还没有操作系统的内核这个概念。随着计算机系统的发展，操作系统内核的概念才渐渐明晰起来了!

简单概括两点：

• 操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。
• 操作系统的内核是连接应用程序和硬件的桥梁，决定着操作系统的性能和稳定性。

中央处理器（CPU，Central Processing Unit）

关于 CPU 简单概括三点：

• CPU 是一台计算机的运算核心（Core）+控制核心（ Control Unit），可以称得上是计算机的大脑。
• ** CPU 主要包括两个部分：控制器+运算器。**
• CPU 的根本任务就是执行指令，对计算机来说最终都是一串由“0”和“1”组成的序列。

CPU vs Kernel(内核)

可以简单从下面两点来区别：

• 操作系统的内核（Kernel）属于操作系统层面，而 CPU 属于硬件。
• CPU 主要提供运算，处理各种指令的能力。内核（Kernel）主要负责系统管理比如内存管理，它屏蔽了对硬件的操作。

2 操作系统的基本特性

操作系统的基本特性是并发性、共享性、虚拟性、异步性。

并发性

并行性和并发性(Concurrence)是既相似又有区别的两个概念，并行性是指两个或多个事件在同一时刻发生；而并发性是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间内宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。（宏观并发微观串行）

并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统

操作系统通过引入进程和线程，使得程序能够并发运行。

共享性

指系统中的资源可供内存中多个并发执行的进程(线程)共同使用，相应地，把这种资源共同使用称为资源共享，或称为资源复用。目前主要实现资源共享的方式有：

• 互斥共享方式
• 同时访问方式

互斥共享方式

当一个进程 A 要访问某资源时，必须先提出请求。如果此时该资源空闲，系统便可将之分配给请求进程 A 使用。此后若再有其它进程也要访问该资源时(只要 A 未用完)，则必须等待。仅当 A 进程访问完并释放该资源后，才允许另一进程对该资源进行访问。我们把这种资源共享方式称为互斥式共享，而把在一段时间内只允许一个进程访问的资源称为临界资源或独占资源，例如打印机。

同时访问方式

系统中还有另一类资源，允许在一段时间内由多个进程“同时”对它们进行访问。这里所谓的“同时”，在单处理机环境下往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问。典型的可供多个进程“同时”访问的资源是磁盘设备，一些用重入码编写的文件也可以被“同时”共享，即若干个用户同时访问该文件。

虚拟性

虚拟技术把一个物理实体转换为多个逻辑实体。

主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术。

多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。

虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。

异步性

在多道程序环境下允许多个进程并发执行，但只有进程在获得所需的资源后方能执行。在单处理机环境下，由于系统中只有一台处理机，因而每次只允许一个进程执行，其余进程只能等待。进程是以人们不可预知的速度向前推进，此即进程的异步性。

3 操作系统的基本功能

操作系统的基本功能包括进程管理、内存管理、文件管理、设备管理。

• 进程管理：进程控制、进程同步、进程通信、死锁处理、处理机调度等
• 内存管理：内存分配、地址映射、内存保护与共享、虚拟内存等
• 文件管理：文件存储空间的管理、目录管理、文件读写管理和保护等
• 设备管理：完成用户I/O请求，方便用户使用各种设备，并提高设备的利用率，主要包括缓冲管理、设备管理、设备处理、虚拟设备等。

4 什么是系统调用/用户态和系统态是？

根据进程访问资源的特点，可以把进程在系统上的运行分为两个级别：

• ** 用户态(user mode) **: 用户态运行的进程或程序可以直接读取用户程序的数据。
• 系统态(kernel mode):可以简单的理解系统态运行的进程或程序几乎可以访问计算机的任何资源，不受限制。

我们运行的程序基本都是运行在用户态，如果要调用操作系统提供的系统态级别的子功能，那就需要系统调用了！

也就是说在运行的用户程序中，凡是与系统态级别的资源有关的操作（如文件管理、进程控制、内存管理等)，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

这些系统调用按功能大致可分为如下几类：

• 设备管理。完成设备的请求或释放，以及设备启动等功能。
• 文件管理。完成文件的读、写、创建及删除等功能。
• 进程控制。完成进程的创建、撤销、阻塞及唤醒等功能。
• 进程通信。完成进程之间的消息传递或信号传递等功能。
• 内存管理。完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。

为什么要有用户态与内核态?

在 cpu 的所有指令中，有些指令是非常危险的，如果使用不当，将会造成系统崩溃等后果。为了避免这种情况发生，cpu 将指令划分为特权级(内核态)指令和非特权级(用户态)指令。

对于那些危险的指令只允许内核及其相关模块调用，对于那些不会造成危险的指令，就允许用户应用程序调用。

• 内核态(核心态,特权态): 内核态是操作系统内核运行的模式。 内核态控制计算机的硬件资源，如硬件设备，文件系统等等，并为上层应用程序提供执行环境。
• 用户态: 用户态是用户应用程序运行的状态。 应用程序必须依托于内核态运行,因此用户态的操作权限比内核态是要低的，如磁盘，文件等，访问操作都是受限的。
• 系统调用: 系统调用是操作系统为应用程序提供能够访问到内核态的资源的接口。

用户态切换到内核态的几种方式

• 系统调用: 系统调用是用户态主动要求切换到内核态的一种方式，用户应用程序通过操作系统调用内核为上层应用程序开放的接口来执行程序。
• 异常: 当 cpu 在执行用户态的应用程序时，发生了某些不可知的异常。于是当前用户态的应用进程切换到处理此异常的内核的程序中去。
• 硬件设备的中断: 当硬件设备完成用户请求后，会向 cpu 发出相应的中断信号，这时 cpu 会暂停执行下一条即将要执行的指令，转而去执行与中断信号对应的应用程序，如果先前执行的指令是用户态下程序的指令，那么这个转换过程也是用户态到内核台的转换。

5 计算机的局部性原理

一个编写良好的计算机程序常常具有良好的局部性，即他们更加倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用或的数据项本身，这种特性，常常称为局部性原理。局部性由两种不同的形式：时间局部性和空间局部性

• 时间局部性：被引用过一次的内存位置很有可能在不久的将来再次被多次引用。
• 空间局部性：一个内存被引用过了，那么极有可能在不久的将来会引用器附近的内存位置。在高速缓存中的表现形式是以数据块的形式进行缓存，弥补未命中时的惩罚

我们应该理解局部性原理，因为一般而言，一个良好局部性的程序比局部性差的程序运行得更快，这是由现代计算机系统得设计结构所决定得，在现代计算系统得各个层次之哦你给，都引入了局部性原理：

• 在硬件层，计算机设计者通过引入称为高速缓存存储器这样小而快得快速存储器来保存最近引用得指令和数据项，从而提高对主存得访问速度。
• 在操作系统中，系统使用主存作为虚拟地址空间，来存储最近被引用得数据项，来避免因从磁盘取数据过慢而导致CPU资源的浪费
• 类似的，用主存来缓存磁盘文件中最近被使用的磁盘块。
• 局部性原理在应用程序中也有应用，入Web浏览器将最近引用的文档放在本地磁盘上，利用的就是时间局部性。

1 链接器

1.1 链接是什么

链接是将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可被加载到内存并执行。

• 链接可以执行与编译时，也就是源代码被翻译成机器代码时；
• 也可以执行与加载时，也就是在程序被加载器（loader)加载带内存并执行时
• 甚至也可执行于运行时，也就是有程序来执行

链接器在开发中是一个关键角色，因为它使得分离编译成为可能，我们不用将一个大型的应用程序组织为一个巨大的源文件，而是可以分解成更小、更好管理的模块。可以单独修改和编译这些模块。理解链接有以下的好处：

• 理解链接器将帮助你构造大型程序。构造大型程序的程序员经常会遇到缺少模块、库或者不兼容版本引起的链接器错误，当你理解了链接器如何解析引用、什么是库以及链接器是如何使用库来解析引用时，你就能够较好的解决这类问题

• 理解链接器将帮助你避免一些危险的编程错误。Linux链接器解析引用时所做的决定可以不动声色影响你程序的正确性。在默认情况下，错误的定义多个全局变量的程序将通过链接器，而不产生任何警告信息。

• 理解链接器将帮助你理解语言的作用域规则是如何实现的。全局变量和局部变量、static变量和static函数，在低层到底有何区别？

• 理解链接器帮助你理解其他重要系统概念。链接器产生的可执行目标文件咋子系统功能中扮演关键角色，如加载运行程序、虚拟内存、分页、内存映射。

• 理解链接器将使你能够利用共享库。共享库和动态链接在现代操作系统日益重要，掌握如何动态链接原理极其重要。

1 存储技术

作为一名程序员，你必须了解存储器的层次结构，因为它对应用程序的性能有着巨大的影响。

• 如果你的数据是在cpu寄存器上，那么指令执行期间在0个周期就能访问到
• 如果是在高速缓存中，需要4-75个周期
• 如果在主存，需要上百个周期
• 如果是在磁盘，那么就需要大约几千万个周期，时间大概是毫秒级，比主存慢10万倍，比高速缓存慢100万倍

1.1 随机访问存储器

随机访问存储器(RAM)有两类：静态和动态。静态RAM(SRAM)比动态DRAM(DRAM)更快，但也更贵，因此SRAM一般集成在CPU上作为高速缓存，DRAM则作为主存。断电以后，DRAM和SRAM都会丢失它们的信息

访问主存：每次CPU和主存之间的数据传送都是通过一系列的步骤来完成，这些步骤称为总线事务。读事务从主存传输数据到CPU，写事务从CPU传送数据到主存。总线是一组并行的导线，能携带地址、数据和控制信号。

1 导读

程序优化涉及的范围实在是太广了，几乎每个层面都可以进行优化，比如撰写<编译器友好型>以及<缓存友好型>的程序，针对不同的目标硬件平台还可能进行特定的优化，等等，优化的难点在于你需要对系统有充分理解，当然了在你做优化之前首先要保证原始程序功能正确（并且有回归测试），否则一切都是徒劳。

首先需要理解，哪些因素会影响程序的性能

内存对齐规则

在C/C++中的结构体或类，存在内存对齐问题。内存对齐是为了方便计算机进行寻址，优化寻址速度的一个措施，其代价是消耗不必要的内存空间。

内存对齐遵循以下规则：

• 第一个成员在与结构体变量偏移量为0的地址处。
• 其他成员变量都放在对齐数（成员的大小和默认对齐数的较小值）的整数倍的偏移地址处。
  • 对齐数=编译器默认的一个对齐数与该成员大小的较小值。（不同的编译器其默认对齐数不同，64位系统中VS默认的对齐数是8，在Linux中没有默认的对齐数）
  • 可以在程序开端声明#pragma pack(数字)来设置默认对齐值
• 结构体总大小为最大对齐数(每个成员变量都有一个对齐数 )的整数倍。
• 如果嵌套了结构体的情况,嵌套的结构体对齐到自己的最大对齐数的整数倍处,结构体的整体大小就是所有最大对齐数(含嵌套结构体的对齐数)的整数倍。--->最大对齐数肯定不超过默认对齐数

示例：VS运行（默认对齐数为8）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

typedef struct test2
 {
     int a;//4-->8，占0，1，2，3地址处，后续补4，5，6，7
     double c;//8，但由于其只能放在与首地址偏移量为8的地址上，因此4，5，6，7作为填补空缺，它从8存储
 };

 typedef struct testMemory
 {
     int a;//4-->8
     long b;//8
     char c;//1
     struct test2 l;//16
 };

cout  <<sizeof(test2) << " " << sizeof(testMemory) << endl;

1

16 40

class类

在C++中，class与struct是相同的，除了：

• 两者中如果不对成员不指定公私有，struct默认是公有的，class则默认是私有的

• class默认是private继承， 而struct默认是public继承

因此，对于struct的对齐规则同样是class的对齐规则，在c++中，还必须注意在存在虚函数时类有一个虚表指针的情况：(在64位中指针大小为8字节，32为4字节)

1
2
3
4
5
6
7
8
9

 class my {
 private:
     int a;
     double b;
     char c;
     virtual int m() { return 0; }
	 virtual int s(){return 0;}
 };
//sizeof(my)为32:8+8+8+8

程序的机器级表示

在本章，会学习观察汇编代码和机器代码。说到汇编语言就不得不提编译器和汇编器。**编译器是基于编程语言规则、目标机器的指令集和操作系统遵循的惯例，经过一系列阶段如图：

gcc编译器以汇编代码的形式产生输出，然后gcc调用汇编器和链接器生成二进制机器文件和可执行文件。对于Linux机，可以使用 gcc -Og -S xxx.c来进行学习。因为参数-Og表明不进行优化，这可以让汇编代码尽可能地保持和C源码一样的顺序，位置，排列等。