• 15.6.1.1 Creating InnoDB Tables

To create an InnoDB table, use the CREATE TABLE statement.

1

CREATE TABLE t1 (a INT, b CHAR (20), PRIMARY KEY (a)) ENGINE=InnoDB;

You do not need to specify the ENGINE=InnoDB clause if InnoDB is defined as the default storage engine, which it is by default. To check the default storage engine, issue the following statement:

1
2
3
4
5
6

mysql> SELECT @@default_storage_engine;
+--------------------------+
| @@default_storage_engine |
+--------------------------+
| InnoDB                   |
+--------------------------+

You might still use ENGINE=InnoDB clause if you plan to use mysqldump or replication to replay the CREATE TABLE statement on a server where the default storage engine is not InnoDB.

如果你计划使用 mysqldump/复制 将 CREATE TABLE 语句复现在另外一个默认存储引擎不是 InnoDB 的服务器上, 就坚持使用 ENGINE=InnoDB 子句 (不过我看 mysqldump 出的语句中会显式指定存储引擎类型)

An InnoDB table and its indexes can be created in the system tablespace, in a file-per-table tablespace, or in a general tablespace. When innodb_file_per_table is enabled, which is the default, an InnoDB table is implicitly created in an individual file-per-table tablespace. Conversely, when innodb_file_per_table is disabled, an InnoDB table is implicitly created in the InnoDB system tablespace. To create a table in a general tablespace, use CREATE TABLE ... TABLESPACE syntax. For more information, see Section 15.6.3.3, “General Tablespaces”.

InnoDB 表及它的索引可以创建在 system tablespace, file-per-table tablespace 或 general tablespace. 当 innodb_file_per_table 启用, InnoDB 表默认创建在单独的 file-per-rable 表空间中, 相反, 则创建在 system tablespace 中.

使用 CREATE TABLE … TABLESPACE 语法可以创建在 general tablespace 中

When you create a table in a file-per-table tablespace, MySQL creates an .ibd tablespace file in a database directory under the MySQL data directory, by default. A table created in the InnoDB system tablespace is created in an existing ibdata file, which resides in the MySQL data directory. A table created in a general tablespace is created in an existing general tablespace .ibd file. General tablespace files can be created inside or outside of the MySQL data directory. For more information, see Section 15.6.3.3, “General Tablespaces”.

当你创建一个在 file-per-table 表空间中的表时, MySQL 在主目录下的单个数据库目录中创建 .idb 文件

在 InnoDB system 表空间中则创建在一个在 MySQL 主目录下已存在的 ibdata 文件中(PS. 那么 ibdata 文件是什么时候创建的? 如何增长?)

Internally, InnoDB adds an entry for each table to the data dictionary. The entry includes the database name. For example, if table t1 is created in the test database, the data dictionary entry for the database name is 'test/t1'. This means you can create a table of the same name (t1) in a different database, and the table names do not collide inside InnoDB.

InnoDB Tables and Row Formats

The default row format for InnoDB tables is defined by the innodb_default_row_format configuration option, which has a default value of DYNAMIC. Dynamic andCompressed row format allow you to take advantage of InnoDB features such as table compression and efficient off-page storage of long column values. To use these row formats, innodb_file_per_table must be enabled (the default).

InnoDB 表的行格式化由 innodb_default_row_format 定义, 默认是 DYNAMIC

Dynamic 和 Compressed 行格式化提供了 InnoDB 高级特性, 比如 压缩表, 高效的长列值页外存储

使用这些行格式化, 必须启用 innodb_file_per_table

1
2
3

SET GLOBAL innodb_file_per_table=1;
CREATE TABLE t3 (a INT, b CHAR (20), PRIMARY KEY (a)) ROW_FORMAT=DYNAMIC;
CREATE TABLE t4 (a INT, b CHAR (20), PRIMARY KEY (a)) ROW_FORMAT=COMPRESSED;

Alternatively, you can use CREATE TABLE ... TABLESPACE syntax to create an InnoDB table in a general tablespace. General tablespaces support all row formats. For more information, see Section 15.6.3.3, “General Tablespaces”.

另外, 你可以使用 CREATE TABLE … TABLESAPCE 语法在 general tablespace 创建 InnoDB 表. general tablespace 支持所有的行格式化

1

CREATE TABLE t1 (c1 INT PRIMARY KEY) TABLESPACE ts1 ROW_FORMAT=DYNAMIC;

CREATE TABLE ... TABLESPACE syntax can also be used to create InnoDB tables with a Dynamic row format in the system tablespace, alongside tables with a Compact orRedundant row format.

CREATE TABLE … TABLESPACE 语法也可以被用作在 system tablespace 中创建 Dynamic 格式化的表, 以及 Compacr 或 Redundant 格式化

1

CREATE TABLE t1 (c1 INT PRIMARY KEY) TABLESPACE = innodb_system ROW_FORMAT=DYNAMIC;

For more information about InnoDB row formats, see Section 15.10, “InnoDB Row Formats”. For how to determine the row format of an InnoDB table and the physical characteristics of InnoDB row formats, see Section 15.10, “InnoDB Row Formats”.

InnoDB Tables and Primary Keys

Always define a primary key for an InnoDB table, specifying the column or columns that:

• Are referenced by the most important queries.

• Are never left blank.

• Never have duplicate values.

• Rarely if ever change value once inserted.

  通常会为 InnoDB 表定义一个主键, 说明列具有: 被最重要的查询引用, 永远不为空, 永远不重复, 一旦插入, 则很少改动

  For example, in a table containing information about people, you would not create a primary key on (firstname, lastname) because more than one person can have the same name, some people have blank last names, and sometimes people change their names. With so many constraints, often there is not an obvious set of columns to use as a primary key, so you create a new column with a numeric ID to serve as all or part of the primary key. You can declare an auto-increment column so that ascending values are filled in automatically as rows are inserted:

  比如, 在一个包含民众信息的表中, 不能创建以 (firstname, lastname) 组合的值为主键, 因为名字很可能重复, 一些人没有 lastname, 一些人会改变他们的名字.

  涉及到这么多的限制, 进程没有一个明显列的集合能作为主键. 所以可以创建一个新的数字列用作整个或部分主键, 声明为 auto-increament 可以使行在插入时自增

  1 2 3 4 5

  # The value of ID can act like a pointer between related items in different tables. CREATE TABLE t5 (id INT AUTO_INCREMENT, b CHAR (20), PRIMARY KEY (id)); # The primary key can consist of more than one column. Any autoinc column must come first. CREATE TABLE t6 (id INT AUTO_INCREMENT, a INT, b CHAR (20), PRIMARY KEY (id,a));

  Although the table works correctly without defining a primary key, the primary key is involved with many aspects of performance and is a crucial design aspect for any large or frequently used table. It is recommended that you always specify a primary key in the CREATE TABLE statement. If you create the table, load data, and then run ALTER TABLE to add a primary key later, that operation is much slower than defining the primary key when creating the table.

  尽管没有定义主键 表也可以正常运行, 但是主键包含了许多性能方面和重要的为大容量或频繁使用表做的设计, 建议你总是在表中指定一个主键.

  在创建和加载表之后使用 ALTER TABLE 语句增加主键, 速度会远慢于一开始创建时指定主键

Viewing InnoDB Table Properties

To view the properties of an InnoDB table, issue a SHOW TABLE STATUS statement:

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

mysql> SHOW TABLE STATUS FROM test LIKE 't%' \G;
*************************** 1. row ***************************
           Name: t1
         Engine: InnoDB
        Version: 10
     Row_format: Compact
           Rows: 0
 Avg_row_length: 0
    Data_length: 16384
Max_data_length: 0
   Index_length: 0
      Data_free: 0
 Auto_increment: NULL
    Create_time: 2015-03-16 15:13:31
    Update_time: NULL
     Check_time: NULL
      Collation: utf8mb4_0900_ai_ci
       Checksum: NULL
 Create_options:
        Comment:

For information about SHOW TABLE STATUS output, see Section 13.7.6.36, “SHOW TABLE STATUS Syntax”.

InnoDB table properties may also be queried using the InnoDB Information Schema system tables:

1
2
3
4
5
6
7
8
9
10

mysql> SELECT * FROM INFORMATION_SCHEMA.INNODB_TABLES WHERE NAME='test/t1' \G
*************************** 1. row ***************************
     TABLE_ID: 45
         NAME: test/t1
         FLAG: 1
       N_COLS: 5
        SPACE: 35
   ROW_FORMAT: Compact
ZIP_PAGE_SIZE: 0
   SPACE_TYPE: Single

For more information, see Section 15.14.3, “InnoDB INFORMATION_SCHEMA Schema Object Tables”.

原文 : https://www.eversql.com/choosing-the-best-indexes-for-mysql-query-optimization/

Which indexes should I create for an SQL query?

我应该为SQL查询创建哪些索引?

As a general rule of thumb, MySQL can only use one index for each table in the query. Therefore, there is no point in creating more than one index for each query. Preferably, same indexes should match as many of the queries as possible, as it will reduce the load on the database when inserting or updating data (which requires updating the indexes as well).

按照一般的经验法则, MySQL查询中的每个表只能使用一个索引

(High Performance MySQL 中澄清了, 有可能会组合, 但最好不要依赖于它)

所以, 为每个查询创建多个索引是没有意义的, 更恰当的情况是, 同样的索引匹配尽可能多的查询

因为这将会在插入或更改数据时, 减少数据库的负载(该操作同样也需要更新索引)

When creating an index, the most important parts are the equality conditions in the WHERE and JOIN conditions. In most cases, conditions such as name = ‘John’ will allow the database to filter most of the rows from the table and go through a small amount of rows to return the required results. Therefore, we should start indexing by adding these columns to the index.

当创建索引时, 最重要的是在 WHERE 和 JOIN 中的等式条件

在大多数情况下, 像 name = ‘John’ 这样的条件会使数据区从表中筛选行, 通过少量的行返回需要的数据

我们应该通过增加这些列到索引中来开始索引

Then, you should look into the range conditions, but you should only add one of them – the most selective one, as MySQL can’t handle more of them. In some cases when there are no range conditions, it makes sense to add the GROUP BY / ORDER BY columns, assuming the ordering is done in only one direction (ASC / DESC).

然后, 你应该关注范围条件, 但是你只能增加其中一个, 可选性最大的一个, 因为MySQL不能处理更多

(PS. 关于 selectivity, High Performance MySQL 5.3 节中 Choosing a Good Column Order 中有介绍)

(简单来理解的话, 就是最具可选性, 最能分辨的列)

在某些情况下没有范围条件, 增加 GROUP BY/ORDER BY 列, 假设顺序由其中一个方向确定(ASC/DESC)

In some cases, it also makes sense to create a separate index that contains the ORDER BY clause’s columns, as MySQL sometimes chooses to use it. Please note though that for this to happen, the index should contain all columns from the ORDER BY clause and they should all be specified with the same order (ASC / DESC). This doesn’t guarantee that the database’s optimizer will pick this index rather than the other compound indexes, but it’s worth a try.

有时候, 也可以创建一个单独的索引包含 ORDER BY 子句的列, 因为 MySQL 有时会选择使用它

请记住, 为了实现这一点, 索引应该包含 ORDER BY 子句中所有的列, 并且被指定为相同的顺序(ASC/DESC)

这不保证数据库的优化是否会选择这个, 而不是其他组合索引, 但是值得一试

Also, in some cases, it makes sense to also add the columns from the SELECT clause to the index, to have a complete covering index. This only relevant if the index isn’t already ‘too large’. What’s too large? Well, no official rule of thumb here, but let’s say… 5-7 columns? Creating a covering index allows the database to not only filter using the index, but to also fetch the information required by the SELECT clause directly from the index, which saves precious I/O operations.

同样的, 有时增加 SELECT 中的列, 以拥有一个完整的覆盖索引也是有必要的, 但只当索引不长时, 才有意义

那么, 多长才是长么? emm… 没有官方规定这个, 但是估计一下… 5-7列?

创建覆盖索引使数据库不仅能过滤, 同时也能直接从索引中获取 SELECT 子句需要的信息, 以节省宝贵的 I/O 操作

Let’s look at an example to clarify: (通过一个例子理解一下)

1
2
3
4
5
6
7
8
9

SELECT
    id, first_name, last_name, age
FROM
    employees
WHERE
    first_name = 'John'
        AND last_name = 'Brack'
        AND age > 25
ORDER BY age ASC;

For this query, we’ll start with adding the columns first_name and last_name, which are compared with an equality operator. Then, we’ll add the age column which is compared with a range condition. No need to have the ORDER BY clause indexed here, as the age column is already in the index. Last but not least, we’ll add id from the SELECT clause to the index to have a covering index.

就这个例子, 我们应该一开始增加在 WHERE 子句中有相等比较操作的列 first_name 和 last_name

然后, 增加具有比较的 age 列. 在这里不需要有 ORDER BY 子句, 因为 age 列已经在索引中了

最后, 但并不是最不重要的. 增加在 SELECT 子句中的 id 列, 以获得一个覆盖索引

So to index this query properly, you should add the index: (为了适当地索引这个查询, 你应该增加这个索引)

1
2

employees (first_name, last_name, age, id).
mysql : CREATE INDEX [INDEX_NAME] ON [TABLE_NAME] (first_name, last_name, age, id)

The above is a very simplified pseudo-algorithm that will allow you to build simple indexes for rather simple SQL queries.

上面是一个非常简单的(= = 这东西咋翻译来着… 虚拟方法? 总之就是一种方法)

让你为简单的 SQL 查询构建简单的索引

(实际情况可能会复杂一些, 参考 High Performance MySQL 第 5 章)

If you’re looking for a way to automate your index creation, while also adding the benefit of a proprietary indexing algorithm and query optimization recommendations, you can try out EverSQL Query Optimizer which does all the heavy lifting for you.

(广告 = =)

What not to do when indexing (or writing SQL queries)?

使用索引时, 不要做的事情

We gathered some of the most common mistakes we see programmers and database administrators do when writing queries and indexing their tables.

我们收集了一些当程序/DBA写查询语句和索引他们的表时, 会犯的常见错误

Indexing each and every column in the table separately

索引每一个表中每一列

In most cases, MySQL won’t be able to use more than one index for each table in the query.

Therefore, when creating a separate index for each column in the table, the database is bound to perform only one of the search operations using an index, and the rest of them will be significantly slower, as the database can’t use an index to execute them.

We recommend using compound indexes (explained later in this article) rather than single-column indexes.

通常, MySQL不能在查询语句中, 为同一张表使用超过一个索引

所以, 当为表中的每个列创建一个索引, MySQL被限制只使用其中一个索引, 而其他的会慢很多

所以数据库不能使用索引去执行它们

我们建议使用复合索引(将会在这篇文章之后介绍), 而不是使用单列索引

The OR operator in filtering conditions

过滤中的 OR 操作

Consider this query: (考虑这个查询)

1
2
3
4
5
6

SELECT
    a, b
FROM
    tbl
WHERE
    a = 3 OR b = 8;

In many cases, MySQL won’t be able to use an index to apply an OR condition, and as a result, this query is not index-able.

Therefore, we recommend to avoid such OR conditions and consider splitting the query to two parts, combined with a UNION DISTINCT (or even better, UNION ALL, in case you know there won’t be any duplicate results)

通常, MySQL不能使用一个索引执行 OR 操作, 所以, 这个索引是 不可索引 的

所以, 我们建议避免这样的 OR 操作, 将其切分为两个部分, 由 UNION DISTINCT 组合

(或者更好地, UNION ALL, 你知道在这个例子中不会有重复的元素)

(PS. 是的, 在这样的情况下, MySQL不会使用索引 )

The order of columns in an index is important

索引中列的顺序很重要

Let’s say I hand you my contacts phone book which is ordered by the contact’s first name and ask you to count how many people are there named “John” in the book. You’ll grab the book in both hands and say “no problem”. You will navigate to the page that holds all names starting with John, and start counting from there.

假设我把我的由联系人的姓作为顺序排序的通讯录给你, 问你在这个通讯录中, 有多少姓 “John” 的人

你会拿着这本书说”没问题”, 你会找到以 “John” 开始的书页, 然后开始计数

Now, let’s say I change the assignment and hand you a phone book that is ordered by the contact’s last name, but ask you to still count all contacts with the first name “John”. How would you approach that? Well, the database scratches his head in this situation as well.

如果我将书的顺序打乱, 以名排序, 问你同样的问题, 你如何回答这个问题?

数据库也会面临同样的麻烦

Now lets look at an SQL query to demonstrate the same behavior with the MySQL optimizer:

现在, 关注一个 SQL 语句来和 MySQL 优化器演示这个行为

Having the index contacts (first_name, last_name) is ideal here, because the index starts with our filtering condition and ends with another column in the SELECT clause.

如果有一个索引组合 (first_name, last_name) 在这里是很好的, 因为索引由 first_name 开始, 由 last_name 结束

(PS. 其实这个 High Performance MySQL 第 5 节有详细讨论)

(这里的优化的前提是, 该索引是 B-tree 类型, 如果是其他的, 比如 hash 类型, 那么可能就没有什么优化效果)

But, having the reverse index contacts (last_name, first_name) is rather useless, as the database can’t use the index for filtering, as the column we need is second in the index and not first.

如果有一个相反顺序的索引, 那么就是无用的

(因为如果是 B-tree 的话, 根本无法索引 = =)

The conclusion from this example is that the order of columns in an index is rather important.

最后点了一下题

Adding redundant indexes

增加冗余索引

Indexes are magnificent when trying to optimize your SQL queries and they can improve performance significantly.

索引在优化你的 SQL 语句和显著提升性能上很有帮助

But, they come with a downside as well. Each index you’re creating should be kept updated and in sync when changes occur in your databases. So for each INSERT / UPDATE / DELETE in your databases, all relevant indexes should be updated. This update can take sometime, especially with large tables / indexes.

但是, 它们也有一些缺点, 每个你创建的索引在你数据库变化时必须保持更新和同步

所以 每个 INSERT/UPDATE/DELETE 操作都会引起相关索引的更新, 这些操作所引起的索引可能会很耗时

Therefore, do not create indexes unless you know you’ll need them.

Also, we highly recommend to analyze your database once in a while, searching for any redundant indexes that can be removed.

所以, 除非你知道你需要它们, 否则不要创建无用的索引

同样地, 我们极力推荐每个一段时间, 分析一下数据库, 删除冗余的索引

How to automate index creation and SQL query optimization?

If you’re looking for a way to automate your index creation, while also adding the benefit of a proprietary indexing algorithm and query optimization recommendations, you can try out EverSQL Query Optimizer which does all the heavy lifting for you.

(广告, 有兴趣可以去原页面试试)

How to track redundant indexes in MySQL?

(这是在另一个页面的片段)

如何跟踪 MySQL 中冗余的索引

Starting MySQL 5.6, the database keeps track of index usage as part of its PERFORMANCE SCHEMA. This data can be queried using the schema_unused_indexes view, which displays indexes for which there are no events. Having no events indicates that these indexes might be redundant and unused for a while.

自 MySQL 5.6 开始, 数据库持续跟踪它 PERFORMANCE SCHEMA 中未使用的索引

这些数据可以用 schema_unused_indexes 来查询

显示哪些索引没有工作过, 这表示这些索引是冗余的, 在一段时间内没有使用过

But life isn’t that good, not yet at least. The potential obstacle here is that this information is re-counted every time MySQL is restarted. Therefore, in order to get reliable information, you should query these views a while after the MySQL instance was started. How long after the startup you’re asking? Well, that depends. My question back to you will be – how busy your database is? Do you know if all types of queries are usually executed in the database in a specific period of time? If so, that’s your window.

但是生活没有那么美好, 至少现在没有. 潜在的障碍是这些信息会在每次 MySQL 重启时重新统计

所以, 为了避免这种情况, 你应该在 MySQL 启动一段时间后去查询这些数据

这时间的长短取决与你数据库的忙碌程度

So let’s take a look at how it’s done: (让我们来看一看如何完成)

1
2
3
4
5

select * from sys.schema_unused_indexes;

object_schema	object_name	index_name
mydb			age			agecountry_index
mydb			country		agecountry_index

(PS. 显然, 如果数据可靠, 那么 age 表中的 agecountry_index 和 country 表中的 agecountry_index 是可以删除的)

原文地址 : https://en.wikipedia.org/wiki/B-tree

B-tree

In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children.[1] Unlike other self-balancing binary search trees, the B-tree is well suited for storage systems that read and write relatively large blocks of data, such as discs. It is commonly used in databases and file systems.

What, if anything, the B stands for has never been established.

在计算机科学中, B-tree 是自平衡树数据结构, 管理排序后的数据, 能常量时间内搜索. 序列访问, 插入和删除操作

B-tree 是二分查找树的广泛实现, 即一个节点可以有超过两个子节点

不像其他自平衡二分查找树, B-tree 适用于存储系统, 用作读取和写入相当庞大的数据

比如 discs, 通常被数据库和操作系统使用

Overview (概览)

In B-trees, internal (non-leaf) nodes can have a variable number of child nodes within some pre-defined range. When data is inserted or removed from a node, its number of child nodes changes. In order to maintain the pre-defined range, internal nodes may be joined or split. Because a range of child nodes is permitted, B-trees do not need re-balancing as frequently as other self-balancing search trees, but may waste some space, since nodes are not entirely full. The lower and upper bounds on the number of child nodes are typically fixed for a particular implementation. For example, in a 2-3 B-tree (often simply referred to as a 2-3 tree), each internal node may have only 2 or 3 child nodes.

Each internal node of a B-tree contains a number of keys. The keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: a1 and a2. All values in the leftmost subtree will be less than a1, all values in the middle subtree will be between a1 and a2, and all values in the rightmost subtree will be greater than a2.

在 B-tree 中, 内部(非叶子)节点可以在预定义范围内拥有可变数量的子节点

当从节点中插入或删除数据时, 子节点的数量改变. 为了管理预定义的范围, 内部节点可以连接或分裂

因为子节点的范围是受限的, B-tree 不需要像其他自平衡二分查找数一样频繁地重平衡, 但是会浪费一些空间, 因为节点不是填充满的

子节点数量的上限和下限通常有具体的实现固定, 比如 2-3 B-tree(通常简称 2-3 tree) 每个内部节点只有 2 个 或 3个子节点

每个 B-tree 的内部节点含有一些 keys, keys 充当分离的值 分离子树

比如, 如果内部节点有 3 个子节点(或子树) 那么, 它必须有 2 个 keys : a1 和 a2

所有在最左边子树的值 <a1, 所有在中间子树的值 >a1 <a2, 在最右子树中的所有值 >a2

(PS. 这里没有考虑 = 的情况, 不过还行, 等于放在值的左边还是右边, 不会有太大影响)

Usually, the number of keys is chosen to vary between {\displaystyle d} and {\displaystyle 2d}, where {\displaystyle d} is the minimum number of keys, and {\displaystyle d+1} is the minimum degree or branching factor of the tree. In practice, the keys take up the most space in a node. The factor of 2 will guarantee that nodes can be split or combined. If an internal node has {\displaystyle 2d} keys, then adding a key to that node can be accomplished by splitting the hypothetical {\displaystyle 2d+1} key node into two {\displaystyle d} key nodes and moving the key that would have been in the middle to the parent node. Each split node has the required minimum number of keys. Similarly, if an internal node and its neighbor each have {\displaystyle d} keys, then a key may be deleted from the internal node by combining it with its neighbor. Deleting the key would make the internal node have {\displaystyle d-1} keys; joining the neighbor would add {\displaystyle d} keys plus one more key brought down from the neighbor’s parent. The result is an entirely full node of {\displaystyle 2d} keys.

一个关于 static 的问题

2019年4月22日19:42:18

日常的一天, 做做 leetcode, 但是突然发现了关于 leetcode 代码优化的问题

题目大概是要你中序遍历树

(看到题目的时候愣了一下, 怀疑自己是不是眼花了, 直到看到了 Follow up… emmm, 好吧, 迭代)

总之我先用递归试了一下

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        static vector<int> ret;

        if (!root) return ret;

        if (root->left)
            inorderTraversal(root->left);

        ret.push_back(root->val);

        if (root->right)
            inorderTraversal(root->right);

        return ret;
    }
};

但是它总是给我报这个错

这是没有理由的! 我代码中不可能无中生有

我怀疑这是 leetcode 平台对于用户所做的一种优化

而这种优化与我使用 static 关键字相冲突

时间复杂度

时间复杂度用于描述算法的效率, 是衡量算法优劣的重要指标

O(1)

void func(int n){
    std::cout << n << std::cout;
}

将自变量视作n, n在此情景下为传入的参数
将因变量视作t, t在此情景下为函数执行的指令次数(这个就是时间复杂度)
上述算法中, 无论n是多少, t都为1, 则此算法复杂度记做: O(1)

O(1)复杂度的算法效率不因外界因素而改变

PS: 也称作常量级复杂度, 是最理想的复杂度

O(2n)

略

PS: 其中O(2n)就是呈2倍复杂度增加, 而O(nn)则意为n倍增加

O(n)

void func(int n){
    for(int i = 0; i < n; ++i){
        std::cout << i << std::endl;
    }
}

上述算法中 t = n + 1(其中的1为最后一次的失败), 算法复杂度为O(n)

O(n)复杂度的算法效率会因外界因素而改变, 其规律为: 复杂度呈1:1形式增加

PS: O(n)是比较常见的复杂度, 效率一般

O(n^2)/O(n^n)

void func(int n){
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++i){
            std::cout << i << std::endl;
        }
    }
}

上述算法中 t = n * n + 1, 记做: O(n^2)

O(n^2)复杂度的算法效率会随外界的影响平方倍变化
同理, 则O(n^n)复杂度的算法效率会随外界的影响呈n次方倍增加

PS: 出现这种复杂度的代码, 则需要考虑优化

O(log n)

要想明白O(log n)时间复杂度, 则先得复习对数
(如果你还没把数学还给数学老师的话, 就不必了)

这东西我也不大说得清楚, 就直接粘贴网上的案例了:

PS: O(log n)的复杂度计算好像不太容易, 一般人还不一定计算得出来…

RET: 总的来说时间复杂度就是一个随着计算数据增加, 算法效率呈何种形式增加的一种规律
了解一下时间复杂度是很有必要的
以后别人问你 你的算法效率如何的时候. 就可以回答: 我的算法时间复杂度是O(1)!

以上经验参照自简书

需求描述

设计一个定时关机的工具

该工具使用lua语言, 通过PLINK链接服务器

接收用户输入, 使用crontab/at设置定时器

详细代码

timer table

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

package.path = package.path .. ";../../script/?.lua"
-- inc是工具类
local inc = require("inc")
-- config记录了服务器的配置信息
local config = require("config")

-- timer用于处理整个定时任务
local timer = {}
timer.file = "crontabtask.sh"			-- 文件名, 因为使用 crontab [file]形式添加任务
timer.path = "/tmp/"					-- 文件位于服务器那个路径下
timer.fullName = timer.path..timer.file	-- 路径+文件名, 当前为: /tmp/crontabtask.sh
timer.filenamemask = "CRONTAB_TASK_"	-- 掩码, 用于区分任务
timer.servername = nil					-- 服务器名称, 这里仅仅占位, 会在之后设置

timer是任务处理表(类), 因为bash下, 没有办法直接使用vim编辑(或者说我不知道有什么办法能这么做)

所以 crontab -e 的方式被舍弃了, 使用 crontab [filename] 的形式来添加任务

(这样的好处是统一使用某一文件作为任务文件, 后续可以使用某种手段(比如修改配置), 来重新定义crontab -e)

(坏处就是动到了系统的东西, 这并不一定是好事)

lobby

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

-- 大厅
function timer.lobby()
    inc.p("请输入要操作的服务器ID", 10)
    local serverID = tonumber(io.stdin:read())
    local scfg, servercfg = inc.getserverinfo(serverID)

    inc.confirm_oper_server(scfg, {servercfg}, "即将操作该服务器")
    -- 检查文件是否存在
    timer.checkFileExists(scfg, servercfg)
    local sFolder = string.format("%s%d.p%d", 
        config.gamename, servercfg.id, servercfg.port)
    timer.servername = sFolder
    -- 根据用户的选项, 我们重新设置了文件掩码, 加上了当前服务器名
    -- 这样更加安全, 也可以筛选统一主机下, 不同服务器任务了
    timer.filenamemask = timer.filenamemask..timer.servername
    while (true)
    do
        inc.p("\n选择操作类型[1: 增加, 2: 删除, 4:查询]", 10)
        local operatetype = io.stdin:read()
        if operatetype == '1' then
            -- 增加定时器
            timer.addTimerTask(scfg, servercfg)
            -- 判断是否增加成功
            timer.isAddSuccess(scfg, servercfg)
            -- 自动刷新定时器列表
            timer.searchTimerTask(scfg, servercfg)
        elseif operatetype == '2' then
            -- 删除定时器
            timer.deleteTimerTask(scfg, servercfg)
            -- 自动刷新定时器列表
            timer.searchTimerTask(scfg, servercfg)
        elseif operatetype == '3' then
            -- 预留
        elseif operatetype == '4' then
            -- 刷新定时器列表
            timer.searchTimerTask(scfg, servercfg)
        else 
            inc.p("操作码异常", 14)
        end
    end
end

大厅界面, 先让用户选择一个操作的服务器, 设置相应的参数, 然后让用户一直操作该服务器

checkFileExists

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

-- 检查文件是否存在
function timer.checkFileExists(scfg, servercfg)
    -- 看一下目录下是否存配置文件
    local cmds = {}
    table.insert(cmds, "cd "..timer.path)
    table.insert(cmds, "ls crontab*");
    local filename;
    inc.popen_server_cmds(scfg, cmds, function (res)
        -- 因为某些原因, 不用在意这行代码. 它的作用是获取文件名
        filename = res[2]
    end, true)

    if (string.find(filename, "crontab") == nil) then
        -- 没找到配置文件, 就新建一个
        inc.p("未找到文件, 即将创建空文件: ", 10)
        local cmds = {}
        table.insert(cmds, "touch "..timer.fullName)
        inc.popen_server_cmds(scfg, cmds, nil, true)
        inc.p("创建成功: ", 10)
    else 
        -- 如果配置文件已经存在了, 那么就直接使用当前文件
        inc.p("已找到文件: "..filename, 10)
        timer.file = filename
        timer.fullName = timer.path..timer.file
    end
end

检查配置文件是否已存在, 存在则世界使用它, 不存在, 则创建一个

addTimerTask

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

-- 增加定时器
function timer.addTimerTask(scfg, servercfg)
    -- 设置时间
    local timetab = {}
    inc.p("请输入任务名", 10)
    local taskname = io.stdin:read()
    local ttaskname = taskname..timer.filenamemask
    -- 检测任务名是否存在, 任务名用于删, 查任务
    while (timer.checkTaskName(scfg, servercfg, ttaskname) == true) do
        inc.p("任务重名, 请重新输入", 14)
        taskname = io.stdin:read()
        ttaskname = taskname..timer.filenamemask
    end

    -- 设置定时器触发时间
    inc.p("请输入服务器关闭时间(月)", 10)
    timetab.month = io.stdin:read()
    inc.p("请输入服务器关闭时间(日)", 10)
    timetab.day = io.stdin:read()
    inc.p("请输入服务器关闭时间(时)", 10)
    timetab.hour = io.stdin:read()
    inc.p("请输入服务器关闭时间(分)", 10)
    timetab.minute = io.stdin:read()
    inc.p("服务器将计划于 "..timetab.month.."月"..timetab.day.."日"..
        timetab.hour.."时"..timetab.minute.."分 关闭, 确定? [输入y继续]", 12)
    if io.stdin:read() ~= 'y' then return end

    -- 这里构造了一条命令, 这条命令实现了添加一个定时器
    -- 这个定时器会到指定的服务器下, 调用 kill.net 来关闭服务器
    -- 关闭之后, 再使用 sed 命令, 将定时器删除, 然后重置定时器
    local cmds = {};
    local dir = timer.getFullPath(servercfg)
    local timestamp = timetab.minute..' '..timetab.hour..' '..timetab.day..' '..
        timetab.month..' '..'*'
    table.insert(cmds, "echo \""..timestamp.." echo \""..ttaskname.."\""
        ..';cd '..dir..';./kill.net'..
        ";sed -i \"/"..ttaskname.."/d\" "..timer.fullName..
        ";crontab "..timer.fullName.."\" >> "..timer.fullName)
    print (cmds[1]);
    -- 这是一个外部工具类中的函数, 主要是使用PLINK携带用户信息和验证, 链接服务器
    -- 然后执行 cmds 中保存的命令
    inc.popen_server_cmds(scfg, cmds, nil, true)
    -- 保存当前任务名, 用于判断任务是否成功
    timer.lastTask = ttaskname;
    timer.syncTask(scfg, servercfg)
end

checkTaskName

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

-- 检查文件名
function timer.checkTaskName(scfg, servercfg, ttaskname)
    local cmds = {}
    table.insert(cmds, "crontab -l")
    local dupname = false
    -- 第三个参数是回调函数, res中存储了执行 cmds 后, 服务器的输出
    -- 使用 crontab -l 查看了当前已有的任务, 如果找到了任务名, 则说明任务名重复
    inc.popen_server_cmds(scfg, cmds, function (res)
        for i, v in pairs(res) do
            if (string.find(v, ttaskname)) then
                dupname = true
                return
            end
        end
    end, true)

    return dupname
end

syncTask

1
2
3
4
5
6
7
8

-- 同步任务
function timer.syncTask(scfg, servercfg)
    local cmds = {}
    table.insert(cmds, "cd "..timer.path)
    table.insert(cmds, "crontab "..'./'..timer.file);
    -- 其实就是执行 crontab [filename], 这里可以合为一句的
    inc.popen_server_cmds(scfg, cmds, nil, true)
end

isAddSuccess

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

-- 是否增加成功
function timer.isAddSuccess(scfg, servercfg)
    local cmds = {}
    table.insert(cmds, "cat "..timer.fullName);
    local size1 = 0;
    -- 获取文件中的行数
    inc.popen_server_cmds(scfg, cmds, function (res)
        size1 = #res
    end, true)

    local cmds = {}
    table.insert(cmds, "crontab -l");
    local size2 = 0;
    -- 获取实际 crontab 任务的行数
    inc.popen_server_cmds(scfg, cmds, function (res)
        size2 = #res
    end, true)

    -- 如果行数不一致, 那么就说明加入失败
    -- 加入失败一般只有一种原因: 时间格式错误
    -- 我们也可以编写代码在执行加入前就判断, 但是判断时间的话, 涉及到平年和润年, 还涉及大小月
    -- 并且是服务器的时间, 所以也不能直接在windows上调用函数处理
    -- 考虑到这些原因, 就让linux帮我们做了这件事(反正行数不一致, 肯定是失败了)
    if size1 ~= size2 then 
        -- 添加失败就回滚一次任务
        timer.rollBack(scfg, servercfg)
    else
        inc.p("添加定时任务成功", 14)
    end
end

rollBack

1
2
3
4
5
6
7
8
9

-- 回滚一次任务
function timer.rollBack(scfg, servercfg)
    local cmds = {}
    -- 这里使用了 sed 来处理, 其中用到了我们之前记录的 lastTask
    table.insert(cmds, "sed -i "..'/'..timer.lastTask.."/d"..
        ' '..timer.fullName);
    inc.popen_server_cmds(scfg, cmds, nil, true)
    inc.p("时间格式错误, 已回滚", 12)
end

searchTimerTask

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

-- 查询定时器
function timer.searchTimerTask(scfg, servercfg)
    local cmds = {}
    table.insert(cmds, "crontab -l")
    inc.p("\n当前已有任务: ", 10)
    local orisrc = {}
    -- 查看当前已有的任务
    inc.popen_server_cmds(scfg, cmds, function (res)
        orisrc = res
    end, true)
	
    -- 这里是为了将数据格式化成方便看懂的格式
    timer.regex(orisrc, servercfg)
end

regex

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

-- 检测记录, 筛选信息
function timer.regex(orisrc, servercfg)
    for i, v in pairs(orisrc) do
        -- 获取任务时间戳
        local taskstamp;
        for v2 in string.gmatch(v, "%d+%s%d+%s%d+%s%d+") do 
            taskstamp = v2
        end

        -- 获取任务名
        local taskname;
        for v3 in string.gmatch(v, "echo.*"..timer.filenamemask..';') do 
            v3 = string.sub(v3, 6, #v3 - #timer.filenamemask - 1)
            taskname = v3 
        end

        -- 获取服务器名
        local hostname;
        for v4 in string.gmatch(v, "CRONTAB_TASK.*;cd%s/data/server/") do 
            v4 = string.sub(v4, 14, #v4 - 17)
            hostname = v4 
        end

        -- 如果这条信息是任务信息, 格式化打印出来
        if (taskstamp ~= nil and taskname ~= nil and hostname == timer.servername) then
            local timetab = {}
            for i in string.gmatch(taskstamp, "%d+") do
                table.insert(timetab, i);
            end

            inc.p("服务器: "..hostname.."  ========  任务名: "..taskname..
                "  ========  时间: "..
                timetab[4].."月"..timetab[3].."日"..
                timetab[2].."时"..timetab[1].."分", 14)
        end
    end
end

deleteTimerTask

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

-- 删除定时器
function timer.deleteTimerTask(scfg, servercfg)
    inc.p("请输入任务名(暂不支持中文)", 10)
    local taskname = io.stdin:read()
    local dir = timer.getFullPath(servercfg)
    local cmds = {}
    table.insert(cmds, "cd "..dir)
    local ttaskname = taskname..timer.filenamemask
    -- 执行一条 sed 命令, 删除一个任务
    table.insert(cmds, "sed -i "..'/'..ttaskname.."/d"..
        ' '..timer.fullName);
    inc.popen_server_cmds(scfg, cmds, nil, true)
    -- 同步一次
    timer.syncTask(scfg, servercfg)
end

summary

那么代码就这些了, 其中主要就是使用lua编写程序, 通过PLINK传递命令行信息

以此达到远程控制服务器定时器的效果

其中最主要的技术是:

lua语言基础, lua正则表达式

{ crontab, sed } 命令行, 数据流重定向

(emmmmmm… 看起来好像没什么厉害的…)

以及从<重构>中学到的代码技术

(一开始看重构这本书的时候, 本来对里面一些降低效率的做法不太满意)

(但是真的使用了之后, 发现代码的确好多了, 无论是易读, 编写, 调试, 增加/删除方面, 都有明显提升)

(不过可惜没有运用到<设计模式>中的东西(或许我用到了, 只是没注意到?) )

第一级值

长久以来一直不太明白之前在 lua 一本书中提到的 “第一类值”

直到今天在一本书上看到类似的解释:

一般而言, 程序设计语言总会对计算元素的可能使用方式强加上某些限制  
带有最少限制的元素具有"第一级"的状态, 第一级元素的某些特权包括:
* 可以用变量命名
* 可以提供给过程作为参数
* 可以由过程作为结果返回
* 可以包含在数据结构中

上述说的是第一级值, 猜想应该是第一类值拥有第一级特权

第一类函数

以下摘自 wiki 对第一类函数(first-class function)的解释

In computer science, a programming language is said to have first-    class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures
在计算机科学中, 一个编程语言如果对他函数就像第一类公民(??)一样, 那么就说他有第一类函数
这意味着语言支持将函数作为参数传递给其他函数
从其他函数中将其作为值返回
将其复制给变量, 或者保存到数据结构中

高阶函数

顺便 wiki 说了一下什么是高阶函数

First-class functions are a necessity for the functional programming style, in which the use of higher-order functions is a standard practice. A simple example of a higher-ordered function is the map function, which takes, as its arguments, a function and a list, and returns the list formed by applying the function to each member of the list. For a language to support map, it must support passing a function as an argument.
第一类函数对于函数化编程是必要的
其中使用高阶函数就是一个标准的实践
一个高阶函数的简单案例就是map函数
(...能意会, 但没法翻译...)
它必须支持传递函数作为参数

lambda 是如何工作的

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

int main() {                                    
    auto f = [](int x, int y) { return x + y; };
    printf("%d\n",  f(1, 2) );                                                        
    return 0;                                   
}                                               
...
_ZZ4mainENKUliiE_clEii:         
.LFB3999:                       
▹   .cfi_startproc              
▹   pushq▹  %rbp                
▹   .cfi_def_cfa_offset 16      
▹   .cfi_offset 6, -16          
▹   movq▹   %rsp, %rbp          
▹   .cfi_def_cfa_register 6     
▹   movq▹   %rdi, -8(%rbp)      // 唯一的区别在于, 多传了一个"this"
▹   movl▹   %esi, -12(%rbp)     
▹   movl▹   %edx, -16(%rbp)     
▹   movl▹   -16(%rbp), %eax     
▹   movl▹   -12(%rbp), %edx     
▹   addl▹   %edx, %eax          
▹   popq▹   %rbp                
▹   .cfi_def_cfa 7, 8           
▹   ret                         
...
▹   subq▹   $16, %rsp
▹   leaq▹   -1(%rbp), %rax	// 这个 this 指向了当前栈帧, 但是这里为什么要 -1 ?
▹   movl▹   $2, %edx
▹   movl▹   $1, %esi
▹   movq▹   %rax, %rdi            
▹   call▹   _ZZ4mainENKUliiE_clEii

在上面基础上, 让 lambda 捕获局部变量和全局变量

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

int gi = 11;
int main() {
    int i = 10;
    auto f = [i, gi](int x, int y) { return i + gi + x + y; };
    printf("%d\n",  f(1, 2) );
    return 0;
}
...
_ZZ4mainENKUliiE_clEii:     
.LFB3999:                   
▹   .cfi_startproc          
▹   pushq▹  %rbp            
▹   .cfi_def_cfa_offset 16  
▹   .cfi_offset 6, -16      
▹   movq▹   %rsp, %rbp      
▹   .cfi_def_cfa_register 6 
▹   movq▹   %rdi, -8(%rbp)  
▹   movl▹   %esi, -12(%rbp) 
▹   movl▹   %edx, -16(%rbp) 
▹   movq▹   -8(%rbp), %rax  
▹   movl▹   (%rax), %edx    
▹   movl▹   gi(%rip), %eax  	// @warning 即使是按值捕获, 全局变量也并未产生复制
▹   addl▹   %eax, %edx      
▹   movl▹   -12(%rbp), %eax 
▹   addl▹   %eax, %edx      
▹   movl▹   -16(%rbp), %eax 
▹   addl▹   %edx, %eax      
▹   popq▹   %rbp            
▹   .cfi_def_cfa 7, 8       
▹   ret                    
...
▹   subq▹   $16, %rsp             
▹   movl▹   $10, -4(%rbp)         
▹   movl▹   -4(%rbp), %eax        
▹   movl▹   %eax, -16(%rbp)       // 复制了一份 i
▹   leaq▹   -16(%rbp), %rax       
▹   movl▹   $2, %edx              
▹   movl▹   $1, %esi              
▹   movq▹   %rax, %rdi            
▹   call▹   _ZZ4mainENKUliiE_clEii

其中关键之处在于对待全局变量的方式, 这有可能产生错误, 事实也的确错了

1
2
3
4
5
6

printf("%d\n",  f(1, 2) );
gi = 100;
printf("%d\n",  f(1, 2) );
...
24
113 // gi 的值改变后, 输出结果也随之改变, 这不应该是按值捕获的结果

那么如果我加上 mutable 去更改这个 gi 呢?

1
2
3
4
5
6
7
8

auto f = [i, gi](int x, int y) mutable { gi = 110; return i + gi + x + y; };
printf("%d\n",  gi);      
printf("%d\n",  f(1, 2) );
printf("%d\n",  gi);
...
11
123
110	// 改变了! 这可是很重要的细节

上述结果, 编译器(gcc 4.8.5)只有一个警告

但是如果不注意这个细节, 去捕获全局变量, 可能会有很严重的错误

接下来专注一下类类型变量, 他会如何捕获 (这里的代码就有点头疼了)

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

int main() {                                   
    vector<int> v {1, 2, 3, 4};                
    int i = 10;                                
    auto f = [i, gi, v](int x, int y) mutable {
        v[2] = 10; gi = 110;·                  
        return i + gi + x + y; };              
    printf("%d\n",  gi);                       
    printf("%d\n",  f(1, 2) );                 
    printf("%d\n",  v[2]);                     

    return 0;                                  
}                                           
...
main:                                                          
.LFB3998:          
▹   pushq▹  %rbp                                                                       
▹   movq▹   %rsp, %rbp                                         
▹   pushq▹  %r13                                               
▹   pushq▹  %r12                                               
▹   pushq▹  %rbx                                               
▹   subq▹   $72, %rsp                                          
▹   leaq▹   -37(%rbp), %rax                                    
▹   movq▹   %rax, %rdi                                         
▹   call▹   _ZNSaIiEC1Ev                                       
▹   movl▹   $._91, %r12d                                       
▹   movl▹   $4, %r13d           // 这里的 4 是告诉 vector, 有 4 个元素 (猜的)
▹   leaq▹   -37(%rbp), %rdi                                    
▹   movq▹   %r12, %rcx                                         
▹   movq▹   %r13, %rbx                                         
▹   movq▹   %r12, %rax                                         
▹   movq▹   %r13, %rdx                                         
▹   movq▹   %rcx, %rsi                                         
▹   leaq▹   -64(%rbp), %rax     // 按照上下文理解, 这应该就是 vector 的 this 指针   
▹   movq▹   %rdi, %rcx                                         
▹   movq▹   %rax, %rdi                                         
.LEHB0:                                                        
▹   call▹   _ZNSt6vectorIiSaIiEEC1ESt16initializer_listIiERKS0_ // 真是个丑陋的小东西 = = 
.LEHE0:                                                        
▹   leaq▹   -37(%rbp), %rax                                    
▹   movq▹   %rax, %rdi                                         
▹   call▹   _ZNSaIiED1Ev                                       
▹   movl▹   $10, -36(%rbp)                                     
▹   movl▹   -36(%rbp), %eax                                    
▹   movl▹   %eax, -96(%rbp)       // 上面的 10 是路标, 这个应该就是 lambda 的 this 指针
▹   leaq▹   -64(%rbp), %rax       
▹   leaq▹   -96(%rbp), %rdx
▹   addq▹   $8, %rdx                                           
▹   movq▹   %rax, %rsi                                         
▹   movq▹   %rdx, %rdi                                         
.LEHB1:                                                        
▹   call▹   _ZNSt6vectorIiSaIiEEC1ERKS1_      // 上面那句最长的应该是列表初始化, 而这一句                 								// 可能是拷贝或者构造? 
.LEHE1:                               
▹   movl▹   gi(%rip), %eax       
▹   movl▹   %eax, %esi
▹   movl▹   $.LC0, %edi
▹   movl▹   $0, %eax
.LEHB2:
▹   call▹   printf
▹   leaq▹   -96(%rbp), %rax
▹   movl▹   $2, %edx
▹   movl▹   $1, %esi
▹   movq▹   %rax, %rdi
▹   call▹   _ZZ4mainENUliiE_clEii
...
_ZZ4mainENUliiE_clEii:              
.LFB4000:                           
▹   .cfi_startproc                  
▹   pushq▹  %rbp                    
▹   .cfi_def_cfa_offset 16          
▹   .cfi_offset 6, -16              
▹   movq▹   %rsp, %rbp              
▹   .cfi_def_cfa_register 6         
▹   subq▹   $16, %rsp               
▹   movq▹   %rdi, -8(%rbp)        // this 指针  
▹   movl▹   %esi, -12(%rbp)         
▹   movl▹   %edx, -16(%rbp)         
▹   movq▹   -8(%rbp), %rax          
▹   addq▹   $8, %rax                
▹   movl▹   $2, %esi                
▹   movq▹   %rax, %rdi
▹   call▹   _ZNSt6vectorIiSaIiEEixEm
▹   movl▹   $10, (%rax)             // 赋值
▹   movl▹   $110, gi(%rip)
▹   movq▹   -8(%rbp), %rax
▹   movl▹   (%rax), %edx
▹   movl▹   gi(%rip), %eax
▹   addl▹   %eax, %edx
▹   movl▹   -12(%rbp), %eax
▹   addl▹   %eax, %edx
▹   movl▹   -16(%rbp), %eax
▹   addl▹   %edx, %eax
▹   leave
▹   .cfi_def_cfa 7, 8
▹   ret

值拷贝类的时候, 会将整个类拷贝一次, 并没有什么特殊的

匿名函数与其说是函数, 不如说是类 他就像一个重载了调用运算符的类一样

前言

在看到<深入理解计算机系统>的浮点数时, 第一想法是:

• 无法精确保存大多数浮点数
• 精度上的缺失

零值的比较

很多面试题都会考一道浮点数零值比较的题(一般是单精度, 双精度太长了)

我觉得答案应该是:

1

f > -0.000001f && f < 0.000001f

这个题的核心在于 float 什么时候缺失精度

这里我没有使用等于, 因为我认为 0.000001f 和 -0.000001f 并不算缺失了精度

(百度上的答案是有等于的, 我很怀疑这个答案, 甚至有人还用的是 0.00001 (눈_눈) )

(而google上我好像没有找到类似的答案, 再根据编译器给我的结果, 我只能如此推断)

下面是我推断的依据:

1
2
3

printf("%f\n", 0.000001f);
printf("%f\n", 0.0000006f);
printf("%f\n", 0.0000005f);

你觉得上面会打印什么呢? 输出结果是:

1
2
3

0.000001
0.000001
0.000000

这也就是我认为 0.000001 它并未损失精度的原因, 既然未损失, 那么就不能当做 0 值来对待

(再次看不起百度上的解答(눈_눈), 不过… 万一是cas错了呢?)

(损失精度还有更精确的 0.00000055f, 这个数字也被认为是 0.000001)

数字的精度取决于有多少位表示

上面看到了6为精度的情况, 他准确表示了0.1 (虽然它把 0.0000006f 当做了0.1…)

我们来看看其他的结果, 比如:

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

printf("%f\n", 255.1f);
printf("%d\n", 254.2f == 254.200001f);
printf("%d\n", 254.2f == 254.200002f);
printf("%d\n", 254.2f == 254.200003f);
printf("%d\n", 254.2f == 254.200004f);
printf("%d\n", 254.2f == 254.200005f);
printf("%d\n", 254.2f == 254.200006f);
printf("%d\n", 254.2f == 254.200007f);
printf("%d\n", 254.2f == 254.200008f);
printf("%d\n", 254.2f == 254.200009f);
printf("%d\n", 254.2f == 254.199999f);
printf("%d\n", 254.2f == 254.199998f);
printf("%d\n", 254.2f == 254.199997f);
printf("%d\n", 254.2f == 254.199996f);
printf("%d\n", 254.2f == 254.199995f);
printf("%d\n", 254.2f == 254.199994f);
printf("%d\n", 254.2f == 254.199993f);
printf("%d\n", 254.2f == 254.199992f);
printf("%d\n", 254.2f == 254.199991f);
printf("%d\n", 254.2f == 254.199990f);

你觉得这次又会输出什么呢?

1

255.100006 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1

(输出结果我做了缩减, 不然太长了)

也就是说, 除了

1
2
3
4
5

254.200005f
254.200006f
254.200007f
254.200008f
254.200009f

之外, 编译器认为它们都是相等的, 为什么呢?

精度再次缺失(我只能如此猜测), 因为整数的数字过大, 剩下的留给小数的位数不足以达到6位精度

所以这次的精度缩减到了5位, 而因为四舍五入(我只能再次如此猜测 (눈_눈))的关系

(其实说四舍五入有点不对, 应该是: 数字的二进制表示刚好进入了有效的区间)

一些能达到 254.20001 的数字被判段为不等, 而一些 254.19999 的数字又可四舍五入的关系被判断为相等

所以, 整数数字的大小会影响小数的精度 (我感觉我在说废话 (눈_눈)), 而当整数过大时, 比如 0x7fffffffff

所有的小数精度全都会缺失(unsigned float 可能是例外, 不过不影响结论)

下面我又做了一次比较, 我将254换成了126, 输出结果是

0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0

emmm… 其实这次的有效精度还是接近5位

不过能够在5位之外, 能判断更多的数字了

(这个数字并未完全达到6位, 也许 0.000005 能判断到, 0.000004 却不能, 就像上面那样)

底层到底对我们的代码做了什么

又到了喜闻乐见的看汇编环节 ┑(￣Д ￣)┍

1
2
3
4
5
6

float f = 0.1f;
printf("%f\n", f);
printf("%f\n", f * 2);
float f2 = 0x7fff + 0.1f;
printf("%f\n", f2);
printf("%f\n", f2 * 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

.cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    subq    $16, %rsp			// 依旧是开辟了16个直接的栈帧, 为什么不是8(我有两个float)?
    movl    .LC0(%rip), %eax	// .long   1036831949
    movl    %eax, -4(%rbp)		// 将变量放到了栈中
    movss   -4(%rbp), %xmm0		// 放到了浮点数寄存器中
    cvtps2pd        %xmm0, %xmm0	// emmm... PS2PD Single-Precision Double-Precision
    						// 它将两个单精度浮点数转化成了双精度, 这可不在我的预料之中 ∑(￣□￣;)
    movl    $.LC1, %edi
    movl    $1, %eax
    call    printf
    movss   -4(%rbp), %xmm0
    addss   %xmm0, %xmm0
    unpcklps        %xmm0, %xmm0
    cvtps2pd        %xmm0, %xmm0
    movl    $.LC1, %edi
    movl    $1, %eax
    call    printf
    movl    .LC2(%rip), %eax	// .long   1191181875
    movl    %eax, -8(%rbp)
    movss   -8(%rbp), %xmm0
    cvtps2pd        %xmm0, %xmm0
    movl    $.LC1, %edi
    movl    $1, %eax
    call    printf
    movss   -8(%rbp), %xmm0
    addss   %xmm0, %xmm0
    unpcklps        %xmm0, %xmm0
    cvtps2pd        %xmm0, %xmm0
    movl    $.LC1, %edi
    movl    $1, %eax
    call    printf
    movl    $0, %eax
    leave
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc

关键点在于 .LC1 和 .LC2, 他们的数字, 不过一点数字看不出什么, 需要多一些数据

1
2
3

1036831949 = 0.1f	= 3dcccccd
1045220557 = 0.2f 	= 3e4ccccd
1038174126 = 0.11f	= 3de147ae

其中 0.1f 和 0.2f 相差 800000

0.1f 和 0.11f 相差 147ae1

emmmm… 想不出来, 或许我该再看看书

嗯 好的, 看完了 (￣ˇ￣)

大概是这样的, 根据不同的位数安排, 计算的结果也有相应的不同

一个浮点数, 1位符号位S, 8位阶码E, 23位小数位M

其中又分为4种情况: 规格, 非规格, NaN(not a number?), 无穷大

(具体的细节请参考书中的介绍)

总之, 我们用书中的算法来检验一下这几个数字

首先 0.1f, 它的数字是 3dcccccd, 它是一个规格化数字

E = 123 - 127 = -4 , M = 5033165 / 8388735 +１

2的E次方 x M = 0.0999994337644472

emmm… 没错, 这是一个非常接近 0.1 的数字

(书中说到了小数的舍入, 简单来说是四舍五入, 同时向偶数舍入, 比如 1.245 它会向 1.24 舍入)

(再次很好奇一些需要极其精确的小数运算是如何做到的 （ー_ー？）)

(像存储金额这样的小数精度, 特别是银行, 损失一个精度都很严重啊)

规格化用于表示一些比较大的数字, 而非规格化用于表示一些相对较小的数字

这里顺便再看一下失去精度的结果, 看看他是怎么计算的

1

printf("%f\n", 255.1f);

奇怪的是, 它有两个数字

1
2
3

111 .LC0:
112     .long   1073741824
113     .long   1081074483

可惜计算不出来, 这种格式是无穷大(不太明白 (눈_눈))

summary

简单来说, 其实也没有做笔记的必要 ┑(￣Д ￣)┍, 书上已经给了你答案

不过还好, 沉浸在思考的海洋中挺不错的(其实都快被淹死了 (눈_눈))

最后, 若无必要, 或者非常确信浮点数的范围, 否则不要使用单精度浮点数

如你所见, 单精度浮点数的范围很小, 一不小心还要失去精度

(这可能也是默认小数是双精度的原因)

前言

下班忘把没读完的 inside the c++ object model 带回去

还好包里有本备用的 go, 简单看了一下前面基础部分

感觉就是, 很”新颖 + 轻巧”, 有很多新的概念和工具, 抛弃了一些沉重的”包袱”

试了一下用例, 看了一下汇编

1
2
3
4
5
6
7

1 package main
2 
3 import "fmt"
4     
5 func main() {
6     fmt.Printf("hello, world\n")
7 }

汇编:

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

 1 # command-line-arguments                                                                 
 2 "".main STEXT size=88 args=0x0 locals=0x48                                               
 3     0x0000 00000 (/test/go/t.go:5)  TEXT    "".main(SB), $72-0                           				// 非常友好地给我加上了对应的源码信息
 4     0x0000 00000 (/test/go/t.go:5)  MOVQ    (TLS), CX                                    
 5     0x0009 00009 (/test/go/t.go:5)  CMPQ    SP, 16(CX)                                   
 6     0x000d 00013 (/test/go/t.go:5)  JLS 81                                               
 7     0x000f 00015 (/test/go/t.go:5)  SUBQ    $72, SP	// 这里应该是在开辟栈帧                                     
 8     0x0013 00019 (/test/go/t.go:5)  MOVQ    BP, 64(SP)	// 栈顶保存了 bp 指针                                   
 9     0x0018 00024 (/test/go/t.go:5)  LEAQ    64(SP), BP  // 重置 bp                                 
10     0x001d 00029 (/test/go/t.go:5)  FUNCDATA    $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)	// gc ? garbage collection?
11     0x001d 00029 (/test/go/t.go:5)  FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
12     0x001d 00029 (/test/go/t.go:5)  FUNCDATA    $3, gclocals·9fb7f0986f647f17cb53dda1484e0f7a(SB)	// 看不懂 = =
13     0x001d 00029 (/test/go/t.go:6)  PCDATA  $2, $1                                       
14     0x001d 00029 (/test/go/t.go:6)  PCDATA  $0, $0	// 还是看不懂 = =
15     0x001d 00029 (/test/go/t.go:6)  LEAQ    go.string."hello, world\n"(SB), AX           						// 加载字符串文本, 者很方便, 我直接可以看到字符串
16     0x0024 00036 (/test/go/t.go:6)  PCDATA  $2, $0                                       
17     0x0024 00036 (/test/go/t.go:6)  MOVQ    AX, (SP)                                     
18     0x0028 00040 (/test/go/t.go:6)  MOVQ    $13, 8(SP)	// 应该是指字符串长度
19     0x0031 00049 (/test/go/t.go:6)  MOVQ    $0, 16(SP)  // 后续参数数量?                                 
20     0x003a 00058 (/test/go/t.go:6)  XORPS   X0, X0	// 单精度异或?
21     0x003d 00061 (/test/go/t.go:6)  MOVUPS  X0, 24(SP)                                   						// 代码中没有用到单精度浮点数, 为什么会有这个指令?
22     0x0042 00066 (/test/go/t.go:6)  CALL    fmt.Printf(SB) // 调用                              					// 这样的格式很清晰
23     0x0047 00071 (/test/go/t.go:7)  MOVQ    64(SP), BP  // 返还 bp                                 
24     0x004c 00076 (/test/go/t.go:7)  ADDQ    $72, SP	// 重置栈顶
25     0x0050 00080 (/test/go/t.go:7)  RET	// 结束
26     0x0051 00081 (/test/go/t.go:7)  NOP
27     0x0051 00081 (/test/go/t.go:5)  PCDATA  $0, $-1                                      
28     0x0051 00081 (/test/go/t.go:5)  PCDATA  $2, $-1                                      
29     0x0051 00081 (/test/go/t.go:5)  CALL    runtime.morestack_noctxt(SB)                 								// 运行时的什么?
30     0x0056 00086 (/test/go/t.go:5)  JMP 0

FUNCDATA 我怀疑和垃圾回收有关, PCDATA 意义不明 (网上查了一下, 都和垃圾回收有关)

我尝试过添加一个参数, 以用作 fmt.Println(), 但是我并未在代码中找到任何有关参数的信息

仅仅只有一句看起来和那个参数有关

1
2
3

LEAQ    ""..autotmp_0+64(SP), AX	// 就是这句话
PCDATA  $2, $0                  
MOVQ    AX, 16(SP)

而且我差点忽略的一点是, 这里参数的传递是用栈

顺便, 我在文件的末尾找到了这些信息, 看起来像是某种标记

1
2
3
4
5
6
7
8

213 gclocals·69c1753bd5f81501d95132d08af04464 SRODATA dupok size=8        
214     0x0000 02 00 00 00 00 00 00 00                          ........  
215 gclocals·568470801006e5c0dc3947ea998fe279 SRODATA dupok size=10       
216     0x0000 02 00 00 00 02 00 00 00 00 02                    ..........
217 gclocals·9fb7f0986f647f17cb53dda1484e0f7a SRODATA dupok size=10       
218     0x0000 02 00 00 00 01 00 00 00 00 01                    ..........
219 gclocals·33cdeccccebe80329f1fdbee7f5874cb SRODATA dupok size=8        
220     0x0000 01 00 00 00 00 00 00 00                          ........

我再次使用了变量存储值的形式, 然后我的数字能够正常看见了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

0x0034 00052 (/test/go/t.go:7)  MOVQ    $100, 8(SP)	// 我的数字在这里
0x003d 00061 (/test/go/t.go:7)  CALL    runtime.convT2E64(SB)
0x0042 00066 (/test/go/t.go:7)  MOVQ    16(SP), AX
0x0047 00071 (/test/go/t.go:7)  PCDATA  $2, $2
0x0047 00071 (/test/go/t.go:7)  MOVQ    24(SP), CX
0x004c 00076 (/test/go/t.go:7)  MOVQ    AX, ""..autotmp_1+64(SP)
0x0051 00081 (/test/go/t.go:7)  PCDATA  $2, $0
0x0051 00081 (/test/go/t.go:7)  MOVQ    CX, ""..autotmp_1+72(SP)
0x0056 00086 (/test/go/t.go:7)  PCDATA  $2, $1
0x0056 00086 (/test/go/t.go:7)  LEAQ    go.string."hello, world\n%d"(SB), AX
0x005d 00093 (/test/go/t.go:7)  PCDATA  $2, $0
0x005d 00093 (/test/go/t.go:7)  MOVQ    AX, (SP)
0x0061 00097 (/test/go/t.go:7)  MOVQ    $15, 8(SP)
0x006a 00106 (/test/go/t.go:7)  PCDATA  $2, $1
0x006a 00106 (/test/go/t.go:7)  LEAQ    ""..autotmp_1+64(SP), AX
0x006f 00111 (/test/go/t.go:7)  PCDATA  $2, $0
0x006f 00111 (/test/go/t.go:7)  MOVQ    AX, 16(SP)
0x0074 00116 (/test/go/t.go:7)  MOVQ    $1, 24(SP)
0x007d 00125 (/test/go/t.go:7)  MOVQ    $1, 32(SP)
0x0086 00134 (/test/go/t.go:7)  CALL    fmt.Printf(SB)	
						// 但是在调用之前, 我并没看到我的数字被加载了, 为什么?
						// 我唯一比较怀疑的是那个 CALL runtime.convT2E64(SB)

好吧, 我的数据再度丢失了, 我甚至不知道它是如何被传过去的…

summary

go的汇编基于 plan 9(一个新的操作系统), 感觉到了新的技术和观点

并且它也更加友好, 我明显觉得看它的汇编会更轻松一些

(除了那个 PCDATA, FUNCDATA, 和那个已经被我跟丢的变量)

emmm… 很不错, 觉得自己听了别人的建议, 去学新的语言

而不学现在看起来很强大, 但是已经很老了的 java 是一个正确的决定

之前就看过关于在内核以及用户空间实现线程的文章, 到现在还对于其中的一些点一知半解, 比如: 为什么实现在用户空间的线程比实现在内核空间的快?. 今天碰巧看到了这篇文章, 原文出自 <modern operating system, fourth edition>

threads implementation in kernel and user space

2.2.4 Implementing Threads in User Space

There are two main places to implement threads: user space and the kernel.
The choice is a bit controversial, and a hybrid implementation is also possible. We
will now describe these methods, along with their advantages and disadvantages.

有两种主要的地方用于实现线程: 用户空间以及内核空间. 如何在哪里实现具有一定争议性, 同时, 一种混合的实现也是可能的. 我们将会概述这些方法, 以及他们的优点和缺点.

The first method is to put the threads package entirely in user space. The kernel knows nothing about them. As far as the kernel is concerned, it is managing
ordinary, single-threaded processes. The first, and most obvious, advantage is that
a user-level threads package can be implemented on an operating system that does
not support threads. All operating systems used to fall into this category, and even
now some still do. With this approach, threads are implemented by a library.

第一种方法是将整个线程包放到用户空间. 内核对此毫无所知. 就内核而言, 它依旧像对待单线程对象一样.

首先, 最明显的优点是, 用户级别的线程可以实现在一个不支持多线程的操作系统上.所有的操作系统曾经都是这种类型, 直到现在还有部分保留, 在这种方式下, 线程通过一个库实现.

All of these implementations have the same general structure, illustrated in
Fig. 2-16(a). The threads run on top of a run-time system, which is a collection of
procedures that manage threads. We have seen four of these already: pthread create, pthread exit, pthread join, and pthread yield, but usually there are more.

所有的实现有同样通用的结构, 如图2-16(a). 线程运行于运行时系统上(一系列管理线程的程序). 我们已经见过四种这样的程序了: 线程创建, 退出, 加入, 放弃(这是本书前面部分的内容, 但为什么是 pthread 呢? 难道是基于 posix 标准的线程实现?)

When threads are managed in user space, each process needs its own private
thread table to keep track of the threads in that process. This table is analogous to
the kernel’s process table, except that it keeps track only of the per-thread proper-
ties, such as each thread’s program counter, stack pointer, registers, state, and so
forth. The thread table is managed by the run-time system. When a thread is
moved to ready state or blocked state, the information needed to restart it is stored
in the thread table, exactly the same way as the kernel stores information about
processes in the process table.

当线程管理于用户空间时, 每个进程需要拥有独有的线程表, 以用于持续跟踪进程中的线程. 这个表类似与内核的进程表, 不过它只跟踪每个线程的属性. 比如每个线程的程序计数器, 栈指针, 寄存器, 状态, 以及…

线程表由运行时系统管理, 当线程转变为就绪/阻塞状态时, 用于重启的信息就存储在线程表中, 就和内核在进程表中存储关于进程的信息一样.

When a thread does something that may cause it to become blocked locally, for
example, waiting for another thread in its process to complete some work, it calls a
run-time system procedure. This procedure checks to see if the thread must be put
into blocked state. If so, it stores the thread’s registers (i.e., its own) in the thread
table, looks in the table for a ready thread to run, and reloads the machine registers
with the new thread’s saved values. As soon as the stack pointer and program
counter have been switched, the new thread comes to life again automatically.

如果线程做了某些操作导致它本地阻塞时, 比如: 等待进程中的其他线程完成某些工作. 它调用一个运行时作业调度.

这个程序检查线程是否必须置于阻塞态, 如果是, 它在线程表中存储线程的寄存器(它自己的). 在表中查找一个就绪态线程运行, 重新加载新线程的寄存器. 同时栈指针和程序计数器也会切换, 新线程再次自动运行.

If the machine happens to have an instruction to store all the registers and another
one to load them all, the entire thread switch can be done in just a handful of in-
structions. Doing thread switching like this is at least an order of magnitude—
maybe more—faster than trapping to the kernel and is a strong argument in favor
of user-level threads packages.

如果机器开始有一个指令可以存储所有的寄存器, 同时另一个指令加载他们, 那么整个线程的切换就只需要少量的指令.

要完成这样的线程切换比捕获内核至少快一个数量级, 或许更快. 这是一个对用户级线程拥护者强有力的论点.

However, there is one key difference with processes. When a thread is finished
running for the moment, for example, when it calls thread yield, the code of
thread yield can save the thread’s information in the thread table itself. Fur-
thermore, it can then call the thread scheduler to pick another thread to run. The
procedure that saves the thread’s state and the scheduler are just local procedures,
so invoking them is much more efficient than making a kernel call. Among other
issues, no trap is needed, no context switch is needed, the memory cache need not
be flushed, and so on. This makes thread scheduling very fast.

然而, 有一个关于进程的关键不同. 当线程暂停时, 比如: 调用 yield, 保存线程的信息到线程表中.

更进步一, 调用线程调度, 选择另一个线程执行. 程序保存线程状态, 因为调度只是本地程序, 所以调用其会比内核调用更加高效. 其他方面, 没有捕获, 没有环境切换, 内存缓冲也不需要刷新, 等等. 这使得线程调度非常快.

User-level threads also have other advantages. They allow each process to have
its own customized scheduling algorithm. For some applications, for example,
those with a garbage-collector thread, not having to worry about a thread being
stopped at an inconvenient moment is a plus. They also scale better, since kernel
threads invariably require some table space and stack space in the kernel, which
can be a problem if there are a very large number of threads.

用户级线程还有其他优点. 它使每个进程都可以有自己的特定调度算法. 对于一些应用, 比如垃圾回收线程, 不用担心线程在不适当时候停下来, 这是一个优点. 他们拥有更好的伸缩性, 因为内核线程总是需要一些表空间和栈空间, 当线程逐渐增加时, 会造成麻烦.

Despite their better performance, user-level threads packages have some major
problems. First among these is the problem of how blocking system calls are im-
plemented. Suppose that a thread reads from the keyboard before any keys hav e
been hit. Letting the thread actually make the system call is unacceptable, since
this will stop all the threads. One of the main goals of having threads in the first
place was to allow each one to use blocking calls, but to prevent one blocked
thread from affecting the others. With blocking system calls, it is hard to see how
this goal can be achieved readily.

即使它们拥有更好的性能, 用户级线程包也有一些固有的问题.

首先, 如何实现阻塞的系统调用. 假如线程等待来自键盘的输入, 让这个线程准确执行系统调用是不允许的, 因为这会阻塞所有线程, 线程的首要目的之一是允许每个线程使用阻塞调用, 但是保证一个阻塞线程不会影响其他线程. 可以看出这很难实现.

The system calls could all be changed to be nonblocking (e.g., a read on the
keyboard would just return 0 bytes if no characters were already buffered), but re-
quiring changes to the operating system is unattractive. Besides, one argument for
user-level threads was precisely that they could run with existing operating sys-
tems. In addition, changing the semantics of read will require changes to many
user programs.

系统调用必须都变为非阻塞的(比如, 读取键盘输入应该在没有任何字符被缓存时返回0), 但是这对于操作系统而已不太友好. 次外(我真不知道怎么翻译这句…). 另外, 改变读取的语义将会影响到大量用户程序.

Another alternative is available in the event that it is possible to tell in advance
if a call will block. In most versions of UNIX, a system call, select , exists, which
allows the caller to tell whether a prospective read will block. When this call is
present, the library procedure read can be replaced with a new one that first does a
select call and then does the read call only if it is safe (i.e., will not block). If the
read call will block, the call is not made. Instead, another thread is run. The next
time the run-time system gets control, it can check again to see if the read is now
safe. This approach requires rewriting parts of the system call library, and is inef-
ficient and inelegant, but there is little choice. The code placed around the system
call to do the checking is called a jacket or wrapper.

在这种情况下还有另一个方法: 提前告知一个调用将会被阻塞是可行的(??? 啥意思啊 = =).

在多个 UNIX 版本中, 选择性地存在系统调用运行调用者判断未来的读操作将会阻塞. 当这样的调用存在时, 库程序读取替换成一个首先做判断, 然后当确定是安全的时候读取(比如, 非阻塞).不会执行会阻塞的读操作, 另一个线程将会运行.

在下次运行时系统获得控制时, 会再次检查读操作是否是安全的. 这个方法需要重写部分系统调用库. 不那么高效和优雅. 不过这是一个选择, 放置在系统函数周围的代码去检查的这种方法被称为 jacket 或 wrapper.

Somewhat analogous to the problem of blocking system calls is the problem of
page faults. We will study these in Chap. 3. For the moment, suffice it to say that
computers can be set up in such a way that not all of the program is in main memo-
ry at once. If the program calls or jumps to an instruction that is not in memory, a
page fault occurs and the operating system will go and get the missing instruction
(and its neighbors) from disk. This is called a page fault. The process is blocked
while the necessary instruction is being located and read in. If a thread causes a
page fault, the kernel, unaware of even the existence of threads, naturally blocks
the entire process until the disk I/O is complete, even though other threads might
be runnable.01

(简单来说, 这段说的是页错误, 主存和磁盘间虚拟空间内容的交换.)

Another problem with user-level thread packages is that if a thread starts run-
ning, no other thread in that process will ever run unless the first thread voluntarily
gives up the CPU. Within a single process, there are no clock interrupts, making it
impossible to schedule processes round-robin fashion (taking turns). Unless a
thread enters the run-time system of its own free will, the scheduler will never get a
chance.

用户级线程将面临的另一个问题是: 当线程开始执行时, 除非自愿放弃, 不然其他线程无法执行.

单线程程序, 不会产生时钟终端, 使用 round-robin 调度器管理进程是不可能的. 除非线程自愿进入运行时系统. 否则调度器将不会生效.

One possible solution to the problem of threads running forever is to have the
run-time system request a clock signal (interrupt) once a second to give it control,
but this, too, is crude and messy to program. Periodic clock interrupts at a higher
frequency are not always possible, and even if they are, the total overhead may be
substantial. Furthermore, a thread might also need a clock interrupt, interfering
with the run-time system’s use of the clock.

一个可能的方法是: 让运行时系统每秒请求一个时钟信号来控制它(总而言之这是一个馊主意).

Another, and really the most devastating, argument against user-level threads is
that programmers generally want threads precisely in applications where the
threads block often, as, for example, in a multithreaded Web server. These threads
are constantly making system calls. Once a trap has occurred to the kernel to carry
out the system call, it is hardly any more work for the kernel to switch threads if
the old one has blocked, and having the kernel do this eliminates the need for con-
stantly making select system calls that check to see if read system calls are safe.
For applications that are essentially entirely CPU bound and rarely block, what is
the point of having threads at all? No one would seriously propose computing the
first n prime numbers or playing chess using threads because there is nothing to be
gained by doing it that way.

另一个反对用户级线程的论证(也是最具破坏性的)是, 程序员通常希望线程在线程经常阻塞的应用中使用, 比如, 在一个多线程 web 服务器中. 线程不间断地使用系统调用, 一旦内核执行系统调用, 如果旧线程已被阻塞, 那么切换线程就几乎没有其他需要做的了. …(后面我翻不下去了, 大概意思是, 这样的话, 程序就没有必要使用多线程了)

(总结归纳一下: 大概意思是, 用户级线程最大的优点是在于其切换起来很快, 但是我们通常希望在频繁发生线程阻塞的应用中使用线程, 而在这种情况下, 线程切换所需的操作就会变少(如果旧线程已经被阻塞了的话), 那么 用户级线程存在的意义就不大了)

2.2.5 Implementing Threads in the Kernel

Now let us consider having the kernel know about and manage the threads. No
run-time system is needed in each, as shown in Fig. 2-16(b). Also, there is no
thread table in each process. Instead, the kernel has a thread table that keeps track
of all the threads in the system. When a thread wants to create a new thread or
destroy an existing thread, it makes a kernel call, which then does the creation or
destruction by updating the kernel thread table.

现在, 让我们考虑让内核知道如何管理线程. 如图 2-16(b) 所示, 在进程中没有运行时系统, 也没有线程表. 内核有张线程表, 用于跟踪系统中的所有线程. 当线程想要创建或删除一个线程时, 使用一个内核调用, 然后通过更新内核线程表来创建或删除.

The kernel’s thread table holds each thread’s registers, state, and other infor-
mation. The information is the same as with user-level threads, but now kept in the
kernel instead of in user space (inside the run-time system). This information is a
subset of the information that traditional kernels maintain about their single-
threaded processes, that is, the process state. In addition, the kernel also maintains
the traditional process table to keep track of processes.

内核的线程表保存每个线程的寄存器, 状态, 以及其他信息. 与用户级线程保存的信息一致, 只是保存在内核中.

这些信息是传统内核管理的单线程进程信息的子集. 内核也同样管理传统的进程表, 以用于跟踪进程.

All calls that might block a thread are implemented as system calls, at consid-
erably greater cost than a call to a run-time system procedure. When a thread
blocks, the kernel, at its option, can run either another thread from the same proc-
ess (if one is ready) or a thread from a different process. With user-level threads,
the run-time system keeps running threads from its own process until the kernel
takes the CPU away from it (or there are no ready threads left to run).

所有可能阻塞线程的调用都被实现为系统调用, 相对运行时系统的调用, 明显有很大的额外消耗. 当线程阻塞时, 内核可以选择同进程下的线程运行, 也可以运行另一个进程的线程. 但用户级线程只会运行本进程的线程, 直到内核不让其使用 CPU 资源.

Due to the relatively greater cost of creating and destroying threads in the ker-
nel, some systems take an environmentally correct approach and recycle their
threads. When a thread is destroyed, it is marked as not runnable, but its kernel
data structures are not otherwise affected. Later, when a new thread must be creat-
ed, an old thread is reactivated, saving some overhead. Thread recycling is also
possible for user-level threads, but since the thread-management overhead is much
smaller, there is less incentive to do this.

因为在内核中创建和销毁线程操作相对更费力, 一些系统使用与环境相关的方法, 重利用它们的线程.

当线程销毁时, 将其标记为不可运行, 但是其内核数据结构不受影响, 随后, 当新线程需要创建时, 重新利用这些资源. 用户级线程也可以使用这个方法, 不过因为线程管理的消耗较小, 并不是很有必要这么做

Kernel threads do not require any new, nonblocking system calls. In addition,
if one thread in a process causes a page fault, the kernel can easily check to see if
the process has any other runnable threads, and if so, run one of them while wait-
ing for the required page to be brought in from the disk. Their main disadvantage is
that the cost of a system call is substantial, so if thread operations (creation, termi-
nation, etc.) a common, much more overhead will be incurred.

内核线程不需要任何新的, 非阻塞系统调用. 另外, 如果线程导致了页错误, 内核可以轻松地检查进程是否有其他线程可运行, 如果有, 在等待所需的页加载入内存中时, 执行该线程. 它们潜在的问题是: 系统调用比较耗时, 所以如果线程操作比较常见, 则会有更多的负载.

While kernel threads solve some problems, they do not solve all problems. For
example, what happens when a multithreaded process forks? Does the new proc-
ess have as many threads as the old one did, or does it have just one? In many
cases, the best choice depends on what the process is planning to do next. If it is
going to call exec to start a new program, probably one thread is the correct choice,
but if it continues to execute, reproducing all the threads is probably best.

内核线程依旧有一些未能解决的问题, 比如, 当多线程进程执行 fork 的时候, 会发生什么? 新的进程是否会像旧进程一样拥有同样多的线程呢? 还是只拥有一个呢? 在大多数情况下, 取决于进程将要做什么, 如果它将会调用 exec 执行一个新的程序, 当然只有一个好, 但是如果是继续运行的话, 则保留所有的线程则是最好的.

(PS: 在 linux posix 线程下, 默认是同样多的线程)

Another issue is signals. Remember that signals are sent to processes, not to
threads, at least in the classical model. When a signal comes in, which thread
should handle it? Possibly threads could register their interest in certain signals, so
when a signal came in it would be given to the thread that said it wants it. But what
happens if two or more threads register for the same signal? These are only two of
the problems threads introduce, and there are more.

另一个问题是信号. 信号是发给进程的, 而并非线程(至少在经典模型下). 当信号到达时, 那个线程来处理它呢? 可能线程会注册自己感兴趣的信号, 所以, 当信号到达, 会交由那个注册线程处理. 但是如果多个线程注册了同样的信号呢? 这仅仅是线程引入的其中两个问题.

2.2.6 Hybrid Implementations

Various ways have been investigated to try to combine the advantages of user-
level threads with kernel-level threads. One way is use kernel-level threads and
then multiplex user-level threads onto some or all of them, as shown in Fig. 2-17.
When this approach is used, the programmer can determine how many kernel
threads to use and how many user-level threads to multiplex on each one. This
model gives the ultimate in flexibility.

已经有多种方法被研究出来, 用于融合用户级线程和内核级线程. 其中一种方法是使用内核级别线程, 然后每个内核线程使用多个用户级别线程. 如 2-17.

程序能够知晓多少内核线程, 多少用户线程被使用. 这种模型给予了很大的灵活性.

With this approach, the kernel is aware of only the kernel-level threads and
schedules those. Some of those threads may have multiple user-level threads multi-
plexed on top of them. These user-level threads are created, destroyed, and sched-
uled just like user-level threads in a process that runs on an operating system with-
out multithreading capability. In this model, each kernel-level thread has some set
of user-level threads that take turns using it.

在这种方法下, 内核只至少内核线程, 并调度它们. 其中一些内核线程上可能存在多个用户级线程. 这些用户线程将会在进程中管控.

内核线程和用户线程各有其优势, 用户线程效率更高, 但是操作系统不知情的情况下, 会产生许多逻辑上是多线程, 但物理上依旧是单线程才会产生的错误. 比如 信号, 中断. 而内核线程虽然相对效率低, 并且占用内核空间, 但是操作系统知晓是多线程, 与操作系统间有更多协作的空间.