Mirror of forum.nim-lang.org

2557 :: Fast branchless sign() function

• Stefan_Salewski (orginal) [2016-09-30T10:43:46+02:00] view original

  http://stackoverflow.com/questions/14579920/fast-sign-of-integer-in-c

  I would like to have a sign function in std lib.

  I was really surprised that the brachless variant makes such a difference -- I had expected nearly no difference because result dominated by random() function, or due to identical assembler code of gcc 5.4.0.

  import random
  
  #proc sign(x: int): int =
  #  if (x > 0): return 1
  #  elif (x < 0): return -1
  #  else: return 0
  
  proc sign(x: int): int =
    (x > 0).int - (x < 0).int
  
  #proc sign(x: float): int =
  #  if (x > 0): return 1
  #  elif (x < 0): return -1
  #  else: return 0
  
  proc sign(x: float): int =
    (x > 0).int - (x < 0).int
  
  var j = 0
  for  i in 0 .. 1e7.int:
    j += sign(random(7).float - 3.0)
  echo j
  
  j = 0
  for  i in 0 .. 1e7.int:
    j += sign(random(7) - 3)
  echo j
  Run

  
  stefan@nuc ~/sign $ nim c -d:release s.nim
  stefan@nuc ~/sign $ time ./s
  -2839
  855
  
  real	0m0.314s
  user	0m0.312s
  sys	0m0.000s
  stefan@nuc ~/sign $ nim c -d:release s.nim
  stefan@nuc ~/sign $ time ./s
  -2839
  855
  
  real	0m0.188s
  user	0m0.188s
  sys	0m0.000s
  
  Run

---

• Krux02 (orginal) [2016-09-30T14:31:41+02:00] view original

  I agree, I want this sign exactly like this in the math module. It always lets be cringe when I see needless branching in code that might be called in tight inner loops.

---

• Stefan_Salewski (orginal) [2016-12-01T20:18:44+01:00] view original

  I just noticed from system module:

  proc cmp*[T](x, y: T): int {.procvar.} =
    if x == y: return 0
    if x < y: return -1
    return 1
  Run

  Looks very similar to sign() function above.

  So maybe we should write that

  (x > y).int - (x < y).int
  Run

  Well, mayby gcc > 5.4 will do that automatically. I have only version 5.4 currently.

  import random
  
  proc cmp*[T](x, y: T): int {.procvar.} =
    (x > y).int - (x < y).int
    #if x == y: return 0
    #if x < y: return -1
    #return 1
  
  proc test =
    var j = 0
    for  i in 0 .. 1e7.int:
      j += cmp(random(5).float, random(7).float)
    echo j
    
    j = 0
    for  i in 0 .. 1e7.int:
      j += cmp(random(5), random(7))
    echo j
  
  test()
  Run

  
  # current version:
  $ time ./t
  -2858343
  -2855075
  
  real	0m0.420s
  user	0m0.416s
  sys	0m0.000s
  
  # new one:
  $ time ./t
  -2858343
  -2855075
  
  real	0m0.344s
  user	0m0.344s
  sys	0m0.000s
  Run

  Well, not a big gain here, but of course random() eats most cpu cycles.

---