SkipList跳表

为什么选择跳表

目前经常使用的平衡数据结构有:B树,红黑树,AVL树,Splay Tree, Treep等。想象一下,给你一张草稿纸,一只笔,一个编辑器,你能立即实现一颗红黑树,或者AVL树出来吗? 很难吧,这需要时间,要考虑很多细节,要参考一堆算法与数据结构之类的树,还要参考网上的代码,相当麻烦。用跳表吧,跳表是一种随机化的数据结构,目前开源软件 Redis 和 LevelDB 都有用到它,它的效率和红黑树以及 AVL 树不相上下,但跳表的原理相当简单,只要你能熟练操作链表,就能轻松实现一个 SkipList。 Continue reading “SkipList跳表”

基于循环数组的无锁队列

引言

最近对于注重性能的应用程序,我们有了一种能显著提高程序性能的选择:多线程.线程的概念实际上已经存在了很长时间.在过去,多数计算机只有一个处理器,线程主要用于将一个大的任务拆分成一系列更小的执行单元.以使得当其中某些执行单元因为等待资源而被阻塞的时候剩余的执行单元能继续执行。举个示例,一个网络应用程序,它监听一个TCP端口,当有外部请求到达时,处理请求.对于一个单线程的应用程序来说,只能在处理完一个请求之后再处理另外的请求,显然这个应用程序对用户非常不友好,它为一个用户服务的时候别的用户就只能干等.而对于多线程解决方案,我们可以让另外的线程来处理接收到的请求,主线程继续等待在服务端口上接受新的请求.

在只有一个处理器的机器上,一个多线程应用程序可能无法达到我们对它的预期.因为所有的线程都要争抢处理器以获得执行机会.而它的性能说不定比一个用单线程方式去解决同样问题的程序还要差,因为线程之间的通讯和数据共享也有不小的开销.

而在一个对称多处理器机器上(SMP),一个多线程应用可以真正的实现多任务并行执行.每个线程都可以拥有单独的处理器以获得执行的机会,不需要再像单处理器一样,必须要等到处理器空闲才能获得执行机会.对一个有N个处理器的SMP系统来说,理论上一个N线程的应用程序只需要它的单线程版本的1/N的时间就可以完成相同的任务(实际上这个理论值是无法达到的,因为线程之间的通讯和数据共享有不小的开销).

SMP的机器在过去是非常昂贵的,只有一些大公司和组织才能负担得起.而现今,多核心处理器已经相当廉价(现今市场上的pc处理器至少都拥有一个以上的核心),所以让应用程序并行化以提高性能现在已经变得非常流行.

但是编写多线程应用程序显然不是一件简单的事.线程之间需要共享数据,互相通信,很快你就会发现又要面对以前就遇到过的老问题:死锁, 对共享数据的非法访问,多线程动态分配/释放内存等.如果你足够幸运,参与到一个对性能有极高要求的项目中,你将会遇到更多导致性能不达标的问题:

  • Cache颠簸(Cache trashing)
  • 在同步机制上的争抢.队列
  • 动态内存分配

本文主要介绍一种基于数组实现的无锁队列用于解决上述三个性能问题,特别是动态内存分配,因为此无锁队列最初的设计目的就是为了解决这个问题. Continue reading “基于循环数组的无锁队列”

nomachine: Server log file growing rapidly

In some cases, mainly dependent on system configuration, after having updated NoMachine Terminal Server to version 6, the server log file fills up rapidly with warning messages like:

2017-12-01 08:04:37 791.607 144754 NXSERVER WARNING! Process ‘/usr/NX/bin/nxexec /usr/NX/scripts/restricted/nxenvironmentget.sh mate-session mate-session’ with pid ‘5111/5111’ finished with exit code 1 after 0,014 seconds.
2017-12-01 08:04:37 791.829 144754 NXSERVER WARNING! __getProcessEnvironment /usr/NX/scripts/restricted/nxenvironmentget.sh finished with 1

This does not impact the software’s functionalities.

Continue reading “nomachine: Server log file growing rapidly”

ES6新特性简介

1.变量声明const和let

我们都是知道在ES6以前,var关键字声明变量。无论声明在何处,都会被视为声明在函数的最顶部(不在函数内即在全局作用域的最顶部)。这就是函数变量提升例如:


Continue reading “ES6新特性简介”

缓存淘汰算法 – LRU

1. LRU
1.1. 原理

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

1.2. 实现

最常见的实现是使用一个链表保存缓存数据,详细算法实现如下:

1. 新数据插入到链表头部;

2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;

3. 当链表满的时候,将链表尾部的数据丢弃。 Continue reading “缓存淘汰算法 – LRU”

如何激励项目团队成员前进,防止成员抱团怼项目经理的情况发生?

老师参考答案:

首先分析问题的根源,为什么项目团队成员会对项目经理不配合,甚至发生互怼的情况?

一、新任项目经理还没有梳理威信:如果是由于项目经理新上任还没有树立威望,那么可以通过团建、访谈的方式建立与团队的信任,并且通过自身的领导能力树立威望。

二、之前发生过矛盾:如果是由于项目经理与团队成员发生过矛盾,造成间隙,那么项目经理作为团队的领导者,应该开诚布公地就之前的问题进行坦诚的交流,对事不对人,矛盾双方要争取达成谅解。

三、团队中有刺头不服管:如果是这个情况,项目经理应该先私下与不服管的成员进行对话,避免公开矛盾,这样会损害项目经理的威信,如果没有改善,那么项目经理必须寻找机会将刺头清出团队,避免对团队造成破坏性的影响。

TIM截图20180302094804.jpg

Continue reading “如何激励项目团队成员前进,防止成员抱团怼项目经理的情况发生?”

gf框架之并发安全容器 – gmap,以及与sync.Map的性能比较

gf框架提供了几个非常实用的并发安全容器,其中gmap就是项目开发中最常用的一个。

gmap具体的方法请参考godoc:https://godoc.org/github.com/johng-cn/gf/g/container/gmap

gmap内部有多个类型结构体定义,包括:IntBoolMapIntIntMapIntInterfaceMapIntStringMapInterfaceInterfaceMapStringBoolMapStringIntMapStringInterfaceMapStringStringMapUintInterfaceMap

从执行效率上考虑,基于不同的需求场景,选择合适的类型结构体,其执行效率是不一样的,以下使用基准测试来对比各个类型的写入性能(测试代码):

Continue reading “gf框架之并发安全容器 – gmap,以及与sync.Map的性能比较”