LevelDB源码解析(2) SkipList(跳跃表)

背景 SkipList是LevelDB的MemTable使用的底层存储结构,LevelDB实现了一个支持泛型的跳跃表。本文不会具体介绍跳跃表的数据结构,如果读者不了解跳跃表的原理、实现,可以先看一下跳跃表(Skiplist)从原理到实现 SkipList的对外……

阅读全文

跳跃表(SkipList)从原理到实现

数组与链表 数组和链表是非常基础的两种数据结构,链表每次查找都需要从头结点开始线性遍历,时间复杂度是O(n)。而数组通过维护元素顺序可以使用二分查找,查找的时间复杂度是O(lg(n))。查找效率方面数组完胜链表。 但是由于数组插入或删除元素时必须要移动所有受影……

阅读全文

LevelDB源码解析(1) Arena内存分配器

背景 LevelDB中需要频繁申请和释放内存,如果直接使用系统的new/delete或者malloc/free接口申请和释放内存,会产生大量内存碎片,进而拖累系统的性能表现。所以LevelDB实现了一个Area内存分配器来对内存进行管理,以保证性能。 Aren……

阅读全文

C/C++中的断言(assert与static_assert)

assert简介 assert被C/C++用来判断某些条件是否成立,比如判断指针类型的大小sizeof(void*)是否大于8,或者判断malloc返回的指针是否为null。 assert的函数申明如下: void assert( int expression ); 如果expression为0,即false,a……

阅读全文

内存乱序与C++内存模型详解

内存乱序 内存乱序指的是内存操作出现乱序,CPU缓存、编译器优化、处理器指令优化等都会改变内存顺序,造成内存乱序。 学习内存顺序容易陷入了一个误区,因为内存顺序是和CPU架构、编译器息息相关的,想要去深入理解CPU缓存怎么导致内存乱序的,编译器优化和处理器指令……

阅读全文

聊一聊原子操作

先举个栗子 下面的C++代码编译执行后,v的输出是多少呢?每个线程都执行了10000次v++,总共2个线程,那么v的最终结果应该是20000,结果是这样吗? #include <iostream> // std::cout #include <thread> // std::thread int v = 0; void plus() { for(int i=0; i<10000; i++) { ++v; } } int main() { std::thread t1(plus); std::thread t2(plus); t1.join(); t2.join(); std::cout << "v: " << v << std::endl; } //编译执行指令:g……

阅读全文

简易编译器实现(二)使用Bison创建语法分析器

简易编译器实现(一)使用Flex创建词法分析器一文介绍了编译器的概念和七个阶段,并说明了如何使用Flex创建词法分析器。本篇文章介绍如何使用Bison创建语法分析器,并实现基本的运算能力。本文继续使用简易编译器实现(一)使用Flex创建词法分析器中提出的集……

阅读全文

简易编译器实现(一)使用Flex创建词法分析器

编译器简介 编程语言是人和计算机交流的媒介,但是计算机只能理解二进制语言,编译器的工作就是把人可以理解的编程语言翻译成机器可以理解的二进制语言,即可执行文件。 编译过程可以细分为7个阶段 词法分析 语法分析 语义分析 中间代码生成 机器无关的代码优化 代码生成 机器相关的代……

阅读全文

内联函数(inline Function)浅析

什么是内联函数 内联函数(inline function)是C和C++都支持的一种语言特性,简单来说,就是在编译阶段在调用内联函数的地方直接展开函数代码,避免函数调用的开销。 内联函数的优点 内联函数的主要作用是避免函数调用开销,那就必须要讨论一下函数调用有哪些开……

阅读全文

学习笔记:相似度度量与协同过滤

相似度度量 相似度度量关注的是两个对象是否相似,相似程度是多少?比如两张图片、两篇文章、两句话、两个人的喜好的相抵程度等。 为了度量相似度,首先需要将比较对象转换成实数向量,这样计算机才能够理解。对象类型不同,转换方式也不同,最终目的都是将比较对象转换成实数向……

阅读全文