Allocation free Match

Question
1 
class Nat(val x: Int) extends AnyVal:
  def get: Int = x
  def isEmpty: Boolean = x < 0

object Nat:
  inline def unapply(x: Int): Nat = new Nat(x)

object Main :
  def test(n: Int): String =
    n match
      case Nat(m) => s"$m is a natural number"
      case _ => s"$n is not a natural number"

  def main(args: Array[String]): Unit =
   println(test(5))   // Output: 5 is a natural number
2 Likes
2

Yes, that is allocation free.

Given

final class Nat(val value: Int) extends AnyVal:
  def get: Int = value
  def isEmpty: Boolean = value < 0
object Nat:
  inline def unapply(x: Int): Nat = Nat(x)

  def testnat(i: Int, j: Int): Int =
    i match
      case Nat(n) => n + j
      case _ => j

the bytecode is

  public int testnat(int, int);
    Code:
       0: iload_1
       1: istore_3
       2: iload_3
       3: istore        4
       5: getstatic     #60                 // Field Nat$.MODULE$:LNat$;
       8: iload         4
      10: invokevirtual #64                 // Method Nat$.isEmpty$extension:(I)Z
      13: ifne          35
      16: getstatic     #60                 // Field Nat$.MODULE$:LNat$;
      19: iload         4
      21: invokevirtual #68                 // Method Nat$.get$extension:(I)I
      24: istore        5
      26: iload         5
      28: istore        6
      30: iload         6
      32: iload_2
      33: iadd
      34: ireturn
      35: iload_2
      36: ireturn

and the methods called are

  public final int get$extension(int);
    Code:
       0: iload_1
       1: ireturn

  public final boolean isEmpty$extension(int);
    Code:
       0: iload_1
       1: iconst_0
       2: if_icmpge     9
       5: iconst_1
       6: goto          10
       9: iconst_0
      10: ireturn

So there are no allocations. The JIT compiler will very likely take care of this.

But if you write

object Gnat:
  inline def apply(x: Int) = x >= 0

def testgnat(i: Int, j: Int): Int =
  i match
    case n if Gnat(n) => n + j
    case _ => j

then the bytecode is cleaner, if not necessarily faster:

 public int testgnat(int, int);
    Code:
       0: iload_1
       1: istore_3
       2: iload_3
       3: istore        4
       5: iload         4
       7: iconst_0
       8: if_icmplt     15
      11: iconst_1
      12: goto          16
      15: iconst_0
      16: ifeq          24
      19: iload         4
      21: iload_2
      22: iadd
      23: ireturn
      24: iload_2
      25: ireturn

and as is usual with inline methods, they leave some clutter in the bytecode so if you write a straight match it’s just

    Code:
       0: iload_1
       1: istore_3
       2: iload_3
       3: istore        4
       5: iload         4
       7: iconst_0
       8: if_icmplt     16
      11: iload         4
      13: iconst_1
      14: iadd
      15: ireturn
      16: iload_2
      17: ireturn

which is in turn more cluttered than the if/else

  public int testifelse(int, int);
    Code:
       0: iload_1
       1: iconst_0
       2: if_icmplt     9
       5: iload_1
       6: iload_2
       7: iadd
       8: ireturn
       9: iload_2
      10: ireturn

However, the JIT compiler is pretty good at working out that all of these are really doing the same thing.

1 Like
3

Thanks, but the problem of the current allocation free and Option less extractor is : if both isEmpty and get need to access the elements of the value, then it will be called twice, eg read from AtomicBoolean

4

For AtomicBoolean you should probably be calling .get() or whatever directly and intentionally to make sure you have the consistent view you think you do, but anyway, you can use the same pattern with inline def unapply(ai: AtomicInteger): Nat = new Nat(ai.get()). The extends AnyVal pattern just lets you apply extra checks on top of whatever you already got.