Refactor condition based on options

Question
1

I battled with this conditional for a while before realizing I had mistyped some of my x1, x2, x3 variables in the maximization formula. Can someone suggest how I could have written this conditional readable, fast (as it is in a critical location in an intensive computation), and concise?

      val xy1 = em.locationToXy(loc1)
      val xy2 = em.locationToXy(loc2)
      val xy3 = em.locationToXy(loc3)
     if (xy1.nonEmpty && xy2.nonEmpty && xy3.nonEmpty && locally {
        import math.abs
        val Some((x1, y1)) = xy1
        val Some((x2, y2)) = xy2
        val Some((x3, y3)) = xy3
        (abs(x1 - x2) max abs(x1 - x3) max abs(x2 - x3)) <= 1 &&
          (abs(y1 - y2) max abs(y1 - y3) max abs(y2 - y3)) <= 1
      })
        () // already colorized
     else if {...}
     else {...}

I didn’t test it, but I was supposing that binding and pattern matching Some((x1,y1)) etc was better to avoid when possible; thus I bind them inside the locally{...} as shown above.

Also I’m supposing that if variables are declared and object created inside a local scope locally{...} then after the dynamic extent completes, the GC is free to reclaim that memory.

I’m also supposing that import ... has no runtime overhead.

2

AFAIK, complex assignments like


val Some((x1, y1)) = xy1

are pattern matching under the hood. If you want to avoid pattern matching, you might want to write it with simple assignments such as:


val x1 = xy1.get._1

val y1 = xy1.get._2

Garbage collection only applies to objects on the heap, and I suspect (based on you using math.abs) that your variables are unboxed primitives, which live on the stack and are released when the method returns.

3

No such thing as a free lunch I’m afraid.

What you would want to write is

for {
  (x1, y1) <- xy1
  (x2, y2) <- xy2
  (x3, y3) <- xy3 if List(x1, x2, x3).combinations(2).forall { case (xi, xj) => abs(xi - xj) <= 1 } &&
                     List(y1, y2, y3).combinations(2).forall { case (yi, yj) => abs(yi - yj) <= 1 }
} () //already colorized, either yield true and getOrElse false, or, depending on the rest of your branches, integrate them

or really ((x1, y1), (x2, y2), (x3, y3)).transpose.forall(triple => triple.combinations(2).forall{ case (a, b) => abs(a - b) <= 1} if that were possible, but there are many performance pitfalls there.

What you did is the seemingly right alternative optimized for performance. I don’t expect locally{} to do anything though – it just introduces a scope for naming I think. It doesn’t look like you’re actually allocating anything within the locally block, so there is nothing to collect there I think. If you did, it already is eligible for collection (though I’m not sure any collectors will actually collect there), but that’s probably the last place I would look for performance gains.

From what I understand, the rub is that you fat-fingered the manual unrolling of List(x1, x2, x3).combinations(2).forall { case (xi, xj) => abs(xi - xj) <= 1 }

That sounds exactly like something I would fat finger too. As it happens, that’s also exactly the slow part.

The alternatives, I think, are either to

  • live with the performance drop the abstraction gives you
  • live with the risk of fat fingering it and staring at your monitor until you spot the bug (unused warnings could be helpful in these kinds of things, but probably wouldn’t have saved you here either)
  • use a metaprogramming technique (code generation or macros)

At the moment, I would recommend against the third option: the snippet really is too small for code generation to be reasonable, scala 2 macros aren’t portable to scala 3 which is on the close horizon, and scala 3 metaprogramming requires scala 3 which doesn’t have a stable release yet.

With 1 being excluded, I’m afraid staring at the monitor until you catch the bug is the only option right now.

When Scala 3 arrives, metaprogramming and inline functions, possibly combined with code generation could offer some neat allocation free transposition options on tuples. You have some statically, compile time known sequence of pairs of indices, forall (ij1, ij2) somepredicate (matrix(ij1), matrix(ij2)) and generating a sequence of && somepredicate(matrix._i1._j1, matrix._i2._j2) at compile time should be possible.

4

That’s true, but it’s helpful for future-proofing. IIRC, there’s a Dotty proposal to eliminate “naked blocks”, in favor of using locally like this to establish a scope.

5

Am I correct in my understanding that the JVM does not gc objects until they go out of scope? I.e., even if a value will not be used again, the GC does not collect it until its references have been eliminated? for example in the following code, the List(1,2,3) could be safely GCed after map returns, and before g is called.

def foo () = {
  val o1 = List(1, 2, 3)
  g(o1.map(f)) //
}

My idea is to use local scopes to aid here. I admit this makes the code uglier. It is work the compiler could do but as I understand it is a capability that neither the scala compiler nor the JVM implement.

def foo () = {
  g(locally{ 
     val o1 = List(1, 2, 3)
     o1.map(f)
  }) // now List(1,2,3) has no more references at the time g is called
}
6

The Java language specification makes an object eligible for garbage collection as soon as it’s no longer reachable. That may be in the middle of a block.

But whether any specific garbage collector actually does collect some specific reference that’s eligible for collection is up to the collector.

Whether earlier collection will mean faster execution of the algorithm or lower latency is anyone’s guess, but I wouldn’t expect so. A GC run to clean 3 or 6 short lived objects is probably suboptimal.

If the locally block is inlined either by the comliler or the JIT, then from a runtime perspective its indistinguisable from the version without. If it’s not inlined, then you carry the method call cost for possibly earlier collection, which may well be more expensive than any gains you got from earlier collection (if, again, there were any to begin with).

Something like a method call GC.free for when you really do know better than the runtime when to collect what is AFAIK impossible on the platform.

On a somewhat related note, in the past I’ve thought about how it would be a neat trick if it were possible to interact directly with the runtime , you could make a comparison operator that, when it would find two references represnt the same immutable data, could replace the reference of whichever one was newer with the older one but it didn’t get past daydreaming, and I don’t think it’s possible.

7

JVM optionally does String deduplication (during GCs IIRC). Given that in Project Valhalla inline classes are immutable and their unboxed representations have no identity by design, JVM (in theory) should be able to deduplicate boxed instances (by making all of them except one to point to that one instead of copying its contents) in a similar way.

1 Like