If Scala Future is half-baked, it should be full-baked rather than dropped IMO. At least right now we can write fairly reasonable async code in plain Scala. This is table stakes, we shouldn’t need third party / external libraries for this.
8 Likes
I’d like to float a proposal — perhaps easy to dismiss — but potentially worth discussion.
Scala collections are optimized around a difficult multidimensional tradeoff: genericity, uniform APIs, abstraction quality, maintainability, and reasonable performance across many use cases.
What I’m wondering is whether there is room in the ecosystem for something at a very different point in that design space: a deliberately data-oriented, minimally abstract collection that explicitly commits to a flat, contiguous, unboxed memory layout — going all in on one axis (raw hardware efficiency) and accepting the significant constraints that follow.
Concretely, the idea would be a collection for which the compiler can guarantee:
-
A single contiguous allocation
-
No reference elements
-
No boxing
-
No structural indirection during traversal
The motivation: modern performance seems to be about memory layout - far more than algorithmic complexity. A flat, contiguous layout maximizes cache locality, enables hardware prefetching, and has potential opportunities for SIMD / loop fusion optimisations.
Such a collection would come with severe constraints?
-
Primitives (or future JVM value types) only
-
No references
-
Limited or no polymorphism
-
Possibly a different API shape to better support fusion and SIMD-friendly traversal
-
Potentially fixed-size, or size changes requiring explicit reallocation
This is not be general-purpose — deliberately so. It would target a narrow, performance-sensitive niche.
Array already provides contiguous storage for primitives. But it doesn’t make layout guarantees explicit at the abstraction level, nor does it explore what an intentionally data-oriented API might look like — particularly in a future™ if JVM value types (Project Valhalla) were to become available.
Summarised :
Is
Array(plus libraries) already the correct and sufficient answer for this niche?Or is there space for a consciously layout-committing, value-class-ready collection in Scala?
I’m genuinely unsure whether this is implementable or even desirable — but I am at least curious about the discussion if it provokes one!
3 Likes
You are looking for struct of arrays? this is a pretty hard problem with the primitive operations offered by the java platform - without waiting for Valhalla at least, every access would need some sort of decoder to read a value out (copy), theres no such thing as “reinterpret this slice of bytes as type X”
however yeah like you say if you only have primitive fields and you dont try to read out rows, but instead only act on columns then I think there is a space
1 Like
I think as you’ve described it, this has to wait for Project Valhalla to finally finish, in whatever form it manages to exist in. I think it is very likely that it will have to be fixed-size to work well, so basically arrays; even if it works, size-adjustment is probably mostly going to be full of performance gotchas, so one would probably want to do it intentionally for a high-performance-by-default API.
In the meantime, we could come up with a library that allows the kind of power and flexibility, without boxing, that one would like to have in an array library, and eventually extend it to an array-of-struct format where the structs were flat in memory; and it might at some point be worth adding inline tuples to the compiler, the idea being that they are never actually instantiated and can be decoupled in macro processing; this would make struct-of-arrays-accessed-like-array-of-structs a possibility.
I already have one possibility for bare-array processing in kse3, which works by making most operations inline so they can be unboxed. Thus, if you have
val xs = Array(1, 2, 3, 4, 5)
val ys = xs.drop(1).zipWithIndex.map{ case (x, i) => x / (i + 1.0) }
val zs = xs.selectOp(1 to End){ (x, i) => x / i.toDouble }
in the ys former case in Scala you duplicate the array, box everything and create an object and put that into another array, and then unbox and rebox and unbox again to put into the final array. In the latter case you act direct on the range of elements with no boxing, and just create a new primitive array directly.
Obviously I chose an example that is a bit extreme, but the point is that we can do the work to create high-efficiency high-level operations on arrays now, even if it doesn’t have as big a win for classes, and then if the JVM people ever get the low-level support there, we have a nice API to build from.
I write high-performance code all the time, and not having to manually write while loops and worry about corner cases all the time is really valuable. And with proper inlining, the overhead is usually either zero or quite small.
Note that the way I’ve done it is extensions on regular arrays. One could also make an opaque type around regular arrays, and then one wouldn’t have to re-invent method names (for instance, I can’t “map”, I have to “copyWith”) for the same/similar operations. For me, just-change-the-name was the easier path to what I needed. For the library, having a separate class or two might be worth the extra effort, especially if compiler people were willing to fix spots where there were performance implications due to cruft being left in the bytecode (which sometimes happens when things are inlined).
I think I am asking about an array of Structs, but clear note: suggesting to casually reproduce the decade or so of research in Valhalla, is obviously not a reasonable position :-).
So I agree, that my questions are probably only valid in a post valhalla world, and should perhaps be interpreted in the context of asking whether the existing collections are the optimal ones for it and / or how they might differ from the status quo?
@Ichoran answer below goes in this direction, and I think starts exploring the discussion I hoped to provoke…
So thank you both for the clarifications / answers.
On this note (however unrelated to SoA vs AoS), if the stdlib decides to provide an unboxed high performance data structure, I wonder if it would also be worth it to implement miniboxed tuples.
E.g.
opaque type TupleII = Long // Miniboxed (Int, Int)
extension (tup: TupleII) {
def _1: Int = ((tup >> 32) & 0xffff).toInt
def _2: Int = (tup & 0xffff).toInt
}
object TupleII {
def apply(x: Int, y: Int): TupleII = (x.toLong << 32) | y.toLong
def unapply(tup: TupleII): Some[(Int, Int)] = Some((tup._1, tup._2))
}
This seems like a simple problem for a library, but one can quickly get in the weeds regarding things like data alignment, autoderivation (maybe it should be possible to have an UnboxedTuple2[UnboxedTuple2[Byte, Byte], Int]) and the like.
So after a certain point, maybe it would make things easier if there was a common interface for all libraries.
Again, not sure if this would make sense in the stdlib (probably not), just some food for thought in case there’s interest in adding some high performance unboxed collections.
3 Likes
There are memory layouts, which are meant of this usecase as far as I understand.
Memory Layouts and Structured Access
1 Like
This is a bit of a tricky problem to have automatic support for - or at least any layout must be stored as a Java static final field to be optimised → so with the user manually declaring some “derived” instances of a shape perhaps this can work with automation.
Since we’re talking about allowing breaking API changes, I have a tentative wish for what I would like, but I appreciate that it comes with downsides that may make this unfeasible.
What:
Safe operations as the canonical default, explicit unsafety opt-in; inverting the current pattern of naming so option-returning methods are the canonical methods, and throwing methods get the explicit names; this should push early learners (and experienced practitioners) to use a safe-by-default coding style, eliminating common runtime errors.
How:
Currently, we have methods throughout Scala that return or throw; the prime example being head that return A or throw a runtime exception; we then have headOption to offer a safe alternative. In an ideal world, without the legacy of what we already have had for years and years, I would have preferred this to be inverted; head should return Option[A] and then we might have a unsafeHead: A - or even denying that existing in the first place, and forcing people to .getOrElse(throw new …)/ headOrThrow.
The collections API is probably the main place where I want this, but generically I would wish for this in places where logic errors result in thrown exceptions. That does not extend to stuff like e.g. I/O errors where the error isn’t inherently a logic-flaw (as such).
My own arguments against this:
- “ease-of-use-even-if-it-means-footguns” methods for early learners of a language may be desirable; even if it means sacrificing safety-first principles.
- We have a long history of Scala, and all example code would stop working with this backwards breaking change to what we could dub the original sin of these methods not being safe-by-default initially - we break “copy/pasting” of decade(s) of code.
- 100% adherence to never throwing becomes an exercise in reductio-ad-absurdum; math operators, overflows, division, etc probably shouldn’t be safe-by-default in the same manner
My own arguments for this:
- The migration could be automated via compiler (no need to get scalafix involved) - 3.x uses
.headcould be rewritten into.unsafeHeadin 3.y - Aligns the default API to encourage (what I believe to be) idiomatic modern Scala -where
Optionis already the expected tool for absent values - We move an issue to a compile time issue, and while a programmer can still cause a logic issue by using of
.getOrElse, I believe core point of Scala’s type system is that the compiler helps direct us via forcing us to perform exhaustivity checks - the fact thatOption[A]andAare different types. You literally cannot pass aOption[String]where aStringis expected without doing something explicit; this is categorically different from an exception that silently lurks. - This conforms to the principle of least surprises (runtime exceptions are always surprising)
- Unsafe throwing variants get an explicit ‘unsafe’ in their name, and scala doc saying why - softly directing towards a style of coding that is safe by default
A tentative step towards safety:
Nothing stops us adding headOrThrow style methods now as a stepping stone, which is something the unfrozen stdlib can actually deliver without (much?) controversy - a purely additive change. Arguably we could then deprecate head - but, again, maybe that is, for the reasons stated above, still too controversial.
On the whole:
I personally think the tradeoffs are worth it, but I understand that the drawbacks may be considerable and that the ship simply has sailed for legacy reasons. In a “redoing-the-api-from-scratch” world, that is, however, what I’d like, so I’m putting the suggestion here regardless.
3 Likes
Scala 2-specific inference problems with foreach[U]:
I prefer the formulation in Subtractable nightmare.
This is related to a question posted today about type inference; but maybe the question is more about how method signatures could be improved to cope with inference.
Maybe that falls under
We just released Steps 0.2.0 which has some improvements to the Result API, please try it out and github issues are open for feedback
We have a new blog post to announce the completion of porting the Scala 2 optimizer to Scala 3 (available in 3.8.3-RC3) - when activated it can help improve performance of programs using the new standard library: Porting the Scala 2 optimizer to Scala 3 | The Scala Programming Language
Thanks to Solal Pirelli for all the hard work!
7 Likes
Did someone already suggest strict versions of mapValues and filterKeys, as they are very common operations:
[warn] 58 | val sizeFrequencies = m.mapValues(_.size).mkString(", ")
[warn] | ^^^^^^^^^^^
[warn] |method mapValues in trait MapOps is deprecated since 2.13.0: Use .view.mapValues(f). A future version will include a strict version of this method (for now, .view.mapValues(f).toMap).
5 Likes
does the @inline works on Scala 3 too now?
1 Like
The post says:
You can override the heuristics with
@inlineand@noinlineannotations, but these should be a last-resort solution that you re-evaluate frequently as the compiler and the JVM improve.
That sounds like the same as Scala 2: the annotation is not needed and not recommended (for most use cases).
Another question is whether there is a reason to use @inline instead of inline. That is, when is optimizing a good idea if principled inlining is not?
2 Likes
Yes, because in projects like pekko / sjsonnet, then we have to split the code for scala 3 and scala 2 to leverage the inline optimizer.
1 Like
final case class Left[+A](value: A) extends Either[A, Nothing]
final case class Right[+B](value: B) extends Either[Nothing, B]
4 Likes
mapAccum is sorely missing from the stdlib – that and flatTraverse are the only two collection operators I use from cats frequently.
Note: this change can be made both without breaking binary compatibility and without special support from the compiler, by using targetName to assign the old binary name to headOrThrow: @targetName("head") def headOrThrow: A; def head: Option[A] - new head doesn’t need a targetName rename because the methods have distinct return types Object and Option.
This is long overdue and involves no risk of binary breakage.
5 Likes
Could we make Array.tabulate and related methods inlined? This would prevent the function objects allocation, similar to how it’s done in Kotlin
4 Likes
Let’s make List less central to the collections.
Saying what needs to be said, List is probably the worst data structure to ever use. On modern CPUs and the cache structure, constantly jumping around to different memory addresses is pretty much the worst thing you can do. The memory use is also pretty high, in respect to object headers, object pointers and object memory alignment. When project Valhalla lands, this performance discrepancy will become even worse compared to Vector, for example.
In my personal experience, List is the best choice only in highly branching recursive algorithms. Moreover, I used to use it for mutable fields, which resulted in many of my sequences to be unnaturally reversed (because only prepend is efficient, and not append), leading to bugs.
I am proposing:
- Change default implementation of
Seqto be something else. Or shorten the name ofIndexedSeqso people will use it more instead. - Shorten names for
VectorandArraySeqto something 3 or 4 letters. EspeciallyArraySeq, it is pain to read and type. Also, import it into predef by default. - Maybe add a version of
Listwhere append is efficient, and prepend is not.
What do you think?
1 Like