Archive for 算法-编程

perf工具应该都听说过,我也试了一把,感觉很好很强大。 先使用sudo perf stat ./a.out命令,查看一下性能统计信息。结果展示为: Performance counter stats for './a.out': 2,740.62 msec task-clock # 3.903 CPUs utilized 39 context-switches # 0.014 K/sec 2 cpu-migrations # 0.001 K/sec 128,974 page-faults # 0.047 M/sec 10,394,863,898 cycles # 3.793 GHz 14,055,693,753 instructions # 1.35 insn per cycle 2,865,438,627 branches # 1045.545 M/sec 17,411,072 branch-misses # 0.61% of all branches 0.702237190 seconds time elapsed 2.533414000 seconds user 0.208445000 seconds sys 因为程序基本跑内存的,这里cpu使用比较高,就是开始的时候读了文件。四个线程高达3.9的使用率 context-switches 是进程上下文切换,这个不知道为啥,可能我系统跑的东西太多了。 CPU-migrations 这个是cpu迁移次数,没办法避免吧,程序跑的多,或者需要cpu绑定。 page-faults 这个感觉有点高,不知道为啥,我这还没涉及文件读写相关,已经这么高了。 branch-misses 这个感觉也比较高,看看使用分支预测改善一下,能不能好。这个需要对比一下。 获取程序的cpu运行时间统计,sudo perf record -e cpu-clock ./a.out,命令会生成perf.data文件,使用perf report查看报告 下边还有个直接展示的高级货,叫做火焰图。用perl写的,感觉好强大,以后可以稍微研究一下怎么生成的。 需要先clone下代码来:git clone --depth=1 https://github.com/brendangregg/FlameGraph.git 上一步收集信息的时候必须加-g参数,用来收集堆栈信息,不然后边生成图像的时候会报错。 sudo perf record -g ./a.out 数据解析 sudo perf script -i perf.data &> perf.unfold 数据折叠 ./stackcollapse-perf.pl perf.unfold &> perf.folded 图像生成 ./flamegraph.pl perf.folded > perf.svg 生成的图片用chrome查看是有效果的,我用ubuntu自带的图片查看软件,发现不能交互。 我发现对于递归程序,展示的不太友好,虽然能从调用栈中获取到递归深度,但是调用的函数差不多都放到递归最里边了,可能是取样的问题嘛,,

Continue

Callgrind是valgrind的一个工具,能够分析程序运行效率,帮助找到程序瓶颈。 命令tool知道使用的valgrind的工具, valgrind --tool=callgrind ./a.out 运行完之后会生成一个callgrind.out.PID文件,然后执行下面命令进行分析 callgrind_annotate callgrind.out.PID 这个命令能够展示每个调用函数对应的执行指令的次数,展示已经排序,可以优先优化最顶部的函数。 cachegrind也是valgrind的一个工具,主要分析内存使用情况的,比如cpu cache的使用等。 简单使用命令: valgrind --tool=cachegrind ./a.out ==12810== ==12810== I refs: 13,413,053,205 ==12810== I1 misses: 3,851 ==12810== LLi misses: 3,552 ==12810== I1 miss rate: 0.00% ==12810== LLi miss rate: 0.00% ==12810== ==12810== D refs: 4,991,204,111 (3,140,940,594 rd + 1,850,263,517 wr) ==12810== D1 misses: 49,675,548 ( 38,504,518 rd + 11,171,030 wr) ==12810== LLd misses: 29,710,307 ( 19,488,129 rd + 10,222,178 wr) ==12810== D1 miss rate: 1.0% ( 1.2% + 0.6% ) ==12810== LLd miss rate: 0.6% ( 0.6% + 0.6% ) ==12810== ==12810== LL refs: 49,679,399 ( 38,508,369 rd + 11,171,030 wr) ==12810== LL misses: 29,713,859 ( 19,491,681 rd + 10,222,178 wr) ==12810== LL miss rate: 0.2% ( 0.1% + 0.6% ) 看着好像程序我的程序允许的比预期的缓存命中高很多,看官方文档说的。On a modern machine, an L1 miss will typically cost around 10 cycles, an LL miss can cost as much as 200 cycles, and a mispredicted branch costs in the region of 10 to 30 cycles. Detailed cache and branch profiling can be very useful for understanding how your program interacts with the machine and thus how to make it faster.现代机器,L1缓存丢失通常花费10个cpu周期,LL丢失花费200个周期,分支预测错误花费10-30个周期,所以这部分性能分析很重要啊。 LL指的是最后一级的cpu缓存,许多cpu架构可能有多级缓存,L1和LL具有代表性,所以只分析了这两种。 程序还是会生成一个cachegrind.out.PID文件,同样可以具体分析每个函数的内存使用情况 cg_annotate cachegrind.out.12810 这俩工具在官方手册上,每个一章进行介绍,具体也没研究,先初步了解一下

Continue

Valgrind可以模拟cpu执行你的程序,然后给出内存使用或者程序错误信息。之前只使用过gdb来调试程序逻辑错误,现在准备多看几个,包括性能方面的调试。 安装直接使用的apt源安装的,使用也比较简单。直接valgrind ./a.out允许程序,运行过程中会给出程序建议。 这个程序我有一个一百万长度的uint64的数组,提示了"Invalid write of size 8"的错误,Warning: client switching stacks? SP change: 0x6c55ef0 --> 0x64b4c60 to suppress, use: --max-stackframe=8000144 or greater 我搜了一下发现说是栈空间消耗太大,我改成calloc,两个错误提示都没了。 ==15130== HEAP SUMMARY: ==15130== in use at exit: 457,122,934 bytes in 4,659,095 blocks ==15130== total heap usage: 4,659,118 allocs, 23 frees, 457,166,878 bytes allocated ==15130== ==15130== LEAK SUMMARY: ==15130== definitely lost: 48,850,904 bytes in 177,241 blocks ==15130== indirectly lost: 400,271,992 bytes in 4,481,851 blocks ==15130== possibly lost: 8,000,000 bytes in 1 blocks ==15130== still reachable: 38 bytes in 2 blocks ==15130== suppressed: 0 bytes in 0 blocks ==15130== Rerun with --leak-check=full to see details of leaked memory 最后有内存统计信息,malloc后没有free的内存都会在统计。下面这段解释是我摘自网上的,我感觉不太准确(可能是valgrind检测的就不太准确),但是个参考。 Memcheck将内存泄露分为两种,一种是可能的内存泄露(Possibly lost),另外一种是确定的内存泄露(Definitely lost)。 Possibly lost 是指仍然存在某个指针能够访问某块内存,但该指针指向的已经不是该内存首地址。Definitely lost 是指已经不能够访问这块内存。而Definitely lost又分为两种:直接的(direct)和间接的(indirect)。直接和间接的区别就是,直接是没有任何指针指向该内存,间接是指指向该内存的指针都位于内存泄露处。在上述的例子中,根节点是directly lost,而其他节点是indirectly lost。 possibly lost: 8,000,000 bytes in 1 blocks这个就是我那个一百万的数组malloc后没有free释放的,然后我free后,这行就没了。但我指针没修改,是个多线程的内存申请,但是只检测出一个来。四个线程没一个都malloc了。 Valgrind User Manual写的很详细,好多功能,一时半会也试不完。先体验一把,有需求再说。

Continue

写个uint64_t的程序,涉及大小端的转换。 uint64_t x = 0x0123456789ABCDEF; On a 32-bit little-endian processor, it will appear in memory as EF CD AB 89 67 45 23 01 On a 64-bit little-endian processor, it will appear in memory as EF CD AB 89 67 45 23 01. On a 32-bit big-endian processor, it will appear in memory as 01 23 45 67 89 AB CD EF. On a 64-bit big-endian processor, it will appear in memory as 01 23 45 67 89 AB CD EF. 转换涉及#include uint64_t htobe64(uint64_t host_64bits); uint64_t htole64(uint64_t host_64bits); uint64_t be64toh(uint64_t big_endian_64bits); uint64_t le64toh(uint64_t little_endian_64bits); The functions with names of the form "htobenn" convert from host byte order to big-endian order. The functions with names of the form "htolenn" convert from host byte order to little-endian order. The functions with names of the form "benntoh" convert from big-endian order to host byte order. The functions with names of the form "lenntoh" convert from little-endian order to host byte order.、 看了一下头文件,判断是否是小端序,然后采用不同转换方式。涉及bits/byteswap.h头文件。没时间细看了,先记录,以后有时间再看。

Continue

零拷贝不是一个新技术了,之前一直接触不到这么底层的技术,最近看的比较多,所以从代码上研究了一下。 在应用程序做数据传输等操作涉及系统调用,而为了提高性能,就是从减少系统调用次数和减少内核空间和用户空间的数据拷贝次数入手的。 具体的我也没看代码,都是从网上总结学来的。 像mmap方式,是减少了内核空间和用户空间的数据拷贝,使用映射还是指针的能够共享内核空间。但涉及比如把一个文件内容通过网络发送的操作,还涉及内核空间的数据拷贝。 sendfile和splice就是解决内核空间的数据copy的,我看linux手册是page buffer指针的复制,所以没有做数据的copy。指针是通过pipe buffer存储的。 ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count); ssize_t sendfile64(int out_fd, int in_fd, loff_t *offset, size_t count); 这俩的区别是sendfile64适合传送大文件,offset类型也决定了适合做大文件的偏移用。但不仅仅是这里,看源码,sendfile指定offset之后,会设置复制的最大值为MAX_NON_LFS,这个值我没找,但是类型初步判断加文档判断来说,最大不到2G(看文档是不到2G).(后来还是去找了,#define MAX_NON_LFS ((1UL<<31) - 1), 文档写的是0x7ffff000 (2,147,479,552) ) 我看了一下函数实现的源码,尽量只看流程,不去细看实现,看看优化能注意的点。 通过看源码,发现最好是不指定offset这个参数,因为指定这个参数后,会多两次的内核函数调用,涉及用户空间和内核空间的数据拷贝,get_user,put_user,copy_from_user。然后统一调用do_sendfile函数。而如果offset为NULL的时候,在do_sendfile函数里,是通过文件的offset来复制数据的。所以尽量不指定offset是最好的,但如果提前设置文件offset还要涉及系统调用,具体权衡就不知道了。 在do_sendfile里没啥可以细讲的,流程大部分能猜到什么意思。主要最后调用do_splice_direct。 这里有个疑问就是,为什么offset要用指针类型,而不能直接传一个数字,我猜可能是历史遗留问题吧,可能接口没办法变动了。 do_splice_direct函数跟splice是在一个文件,可以差不多猜到,俩的实现原理是一样的了。 do_splice_direct里splice_desc sd定义输出文件的信息。 然后调用了splice_direct_to_actor,这里有一个pipe = current->splice_pipe;这个pipe是在linux的进程管理的pcb(task_struct)中,这里边有一个splice_pipe,用来存储splice()上一次使用的过的pipe。这里是判断如果current->splice_pipe不存在,就新创建一个,然后缓存到current->splice_pipe。然后调用do_splice_to,流程跟splice复制文件到pipe的流程差不多。 splice里直接调用do_splice,这里分三种情况,in和out都有pipe时,调用splice_pipe_to_pipe;in为pipe时调用do_splice_from,out为pipe时调用do_splice_to。这俩单个的也涉及offset的用户空间和内核空间复制的问题。 do_splice_from我直接看的default_file_splice_write,调用splice_from_pipe。里边初始化splice_desc sd,存了要写的文件信息,调用__splice_from_pipe,splice_from_pipe_feed里是将pip内容关联复制到文件。 do_splice_to也是直接看default_file_splice_read,初始化一个结构体splice_pipe_desc spd,看起来是存储pagebuffer信息的,具体看不太懂,也没去查,初始化spd空间,kernel_readv应该是用来吧in的page buffer内容的指针存入spd了,nr_pages_max = PIPE_DEF_BUFFERS这个值是16(看文档在内核版本2.6.35之后,可以通过fcntl的F_GETPIPE_SZ和F_SETPIPE_SZ进行设置),好像是最大页数,最后调用splice_to_pipe(pipe, &spd);好像就是从spd里刚保存的页信息关联复制数据到pipe。 vmsplice支持从用户空间复制数据到pipe,反方向的复制也支持,但是是内存数据的真复制。 tee复制管道内容,从一个复制到另一个 总结一下就是,文件的传输使用sendfile比较好,他会缓存pipe,并且少一次的系统调用。如果用splice,需要先从一个文件到pipe,然后pipe到另一个文件,虽然也没有真正复制,但是系统调用是两次。 splice可以实现类似代理服务器数据转发的功能,使用一个pipe连接两个socket。 上边说的都是PIPESIZE。在Linux 2.6.11之前,PIPESIZE和PIPEBUF实际上是一样的。在这之后,Linux重新实现了一个管道缓存,并将它与写操作的PIPEBUF实现成了不同的概念,形成了一个默认长度为65536字节的PIPESIZE,而PIPEBUF只影响相关读写操作的原子性,一般为page大小,内核每次操作量。PIPESIZE的最大值在/proc/sys/fs/pipe-max-size里进行设置。从Linux 2.6.35之后,在fcntl系统调用方法中实现了F_GETPIPE_SZ和F_SETPIPE_SZ操作,来分别查看当前管道容量和设置管道容量。

Continue

照着别人写的js库,重新写了一个c版本的,也学了一下其中的算法。为什么需要松圆盘采样这个算法进行采样,是因为存随机其实也不是纯随机,随机分布不均匀。而这样生成的伪随机(psuedorandom)数列,很大程度保证了随机的均匀性。 开始以为很难,边写边学发现其实原理不太难。 基本思想就是,初始点可以给定或者随机。 第二步根据初始点,按照一定角度生成不同方向的新点,其中这个角度是关键。通过三角函数,保证生成的新点到初始点的距离为r。 第三步判断新生成点跟周围两个区域的点的距离,保证距离大于r。如果点不合法,则改变角度,重新生成。有一个重试次数保证重新生成上限,如果达到上限还没有找到一个新点,就说明这个点有问题,进行删除。如果合法,生成的点作为一个选择点并插入队列,作为下一次判断的初始点 第四步,队列中有其他生成点,继续上边第二第三步,直到没有生成点可以用。 期间我看js版本生成随机数的时候用的自己写的伪随机生成数,然后我就看了一下用的库,发现里边用了一个Thomas Wang写的 hash生成随机数,又简单看了一下。都是位操作,也懒得找原理看。先记一下,以后用到再看原理吧。

Continue

在setup.py里只需要写很少的代码,所有配置都放在setup.cfg里。如果参数通过setup()传入,以setup.cfg里的配置为准 #!/usr/bin/env python from setuptools import setup setup( setup_requires=['pbr'], pbr=True, ) setup.cfg里配置跟ini文件差不多。 [files]定义代码包里文件的安装目录,其中packages指定要安装的包;namespace_packages制定有命名空间的包;data_files指定要安装的文件的源地址和目的地址; [entry_points]指定模块入口点的运行脚本和模块。主要定义一些控制台脚本,pbr会自动生成这些脚本,做到脚本的跨平台。等号后边就相当于脚本执行调用的函数 随便看了两眼pbr源码: console_scripts就是两行,先import,后执行。 wsgi_scripts比较多,从代码来看,可以直接当脚本启动一个server或者,返回一个app提供给wsgi调用 知道了这个,基本就了解openstack一些模块入口函数怎么找了 看了看neutron service启动命令为 /usr/bin/neutron-server --config-file /etc/neutron/neutron.conf --config-file /etc/neutron/plugin.ini neutron-server脚本在console_scripts里定义。 openstack rpm包打包项目https://github.com/openstack/rpm-packaging

Continue

今天看见了别人总结的,感觉太有用了。 num&0x1, 为1说明是奇数,为0说明是偶数。因为只看二进制位的最后一位 a % b,当底b为2的n次幂的时候,可以改写成 a & (b - 1) 原理也是按位只看最后n位的数据,高位直接不用看。 我这个还专门看了一下有多块,数量级差的太多了, 但初步能看见的时间来说,1亿次差了0.1秒,从时间成本上来说其实差别不大。 看了一下,差了四条汇编指令,还得考虑取数据的时间

Continue

写了个汇编程序,照着别人的写的,其中有个系统调用,然后就去搜了一下linux系统的系统调用表。这一搜不要紧,搜出问题来了。 我找到了两个版本,一个x86-64版本的,一个i386版本的。比如32位的sys_exit系统调用里调用号%eax为1,64位里sys_exit调用号%rax为60,这个不重要。然后我看了一下我的代码,我用了32位的调用号,功能也是32位的。第一反应就是编译的elf是32位的,然后我看了一下readelf -h 64,为64位。后来发现还有个简单命令 直接file 64就能看。然后我就觉得很不可思议。 接着我查了两个版本的头文件在哪里,看怎么用的。学到很多东西。比如查看调用头文件 printf SYS_exit | gcc -include sys/syscall.h -E - echo '#include ' | gcc -E -x c -l echo '#include ' | gcc -E -x c - | egrep '# [0-9]+ ' | awk '{print $3;}' | sort -u 发现是找的是64位的,然后我更糊涂了。主要就这几个文件 # 1 "/usr/include/x86_64-linux-gnu/asm/unistd_64.h" 1 3 4 # 14 "/usr/include/x86_64-linux-gnu/asm/unistd.h" 2 3 4 # 25 "/usr/include/x86_64-linux-gnu/sys/syscall.h" 2 3 4 # 1 "/usr/include/x86_64-linux-gnu/bits/syscall.h" 1 3 4 # 1 "/usr/include/x86_64-linux-gnu/asm/unistd_32.h" 看头文件确实是看是否定义i386,但是我其实是没用头文件的,直接写的中断号,用as编译的代码,没有使用gcc。 然后我查unistd_32.h和unistd_64.h的区别,然后找到原因了。 首先我64位系统,默认都是编译的64位二进制这个没啥问题。汇编和链接的时候可以制定生成32位: as e.s --32 -o 32.o ld 32.o -o 32 我生成32位汇编也是一样能执行的。 其次,32位汇编和64位汇编所使用的系统中断是不一样的。intel和amd都提供了硬件中断,而且还不兼容。为了兼容尽量使用的一下两个: 32位: sysenter sysexit. 64位: syscall sysret. 与这个相对应的是软件中断,那个速度比较慢,也是比较老的遗留下来的。int $0x80。 然后我代码用的是这个老的软中断。软中断用的都是32位的调用号,而且在64位的系统里,同样是可以使用的,因为他只使用低32位的寄存器。所以问题就解决了,我是用的软中断导致的,应该看软中断的调用号,而不是看编译的二进制是64位还是32位。

Continue

主要看pymain_run_filename,是文件执行pymain_open_filename,不是文件赋值fp = stdin,最后执行pymain_run_file(fp, pymain->filename, cf)。看这里应该交互和文件执行都在这一个里边的。 pymain_open_filename就是打开文件返回句柄。 pymain_run_file文件里,主要就是调用PyRun_AnyFileExFlags。下面应该与main.c没关系了,主要在Python/pythonrun.c里了. pymain_repl里调用 PyRun_AnyFileFlags,然后也是调用的PyRun_AnyFileExFlags。 PyRun_AnyFileExFlags里, Py_FdIsInteractive判断是否是交互模式,如果是调用PyRun_InteractiveLoopFlags,里边有个do,这个不看了。如果不是调用PyRun_SimpleFileExFlags, 先调用PyImport_AddModule,interp->modules里插入了__main__,对我没啥用。maybe_pyc_file判断是否是pyc文件,比较了文件后缀,MagicNumber. MAGIC_NUMBER是在Lib/importlib的_bootstrap_external.py文件里定义的,直接写在python文件里了。 如果像pyc文件,关闭文件句柄,重新打开文件,然后调用set_main_loader,再调用run_pyc_file。 如果不像pyc文件,调用PyRun_FileExFlags。 set_main_loader中通过loader_name,从importlib/_bootstrap_external中获取loader,源码为SourceFileLoader,pyc为SourcelessFileLoader,设置到__loader__ run_pyc_file,先比较MagicNumber是否匹配,然后PyMarshal_ReadLastObjectFromFile读取文件,其中的就不看了,不关心。PyEval_EvalCode应该是执行代码了,这个也不看了。 然后就完结了。 import 相关 第一篇里边的pymain_init_sys_path,调用pymain_get_importer,然后调用PyImport_GetImporter,然后调用get_path_importer,然后从path_hooks里找合适的import的方法进行导入 pymain_update_sys_path更新sys.path config_init_module_search_paths里有个Py_GetPath(,这里比较乱,调用了几次_PyPathConfig_Init,我也没仔细看。_PyPathConfig_Calculate里应该是初始化的path,没仔细看。 第三方库的搜索路径添加在initsite,导入Lib/site.py模块,执行addusersitepackages里添加的

Continue