Posted on

常用HASH算法 代码 & 比较

  • 常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。
  • 常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。

1
2
3
4
5
6
7
8
9
Hash函数  数据1 数据2   数据3    数据4     数据1得分 数据2得分    数据3得分    数据4得分     平均分
BKDRHash    2   0     4774    481       96.55   100         90.95       82.05       92.64
APHash      2   3     4754    493       96.55   88.46       100         51.28       86.28
DJBHash     2   2     4975    474       96.55   92.31       0           100         83.43
JSHash      1   4     4761    506       100     84.62       96.83       17.95       81.94
RSHash      1   0     4861    505       100     100         51.58       20.51       75.96
SDBMHash    3   2     4849    504       93.1    92.31       57.01       23.08       72.41
PJWHash     30  26    4878    513       0       0           43.89       0           21.95
ELFHash     30  26    4878    513       0       0           43.89       0           21.95

Continue reading "常用HASH算法 代码 & 比较"

Posted on

通过完整示例来理解如何使用 epoll

网络服务器通常使用一个独立的进程或线程来实现每个连接。由于高性能应用程序需要同时处理大量的客户端，这种方法就不太好用了，因为资源占用和上下文切换时间等因素影响了同时处理大量客户端的能力。另一种方法是在一个线程中使用非阻塞 I/O，以及一些就绪通知方法，即当你可以在一个套接字上读写更多数据的时候告诉你。

Continue reading "通过完整示例来理解如何使用 epoll"

Posted on

select,poll,epoll的归纳总结区分

1 Select、Poll与Epoll简介

Select

select本质上是通过设置或者检查存放fd标志位的数据结构来进行下一步处理。这样所带来的缺点是：

1 单个进程可监视的fd数量被限制

2 需要维护一个用来存放大量fd的数据结构，这样会使得用户空间和内核空间在传递该结构时复制开销大

3 对socket进行扫描时是线性扫描

Poll

poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态，如果设备就绪则在设备等待队列中加入一项并继续遍历，如果遍历完所有fd后没有发现就绪设备，则挂起当前进程，直到设备就绪或者主动超时，被唤醒后它又要再次遍历fd。这个过程经历了多次无谓的遍历。

它没有最大连接数的限制，原因是它是基于链表来存储的，但是同样有一个缺点：大量的fd的数组被整体复制于用户态和内核地址空间之间，而不管这样的复制是不是有意义。

poll还有一个特点是“水平触发”，如果报告了fd后，没有被处理，那么下次poll时会再次报告该fd。

Epoll

epoll支持水平触发和边缘触发，最大的特点在于边缘触发，它只告诉进程哪些fd刚刚变为就需态，并且只会通知一次。

在前面说到的复制问题上，epoll使用mmap减少复制开销。

还有一个特点是，epoll使用“事件”的就绪通知方式，通过epoll_ctl注册fd，一旦该fd就绪，内核就会采用类似callback的回调机制来激活该fd，epoll_wait便可以收到通知

注：水平触发（level-triggered）——只要满足条件，就触发一个事件(只要有数据没有被获取，内核就不断通知你)；边缘触发（edge-triggered）——每当状态变化时，触发一个事件。

Continue reading "select,poll,epoll的归纳总结区分"

Posted on

Linux C 开发 - libevent

Libevent介绍
libevent是一个事件触发的网络库，适用于windows、linux、bsd等多种平台，内部使用select、epoll、kqueue等系统调用管理事件机制。著名分布式缓存软件memcached也是libevent based，而且libevent在使用上可以做到跨平台，而且根据libevent官方网站上公布的数据统计，似乎也有着非凡的性能。
官方网站：http://libevent.org/
英文文档：http://www.wangafu.net/~nickm/libevent-book/
中文文档：http://www.cppblog.com/mysileng/category/20374.html
Libevent是基于事件的网络库。说的通俗点，例如我的客户端连接到服务端属于一个连接的事件，当这个事件触发的时候就会去处理。
该文章阅读过程中，请结合下面的socket例子，可能会更加清晰的理解每一个接口的用法。

Continue reading "Linux C 开发 - libevent"

Posted on

常用的C/C++框架和库、开发资源

- 1. Webbench

Webbench是一个在Linux下使用的非常简单的网站压测工具。它使用fork()模拟多个客户端同时访问我们设定的URL，测试网站在压力下工作的性能，最多可以模拟3万个并发连接去测试网站的负载能力。Webbench使用C语言编写, 代码实在太简洁，源码加起来不到600行。

下载链接：http://home.tiscali.cz/~cz210552/webbench.html

Continue reading "常用的C/C++框架和库、开发资源"

Posted on

需找新的美猴王——约瑟夫环 猴王问题

猴王问题：
某森林中有n只猴子在商量猴王选举问题，所有的猴子都想当猴王，
因此大家商量了一个选举办法如下：
所有的猴子围成一圈，先从第一个猴子开始报数，报数到13的猴子就出列。
紧接着的下一个猴子，又从1开始进行新的一轮报数，报数到12的猴子再出列；
依此重复下去，每一轮报数都比上一轮的报数少1，直到报数减为1之后，又从13开始报数。
直到原列中只剩下一个猴子为止，这个猴子就是猴王。

 

试设计一个程序求出猴王。
Continue reading "需找新的美猴王——约瑟夫环 猴王问题"

Posted on

C/C++静态连接PHP5：libphp5.a以及libphp5.la的使用

C/C++静态连接php5需要使用到libtool，主要使用libphp5.la。

编译成目标文件：

1
libtool --mode=link cc -export-dynamic -I/usr/include -g -O2 /home/john/Documents/php-5.5.7/libs/libphp5.la ./main.lo -o main

通过libphp5.la静态连接libphp5.a：

1
libtool --mode=compile cc -I/usr/local/include/php -I/usr/local/include/php/Zend -I/usr/local/include/php/main -I/usr/local/include/php/TSRM -I/usr/local/include -g -O -c main.c

不过生成的可执行文件很大，php5.5的话大概有27MB，包含一些基本的内置扩展，这样和使用动态连接没有什么区别了，动态链接库也有27MB。

Posted on

Embedding the PHP Interpreter

Few weeks ago I had to use iDealer PHP library from C++. I did that and now the code has been tested and is working fine.

I had embedded Python before, so I knew what I had to do: initialize the PHP interpreter, create some variables, execute PHP code, read some PHP variables and shutdown the PHP interpreter. The first and the last step will be executed only once for whole server lifetime (performance considerations) while steps 2-4 will be executed for every request. To keep it simple, I will use global PHP variables and global symbol table known as EG(symbol_table) in C code and $GLOBALS in PHP code. To keep it even more simple, I will use only string PHP variables and will create a correct type ( array for example) in PHP code.

I can’t assure that everything written below is 100% correct, since PHP documentation was really poor, especially compared to Python. I found a part of solutions in Zend source code, so there might be a better and cleaner solutions. I also spent some time using gdb (The GNU Debugger) and valgrind and chasing bugs.
Continue reading "Embedding the PHP Interpreter"

Posted on

32位和64位系统区别及int字节数

一、64位系统和32位有什么区别？

1、64bit CPU拥有更大的寻址能力，最大支持到16GB内存，而32bit只支持4G内存

2、64位CPU一次可提取64位数据，比32位提高了一倍，理论上性能会提升1倍。但这是建立在64bit操作系统，64bit软件的基础上的。

什么是64位处理器？

之所以叫做“64位处理器”，是因为电脑内部都是实行2进制运算，处理器（CPU）一次处理数据的能力也是2的倍数。8位处理器、16位处理器、32位处理器和64位处理器，其计数都是2的倍数。一次处理的数据越大，该电脑处理信息的能力越来越大；因此64位处理在先天就比32位处理器具有快速的能力。那为什么不用更高级的128位处理器呢？因为位数越高，处理器芯片的设计也就越复杂，目前的技术水平暂时无法制造这么复杂的芯片。

64位处理器之失

※硬件———缺乏驱动程序，很多现有硬件无法使用

※软件———操作系统不是问题，但是软件出现不兼容难题

64位处理器之得

※硬件———更快的执行速度，更大的内存管理

※软件———最新的尖端软件首先出现在64位平台

Continue reading "32位和64位系统区别及int字节数"

Posted on

hash table

今天用到哈希表，特地查了一下hash 算法:
========================  P1  ====================
我们知道，哈希表是一个固定大小的数组，数组的每个元素是一个链表（单向或双向）的头指针。如果Key一样，则在一起，如果Key不一样，则不在一起。哈希表的查询是飞快的。因为它不需要从头搜索，它利用Key的“哈希算法”直接定位，查找非常快，各种数据库中的数据结构基本都是它。但带来的问题是，哈希表的尺寸、哈希算法。
Continue reading "hash table"