# PureBasic Forum

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

 All times are UTC + 1 hour

 Page 1 of 4 [ 58 posts ] Go to page 1, 2, 3, 4  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: A small procedure asmPosted: Thu Apr 09, 2015 7:51 pm
 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

 Post subject: Re: A small procedure asmPosted: Fri Apr 10, 2015 2:26 pm
 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

 Post subject: Re: A small procedure asmPosted: Fri Apr 10, 2015 5:11 pm
 PureBasic Expert

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

 Post subject: Re: A small procedure asmPosted: Fri Apr 10, 2015 6:07 pm
 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

 Post subject: Re: A small procedure asmPosted: Fri Apr 10, 2015 6:18 pm
 User

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

 Post subject: Re: A small procedure asmPosted: Fri Apr 10, 2015 7:02 pm
 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

 Post subject: Re: A small procedure asmPosted: Fri Apr 10, 2015 7:36 pm
 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
CompilerElse
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
CompilerElse
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

 Post subject: Re: A small procedure asmPosted: Fri Apr 10, 2015 9:02 pm
 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

 Post subject: Re: A small procedure asmPosted: Sat Apr 11, 2015 5:56 am
 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]
!shl cx, 12
!shr ecx, 12
CompilerElse
mov cx, [rdx]
!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
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

 Post subject: Re: A small procedure asmPosted: Sun Apr 12, 2015 4:56 am
 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

 Post subject: Re: A small procedure asmPosted: Sun Apr 12, 2015 5:33 am
 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.

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

 Post subject: Re: A small procedure asmPosted: Sun Apr 12, 2015 11:42 am

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.

_________________

Top

 Post subject: Re: A small procedure asmPosted: Sun Apr 12, 2015 1:31 pm

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.

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

Top

 Post subject: Re: A small procedure asmPosted: Mon Apr 13, 2015 9:14 pm
 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

 Post subject: Re: A small procedure asmPosted: Mon Apr 13, 2015 9:16 pm
 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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 4 [ 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 forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ PureBasic    Coding Questions    Game Programming    3D Programming    Assembly Programming    The PureBasic Editor    The PureBasic Form Designer    General Discussion    Feature Requests and Wishlists    Tricks 'n' Tips Bug Reports    Bugs - Windows    Bugs - Linux    Bugs - Mac OSX    Bugs - IDE    Bugs - Documentation OS Specific    AmigaOS    Linux    Windows    Mac OSX Miscellaneous    Announcement    Off Topic Showcase    Applications - Feedback and Discussion    PureFORM & JaPBe    TailBite