Tim Bray's Erlang Exercise "WideFinder" - After Find Wide

===>>> Updated Nov 7:
A new version tbray9a.erl which uses ets instead of dict, with 116 LoC, took about 3.8 sec on 5 million lines log file, 0.93 sec on 1 million lines file on my 4-core linux box.

* Results on T5120, an 8-core 1.4 GHz machine with 2 integer instruction threads per core and support for 8 thread contexts per core. Solaris thinks it sees 64 CPUs:

Schedulers#Elapsed(s)User(s)System(s)(User+System)/Elapsed
137.5835.517.821.15
220.1435.318.282.16
411.8135.378.253.69
87.6335.288.335.72
165.6036.088.277.92
325.2936.648.118.46
645.4536.798.238.26
1285.2636.758.398.58

When schedulers was 16, (User+System)/Elapsed was 7.92, and the elapsed time reached 5.60 sec (near the best), so, the 8-core computing ability and 2 x 8 =16 integer instruction threads ability almost reached the maxima. The 8 x 8 thread contexts seemed to do less help on gaining more performance improvement.

It seems that T5120 is a box with 8-core parallel computing ability and 16-thread for scheduler?

On my 4-core linux box, the slowest time (1 scheduler) vs the fastest time (128 schedulers) was 6.627/3.763 = 1.76. On this T5120, was 37.58/5.26 = 7.14. So, with the 8-core and 16-integer-instruction-thread combination, the T5120 is pretty good on parallel computing.

An interesting point is, when schedulers increased, Elpased time dropped along with User time and System time keeping almost constancy. This may because I separated the parallelized / sequential part completely in my code.

* Results on 2.80Ghz 4-core Intel xeon linux box (5 million lines log file):

Schedulers#Elapsed(s)User(s)System(s)(User+System)/Elapsed
16.6275.3564.2481.45
24.4866.1763.9362.25
44.2998.9894.1563.06
83.9609.6293.6443.35
163.8269.1013.6963.34
323.8589.0293.8403.34
643.7638.8013.8203.35
1283.9209.1373.9803.35


========

I'm a widefinder these days, and after weeks found wide, I worte another concise and fast widefinder tbray9.erl, which is based on Steve, Anders and my previous code, with Boyer-Moore searching (It seems Python's findall uses this algorithm) and parallelized file reading. It's in 120 LoC (a bit shorter than Fredrik Lundh's wf-6.py), took about 1 sec for 1 million lines log file, and 5.2 sec for 5 million lines on my 4-core linux box. Got 5.29 sec on T5120 per Tim's testing.

To evaluate:

erlc -smp tbray9.erl
erl -smp +A 1024 +h 10240 -noshell -run tbray9 start o1000k.ap

BTW since I use parallelized io heavily, by adding flag +A 1024, the code can get 4.3 sec for 5 million lines log file on my 4-core linux box.

Binary efficiency in Erlang is an interesting topic, except some tips I talked about in previouse blog, it seems also depending on binary size, memory size etc., The best buffer size for my code seems to be around 20000k to 80000k, which is the best range on my 4-core linux box and T5120, but it may vary for different code.

Note: There is a maximum element size limit of 2^27 - 1 (about 131072k) for binary pattern matching in current Erlang, this would be consistent with using a 32-bit word to store the size value (with 4 of those bits used for a type identifier and 1 bit for a sign indicator) (For this topic, please see Philip Robinson's blog). So, the buffer size can not be great than 131072k.

I. Boyer-Moore searching

Thanks to Steve and Anders, they've given out a concise Boyer-Moore searching algorithm in Erlang, I can modify it a bit to get a general BM searching module for ASCII encoded binary:

%% Boyer-Moore searching on ASCII encoded binary
-module(bmsearch).
-export([compile/1, match/3]).

-record(bmCtx, {pat, len, tab}).

compile(Str) ->
    Len = length(Str),
    Default = dict:from_list([{C, Len} || C <- lists:seq(1, 255)]),
    Dict = set_shifts(Str, Len, 1, Default),
    Tab = list_to_tuple([Pos || {_, Pos} <- lists:sort(dict:to_list(Dict))]),
    #bmCtx{pat = lists:reverse(Str), len = Len, tab = Tab}.

set_shifts([], _, _, Dict) -> Dict;
set_shifts([C|T], StrLen, Pos, Dict) ->
    set_shifts(T, StrLen, Pos + 1, dict:store(C, StrLen - Pos, Dict)).

%% @spec match(Bin, Start, #bmCtx) -> {true, Len} | {false, SkipLen}
match(Bin, S, #bmCtx{pat=Pat, len=Len, tab=Tab}) -> 
    match_1(Bin, S + Len - 1, Pat, Len, Tab, 0).
match_1(Bin, S, [C|T], Len, Tab, Count) ->
    <<_:S/binary, C1, _/binary>> = Bin,
    case C1 of
        C -> 
            match_1(Bin, S - 1, T, Len, Tab, Count + 1);
        _ ->    
            case element(C1, Tab) of
                Len -> {false, Len};
                Shift when Shift =< Count -> {false, 1};
                Shift -> {false, Shift - Count}
            end
    end;
match_1(_, _, [], Len, _, _) -> {true, Len}.

Usage:

> Pattern = bmsearch:compile("is a").
{bmCtx,"a si",4,{4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,...}}
> Bin = <<"this is a test">>.
<<"this is a test">>
> bmsearch:match(Bin, 1, Pattern).
{false,1}
> bmsearch:match(Bin, 5, Pattern).
{true, 4}
> bmsearch:match(Bin, 7, Pattern).
{false, 4}

II. Reading file in parallel and scan

To read file in parallel, we should open a new file handle for each process. To resolve the line break bound, we just split each chunk to first line (Head), line-bounded Data, and last line (Tail), and mark Head, Tail with the serial number as {I * 10, Head}, {I * 10 + 1 Tail}, so we can join all pending segments (Head and Tail of each chunk) later in proper order.

scan_file({FileName, Size, I, BmCtx}) ->
    {ok, File} = file:open(FileName, [raw, binary]),
    {ok, Bin} = file:pread(File, Size * I, Size),
    file:close(File),
    HeadL = split_on_first_newline(Bin),
    TailS = split_on_last_newline(Bin),
    DataL = TailS - HeadL,
    <<Head:HeadL/binary, Data:DataL/binary, Tail/binary>> = Bin,
    {scan_chunk({Data, BmCtx}), {I * 10, Head}, {I * 10 + 1, Tail}}.

III. Spawn workers

Luke's spawn_worker are two small functions, they are very useful, stable and good abstract on processing workers:

spawn_worker(Parent, F, A) ->
    erlang:spawn_monitor(fun() -> Parent ! {self(), F(A)} end).

wait_result({Pid, Ref}) ->
    receive
        {'DOWN', Ref, _, _, normal} -> receive {Pid, Result} -> Result end;
        {'DOWN', Ref, _, _, Reason} -> exit(Reason)
    end.

So, I can start a series of workers simply by:

read_file(FileName, Size, ProcN, BmCtx) ->
    [spawn_worker(self(), fun scan_file/1, {FileName, Size, I, BmCtx})        
     || I <- lists:seq(0, ProcN - 1)].

And then collect the results by:

    Results = [wait_result(Worker) || Worker <- read_file(FileName, ?BUFFER_SIZE, ProcN1, BmCtx)],

In this case, returning Results is a list of {Dict, {Seq1, Head}, {Seq2, Tail}}

IV. Concat segments to a binary and scan it

Each chunk is slipt to Head (first line), line-bounded Data, and Tail (last line). The Head and Tail segments are pending for further processing. After all workers finished scanning Data (got a Dict), we can finally sort these pending segments by SeqNum, concat and scan them in main process.

Unzip the results to Dicts and Segs, sort Segs by SeqNum:

    {Dicts, Segs} = lists:foldl(fun ({Dict, Head, Tail}, {Dicts, Segs}) ->
                                        {[Dict | Dicts], [Head, Tail | Segs]}
                                end, {[], []}, Results),
    Segs1 = [Seg || {_, Seg} <- lists:keysort(1, Segs)],    

The sorted Segments is a list of binary, list_to_binary/1 can concat them to one binary efficently, you do not need to care about if it's a deep list, they will be flatten automatically:

    Dict = scan_chunk({list_to_binary(Segs1), BmCtx}),

Conclution

Thinking in parallel is fairly simple in Erlang, right? Most of the code can run in one process, and if you want to spawn them for parallel, you do not need to modify the code too much. In this case, scan_file/4 is sequential, which just return all you want, you can spawn a lot of workers which do scan_file/4 work, then collect the results later. That's all.

Comments

1. emptist -- 2007-11-21 16:00

Hi, Caoyuan, Since AIOTrader topic has closed I write here, sorry. And sorry for my English. I've just download and tried AIOTrader and impressed by it. I can do a little Smalltalk and want to use AIOTrader as a user defined indicator data representing tool. Is it possible for AIOTrader to open an API that would support UDI data exchange/importing and maybe quote data? I can provide with end-of-day quotes and related indicator data (daily, weekly, even quarterly, separated). In this way, customer needs no Java skills to add any indicators with no limitation. I've looking for such kind of free software for a long time but not found.

2. Caoyuan -- 2007-11-23 16:00

emptist,

But I don't know what is UDI data.

3. emptist -- 2007-11-24 16:00

hi, I'm sorry but it's User Defined Indicator.

Say, I don't know any Java, but I can do some other language or I just have the data from a friend then may it be possible and easy for you to open some API(for programmer of other languages and even worse, perhaps not that skillful) and some Importing approach to let them watch the indicator data in your wonderful AIOTrader? The user may or may not want to import his own quote data, too.

For example, we have stock 000001.sz, shenzhen dev. bank in other words, and user want to display a home made indicator, and user can provide it as a file or as through API call to AIOTrader.

Say the data knows these: a indicator name, a wanted display color, a display object type(line or stick line or signal, etc,), and of course the data table, maybe separated daily table, weekly table, etc. such as: daily data: date .............value 20050101.....20.05 20050102.....20.15

monthly data: date ............value

quarterly data: etc. and he might want to supply with his own quote data, maybe also as separated daily, monthly, etc tables.

In short use AIOTrader to display but not to develop. Will you think this none sense?

I'm asking since AIOTrader is open-sourced, and you are so open-minded and generous in many ways :)

Sorry for bothering.

4. emptist -- 2007-11-24 16:00

hi, User Defined Data, sir. Sorry.

In short, APIs(for programmer) and Importing tools(for programmer and non-programmer) for using AIOTrader more as a ready data presenting platform but not a indicator developing platform.

This is very useful for those who can't program in Java and has already his own developing language.

I've been looking for this kind of platform for a long time but failed to find any.

5. emptist -- 2007-11-24 16:00

Sorry again. It should have been Use Defined Indicator, UDI.

In fact I typed correctly in my previous response but the post is too long for your spam remover.....

6. emptist -- 2007-11-28 16:00

Hi, I'm back to see if there's new response. In your another post I learned that now you're still focusing on features but not APIs. Well, I'm not an expert but in my situation I can export User defined Indicator data files or exchange data through web services (SOAP). Both will be platform independent. Thanks :)

7. Caoyuan -- 2007-11-28 16:00

Hi emptist,

AIOTrade currently supports import data from csv file. But for other options your mentioned, will not be supported in near future.

Not only the API is not stable yet, but also I'm thinking new architecture for AIOTrade.

8. anonymous -- 2012-03-26 20:02

Hi there, can you please fix the link to the erlang module, as it's no longer download-able. Cheers.

9. md5 hacker -- 2012-03-30 07:15

This is really satisfied by the nice info is visible in this blog. I am very much enjoy the great info is visible in this blog that to using the great technology in this blog.Link:md5 file

10. coach factory outlet -- 2012-03-31 06:42

No one can deny the shopping at the coach factory outlet is satisfactory. For the low prices and good quality.Over the years, coach factory online has added a multitude of new handbag shapes, styles and materials to their collection. However, the highest care is taken that every Coach handbags is both aesthetically beautiful and functional.Many fashionable women match with practical Coach Purses which will make the street shopping become relaxed,and make every person can enjoy more diversiform combination in coach factory outlet online.

http://www.ccoachfactoryoutlet.com

11. louis vuitton sale -- 2012-03-31 06:42

Don't feel upset, there will be a great conversion to this kind of situation because there are a large number of louis vuitton sale now!louis vuitton outlet,welcome to buy urban louis vuitton on our online shop.discount price is our special offer, durability and high quality is our promise.louis vuitton Outlets offer famous classic brand for LV,Channel, with perfect service.So become to the VIP soon.They offer more new styles,like LV purses,LV wallets etc. And are tested by product quality monitoring center .

http://www.louisvuittonoutletsaleo.com

12. coach outlet online, -- 2012-03-31 06:43

Turn your attention to such discount coach sneakers for women from coach outlet online, you will find something unique and special of such authentic coach for sale at coach factory outlet store online.coach outlet store sells goods that are constructed to meet the highest standards of quality and functionality.You can trust it 100 percent.coach outlet has become a popular shopping experience for consumers around the world, and a desirable distribution channel for manufacturer's and retailers.

http://www.coachoutletonlinesl.com

13. louis vuitton outlet -- 2012-03-31 07:09

any louis vuitton outlet New backpack features usa a function grownup overall look. Varied piece allows that it is captivated me within the approve and also further than your body.It’s induced by way of severe hardworking liver diseases, and also the most familiar factors behind constant louis vuitton bags outlet hard working liver disorder usually are excessive drinking and also liver disease Chemical.Ladies have an ardent love for the Louis Vuitton handbags outlet because Louis Vuitton enjoys a worldwide reputation of high quality and fashionable designs.

http://www.louisvuittonoutletbagsc.com

14. coach outlet store online -- 2012-03-31 07:11

coach outlet store online marketed properly all greater compared to earth and earn cozy praise from customers. They are made from the finest leather and fabric.coach outlet store have Coach handbags,Coach Shoulder Bags,Coach Briefcases and so on,these bags are so perfectly reproduced,you won't even be able to tell the difference!Coach Outlet Online Store would dynamically change your overall styles right away. The amazing knack about the unique coach handbag is that it would never disappoint your individual styles at all. Rather, it would instantly change your ultimate fashions in a remarkable manner.

http://www.coachoutletstoreonlineeo.com

15. louis vuitton uk -- 2012-03-31 07:18

Our online store offers you discounted Designer louis vuitton replica wallet at present. You could find them in desirable quality and price. If you don't mind high class louis vuitton uk, have a good time here.These is the first time your visit our louis vuit Louis vuitton online shop ,welcome.

http://www.louisvuittonukk.org.uk

16. anonymous -- 2012-04-03 10:20

I am really very happy for the great technology is visible in this blog and the different info in this blog that to sharing the nice services in this blog. I had really like this info in this website and the amazing technology. super casino ladbrokes casino online casinos casino bonus Online Gambling

17. anonymous -- 2012-04-03 13:14

For those looking for the file tbray9a.erl, after a bit of poking around (sorry dcaoyuan!), I found it here:

http://blogtrader.net/htdocs/images/uploads/dcaoyuan/code/tbray9a.erl

18. Louis Vuitton Handbags -- 2012-04-15 11:38

Welcome to order Discount Louis Vuitton UK and lead a fashionable, luxury and elegant life from our Louis Vuitton Canada Outlet Store. Enjoy the shopping now here! The Louis Vuitton Handbags are amazing and you will rest assured by proudly owning a bed that you will find yourself envied by simply your colleagues. Louis Vuitton Store Online Handbags can also bring great accuracy as well as practical applicability and fashionable.

http://www.uk-louisvuittonhandbags.co.uk

19. chistian louboutin uk -- 2012-04-18 01:09
20. louis vuitton uk -- 2012-04-18 01:17
21. mulberry outlet uk -- 2012-04-18 01:24
22. garlandsmith07 -- 2012-04-27 11:09

I am really very happy for visiting the nice info in this Online top poker blog and the great technology is visible in this 777 Poker Online blog. This is very much satisfied by the info in this 888 POKER GAMES blog. I am really very great for the info wise that to helpful info in this Blackjack Online Play blog. I really love this info in this website and the nice info in this 777 Best pokers blog. Thanks a lot for sharing some info in this blog.

23. francesjordan -- 2012-04-28 14:19

This is providing interview questions for u the nice posts are SEO interview questions display in this blog that to interview questions display the nice info is visible in this CSS interview questions blog. Thanks a lot for providing UNIX interview questions the great technology is visible in this Networking interview questions blog that to using the nice services in this blog.

24. smith -- 2012-06-05 17:30

This is very much satisfied by the nice info is visible in this blog that to using the great services in this Top free casinos blog. Thanks a lot for using the great approach is visible in this blog and utilize the nice services in this blog.

25. chrisvinson -- 2012-06-23 17:06

I am really admired for top betting place the nice approach is visible in this Casino Game Plan blog that to sharing the great info is visible in this 365 CASINO GAME blog. Thanks a lot for providing the amazing approach Blackjack Play Live is visible in this blog that to interesting info is visible in this 777 Poker Games blog.

26. air max 2011 -- 2012-07-23 01:24

Air Max 2012 is helpful for running and movement because of the upper hyperfuse for light weight and permeability, and a complete midsole and 360 air units max buffering and ensure a smooth ride. http://www.airmax2011foryou.com/ Air Max 2012 Womens Specific quantity of fuel molecules is higher compared to slight gap artificial rubber layer,so the Air Max 2012 Nike will not be lost within the fuel cushion.

27. davidsfrost -- 2012-08-01 08:20

Thanks a lot for providing the great info is visible in this blog that to sharing the great info is visible in this blog. I am very much inspired the great technology in this blog. For more details visit our site ladbrokes bingo wink bingo sun bingo new bingo roulette table

28. davidsfrost -- 2012-08-02 06:17

I am very much happy for the great technology is visible in this blog that to sharing the great technology in this blog. Thanks a lot for providing the valuable info is visible in this blog. For more details visit our site roulette table roulette Online cam roulette man roulette

29. davidsfrost -- 2012-08-03 12:00

I am really admired for the great info is visible in this blog that to sharing the great services in this blog. Thanks a lot for providing the valuable info is visible in this blog that to utilize the different services by this website. For more details visit our site russian roulette poker games free poker games gambling commission gambling

30. anonymous -- 2012-08-06 07:02

Pretty info is Link: a1 casino news visible in this blog Link: casino games play forfun and the great services in this blog Link: play free casino I am really admired for using the great Link: hot casino blackjack services in this blog and thank you very much for Link: top uk casinos online visiting the nice info.

31. sandeepseo -- 2012-09-13 04:25

I was searching for some info is visible in this blog and useful info is visible in this blog. I am really very happy for providing the lot info in this blog. I am searching for some different info in this blog. This is very much impressive with this website. I had really like it very much for useful info in this blog. Thanks a lot for sharing the nice info in this blog. <a href="http://casino-gambling-rules.com">casino gambling rules</a> <a href="http://royalvegascasinonow.com">royalvegas casino</a> <a href="http://firsttimetoplaycasino.com">play casino</a> <a href="http://livebingocasinogame.net">bingo casino game</a> <a href="http://onlinebestcasinowebsites.com">online best casino</a>

32. anonymous -- 2012-09-17 06:08

<a href= " http://www.nikeairjordans.biz/nike-air-jordan-10-retro-c-18.html " title= " jordan 10 retro " ><strong>jordan 10 retro </strong></a>.step on the gas, such as Jianban of washed out, trucks tight steps to follow, and then have a bunch of bullets hit the door, in the four weeks, there are few black car, stuck a black window in the muzzle, spewing fire with flames. Lei Zhengyang not neglect bypass around the steering wheel, two cars from the middle of Diagonal Crossing out, it is just a short few seconds, before and after windshield were broken, even right out the door also Zhuangfei. few cars caught up with a strong suppression of the fire, Lei Zhengyang do not know if this is the counsel of family division, but the moment, these people have given him causing trouble. car pulled into an open-meter mountain, however, but Leizheng Yang found that one in the hole, a large tanker already has the road blocked , and turning a Jicha, Lei Zhengyang since the car jumped out, almost no trace of hesitation, who has been on the fly from the tanker. one kind of gunpowder filled the air here, almost Leizheng Yang tanker flying the moment, the car exploded, air waves rolling Lei Zhengyang body suffered a heavy blow, if not in this moment, to enhance the strength of six dragon body care, die moment that hurt. really good terms, considered so accurate, if it were not him, would definitely die. Leizheng Yang sprang from the hole when the clothes have been fragmented, as has just been roasted some, even the hair into a mass of chaos. but that did not end in that hole, four Baojian re-written for the swordsman stands waiting. them 20 people, seems to be waiting for the arrival of Leizheng Yang. surrounded by up to Leizheng Yang, the twenty people, not only the swordsman so simple, they are running is simply a Jian Zhen. Yes, a Jian Zhen, Lei Zhengyang stature several ups and downs, they did not escape the siege. Jianshi such as showers, Tao of the array to form a sword, Leizheng Yang did not expect, the three families in the North, even with such a powerful hidden strength. It looks as if Chennai, said that, no good dinner feast, eat, you prepare so that he killed the. broke into three steps, but was driven back three steps, the swordsman with just right, almost no loopholes, like turning around, perhaps only a strong attack. Leizheng Yang hands an, idea of ??a move, it seems long ago to hide the dragon head has been stifled, jump out, transmit voice whisper a kind of dragon With Leizheng Yang physique of a move, as the swirling floating sword, all of a sudden Annihilation, ears, heard a few sound Leizheng Yang barely a moment's hesitation, physique of a vertical sky to hand to grab the first dragon float in the air, full of split down, while you are sick, to your life, this time is not kind, when the moment of death in this swordsman, Lei Zhengyang not been patched since the only complete gap rushed past four handle sword, has been moving his head hit, Leizheng Yang dragon head of a block, stature can not <p>

33. moreknow100@… -- 2012-09-20 08:15

admin of this blog is great Promote Your Website

34. True Religion Jeans Outlet -- 2012-10-11 06:14

Serums and mild hair sprays square measure currently turning into one among the foremost essential beauty merchandise. If you've got long hair, you wish a product that http://www.truereligionjeansoutlet-onsale.com/ True Religion Outlet controls the kink up and keeps long hair stunning and glossy. girls with crisp hair may like a reliable product to take care of the curls and convey out nice volume and bounce. you'll use your Parlux http://clarisonicmia.brushstore0o.com/ Clarisonic Outlet hand blower reception, then bring a hair blood serum or mild spray for a fast fix.

35. anonymous -- 2012-10-12 01:22

Welcome!Coach Outlet Store are loved by many people,when you walk in the street, you could see many people take Coach Shoulder Bags styles.

Coach Factory http://coachfactoryoutlet.1uxury--best.com

Coach Factory Outlet http://www.coachfactoryoutletcd.com

Coach Outlet Store http://www.coachoutletstoreusac.com

Coach Outlet http://www.coachoutletonlinecss.com

36. Canada Goose UK -- 2012-10-12 01:41

The Canada Goose UK are only some of the must have pieces you should definitely include into your accessory parade.

http://www.canada-goose-outlet.co.uk Canada Goose UK

http://www.canadagooseparkas.org Canada Goose Parkas

http://www.canadagoose-sale.org Canada Goose Sale

http://www.canadiagoosejackets.com Canada Goose Jackets

37. Tubal Ligation Reversal -- 2013-01-18 09:50

GOOD and NEW factors, just create me experience fresh and dynamic. That is the miracle of your material . http://www.tubal-reversal-surgery.net/tubal-ligation-reversal-financing-and-insurance-coverage.html

38. sharathseo4@… -- 2013-01-22 16:32

This is really <a href="http://OnlineTopPoker.com/">Online Top Poker</a> ultimate info is visible in this blog that to really admire for <a href="http://777PokerOnline.com/">777 Poker Online</a> the nice approach is visible in this blog. I had really admired for the fantastic info <a href="http://888POKERGAMES.COM/">888 POKER GAMES</a>is visible in this blog and superb science is visible in this blog. This is <a href="http://BlackjackOnlinePlay.com/">Blackjack Online Play</a> really superb info is visible in this blog that to <a href="http://777BESTPOKERS.COM/">777 BEST POKERS</a> sharing the nice services in this blog. Thanks a lot for providing the nice services.

39. anonymous -- 2013-07-11 07:19
41. anonymous -- 2013-10-27 21:47

Great post and a really good blog. Thank you so much for your efforts to put this amazing source of useful information together. Keep the great work up!<a href="http://www.pokeroom.it/public/temmins.asp"><STRONG>moncler outlet</STRONG></a>, <a href="http://www.cc-vezerecausse.com/images/goose/index.asp"><STRONG>cc-vezerecausse.com/images/goose/index.asp</STRONG></a>