发表于 | 分类于 | 评论数： | 阅读次数：

近期工作的内容主要是设计一个通用的游戏排行榜服务器, 通用的含义指的是同时为多个项目组提供一套通用的解决方案, 经过不断的调研, 最终写下此文.

本文将会讲述 排行榜的多种实现方式, 不过最终我选择了 SkipList 作为底层的数据结构, 因此会着重讲SkipList.

先来讲一下排行榜的主要功能.

排行榜主要功能

  • 更新/删除/获取 一个 Key 在某个 排行榜 上的 排名, 及展示信息
  • 获取 一个排行榜 任意区间(例如排名区间) 的展示信息

排行榜排序方案

游戏中的排行榜的排序方案无非就两种

  • 实时排序, 即玩家数值变化的瞬间, 就完成了对它的排序
  • 非实时排序, 亦可称之为定时排序, 玩家数据变动不立即排序, 而是直到策划所配的时间点到的时候才进行排序

这两种排序方案没有好坏之分, 主要是看策划他想要什么? (或许他自己也不知道想要什么, 他都想试试看, 他只顾着他自己)

阅读全文 »

发表于 | 分类于 | 评论数： | 阅读次数：

前言

本节主要是讲 网络编程中, 常用的I/O 多路复用. 全文大概分为以下几点.

  1. 为什么需要I/O多路复用?
  2. I/O多路复用的使用场景?
  3. 为什么都是与非阻塞I/O进行搭配, 而不是与阻塞I/O进行搭配呢?
  4. select 的 优缺点 及 内核实现
  5. poll 的 优缺点 及 内核实现
  6. epoll 的 优缺点 及 内核实现
阅读全文 »

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

这是 Linux 系统编程系列 中的第一篇, 在这个系列里面, 我想以这么个顺序来讲述每一篇的内容, 先是快速简单地了解一下 常见的使用方法, 即API如何使用, 接着再深入其中, 了解内核为API提供的帮助, 大致是 C标准库 → 系统调用 这么个学习路线.

时间的定义

首先要记住 计算机的起始时间 为 (格林威治时间)1970年1月1日0点, 被称作 GMT时间 是时区时间, 不过它是根据地球公转和自转来计算的, 不是特别准确. 在计算机世界中, 往往被称作 UTC时间, 它是以原子钟来计算时间, 简单来说就是 UTC时间 比 GMT时间要准确, 同时两个时间又恰好没有时差, 但是UTC时间又不是时区时间, 因此容易被人弄混.

阅读全文 »

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

本篇主要讲 Lua 中的 字符串 是如何设计实现的, 为本系列第二篇.

TString

Lua 中的字符串 的结构体名字为 TString 主要由以下内容构成.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define CommonHeader \
  GCObject* next; \
  lu_byte tt; \
  lu_byte marked

typedef struct TString {
  CommonHeader;  // GC 回收
	// 短字符串时 0为需要被GC接管, 1为不被GC回收
	// 长字符串时 0为未hash, 1为已hash
  lu_byte extra;
  lu_byte shrlen; // 短字符串长度, 如果是长字符串则无意义
  unsigned int hash; // 字符串哈希值
  union {
    size_t lnglen; // 长字符串长度 如果为短字符串则无效
    struct TString* hnext; // 短字符串的时候 与相同哈希值的字符串串起的链表
  } u;
} TString;

从中我们可以猜想, Lua 中的字符串主要分为两个部分, 其中一个 是 String Header, 用于记录字符串的长度, hash值, 和 GC回收的链表.

记录字符串的长度我们可以比较好理解, 提高效率, 不用每次都重新计算一次字符串长度, 但是 Hash值是用来做什么的呢?

阅读全文 »

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

由于之前实习包括现在正式的工作 都做的是 游戏服务端研发, 少不了 与 Lua 打交道, 因此 也对 Lua 的实现产生了兴趣, 在这里试图 将 Lua 的实现原理 剖析出来, 此为本系列的首篇.

本文主要分两个部分 一个部分是剖析 Lua 中内置的各种类型的数据结构, 另一个部分是剖析 Lua 虚拟机中所要用的必要的数据结构.

基础数据结构

基本类型

众所周知, Lua 的基本类型 非常少, 仅有 int, number(浮点数), 闭包(函数), userdata(指针), string, nil, table 等类型. 这种时候 就要 有一个数据结构 来方便的表示出 这几种类型.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef union Value {
  GCObject *gc;    // GC回收用的 暂时可以理解成一个链表 链上所有可回收的对象

  void *p;         /* light userdata */
  int b;           /* booleans */
  lua_CFunction f; /* light C functions */
  lua_Integer i;   /* integer numbers */
  lua_Number n;    /* float numbers */
} Value;

#define TValuefields	Value value_; int tt_

typedef struct lua_TValue {
  TValuefields;
} TValue;
阅读全文 »

发表于 | 分类于 | 评论数： | 阅读次数：

前言

终于的终于, 2016-2020年 这四年大学时光已经结束, 而我也入职了金山西山居, 依然从事游戏服务端的研发.

很久没有更新过博文了, 主要是因为 时间比较紧张, 还有经历了一系列 糟糕的事情(可进行脑补, 你脑补出来的几乎都是对的hhhh), 还有自认学习深度不足, 在探索一种全新的学习模式, 来调整工作与生活的状态.

新篇章

阅读全文 »

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

Loki Allocator 有三个类 这玩意对比起 pool allocator 的优点就在于 它有把内存还给系统

但是它作为一个 内存分配器 却在里面使用了 vector 作为容器… 按道理来说 应该在其内部实现一个简易版的 vector 才不会那么奇怪 但也没所谓 只是 先用了一次标准库的分配器 后续使用容器的时候 就可以用 Loki 分配器了.

  • Chunk
  • FixedAllocator
  • SmallObjAllocator

Chunk 解剖

Chunk 是整个分配器的最底层 里面主要是三个 成员变量

1
2
3
4
5
6
// 指向内存块
unsigned char * pData_;
// 目前可用区块的第一块的索引
unsigned char firstAvailableBlock_;
// 有多少块可用
unsigned char blocksAvailable_;

Chunk 的几个关键函数 已进行 剪裁 和 修改

Chunk 分配

分配流程很简单 就是 申请了内存以后 将每个小区块的第一个字节设置为索引 排好号

取的流程:

  1. 从 当前可用区块的第一块索引中取 得当前可用区块
  2. 当前可用区块会被返回
  3. 被返回的可用区块中的索引 被设置到 当前可用区块索引去(这样下一次就会使用到它)
  4. 可用区块数目 - 1
阅读全文 »

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

为什么要实现内存池?

一方面 是为了减少 调用 malloc() 的次数(尽管 malloc() 不慢) 但是调多了 会产生(外碎片)

另一方面 是因为 每次用 malloc() 分配到的内存 是要交税的 就是上一节中讲的 cookie 里面记录着 这一块内存的大小信息(内碎片) 特别是在频繁申请小内存的时候尤为明显

最终 pool_allocator 版本

具体代码可见 Memory_Pool

原理可见 C++ 内存管理 之 STL内存分配实现原理

阅读全文 »

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

本文主要讲讲 GNU-C++ 4.9 下的扩展内存分配器

首先 GNU-C++ 4.9 有 7 个扩展的内存分配器

  • new_allocator
  • malloc_allocator
  • pool_allocator
  • __mt_alloc
  • array_allocator
  • debug_allocator
  • bitmap_allocator

主要看看 pool_allocator array_allocator bitmap_allocator

以下源码都可在 .../ext/*.h 下找到 我将其进行了适当的 删减和修改

__gnu_cxx::new_allocator

直接用 ::operator new 和 ::operator delete 实现出来的 好处是 可以被重载 没啥特色

1
2
3
4
5
6
7
8
9
10
template<typename _Tp>
class new_allocator {
public:
    pointer allocate(size_type __n, const void* = 0) {
        return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
    }
    void deallocate(pointer __p, size_type) {
        ::operator delete(__p);
    }
};
阅读全文 »

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

本文主要讲的是 各个C++版本 中的STL标准库中的默认内存分配器 的 各种实现

VC6 标准分配器实现

VC6 它什么内存管理都没做 直接调用的 operator new 而 operator new 内部实际上 调用的就是 malloc

此外 VC6 下 是以元素为单位 比如 int 的话 他就会分配 512 ints 如果是 double 则会分配 512 doubles

而 GNU-C++ 2.9 以字节为单位 GNU-C++ 4.9 以元素为单位 在 G2.9 中的容器默认分配器 被移到了 pool_allocator 中

注意 G2.9 的标准分配器 和 容器默认分配器 不一样噢!

GNU-C++ 2.9 标准分配器实现

std::allocator 标准分配器 也是什么都没做

但是 G2.9 容器使用的分配器 不是上面的那个 std::allocator 而是 std::alloc

阅读全文 »