A small procedure asm
Re: A small procedure asm
Fernando, it's all good then (I think).
Speaking for myself I didn't misunderstand you, I didn't make assumptions about your age or your teacher (both not pertinent to me).
I commented on the only two things you made available: some naive Basic code which can be re-written to perform faster of an order of magnitude without even thinking about it and your request for someone to write something faster for you and specifically in ASM.
If you'd asked "I wrote this, it works, but it's very slow. Can be written in a better way to make it faster ?" it would have been different.
So I still stand behind all the stuff I wrote based on the above.
The one part you are telling me now which I didn't expect (and about which I made an assumption) is the fact you are working to understand the ASM code.
It was a general opinion about something I see happening often in all programming forums, and some unsolicited advice I thought it was good advice.
Being unsolicited you are more then ever free to throw it out of the window if you feel it was off the mark.
Anyway to make it clear, please understand I didn't write that to denigrate you or anything like that, the purpose was different.
Speaking for myself I didn't misunderstand you, I didn't make assumptions about your age or your teacher (both not pertinent to me).
I commented on the only two things you made available: some naive Basic code which can be re-written to perform faster of an order of magnitude without even thinking about it and your request for someone to write something faster for you and specifically in ASM.
If you'd asked "I wrote this, it works, but it's very slow. Can be written in a better way to make it faster ?" it would have been different.
So I still stand behind all the stuff I wrote based on the above.
The one part you are telling me now which I didn't expect (and about which I made an assumption) is the fact you are working to understand the ASM code.
It was a general opinion about something I see happening often in all programming forums, and some unsolicited advice I thought it was good advice.
Being unsolicited you are more then ever free to throw it out of the window if you feel it was off the mark.
Anyway to make it clear, please understand I didn't write that to denigrate you or anything like that, the purpose was different.
"Have you tried turning it off and on again ?"
A little PureBasic review
A little PureBasic review
-
- User
- Posts: 70
- Joined: Wed May 02, 2012 2:17 am
- Location: Brazil
Re: A small procedure asm
My English is reasonable to read and understand manuals and documentation, do it a long time,luis wrote:Fernando, it's all good then (I think)
but it is lousy to understand issues and vocabularies that do not see often.
conclusion:
I initially when read your comment I understood that I was using
the work from "wilbert" as developed by me and that I should
spend more time trying hard to program better, I got it wrong, sorry.
I'm already making changes in various parts of my program using the command Peek? and Poke? as suggested
by "infratec" initially, I always developed my programming knowledge looking codes made by others,
so I can learn and create new completely different routines.
That is, if you understand some of my text as offensive or out of context please do not believe,
because it sure was my mistake to write with my poor English.
If Wilbert can help me in the second routine I'll be very grateful.
If you need something from Sao Paulo do not hesitate to ask, I will be happy
to help you, have you ever been in Brazil?
-
- Addict
- Posts: 4519
- Joined: Thu Jun 07, 2007 3:25 pm
- Location: Berlin, Germany
Re: A small procedure asm
Hello Fernando,
my reply was not meant offensive.
I am sorry for any misunderstandings.
my reply was not meant offensive.
I see this as well, and I'm drawing the same general conclusions as luis does.luis wrote:It was a general opinion about something I see happening often in all programming forums
I am sorry for any misunderstandings.
Re: A small procedure asm
still think more info is needed before diving into asm
uses sax hash but I can't rule out collisions
takes around 13 seconds ascii and 16 seconds unicode
what's the maximum length of a field in an input string?
what's the maximum length of an input string?
uses sax hash but I can't rule out collisions
takes around 13 seconds ascii and 16 seconds unicode
what's the maximum length of a field in an input string?
what's the maximum length of an input string?
Code: Select all
Structure char
c.c[0]
EndStructure
Procedure grep(*s1.char,*s2.char)
Protected a,b,c,hash,hash1,rep
While *s1\c[a] <> 0
hash=0
While *s1\c[b] <> ' ' And *s1\c[b] <> 0
hash ! (((hash <<5) + (hash >> 2)) + *s1\c[b])
b+1
Wend
b+1
a=b
c=0
While *s2\c[c] <> 0
hash1=0
While *s2\c[c] <> ' ' And *s2\c[c] <> 0
hash1 ! (((hash1 <<5) + (hash1 >> 2)) + *s2\c[c])
c+1
Wend
If hash=hash1
rep+1
EndIf
c+1
Wend
Wend
ProcedureReturn rep
EndProcedure
string1.s="ac3 b9d45 b ks23 al97 ac5 al99 vs42159ssbpx"
string2.s ="b xl33 ac3 bxp12 ac5 ks27t2l9"
result = grep(@string1,@string2)
MessageRequester("Result",Str(Result))
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 11, Manjaro, Raspberry Pi OS
Re: A small procedure asm
Hello Fernando. This is a programming language forum, and not an English language one. So don't worry about it - your English is good and gets your message across well. That's important.fvillanova wrote:My English is reasonable to read and understand manuals and documentation, do it a long time, but it is lousy to understand issues and vocabularies that do not see often.
Many of the other forum members here aren't native English speakers either. Nevertheless, language or not, jumping to conclusions about your intentions or your programming aptitude is in poor taste. But like Little John said, it's not meant to be offensive.
The great thing about PureBasic is its ability to include inline Assembly. That's a real bonus, especially for speed-critical routines. We continue to enjoy the simplicity of a Basic programming environment, while being able to take advantage of Assembly when required.
It's a feature, so why not use it.
Texas Instruments TI-99/4A Home Computer: the first home computer with a 16bit processor, crammed into an 8bit architecture. Great hardware - Poor design - Wonderful BASIC engine. And it could talk too! Please visit my YouTube Channel
Re: A small procedure asm
Here's my attempt (without asm)fvillanova wrote: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
It allows 1024 elements per string with a maximum of 32 characters per element.
Speed can be further improved by converting things to asm but in that case it would be convenient to know in advance if you are using ascii or unicode and 32 or 64 bits.
Code: Select all
DisableDebugger
; max 1024 elements of 32 characters per string
Structure ElCount
l.u[32]
EndStructure
Structure El1024
*p[1024]
EndStructure
Structure Elements
l.El1024[32]
EndStructure
Threaded Elements.Elements
Procedure.i Grep(*String1.Character, *String2.Character)
Protected ec.ElCount, *p = *String1
Protected.i j, l, result
Repeat
If *String1\c <= 32
If *String1 > *p
CompilerIf #PB_Compiler_Unicode
l = (*String1 - *p) >> 1 - 1
CompilerElse
l = (*String1 - *p) - 1
CompilerEndIf
Elements\l[l]\p[ec\l[l]] = *p
ec\l[l] + 1
EndIf
If *String1\c = 0
Break
EndIf
*String1 + SizeOf(Character)
*p = *String1
Else
*String1 + SizeOf(Character)
EndIf
ForEver
*p = *String2
Repeat
If *String2\c <= 32
If *String2 > *p
CompilerIf #PB_Compiler_Unicode
l = (*String2 - *p) >> 1
CompilerElse
l = (*String2 - *p)
CompilerEndIf
j = ec\l[l - 1]
While j
j - 1
CompilerIf #PB_Compiler_Unicode
If CompareMemory(Elements\l[l - 1]\p[j], *p, l << 1)
result + 1
EndIf
CompilerElse
If CompareMemory(Elements\l[l - 1]\p[j], *p, l)
result + 1
EndIf
CompilerEndIf
Wend
EndIf
If *String2\c = 0
Break
EndIf
*String2 + SizeOf(Character)
*p = *String2
Else
*String2 + SizeOf(Character)
EndIf
ForEver
ProcedureReturn result
EndProcedure
String1.s = "ac3 b9d45 b ks23 al97 ac5 al99 vs42159ssbpx"
String2.s = "b xl33 ac3 bxp12 ac5 ks27t2l9"
t1 = ElapsedMilliseconds()
For i = 1 To 12000000
Result = Grep(@String1, @String2)
Next
t2 = ElapsedMilliseconds()
MessageRequester("Result (" + Str(t2-t1) + " ms)", Str(Result))
Last edited by wilbert on Tue Apr 14, 2015 12:57 pm, edited 7 times in total.
Windows (x64)
Raspberry Pi OS (Arm64)
Raspberry Pi OS (Arm64)
Re: A small procedure asm
Hi,
My little version (with PB RegularExpression)
Or without debug display to go faster
(I do not know if it's faster or not)
My little version (with PB RegularExpression)
Code: Select all
Where$ = "ac3 b9d45 b ks23 al97 ac5 al99 vs42159ssbpx"
What$ = "b xl33 ac3 bxp12 ac5 ks27t2l9"
For i = 1 To CountString(What$, " ") + 1
StrToFind$ = StringField(What$, i, " ")
CreateRegularExpression(0, StrToFind$)
If MatchRegularExpression(0, Where$)
Debug "Yes: " + StrToFind$
Result + 1
Else
Debug "No : " + StrToFind$
EndIf
FreeRegularExpression(0)
Next
Debug "=> Total Match: " + Str(Result)
Code: Select all
Where$ = "ac3 b9d45 b ks23 al97 ac5 al99 vs42159ssbpx"
What$ = "b xl33 ac3 bxp12 ac5 ks27t2l9"
For i = 1 To CountString(What$, " ") + 1
StrToFind$ = StringField(What$, i, " ")
CreateRegularExpression(0, StrToFind$)
If MatchRegularExpression(0, Where$)
Result + 1
EndIf
FreeRegularExpression(0)
Next
Debug "=> Total Match: " + Str(Result)
- Michael Vogel
- Addict
- Posts: 2666
- Joined: Thu Feb 09, 2006 11:27 pm
- Contact:
Re: A small procedure asm
Tried to see if 'Map' could speed up some things (doesn't seem so - so I did my own hash version at the end), but why not keep the 'StringFind', is it that slow ?
Code: Select all
RandomSeed(0)
s1.s
s2.s
For i=0 To 999
s1=s1+Chr('a'+Random(25))+Str(Random(99))+"z"+Str(Random(99))+" "
s2=s2+"z"+Str(Random(99))+"x"+Str(Random(99))+" "
Next i
s1+"ac3 b9d45 b ks23 al97 ac5 al99 vs42159ssbpx"
s2+"b xl33 ac3 bxp12 ac5 ks27t2l9"
Procedure StringFieldInitialize(*string.string,char)
Global *StringFieldMem.Character
Global StringFieldChar
*StringFieldMem=*string
StringFieldChar=char
EndProcedure
Procedure.s StringFieldNext()
Protected Field.s
While *StringFieldMem\c<>StringFieldChar And *StringFieldMem\c
Field+Chr(*StringFieldMem\c)
*StringFieldMem+SizeOf(Character)
Wend
If *StringFieldMem\c
*StringFieldMem+SizeOf(Character)
EndIf
ProcedureReturn Field
EndProcedure
Procedure.i GrepHash(s1.s,s2.s)
Protected n,i,x
Protected NewMap hash.i()
If s1 And s2
x=CountString(s1," ")+1
StringFieldInitialize(@s1,' ')
For i=1 To x
AddMapElement(hash(),StringFieldNext())
Next i
x=CountString(s2," ")+1
StringFieldInitialize(@s2,' ')
For i=1 To x
If FindMapElement(hash(),StringFieldNext())
n+1
EndIf
Next i
EndIf
ProcedureReturn n
EndProcedure
Procedure.i GrepFind(s1.s,s2.s)
Protected n,i,x
If s1 And s2
s1=" "+s1+" "
x=CountString(s2," ")+1
StringFieldInitialize(@s2,' ')
For i=1 To x
If FindString(s1," "+StringFieldNext()+" ")
n+1
EndIf
Next i
EndIf
ProcedureReturn n
EndProcedure
Procedure.i GrepBird(s1.s,s2.s)
Protected n,i,j,x,y
Protected Dim Bird.s(4095)
Protected s.s
If s1 And s2
x=CountString(s1," ")+1
StringFieldInitialize(@s1,' ')
For i=1 To x
s=StringFieldNext()
y=PeekW(@s)
y=(y!(y>>5))&$FFF
If Bird(y)=""
Bird(y)="|"
EndIf
Bird(y)+s+"|"
Next i
x=CountString(s2," ")+1
StringFieldInitialize(@s2,' ')
For i=1 To x
s=StringFieldNext()+"|"
y=PeekW(@s)
y=(y!(y>>5))&$FFF
If FindString(Bird(y),"|"+s)
n+1
EndIf
Next i
EndIf
ProcedureReturn n
EndProcedure
DisableDebugger
time-ElapsedMilliseconds()
For i=0 To 99
;r=GrepHash(s1,s2)
;r=GrepFind(s1,s2)
r=GrepBird(s1,s2)
Next i
time+ElapsedMilliseconds()
MessageRequester(">|<","Result = "+Str(r)+#CR$+"Time = "+Str(time)+"ms")
-
- User
- Posts: 70
- Joined: Wed May 02, 2012 2:17 am
- Location: Brazil
Re: A small procedure asm
Hi TI-994A,TI-994A wrote: The great thing about PureBasic is its ability to include inline Assembly. That's a real bonus, especially for speed-critical routines....
It's a feature, so why not use it.
You with a few words and good perception correctly summarized my position, thank you for your comments.
This ability to introduce routines in assembler in the program's critical parts is a great advantage of PureBasic.
My surprise was discovering that replacing the command StringField by Peeks will accelerate the performance of a program that uses this a million times.
I thought the "StringField" command within the "FindString" command would be compiled in an optimized and fast code, but I saw no!
Even more impressive was seeing the same routine with asm commands made by Wilbert, amazing!
I like to make rotines with Perl where there are incredible commands such as the famous "Grep"
that has numerous different synthases, with it you can solve and create routines that do virtually everything!
Surely Grep is the most powerful command created in the last two decades, those who do not know should search about it in the Internet.
Who wants to know the origins of this command can access the link below:
http://www.manning.com/maher/ch03.pdf
I think the PureBasic developer staff should analyze the possibility of creating a similar command "Grep" from Perl,
if he did 20% of the existing perl Grep command would be a great success!
Correct me if I'm talking nonsense!
thanks
Fernando
Re: A small procedure asm
Actually, with the debugger turned off, your original code, which utilised the CountString(), FindString(), and StringField() functions, took only about 30 seconds to execute. Still not too bad for string-intensive iterations.fvillanova wrote:...My surprise was discovering that replacing the command StringField by Peeks will accelerate the performance of a program that uses this a million times.
And by simply moving the CountString() function out of the loop, your code executed in just 10 seconds:
Code: Select all
Procedure.b grep(string1.s, string2.s)
occur=0
;12000000 iterations in just 10 seconds
;if CountString() is moved out of the loop
string2Count = CountString(string2, " ") + 1
;For j = 1 To CountString(string2, " ") + 1
For j = 1 To string2Count
If FindString(string1, StringField(string2, j, " ")) : occur + 1 : EndIf
Next
ProcedureReturn occur
EndProcedure
Based on this criteria, you could also convert the number-strings into integer-arrays to remarkably improve the speed:fvillanova wrote:...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"
Code: Select all
DisableDebugger
Procedure.i IntMatch(Array i1.i(1), Array i2.i(1))
i1Len = ArraySize(i1())
i2Len = ArraySize(i2())
For i = 1 To i1Len
For ii = 1 To i2Len
If i1(i) = i2(ii)
match + 1
EndIf
Next ii
Next i
ProcedureReturn match
EndProcedure
Input1.s = "02 09 15 21 37 59 72 81"
Input2.s = "07 11 15 22 37 40"
;convert the strings into integer-arrays
i1 = CountString(Input1, " ") + 1
i2 = CountString(Input2, " ") + 1
Dim intInput1(i1)
Dim intInput2(i2)
For i = 1 To i1
intInput1(i) = Val(StringField(Input1, i, " "))
Next i
For i = 1 To i2
intInput2(i) = Val(StringField(Input2, i, " "))
Next i
;then run the arrays through the test
t1 = ElapsedMilliseconds()
For i = 1 To 12000000
Result = IntMatch(intInput1(), intInput2())
Next
t2 = ElapsedMilliseconds()
r$ = Str(Result) + " matches found" +
#CRLF$ + "in " + Str(t2 - t1) + " ms"
MessageRequester("Integer Match", r$)
Ultimately, it all depends on your requirements. And most of the time, PureBasic is equal to the task.
Texas Instruments TI-99/4A Home Computer: the first home computer with a 16bit processor, crammed into an 8bit architecture. Great hardware - Poor design - Wonderful BASIC engine. And it could talk too! Please visit my YouTube Channel
-
- User
- Posts: 70
- Joined: Wed May 02, 2012 2:17 am
- Location: Brazil
Re: A small procedure asm
Hi Wilbert,wilbert wrote: It allows 1024 elements per string with a maximum of 32 characters per element.
Speed can be further improved by converting things to asm but in that case it would be convenient to know in advance if you are using ascii or unicode and 32 or 64 bits.
Sorry for the delay in responding, I had to travel 3 times in the last 10 days.
The routine uses only ASCII for strings.
Currently I use compilation in 32-bit on a 64 environment.
I did tests today with this routine and is very good, is fast!
Limiting the amount in 1024 and 32 the maximum element size is perfect.
thanks
Fernando
Re: A small procedure asm
What I did is create 32 lists (one for each size) and fill those with the positions where those elements occur so it only has to search the elements with the correct size.fvillanova wrote:I did tests today with this routine and is very good, is fast!
Limiting the amount in 1024 and 32 the maximum element size is perfect.
This works pretty well if the size of the elements has a lot of variation. If a lot of elements have the same size, using a hash should be a better approach.
Windows (x64)
Raspberry Pi OS (Arm64)
Raspberry Pi OS (Arm64)
Re: A small procedure asm
A Trie would probably be better to use, something like this perhaps, it shaves off a few more secondswilbert wrote:What I did is create 32 lists (one for each size) and fill those with the positions where those elements occur so it only has to search the elements with the correct size.fvillanova wrote:I did tests today with this routine and is very good, is fast!
Limiting the amount in 1024 and 32 the maximum element size is perfect.
This works pretty well if the size of the elements has a lot of variation. If a lot of elements have the same size, using a hash should be a better approach.
takes ~5 seconds to complete 12,000,000 iterations in ascii and ~6 in unicode
Code: Select all
Structure char
c.c[0]
EndStructure
Structure Trinode
node.i[255]
value.i
EndStructure
Structure trie
t.Trinode[1024]
EndStructure
Procedure grep(*s1.char,*s2.char)
Protected a,b,ind,rep,ct
Protected *current.Trinode
Static root.trie
Static Grep_itr=1
While *s1\c[a] <> 0
*current = root\t[0]
While *s1\c[b] > 32
ind = *s1\c[b]
If Not *current\node[ind]
ct+1
*current\node[ind] = root\t[ct]
EndIf
*current = *current\node[ind]
b+1
Wend
*current\value = Grep_itr
b+1
a=b
Wend
a=0
b=0
While *s2\c[a] <> 0
*current = root\t[0]
While *s2\c[b] > 32
ind = *s2\c[b]
If Not *current\node[ind]
b+1
Goto l1
Else
*current = *current\node[ind]
EndIf
b+1
Wend
If *current\value = Grep_itr
rep+1
EndIf
l1:
b+1
a=b
Wend
Grep_itr+1
ProcedureReturn rep
EndProcedure
string1.s="ac3 b9d45 b ks23 al97 ac5 al99 vs42159ssbpx"
string2.s ="b xl33 ac3 bxp12 ac5 ks27t2l9"
result = grep(@string1,@string2)
MessageRequester("Result",Str(Result))
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 11, Manjaro, Raspberry Pi OS
Re: A small procedure asm
It doesn't work as it shouldidle wrote:A Trie would probably be better to use, something like this perhaps, it shaves off a few more seconds
takes ~5 seconds to complete 12,000,000 iterations in ascii and ~6 in unicode
Code: Select all
string1.s = "02 09 15 21 37 59 72 81"
string2.s = "07 11 15 22 37 40"
result = grep(@string1,@string2)
MessageRequester("Result",Str(Result))
string1.s= "07 11 15 22 37 40"
string2.s= "02 09 15 21 37 59 72 81"
result = grep(@string1,@string2)
MessageRequester("Result",Str(Result))
Windows (x64)
Raspberry Pi OS (Arm64)
Raspberry Pi OS (Arm64)
Re: A small procedure asm
yes I noticed that and haven't found a way to get around it using the static structure
I had thought it'd work using a static counter to set a node value but it hasn't.
All I can do is iterate back through the first string and reset the trie that way but then it takes ~10 seconds
I had thought it'd work using a static counter to set a node value but it hasn't.
All I can do is iterate back through the first string and reset the trie that way but then it takes ~10 seconds
Code: Select all
Structure char
c.c[0]
EndStructure
Structure Trinode
node.i[255]
value.i
EndStructure
Structure trie
t.Trinode[1024]
EndStructure
Procedure grep(*s1.char,*s2.char)
Protected a,b,ind,rep,ct
Protected *current.Trinode
Static root.trie
Static Grep_itr=1
While *s1\c[a] <> 0
*current = root\t[0]
While *s1\c[b] > 32
ind = *s1\c[b]
If Not *current\node[ind]
ct+1
*current\node[ind] = root\t[ct]
EndIf
*current = *current\node[ind]
b+1
Wend
*current\value = Grep_itr
b+1
a=b
Wend
a=0
b=0
While *s2\c[a] <> 0
*current = root\t[0]
While *s2\c[b] > 32
ind = *s2\c[b]
If Not *current\node[ind]
b+1
Goto l1
Else
*current = *current\node[ind]
EndIf
b+1
Wend
If *current\value = Grep_itr
rep+1
EndIf
l1:
b+1
a=b
Wend
Grep_itr+1
a=0
b=0
While *s1\c[a] <> 0
*current = root\t[0]
While *s1\c[b] > 32
ind = *s1\c[b]
If Not *current\node[ind]
ct+1
*current\node[ind] = root\t[ct]
EndIf
t = *current\node[ind]
*current\node[ind] = 0
*current = t
b+1
Wend
b+1
a=b
Wend
ProcedureReturn rep
EndProcedure
string1.s="ac3 b9d45 b ks23 al97 ac5 al99 vs42159ssbpx"
string2.s ="b xl33 ac3 bxp12 ac5 ks27t2l9"
result = grep(@string1,@string2)
MessageRequester("Result",Str(Result))
Input1.s = "02 09 15 21 37 59 72 81"
Input2.s = "ac3 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 11, Manjaro, Raspberry Pi OS