Page 4 of 5
Re: Absolute Val for Integers?
Posted: Fri Jan 25, 2019 1:14 am
by Olliv
If I disturb nobody, I take the Josh's benchmark, I adjust his benchmark, I take the slowest algo and I add my thing about exception...
Magic wand... The slowest seems to become the quickest.
Code: Select all
Procedure AbsI(value.i)
! mov rax, [p.v_value]
! bt rax, 63
! jnb __absi_no
! not rax
! add rax, 1
! __absi_no:
ProcedureReturn
EndProcedure
Procedure AbsI_2(value.I)
! mov rax, [p.v_value]
! cqo
! add rax, rdx
! xor rax, rdx
ProcedureReturn
EndProcedure
Procedure AbsI_3(value.I)
! mov rax, [p.v_value]
! neg rax
! cmovs rax, [p.v_value]
ProcedureReturn
EndProcedure
Procedure Except()
MessageRequester("Error", "exception overflow")
End
EndProcedure
Procedure AbsI_4(value.I, *pointor)
! mov rdx, 0x8000000000000000
! mov rax, [p.v_value]
! mov rbx, rax
! cmp rbx, rdx
! je exception
! neg rax
! cmovs rax, rbx
ProcedureReturn
! exception:
! call qword [p.p_pointor]
EndProcedure
Procedure void(value.I)
! mov rax, [p.v_value]
ProcedureReturn
EndProcedure
#max = 1 << 26 - 1
Dim m1(#max)
Dim m2(#max)
Dim m3(#max)
Dim m4(#max)
Dim m5(#max)
Dim n(#max)
For i = 0 To #max
n(i) = Random($7FFFFFFFFFFFFFFF)
If Random(1)
n(i) | $8000000000000000
EndIf
Next
t1 = ElapsedMilliseconds()
For i = 0 To #max
m3(i) = AbsI_3(n(i) )
Next
t2 = ElapsedMilliseconds()
For i = 0 To #max
m2(i) = AbsI_2(n(i) )
Next
t3 = ElapsedMilliseconds()
For i = 0 To #max
m1(i) = AbsI(n(i) )
Next
t4 = ElapsedMilliseconds()
For i = 0 To #max
m4(i) = AbsI_4(n(i), @Except() )
Next
t5 = ElapsedMilliseconds()
For i = 0 To #max
m5(i) = void(n(i) )
Next
t6 = ElapsedMilliseconds()
t0 = t6 - t5
For i = 0 To #max
If m1(i) <> m4(i)
MessageRequester("", "problem")
End
EndIf
Next
MessageRequester("", Str(t2 - t1 - t0) + Chr(9) + Str(t3 - t2 - t0) + Chr(9) + Str(t4 - t3 - t0) + Chr(9) + Str(t5 - t4 - t0) )
Re: Absolute Val for Integers?
Posted: Fri Jan 25, 2019 8:25 am
by wilbert
Olliv wrote:I take the slowest algo and I add my thing about exception...
It's also possible to use the overflow flag. It makes the code a bit shorter.
Code: Select all
Procedure Except()
MessageRequester("Error", "exception overflow")
End
EndProcedure
Procedure AbsI_4(value, *overflow_handler)
!mov rax, [p.v_value]
!neg rax
!jo .overflow
!cmovs rax, [p.v_value]
ProcedureReturn
!.overflow:
!call qword [p.p_overflow_handler]
EndProcedure
Debug AbsI_4($8000000000000000, @Except())
Or for both x86 and x64
Code: Select all
Procedure.q AbsQ(value.q, *overflow_handler)
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
!mov rax, [p.v_value]
!neg rax
!jo .overflow
!cmovs rax, [p.v_value]
ProcedureReturn
!.overflow:
!call qword [p.p_overflow_handler]
CompilerElse
!mov edx, [p.v_value + 4]
!mov eax, [p.v_value]
!test edx, 0x80000000
!jz .absq_no
!not edx
!neg eax
!sbb edx, -1
!jo .overflow
!.absq_no:
ProcedureReturn
!.overflow:
!call dword [p.p_overflow_handler]
CompilerEndIf
EndProcedure
Re: Absolute Val for Integers?
Posted: Fri Jan 25, 2019 9:11 am
by Michael Vogel
This thread is very interesting because sometimes quick integer handling is really a must.
Anyhow it seems that macros will be much faster than the trickiest assembler procedures (see below)...
...so could it be possible to extend Purebasic somewhen allowing to create special macros using assembler code?
Code: Select all
Macro _Abs(n)
((n)*(Bool((n)>0)*2-1))
EndMacro
CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
Procedure AbsI(value.i)
!mov rax, [p.v_value]
!neg rax
!cmovs rax, [p.v_value]
ProcedureReturn
EndProcedure
CompilerElse
Procedure AbsI(value.i)
!mov eax, [p.v_value]
!neg eax
!cmovs eax, [p.v_value]
ProcedureReturn
EndProcedure
CompilerEndIf
Define iVal.i = $80000006
#n=100000
t1-ElapsedMilliseconds()
For i=1 To #n
a1=AbsI(ival)
b1=AbsI(9999)
c1=AbsI(-9999)
Next i
t1+ElapsedMilliseconds()
t2-ElapsedMilliseconds()
For i=1 To #n
a2=_Abs(ival)
b2=_Abs(9999)
c2=_Abs(-9999)
Next i
t2+ElapsedMilliseconds()
MessageRequester("",Str(t1)+": "+Str(b1-c1)+", "+Str(a1)+#CRLF$+Str(t2)+": "+Str(b2-c2)+", "+Str(a2))
Re: Absolute Val for Integers?
Posted: Fri Jan 25, 2019 9:13 am
by Olliv
@Wilbert
If it is quicker or near equal, yes : you just use only one register too. I cannot edit a benchmark. What does it give ?
@Michael Vogel
Yes, but the complete function should be included. Just comparing two ways, or comparing forgetting measuring parameters, drive to bad surprising things.
Even if exception overflow seems to be the 0.0000000000000000001% of the domain, it is the same ratio for a carry ! Exception can be treated by a macro but to branch it from a math macro, I do not know if MacroExpandedCount could be concatenated in an assembly label. If yes, macro will be better.
Re: Absolute Val for Integers?
Posted: Fri Jan 25, 2019 9:16 am
by wilbert
mk-soft wrote:I added AbsQ(Value)
I experimented a bit with the x86 code.
On my computer,
test seems to be faster as
bt .
It also looks like you can do the inversion with three instructions instead of four.
Code: Select all
Procedure.q AbsQ(value.q)
!mov edx, [p.v_value + 4]
!mov eax, [p.v_value]
!test edx, 0x80000000
!jz .absq_no
!not edx
!neg eax
!sbb edx, -1
!.absq_no:
ProcedureReturn
EndProcedure
Michael Vogel wrote:Anyhow it seems that macros will be much faster than the trickiest assembler procedures (see below)...
Calling a procedure causes quite a bit of overhead.
That's why a more complicated macro can still be faster compared to calling a procedure.
Re: Absolute Val for Integers?
Posted: Fri Jan 25, 2019 10:27 am
by Olliv
Wilbert wrote:On my computer, test seems to be faster as bt .
BT instruction is a strange UFO. It is slow for this use (and I do not mention this, above), but I am sure it can gain time and register use in others ways...
Re: Absolute Val for Integers?
Posted: Sun Feb 03, 2019 7:20 pm
by Michael Vogel
As some of you found brilliant macros fot the abs function I have a new puzzle for you: calculate the minimum non zero value of two integers:
Here's a procedure doing so, but would there be a simple math expression to get the same results?
Code: Select all
Procedure Min(a,b)
If a And a<b
ProcedureReturn a
ElseIf b
ProcedureReturn b
ElseIf a
ProcedureReturn a
Else
ProcedureReturn b
EndIf
EndProcedure
s.s=""
Debug "m|0 1 2 3"
Debug "-+-------"
For a=0 To 3
s=""+a+"|"
For b=0 To 3
m=min(a,b)
s+m+" "
Next b
Debug s
Next a
Re: Absolute Val for Integers?
Posted: Sun Feb 03, 2019 8:43 pm
by wilbert
Michael Vogel wrote:As some of you found brilliant macros fot the abs function I have a new puzzle for you: calculate the minimum non zero value of two integers:
Here's a procedure doing so, but would there be a simple math expression to get the same results?
If you want a macro, this seems to do it but it's not a really simple expression
Code: Select all
Macro Min(a, b)
((b) + ((a)-(b)) & -Bool(((a)<(b) And (a)) Or (b)=0))
EndMacro
s.s=""
Debug "m|0 1 2 3"
Debug "-+-------"
For a=0 To 3
s=""+a+"|"
For b=0 To 3
m=min(a,b)
s+m+" "
Next b
Debug s
Next a
There might be an easier way.
If speed is your goal, an asm procedure might be faster.
It might have been better to open a new topic since this has little to do with absolute values 
Re: Absolute Val for Integers?
Posted: Sun Feb 03, 2019 9:28 pm
by idle
a branch less version of min max probably won't be faster but in some circumstances it could be
Code: Select all
Macro Min(a,b)
b + ((a - b) & ((a - b) >> (SizeOf(integer)<<3 -1)))
EndMacro
Macro Max(a,b)
a - ((a - b) & ((a - b) >> (SizeOf(integer)<<3 - 1)));
EndMacro
s.s=""
Debug "m|0 1 2 3"
Debug "-+-------"
For a=0 To 3
s=""+a+"|"
For b=0 To 3
m=min(a,b)
s+m+" "
Next b
Debug s
Next a
Re: Absolute Val for Integers?
Posted: Mon Feb 04, 2019 10:57 am
by NicTheQuick
Not very efficient if you feed something else than pure variables or constants to that macro, but it works. I just converted your If-Condition to one line.
Code: Select all
Macro Min(a, b)
((b) - Bool(((a) And (a) < (b)) Or (Not (b) And (a))) * ((b) - (a)))
EndMacro
s.s = ""
Debug " m | 0 1 2 3"
Debug "----+------------"
For a = 0 To 3
s = RSet(Str(a), 3) + " | "
For b = 0 To 3
m = Min(a, b)
s + RSet(Str(m), 2) + " "
Next
Debug s
Next
But in principle your If-condition is best practice because there will never be more evaluated than needed, provided that the most common case is the first one.
Re: Absolute Val for Integers?
Posted: Mon Feb 04, 2019 3:04 pm
by Michael Vogel
Thanks, would be fine to simplify the boolean expressions in general, but purebasic sees a recursion then...
Code: Select all
Macro Is(relation,result)
(Bool(relation)*(result))
EndMacro
Macro mMin(a,b)
(a)+(b) - (Bool(a*b) * (Bool((a)<(b))*(b) + Bool((b)<=(a))*(a))); works fine, but not very easy to read
;(a)+(b) - Is(a*b,Is(a<b,b) + Is(b<=a,a)); easier to undesrtand, but does't work
EndMacro
s.s=""
Debug "m|0 1 2 3" : Debug "-+-------"
For a=0 To 3
s=""+a+"|"
For b=0 To 3 : m=mMin(a,b) : s+m+" " : Next b
Debug s
Next a
Re: Absolute Val for Integers?
Posted: Mon Feb 04, 2019 3:32 pm
by NicTheQuick
It seems that you can not use a Macro X more than once inside of an other Macro Y. Looks like a bug to me.
Re: Absolute Val for Integers?
Posted: Mon Feb 04, 2019 4:29 pm
by Little John
NicTheQuick wrote:It seems that you can not use a Macro X more than once inside of an other Macro Y.
This general statement certainly is not true. Simple proof is, that e.g. the following code works fine.
Code: Select all
Macro Is (a)
Bool(a <> 0)
EndMacro
Macro Test (x, y)
Is(x) * Is(y)
EndMacro
Debug Test( 3, 5)
Debug Test(-3, 5)
Debug Test( 3, 0)
The problem in Michael Vogel's code is the
recursion:
Is(a*b,Is(a<b,b) + Is(b<=a,a))
And that Macro recursion is not supported by PB is old news.
Re: Absolute Val for Integers?
Posted: Mon Feb 04, 2019 5:43 pm
by #NULL
You can just duplicate the macro with a different name to avoid the recursion
Code: Select all
Macro Is(relation,result)
(Bool(relation)*(result))
EndMacro
Macro Is2(relation,result)
(Bool(relation)*(result))
EndMacro
Macro mMin(a,b)
;(a)+(b) - (Bool(a*b) * (Bool((a)<(b))*(b) + Bool((b)<=(a))*(a))); works fine, but not very easy to read
(a)+(b) - Is(a*b,Is2(a<b,b) + Is2(b<=a,a)); easier to undesrtand, but does't work
EndMacro
s.s=""
Debug "m|0 1 2 3" : Debug "-+-------"
For a=0 To 3
s=""+a+"|"
For b=0 To 3 : m=mMin(a,b) : s+m+" " : Next b
Debug s
Next a
Re: Absolute Val for Integers?
Posted: Mon Feb 04, 2019 5:57 pm
by NicTheQuick
I think the problem is that Macros have a higher precedence than anything else. So after replacing the outer "Is" the first time with the content of the Macro it sees that it has to replace Is again and shows the recursion error. If brackets would have a higher precedence it would first replace the two "Is" in the middle and after expanding it could then expand the outer one.