哪些情况会导致"Undefined Reference Error"

“Undefined Reference Error” 是在程序链接(link)时经常遇到的错误,字面意思来说就是没有找到已经定义的引用,在编译器无法找到用户所使用的变量或函数:

一、缺失头文件

例如声明变量 uint64_t tmp,但没有在开头包含 #include<stdint.h>

例如使用 memset() 需要包含头文件 string.h 或 memory.h

二、缺失目标文件或者库文件(.a .o .so …)

编译器查找用户函数,首先会在本文件中的函数中找,然后在系统环境变量定义的目标文件/库(.a .o .so …)文件中找,最后在链接的目标文件/库文件(.a .o .so …)中寻找用户函数;如果没有找到则报”Undefined Reference Error”错

四、库(目标)文件链接顺序有误

库文件的链接顺序是:依赖的库A 放后面,被依赖的库B 放前面。如果A 和B 相互依赖,则使用A B A 或者B A B 的。

例如main 文件中引用func 文件中函数,则编译顺序为main.o func.o

五、C 函数和C++函数引用问题

C++ 程序链接时可以链接C 的库文件,但在.cc(.cpp) 中引用头文件时需要通过extern “C”{ #include “func.h”} 的方式引用该头文件,否则会提示”Undefined Reference Error”

C 程序无法链接C++ 库文件,否则会提示”Undefined Reference Error”,找不到引用C++ 函数的引用

 

参考:http://blog.csdn.net/aiwoziji13/article/details/7330333

内存拷贝速度(memcpy())和异或速度

内存拷贝(memcpy())和异或(bit-wise XOR)是程序中运行最快的操作之一,其速度受到CPU、内存和编译器(GCC版本)的影响。

内存拷贝memcpy(des, src, len) 则是将长度为len 的数据从地址src 拷贝到地址des 。

按位异或(异或)可以分为几类:

  1. a^b:两个数值的异或。相当于两个寄存器内值在CPU 中计算异或,大多数CPU 中一个时钟周期完成。速度取决于CPU 的频率,频率越高,速度越快。
  2. a^Region:一个数值与一块内存Region 中的每个值异或,结果保存在Region 中,速度相当于顺序访存。
  3. RegionA = RegionA^RegionB:两块内存中对应位置上的值异或。
  4. RegionC = RegionA^RegionB:两块内存中对应位置上的值异或,结果保存在另一块内存中。

四类异或速度依次递减。平常中越到的是第3 种,本文中异或速度也是第3 种。

继续阅读

CPU Cache 如何影响程序性能

CPU Cache 是CPU 中用于减少平均访问内存时间的高速存储器件。较内存使用的DRAM ,cache 使用的SRAM 速度更快、价格也更高,所以cache 容量一般较小。与cache 相关的概念有:cache line,associativity(相连性),L1 cache,L2 cache ,cache 命中,cache 失效等。

cache 按层次分为L1、L2 甚至L3级cache,速度依次递减,容量依次增大。CPU 直接能够读取的只有L1 cache。在大多数处理器包括Intel CPU 中,cache按照缓存的指令或者数据分为数据缓存和指令缓存(如L1d 和L1i) 。在多核的CPU 中,每个核心具有独立的L1 级cache,往往公用L2 级cache。公用cache 可能存在多线程缓存污染等问题。

cache 和内存传输的最小单位是cache line,一般大小为64 bytes。cache 每次从内存读取或者写入cache line 大小的数据,而不是我们在程序中定义的数据结构的大小。cache lines 之间的替换常用的是LRU 算法。如果CPU 读取的数据在cache 中,则cache 命中(cache hit),否则cache 失效(cache miss)。每一级的cache 失效将到下一级cache 中寻找数据,直至内存。cache miss 是有开销的,小于访存时间,大于cache hit 时间。每次cache 失效,CPU 就会处于停滞(stall)状态,直至缓存读取到所需要的数据。

因为cache 容量远小于内存(有种说法是1:1000),内存和cache 之间存在映射关系(associativity)。按照映射关系不同,分为:全相连映射(fully associative),多路组相连映射(N-way set associative)和直接映射(directly mapped)。全相连映射缓存和内存是全映射关系,内存中任何一块数据都可以没有限制地放的任何一个cache line 中,缓存利用率高,但设计复杂未被采用;直接映射将一块内存地址映射到一个cache line(the number of cache line = memory address%number of cache lines,其中内存地址以cache line 大小为单位),直接映射设计起来简单,但利用率低;多路组相连映射缓存更为常见,是设计复杂度和性能的权衡。它将一块内存映射到不同路上的cache lines 中,如果是8-路组相连,则一块内存映射到8-路上的cache lines 上(the number of cache line = memory address%(number of cache lines/number of ways)。不同路上的负责缓存相同内存的缓存构成一个集合set,不同set 缓存不同内存地址的数据。number of set = cache size/(ways of associativity * size of cache line)。

继续阅读

和NTL(Number Theory Library) 比较有限域上矩阵求秩

下载了NTL(Number Theory Library),简单对正方矩阵(square matrix)求秩和nclib 进行了测试,测试参数如下:

  • 有限域大小为:GF(28)、GF(216)和GF(232)
  • 正方矩阵维度从2 到255(横坐标)

测试方法:随机生成指定大小的矩阵,计算其秩大小,仅计算一次。

测试结果如下(分别是GF(28)、GF(216)和GF(232) 域上的结果):

 

320816

在域大小为GF(28)和GF(216)时差别还不是很大,但为GF(232) 时,计算速度差距就有些大了,主要还是矩阵的表示方法不同,nclib 用uint_8/uint_16/uint_32 类型表示三个域中元素,而NTL 中域中元素全部二进制表示,计算秩更多的使用了单个元素求逆和而不是像nclib 建立域上计算表。比如GF(232) 上进行求秩,方阵很小的时候速度也很慢,是把有限域上计算表(乘法表、对数表)时间给算进去了。nclib 可以对此进行改进。

相关文件

求组合数、排列数等

最近写程序一直遇到组合数,排列数等问题。文章介绍程序实现全排列$A_{n}^{n}$、组合$C_{n}^{k}$ 中每个项的列举。

全排列$A_{n}^{n}$ 有顺序的排列n 个数;

组合$C_{n}^{k}$ 从n 个数中选取k 个进行无顺序的组合;

附:一般性的排列$A_{n}^{k}$ 可以通过组合和全排列一起完成。

继续阅读