Page 2 of 9
Re: A small procedure asm
Posted: Mon Apr 13, 2015 11:12 pm
by luis
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.
Re: A small procedure asm
Posted: Tue Apr 14, 2015 1:19 am
by fvillanova
luis wrote:Fernando, it's all good then (I think)
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.
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?
Re: A small procedure asm
Posted: Tue Apr 14, 2015 3:49 am
by Little John
Hello Fernando,
my reply was not meant offensive.
luis wrote:It was a general opinion about something I see happening often in all programming forums
I see this as well, and I'm drawing the same general conclusions as luis does.
I am sorry for any misunderstandings.
Re: A small procedure asm
Posted: Tue Apr 14, 2015 6:07 am
by idle
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?
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))
Re: A small procedure asm
Posted: Tue Apr 14, 2015 8:00 am
by TI-994A
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.
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.
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.
Re: A small procedure asm
Posted: Tue Apr 14, 2015 8:29 am
by wilbert
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
Here's my attempt (without asm)
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))
Re: A small procedure asm
Posted: Tue Apr 14, 2015 10:23 am
by Marc56us
Hi,
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)
Or without debug display to go faster
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)
(I do not know if it's faster or not)
Re: A small procedure asm
Posted: Tue Apr 14, 2015 2:47 pm
by Michael Vogel
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")
Re: A small procedure asm
Posted: Tue Apr 14, 2015 5:47 pm
by fvillanova
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.
Hi TI-994A,
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
Posted: Wed Apr 15, 2015 1:57 pm
by TI-994A
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.
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.
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
Pretty decent string-handling on PureBasic's part.
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"
Based on this criteria, you could also convert the number-strings into integer-arrays to remarkably improve the speed:
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$)
This performed 12 million iterations in just 2 seconds, with no assembly.
Ultimately, it all depends on your requirements. And most of the time, PureBasic is equal to the task.
Re: A small procedure asm
Posted: Fri Apr 17, 2015 2:27 am
by fvillanova
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.
Hi Wilbert,
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
Posted: Fri Apr 17, 2015 5:54 am
by wilbert
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.
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.
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.
Re: A small procedure asm
Posted: Sat Apr 18, 2015 1:56 am
by idle
wilbert wrote: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.
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.
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.
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
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))
Re: A small procedure asm
Posted: Sat Apr 18, 2015 5:07 am
by wilbert
idle 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
It doesn't work as it should
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))
Should present 2 in both cases but the second one presents 5.
Re: A small procedure asm
Posted: Sat Apr 18, 2015 5:24 am
by idle
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
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))