利用jemalloc分析内存泄漏以及LD_PRELOAD

Jemalloc 不仅实现了一种通用的malloc, 还能利用它来做内存分析和监控/调优等.

这里介绍如何利用jemalloc来检测内存泄漏问题. 并且利用LD_PRELOAD环境变量, 可以做到不需要源代码, 将jemalloc库嵌入到可执行程序中, 从而用jemalloc去malloc内存, 并进行管理. 也就是说, 每当程序中调用malloc/new时, 实际调用的是jemalloc里实现的函数.

Read More

SuRF: 基于Fast Succinct Tries的Range Query Filter

最近学习了一篇2018 SIGMOD会议上的best paper, 无奈, 谁让我入了database的坑呢.

论文: “SuRF: Practical Range Query Filtering with Fast Succinct Tries”

我们知道Bloom filter由于采用hash实现, 对single-key查询效率高, 但对range query就无能为力了. 虽然有支持range query的prefix Bloom filter存在, 但还是不够通用. 而Succinct Range Filter (SuRF)是基于一种新的数据结构Fast Succinct Trie (FST), 不仅支持point query还支持range query. 除了速度快之外, 还非常节省空间.

Read More

Hacking on Clang : Diagnostics

Clang比传统编译器具有更加友好的错误提示。

本文主要对Diagnostics模块中的相关API做一个简单梳理。

DiagnosticsEngine

我们主要用DiagnosticsEngine类中的Report()方法报告诊断信息。该方法的函数声明如下:

DiagnosticBuilder Report (SourceLocation Loc, unsigned DiagID)
DiagnosticBuilder Report (unsigned DiagID)

SourceLocation记录了源代码中对应的位置信息。

每个诊断都需要指定一个唯一的DiagID. DiagID可以通过DiagnosticsEngine类中的getCustomDiagID()方法生成,其函数声明如下:

unsigned getCustomDiagID (Level L, const char(&FormatString)[N])
Read More

2017找工作小结

本来想着在新年写个年度小结,却发现整一年基本都在找工作,实习,找工作中度过,没有技能提升,也没有什么大的改变,惭愧。

offer: 阿里蚂蚁,商汤,face++,网易游戏,网易有道,京东,滴滴,小米。

挂的:Indeed,微软美国,Airbnb,Hulu,猿题库,头条


Indeed:东京,年薪58w+。一开始是online笔试,需要全部编程题AC才行。然后是人事,最后三轮技术onsite。都是英文面,比以往多了一轮人事面,太渣,挂在了人事。

微软美国:当时在微软北京实习,做的是推荐系统,最后没有选择转正,而是投了美国的岗位。面试官是从三藩飞过来的歪果人,三轮onsite,不是很难,可能口语还是不行吧。话说四月份要去法国出差,还是我一个人,真的能活着回来么。。。

WAP:日企。也都是英文面。先是online interview,视频编程,写代码之前跟对方说下思路,然后再写。最少要过两道,当时过了两道半吧,第三道说了思路,没时间写代码了。然后是三轮onsite,前两轮都是编程题,第三轮vp面,有技术题,智力题,偏工程的,基础知识的,简历项目内容都会涉及。都走到最后一步了,最后HR还是只给了实习,觉得很遗憾。那天不知道什么情况,唯一一次上来就写代码的,没有跟面试官说思路,后来二面面试官送我的时候,好心提醒了我这个问题。最后觉得实习太麻烦,就没有去。

Read More

约瑟夫环问题

已经不止一次在面试中遇到过这种问题了。

n个人(编号为1~n)组成一个环,从第一个人以1开始报数,报的数为k的整数倍的那个人将从环中移除。问最后一个被移除人的编号。

比如,n=5, k = 3时,最后一个被移除人的编号为4.


最简单的实现方式:用链表进行模拟操作。这种方式复杂度太高。

以下介绍的是数学方式:O(n).

将报的数为k的整数倍的人移除,等价于,将某个人移除之后,后面的人再重新以1开始报,报到k的人移除,以此循环下去。

为了方便,设这n个人的编号以0开始。取f(n)表示,由n个人组成的约瑟夫环问题,最后一个被移除人的编号。

在第一轮操作中,将编号为(k-1)的人移除,之后的所有人再做一个编号映射,即:

  0      1    ...  k-2    k-1     k    k+1   ...    n
  |      |          |      |      |     |           |
n-k+1  n-k+2  ...  n-1  deleted   0     1    ...   n-k
Read More

^