Yebangyu's Blog

Fond of Concurrency Programming , Distributed System and Machine Learning

C99中的柔性数组

柔性数组是C99引入的feature。

1
2
3
4
5
struct Data
{
  int i;
  int a[0];
};

其中柔性数组a处于结构体的末尾,并且声明的大小为0。

深入解析快速排序(Quick Sort)

本文将对快速排序进行深入的分析和介绍。通过学习本文,您将

  • 秒杀快速排序面试
  • 掌握高效实现快排
  • 加深范型编程意识

八卦花絮

快速排序是由图灵奖获得者、计算机语言设计大佬C. A. R. Hoare在他26岁时提出的。说起C. A. R. Hoare老爷爷,可能很多人的第一印象就是快速排序,但是快排仅仅是他人生中非常小的成就而已。例如,他在1978年提出的Communicating Sequential Processes(CSP)理论,则深深的影响了并行程序设计,Go语言中的Goroutine就是这种典范。

Peterson算法实现spin lock

对spin lock和mutex不熟悉的朋友,可以看上篇博客。

提出问题

如何仅仅通过load和store实现spin lock呢?

本文只考虑、只针对只有两个线程的情形。假设这两个线程的id分别为0和1。编程环境为X86体系结构 + Intel CPU + gcc

编写高质量代码(下)

上回我们从微观角度,以一个实际的例子,从正确、高效、易读等特性着手,介绍了如何编写高质量的代码。这次,我们从宏观出发,从软件开发流程入手,着重介绍其中的几个方面,包括代码规范、Code Review、测试等。

如果说上回的内容注重个人编码,那么本文将偏向团队开发。

代码规范

团队的代码规范,一般由领导和大佬们制定后,大家统一实行。这里面有几个问题:

真的需要代码规范吗?

言下之意,制定和执行代码规范是否浪费时间?

C++函数对象(function object)的应用

假如我们实现了这样的一个单向链表:

1
2
3
4
5
6
7
8
9
10
11
12
13
class LinkedListNode
{
  int data_;
  LinkedListNode *next_;
};
class LinkedList
{
  public:
    void insert(LinkedListNode* &p);
    void del(LinkedListNode *p);
  private:
    LinkedListNode *head_;
};

多线程内存问题分析之mprotect方法

多线程中的内存问题,一直被认为是噩梦般的存在,几乎只有高手、大仙才能解决。除了大量的打log、gdb调试、code review以及依靠多年的经验和直觉之外,有没有一些分析的手段和工具呢?答案是肯定的。本文首先介绍其中的一种:mprotect大法。通过mprotect,保护特定的感兴趣的内存,当有线程改写该区域时,会产生一个中断,我们在中断处理函数中把调用栈等信息打印出来。这是大概的思路,不过其中的问题很多,我们慢慢道来。

深入解析Bloom Filter(中)

本篇将介绍:

  • d-left hashing
  • d-left counting bloom filter

上篇文章,我们介绍了Standard Bloom Filter(SBF)和Counting Bloom Filter(CBF)。简单回顾下,我们大概思路和历程是:为了解决允许false positive下的membership问题,我们设计了哈希表算法,由于它所需空间巨大,我们引入bitmap方法;因为它false positive possibility太大,我们引入了SBF,它使用多个独立的、均匀分布的哈希函数。而SBF的一个缺点是不支持删除操作,为了能够删除,我们引入了CBF,然而,CBF存在一个问题。

什么问题呢?那就是空间利用率不高。这可以通过简单的数学计算知道大概:

考察某个位置,该位置的计数器counter的值$\xi$

$P(\xi = c) \approx \binom{mk}{c} {(\frac{1}{n})}^{c}({1-\frac{1}{n}})^{mk-c} = B(km,\frac{1}{n})$

Spinlock and mutex

Spinlock(自旋锁)和mutex作为两种互斥锁,在并行编程中都得到了广泛应用。那么,这两种锁有什么区别吗?

当一个线程对Spinlock加锁时,如果该锁被其他线程占用,那么该线程会通过一个loop不断地重试( try again and again);而使用mutex的线程没有得到锁时,会sleep。

因为,当临界区较短时,Spinlock因为没有上下文切换,可能性能更优;当临界区较长时,不断的spin将浪费大量的cpu资源。

深入解析Bloom Filter(上)

本文将介绍:

  • Bloom Filter和它的变形与拓展
  • Bloom Filter的使用场景
  • Bloom Filter的详细数学分析

提出问题

Google的爬虫每天需要抓取大量的网页。于是就有一个问题:每当爬虫分析出一个url的时候,是抓呢,还是不抓呢?如何知道这个url已经爬过了?