答erlang静态数据查询方式

主题：erlang静态数据查询方式的一种构想 http://www.iteye.com/topic/461367

解决这个问题有2种方式：

1.  函数匹配
2.  per module constant pool

针对这个问题我做了个试验， 构建一个atom->int的查询。

yu-fengdemacbook-2:~ yufeng$ cat t.erl
-module(t).
-export([start/1, start/2]).


start([A1, A2])->
    start(list_to_integer(atom_to_list(A1)), A2).

start(N, Meth)->
    Start = erlang:now(),
    dotimes(N, case Meth of m->fun dict_lookup/1; f->fun fun_lookup/1 end),
    Stop = erlang:now(),
   erlang:display( N / time_diff(Start, Stop)).

dotimes(0, _) ->
     done;
dotimes(N, F) ->
    F(N),
    dotimes(N - 1, F).

time_diff({A1,A2,A3}, {B1,B2,B3}) ->
    (B1 - A1) * 1000000 + (B2 - A2) + (B3 - A3) / 1000000.0 .

dict_lookup(I) ->
    {ok, I} = dict:find(list_to_atom("x" ++ integer_to_list(I)), h1:get_dict()) .

fun_lookup(I) ->
    I = h2:lookup(list_to_atom("x" ++ integer_to_list(I))).

echo "done."yu-fengdemacbook-2:~ yufeng$ cat make_dict
#!/opt/local/bin/escript
main([A])->
N = list_to_integer(A),
L = [{list_to_atom("x" ++ integer_to_list(X)), X} || X<-lists:seq(1, N)],
D = dict:from_list(L),
io:format("-module(h1).~n-export([get_dict/0]).~nget_dict()->~n",[]),
erlang:display(D),
io:format(".~n"),
ok.
yu-fengdemacbook-2:~ yufeng$ cat make_fun
#!/opt/local/bin/escript
main([A])->
N = list_to_integer(A),
io:format("-module(h2).~n-export([lookup/1]).~n",[]),
[io:format("lookup(~p)->~p;~n",[list_to_atom("x" ++ integer_to_list(X)), X]) || X<-lists:seq(1, N)],
io:format("lookup(_)->err.~n", []),
ok.

yu-fengdemacbook-2:~ yufeng$ head h1.erl
-module(h1).
-export([get_dict/0]).
get_dict()->
{dict,100,20,32,16,100,60,{[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},{{[[x10|10],[x30|30],[x50|50],[x70|70],[x90|90]],[[x11|11],[x31|31],[x51|51],[x71|71],[x91|91]],[[x12|12],[x32|32],[x52|52],[x72|72],[x92|92]],[[x13|13],[x33|33],[x53|53],[x73|73],[x93|93]],[[x4|4],[x14|14],[x24|24],[x34|34],[x44|44],[x54|54],[x64|64],[x74|74],[x84|84],[x94|94]],[[x5|5],[x15|15],[x25|25],[x35|35],[x45|45],[x55|55],[x65|65],[x75|75],[x85|85],[x95|95]],[[x6|6],[x16|16],[x26|26],[x36|36],[x46|46],[x56|56],[x66|66],[x76|76],[x86|86],[x96|96]],[[x7|7],[x17|17],[x27|27],[x37|37],[x47|47],[x57|57],[x67|67],[x77|77],[x87|87],[x97|97]],[[x8|8],[x18|18],[x28|28],[x38|38],[x48|48],[x58|58],[x68|68],[x78|78],[x88|88],[x98|98]],[[x9|9],[x19|19],[x29|29],[x39|39],[x49|49],[x59|59],[x69|69],[x79|79],[x89|89],[x99|99]],[],[],[],[],[],[]},{[[x20|20],[x40|40],[x60|60],[x80|80],[x100|100]],[[x1|1],[x21|21],[x41|41],[x61|61],[x81|81]],[[x2|2],[x22|22],[x42|42],[x62|62],[x82|82]],[[x3|3],[x23|23],[x43|43],[x63|63],[x83|83]],[],[],[],[],[],[],[],[],[],[],[],[]}}}
.
yu-fengdemacbook-2:~ yufeng$ head h2.erl
-module(h2).
-export([lookup/1]).
lookup(x1)->1;
lookup(x2)->2;
lookup(x3)->3;
lookup(x4)->4;
lookup(x5)->5;
lookup(x6)->6;
lookup(x7)->7;
lookup(x8)->8;


yu-fengdemacbook-2:~ yufeng$ cat test.sh
#!/bin/bash

#OPT=+native
OPT=

echo "build $1..."
echo "make h1..."
./make_dict $1 >h1.erl
echo "make h2..."
./make_fun $1 >h2.erl
echo "compile h1..."
erlc $OPT  h1.erl
echo "compile h2..."
erlc $OPT h2.erl
echo "compile t..."
erlc $OPT t.erl

echo "running..."
echo "map..."
erl -s t start $1 m -noshell -s erlang halt
echo "fun..."
erl -s t start $1 f -noshell -s erlang halt

yu-fengdemacbook-2:~ yufeng$ ./test.sh 10000
build 10000...
make h1...
make h2...
compile h1...
compile h2...
compile t...
running...
map...
2.767323e+05
fun...
2.656819e+05
done.

在10000条记录的情况下 每个查询几个us， 速度不是很快.

结果发现 函数和constant pool在处理上上差不多快的。在实践中根据需要采用把。

评论

13 楼 whaosoft 2009-09-16  

谢谢，受教啦

12 楼 litaocheng 2009-09-14  

mryufeng 写道

谁说dict的复杂度是N, 它的实现是个hash表， 它的复杂度是最后桶的seg的大小 ＋ 常数。

ets用的是读写锁 如果是同一个调度器上的process，那么根据读写锁的futex实现 这个都在用户空间裁决，速度是飞快的，无什么太大的开销。 但是如果你有很多cpu 进程在不同的调度器上(不同的os线程) 那么涉及到内核裁决 速度就慢很多。

解释的太好了

11 楼 mryufeng 2009-09-14  

今天仔细看了下 函数匹配 原理是 把key收集在一起 在opcode  i_select_val里面2分查找

汇编码：
    {select_val,{x,0},
                {f,7},
                {list,[{integer,4},
                       {f,3},
                       {integer,3},
                       {f,4},
                       {integer,2},
                       {f,5},
                       {integer,1},
                       {f,6}]}}.


beam_emu.c:

OpCase(i_select_val_sfI):
     GetArg1(0, tmp_arg1);

do_binary_search:

怪不得这么快。

10 楼 xvyu 2009-09-05  

多谢指点

这么说在多核的cpu上,常量字典的表现应该优于ets
回头我尝试下

9 楼 mryufeng 2009-09-05  

谁说dict的复杂度是N, 它的实现是个hash表， 它的复杂度是最后桶的seg的大小 ＋ 常数。

ets用的是读写锁 如果是同一个调度器上的process，那么根据读写锁的futex实现 这个都在用户空间裁决，速度是飞快的，无什么太大的开销。 但是如果你有很多cpu 进程在不同的调度器上(不同的os线程) 那么涉及到内核裁决 速度就慢很多。

8 楼 xvyu 2009-09-05  

看这个结构，dict的时间复杂度应该是N，而gb_trees的时间复杂度是logN，大数据量的情况下差别会很明显

不太清楚ets的锁机制如何运作，有很多进程，比方100个，同时读，会不会有影响

7 楼 mryufeng 2009-09-05  

这2种方式都不会触发GC操作，所以还是值得尝试的。。。

6 楼 mryufeng 2009-09-05  

我这里demo的是一种方法 至于用gb_trees dict 还是其他的数据 结构 不都是一样的吗 只是数据组织的方式不同而已。

5 楼 xvyu 2009-09-05  

以前测试过
用gb_trees比dict快一些

4 楼 mryufeng 2009-09-05  

那个dict的tuple是代码生成的 不是我写的哦

3 楼 darkdestiny 2009-09-05  

直接用一个大tuple来写dict，太高级了点。
写一个dict相关的tuple格式说明就好了，manual上好像没有

2 楼 xvyu 2009-09-05  

十分感谢mryufeng的解答

在http://mryufeng.iteye.com/blog/435855这篇文章里
ets测试的结果也是us级,这样说常量池和函数匹配的意义不大了

1 楼 mryufeng 2009-09-05  

#!/opt/local/bin/escript  的路径 根据需要改下