[9front] [PATCH] branchless assembly abs() and labs() for amd64

[9front] [PATCH] branchless assembly abs() and labs() for amd64

[Kemal]

hello,

i remembered a method to do branchless abs.
can i send it as a patch?

regards.

diff -r d9e940a768d1 sys/src/libc/amd64/abs.s
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/sys/src/libc/amd64/abs.s Fri Dec 25 15:54:42 2020 +0300
@@ -0,0 +1,16 @@
+/*
+this method of abs works this way:
+first it gets the sign bit and extends it with cdq
+sign bit is the most significant bit of an integer showing it's sign
+lets say we have a decimal number -127. according to two's
complement, this is "10000001" in binary. the sign bit here is the
first "1" cdq gets the ax's
+sign bit and extends it like "11111111" then puts it to dx. now we are going to
+do a little math trick here. if we xor dx and ax we will have
"01111110" which is 126. according to two's complement, anything goes
like "11...11" is -1, so to recover the missing 1 we can substract dx
from ax which will
+result in ax-(-1) which would be ax+1. we have 127, the abs value.
+i don't remember the source where i got this method from so i can't
cite them :-(
+*/
+TEXT abs(SB),$0
+ MOVL RARG, AX
+ CDQ
+ XORL DX, AX
+ SUBL DX, AX
+ RET
diff -r d9e940a768d1 sys/src/libc/amd64/labs.s
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/sys/src/libc/amd64/labs.s Fri Dec 25 15:54:42 2020 +0300
@@ -0,0 +1,7 @@
+/* check abs.s for explanation */
+TEXT labs(SB),$0
+ MOVL RARG, AX
+ CDQ
+ XORL DX, AX
+ SUBL DX, AX
+ RET
diff -r d9e940a768d1 sys/src/libc/amd64/mkfile
--- a/sys/src/libc/amd64/mkfile Mon Oct 19 01:20:29 2020 +0200
+++ b/sys/src/libc/amd64/mkfile Fri Dec 25 15:54:42 2020 +0300
@@ -3,10 +3,12 @@

 LIB=/$objtype/lib/libc.a
 SFILES=\
+ abs.s\
  argv0.s\
  atom.s\
  cycles.s\
  getfcr.s\
+ labs.s\
  main9.s\
  main9p.s\
  memccpy.s\

Re: [9front] [PATCH] branchless assembly abs() and labs() for amd64

[ori]

Quoth Kemal <kemalinanc8@gmail.com>:
> hello,
> 
> i remembered a method to do branchless abs.
> can i send it as a patch?

more code is more work, especially with platform
specific assembly. is there any real world program
where this matters a lot?

Re: [9front] [PATCH] branchless assembly abs() and labs() for amd64

[boehm.igor]

> Quoth Kemal <kemalinanc8@gmail.com>:
>> hello,
>> 
>> i remembered a method to do branchless abs.
>> can i send it as a patch?

Nice :-)

> more code is more work, especially with platform
> specific assembly. is there any real world program
> where this matters a lot?

On top of having quantitative data (i.e.  a microbenchmark as well as
something real like a benchmark suite) available that show the benefit,
it would also be interesting what the compiler generates for
abs()/labs() and juxtapose that to see how much savings in code size,
improvement in performance, etc. this can accomplish.

That way it is easier to make the trade-off between maintainability
burden vs. performance gain.

Re: [9front] [PATCH] branchless assembly abs() and labs() for amd64

[Kemal]

hello again,

on maintainability issue, we can do it on c with bit shifts like this:

#include <u.h>
#include <libc.h>

int
abs(int a)
{
 return (a ^ (a >> 8*sizeof(int)-1)) - (a >> 8*sizeof(int)-1));
}

so that we don't have to maintain more platform specific code.

on size, the assembly one seems to be the clear winner. the original
abs's object file (unlinked) is around 400~ bytes, assembly one is
120-140~, the branchless c one is 300~.

on performance, well i couldn't do much tests on this and i think my
test program doesn't compare these 3 implementations properly. i might
try performance benchmarks if i can setup a better suite.

on if abs is commonly used, well i couldn't find a program that uses
it heavily so having branchless abs is not important.

Re: [9front] [PATCH] branchless assembly abs() and labs() for amd64

[ori]

Quoth Kemal <kemalinanc8@gmail.com>:
> hello again,
> 
> on maintainability issue, we can do it on c with bit shifts like this:

Simplicity and clarity should win unless the
added complexity buys us something. To me, the
bit twiddling operation seems less obviously
correct than the current:

		if(a < 0)
			return -a;
		return a;

I appreciate the effort, but I'd prefer that we
leave this patch be unless it's solving a problem
Optimization should ideally start with measuring
a real program.

> on size, the assembly one seems to be the clear winner. the original
> abs's object file (unlinked) is around 400~ bytes, assembly one is
> 120-140~, the branchless c one is 300~.

Note that unlinked sizes don't matter much: our
object files do not contain encoded assembly, but
instead a simpler "bytecode" that the linker will
optimize lightly and then encode.

Re: [9front] [PATCH] branchless assembly abs() and labs() for amd64

[Kemal]

i agree that this optimization is useless when there is no program
using it heavily so unless we have one you can discard this patch.
> I appreciate the effort, but I'd prefer that we
> leave this patch be unless it's solving a problem
> Optimization should ideally start with measuring
> a real program.