roaring bitmap aka RBM

首先,redis的bitmap占用空间是很恐怖的,512M,就算用的很少也是512M

但是使用概率型数据结构,比如hyperloglog,省空间,但是有误差,且只能增不能删

又想要大量标记,又不想有误差,又不想占用大空间,解决方案 roaring bitmap

对稀疏位图进行压缩,减少内存占用并提高效率。比较有代表性的有WAH、EWAH、Concise,以及RoaringBitmap。前三种算法都是基于行程长度编码(Run-length encoding, RLE)做压缩的,而RoaringBitmap算是它们的改进

  1. 支持动态修改位图(静态的位图有其它压缩方式)
  2. 利用SIMD加速位图操作

image-20201214204833017

32位无符号整数按照高16位分桶,即最多可能有216=65536个桶,论文内称为container。存储数据时,按照数据的高16位找到container(找不到就会新建一个),再将低16位放入container中。也就是说,一个RBM就是很多container的集合

  • 第一层称之为Chunk,每个Chunk表示该区间取值范围的base(n2^16, 0<= n < 2^16),如果该取值范围内没有数据则Chunk不会创建
  • 第二层称之为Container,会依据数据分布进行创建(Container内的值实际是区间内的offset)

ArrayContainer

当桶内数据的基数不大于4096时,会采用它来存储,其本质上是一个unsigned short类型的有序数组。数组初始长度为4,随着数据的增多会自动扩容(但最大长度就是4096)。另外还维护有一个计数器,用来实时记录基数。

  • 当区间内数量少于4096时,数组占用更紧凑;多于4096,则使用位图更经济

BitmapContainer

当桶内数据的基数大于4096时,会采用它来存储,其本质就是上一节讲过的普通位图,用长度固定为1024的unsigned long型数组表示,亦即位图的大小固定为216位(8KB)。它同样有一个计数器。

上图中的第三个container基数远远大于4096,所以要用BitmapContainer存储。

RunContainer

RunContainer在图中并未示出,初始的RBM实现中也没有它,而是在本节开头的第二篇论文中新加入的。它使用可变长度的unsigned short数组存储用行程长度编码(RLE)压缩后的数据。

AAAAAAbbbXXXXXt
6A3b5X1t

由此可见,RunContainer的压缩效果可好可坏。考虑极端情况:如果所有数据都是连续的,那么最终只需要4字节;如果所有数据都不连续(比如全是奇数或全是偶数),那么不仅不会压缩,还会膨胀成原来的两倍大。所以,RBM引入RunContainer是作为其他两种container的折衷方案。

O(logn)的查找性能:

  • 首先二分查找key值的高16位是否在分片(chunk)中
  • 如果分片存在,则查找分片对应的Container是否存
    • 如果Bitmap Container,查找性能是O(1)
    • 其它两种Container,需要进行二分查找

参考链接

  • 论文地址 https://arxiv.org/pdf/1603.06549.pdf
  • 官网 http://roaringbitmap.org/,有各种实现 c实现 https://github.com/RoaringBitmap/CRoaring
  • redis的bitmap不是这个方案,社区实现了一个module https://github.com/aviggiano/redis-roaring,直接搬croaring
  • 图来自 https://blog.bcmeng.com/post/doris-bitmap.html 这篇介绍,doris了解一下,doris和clickhouse啥区别?
    • https://github.com/apache/incubator-doris
    • 他这篇hbase rowkey设计也不错,基本覆盖了书里介绍的内容 https://blog.bcmeng.com/post/hbase-rowkey.html
  • 本文内容整理自 https://zhuanlan.zhihu.com/p/39828878和https://www.jianshu.com/p/818ac4e90daf
  • sigmod2021有一个新的设计 Tree-Encoded Bitmaps http://db.in.tum.de/~lang/papers/tebs.pdf 值得研究一下,这里留个坑 TODO

Read More

整数划分


我不怎么做算法题,今天才碰到整数划分,结果还是个经典递归/dp题目

参考链接给的是递归解法。

#include<iostream>
using namespace std;

int equationCount(int n,int m)
{
    if(n==1||m==1)
        return 1;
    else if(n<m)
        return equationCount(n,n);
    else if(n==m)
        return 1+equationCount(n,n-1);
    else
        return equationCount(n,m-1)+equationCount(n-m,m);
}

int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF&&(n>=1&&n<=120))
    {
        printf("%d\n",equationCount(n,n));
    }
    return 0;
}

递归和DP是一体两面,比如台阶dp

l = []
l.append(0)
l.append(1)
l.append(2)
n=int(input())
for i in range(3,n+1):
    l.append(l[i-1]+l[i-2])

print(l[n])

判断进程

lsof

netstat -tcp closewait

netstat -na awk ‘/^tcp/ {++S[$NF]} END {for(a in S) print a, S[a]}’

ref

  • https://www.cnblogs.com/dolphin0520/archive/2011/04/04/2005098.html

  • https://www.zhihu.com/question/56577396 这个问题讲了整数划分的背景

  • https://blog.csdn.net/dst111188/article/details/78554698 递归和DP的关系,空间换时间。核心的转换公式都是一样的。

  • http://blackblog.tech/2018/08/24/LeetCodeReview6/ 列了一些leetcode上的DP题目的解法。很有心了

  • https://blog.csdn.net/sxhelijian/article/details/8978794

  • https://blog.csdn.net/sxhelijian/article/details/8978850 上面这两个链接是c/c++输入模板

Read More


招人啦

老东家,对我挺好,早知道当初留在那边了,宁做鸡头不做凤尾,平台优势不是你个人优势

Read More

relocation error version GLIBC_PRIVATE not defined in file


拷贝库到某某目录,执行

 export LD_LIBRARY_PATH=$PWD:$LD_LIBRARY_PATH

导入,遇到了一堆类似的错误。做个记录。以后弄清楚


ref

  1. https://lists.debian.org/debian-glibc/2016/03/msg00153.html
  2. https://askubuntu.com/questions/831592/glibc-private-not-defined-in-file-libc-so-6 貌似是resolv库拷贝引发的不兼容
  3. https://unix.stackexchange.com/questions/367597/almost-no-commands-working-relocation-error-symbol-getrlimit-version-glibc 解决办法,unset LD_LIBRARY_PATH,没说具体原因
  4. 打开vim提示错误vim: : ATUSHHH-! : Error 43692576的罪魁祸首 https://stackoverflow.com/questions/31155824/dlopen-in-libc-and-libdl
Read More

__FILE__路径显示过长


有运行时解决办法,把 __FILE__结果裁剪一下,太弱智了

#define __FILENAME__ (strrchr(__FILE__, '/') ? strrchr(__FILE__, '/') + 1 : __FILE__)

见参考链接,居然还采纳了你敢信??

正确的编译期做法是第二个答案

如果是cmake

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -D__FILENAME__='\"$(subst  ${CMAKE_SOURCE_DIR}/,,$(abspath $<))\"'")

另外@houjw-hx 提到notdir,更清爽,在此补充表示感谢

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -D__FILENAME__='"$(notdir $<)"'")

确实简单一些。不太了解cmake这些小接口,我都是搜到能对付用的就直接用了。。

如果是makefile

CXX_FLAGS+=-D__FILENAME__='\"$(subst $(SOURCE_PREFIX)/,,$(abspath $<))\"'"

然后把__FILE__替换成__FILENAME__或者把上面的__FILENAME__替换成__FILE__

可能会有告警,但是无关紧要

但是如果设置了-Werror可能会编译不过,需要设定-Wno-builtin-macro-redefined

cmake

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wno-builtin-macro-redefined")

不然会有<command line>:41:9: error: redefining builtin macro [-Werror,-Wbuiltin-macro-redefined] 编译错误


ref

  1. https://stackoverflow.com/questions/8487986/file-macro-shows-full-path/16658858# 第一个答案是运行时裁剪,第二个答案更好。
  2. https://public.kitware.com/pipermail/cmake/2013-January/053117.html cmake做法
  3. https://blog.csdn.net/huojianying123456/article/details/70176755 makefile做法
  4. https://blog.csdn.net/yindongjie1221/article/details/90614261 这个写了一大堆,太复杂了。没用
  5. https://stackoverflow.com/questions/53182242/how-to-override-the-value-of-time-and-date-macros-using-command-line-opt 告警处理方法
Read More

subprocess一次挂死问题


用python脚本拉起后台进程,拉起的代码是这样的

cmds = cmd.split("|")
previous_result, p = None, None
for c in cmds:
    p = subprocess.Popen(shlex.split(c), stdin=previous_result, stdout=subprocess.PIPE, stderr=subprocess.PIPE, close_fds=True)
    previous_result = p.stdout
result, err = p.communicate()

我有两个二进制,一个二进制用的是glog做打印日志,默认输出到stderr,用这个拉起没有问题

另一个二进制使用的print打印日志,默认输出到stdout,用这个拉起会hang住

原因见参考链接1 默认是 shell=True , 如果调用了communicate,表示和stdout交互,除非显式输入EOF,否则会一直等待输入。解决方法就是加上shell=False ,不调用communicate

subprocess.Popen(shlex.split(cmd), stdin=subprocess.PIPE, stdout=subprocess.PIPE,stderr=subprocess.PIPE, close_fds=True, shell=False)

这样输出到stdout的二进制也能拉起。 我考虑过调整日志输出,不输出到stdout, 太麻烦了。作罢


ref

  1. https://stackoverflow.com/questions/2408650/why-does-python-subprocess-hang-after-proc-communicate
Read More

移动构造函数的生成时机


场景是想确定什么时候调用移动构造函数,参考链接有解释

  • X does not have a user-declared copy constructor,

  • X does not have a user-declared copy assignment operator,
  • X does not have a user-declared move assignment operator,
  • X does not have a user-declared destructor, and
  • the move constructor would not be implicitly defined as deleted.

比如下面这段代码

#include <iostream>
#include <tuple>

struct A{
A(){std::cout<<"ctor\n";}
};

int main()
{
   A a;
   A b(std::move(a));
}

无法判断

#include <iostream>
#include <tuple>

struct A{
A(){std::cout<<"ctor\n";}
A(const A& a)=delete;//{std::ignore = a; std::cout<<"copy"<<'\n';}
};

int main(){
   A a;
   A b(std::move(a));
}

这样会提示

prog.cc: In function 'int main()':
prog.cc:15:20: error: use of deleted function 'A::A(const A&)'
    A b(std::move(a));
                    ^
prog.cc:7:1: note: declared here
 A(const A& a)=delete;//{std::ignore = a; std::cout<<"copy"<<'\n';}

当有析构的时候也无法生成move ctor,比如

#include <iostream>
#include <tuple>
#include <memory>
struct A{
A(int a=0):a_(std::make_unique<int>(a)){std::cout<<"ctor\n";}
//A(const A& a)=delete;//{std::ignore = a; std::cout<<"copy"<<'\n';}
//A(A&& a){std::ignore = a; std::cout<<"move"<<'\n';}
~A(){std::cout<<"dtor\n";}
std::unique_ptr<int> a_;
};

int main()
{
   A a;
   A b(std::move(a));
}
/*
prog.cc:16:20: error: use of deleted function 'A::A(const A&)'
    A b(std::move(a));
                    ^
prog.cc:5:8: note: 'A::A(const A&)' is implicitly deleted because the default definition would be ill-formed:
 struct A{
        ^
prog.cc:5:8: error: use of deleted function 'std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = int; _Dp = std::default_delete<int>]'
In file included from /opt/wandbox/gcc-5.4.0/include/c++/5.4.0/memory:81:0,
                 from prog.cc:4:
/opt/wandbox/gcc-5.4.0/include/c++/5.4.0/bits/unique_ptr.h:356:7: note: declared here
       unique_ptr(const unique_ptr&) = delete;
*/

由于有dtor,没有默认生成move ctor,而是生成了copy ctor,而unique_ptr的copy ctor是删除的导致错误

如何捕捉编译器调用了什么构造函数?有没有例外情况?

貌似汇编能看出来https://godbolt.org/z/Nn4iod


ref

  1. https://zh.cppreference.com/w/cpp/language/move_constructor
  2. https://stackoverflow.com/questions/8283589/are-move-constructors-produced-automatically
Read More

base from member

一个遇到的技巧


场景是这样的,基类需要子类的成员变量来初始化父类

#include <streambuf>  // for std::streambuf
#include <ostream>    // for std::ostream

class fdoutbuf : public std::streambuf {
public:
    explicit fdoutbuf(int fd);
    //...
};

class fdostream : public std::ostream {
protected:
    fdoutbuf buf;
public:
    explicit fdostream(int fd) : buf(fd), std::ostream(&buf) {}
};

这种场景是无法编译通过的,因为需要基类先初始化

但交换初始化列表和基类构造函数的位置

    explicit fdostream(int fd) :  std::ostream(&buf), buf(fd) {}

这样语义不对,buf十有八九是错的。

需要提前把buf初始化。所以加了一个中间层,把buf放到另外一个基类里,让这个基类先于原来的基类。

class fdoutbuf : public std::streambuf {
public:
    explicit fdoutbuf(int fd);
    //...
};

struct fdostream_pbase {
    fdoutbuf sbuffer;
    explicit fdostream_pbase(int fd) : sbuffer(fd) {}
};

class fdostream : private fdostream_pbase, public std::ostream{
    typedef fdostream_pbase  pbase_type;
    typedef std::ostream     base_type;
public:
    explicit fdostream(int fd): pbase_type(fd), base_type(&sbuffer)  {}
    //...
};

就解决了。

boost提供了一个base_from_member类,用于托管你要抽离出来的字段

用法是这样的

#include <boost/utility/base_from_member.hpp>
#include <streambuf>  // for std::streambuf
#include <ostream>    // for std::ostream

class fdoutbuf : public std::streambuf {
public:
    explicit fdoutbuf(int fd);
    //...
};

class fdostream : private boost::base_from_member<fdoutbuf> , public std::ostream {
    // Helper typedef's
    typedef boost::base_from_member<fdoutbuf>  pbase_type;
    typedef std::ostream                        base_type;

public:
    explicit fdostream(int fd) : pbase_type(fd), base_type(&member) {}
    //...
};

base_from_member有个member字段就是要抽离出来托管的字段。

实际上这个类也没那么复杂,自己写一个base_from_member或者自己写个类似的类,不用base_from_member这种模板继承也是可以的

template < typename MemberType, int UniqueID = 0 >
class boost::base_from_member
{
protected:
    MemberType  member;
    base_from_member();
    template< typename T1 >
    explicit  base_from_member( T1 x1 );
    //...
};

ref

  1. 介绍
    1. http://sns.hwcrazy.com/boost_1_41_0/libs/utility/base_from_member.html boost相关中文翻译
    2. http://www.josuttis.com/cppcode/ronsmember.html
    3. https://remonstrate.wordpress.com/tag/base-from-member/
    4. https://remonstrate.wordpress.com/2011/01/26/boost-%e7%9a%84-utility/ 这个博客其实还可以。文章不错
    5. https://stackoverflow.com/questions/4815956/base-from-member-idiom-in-c
    6. https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Base-from-Member
  2. 一个类似的应用例子 https://stackoverflow.com/questions/16613191/stl-initializing-a-container-with-an-unconstructed-stateful-comparator 值得一看
Read More

std::condition_variable::notify_one 使用细节


官方的这个例子,真给我看傻了

#include <iostream>
#include <string>
#include <thread>
#include <mutex>
#include <condition_variable>
 
std::mutex m;
std::condition_variable cv;
std::string data;
bool ready = false;
bool processed = false;
 
void worker_thread()
{
    // Wait until main() sends data
    std::unique_lock<std::mutex> lk(m);
    cv.wait(lk, []{return ready;});
 
    // after the wait, we own the lock.
    std::cout << "Worker thread is processing data\n";
    data += " after processing";
 
    // Send data back to main()
    processed = true;
    std::cout << "Worker thread signals data processing completed\n";
 
    // Manual unlocking is done before notifying, to avoid waking up
    // the waiting thread only to block again (see notify_one for details)
    lk.unlock();
    cv.notify_one();
}
 
int main()
{
    std::thread worker(worker_thread);
 
    data = "Example data";
    // send data to the worker thread
    {
        std::lock_guard<std::mutex> lk(m);
        ready = true;
        std::cout << "main() signals data ready for processing\n";
    }
    cv.notify_one();
 
    // wait for the worker
    {
        std::unique_lock<std::mutex> lk(m);
        cv.wait(lk, []{return processed;});
    }
    std::cout << "Back in main(), data = " << data << '\n';
 
    worker.join();
}

为什么在notify_one之前需要unlock?

为什么notify_one不用在锁里?不怕丢吗(当然这个例子里不会丢,一共就俩线程)

notify_one有这么个注释

The effects of notify_one()/notify_all() and each of the three atomic parts of wait()/wait_for()/wait_until() (unlock+wait, wakeup, and lock) take place in a single total order that can be viewed as modification order of an atomic variable: the order is specific to this individual condition_variable. This makes it impossible for notify_one() to, for example, be delayed and unblock a thread that started waiting just after the call to notify_one() was made.

The notifying thread does not need to hold the lock on the same mutex as the one held by the waiting thread(s); in fact doing so is a pessimization, since the notified thread would immediately block again, waiting for the notifying thread to release the lock. However, some implementations (in particular many implementations of pthreads) recognize this situation and avoid this “hurry up and wait” scenario by transferring the waiting thread from the condition variable’s queue directly to the queue of the mutex within the notify call, without waking it up.

Notifying while under the lock may nevertheless be necessary when precise scheduling of events is required, e.g. if the waiting thread would exit the program if the condition is satisfied, causing destruction of the notifying thread’s condition_variable. A spurious wakeup after mutex unlock but before notify would result in notify called on a destroyed object.

这个注释能解释第一个notify_one不加锁

另外,wait必须要有条件,无条件wait容易丢失notify 已经写到官方建议里了 https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#cp42-dont-wait-without-a-condition

主要是notify_one多线程消费场景,不知道被谁消费了,所以指定某个满足条件的去wait wait一个触发条件。这样配对用

在这个讨论里, 有个结论,也有人提问

unlocking the mutex before notifying is an optimisation, and not essential. I intentionally didn’t do that, to keep the example simple. There could be a second guideline about that point, but it’s not related to the “always use a predicate” rule. I would object strongly to complicating the example by doing that.

anyway 提前unlock算是个人选择(有优化),不提前unlock也没啥大的影响


说句题外话

最近在看一个时间队列实现,这个cond var用的让我有点迷惑

class TimerQueue {
public:
    TimerQueue() {
        m_th = std::thread([this] { run(); });
    }
 
    ~TimerQueue() {
        cancelAll();
        add(0, [this](bool) { m_finish = true; });
        m_th.join();
    }
 
    uint64_t add(int64_t milliseconds, std::function<void(bool)> handler) {
        WorkItem item;
        item.end = Clock::now() + std::chrono::milliseconds(milliseconds);
        item.handler = std::move(handler);
 
        std::unique_lock<std::mutex> lk(m_mtx);
        uint64_t id = ++m_idcounter;
        item.id = id;
        m_items.push(std::move(item));
        lk.unlock();
 
        // Something changed, so wake up timer thread
        m_checkWork.notify();
        return id;
    }
  ....

注意是先lk.unlock再notify,这个unlock有必要么?

后来发现是用cond var封装了一个 信号量,自己用内部的mtx。和这个没啥关系。

这个代码给我整晕了。rocksdb的timerqueue抄了这个,但是体验没那么迷糊


ref

  • https://www.crazygaze.com/blog/2016/03/24/portable-c-timer-queue/
  • https://en.cppreference.com/w/cpp/thread/condition_variable

Read More

^