程序设计 | 宝酷 - sou-ip

7个示例科普CPU Cache

2013年07月30日 Leo 评论 73 条评论 116,090 人阅读

（感谢网友 @我的上铺叫路遥 翻译投稿）

CPU cache一直是理解计算机体系架构的重要知识点，也是并发编程设计中的技术难点，而且相关参考资料如同过江之鲫，浩瀚繁星，阅之如临深渊，味同嚼蜡，三言两语难以入门。正好网上有人推荐了微软大牛Igor Ostrovsky一篇博文《漫游处理器缓存效应》，文章不仅仅用7个最简单的源码示例就将CPU cache的原理娓娓道来，还附加图表量化分析做数学上的佐证，个人感觉这种案例教学的切入方式绝对是俺的菜，故而忍不住贸然译之，以飨列位看官。

原文地址：Gallery of Processor Cache Effects

大多数读者都知道cache是一种快速小型的内存，用以存储最近访问内存位置。这种描述合理而准确，但是更多地了解一些处理器缓存工作中的“烦人”细节对于理解程序运行性能有很大帮助。

在这篇博客中，我将运用代码示例来详解cache工作的方方面面，以及对现实世界中程序运行产生的影响。

下面的例子都是用C#写的，但语言的选择同程序运行状况以及得出的结论几乎没什么影响。

示例1：内存访问和运行

你认为相较于循环1，循环2会运行多快？

int[] arr = new int[64 * 1024 * 1024];

// Loop 1
for (int i = 0; i < arr.Length; i++) arr[i] *= 3;

// Loop 2
for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

…

阅读全文 Read More

(55 人打了分，平均分： 4.00 )

二叉树迭代器算法

2013年07月14日 Todd 评论 54 条评论 46,959 人阅读

（感谢 @文艺复兴记（todd）投递此文）

二叉树(Binary Tree)的前序、中序和后续遍历是算法和数据结构中的基本问题，基于递归的二叉树遍历算法更是递归的经典应用。

假设二叉树结点定义如下：

// C++
struct Node {
    int value;
    Node *left;
    Node *right;
}

中序递归遍历算法：

// C++
void inorder_traverse(Node *node) {
    if (NULL != node->left) {
        inorder_traverse(node->left);
    }
    do_something(node);
    if (NULL != node->right) {
        inorder_traverse(node->right);
    }
}

前序和后序遍历算法类似。

但是，仅有遍历算法是不够的，在许多应用中，我们还需要对遍历本身进行抽象。假如有一个求和的函数sum，我们希望它能应用于链表，数组，二叉树等等不同的数据结构。这时，我们可以抽象出迭代器(Iterator)的概念，通过迭代器把算法和数据结构解耦了，使得通用算法能应用于不同类型的数据结构。我们可以把sum函数定义为：

…

阅读全文 Read More

(25 人打了分，平均分： 3.04 )

IoC/DIP其实是一种管理思想

2013年07月05日宝酷评论 66 条评论 74,106 人阅读

关于IoC的的概念提出来已经很多年了，其被用于一种面象对像的设计。我在这里再简单的回顾一下这个概念。我先谈技术，再说管理。

话说，我们有一个开关要控制一个灯的开和关这两个动作，最常见也是最没有技术含量的实现会是这个样子：

然后，有一天，我们发现需要对灯泡扩展一下，于是我们做了个抽象类：

但是，如果有一天，我们发现这个开关可能还要控制别的不单单是灯泡的东西，我们就发现这个开关耦合了灯泡这种类别，非常不利于我们的扩展，于是反转控制出现了。

就像现实世界一样，造开关的工厂根本不关心要控制的东西是什么，它只做一个开关应该做好的事，就是把电接通，把电断开（不管是手动的，还是声控的，还是光控，还是遥控的），而我们的造各种各样的灯泡（不管是日关灯，白炽灯）的工厂也不关心你用什么样的开关，反正我只管把灯的电源接口给做出来，然后，开关厂和电灯厂依赖于一个标准的通电和断电的接口。于是产生了IoC控制反转，如下图：

…

阅读全文 Read More

(36 人打了分，平均分： 3.83 )

Javascript 装载和执行

2013年06月05日宝酷评论 104 条评论 109,219 人阅读

一两个月前在淘宝内网里看到一个优化Javascript代码的竞赛，发现有不少的人对Javascript的执行和装载的基础并不懂，所以，从那天起我就想写一篇文章，但一直耽搁了。自上篇《浏览器渲染原理简介》，正好也可以承前启后。

首先，我想说一下Javascript的装载和执行。通常来说，浏览器对于Javascript的运行有两大特性：1）载入后马上执行，2）执行时会阻塞页面后续的内容（包括页面的渲染、其它资源的下载）。于是，如果有多个js文件被引入，那么对于浏览器来说，这些js文件被被串行地载入，并依次执行。

因为javascript可能会来操作HTML文档的DOM树，所以，浏览器一般都不会像并行下载css文件并行下载js文件，因为这是js文件的特殊性造成的。所以，如果你的javascript想操作后面的DOM元素，基本上来说，浏览器都会报错说对象找不到。因为Javascript执行时，后面的HTML被阻塞住了，DOM树时还没有后面的DOM结点。所以程序也就报错了。

传统的方式

所以，当你写在代码中写下如下的代码：

<script type="text/javascript"
        src="https://sou-ip.com/asyncjs/alert.js"></script>

…

阅读全文 Read More

(66 人打了分，平均分： 4.27 )

无锁HashMap的原理与实现

2013年05月30日 onetwogoo 评论 35 条评论 71,352 人阅读

(本文由onetwogoo投稿)

在《疫苗：Java HashMap的死循环》中，我们看到，java.util.HashMap并不能直接应用于多线程环境。对于多线程环境中应用HashMap，主要有以下几种选择：

使用线程安全的java.util.Hashtable作为替代。
使用java.util.Collections.synchronizedMap方法，将已有的HashMap对象包装为线程安全的。
使用java.util.concurrent.ConcurrentHashMap类作为替代，它具有非常好的性能。

而以上几种方法在实现的具体细节上，都或多或少地用到了互斥锁。互斥锁会造成线程阻塞，降低运行效率，并有可能产生死锁、优先级翻转等一系列问题。

CAS(Compare And Swap)是一种底层硬件提供的功能，它可以将判断并更改一个值的操作原子化。关于CAS的一些应用，《无锁队列的实现》一文中有很详细的介绍。

Java中的原子操作

在java.util.concurrent.atomic包中，Java为我们提供了很多方便的原子类型，它们底层完全基于CAS操作。

例如我们希望实现一个全局公用的计数器，那么可以：

private AtomicInteger counter = new AtomicInteger(3);

public void addCounter() {
    for (;;) {
        int oldValue = counter.get();
        int newValue = oldValue + 1;
        if (counter.compareAndSet(oldValue, newValue))
            return;
    }
}

…

阅读全文 Read More

(30 人打了分，平均分： 3.40 )

浏览器的渲染原理简介

2013年05月22日宝酷评论 157 条评论 212,193 人阅读

看到这个标题大家一定会想到这篇神文《How Browsers Work》，这篇文章把浏览器的很多细节讲得很细，而且也被翻译成了中文。为什么我还想写一篇呢？因为两个原因，

1）这篇文章太长了，阅读成本太大，不能一口气读完。

2）花了大力气读了这篇文章后可以了解很多，但似乎对工作没什么帮助。

所以，我准备写下这篇文章来解决上述两个问题。希望你能在上班途中，或是坐马桶时就能读完，并能从中学会一些能用在工作上的东西。

浏览器工作大流程

废话少说，先来看个图：

从上面这个图中，我们可以看到那么几个事：

…

阅读全文 Read More

(72 人打了分，平均分： 4.35 )

疫苗：Java HashMap的死循环

2013年05月10日宝酷评论 184 条评论 352,619 人阅读

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障，并且这个事发生了很多次，原因是在Java语言在并发情况下使用HashMap造成Race Condition，从而导致死循环。这个事情我4、5年前也经历过，本来觉得没什么好写的，因为Java的HashMap是非线程安全的，所以在并发下必然出现问题。但是，我发现近几年，很多人都经历过这个事（在网上查“HashMap Infinite Loop”可以看到很多人都在说这个事）所以，觉得这个是个普遍问题，需要写篇疫苗文章说一下这个事，并且给大家看看一个完美的“Race Condition”是怎么形成的。

问题的症状

从前我们的Java代码因为一些原因使用了HashMap这个东西，但是当时的程序是单线程的，一切都没有问题。后来，我们的程序性能有问题，所以需要变成多线程的，于是，变成多线程后到了线上，发现程序经常占了100%的CPU，查看堆栈，你会发现程序都Hang在了HashMap.get()这个方法上了，重启程序后问题消失。但是过段时间又会来。而且，这个问题在测试环境里可能很难重现。

我们简单的看一下我们自己的代码，我们就知道HashMap被多个线程操作。而Java的文档说HashMap是非线程安全的，应该用ConcurrentHashMap。

但是在这里我们可以来研究一下原因。

…

阅读全文 Read More

(207 人打了分，平均分： 4.68 )

从面向对象的设计模式看软件设计

2013年02月01日宝酷评论 93 条评论 100,154 人阅读

前些天发了一篇《如此理解面向对象编程》的文章，然后引起了大家的热议。然后我在微博上说了一句——“那23个经典的设计模式和OO半毛钱关系没有，只不过人家用OO来实现罢了……OO的设计模式思想和Unix的设计思想基本没什么差别”，结果引来了一点点争议。所以，我写下这篇文章把我的观点说明一下。我希望这样可以让大家更容易地理解什么是设计模式。我顺便帮OO和 Unix/Linux搞搞基。

什么是模式

在正式说明GoF的那23个经典的设计模式其实和OO关系不大并和Unix的设计思想很相似的这个观点之前，让我先来说说什么是模式？设计模式的英文是Design Pattern，模式是Pattern的汉译。所谓Pattern就是一种规则，或是一种模型，或是一种习惯。Pattern这个东西到处都是，并不只有技术圏子里才有。比如：

文章有文章的Pattern。如新闻有新闻的Pattern（第一段话简述了整个新闻），诗歌总是抒情的，论文总是死板的，讲稿总是高谈的，漫画总是幽默的，……
小说有小说的Pattern。比如，
- 武侠小说必然要整个武林大会，整几个NB的武功和大师，分个正派和反派，还有一个或数个惊天阴谋，坏人总是要在一开始占尽优势，好人总是要力挽狂澜……
- 言情小说总是要有第三者，总是要有负心人，里面的女子总是要哭得死去活来，但又痴心不改，……
新闻联播的模式是：头10分钟领导很忙，中间10分钟人民很幸福，后10分钟国外很乱。中国政府官方宣传稿也模式也很明显，各种赞美，口号，胜利，总是要坚持个什么，团结个什么，迈向个什么，某某精神，某某思想，群众情绪稳定，不明真相，等等……
春节的模式是，回家，吃饺子，放个鞭炮，给压岁钱，同学聚会…… 同学聚会的模式基本上都是在饭桌上回忆一下校园时光，比较一下各自的当前处境，调戏一下女同学……
…… ……

这就是Pattern，只要你细心观察，你会发现这世间有很多很多的Pattern。

…

阅读全文 Read More

(52 人打了分，平均分： 4.12 )

如此理解面向对象编程

2012年12月13日宝酷评论 185 条评论 183,212 人阅读

从Rob Pike 的 Google+上的一个推看到了一篇叫《Understanding Object Oriented Programming》的文章，我先把这篇文章简述一下，然后再说说老牌黑客Rob Pike的评论。

先看这篇教程是怎么来讲述OOP的。它先给了下面这个问题，这个问题需要输出一段关于操作系统的文字：假设Unix很不错，Windows很差。

这个把下面这段代码描述成是Hacker Solution。（这帮人觉得下面这叫黑客？我估计这帮人真是没看过C语言的代码）

public class PrintOS
{
	public static void main(final String[] args)
	{
		String osName = System.getProperty("os.name") ;
		if (osName.equals("SunOS") || osName.equals("Linux"))
		{
			System.out.println("This is a UNIX box and therefore good.") ;
		}
		else if (osName.equals("Windows NT") || osName.equals("Windows 95"))
		{
			System.out.println("This is a Windows box and therefore bad.") ;
		}
		else
		{
			System.out.println("This is not a box.") ;
		}
	}
}

然后开始用面向对象的编程方式一步一步地进化这个代码。

先是以过程化的思路来重构之。

…

阅读全文 Read More

(63 人打了分，平均分： 4.25 )

Go 语言简介（下）— 特性

2012年11月07日宝酷评论 96 条评论 110,351 人阅读

希望你看到这篇文章的时候还是在公交车和地铁上正在上下班的时间，我希望我的这篇文章可以让你利用这段时间了解一门语言。当然，希望你不会因为看我的文章而错过站。呵呵。

如果你还不了解Go语言的语法，还请你移步先看一下上篇——《Go语言简介（上）：语法》

goroutine

GoRoutine主要是使用go关键字来调用函数，你还可以使用匿名函数，如下所示：

…

阅读全文 Read More

(35 人打了分，平均分： 4.23 )

宝酷 – sou-ip

享受编程和技术所带来的快乐 – Coding Your Ambition

Browsed by
分类：程序设计

7个示例科普CPU Cache

2013年07月30日 Leo 评论 73 条评论 116,090 人阅读

示例1：内存访问和运行

二叉树迭代器算法

2013年07月14日 Todd 评论 54 条评论 46,959 人阅读

IoC/DIP其实是一种管理思想

2013年07月05日宝酷评论 66 条评论 74,106 人阅读

Javascript 装载和执行

2013年06月05日宝酷评论 104 条评论 109,219 人阅读

传统的方式

无锁HashMap的原理与实现

2013年05月30日 onetwogoo 评论 35 条评论 71,352 人阅读

Java中的原子操作

浏览器的渲染原理简介

2013年05月22日宝酷评论 157 条评论 212,193 人阅读

浏览器工作大流程

疫苗：Java HashMap的死循环

2013年05月10日宝酷评论 184 条评论 352,619 人阅读

问题的症状

从面向对象的设计模式看软件设计

2013年02月01日宝酷评论 93 条评论 100,154 人阅读

什么是模式

如此理解面向对象编程

2012年12月13日宝酷评论 185 条评论 183,212 人阅读

Go 语言简介（下）— 特性

2012年11月07日宝酷评论 96 条评论 110,351 人阅读

goroutine