A small procedure asm
-
- User
- Posts: 70
- Joined: Wed May 02, 2012 2:17 am
- Location: Brazil
A small procedure asm
Hi, I need a small Procedure in asm to do the same processing below:
................................................
Procedure.b grep(string1.s, string2.s)
occur=0
For j=1 To CountString(string2," ")+1
If FindString(string1, StringField(string2, j," ")): occur+1: EndIf
Next
ProcedureReturn occur
EndProcedure
...............................................
Example:
Input1.s = "02 09 15 21 37 59 72 81"
Input2.s = "07 11 15 22 37 40"
Result = grep(Input1,Input2)
; In this example the Result will be 2 ... ( 15 and 37 match between strings Input1 & Input2)
Can anyone help me do this procedure in asm to be faster?
i await
thanks
Fernando
................................................
Procedure.b grep(string1.s, string2.s)
occur=0
For j=1 To CountString(string2," ")+1
If FindString(string1, StringField(string2, j," ")): occur+1: EndIf
Next
ProcedureReturn occur
EndProcedure
...............................................
Example:
Input1.s = "02 09 15 21 37 59 72 81"
Input2.s = "07 11 15 22 37 40"
Result = grep(Input1,Input2)
; In this example the Result will be 2 ... ( 15 and 37 match between strings Input1 & Input2)
Can anyone help me do this procedure in asm to be faster?
i await
thanks
Fernando
Re: A small procedure asm
Not assembler, but definately faster:
Why:
1. Calculate not for each loop the length of the string
2. Walk not for each loop again through the whole second string
For FindString() you can search the forum, I think wilbert wrote a FindString() in asm already.
Bernd
Code: Select all
Procedure.i grep(string1.s, string2.s)
Protected.i j, Count, occur
Count = CountString(string2, " ")
For j = 0 To Count
If FindString(string1, PeekS(@string2 + j * 3, 2))
occur + 1
EndIf
Next
ProcedureReturn occur
EndProcedure
1. Calculate not for each loop the length of the string
2. Walk not for each loop again through the whole second string
For FindString() you can search the forum, I think wilbert wrote a FindString() in asm already.
Bernd
Re: A small procedure asm
It helps to have more information.
Do all strings you have to compare exist of only numbers separated by space characters and if so, is there a maximum value to these numbers ?
If the strings also contain other characters, does it have to be case sensitive ?
Do all strings you have to compare exist of only numbers separated by space characters and if so, is there a maximum value to these numbers ?
If the strings also contain other characters, does it have to be case sensitive ?
Windows (x64)
Raspberry Pi OS (Arm64)
Raspberry Pi OS (Arm64)
-
- User
- Posts: 70
- Joined: Wed May 02, 2012 2:17 am
- Location: Brazil
Re: A small procedure asm
Hi, Berndinfratec wrote:Not assembler, but definately faster:Why:Code: Select all
Procedure.i grep(string1.s, string2.s) Protected.i j, Count, occur Count = CountString(string2, " ") For j = 0 To Count If FindString(string1, PeekS(@string2 + j * 3, 2)) occur + 1 EndIf Next ProcedureReturn occur EndProcedure
1. Calculate not for each loop the length of the string
2. Walk not for each loop again through the whole second string
For FindString() you can search the forum, I think wilbert wrote a FindString() in asm already.
Bernd
Thank you for responding and give your idea.
Yes, I can not calculate the amount items of string2 every time.
The idea of removing "StringField" was great!
My routine was in 154 seconds to process 12 million times,
now with the "PeekS()" only 6 seconds, amazing!
Congratulations again, thank you.
Fernando ( from Brazil - Sao Paulo)
-
- User
- Posts: 70
- Joined: Wed May 02, 2012 2:17 am
- Location: Brazil
Re: A small procedure asm
Hi,wilbert wrote:It helps to have more information.
Do all strings you have to compare exist of only numbers separated by space characters and if so, is there a maximum value to these numbers ?
If the strings also contain other characters, does it have to be case sensitive ?
Yes, all strings are numbers between spaces.
The numbers can be from 00 to 99 and the amount of 5 to 90 in both strings.
Examples: "00 07 19 23 32 45 46 50 62 71 80 83 99"
The idea of removing "StringField" and putting "PeekS" was great, but you have another idea that will leave faster processing?
Tanks to respond and help.
Fernando
-
- User
- Posts: 70
- Joined: Wed May 02, 2012 2:17 am
- Location: Brazil
Re: A small procedure asm
Now my Procedure is as follows:
Procedure.i grep(string1.s,string2.s,n1.i)
; n1 = the amount of numbers within the string2 ex: string2="00 07 11 18 21 23 27 65 71 74 78 85 90 99" n1=14
Protected.i j, occur
For j=0 To n1-1
If FindString(string1, PeekS(@string2 + j * 3, 2,#PB_Ascii)): occur+1: EndIf
Next
ProcedureReturn occur
EndProcedure
25 times faster, someone can do faster?
I wait.
Thanks
Fernando
Procedure.i grep(string1.s,string2.s,n1.i)
; n1 = the amount of numbers within the string2 ex: string2="00 07 11 18 21 23 27 65 71 74 78 85 90 99" n1=14
Protected.i j, occur
For j=0 To n1-1
If FindString(string1, PeekS(@string2 + j * 3, 2,#PB_Ascii)): occur+1: EndIf
Next
ProcedureReturn occur
EndProcedure
25 times faster, someone can do faster?
I wait.
Thanks
Fernando
Re: A small procedure asm
If you are 100% sure your strings look like that, you can do something like thisfvillanova wrote:25 times faster, someone can do faster?
Code: Select all
DisableDebugger
CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
Macro rdx : edx : EndMacro
CompilerEndIf
Structure GrepBits
a.a[13]
EndStructure
Procedure.i Grep(*String1, *String2)
Protected Count.l, GrepBits.GrepBits
EnableASM
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!lea r8, [p.v_GrepBits]
CompilerEndIf
!xor ecx, ecx
mov rdx, *String1
!grep_loop0:
movzx eax, byte [rdx]
CompilerIf #PB_Compiler_Unicode
add rdx, 2
CompilerElse
add rdx, 1
CompilerEndIf
!cmp al, 32
!jbe grep_cont0
!imul ecx, 10
!lea ecx, [ecx + eax - 48]
!jmp grep_loop0
!grep_cont0:
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!bts [r8], ecx
CompilerElse
!bts [p.v_GrepBits], ecx
CompilerEndIf
!xor ecx, ecx
!and al, al
!jnz grep_loop0
mov rdx, *String2
!grep_loop1:
movzx eax, byte [rdx]
CompilerIf #PB_Compiler_Unicode
add rdx, 2
CompilerElse
add rdx, 1
CompilerEndIf
!cmp al, 32
!jbe grep_cont1
!imul ecx, 10
!lea ecx, [ecx + eax - 48]
!jmp grep_loop1
!grep_cont1:
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!bt [r8], ecx
CompilerElse
!bt [p.v_GrepBits], ecx
CompilerEndIf
!jnc grep_cont2
inc Count
!grep_cont2:
!xor ecx, ecx
!and al, al
!jnz grep_loop1
DisableASM
ProcedureReturn Count
EndProcedure
Input1.s = "02 09 15 21 37 59 72 81"
Input2.s = "07 11 15 22 37 40"
t1 = ElapsedMilliseconds()
For i = 1 To 12000000
Result = Grep(@Input1, @Input2)
Next
t2 = ElapsedMilliseconds()
MessageRequester("Result (" + Str(t2-t1) + " ms)", Str(Result))
Windows (x64)
Raspberry Pi OS (Arm64)
Raspberry Pi OS (Arm64)
-
- User
- Posts: 70
- Joined: Wed May 02, 2012 2:17 am
- Location: Brazil
Re: A small procedure asm
Wow man!wilbert wrote:fvillanova wrote:25 times faster, someone can do faster?Code: Select all
Input1.s = "02 09 15 21 37 59 72 81" Input2.s = "07 11 15 22 37 40"
Now I am processing in 2 seconds!
I do not believe the speed that was the program!
I have a question:
This Procedure will work for any amount numbers (XX) within the strings?
Thank you very much, was a great help.
Fernando
Re: A small procedure asm
If your strings always look exactly like this (2 numbers, space, 2 numbers etc.) it will work.fvillanova wrote:This Procedure will work for any amount numbers (XX) within the strings?
The amount of numbers doesn't matter but it doesn't detect doubles (if you would have multiple times the same number in on of the strings)
What it does is parse the numbers and use them as indices of a bit array.
This should be even faster compared to my previous routine.
Code: Select all
DisableDebugger
CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
Macro rdx : edx : EndMacro
CompilerEndIf
Macro Grep_GetNumber()
CompilerIf #PB_Compiler_Unicode
mov ecx, [rdx]
add rdx, 6
!shl cx, 12
!shr ecx, 12
CompilerElse
mov cx, [rdx]
add rdx, 3
!shl cl, 4
!shr ecx, 4
CompilerEndIf
!and ecx, 0xff
EndMacro
Macro Grep_TestEndOfString()
CompilerIf #PB_Compiler_Unicode
cmp byte [rdx - 2], 0
CompilerElse
cmp byte [rdx - 1], 0
CompilerEndIf
EndMacro
Structure GrepBits
l.l[5]
EndStructure
Procedure.i Grep(*String1, *String2)
Protected GrepBits.GrepBits
EnableASM
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!lea r8, [p.v_GrepBits]
CompilerEndIf
!sub eax, eax
mov rdx, *String1
cmp byte [rdx], 0
!je grep_exit
!align 8
!grep_loop0:
Grep_GetNumber()
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!bts [r8], ecx
CompilerElse
!bts [p.v_GrepBits], ecx
CompilerEndIf
Grep_TestEndOfString()
!jne grep_loop0
mov rdx, *String2
cmp byte [rdx], 0
!je grep_exit
!align 8
!grep_loop1:
Grep_GetNumber()
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!bt [r8], ecx
CompilerElse
!bt [p.v_GrepBits], ecx
CompilerEndIf
!adc eax, 0
Grep_TestEndOfString()
!jne grep_loop1
!grep_exit:
DisableASM
ProcedureReturn
EndProcedure
Input1.s = "02 09 15 21 37 59 72 81"
Input2.s = "07 11 15 22 37 40"
t1 = ElapsedMilliseconds()
For i = 1 To 12000000
Result = Grep(@Input1, @Input2)
Next
t2 = ElapsedMilliseconds()
MessageRequester("Result (" + Str(t2-t1) + " ms)", Str(Result))
Windows (x64)
Raspberry Pi OS (Arm64)
Raspberry Pi OS (Arm64)
-
- User
- Posts: 70
- Joined: Wed May 02, 2012 2:17 am
- Location: Brazil
Re: A small procedure asm
Hi Wilbert,wilbert wrote:If your strings always look exactly like this (2 numbers, space, 2 numbers etc.) it will work.fvillanova wrote:This Procedure will work for any amount numbers (XX) within the strings?
The amount of numbers doesn't matter but it doesn't detect doubles (if you would have multiple times the same number in on of the strings)
What it does is parse the numbers and use them as indices of a bit array.
I did not imagine possible to make even faster, did tests with
last routine and is working, congratulations! Was faster!
I made tests with the first routine with different amounts and worked perfectly.
My program is used for mathematical calculations and distribution of elements.
In various locations of the program I need to compare the strings and count the equal occurrences.
Sorry for my English, I do not know if I'm getting right explain my system.
Your routine will help me a lot, my program now makes instant calculations.
I'll put your name in the system, what's your full name and country?
My teacher was very impressed with the results I'm getting with my system.
I have other more complicated routine that takes too long to be processed millions of times.
It would be a lot of work to do a new routine to accept alphanumeric groups with different sizes?
All groups inside the string always separated by space and lower case.
example:
Code: Select all
string1="ac3 b9d45 b ks23 al97 ac5 al99"
string2="b xl33 ac3 bxp12 ac5"
Result = Grep_alfa(@string1, @string2)
it's possible?
thanks
Fernando
Re: A small procedure asm
There's no need to do that. I just try to help out sometimes as do many others on this forum.fvillanova wrote:Your routine will help me a lot, my program now makes instant calculations.
I'll put your name in the system, what's your full name and country?
Unfortunately it can't be done like I did the previous one.fvillanova wrote:It would be a lot of work to do a new routine to accept alphanumeric groups with different sizes?
All groups inside the string always separated by space and lower case.
Like with the previous issue, it always helps to have more information when you consider what approach is best.
Probably a simple hash for each group can speed up the search procedure.
Is there a maximum to the length of each element and the number of elements inside a string in this case ?
Is each element inside a string unique or can it occur multiple times ?
Is it most likely that there are many matches for each comparison or a few ?
Another thing that is important is how you compare.
If both strings are different each time, how you handle it best is very different to having the first string and comparing it against a thousand other strings.
Windows (x64)
Raspberry Pi OS (Arm64)
Raspberry Pi OS (Arm64)
Re: A small procedure asm
Problem is now you don't have the slightest idea of what's happening in "your" code and you made the transition from bad Basic programmer to code gluer.fvillanova wrote: My teacher was very impressed with the results I'm getting with my system.
As infratec shown you really didn't need ASM, you just needed better Basic.
I believe it would have been a lot better for you to get the hints from that and try to make the transition (maybe in your reach with some work) from bad Basic programmer to decent Basic programmer and leave ASM alone for now.
It's symptomatic you saw your code was slow and jumped directly to ask for an ASM version.
90% of the time to get 2 - 100 times gains you just need to become a better programmer in the same language and equally important (and a consequence of the former) to select the appropriate algorithm instead of the first thing it comes to your mind (the clear approach followed with your original code when you even calculate the same complex expression at each iteration when it wasn't needed).
Wouldn't be better for you to concentrate on the above two points instead of copy/paste some magic code you can't even touch anymore ?
If you have to read just one book read this -> http://www.nostarch.com/greatcode.htm and you'll see things in a way you never imagined before. And you'll write code at least 10 time faster.
Knowing how computers works and having a vague idea of how a compiler work would help you enormously in writing better code.
This remark has nothing to do with Wilbert or the fact hand crafted ASM is actually unbeatable in both speed and size.
"Have you tried turning it off and on again ?"
A little PureBasic review
A little PureBasic review
-
- Addict
- Posts: 4527
- Joined: Thu Jun 07, 2007 3:25 pm
- Location: Berlin, Germany
Re: A small procedure asm
Very wise reply, luis!
This could (almost) be the preface of a book about computer programming.
This could (almost) be the preface of a book about computer programming.
And he only can hope that his teacher will not ask him to explain in detail how "his" code works.luis wrote:Problem is now you don't have the slightest idea of what's happening in "your" codefvillanova wrote: My teacher was very impressed with the results I'm getting with my system.
-
- User
- Posts: 70
- Joined: Wed May 02, 2012 2:17 am
- Location: Brazil
Re: A small procedure asm
In fact I'm converting an old program that is running in Perl as follows:wilbert wrote: Is there a maximum to the length of each element and the number of elements inside a string in this case ?
Is each element inside a string unique or can it occur multiple times ?
Is it most likely that there are many matches for each comparison or a few ?
Code: Select all
$string1=~ s/ /\|/g; @array=split(/ /,$string2);
$count=grep /$string1/,@array;
Is currently as follows in Purebasic, because the solution from "infratec" via PeekS() is not applicable for these
strings with different sizes of elements.
Code: Select all
Procedure.b grep(string1.s, string2.s)
occur=0
For j=1 To CountString(string2," ")+1
If FindString(string1, StringField(string2, j," ")): occur+1: EndIf
Next
ProcedureReturn occur
EndProcedure
with a similar solution that you get with the elements from 00 to 99!
There is no limit to the number of elements within the strings ... but usually no more than 100, 300 up to 1024.
Elements within the strings can occur more than once often, may occur multiple times.
But in Perl I have only count once, if more than once count one.
The correct is to count exactly how many times the element of string2 occurs in string1.
In string2 the elements may also occur more than once.
The maximum size of an element within the string 1 or string2 is 32 characters (numbers and letters)
and at least one, see example:
Code: Select all
string1="ac3 b9d45 b ks23 al97 ac5 al99 vs42159ssbpx"
string2="b xl33 ac3 bxp12 ac5 ks27t2l9"
I did not understand 100% the comments from "luis and Little John", but I will try to respond.
-
- User
- Posts: 70
- Joined: Wed May 02, 2012 2:17 am
- Location: Brazil
Re: A small procedure asm
Hi Luis and Little John,luis wrote:fvillanova wrote: My teacher was very impressed with the results I'm getting with my system.
See, I have programs and systems developed by me in other languages (perln and APP/Studio) that are great for creating programs on the Internet and mobile devices respectively.
Now I'm converting an existing program in Perl (developed by me) to windows (32/64) that is already up and running 100% in PureBasic.
Help from Wilbert was very valuable only to speed up a command that was already
working in my program, my teacher is impressed with my system, is not with any particular routine or
programming language, he liked the 21 screens of my program with dozens of functions and statistical calculations.
I work with statistics and mathematical calculations distributions since I graduated from college a long time.
I'm 57 years old, the current teacher I mentioned is teaching market research techniques in a course I'm doing.
I do not have fluent English and therefore you should misunderstood what I'm doing.
I've started to analyze step by step the routine performed by Wilbert and understand several basic commands,
already got the Internet on various documentation asm and I intend to continue studying.
Now I'm just optimizing and enhancing screens of my program
and the name Wilbert on the about screen of my program would be just.
Not a sold or marketed program, will be distributed to friends and known people.
The situation to explain how a code works within my program will never happen!
I was misunderstood, sorry.