RoundRobinRountingLogic: A slightly faster version?

[Guido Medina]

Hi,

I have my own version of a RoundRobinRouting logic which I believe it is faster and less CPU intensive due to no mod math operation, here is my version in Java 8, it has though one small error because NoRoutee instance if private and I don't know much Scala, so here it is a copy/proposal :

public class CircularRoutingLogic implements RoutingLogic {

  final AtomicInteger next = new AtomicInteger(-1);

  @Override
  public Routee select(Object message, IndexedSeq<Routee> routees) {
    final int size = routees.size();

    // null should be replaced by NoRoutee Akka/Scala instance.
    return size == 0 ? null : routees.apply(next.accumulateAndGet(1, (index, increment) -> ++index >= size ? 0 : index));
  }
}

[Guido Medina]

Also it is unlikely such thing will happen, my atomic integer will never overflow because it goes back to zero.

[Chris Baxter]

Have you profiled this to quantify the performance improvement, and if so, did you run it under high contention situations to be sure the locks on the atomic don't start to be an issue under high contention?

[Guido Medina]

There is one thing to clarify and two differences:

• There are no locks in atomic operations, remember atomic operations are based on CAS.
• Incrementing an AtomicInteger will definitely be cheaper than incrementing an AtomicLong.
• Comparing the value and returning is definitely cheaper than division/mod operation which is CPU intensive.
• And last but least important and highly unlikely: No risk of overflowing the counter because the value is always reset to zero.

Though you are right, I should JMH it, let me do that tonight:

Here is what the side-effect function looks like in Java 8:

/**
 * Atomically updates the current value with the results of
 * applying the given function to the current and given values,
 * returning the updated value. The function should be
 * side-effect-free, since it may be re-applied when attempted
 * updates fail due to contention among threads.  The function
 * is applied with the current value as its first argument,
 * and the given update as the second argument.
 *
 * @param x the update value
 * @param accumulatorFunction a side-effect-free function of two arguments
 * @return the updated value
 * @since 1.8
 */
public final int accumulateAndGet(int x,
                                  IntBinaryOperator accumulatorFunction) {
    int prev, next;
    do {
        prev = get();
        next = accumulatorFunction.applyAsInt(prev, x);
    } while (!compareAndSet(prev, next));
    return next;
}

[Guido Medina]

In fact, I think my implementation should not only be faster but it is also safer due to the -unlikely event?- of reaching Long.MAX_VALUE, a side by side comparison:

• Both implementations "compare and set" the value atomically, but mine does it for an AtomicInteger vs AtomicLong which is cheaper.
• My implementation does one increment of an integer and compare it against the size and return either the new value if less or  equal than size or zero, the original implementation always MOD a long value which according to my research -not a very extensive one- moding cost > dividing cost > multiplying cost > incrementing cost

The other issue not strictly related with my implementation is that the static and singleton NoRoutee instance is a private member of Router.scala making it unusable for RoutingLogic extenders, and Akka does use equality -if routee == NoRoutee then deadletters ! tell...- which makes anyone's custom RoutingLogic implementation not able to behave like any other Akka provided RoutingLogic so I think it needs to be made public and mentioned in the documentation clarifying that returning it from a RoutingLogic will drop the message into the dead letters.

Best regards,

Guido.

[Konrad Malawski]

Hi Guido,

we're happy to take performance improvement contributions however they should be backed with some JMH benchmark to prove the claimed perf benefits :-)

You can easily run benchmarks by just adding one to our akka-bench-jmh subproject.

Looking forward to the PR, then we can discuss changes in detail!

--
>>>>>>>>>> Read the docs: http://akka.io/docs/
>>>>>>>>>> Check the FAQ: http://doc.akka.io/docs/akka/current/additional/faq.html
>>>>>>>>>> Search the archives: https://groups.google.com/group/akka-user
---
You received this message because you are subscribed to the Google Groups "Akka User List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to akka-user+...@googlegroups.com.
To post to this group, send email to akka...@googlegroups.com.
Visit this group at http://groups.google.com/group/akka-user.
For more options, visit https://groups.google.com/d/optout.

--

Cheers,

Konrad 'ktoso' Malawski

Akka @ Typesafe

[Patrik Nordwall]

Sounds like a great contribution!

/Patrik

[Guido Medina]

Will do that ;-)

[Guido Medina]

I modified the original to be correct, theoretically when your AtomicLong reaches the Long.MAX_VALUE + 1 it will shift to Long.MIN_VALUE making the mod (%) function return negative which will make the application fail due to invalid list index -list.get(neg_index)-

In practice that is unlikely to happen but there might be some crazy lab running DNA sequencing so in practice infinite is now reachable, could take hours, days or weeks, but once it happen, original RoundRobinRountingLogic will fail, perf tests concluded that at least in Java 8 atomic adder + mod is faster than CAS, but the class needs to be modified from this:

final class RoundRobinRoutingLogic extends RoutingLogic {
  val next = new AtomicLong(0)


  override def select(message: Any, routees: immutable.IndexedSeq[Routee]): Routee =
    if (routees.isEmpty) NoRoutee
    else routees((next.getAndIncrement % routees.size).asInstanceOf[Int])

}

To this, not sure if it is going to compile, I'm not a Scala programmer, not sure if the "asInstanceOf" is needed anymore, Integer or Long they will eventually overflow and go to their MIN_VALUE so why bother with a Long?

It looks to me Long was put there with fear of reaching MAX_VALUE causing a failure, well, it won't fail because overflows will just shift a bit, but it will fail because mod(%) will return negative -list.get(neg_index)-, so here is the original with Math.abs and AtomicInteger instead:

final class RoundRobinRoutingLogic extends RoutingLogic {
  val next = new AtomicInteger(0)


  override def select(message: Any, routees: immutable.IndexedSeq[Routee]): Routee =
    if (routees.isEmpty) NoRoutee
    else routees(Math.abs(next.getAndIncrement % routees.size).asInstanceOf[Int])

}

JMH perf tested results:

Benchmark            Mode  Cnt          Score          Error  Units

CASvsMOD.intCAS_1   thrpt    5   76444721.566 ±   813686.931  ops/s

CASvsMOD.intCAS_4   thrpt    5   73853879.600 ±   689854.722  ops/s

CASvsMOD.intCAS_8   thrpt    5   76352315.163 ±  2300065.091  ops/s

CASvsMOD.intMOD_1   thrpt    5  131541916.778 ±  3400828.887  ops/s

CASvsMOD.intMOD_4   thrpt    5   96787272.406 ±  1540417.674  ops/s

CASvsMOD.intMOD_8   thrpt    5   96954428.161 ±  1007965.370  ops/s

CASvsMOD.longMOD_1  thrpt    5  129730846.046 ± 23522696.956  ops/s

CASvsMOD.longMOD_4  thrpt    5   96930440.731 ±  1549403.070  ops/s

CASvsMOD.longMOD_8  thrpt    5   96882920.242 ±  1342011.843  ops/s

JMH perf source code:

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;


import java.io.IOException;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;


@State(Scope.Benchmark)
public class CASvsMOD {


  private final AtomicInteger nextInt = new AtomicInteger();
  private final AtomicLong nextLong = new AtomicLong();


  private int nextInt(int routees) {
    return nextInt.accumulateAndGet(1, (index, increment) -> ++index < routees ? index : 0);
  }


  @Benchmark
  public void intCAS_1() {
    nextInt(1);
  }


  @Benchmark
  public void intCAS_4() {
    nextInt(4);
  }


  @Benchmark
  public void intCAS_8() {
    nextInt(8);
  }


  private int nextIntWithMod(int routees) {
    return Math.abs(nextInt.incrementAndGet() % routees);
  }


  @Benchmark
  public void intMOD_1() {
    nextIntWithMod(1);
  }


  @Benchmark
  public void intMOD_4() {
    nextIntWithMod(4);
  }


  @Benchmark
  public void intMOD_8() {
    nextIntWithMod(8);
  }


  private long nextLong(int routees) {
    return Math.abs(nextLong.incrementAndGet() % routees);
  }


  @Benchmark
  public void longMOD_1() {
    nextLong(1);
  }


  @Benchmark
  public void longMOD_4() {
    nextLong(4);
  }


  @Benchmark
  public void longMOD_8() {
    nextLong(8);
  }


  public static void main(String[] args) throws RunnerException, IOException {
    final Options opt = new OptionsBuilder().
      include(CASvsMOD.class.getSimpleName()).
      warmupIterations(5).
      measurementIterations(5).
      forks(1).
      build();
    new Runner(opt).run();
  }
}

Why am I proposing code here?, well, I tried to import and compile Akka on IntelliJ -I have latest IntelliJ with Scala plugin-, but I gave up because several issues I didn't have the time nor patience to resolve like SBT, so this is the best I can do.

[Akka Team]

Hi Guido,

You cannot import the release-2.3-dev in newest IntelliJ, I filed them a bug last week. Can you still make this a proper PR? You can build Akka using sbt only, or you can still use the old sbt-idea plugin to make a project that IDEA can read (that is what I use now until they fix the import).

-Endre

--
>>>>>>>>>> Read the docs: http://akka.io/docs/
>>>>>>>>>> Check the FAQ: http://doc.akka.io/docs/akka/current/additional/faq.html
>>>>>>>>>> Search the archives: https://groups.google.com/group/akka-user
---
You received this message because you are subscribed to the Google Groups "Akka User List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to akka-user+...@googlegroups.com.
To post to this group, send email to akka...@googlegroups.com.
Visit this group at http://groups.google.com/group/akka-user.
For more options, visit https://groups.google.com/d/optout.

--

Akka Team

Typesafe - Reactive apps on the JVM

Blog: letitcrash.com
Twitter: @akkateam

[Patrik Nordwall]

I have created an issue so that someone (great community contribution) can pick it up: https://github.com/akka/akka/issues/17738

Patrik Nordwall

Typesafe -  Reactive apps on the JVM

Twitter: @patriknw

[Guido Medina]

I'll send you the pull request in several minutes, also the signing for contribution.

[Patrik Nordwall]

Awesome, thanks for making Akka better!

/Patrik

[Konrad Malawski]

Awesome, thanks a lot Guido!

-- 

Cheers,

Konrad 'ktoso’ Malawski
Akka @ Typesafe