C++ 简史

Bjarne Stroustrup 在剑桥读博的时候,需要实现一个「分布式的操作系统」。他回忆起自己在丹麦读大学的时候就用过 Simula,认为 Simula 的一些特性比如「类型表达」、「编译排错」能力以及「类」和「协程」都很有吸引力,于是选择 Simula 语言作为工具来实现这个系统。

结果他实现的系统慢得不能接受,为了能按时毕业,他只好用 BCPL 重写了那个程序。他也在那时暗下决心,之后要是没有顺手的工具,他再也不会去处理类似这种的问题。当然他也对顺手的工具做出了定义,它应该:

  • 具有 Simula 这种对程序组织的支持——某种形式的类分层结构,对并发的某种支持以及基于类的静态检查。
  • 运行得像 BCPL 一样
  • 支持高度可移植实现

毕业之后,他来到了贝尔实验室。工作过程中有一个需求是要去分析 Unix 内核,然后把它部署在一个局域网上。这时候他面临了两个问题,一是如何分析因为内核分布造成的网络流量,其次是怎么将内核模块化。

那时的他也更明确了自己所描述的语言会以什么样的形式诞生,他形容这种语言是『带有 「Simula 类」的「Algol 68」』。但他坦言,如果要构造以及实际工具,C 还是稍微比 Algol 68 要合适一些,因为在当时,C 语言可以用到当时几乎所有领域,同时程序员可以用 C 语言有效地利用硬件资源,并且在当时已有可用的 C 编译系统和标准库,以及一些相关的工具,所以在灵活性,高效性,可用性和可移植性方面,C 语言都当仁不让。这也是为什么 C 成为了 C++ 的母语言。在实现新语言的过程中,BS 最初的需求是:可以像使用 Simula 一样使用 C,让程序员去描述类型。于是他采用了 Simula 中的术语 Class 来让 C++ 支持定义类型。

待续

Reference

《C++语言的设计与演化》

人类误判心理(3)

作者:查理·芒格

Third: incentive-cause bias, both in one’s own mind and that of ones trusted advisor, where it creates what economists call ‘agency costs.’

第三条:由激励导致的偏见,同时存在于每个人和其所信赖的顾问的脑海中,它造就了经济学家所谓的「代理成本」(agency costs)

Here, my early experience was a doctor who sent bushel baskets full of normal gall bladders down to the pathology lab in the leading hospital in Lincoln, Nebraska. And with that quality control for which community hospitals are famous, about five years after he should’ve been removed from the staff, he was. And one of the old doctors who participated in the removal was also a family friend, and I asked him: I said, “Tell me, did he think, ‘Here’s a way for me to exercise my talents’” — this guy was very skilled technically— “’and make a high living by doing a few maimings and murders every year, along with some frauds?’” And he said, “Hell no, Charlie. He thought that the gall bladder was the source of all medical evil, and if you really love your patients, you couldn’t get that organ out rapidly enough.”

之前在 Lincoln, Nebraska 的一家顶级医院中,有一名医生经常提着装了一篮子「一切正常」的胆囊到病理学实验室,五年之后,他被这家以质量闻名的社区医院开除了。

有一位当时参与了做出开除决定的老医生,是家里的朋友。我问他:『是不是这人觉得自己技术不错,通过致残、杀害和欺诈一些人,来施展自己的「才华」,过上土豪的生活?』。

老医生回答说:「当然不是,他认为胆囊是医疗隐患,如果你真的爱你的病人,就要用最快的速度把这个它从他体内取出。」

未完待续

软件工程师的核心价值

高效完成产品需求

用最少的时间完成PM的需求,用更多的时间去接触新技术,制造(学习)工具,提高效率,享受生活

提取工作重复部分 (DRY)

提取工作中的重复部分,独立维护。写的代码越多,需要维护的代码就越多,所以要尽量减少代码冗余(据嗣彬同学说,邓公在FW内部培训的时候也表达过类似的观点)。

将系统抽象成模型

因为语言和文字是一切知识的载体,所以要能够用语言和文字精确和完整地描述整个系统,让他人无障碍地了解这个系统。

Code and Error

推荐阅读

靠谱的代码和DRY

B-Tree

简介

如果一个内部节点 X 包含了 n 个有序关键字,那么节点 Xn + 1 个子节点,每个叶节点有相同的深度即树的高度。

节点 X 由其关键字分隔为 n + 1 个子域,每个子域和一个子树相对应。在对一个关键字进行搜索时,会通过比较节点中关键字,进行 n + 1 路选择遍历查找。

B-Tree

节点中关键字的个数存在上下界,用B-Tree的最小度数 t >= 2 来表示。非根节点至少有 t - 1 个关键字,即有 t 棵子树;至多有 2t - 1 个关键字,即有 2t 棵子树,这时我们称这个节点是满的。当 t = 2 时,每个内部节点有 2 个、 3 个或 4 个子树,即一棵 2-3-4 树

基本操作

class BTree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def search(key)
b_tree_search(@root, key)
end

def b_tree_search(node = nil, search_key)
return nil unless node
node.keys.each_with_index do |key, idx|
return [node, idx] if search_key == key
next if search_key > key
b_tree_search(node.child[idx], key)
break
end
b_tree_search(node.child.last, key)
nil
end

B-TREE-CREATE

class Node

1
2
3
4
5
def initialize
@leaf = true
@keys = []
@child = []
end

class BTree

1
2
3
def initialize
@root = Node.new
end

插入关键字

我们无法直接新建一个叶节点,把关键字插入其中(这样的B-Tree可能是不合法的),所以我们会把新的关键字插入到已有的节点中。不过这样可能会导致一个节点关键字的数量超过它的上界,所以我们引入一个新的操作:分裂B-Tree中的节点。

B-TREE-SPLIT-CHILD

B-TREE-SPLIT-CHILD
class BTree

1
2
3
4
5
6
7
8
9
10
11
def b_tree_split_node(node, pos)
new_child = Node.new
old_child = node.child[pos]

new_child.leaf = old_child.leaf
new_child.keys = old_child.pop(@t - 1)
new_child.child = old_child.pop(@t)

node.insert_child( new_child, pos + 1 )
node.insert_key( old_child.keys.pop, pos )
end

待续

[Rails] 从Request到Response(2)

本文翻译自:Rails from Request to Response 系列;个人选择了自己感兴趣的部分进行翻译,需要阅读原文的同学请戳前面的链接。

第二部分 路由(Routing)

Blog::Application.routes 的定义也在 engine.rb 文件中:

1
2
3
4
5
6
7
# rails/railties/lib/rails/engine.rb

def routes
@routes ||= ActionDispatch::Routing::RouteSet.new
@routes.append(&Proc.new) if block_given?
@routes
end

Blog::Application.routes 会返回一个 ActionDispatch::Routing::RouteSet 的实例。这是我们第一次接触到 ActionDispatch 模块(module),它是 ActionPack 的一部分。

ActionDispatch :
负责处理例如「路由(Routing)」,「参数解析(Parameter Parsing)」,「Cookies」和「Sessions」之类的工作;

ActionPack :
Rails 源码的顶层的 gem 之一,功能包括:路由功能, controller (ActionController)的定义和 view (ActionView)的渲染;

RouteSet :
此类是一个Route的集合,包括一个 route 的数组(Mapper),和一个 named route (NamedRouteCollection: name 对应着一组普通的 route 集合的Hash)。负责解释和分派请求(Request)到对应的控制器(Controller)动作(Action)。

现在继续来看 engine ,回到 RouteSet 的 #call 方法,相关的代码在 actionpack/lib/action_dispatch/routing/route_set.rb 中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# rails/actionpack/lib/action_dispatch/routing/route_set.rb

module ActionDispatch
module Routing
class RouteSet

def call(env)
@router.call(env)
end

...

end
end
end

RouteSet 不会处理 @router 里的事情。如果我们看一下 RouteSet constructor,会发现 @router 其实是 Journey::Router 的一个实例。

Journey

Journey 是 ActionDispatch 的核心路由模块。它的代码是非常有趣的,其中用到了广义状态转移图(generalized transition graph)和非确定性有限状态自动机(non-deterministic finite automata)来配对URLs和路由。

有兴趣的话可以拿出你的计算机科学与技术本科的教科书(译注:指的应是《形式语言与自动机》)复习一下!Journey 甚至还包含了一个完整的 yacc 语法文件来对 routes 进行语法分析。

Journey::Router 的 #call 方法有些长,下面是相关部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# rails/actionpack/lib/action_dispatch/journey/router.rb

module ActionDispatch
module Journey
class Router

def call(env)
find_routes(env).each do |match, parameters, route|
env[@params_key] = (set_params || {}).merge parameters
status, headers, body = route.app.call(env)
return [status, headers, body]
end
end

...

end
end
end

我们看到了和 Unicorn 中 #process_client 一样的 Rack 接口。 #find_routes 通过路由表 GTG (generalized transition graph) simulator 对URL进行执行。路由表本身是由 config/routes.rb 中规定的路由信息,构造的一个 Journey::Routes 实例,它包含了全部的路由(多个 Journey::Route 实例),个人十分推荐通过 RailsCasts #231#232来学习路由结构的更多细节。

倘若发现了匹配的路由,我们便调用与 route 相关联的 app 上的 #call 方法。只要我们现在在 Rails 源码中看到引用 app 的地方,就可以假定它是 Rack app 。其实每个 controller 中 action 的行为都和一个 Rack app 一样。与 route 相关联的 app 的初始化过程有一些 Tricky。

在构造路由表时, ActionDispatch::Routing::Mapper 类调用 add_route ,它将会构造 Journey::Route 的一个实例,与 controller endpoint —— the Rack app 相关联。

然而,在 mapper.rb 中这个类的定义有将近 2,000 行,以下是删减版的 Mapper#add_route 定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# rails/actionpack/lib/action_dispatch/routing/mapper.rb

module ActionDispatch
module Routing
class Mapper

def add_route(action, options)
path = path_for_action(action, options.delete(:path))

...

mapping = Mapping.new(@set, @scope, URI.parser.escape(path), options)
app, conditions, requirements, defaults, as, anchor = mapping.to_route
@set.add_route(app, conditions, requirements, defaults, as, anchor)
end

...

end
end
end

在这里, @set 是我们之前提到的 RouteSet ,这里的 app 其实是 ActionDispatch::Routing::Dispatcher 的一个实例。 Dispatcher 类定义在 route_set.rb 中,这是 #call 的一个简单定义。

为了说的更清楚,想象一下我们正在通过URL /posts 访问我们的博客应用,它的路由指向了 Posts Controller 的 index 方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# rails/actionpack/lib/action_dispatch/routing/route_set.rb

module ActionDispatch
module Routing
class Dispatcher

def call(env)
params = env[PARAMETERS_KEY]
prepare_params!(params)
# params = {:action=>"index", :controller=>"posts"}

controller = controller(params, @defaults.key?(:controller))
# controller = PostsController

dispatch(controller, params[:action], env)
end

...

end
end
end

在这里, controller 方法已经解析了控制器参数(比如 posts ),并且给了我们一个类(PostsController)的引用,得到了基本的参数哈希(params hash)。

现在,已经准备好了去调用控制器(controller)上的方法(aciton),来得到完整的响应(response)。以下是 dispatch 方法的定义:

1
2
3
4
5
# rails/actionpack/lib/action_dispatch/routing/route_set.rb

def dispatch(controller, action, env)
controller.action(action).call(env)
end

到这里,我们成功地将 route 映射到了一个 controller/action ,作为下一个 post 处理的请求(request)被压入ActionController工作栈。

路由是 Rails 中一个相当复杂的一个部分,他的方法链很长。像之前所说的,我们并没有必要了解它的全部细节。Rails 具有魔力的地方就是它为你隐藏了所有这些细节。当然去探索这整个执行过程到底是如何发生的是一件很有趣的事情。

译者总结:

实际上每个存在的 Controller 和 Action 的组合都是一个 Rack App ,假设它们存在于一个集合 rack_app_set 中;同时假设所有系统可接受的合法URL的集合为 URL_set 。

则路由为函数:

ƒ: URL_setrack_app_set

[Rails] 从Request到Response(1)

本文翻译自:Rails from Request to Response 系列;个人选择了自己感兴趣的部分进行翻译,需要阅读原文的同学请戳前面的链接。

第一部分 导言(Introduction)

服务器

在讲 Rails 调用栈之前,先简单介绍一下不同服务器应用的作用,其中并不会涉及到各个服务器应用(比如 Thin 和 Unicorn 或 Nginx)的细节,因为文章的重点是讲 Rails 端的一些东西。

这里举一个 Unicorn 的简单例子,管窥整个 Rails 应用。

Unicorn架构

Unicorn 是一个实现了Rack接口的服务器应用,通过多个 worker 并行处理请求(request)。启动时,主进程会将 Rails App 代码加在到内存中,随后以加载进来内存为原料进行复制,生成一定数量的 worker,并对他们进行监控和信号捕获(比如被用作关闭和重启的 QUIT,TERM,USR1 信号等等)。这些 worker 负责处理的一个个真实的 web 请求(request)。

下图是 Unicorn 的架构(这幅图片来自Github一篇很棒的文章):
Unicorn Architecture

这些 worker 从共享的 socket 中读取 HTTP 请求(request),并将它们发给 Rails 应用。随后得到响应(response),写回到共享的 socket 中。这个过程中的大部份都发生在Unicorn HttpServer 类的 #process_client 方法中,下面是相关部分的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# unicorn/lib/unicorn/http_server.rb

def process_client(client)
status, headers, body = @app.call(env = @request.read(client))

...

http_response_write(client, status, headers, body,
@request.response_start_sent)

client.shutdown
client.close
rescue => e
handle_error(client, e)
end

其中省略了一些关于HTTP 100状态处理和 Rack socket hijacking 相关的代码,感兴趣的话可以阅读完整版本

我们可以看到,这个方法的核心逻辑相当的简明!

第一行是Rack specification:Rack App 其实就是一个 Ruby Object,我们只需要为它写一个可以接受 hash 参数 env 的 #call 方法,让它的返回 [status, headers, body](译者:还不是很明白 rack 是什么鬼的同学可以去看一下这个视频,亲测好评)。

这个就是 Rails,Sinatra,Padrino 等那些兼容了Rake接口的框架的核心。回到 #process_client 方法,可以看到,我们向 @app 的 #call 方法传递 env 参数,并在 client 关闭之前,将响应(response)写回。

你没猜错,这个 @app 就是我们的 Rails 项目,我们来看他的声明:

1
2
3
4
5
6
7
# blog/config/application.rb

module Blog
class Application < Rails::Application
...
end
end

这就是 Rails 调用栈的入口,但是如果你仔细观察,你会发现 #call 并没有定义在 Blog::Application,而是被声明在了父类 Rails::Application 中。

现在开始,我们需要了解 Rails 应用的继承机制,以及一个请求(request)是如何在 Rails 内部被处理的。

Rails Application and Engines

我们之前提到,整个 Rails 应用的入口 #call 被定义在了 Rails::Application 中,我们通过继承来使用它。这里是它的定义(源码):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# rails/railties/lib/rails/application.rb

module Rails
class Application < Engine

# Implements call according to the Rack API. It simply
# dispatches the request to the underlying middleware stack.
def call(env)
env["ORIGINAL_FULLPATH"] = build_original_fullpath(env)
env["ORIGINAL_SCRIPT_NAME"] = env["SCRIPT_NAME"]
super(env)
end

...

end
end

这里并没有什么东西,大部分功能通过调用 super 来执行。如果我们跟着代码看,可以发现 Rails::Application 类继承于 Rails::Engine 类。如果你熟悉Rails engines,你会惊喜地发现,Rails::Application 就是一个超级 engine!

我们来看看 Engine 类中的 #call 方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# rails/railties/lib/rails/engine.rb

module Rails
class Engine < Railtie

def call(env)
env.merge!(env_config)
if env['SCRIPT_NAME']
env.merge! "ROUTES_#{routes.object_id}_SCRIPT_NAME" => env['SCRIPT_NAME'].dup
end
app.call(env)
end

...

end
end

所以,Engine 类继承于 Rails::Railtie 。通过观察源码,我们可以发现Railtie0是 Rails 框架的核心,他为 initializers,config keys,generators 和 rack tasks 等提供钩子方法。

所有Rails的主要部件(ActionMailer,ActionView,ActionController 和 ActiveRecord)都是一个 Railtie,这也就是为什么你可以随意拆装组合这些部件。

在 Engine 的 #call 方法中我们看到了 #call 的另一个代理方法(delegation),这里的 app 代表的是什么?在同一个文件中,我们发现了他的定义:

1
2
3
4
5
6
7
8
9
# rails/railties/lib/rails/engine.rb

# Returns the underlying rack application for this engine.
def app
@app ||= begin
config.middleware = config.middleware.merge_into(default_middleware_stack)
config.middleware.build(endpoint)
end
end

现在我们到了一个牛逼的位置。这个engine构造了一个类似Rack application的中间件,并将 #call 方法代理(delegate)给它,他的终点是我们应用的 routes,ActionDispatch::Routing::RouteSet 类的一个实例。

Rack middleware可以用来「过滤」请求(request)和响应(response),并且可以将一个请求(request)处理过程分解成多个步骤,并视为一个「管道」进行处理,比如:处理权限认证,缓存等等。

你可以通过执行 rake middleware 来列出一个应用所使用的全部中间件。这里是我对 Blog 应用执行这条指令所得到的结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
$ RAILS_ENV=production rake middleware
use Rack::Sendfile
use #<ActiveSupport::Cache::Strategy::LocalCache::Middleware:0x007f7ffb206f20>
use Rack::Runtime
use Rack::MethodOverride
use ActionDispatch::RequestId
use Rails::Rack::Logger
use ActionDispatch::ShowExceptions
use ActionDispatch::DebugExceptions
use ActionDispatch::RemoteIp
use ActionDispatch::Callbacks
use ActiveRecord::ConnectionAdapters::ConnectionManagement
use ActiveRecord::QueryCache
use ActionDispatch::Cookies
use ActionDispatch::Session::CookieStore
use ActionDispatch::Flash
use ActionDispatch::ParamsParser
use Rack::Head
use Rack::ConditionalGet
use Rack::ETag
run Blog::Application.routes

其中的大部分都不会讲,因为没有必要去了解全部这些中间件,即使一个请求(request),在到达 Blog::Application.routes 之前,会途径列表中从上到下所有的中间件。

到这里,我们已经完成了 App server / Rails application stack 的导言部分的介绍,接下来会着重介绍 Rails routing / dispatch stack。

译者总结

我们可以将 rack app 简化地表示为一个函数:

ƒ: env_set{ [status, headers, body] }

Rails app 其实就是若干个函数的嵌套,逐层对输入的 env 和返回 [status, headers, body] 进行加工。整个Rails的执行过程,不过如此。

1
env(1)env(2) → ... → env(i) → ... env(n)

令:s: [status, headers, body]

1
s(n)s(n-1) → ... → s(i) → ... s(1)

看完这篇文章后,终于理解了《Ruby社区应该去Rails化了》中这段话的意思:

Rails为何不适合做Web Service?

我发现了一个有意思的现象,最早的一批用Ruby开发Web Service服务的网站,都选择了用Rails开发,而在最近几年又不约而同抛弃Rails重写Web服务框架。当初用Rails的原因很简单,因为产品早期起步,不确定性很高,使用Rails快速开发,可以最大限度节约开发成本和时间。但为何当请求量变大以后,Rails不再适合了呢?

这主要是因为Rails本身是一个full-stack的Web框架,所有的设计目标就是为了开发Website,所以Rails框架封装过于厚重,对于需要更高性能更轻薄的Web Service应用场景来说,暴露出来了很多缺陷:

Rails调用堆栈过深,URL请求处理性能很差

Rails的设计目标是提供Web开发的 最佳实践 ,所以无论你需要不需要,Rails默认提供了开发Website所有可能的组件,但其中绝大部分你可能一辈子都用不上。例如Rails项目默认添加了20个middleware,但其中10个都是可以去掉的,我们自己的项目当中手工删除了这些middleware:

1
2
3
4
5
6
7
8
9
10
config.middleware.delete 'Rack::Cache'   # 整页缓存,用不上
config.middleware.delete 'Rack::Lock' # 多线程加锁,多进程模式下无意义
config.middleware.delete 'Rack::Runtime' # 记录X-Runtime(方便客户端查看执行时间)
config.middleware.delete 'ActionDispatch::RequestId' # 记录X-Request-Id(方便查看请求在群集中的哪台执行)
config.middleware.delete 'ActionDispatch::RemoteIp' # IP SpoofAttack
config.middleware.delete 'ActionDispatch::Callbacks' # 在请求前后设置callback
config.middleware.delete 'ActionDispatch::Head' # 如果是HEAD请求,按照GET请求执行,但是不返回body
config.middleware.delete 'Rack::ConditionalGet' # HTTP客户端缓存才会使用
config.middleware.delete 'Rack::ETag' # HTTP客户端缓存才会使用
config.middleware.delete 'ActionDispatch::BestStandardsSupport' # 设置X-UA-Compatible, 在nginx上设置

其中最夸张的是ActionDispatch::RequestIdmiddleware,只有在大型应用部署在群集环境下进行线上调试才可能用到的功能,有什么必要做成默认的功能呢? Rails的哲学是:提供最全的功能集给你,如果你用不到,你自己手工一个一个关闭掉 ,但是这样带来的结果就是默认带了太多不必要的冗余功能,造成性能损耗极大。

我们看一个Ruby web框架请求处理性能评测 ,这个评测不访问数据库,也不测试并发性能,主要是测试框架处理URL请求路由,渲染文本,返回结果的处理速度。

Rack: 1570.43 request/s
Campig: 1166.16 request/s
Sinatra: 912.81 request/s
Padrino: 648.68 request/s
Rails: 291.27 request/s

Sinatra至少是Rails速度的3倍以上。

人类误判心理(2)

作者:查理·芒格

My second factor is simple psychological denial.

第二条:单纯的心理学上的「否定」

This first really hit me between the eyes when a friend of our family had a super-athlete, super-student son who flew off a carrier in the north Atlantic and never came back, and his mother, who was a very sane woman, just never believed that he was dead. And, of course, if you turn on the television, you’ll find the mothers of the most obvious criminals that man could ever diagnose, and they all think their sons are innocent. That’s simple psychological denial. The reality is too painful to bear, so you just distort it until it’s bearable. We all do that to some extent, and it’s a common psychological misjudgment that causes terrible problems.

译者:一则小故事,不作具体翻译。了解「精神分析」理论的同学肯定都知道,其实说的就是所谓「心理防卫机制」中的「否认」[1]。借此机会向大家推荐「心理防卫机制」,希望可以帮助各位更加了解自己。鉴于有些同学无法访问维基百科,将原文复制了一份过来。

人类误判心理(1)

作者:查理·芒格(伯克夏·哈撒韦公司董事会副主席,沃伦·巴菲特的搭档)

本文是作者1995年在哈佛法学院的演讲 原文链接

First: Under-recognition of the power of what psychologists call ‘reinforcement’ and economists call ‘incentives.’

第一条:低估 心理学家所谓的「强化」 / 经济学家所谓的「激励」的 效果。

Well you can say, “Everybody knows that.” Well I think I’ve been in the top 5% of my age cohort all my life in understanding the power of incentives, and all my life I’ve underestimated it. And never a year passes but I get some surprise that pushes my limit a little farther.

好吧,你们可能说俺们都知道,然而你们知道的那些并没有什么卵用。老子是俺们这辈人里最了解「激励」的人之一,我这大半辈子还都低估了它有多屌,甚至到现在老子每年还老丁[1]能在这玩意上学到新东西,得到新惊喜。

One of my favorite cases about the power of incentives is the Federal Express case. The heart and soul of the integrity of the system is that all the packages have to be shifted rapidly in one central location each night. And the system has no integrity if the whole shift can’t be done fast. And Federal Express had one hell of a time getting the thing to work. And they tried moral suasion, they tried everything in the world, and finally somebody got the happy thought that they were paying the night shift by the hour, and that maybe if they paid them by the shift, the system would work better. And lo and behold, that solution worked.

俺最喜欢的一个关于「激励」的案例来自联邦快递:对这家公司来说,最重要的就是在每天夜里,包裹必须从一个中央位置被快速地转运出去。而且,如果不足够快的话,这个系统基本上就屁用不顶了。之前该公司就经常被这事折磨得欲仙欲死。他们试着和快递员小哥儿们进行道德教育,和其他所有能想到的奇奇怪怪的方法,然而并没有什么卵用。最后有个人想出了一招,按小时给晚班工人计费。如果给小哥儿们按照轮班发钱,这个系统就更好地运转起来了。你看,这回牛逼了吧。

Early in the history of Xerox, Joe Wilson, who was then in the government, had to go back to Xerox because he couldn’t understand how their better, new machine was selling so poorly in relation to their older and inferior machine. Of course when he got there he found out that the commission arrangement with the salesmen gave a tremendous incentive to the inferior machine.

在Xerox公司的早期,Joe Wilson这货从他的政府工作上回到Xerox,因为他不知道为啥更牛逼的新机器比渣渣的旧机器卖的还差。妈蛋的,他发现销售人员的佣金制度竟然鼓励他们卖老机器!!!

And here at Harvard, in the shadow of B.F. Skinner — there was a man who really was into reinforcement as a powerful thought, and, you know, Skinner’s lost his reputation in a lot of places, but if you were to analyze the entire history of experimental science at Harvard, he’d be in the top handful. His experiments were very ingenious, the results were counterintuitive, and they were important. It is not given to experimental science to do better. What gummed up Skinner’s reputation is that he developed a case of what I always call man-with-a-hammer syndrome: to the man with a hammer, every problem tends to look pretty much like a nail. And Skinner had one of the more extreme cases in the history of Academia, and this syndrome doesn’t exempt bright people. It’s just a man with a hammer…and Skinner is an extreme example of that. And later, as I go down my list, let’s go back and try and figure out why people, like Skinner, get man-with-a-hammer syndrome.

在哈尔滨服装学院,有一个叫B.F. Skinner的人,真的视「强化」为一个强有力的思维模式。他在很多地方都名誉受损,不过从哈佛实验科学的历史上看,他算是很屌的了。他的实验很有创造性,实验结果也是反直觉而且重要的。他没能将实验科学做的更好。我经常称将他名誉搞差的原因叫做「王大锤综合征」:对于手里拿着锤子的同学来说,所有问题都像钉子。斯金纳是学术史上的一个极端案例,然而有些明白人也会有这个问题。我先按我本儿上接着说,等会再说为啥大家会得「王大锤综合症」。

Incidentally, when I was at the Harvard Law School there was a professor, naturally at Yale, who was derisively discussed at Harvard, and they used to say, “Poor old Blanchard. He thinks declaratory judgments will cure cancer.” And that’s the way Skinner got. And not only that, he was literary, and he scorned opponents who had any different way of thinking or thought anything else was important. This is not a way to make a lasting reputation if the other people turn out to also be doing something important.

Btw,我当年在哈佛法学院的时候,有一个教授,他认为宣告判决将治愈癌症,就像Skinner一样。不止如此,他精通文学,经常嘲讽和自己有不同想法的对手。这绝壁不是个维系持久名誉的方法(我擦,这段好难翻译。因为是演讲,可能是作者随便说些有的没的。


[1] 老丁:经常的意思;例句:王雪冰常说:“我老丁(经常)找老丁(丁麒玮)玩,老丁(丁麒玮)老丁(经常)不出来。”

并发模型:线程与锁模型

互斥和内存模型

互斥:用锁保证某一时间仅有一个线程可以访问数据;
可能带来的麻烦:竞态条件和死锁。

线程

并发的基本单元:线程,可以讲线程看做控制流;
线程间通信方式:共享内存。

1
2
3
4
5
6
7
8
9
10
11
def say_hi(name)
puts "Hi #{name}!"
end

def say_hi_to_folks(folks)
folks.inject([]) do |threads_array, name|
threads_array << Thread.new { say_hi(name) }
end.each(&:join)
end

say_hi_to_folks %w(Larry Jack)

执行结果有可能是

1
2
Hi Larry!
Hi Jack!

或者是

1
2
Hi Jack!
Hi Larry!

多线程的运行结果依赖于时序,多次运行结果并不稳定。

*注:这里使用 Jruby(基于 JVM),两个线程分别为主线程和子线程,由于 Ruby 中没有相对应的「让出线程」方法 Thread.yield() ,而在 Ruby 中相接近的 Thread.pass 实验效果又很差,故而改由两个子线程举例(为啥要用JRuby? 因为不用编译)

锁儿

多个线程共享内存时,避免同时修改同一个部分内存造成的问题,需要用达到线程互斥的目的。某一时间,至多有一个线程持有锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 class Counter
def initialize
@count = 0
end
def increment
@count += 1
end
def count
@count
end
end
counter = Counter.new

def thread(counter)
10_000.times { counter.increment }
end

t1 = Thread.new { thread(counter) }
t2 = Thread.new { thread(counter) }

[t1, t2].each(&:join)
puts counter.count

执行结果

1
2
3
4
5
6
➜  /private/tmp ruby:(system: jruby 1.7.19)
$ ruby test.rb
13779
➜ /private/tmp ruby:(system: jruby 1.7.19)
$ ruby test.rb
16440

这段代码创建了一个 counter 对象和两个线程,每个线程调用 counter.increment 10,000次。这段代码看上去很简单,但很脆弱。

几乎每次运行都将获得不同的结果,产生这个结果的原因是两个线程使用 counter.count 时发生了竞态条件(即代码行为取决于各操作的时序)

我们来看一下 JVM 是如何解释 ++count 的。其字节码:

1
2
3
4
getfield #2 ;//获取count的值
iconst_1 ;//设置加数
iadd ;//count加设置好的加数
putfield #2 ;//将更新的值写回count

这就是通称的读-改-写模式。

如果两个线程同时调用 increment ,线程1执行 getfield #2 ,获取值42。在线程1执行其他动作之前,线程2也执行了 getfield #2 ,获得值42。不过,现在两个线程都将获得的值加1,将43写回count中。导致 count 只被增加了一次。

竞态条件的解决方案:对 count 进行同步(synchronize)访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Counter
attr_reader :count
def initialize
@count = 0
@counter_mutex = Mutex.new
end

def increment
@counter_mutex.synchronize { @count += 1 }
end
end

def thread(counter)
10_000.times { counter.increment }
end

counter = Counter.new
t1 = Thread.new { thread(counter) }
t2 = Thread.new { thread(counter) }

[t1, t2].each(&:join)
puts counter.count

执行结果

1
2
3
➜  /private/tmp ruby:(system: jruby 1.7.19)
$ ruby test.rb
20000

线程进入 increment 方法时,获得 counter_mutex 锁,函数返回的时候释放该锁。同一时间最多有一个进程可以执行函数体,其他线程调用方法时将被阻塞,直到锁被释放。

优化的副作用

What is the meaning of my life?

由于没有通读过Ruby源码,无法确定这个Bug是否能用Ruby来复现,先用Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Puzzle {
static boolean answerReady = false;
static int answer = 0;
static Thread t1 = new Thread() {
public void run() {
answer = 42;
answerReady = true;
}
};
static Thread t2 = new Thread() {
public void run() {
if (answerReady)
System.out.println("The meaning of life is: " + answer);
else
System.out.println("I don't know the answer");
}
};
public static void main(String[] args) throws InterruptedException {
t1.start(); t2.start();
t1.join(); t2.join();
}
}

根据线程执行的时序,这段代码的输出可能是:

1
The meaning of life is: 42

或者是

1
I don't know the answer

但是还有一种结果可能是:

1
The meaning of life is: 0

这说明了,当 answerReady 为 true 时 answer 可能为0!

就好像第六行和第七行颠倒了执行顺序。但是乱序执行是完全可能发生的:

  1. 编译器的静态优化可以打乱代码的执行顺序(编译原理)
  2. JVM的动态有话也会打乱代码的执行顺序(JVM)
  3. 硬件可以通过乱序执行来优化其性能(计算机体系结构)

比乱序执行更糟糕的时,有时一个线程产生的修改可能对另一个线程不可见,

如果讲 run() 写成:

1
2
3
4
5
public void run() {
while (!answerReady)
Thread.sleep(100);
System.out.println("The meaning of life is: " + answer);
}

answerReady 可能不会变成 true 代码运行后无法退出。

显然,我们需要一个明确的标准来告诉我们,优化会产生什么副作用影响,这就是 Java 内存模型(其他语言应该也有类似的东西)。Btw,经过本天才的多次试验,Ruby这边可以复现啦!!!

复现代码:

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
require 'singleton'  

class Puzzle
include Singleton

def initialize
@answer_ready = false
@answer = 0
end

def thread1
Thread.new do
@answer = 'eat'
@answer_ready = true
end
end

def thread2
Thread.new do
meaning_of_life = "The meaning of life is: #{@answer}"
no_answer = "I don't know the answer"
puts @answer_ready ? meaning_of_life : no_answer
end
end

def main
[thread1, thread2].each(&:join)
end
end

Puzzle.instance.main

实验过程:

1
2
3
4
5
6
#!/bin/bash

while [ "$result" != "The meaning of life is: 0" ]; do
result="$(ruby test.rb)"
echo $result
done

实验结果:

1
2
3
4
5
6
7
8
9
➜  /tmp ruby:(system: ruby 2.1.5p273)
$ sh test.sh
The meaning of life is: eat
The meaning of life is: eat
I don't know the answer
The meaning of life is: eat
I don't know the answer
I don't know the answer
The meaning of life is: 0

内存可见性

Java 内存模型定义了何时一个线程对内存的修改对另一个线程可见。基本原则是,如果读线程和写线程不进行同步,就不能保证可见性。

除了 increment 之外, count 的 getter 方法也需要进行同步。否则 count 方法可能获得一个失效的值:对于前面交互的两个线程, conter 在 join 之后调用因此是线程安全的。但这种设计为其他调用 conter 的方法埋下了隐患。

所以,「竞态条件」和「内存可见性」都可能让多线程程序运行结果出错。除此之外,还有一类问题:「死锁」。

推荐阅读

深入理解Java内存模型系列
内存可见性

哲学家用餐问题(Dining philosophers problem)

简单来说:有五个哲学家坐在一张圆桌上,每个人之间放着一只餐叉,这样桌上就有五只餐叉。哲学家只会做两件事,吃饭,或者思考。吃东西的时候,他们就停止思考,思考的时候也停止吃东西。
来自Wikipedia

是的,他们每个人都会用到别人用过的餐叉,开不开心。

这个例子一般用来说明死锁问题,经典的场景之一:一名哲学家拿起了自己左手的餐叉,并为其加锁(以免同时被自己左边的哲学家拿到),而后等待自己右手的餐叉锁的释放。

然而,如果五个哲学家同时处于这个状态,就会死锁。

举个栗子:
Chopstick.java

1
2
class Chopstick {
}

Philosopher.java

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
import java.util.Random;

class Philosopher extends Thread {
private int id;
private Chopstick left, right;
private Random random;

public Philosopher(Chopstick left, Chopstick right, int id) {
this.left = left; this.right = right; this.id = id;
random = new Random();
}

public void run() {
try {
while (true) {
Thread.sleep( random.nextInt(1000) ); // Think for a while
synchronized (left) { // Grab left chopstick
System.out.println("Philosopher#" + id + " take left Chopstick");

synchronized (right) { // Grab right chopstick
System.out.println("Philosopher#" + id + " take right Chopstick");
Thread.sleep( random.nextInt(1000) ); // Eat for a while
}
System.out.println("Philosopher#" + id + " put right chopsticks");
}
System.out.println("Philosopher#" + id + " put left chopsticks");
}
} catch (InterruptedException e) {}
}
}

DiningPhilosophers.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Random;

public class DiningPhilosophers {

public static void main(String[] args) throws InterruptedException {
Philosopher[] philosophers = new Philosopher[5];
Chopstick[] chopsticks = new Chopstick[5];

for (int i = 0; i < 5; ++i)
chopsticks[i] = new Chopstick();

for (int i = 0; i < 5; ++i) {
philosophers[i] = new Philosopher(chopsticks[i], chopsticks[(i + 1) % 5], i);
philosophers[i].start();
}

for (int i = 0; i < 5; ++i)
philosophers[i].join();
}
}

这个栗子属于可以锁得死死的那种。

因为全局的多个代码块可能会共同使用一些锁,所以我们可以通过为所有的锁添加一个偏序关系,来避免死锁状态的产生。

Philosopher.java

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
class Philosopher extends Thread {
private int id;
private Chopstick first, secound;
private Random random;

public Philosopher(Chopstick left, Chopstick right, int id) {
this.id = id;
if (left.getId() < right.getId()) {
this.first = left; this.second = right;
} else {
this.first = right; this.second = left;
}
random = new Random();
}
public void run() {
try {
while (true) {
Thread.sleep(random.nextInt(1000));
synchronized(first) {
System.out.println("Philosopher#" + id + " take Chopstick#" + first.getId());

synchronized(second) {
System.out.println( "Philosopher#" +
id +" take Chopstick#" + second.getId() );
Thread.sleep( random.nextInt(1000) );
}
System.out.println("Philosopher#" + id + " put Chopstick#" + second.getId());
}
System.out.println("Philosopher#" + id + " put Chopstick#" + first.getId());
}
} catch (InterruptedException e) {}
}
}

外星方法

这里我们构造有一个类从一个URL进行下载, 用 ProgressListeners 监听下载速度

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
class Downloader extends Thread {
private InputStream in;
private OutputStream out;
private ArrayList<ProgressListener> listeners;

public Downloader(URL url, String outputFilename) throws IOException {
in = url.openConnect().getInputSteam();
out = new FileOutputStream(outputFilename);
listeners = new ArrayList<ProgressListener>();
}

public synchronized void addListener(ProgressListener listener) {
listeners.add(listener);
}

public synchronized void removeListener(ProgressListener listener) {
listeners.remove(listener);
}

private synchronized void updateProgress(int n) {
for (ProgressListener listener: listeners)
listener.onProgress(n);
}

public void run() {
int n = 0, total = 0;
byte[] buffer = new byte[1024];

try {
while ( (n = in.read(buffer)) != -1 ) {
out.write(buffer, 0, n);
total += n;
updateProgress(total);
}
out.flush();
} catch (IOException e) {}
}
}

未完待续

Reference

《七周七并发模型》

LeetCode: Longest Substring Without Repeating Characters 解题报告

题目描述:
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.


分析:找到最长的不包含相同字母的字串

题解:用一个队列来存储不含相同字母的子串,用一个hash来标记队列中已经使用过的字符。

  1. 当发现即将入队的字符未被使用过时,入队,并在hash中标记下来;
  2. 当发现即将入队的字符已经被使用过时,记下当前队列中字串的长度,取其与历史最大长度之间的最大值作为新的解。之后将队首的字符逐一出队,并在hash中清除标记,直道清除了即将入队的字符为止,最后字符入队。
  3. 循环这个过程,直到所有的字符都被处理完成。
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
class Solution {
public:
int lengthOfLongestSubstring(string s) {
queue<char> current_sub_str;
int sub_string_max_length = 0;

for (auto it = s.begin() ; it < s.end(); it++) {
char current_alphabet = *it;

if (isAlphabetExist(current_alphabet)) {
syncMaxValue( sub_string_max_length, current_sub_str.size() );
popSubStringUntilAlphabet( current_alphabet, current_sub_str );
} else {
markAlphabet(current_alphabet);
}

current_sub_str.push(current_alphabet);
}
syncMaxValue( sub_string_max_length, current_sub_str.size() );
return sub_string_max_length;
}
private:
static const int SIZE_OF_ASCII = 128;
bool alphabet_flag[SIZE_OF_ASCII] = { false };

bool isAlphabetExist(const char alphabet) const {
return alphabet_flag[int(alphabet)];
}
void syncMaxValue(int &sub_string_max_length, const size_t current_sub_string_length) const {
if (current_sub_string_length > sub_string_max_length) {
sub_string_max_length = int(current_sub_string_length);
}
}
void popSubStringUntilAlphabet(const char alphabet, queue<char> &current_sub_str) {
for ( char current_alphabet = current_sub_str.front(); current_alphabet != alphabet;
alphabet_flag[int(current_alphabet)] = false,
current_sub_str.pop(),
current_alphabet = current_sub_str.front()
);
current_sub_str.pop();
}
void markAlphabet(const char alphabet) {
alphabet_flag[int(alphabet)] = true;
}
};