Browsed by
分类:程序设计

无锁HashMap的原理与实现

无锁HashMap的原理与实现

 (本文由投稿)

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

  1. 使用线程安全的java.util.Hashtable作为替代。
  2. 使用java.util.Collections.synchronizedMap方法,将已有的HashMap对象包装为线程安全的。
  3. 使用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

好烂啊有点差凑合看看还不错很精彩 (26 人打了分,平均分: 3.62 )
Loading...
浏览器的渲染原理简介

浏览器的渲染原理简介

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

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

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

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

浏览器工作大流程

废话少说,先来看个图:

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

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (61 人打了分,平均分: 4.62 )
Loading...
疫苗:Java HashMap的死循环

疫苗:Java HashMap的死循环

在淘宝内网里看到同事发了贴说了一个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

好烂啊有点差凑合看看还不错很精彩 (90 人打了分,平均分: 4.69 )
Loading...
从面向对象的设计模式看软件设计

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

前些天发了一篇《如此理解面向对象编程》的文章,然后引起了大家的热议。然后我在微博上说了一句——“那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

好烂啊有点差凑合看看还不错很精彩 (40 人打了分,平均分: 4.60 )
Loading...
如此理解面向对象编程

如此理解面向对象编程

从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

好烂啊有点差凑合看看还不错很精彩 (54 人打了分,平均分: 4.57 )
Loading...
Go 语言简介(下)— 特性

Go 语言简介(下)— 特性

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

如果你还不了解Go语言的语法,还请你移步先看一下上篇——《Go语言简介(上):语法

goroutine

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

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (26 人打了分,平均分: 4.46 )
Loading...
Go 语言简介(上)— 语法

Go 语言简介(上)— 语法

周末天气不好,只能宅在家里,于是就顺便看了一下Go语言,觉得比较有意思,所以写篇文章介绍一下。我想写一篇你可以在乘坐地铁或公交车上下班时就可以初步了解一门语言的文章。所以,下面的文章主要是以代码和注释为主。只需要你对C语言,Unix,Python有一点基础,我相信你会在30分钟左右读完并对Go语言有一些初步了解的。

Hello World

package main //声明本文件的package名

import "fmt" //import语言的fmt库——用于输出

func main() {
    fmt.Println("hello world")
}

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (29 人打了分,平均分: 4.59 )
Loading...
TF-IDF模型的概率解释

TF-IDF模型的概率解释

(感谢 @猫叔shiro(以前的todd) 投递此文)

信息检索概述

信息检索是当前应用十分广泛的一种技术,论文检索、搜索引擎都属于信息检索的范畴。通常,人们把信息检索问题抽象为:在文档集合D上,对于由关键词w[1] … w[k]组成的查询串q,返回一个按查询q和文档d匹配度relevance(q, d)排序的相关文档列表D’。

对于这一问题,先后出现了布尔模型、向量模型等各种经典的信息检索模型,它们从不同的角度提出了自己的一套解决方案。布尔模型以集合的布尔运算为基础,查询效率高,但模型过于简单,无法有效地对不同文档进行排序,查询效果不佳。向量模型把文档和查询串都视为词所构成的多维向量,而文档与查询的相关性即对应于向量间的夹角。不过,由于通常词的数量巨大,向量维度非常高,而大量的维度都是0,计算向量夹角的效果并不好。另外,庞大的计算量也使得向量模型几乎不具有在互联网搜索引擎这样海量数据集上实施的可行性。

tf-idf模型

目前,真正在搜索引擎等实际应用中广泛使用的是tf-idf模型。tf-idf模型的主要思想是:如果词w在一篇文档d中出现的频率高,并且在其他文档中很少出现,则认为词w具有很好的区分能力,适合用来把文章d和其他文章区分开来。该模型主要包含了两个因素:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (17 人打了分,平均分: 4.35 )
Loading...
Bret Victor – Learnable Programming

Bret Victor – Learnable Programming

大家是否还记得之前酷壳向大家介绍的苹果设计师Bret Victor一种可视编程的视频《Bret Victor – Inventing on Principle》,最近,他写了一篇文章—— Learnable Programming,写这篇文章的原因是因为“可汗学院(Khan Academy)”近期上线的一个在线编程环境,根据他的演讲提供了一堆基于Javascript的“实时编程”的环境,因为这个环境是引用了他的想法,所以,他有必要出来喷两句。

这篇文章的开头就是一个问题——“How do we get people to understand programming?”,我们怎么让人们懂得编程?

然后,他说了两条——

  • 编程是一种思考,而不是一种死记硬背的技能!你学会了“for循环”并不是说你就学会了编程,这就好像你知道有铅笔这个东西,但是你对绘画还是什么不懂。(对于这一条,正好这两天我在微博上和人辩论“基础算法面试题是否好”(还有微博一微博二),而且我以前也写过一篇《为什么我反对纯算法面试》,这里借用Bret的话再加强一下我的观点——“我们一方面在骂中国的应试教育毁了学生,另一方面我们又在把我们的面试变成“考八股文”式的考试!  你会qsort有什么用?你只不过是会用一支高级铅笔而已罢了。”)
  • 人只有看得见,才能理解。如果一个程序员不能看到他的程序在干什么,那么她就不能理解程序。(对于这一条,让我想到了Donald Knuth的话——“An algorithm must be seen to be believe!”)

所以,Bret 觉得编程软件的目标是——

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (20 人打了分,平均分: 4.50 )
Loading...
无锁队列的实现

无锁队列的实现

————注:本文于2019年11月4日更新————

关于无锁队列的实现,网上有很多文章,虽然本文可能和那些文章有所重复,但是我还是想以我自己的方式把这些文章中的重要的知识点串起来和大家讲一讲这个技术。下面开始正文。

关于CAS等原子操作

在开始说无锁队列之前,我们需要知道一个很重要的技术就是CAS操作——Compare & Set,或是 Compare & Swap,现在几乎所有的CPU指令都支持CAS的原子操作,X86下对应的是 CMPXCHG 汇编指令。有了这个原子操作,我们就可以用其来实现各种无锁(lock free)的数据结构。

这个操作用C语言来描述就是下面这个样子:(代码来自Wikipedia的Compare And Swap词条)意思就是说,看一看内存*reg里的值是不是oldval,如果是的话,则对其赋值newval

int compare_and_swap (int* reg, int oldval, int newval)
{
  int old_reg_val = *reg;
  if (old_reg_val == oldval) {
     *reg = newval;
  }
  return old_reg_val;
}

我们可以看到,old_reg_val 总是返回,于是,我们可以在 compare_and_swap 操作之后对其进行测试,以查看它是否与 oldval相匹配,因为它可能有所不同,这意味着另一个并发线程已成功地竞争到 compare_and_swap 并成功将 reg 值从 oldval 更改为别的值了。

这个操作可以变种为返回bool值的形式(返回 bool值的好处在于,可以调用者知道有没有更新成功):

bool compare_and_swap (int *addr, int oldval, int newval)
{
  if ( *addr != oldval ) {
      return false;
  }
  *addr = newval;
  return true;
}

与CAS相似的还有下面的原子操作:(这些东西大家自己看Wikipedia,也没什么复杂的)

注:在实际的C/C++程序中,CAS的各种实现版本如下:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (29 人打了分,平均分: 4.76 )
Loading...