Author Topic: Instr, strstr, find$  (Read 16413 times)

johnsa

  • Member
  • ****
  • Posts: 714
    • Uasm
Re: Instr, strstr, find$
« Reply #30 on: July 25, 2014, 12:03:51 AM »
I'm at work at the moment so I don't have much time to test, what are the parameters for the test:

Search string (needle)
Search body (haystack)

and number of timing iterations?

ie: find "te" in "test" 1 million times?
I've got my own instr algo but it's 64bit so i can't put it into your testbench, would be interesting to see the comparison (I'd have to report ms not cycles for now).

jj2007

  • Member
  • *****
  • Posts: 8891
  • Assembler is fun ;-)
    • MasmBasic
Re: Instr, strstr, find$
« Reply #31 on: July 25, 2014, 02:04:25 AM »
Search string (needle)
Search body (haystack)

and number of timing iterations?

Yes, body is \Masm32\include\winextra.inc, and string is echo WARNING

Thanks for your timings :icon14:

Gunther

  • Member
  • *****
  • Posts: 3585
  • Forgive your enemies, but never forget their names
Re: Instr, strstr, find$
« Reply #32 on: July 25, 2014, 04:04:31 AM »
Jochen,

InstrTimings5 brings:
Code: [Select]

c:\yasm\work>InstrTimingsNew.exe
Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz (SSE4)
+++++++13 of 20 tests valid, loop overhead is approx. 36/10 cycles

20406   kCycles for 10 * MbInstr 0 (zero-delimited)
18924   kCycles for 10 * MbInstr 0 (file size)
7679    kCycles for 10 * MbInstr FAST
23118   kCycles for 10 * crt_strstr
31910   kCycles for 10 * M32 find$
25510   kCycles for 10 * strstr_nidud

20353   kCycles for 10 * MbInstr 0 (zero-delimited)
21436   kCycles for 10 * MbInstr 0 (file size)
4674    kCycles for 10 * MbInstr FAST
22646   kCycles for 10 * crt_strstr
28390   kCycles for 10 * M32 find$
24980   kCycles for 10 * strstr_nidud

20306   kCycles for 10 * MbInstr 0 (zero-delimited)
18900   kCycles for 10 * MbInstr 0 (file size)
4582    kCycles for 10 * MbInstr FAST
22577   kCycles for 10 * crt_strstr
28547   kCycles for 10 * M32 find$
24806   kCycles for 10 * strstr_nidud

1068448 = eax MbInstr 0 (zero-delimited)
1068448 = eax MbInstr 0 (file size)
1068448 = eax MbInstr FAST
1068448 = eax crt_strstr
1068448 = eax M32 find$
1068448 = eax strstr_nidud

The environment is Windows XP under Virtual PC.

Gunther
Get your facts first, and then you can distort them.

jj2007

  • Member
  • *****
  • Posts: 8891
  • Assembler is fun ;-)
    • MasmBasic
Re: Instr, strstr, find$
« Reply #33 on: July 25, 2014, 05:30:22 AM »
4674    kCycles for 10 * MbInstr FAST
22646   kCycles for 10 * crt_strstr

Nice  :biggrin:

It gets even worse with a string like vc2010 (attached) - the speed depends strongly on the frequency of the first pattern byte, and e as in echo WARNING is pretty frequent.

Gunther

  • Member
  • *****
  • Posts: 3585
  • Forgive your enemies, but never forget their names
Re: Instr, strstr, find$
« Reply #34 on: July 25, 2014, 08:20:08 AM »
Jochen,

InstrTimings5a (same environment):
Code: [Select]

c:\yasm\work>InstrTimingsNew.exe
Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz (SSE4)
+++++++++++++7 of 20 tests valid, loop overhead is approx. 44/10 cycles

18711   kCycles for 10 * MbInstr 0 (zero-delimited)
20339   kCycles for 10 * MbInstr 0 (file size)
1794    kCycles for 10 * MbInstr FAST
17515   kCycles for 10 * crt_strstr
22578   kCycles for 10 * M32 find$
17415   kCycles for 10 * strstr_nidud

18347   kCycles for 10 * MbInstr 0 (zero-delimited)
17085   kCycles for 10 * MbInstr 0 (file size)
4439    kCycles for 10 * MbInstr FAST
17287   kCycles for 10 * crt_strstr
22561   kCycles for 10 * M32 find$
17376   kCycles for 10 * strstr_nidud

18455   kCycles for 10 * MbInstr 0 (zero-delimited)
17043   kCycles for 10 * MbInstr 0 (file size)
1773    kCycles for 10 * MbInstr FAST
17269   kCycles for 10 * crt_strstr
22668   kCycles for 10 * M32 find$
20817   kCycles for 10 * strstr_nidud

995374  = eax MbInstr 0 (zero-delimited)
995374  = eax MbInstr 0 (file size)
995374  = eax MbInstr FAST
995374  = eax crt_strstr
995374  = eax M32 find$
995374  = eax strstr_nidud

Gunther
Get your facts first, and then you can distort them.

dedndave

  • Member
  • *****
  • Posts: 8807
  • Still using Abacus 2.0
    • DednDave
Re: Instr, strstr, find$
« Reply #35 on: July 26, 2014, 02:30:55 AM »
prescott w/htt xp sp3 msvcrt 7.0.2600.5701
Code: [Select]
Intel(R) Pentium(R) 4 CPU 3.00GHz (SSE3)
++18 of 20 tests valid, loop overhead is approx. 30/10 cycles

54049   kCycles for 10 * MbInstr 0 (zero-delimited)
47497   kCycles for 10 * MbInstr 0 (file size)
7165    kCycles for 10 * MbInstr FAST
44331   kCycles for 10 * crt_strstr
43292   kCycles for 10 * M32 find$
40909   kCycles for 10 * strstr_nidud

54272   kCycles for 10 * MbInstr 0 (zero-delimited)
47732   kCycles for 10 * MbInstr 0 (file size)
7299    kCycles for 10 * MbInstr FAST
43498   kCycles for 10 * crt_strstr
43493   kCycles for 10 * M32 find$
41158   kCycles for 10 * strstr_nidud

53552   kCycles for 10 * MbInstr 0 (zero-delimited)
47853   kCycles for 10 * MbInstr 0 (file size)
7176    kCycles for 10 * MbInstr FAST
44348   kCycles for 10 * crt_strstr
42919   kCycles for 10 * M32 find$
41179   kCycles for 10 * strstr_nidud

995374  = eax MbInstr 0 (zero-delimited)
995374  = eax MbInstr 0 (file size)
995374  = eax MbInstr FAST
995374  = eax crt_strstr
995374  = eax M32 find$
995374  = eax strstr_nidud

jj2007

  • Member
  • *****
  • Posts: 8891
  • Assembler is fun ;-)
    • MasmBasic
Assembler beats C hands down
« Reply #36 on: July 26, 2014, 04:11:17 AM »
1794    kCycles for 10 * MbInstr FAST
17515   kCycles for 10 * crt_strstr

Almost 10:1 against CRT is really nice, that's ammunition against those who claim that C compilers are better than assembler :greensml:

Even with Dave's trusty P4 it's 6 x CRT. But again, the test with a pattern that starts with "v" is a little bit unfair ;-)

nidud

  • Member
  • *****
  • Posts: 1614
    • https://github.com/nidud/asmc
Re: Instr, strstr, find$
« Reply #37 on: July 26, 2014, 05:12:15 AM »
Quote
Assembler beats C hands down

jj2007

  • Member
  • *****
  • Posts: 8891
  • Assembler is fun ;-)
    • MasmBasic
Re: Assembler beats C hands down
« Reply #38 on: July 26, 2014, 06:27:43 AM »
So Intel themselves use assembler to code the CRT... ::)
Somebody will probably argue now that strstr would be much faster had they only used their compiler instead :badgrin:

Gunther

  • Member
  • *****
  • Posts: 3585
  • Forgive your enemies, but never forget their names
Re: Instr, strstr, find$
« Reply #39 on: July 26, 2014, 08:40:44 AM »
Jochen,

Somebody will probably argue now that strstr would be much faster had they only used their compiler instead :badgrin:

but that would be a bad joke. No one will believe that.

Gunther
Get your facts first, and then you can distort them.

jj2007

  • Member
  • *****
  • Posts: 8891
  • Assembler is fun ;-)
    • MasmBasic
Volnitsky substring search algorithm
« Reply #40 on: July 30, 2015, 07:24:13 AM »
http://volnitsky.com/project/str_search/
Quote
Described new online substring search algorithm which allows faster string traversal. Presented here implementation is substantially faster than any other online substring search algorithms for average case.

Grincheux

  • Member
  • ***
  • Posts: 330
  • Never be pleased, Always improve
    • Asm for fun
Re: Instr, strstr, find$
« Reply #41 on: January 04, 2016, 11:49:45 PM »
Is possible to make a backward seach. I explain :
1 - I search for "jpg"
2 - I search the first '"' BEFORE "jpg"

That would simplify the program.
Kenavo (Bye)
----------------------
Asm for Fun
My Links
"La garde meurt mais ne rend pas"
Cambronne à Waterloo

Grincheux

  • Member
  • ***
  • Posts: 330
  • Never be pleased, Always improve
    • Asm for fun
Re: Instr, strstr, find$
« Reply #42 on: January 04, 2016, 11:59:06 PM »
Quote
C:\Users\Grincheux\Downloads\InstrTimings5a>InstrTimingsNew.exe
AMD Athlon(tm) II X2 250 Processor (SSE3)
++++++++++++++++++++
22129   kCycles for 10 * MbInstr 0 (zero-delimited)
19881   kCycles for 10 * MbInstr 0 (file size)
3080    kCycles for 10 * MbInstr FAST
49397   kCycles for 10 * crt_strstr
46292   kCycles for 10 * M32 find$
20135   kCycles for 10 * strstr_nidud

22177   kCycles for 10 * MbInstr 0 (zero-delimited)
19904   kCycles for 10 * MbInstr 0 (file size)
3100    kCycles for 10 * MbInstr FAST
49343   kCycles for 10 * crt_strstr
45889   kCycles for 10 * M32 find$
20143   kCycles for 10 * strstr_nidud

22259   kCycles for 10 * MbInstr 0 (zero-delimited)
19881   kCycles for 10 * MbInstr 0 (file size)
3048    kCycles for 10 * MbInstr FAST
49342   kCycles for 10 * crt_strstr
45947   kCycles for 10 * M32 find$
20126   kCycles for 10 * strstr_nidud

995374  = eax MbInstr 0 (zero-delimited)
995374  = eax MbInstr 0 (file size)
995374  = eax MbInstr FAST
995374  = eax crt_strstr
995374  = eax M32 find$
995374  = eax strstr_nidud

C:\Users\Grincheux\Downloads\InstrTimings5a>

I think that the best is MbInstr

I include MasmBasic.inc and MasmBasic.lib. That'sll I have to do?
Kenavo (Bye)
----------------------
Asm for Fun
My Links
"La garde meurt mais ne rend pas"
Cambronne à Waterloo

Grincheux

  • Member
  • ***
  • Posts: 330
  • Never be pleased, Always improve
    • Asm for fun
Re: Instr, strstr, find$
« Reply #43 on: January 05, 2016, 02:01:22 AM »
I have installed the JJ2007's "InstrJJ" function.
A small part of AgnerAfrog (strlen) and an other part of JJ2007.
I forgot, a small part of Hutch for the memory, and Fearless for the interface.
I dropped VirtualAlloc and replaced it with a big buffer into the data segment.
It works fine.
I don't understand again files are not well downloaded, some of them are good but a big part are bad.
I continue searching before uploading this new version
Kenavo (Bye)
----------------------
Asm for Fun
My Links
"La garde meurt mais ne rend pas"
Cambronne à Waterloo

Grincheux

  • Member
  • ***
  • Posts: 330
  • Never be pleased, Always improve
    • Asm for fun
Re: Instr, strstr, find$
« Reply #44 on: January 05, 2016, 04:20:53 AM »
Quote
0D 0A 0D 0A 0D 0A 0D 0A 3C 21 44 4F 43 54 59 50 45 20 68 74 6D 6C 3E 0D 0A 0D 0A 3C 21 2D 2D 5B
........<!DOCTYPE html>....<!--[

I thought that "<!DOCTYPE html>" always was on the first line, so my test verifying if the file is an html file was wrong. I made correction.
Kenavo (Bye)
----------------------
Asm for Fun
My Links
"La garde meurt mais ne rend pas"
Cambronne à Waterloo