It is currently Sat Jan 23, 2021 2:23 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 58 posts ]  Go to page 1, 2, 3, 4  Next
Author Message
 Post subject: A small procedure asm
PostPosted: Thu Apr 09, 2015 7:51 pm 
Offline
User
User

Joined: Wed May 02, 2012 2:17 am
Posts: 25
Location: Brazil
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


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Fri Apr 10, 2015 2:26 pm 
Offline
Always Here
Always Here

Joined: Sun Sep 07, 2008 12:45 pm
Posts: 5209
Location: Germany
Not assembler, but definately faster:
Code:
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


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


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Fri Apr 10, 2015 5:11 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3710
Location: Netherlands
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 ?

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Fri Apr 10, 2015 6:07 pm 
Offline
User
User

Joined: Wed May 02, 2012 2:17 am
Posts: 25
Location: Brazil
infratec wrote:
Not assembler, but definately faster:
Code:
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


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


Hi, 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)


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Fri Apr 10, 2015 6:18 pm 
Offline
User
User

Joined: Wed May 02, 2012 2:17 am
Posts: 25
Location: Brazil
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 ?

Hi,
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


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Fri Apr 10, 2015 7:02 pm 
Offline
User
User

Joined: Wed May 02, 2012 2:17 am
Posts: 25
Location: Brazil
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


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Fri Apr 10, 2015 7:36 pm 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3710
Location: Netherlands
fvillanova wrote:
25 times faster, someone can do faster?

If you are 100% sure your strings look like that, you can do something like this
Code:
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))

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Fri Apr 10, 2015 9:02 pm 
Offline
User
User

Joined: Wed May 02, 2012 2:17 am
Posts: 25
Location: Brazil
wilbert wrote:
fvillanova wrote:
25 times faster, someone can do faster?


Code:
Input1.s = "02 09 15 21 37 59 72 81"
Input2.s = "07 11 15 22 37 40"

Wow man!
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


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Sat Apr 11, 2015 5:56 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3710
Location: Netherlands
fvillanova wrote:
This Procedure will work for any amount numbers (XX) within the strings?

If your strings always look exactly like this (2 numbers, space, 2 numbers etc.) it will work.
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:
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))

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Sun Apr 12, 2015 4:56 am 
Offline
User
User

Joined: Wed May 02, 2012 2:17 am
Posts: 25
Location: Brazil
wilbert wrote:
fvillanova wrote:
This Procedure will work for any amount numbers (XX) within the strings?

If your strings always look exactly like this (2 numbers, space, 2 numbers etc.) it will work.
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.


Hi Wilbert,
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:
string1="ac3 b9d45 b ks23 al97 ac5 al99"
string2="b xl33 ac3 bxp12 ac5"

Result = Grep_alfa(@string1, @string2)

(Result is 3 in the above example)
it's possible?
thanks
Fernando


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Sun Apr 12, 2015 5:33 am 
Offline
PureBasic Expert
PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3710
Location: Netherlands
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?

There's no need to do that. I just try to help out sometimes as do many others on this forum. :wink:

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.

Unfortunately it can't be done like I did the previous one.
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.

_________________
macOS 10.15 Catalina, Windows 10


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Sun Apr 12, 2015 11:42 am 
Offline
Addict
Addict
User avatar

Joined: Wed Aug 31, 2005 11:09 pm
Posts: 3698
Location: Italy
fvillanova wrote:
My teacher was very impressed with the results I'm getting with my system.


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.
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.

_________________
[ My little PureBasic review ]


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Sun Apr 12, 2015 1:31 pm 
Offline
Addict
Addict

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3967
Location: Berlin, Germany
Very wise reply, luis!

This could (almost) be the preface of a book about computer programming. :-)

luis wrote:
fvillanova wrote:
My teacher was very impressed with the results I'm getting with my system.


Problem is now you don't have the slightest idea of what's happening in "your" code

And he only can hope that his teacher will not ask him to explain in detail how "his" code works. :twisted:

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Mon Apr 13, 2015 9:14 pm 
Offline
User
User

Joined: Wed May 02, 2012 2:17 am
Posts: 25
Location: Brazil
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 ?

In fact I'm converting an old program that is running in Perl as follows:
Code:
$string1=~ s/ /\|/g; @array=split(/ /,$string2);
$count=grep /$string1/,@array;

Perl already has the grep command internally, is very fast!

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:
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

I just need to know how many times the element from string2 occurs in string1, it's working, I want to speed up
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:
string1="ac3 b9d45 b ks23 al97 ac5 al99 vs42159ssbpx"
string2="b xl33 ac3 bxp12 ac5 ks27t2l9"


are generally elements with 5 or 7 to 12 characters but may be up to 32, this is the limit.

I did not understand 100% the comments from "luis and Little John", but I will try to respond.


Top
 Profile  
Reply with quote  
 Post subject: Re: A small procedure asm
PostPosted: Mon Apr 13, 2015 9:16 pm 
Offline
User
User

Joined: Wed May 02, 2012 2:17 am
Posts: 25
Location: Brazil
luis wrote:
fvillanova wrote:
My teacher was very impressed with the results I'm getting with my system.

Hi Luis and Little John,
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.


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 58 posts ]  Go to page 1, 2, 3, 4  Next

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye