Yebangyu's Blog

Fond of Concurrency Programming, Distributed System and Performance Optimization.

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。

深入解析快速排序(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