Strict alising的坑

1

int foo(int *x, long *y) {
  *x = 0;
  *y = 1;
  return *x;
}

会被优化成

foo2:   movl    $0, (%rdi)
        xorl    %eax, %eax
        movq    $1, (%rsi)
        ret

因为编译器会认为,两个不能alising的指针,一定不会指向同一块内存区域,所以会推断出结果一定是0

所以啊,之前网上很多(float *)(&int_var)然后乱搞的做法都容易爆炸……

继续阅读“Strict alising的坑”

TRASH A dynamic LC-trie and hash data structure

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.2143

传统Trie的优化。

  • path compression: 连续若干个只有一个孩子节点可以压成一个
  • LC(level compression):若某一节点下面第k层的子树都非空,那么中间的k-1层都可以省略,直接把第k层的2^k个子树都接到自身
    • 压缩原理:现代指针大小8byte远远大于char的大小
  • TRASH:在每个插入Trie的子串前面都加一个hash值,这样能在LC的基础上分布更均匀