dcdev mailing list

---- HUGE (windows) ----

 >RegexTest.exe huge.txt ".*microsoft.*"

       file: huge.txt
    pattern: .*microsoft.*
Reading... 121028 lines read
OK! reading took 13,25 seconds.
Beginning regex test of against lines in memory (121028 lines to test)
Test completed. 76 matches where found.
The search took 12,484375 seconds!

Well, I should admit I have the fastest computer in the world (perhaps in the universe :) ). I have not used your program to perform the test, I have used a simple (but wonderful) shell command:
grep '.*microsoft.*' < huge.txt
and to be more exact:
time grep '.*microsoft.*' < huge.txt
to have the run time duration. My computer is a P4C 2.8 with 1GB and I run linux 2.4.22. At the end of the program, I have 76 matches like you but it takes 0.01s to do the search. I see only the following reasons:
1) windoz sucks :) and linux rules but even with this, I don't think this explain the fact I go 77 times faster
2) I have a faster CPU (let's say 2 or even 3 time faster than yours).
3) the regex library you use has a poor speed.
I think it is even possible to go faster using file mapping  but this already is optimization :)

To do the comparison, I have run:
time fgrep 'microsoft' < huge.txt
(fgrep only does simple string search, no regex).
and the result is good... it takes the same time (0.01s or even 0.0 because the execution is too fast).

Finally, I have run a bigger test (3 lines of code :) ). I have written a small PERL program which does the same search:
==============
while (<>) {
  print if /.*microsoft.*/;
  }
==============
The run time (including perl loading and perl is big :) ) is between 0.07 and 0.09s. This clearly means perl like expression is usable.

I think that instead of removing features to a powerful search model, there is a more simple solution. Why a client could not just discard some search queries when it is overloaded.

Eric

Carl-Adam Brengesjö writes:
> Made a test for regex matching. Source code, filelists and binaries used > are attached to this mail. If that doesnt work (don't know if attaching > files on this mailing list works) they can be downloaded from > <http://ptha.mine.nu/~ptha/regextest.tar.bz2>. Be nice on the server > though, its hosted on my personal home 0.5Mbit connection...
> [...]
> ---- HUGE (*nix) ----
> $ mono RegexTest.exe huge.bz2 ".*microsoft.*"
>        file: huge.bz2
>     pattern: .*microsoft.*
> Begin decompression... (`bzip2 -dc "huge.bz2"')OK!
> Reading...OK! reading took 36.705775 seconds.
> Beginning regex test of against lines in memory (121028 lines to test)
> Test completed. 76 matches where found.
> The search took 45.15112 seconds!
> > ---- HUGE (windows) ----
>  >RegexTest.exe huge.txt ".*microsoft.*"
>        file: huge.txt
>     pattern: .*microsoft.*
> Reading... 121028 lines read
> OK! reading took 13,25 seconds.
> Beginning regex test of against lines in memory (121028 lines to test)
> Test completed. 76 matches where found.
> The search took 12,484375 seconds!

OK, I don't know what those Mono (or M$, for that part) guys are
doing, but when I try egrepping through the 'net' subdir on my Linux
2.6.0 source, which is in total 404715 lines, egrep -i runs for a
total of 1.8 seconds, with an active CPU time of 0.04 seconds user
time and 0.02 seconds system time, so I'd say that it's no problem
performance-wise to use regexps:

$ find -type f -exec cat {} \; | wc
404715 1246842 14942600
$ find -type f -exec cat {} \; | time egrep -i '.*ipv4.*' | wc
0.04user 0.02system 0:01.76elapsed 4%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (399major+90minor)pagefaults 0swaps
  1408    8629  400709

I don't know what you guys say, but I think that very much speaks for
itself, especially considering the performance losses of testing it
this way. I don't really think that it's going to be slower if you use
the regex functions directly instead of piping data back and forth,
and especially when you feed it the share cache from memory instead of
going through tons of VFS code (admittedly, I had pre-heated the
caches, but I think that's not more than right... :-) ).

If it takes 0.04 seconds of CPU time to regex search 400000 lines, it
seems not even the largest filelists should be a problem with a
properly optimized program.

Fredrik

eric writes:
>[...]
> Finally, I have run a bigger test (3 lines of code :) ). I have
> written a small PERL program which does the same search:
> ==============
> while (<>) {
>    print if /.*microsoft.*/;
>    }
> ==============
> The run time (including perl loading and perl is big :) ) is
> between 0.07 and 0.09s. This clearly means perl like expression is
> usable.

From what I've heard (or at least as stated by the PHP manual), the

PCRE engine than the glibc regex engine. I guess the extra just
_might_ come from the fact that you're running it in an interpreted
language (and yes, I know Perl has a compiler, but, no, it doesn't
compile to native code). Nonetheless, having an interpreted langauge
do the search in less than 0.1 seconds is a really good indication
that it's more than well feasible. As you can also see from my own
test, speed really doesn't seem to be a problem, even for extremely
large file lists.

What I can't understand is why Carl-Adam's C# code was so enormously
much slower (why are you mumbling 77 times faster when in fact it is
closer to a thousand times?), but I guess it is to be expected from a
M$ invention...

Carl-Adam, had you pre-heated the buffer cache before running your
test. If not, could you please do so and rerun it? I just can't
imagine even .net would be _that_ slow.

> I think that instead of removing features to a powerful search
> model, there is a more simple solution. Why a client could not just
> discard some search queries when it is overloaded.

Precisely what I have been thinking all the time. I don't know why I
didn't say it, though... =)

Fredrik

What I can't understand is why Carl-Adam's C# code was so enormously
much slower (why are you mumbling 77 times faster when in fact it is
closer to a thousand times?), but I guess it is to be expected from a
M$ invention...

This also may be due to the fact it use the date() function, not the real run time.

Carl-Adam, had you pre-heated the buffer cache before running your
test. If not, could you please do so and rerun it? I just can't
imagine even .net would be _that_ slow.

no need for imagination, it is reality ;)

Eric

Yea it worked... :D
now other ppl finally made some tests to prove how lousy my app was, and
the results are good!

Well, 2 against 1 - regex is very fast. Why not use it then?

eric writes:
> > > What I can't understand is why Carl-Adam's C# code was so
> > enormously much slower (why are you mumbling 77 times faster when
> > in fact it is closer to a thousand times?), but I guess it is to
> > be expected from a M$ invention...
> > This also may be due to the fact it use the date() function, not
> the real run time.

Nonetheless, my grep through 400000 lines of kernel source took just
1.8 seconds of actual elapsed (as in real-world) time, as opposed to
12 seconds of elapsed time for 120000 lines, so even in that regard it
processes lines at a speed factor of about 20.

Fredrik

Carl-Adam, had you pre-heated the buffer cache before running your
test. If not, could you please do so and rerun it? I just can't
imagine even .net would be _that_ slow.

I have no idea about what you are talking about :/ I am not much of an experienced programmer. But I knew it would be very slow, and I'd never choose C# or .NET for perfomance tasks. The main purpose was really to give a boost to this discussion about regex, and it worked.

The System.IO.StreamReader that I used does not use any buffer (nor cache), to my knowledge. I can see what happens if I use a buffered stream :)

Besides, Mono itself is written in C# and for the .NET framework, so in reality it has to compile iself at runtime (on-the-fly) aswell as for my application. Not sure about Microsoft's framework, but if I've got it right the .NET framework are mainly wrappers of the old .dll's and libraries and so here goes the microsoft problems again: layers, layers and even more layers before the work is actually done.
While on Linux (and other *nix) the libraries often work directly with the kernel. But this is no news.

$ find -type f -exec cat {} \; | time egrep -i '.*ipv4.*'

Well, how are these searches _different_ from normal DC searches? In no way.
I suspect the reason someone said regexps are slower werent that theyre
inherently slower for a regular DC substring match, but rather that they
have other variants that are slower.

---
John Bäckstrand

On Friday 16 January 2004 16:59, John Bäckstrand wrote:

>$ find -type f -exec cat {} \; | time egrep -i '.*ipv4.*'

Well, how are these searches _different_ from normal DC searches? In no
way. I suspect the reason someone said regexps are slower werent that
theyre inherently slower for a regular DC substring match, but rather that
they have other variants that are slower.

probably. To increase replay speed, it probably is a good idea to keep a cache of the last 1000 searchs with their replies.

Eric

Made a test for regex matching. Source code, filelists and binaries used are attached to this mail. If that doesnt work (don't know if attaching files on this mailing list works) they can be downloaded from <http://ptha.mine.nu/~ptha/regextest.tar.bz2>. Be nice on the server though, its hosted on my personal home 0.5Mbit connection...

There is no cpu usage limit, so it will go up in the top. If you want to implent one, please do and mail the results.

I decided to first read the file and add the entries (each line) in memory, then loop the memory and match the regex. Don't know if clients do that or not, but if you want to read and match on the fly - the source is free to use.

The tests were made on a 2.18TB share (named huge), a 669.58GB share (large) and a 34.31GB share (small).

The machines used are
 *nix:
   Intel Pentium 2, 333MHz. 192 MB SDRAM. Slackware 9.1 (Linux 2.4.22)
 windows:
   Intel Celeron, 2GHz. 768MB DDR-RAM. Windows XP, SP1.

There is another .NET library for *nix - dotGnu, but I don't have it installed.

Anyways - now I have atleast done some /real/ job with this, and now (finnally) going to bed! Juding is a job I leave for you.

this tool is really slow though, using .NET and all.. but I don't know any other language so well (newb ;)

---- SMALL (*nix) ----
$ mono RegexTest.exe small.bz2 ".*microsoft.*"
      file: small.bz2
   pattern: .*microsoft.*
Begin decompression... (`bzip2 -dc "small.bz2"')OK!
Reading...OK! reading took 0.326057 seconds.
Beginning regex test of against lines in memory (854 lines to test)
Test completed. 0 matches where found.
The search took 0.202791 seconds!

---- SMALL (windows) ----
>RegexTest.exe small.txt ".*microsoft.*"
      file: small.txt
   pattern: .*microsoft.*
Reading... 854 lines read
OK! reading took 0,09375 seconds.
Beginning regex test of against lines in memory (854 lines to test)
Test completed. 0 matches where found.
The search took 0 seconds!

---- LARGE (*nix) ----
$ mono RegexTest.exe large.bz2 ".*microsoft.*"
      file: large.bz2
   pattern: .*microsoft.*
Begin decompression... (`bzip2 -dc "large.bz2"')OK!
Reading...OK! reading took 9.072878 seconds.
Beginning regex test of against lines in memory (28453 lines to test)
Test completed. 1 matches where found.
The search took 19.938845 seconds!

---- LARGE (windows) ----
>RegexTest.exe large.txt ".*microsoft.*"
      file: large.txt
   pattern: .*microsoft.*
Reading... 28453 lines read
OK! reading took 3,0625 seconds.
Beginning regex test of against lines in memory (28453 lines to test)
Test completed. 1 matches where found.
The search took 1,3125 seconds!

---- HUGE (*nix) ----
$ mono RegexTest.exe huge.bz2 ".*microsoft.*"
      file: huge.bz2
   pattern: .*microsoft.*
Begin decompression... (`bzip2 -dc "huge.bz2"')OK!
Reading...OK! reading took 36.705775 seconds.
Beginning regex test of against lines in memory (121028 lines to test)
Test completed. 76 matches where found.
The search took 45.15112 seconds!

---- HUGE (windows) ----
>RegexTest.exe huge.txt ".*microsoft.*"
      file: huge.txt
   pattern: .*microsoft.*
Reading... 121028 lines read
OK! reading took 13,25 seconds.
Beginning regex test of against lines in memory (121028 lines to test)
Test completed. 76 matches where found.
The search took 12,484375 seconds!

/Carl-Adam

ps. reading the files/streams are _really_ slow.. "Men orka!" as we say in swedish.