A small procedure asm

Bare metal programming in PureBasic, for experienced users
fvillanova
User
User
Posts: 70
Joined: Wed May 02, 2012 2:17 am
Location: Brazil

A small procedure asm

Post by fvillanova »

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
infratec
Always Here
Always Here
Posts: 6810
Joined: Sun Sep 07, 2008 12:45 pm
Location: Germany

Re: A small procedure asm

Post by infratec »

Not assembler, but definately faster:

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

Re: A small procedure asm

Post by wilbert »

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 ?
Windows (x64)
Raspberry Pi OS (Arm64)
fvillanova
User
User
Posts: 70
Joined: Wed May 02, 2012 2:17 am
Location: Brazil

Re: A small procedure asm

Post by fvillanova »

infratec wrote:Not assembler, but definately faster:

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

Re: A small procedure asm

Post by fvillanova »

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

Re: A small procedure asm

Post by fvillanova »

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

Re: A small procedure asm

Post by wilbert »

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

Re: A small procedure asm

Post by fvillanova »

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"
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
wilbert
PureBasic Expert
PureBasic Expert
Posts: 3870
Joined: Sun Aug 08, 2004 5:21 am
Location: Netherlands

Re: A small procedure asm

Post by wilbert »

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

Re: A small procedure asm

Post by fvillanova »

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

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

Re: A small procedure asm

Post by wilbert »

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.
Windows (x64)
Raspberry Pi OS (Arm64)
User avatar
luis
Addict
Addict
Posts: 3876
Joined: Wed Aug 31, 2005 11:09 pm
Location: Italy

Re: A small procedure asm

Post by luis »

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.
"Have you tried turning it off and on again ?"
A little PureBasic review
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: A small procedure asm

Post by Little John »

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

Re: A small procedure asm

Post by fvillanova »

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

$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: 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
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: Select all

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

Re: A small procedure asm

Post by fvillanova »

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