(learn&think)

不浮躁,不自傲,学习,思考,总结

Make Colorful Equations With Mathjax

| Comments

其中, $\mu$ 是分布的均值或期望值, 而 $\sigma$ 是它的标准差, $\sigma^2$ 则是方差.

浅谈C++11 Multithreading Programming

| Comments

Overview

上一篇浅谈 C++ Multithreading Programming主要介绍时下规范好的 C++使用 Pthread 库和 Boost Thread 库实现 C++多线程编程.这里主要谈谈正在规范的 C++11 引入的 Thread 库和 Atomic 库,终于自带的 C++库能支持高效并可移植的 Multithreading 编程.分为 2 篇,这里先谈谈 C++11 的Thread 的库 (并包含对 C 的支持), 后一篇谈谈 C++11 的Atomic 操作的库.

C++11(之前被成为 C++0x)是编程语言 C++最新版本的标准.它由 ISO 在 2011 年 8 月 12 日被批准替代C++03. C++11 标准正在规范中,从ISO 页面 可以知道如何获得进行中的草稿:

所以本文:

更多有关 C++参考最后的其他资料.

浅谈C++ Multithreading Programming

| Comments

Overview

随着多核 CPU 随处可见,多线程(multithreading)可以被用来实现并行,提高 CPU 的利用率和性能显著的提高.掌握多线程编程也成为现代实现软件的基本要求技能之一.Introduction to Parallel Computing详细的介绍了 Parallel Computing; 为什么使用它;Parallel Computing 的分类;Parallel Computing 的 limits 和 costs; Parallel Computing 的程序模型;如何设计 Parallel 程序等.

这里先介绍多线程的概念,多线程中涉及的基本概念,然后用实例介绍 Pthread 库的使用,并介绍 Google Code 中如何把它封装成 C++类,最后介绍可移植并大量使用的 Boost Thread 库.

还有一些其他的 Thread 库:

Multithreading相关术语总结

| Comments

在谈到内存模型,Multithreading,尤其 lock-free programmming 等时,总会遇到一些相关术语来描述,如 Memory Barrier,Acquire semantics,Release semantics,happens-before relation 等.在这里稍微整理一下.

浅谈Mutex (Lock)

| Comments

Mutex(又叫 Lock),在多线程中,作为同步的基本类型,用来保证没有两个线程或进程同时在他们的关键区域.因为 Mutex 这种排它性,很多人认为 Mutex 开销很大,尽量避免使用它.就如这篇分析完共享数据问题后,进一步分析说明 Avoiding locks 来解决这个问题.但 Mutex 真的开销如此大,还是被大家误解了?Matthew Dillon 写道,”Most people have the misconception that locks are slow.”, Jeff Preshing 也 写了这篇”Locks Aren’t Slow; Lock Contention Is”.

那么接下来做 3 个关于 Mutex 的 Benchmark,具体分析一下 Mutex 的开销如何,最后并利用原子操作和 semaphore 实现一个 lightweight Mutex.

浅谈Memory Reordering

| Comments

Memory ordering

在我们编写的 C/C++代码和它被在 CPU 上运行,按照一些规则,代码的内存交互会被乱序.内存乱序同时由编译器(编译时候)和处理器(运行时)造成,都为了使代码运行的更快.

被编译开发者和处理器制造商遵循的中心内存排序准则是:

不能改变单线程程序的行为.

因为这条规则,在写单线程代码时内存乱序被普遍忽略.即使在多线程程序中,它也被时常忽略,因为有 mutexes,semaphores 等来防止它们调用中的内存乱序.仅当 lock-free 技术被使用时,内存在不受任何互斥保护下被多个线程共享,内存乱序的影响能被看到.

下面先比较 Weak 和 Strong 的内存模型,然后分两部分,实际内存乱序如何在编译和运行时发生,并如何防止它们.

High Resolution Time

| Comments

在不同的平台有繁多的 Time API,如何选用精准的高精度 Time 函数来做 performance benchmarking 呢?

Wall-clock time VS CPU time

先理解一些时间的概念。明白不同时间 API 测量的是什么时间。

Wall-clock time,顾名思义,墙上的钟,代表一个任务从开始到完成所经历的时间。它包含 3 部分:CPU 的时间,I/O 的时间和通信延迟的时间。但 wall-clock 很少是正确的时钟来使用,因为它随着时区,和 daylightsaving 改变,或与 NTP 同步。而这些特性没有一个是有益的,如果你用它来调度任务或做 performance benchmarking。它仅仅如名字所言,墙上的一个时钟。

CPU time 仅仅统计一个任务从开始到完成在 CPU 上所花的时间。CPU time 主要包括 User time(在 user space 所花时间)和 System time(在 kernel space 所花时间)。

以并行程序为例,CPU time 就是所有 CPU 在这个程序所花的时间总和, Wall-clock time 在这种情况可能时间相对短,它只统计任务开始到结束所花时间。

Double-Checked Locking Works in C++11

| Comments

浅谈设计模式六: 单例模式(Singleton) 中提到 double-checked locking pattern(DCLP)来实现 Singleton 设计模式,但是在 C++11 之前,没有安全方法在可移植的 C++中去实现它.具体原因可见 单例模式(Singleton) 或 Scott Meyers 和 Andrei Alexandrescu 发布的原文 “C++ and the Perils of Double-Checked Locking”

C++11 引入了新的内存模型和线程库,使得能在 C++中实现可移植的 DCLP.本文说明如何实现它.

Algorithm Design Manual Chapter 6

| Comments

Book Notes

6.1 Minimum Spanning Trees

6.1.1 Prim’s Algorithm

A greedy algorithm suffices for correctness: we always add the lowest-weight edge linking a vertex in the tree to a vertex on the outside. (选取相邻最近的不在树内的点。)

Algorithm Design Manual Chapter 5

| Comments

Book Notes

5.1 Flavors of Graphs

  • Undirected vs. Directed
  • Weighted vs. Unweighted
  • Simple vs. Non-simple
  • Sparse vs. Dense
  • Cyclic vs. Acyclic
  • Embedded vs. Topological
  • Implicit vs. Explicit
  • Labeled vs. Unlabeled