Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

String与Copy On Write

什么是Copy On Write

Copy On Write(COW)作为一种优化技术被广泛使用,在string的实现中也不例外。考虑如下的代码:

1
2
3
string s("1234");
string t = s;
cout<<t[1]<<endl;

第二行,通过调用copy constructor(注意,这里调用的是copy constructor,而不是copy assignment,因为它是从无到有构造对象,而不是设置已有对象)构造对象t,第三行对t中的某个元素进行只读操作。

如果让你实现copy constructor,你会怎么做呢?教科书里的、简单的实现大概是这样:

Ticket Lock

简单回顾

上回 我们介绍了peterson算法来实现spin lock,算法简单,实现简单,但是值得注意和留心的点很多。

粗略说来,peterson算法的主要缺点在于:

1,很难推广到n个线程(n>=3)。原始的算法针对两个线程,如果想应用在多个线程的场景里,需要做一定的修改。

2,peterson算法的动机是仅仅使用load和store来实现互斥访问。然而,我们知道,现代体系结构下,CPU和编译器会对读写操作进行乱序,仅仅依靠读写操作而不使用memory barrier就编写正确的程序非常困难。

Ticket Lock

在介绍Ticket Lock之前,我们首先分析一个妇孺皆知、地球人都知道的实现spin lock的方法(伪代码):

Soupen源码解析之string实现

写在最前

Soupen是一款高性能的nosql数据库,旨在能在某些方面替代Redis。它由不著名码农、秦汉史历史学家、本站站长Yebangyu同学在业余时间独立开发完成。

Github请访问这里 ,Python客户端请点击这里

在Soupen中有两种字符串(或者更准确的说,字节流)实现: SoupenString和SoupenNormalString。代码都在src/ds/soupen_string.hsrc/ds/soupen_string.cpp文件里。两种实现都设计为大小写不敏感。

SoupenNormalString

\0结尾的字符串实现,也就是说SoupenNormalString中的字符串都是以 \0结尾的。因此,对其施加任何类似于strcmp等传统C字符串函数都是安全的。

在实现时,针对短字符串,为了进一步优化效率,使用了柔性数组技术来提高cache命中。

Soupen源码解析之rank实现

写在最前

Soupen是一款高性能的nosql数据库,旨在能在某些方面替代Redis。它由不著名码农、秦汉史历史学家、本站站长Yebangyu同学在业余时间独立开发完成。

Github请访问这里 ,Python客户端请点击这里

和Redis一样,Soupen也同样支持rank功能,但是所使用的数据结构是Treap(Redis使用的是Skip List)。Treap和Skip List都是概率性的高级数据结构。

那么,什么是Treap呢?

What is Treap

Treap

(图片来源于WikiMedia)

简单说来,Treap是这样的树:Treap中的每个节点至少包含key和优先级两个字段,其中key满足搜索树性质,优先级满足堆序性。如上图所示,数字是优先级字段,字母是key字段。其中优先级构成了一个大根堆。

也就是说,在Treap中,key组成了一个二叉搜索树,优先级组成了一个堆。所谓Treap = Tree + Heap。

论汉武帝独尊儒术

汉武帝为什么独尊儒术?

在讨论这个问题前,先让我们回忆一个非常基本的常识,还是不厌其烦的交待两个人物的关系:汉武帝和窦太后。窦太后是汉文帝的老婆,汉景帝的妈妈,汉武帝的奶奶。

窦太后

汉武帝为什么独尊儒术呢?大家都说,这是因为汉武帝推崇并认可儒家学说。然而,以我个人的浅见,汉武帝其实并不是多么喜欢儒家思想,也不懂儒家学说。

Introduction To Performance Optimization

写在最前

本文针对C++linux环境,但是思想和方法,却对其他语言和环境同样适用。很可供参考的。

优化前

1,确定优化是必须要做的。

如果程序已经跑的足够快了,内存使用也足够省了,那么完全没有优化的必要。什么是足够呢?能够满足当前的业务和需求。因此,如果不是绝对必要,不要优化。

这是因为虽然优化不是万恶之源,但是优化可能会带来问题。为了提升一点点性能就得绞尽脑汁、辗转反侧;它可能让之前只需要一两行逻辑很清晰的代码,变成很难理解的高度优化的实现。优化很多时候某种程度上让代码可读性和可维护性变差。

2,确定该做的优化都做了

String Literal In C++

最近被一个很基本的知识点给咬伤,虽然之前知道这个问题,但是写代码的时候不小心还是容易犯错。简单记录一下。

提出问题

之前,代码里拥有如下数组:

1
2
3
4
const char *COLORS[3] = {"red",
                         "black",
                         "green"
                        };

现在需要以追加的形式,添加一个yellow的颜色。粗心之下,我写成了:

Soupen源码解析之itoa实现

写在最前

Soupen是一款高性能的nosql数据库,旨在能在某些方面替代Redis。它由不著名码农、秦汉史历史学家、本站站长Yebangyu同学在业余时间独立开发完成。

Github请访问这里 ,Python客户端请点击这里

提出问题

如何用C/C++实现正确的、可移植的、高效的、对所有整数都work的itoa函数?

原型如下

int itoa(char *buffer, int64_t value);

将value转为字符串后存在buffer中,返回字符串的长度。

Soupen: A High Performance Nosql

Soupen是一款高性能的nosql数据库,旨在能在某些方面替代Redis。它由不著名码农、秦汉史历史学家、本站站长Yebangyu同学在业余时间独立开发完成。

Github请访问这里 ,很烂的一个Python客户端请点击这里

动机

开发Soupen的主要原因是想通过这个项目,进一步提高和熟悉C++服务器端开发相关的技术和知识。

特性

换句话说,它和Redis相比有什么不同?

C99中的柔性数组

柔性数组是C99引入的feature。

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

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