Is there or will there be a Scala collection extending Seq with faster iteration than Array?Iterating through a Collection, avoiding ConcurrentModificationException when removing objects in a loopIs the Scala 2.8 collections library a case of “the longest suicide note in history”?Seq for fast random access and fast growth in ScalaWhy are elementwise additions much faster in separate loops than in a combined loop?Difference between a Seq and a List in ScalaWhy is it faster to process a sorted array than an unsorted array?Is < faster than <=?Why is [] faster than list()?C++ code for testing the Collatz conjecture faster than hand-written assembly - why?Why is 2 * (i * i) faster than 2 * i * i in Java?
Network latencies between opposite ends of the Earth
tikz drawing rectangle discretized with triangle lattices and its centroids
How to redirect stdout to a file, and stdout+stderr to another one?
Do people who work at research institutes consider themselves "academics"?
Why are lawsuits between the President and Congress not automatically sent to the Supreme Court
Why when I add jam to my tea it stops producing thin "membrane" on top?
I recently started my machine learning PhD and I have absolutely no idea what I'm doing
Why doesn't Iron Man's action affect this person in Endgame?
My bread in my bread maker rises and then falls down just after cooking starts
Why did the metro bus stop at each railway crossing, despite no warning indicating a train was coming?
What do the "optional" resistor and capacitor do in this circuit?
Did any "washouts" of the Mercury program eventually become astronauts?
Should I communicate in my applications that I'm unemployed out of choice rather than because nobody will have me?
Does the wearer know what items are in which patch in the Robe of Useful items?
Is the seat-belt sign activation when a pilot goes to the lavatory standard procedure?
How does a permutation act on a string?
Is random forest for regression a 'true' regression?
Formal Definition of Dot Product
Cuban Primes
Why does SSL Labs now consider CBC suites weak?
Variance and covariance inequality
Given 0s on Assignments with suspected and dismissed cheating?
Why commonly or frequently used fonts sizes are even numbers like 10px, 12px, 16px, 24px, or 32px?
Will consteval functions allow template parameters dependent on function arguments?
Is there or will there be a Scala collection extending Seq with faster iteration than Array?
Iterating through a Collection, avoiding ConcurrentModificationException when removing objects in a loopIs the Scala 2.8 collections library a case of “the longest suicide note in history”?Seq for fast random access and fast growth in ScalaWhy are elementwise additions much faster in separate loops than in a combined loop?Difference between a Seq and a List in ScalaWhy is it faster to process a sorted array than an unsorted array?Is < faster than <=?Why is [] faster than list()?C++ code for testing the Collatz conjecture faster than hand-written assembly - why?Why is 2 * (i * i) faster than 2 * i * i in Java?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
From what I tested and read, Array is the fastest collection when it comes to do random access or iteration through foreach, while, and tailrec, but they are mutable, unlike Vector, which is unfortunately not as fast as Array.
I'm still stuck on Scala 2.11, but I recently discovered that changes have been made on Scala 2.13. Is there some hope that there exists or will exist an immutable collection that surpasses Array in term of random access?
Here is an exemple for euclidean distance on Array[Double], it works exactly the same on Seq descendants.
final def euclidean(v1: Array[Double], v2: Array[Double]): Double =
@annotation.tailrec
def go(d: Double, i: Int): Double =
if(i < v1.size)
val toPow2 = v1(i) - v2(i)
go(d + toPow2 * toPow2, i + 1)
else d
sqrt(go(0D, 0))
scala performance collections
asked Mar 23 at 15:13
KyBeKyBe
414723
|
show 2 more comments
From what I tested and read, Array is the fastest collection when it comes to do random access or iteration through foreach, while, and tailrec, but they are mutable, unlike Vector, which is unfortunately not as fast as Array.
I'm still stuck on Scala 2.11, but I recently discovered that changes have been made on Scala 2.13. Is there some hope that there exists or will exist an immutable collection that surpasses Array in term of random access?
Here is an exemple for euclidean distance on Array[Double], it works exactly the same on Seq descendants.
final def euclidean(v1: Array[Double], v2: Array[Double]): Double =
@annotation.tailrec
def go(d: Double, i: Int): Double =
if(i < v1.size)
val toPow2 = v1(i) - v2(i)
go(d + toPow2 * toPow2, i + 1)
else d
sqrt(go(0D, 0))
scala performance collections
asked Mar 23 at 15:13
KyBeKyBe
414723
2
2.13will have an immutable Array.
– Luis Miguel Mejía Suárez
Mar 23 at 15:27
I just tried comparing euclidean distance usingtailrecand ArraySeq are still ~10% slower for 1M runs.
– KyBe
Mar 23 at 15:42
What do you mean withtailrec? A tail-recursive algorithm that splits the collection usinghead&tail? If so, you probably better use a List instead of an Array. Everytailcall will copy the contents of the array to a new one. Arrays are good for iterative algorithms.
– Luis Miguel Mejía Suárez
Mar 23 at 16:25
I'm not using tail and head in this case, just replace the while loop by a tail recursive call to iterate overX <: SeqorArray.
– KyBe
Mar 23 at 16:28
Can you pleae share the code in the question. I am not an expert about collections, but if you look at the source, the immutable Array is just a wrapper over a normal (mutable) Array. So, they should behave very similar, or at least I believe so.
– Luis Miguel Mejía Suárez
Mar 23 at 16:34
|
show 2 more comments
From what I tested and read, Array is the fastest collection when it comes to do random access or iteration through foreach, while, and tailrec, but they are mutable, unlike Vector, which is unfortunately not as fast as Array.
I'm still stuck on Scala 2.11, but I recently discovered that changes have been made on Scala 2.13. Is there some hope that there exists or will exist an immutable collection that surpasses Array in term of random access?
Here is an exemple for euclidean distance on Array[Double], it works exactly the same on Seq descendants.
final def euclidean(v1: Array[Double], v2: Array[Double]): Double =
@annotation.tailrec
def go(d: Double, i: Int): Double =
if(i < v1.size)
val toPow2 = v1(i) - v2(i)
go(d + toPow2 * toPow2, i + 1)
else d
sqrt(go(0D, 0))
scala performance collections
asked Mar 23 at 15:13
KyBeKyBe
414723
From what I tested and read, Array is the fastest collection when it comes to do random access or iteration through foreach, while, and tailrec, but they are mutable, unlike Vector, which is unfortunately not as fast as Array.
I'm still stuck on Scala 2.11, but I recently discovered that changes have been made on Scala 2.13. Is there some hope that there exists or will exist an immutable collection that surpasses Array in term of random access?
Here is an exemple for euclidean distance on Array[Double], it works exactly the same on Seq descendants.
final def euclidean(v1: Array[Double], v2: Array[Double]): Double =
@annotation.tailrec
def go(d: Double, i: Int): Double =
if(i < v1.size)
val toPow2 = v1(i) - v2(i)
go(d + toPow2 * toPow2, i + 1)
else d
sqrt(go(0D, 0))
scala performance collections
scala performance collections
asked Mar 23 at 15:13
KyBeKyBe
414723
asked Mar 23 at 15:13
KyBeKyBe
414723
edited Mar 23 at 16:36
KyBe
asked Mar 23 at 15:13
KyBeKyBe
414723
asked Mar 23 at 15:13
KyBeKyBe
414723
asked Mar 23 at 15:13
KyBeKyBe
414723
414723
2
2.13will have an immutable Array.
– Luis Miguel Mejía Suárez
Mar 23 at 15:27
I just tried comparing euclidean distance usingtailrecand ArraySeq are still ~10% slower for 1M runs.
– KyBe
Mar 23 at 15:42
What do you mean withtailrec? A tail-recursive algorithm that splits the collection usinghead&tail? If so, you probably better use a List instead of an Array. Everytailcall will copy the contents of the array to a new one. Arrays are good for iterative algorithms.
– Luis Miguel Mejía Suárez
Mar 23 at 16:25
I'm not using tail and head in this case, just replace the while loop by a tail recursive call to iterate overX <: SeqorArray.
– KyBe
Mar 23 at 16:28
Can you pleae share the code in the question. I am not an expert about collections, but if you look at the source, the immutable Array is just a wrapper over a normal (mutable) Array. So, they should behave very similar, or at least I believe so.
– Luis Miguel Mejía Suárez
Mar 23 at 16:34
|
show 2 more comments
2
2.13will have an immutable Array.
– Luis Miguel Mejía Suárez
Mar 23 at 15:27
I just tried comparing euclidean distance usingtailrecand ArraySeq are still ~10% slower for 1M runs.
– KyBe
Mar 23 at 15:42
What do you mean withtailrec? A tail-recursive algorithm that splits the collection usinghead&tail? If so, you probably better use a List instead of an Array. Everytailcall will copy the contents of the array to a new one. Arrays are good for iterative algorithms.
– Luis Miguel Mejía Suárez
Mar 23 at 16:25
I'm not using tail and head in this case, just replace the while loop by a tail recursive call to iterate overX <: SeqorArray.
– KyBe
Mar 23 at 16:28
Can you pleae share the code in the question. I am not an expert about collections, but if you look at the source, the immutable Array is just a wrapper over a normal (mutable) Array. So, they should behave very similar, or at least I believe so.
– Luis Miguel Mejía Suárez
Mar 23 at 16:34
2
2
2.13 will have an immutable Array.– Luis Miguel Mejía Suárez
Mar 23 at 15:27
2.13 will have an immutable Array.– Luis Miguel Mejía Suárez
Mar 23 at 15:27
I just tried comparing euclidean distance using
tailrec and ArraySeq are still ~10% slower for 1M runs.– KyBe
Mar 23 at 15:42
I just tried comparing euclidean distance using
tailrec and ArraySeq are still ~10% slower for 1M runs.– KyBe
Mar 23 at 15:42
What do you mean with
tailrec? A tail-recursive algorithm that splits the collection using head & tail? If so, you probably better use a List instead of an Array. Every tail call will copy the contents of the array to a new one. Arrays are good for iterative algorithms.– Luis Miguel Mejía Suárez
Mar 23 at 16:25
What do you mean with
tailrec? A tail-recursive algorithm that splits the collection using head & tail? If so, you probably better use a List instead of an Array. Every tail call will copy the contents of the array to a new one. Arrays are good for iterative algorithms.– Luis Miguel Mejía Suárez
Mar 23 at 16:25
I'm not using tail and head in this case, just replace the while loop by a tail recursive call to iterate over
X <: Seq or Array.– KyBe
Mar 23 at 16:28
I'm not using tail and head in this case, just replace the while loop by a tail recursive call to iterate over
X <: Seq or Array.– KyBe
Mar 23 at 16:28
Can you pleae share the code in the question. I am not an expert about collections, but if you look at the source, the immutable Array is just a wrapper over a normal (mutable) Array. So, they should behave very similar, or at least I believe so.
– Luis Miguel Mejía Suárez
Mar 23 at 16:34
Can you pleae share the code in the question. I am not an expert about collections, but if you look at the source, the immutable Array is just a wrapper over a normal (mutable) Array. So, they should behave very similar, or at least I believe so.
– Luis Miguel Mejía Suárez
Mar 23 at 16:34
|
show 2 more comments
1 Answer
1
active
oldest
votes
In general, I don't think it is possible to surpass Array in terms of random access in JVM. As the array element are of equal size and they are located sequentially in memory, the position of an element can be quickly calculated in constant time using the given index. What is more, this leads to good cache locality.
In the best case the collection can have random access performance on par with arrays. Taking a look of scala 2.11 sources for the mentioned ArraySeq, it says:
This means that elements of
* primitive types are boxed.
https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/ArraySeq.scala#L19
This most likely explains the observed 10% drop in performance. Arrays have method toSeq which is implemented as a WrappedArray and there is specialized implementation for each primitive types which I believe is the most performant collection in scala 2.11 to wrap an array https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/WrappedArray.scala#L173 .
answered Mar 24 at 17:02
ollik1ollik1
1,58519
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55315177%2fis-there-or-will-there-be-a-scala-collection-extending-seq-with-faster-iteration%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
In general, I don't think it is possible to surpass Array in terms of random access in JVM. As the array element are of equal size and they are located sequentially in memory, the position of an element can be quickly calculated in constant time using the given index. What is more, this leads to good cache locality.
In the best case the collection can have random access performance on par with arrays. Taking a look of scala 2.11 sources for the mentioned ArraySeq, it says:
This means that elements of
* primitive types are boxed.
https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/ArraySeq.scala#L19
This most likely explains the observed 10% drop in performance. Arrays have method toSeq which is implemented as a WrappedArray and there is specialized implementation for each primitive types which I believe is the most performant collection in scala 2.11 to wrap an array https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/WrappedArray.scala#L173 .
answered Mar 24 at 17:02
ollik1ollik1
1,58519
add a comment |
In general, I don't think it is possible to surpass Array in terms of random access in JVM. As the array element are of equal size and they are located sequentially in memory, the position of an element can be quickly calculated in constant time using the given index. What is more, this leads to good cache locality.
In the best case the collection can have random access performance on par with arrays. Taking a look of scala 2.11 sources for the mentioned ArraySeq, it says:
This means that elements of
* primitive types are boxed.
https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/ArraySeq.scala#L19
This most likely explains the observed 10% drop in performance. Arrays have method toSeq which is implemented as a WrappedArray and there is specialized implementation for each primitive types which I believe is the most performant collection in scala 2.11 to wrap an array https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/WrappedArray.scala#L173 .
answered Mar 24 at 17:02
ollik1ollik1
1,58519
add a comment |
In general, I don't think it is possible to surpass Array in terms of random access in JVM. As the array element are of equal size and they are located sequentially in memory, the position of an element can be quickly calculated in constant time using the given index. What is more, this leads to good cache locality.
In the best case the collection can have random access performance on par with arrays. Taking a look of scala 2.11 sources for the mentioned ArraySeq, it says:
This means that elements of
* primitive types are boxed.
https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/ArraySeq.scala#L19
This most likely explains the observed 10% drop in performance. Arrays have method toSeq which is implemented as a WrappedArray and there is specialized implementation for each primitive types which I believe is the most performant collection in scala 2.11 to wrap an array https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/WrappedArray.scala#L173 .
answered Mar 24 at 17:02
ollik1ollik1
1,58519
In general, I don't think it is possible to surpass Array in terms of random access in JVM. As the array element are of equal size and they are located sequentially in memory, the position of an element can be quickly calculated in constant time using the given index. What is more, this leads to good cache locality.
In the best case the collection can have random access performance on par with arrays. Taking a look of scala 2.11 sources for the mentioned ArraySeq, it says:
This means that elements of
* primitive types are boxed.
https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/ArraySeq.scala#L19
This most likely explains the observed 10% drop in performance. Arrays have method toSeq which is implemented as a WrappedArray and there is specialized implementation for each primitive types which I believe is the most performant collection in scala 2.11 to wrap an array https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/WrappedArray.scala#L173 .
answered Mar 24 at 17:02
ollik1ollik1
1,58519
answered Mar 24 at 17:02
ollik1ollik1
1,58519
answered Mar 24 at 17:02
ollik1ollik1
1,58519
answered Mar 24 at 17:02
ollik1ollik1
1,58519
1,58519
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55315177%2fis-there-or-will-there-be-a-scala-collection-extending-seq-with-faster-iteration%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
2.13will have an immutable Array.– Luis Miguel Mejía Suárez
Mar 23 at 15:27
I just tried comparing euclidean distance using
tailrecand ArraySeq are still ~10% slower for 1M runs.– KyBe
Mar 23 at 15:42
What do you mean with
tailrec? A tail-recursive algorithm that splits the collection usinghead&tail? If so, you probably better use a List instead of an Array. Everytailcall will copy the contents of the array to a new one. Arrays are good for iterative algorithms.– Luis Miguel Mejía Suárez
Mar 23 at 16:25
I'm not using tail and head in this case, just replace the while loop by a tail recursive call to iterate over
X <: SeqorArray.– KyBe
Mar 23 at 16:28
Can you pleae share the code in the question. I am not an expert about collections, but if you look at the source, the immutable Array is just a wrapper over a normal (mutable) Array. So, they should behave very similar, or at least I believe so.
– Luis Miguel Mejía Suárez
Mar 23 at 16:34