Copying of lists is surprisingly slow

[tomas kulich]

I made a simple benchmark that copies list/array of fixed size. For me, the results couldn't be more surprising (in what follows, higher is better, Dart VM is taken as unit. The results are quite stable when re-running the code multiple times):

Dart on VM: 1 

Dart2js on chromium: 3.7

Dart2js on node: 1.4

Vanilla js on chromium: 6

Vanilla js on node: 10

Java on JVM: 30

- why is Dart VM so slow, especially, why is Dart code so much faster when compiled to js?

and, btw

- why there is so big difference between chromium and node? They are both powered by V8, which means they should perform similarly?

 

I ran into this issue, when optimizing (quite slow) inserts to persistent map implemented in Dart; after some profiling, copying arrays seems to be the root-cause for its slowness.

Dart code:

main(){

  var stopwatch = new Stopwatch()..start();

  var list = new List.filled(16, 'hello world');

  for (num i=0;i<100000000;i++){

    var copy = new List.from(list, growable: false);

  }

  print(stopwatch.elapsed);

}

JS code:

var source=[];

for(var i=0;i<16;i++){

    source.push('hello world');

}

start = new Date();

for(var i=0;i<100000000;i++){

    copy=source.slice(0);

}   

end = new Date();

console.log((end-start)/1000.0);

Java code:

import java.util.Arrays;

public class Main {

  public static void main(String []args){

  String s = "hello world";

  int len = 16;

  String[] array = new String[len];

  Arrays.fill(array, s);

  long start = System.currentTimeMillis();

  for(int i=0; i<100000000; i++){

  String[] copy = new String[len];

  System.arraycopy(array, 0, copy, 0, len);

  }

  long stop = System.currentTimeMillis();

  System.out.println((stop-start)/1000.0);

  }

}

[Lasse R.H. Nielsen]

Interesting!

Could you try changing new List.from(list) to list.sublist(0) and
see if it makes a difference ?

Cheers
/L

> --
> For other discussions, see https://groups.google.com/a/dartlang.org/
>
> For HOWTO questions, visit http://stackoverflow.com/tags/dart
>
> To file a bug report or feature request, go to http://www.dartbug.com/new
>
> To unsubscribe from this group and stop receiving emails from it, send an
> email to misc+uns...@dartlang.org.



--
Lasse R.H. Nielsen - l...@google.com
'Faith without judgement merely degrades the spirit divine'
Google Denmark ApS - Frederiksborggade 20B, 1 sal - 1360 København K -
Denmark - CVR nr. 28 86 69 84

[tomas kulich]

wow, interesting idea! On the same scale as before:

dart VM (sublist): 4

dart2js on chromium (sublist) 3.4

dart2js on node (sublist) 6.7 (wtf moment)

Dňa pondelok, 18. augusta 2014 19:32:33 UTC+2 Lasse Reichstein Holst Nielsen napísal(-a):

[tomas kulich]

Btw, meanwhile I upgraded from dart v. 1.5.1 to 1.5.8, however, it does not seem to change anything

Dňa pondelok, 18. augusta 2014 20:33:13 UTC+2 tomas kulich napísal(-a):

[Warren]

Hey Tomas - did you run the Dart VM in unchecked mode?

[Alex Tatumizer]

It's implemented via iterator, no wonder it's slow. On top of that, it adds one at a time. You can press F3 while cursor is on "from" to see implementation.

  factory List.from(Iterable other, { bool growable: true }) {

    List<E> list = new List<E>();

    for (E e in other) {

      list.add(e);

    }

    if (growable) return list;

    return makeListFixedLength(list);

  }

[Alex Tatumizer]

Actually, for loop is fast, it's not the culprit.

Here's an account of what happens:

(I'm testing on slow comp, so absolute numbers are off by a factor of ~1.7)

Per unit of data (single reference to "hello"), copy takes 26 nanoseconds.

Of which 7 is spent in makeListFixed.

At least 12 ns are "add" expenses (very slow).

which leaves us with 7 spent here and there (hard to figure out exactly where), which is slow, too. 

 

[Alex Tatumizer]

WOW, "list.add" is really slow, it's not 12, but rather like 14.5.

This may explain something we see in other benchmarks.

[Alex Tatumizer]

slow List.add -> slow StringBuffer

slow StringBuffer -> slow JSON.stringify

It was one of dart's mysteries until now.

In JSON.stringify, there's a lot of short strings added to StringBuffer.

Quote, { ,}, [, ], comma  are all added as 1-char Strings to StringBuffer, which, in turn, translates each call into List.add

The costs of these calls don't amortize if added Strings have only 1 char, or small number of chars.

[tomas kulich]

wow again, I'm looking forward to even faster Dart once this issue is fixed (hope it can be fixed somehow) :) 

Dňa utorok, 19. augusta 2014 5:52:32 UTC+2 Alex Tatumizer napísal(-a):

[tomas kulich]

oh, silly me, I forgot about the checked mode.. This changes the "Dart on VM" result to cca. 3.5; however, the main message still holds: Dart & Dart2js are slower than expected. 

Dňa pondelok, 18. augusta 2014 23:11:53 UTC+2 Warren napísal(-a):

[tomas kulich]

Alex,

what is the status of this issue? Did you/someone create an issue in Dart issue tracker? If so, can you post a link to it pls.?

Thanks

Dňa utorok, 19. augusta 2014 5:52:32 UTC+2 Alex Tatumizer napísal(-a):

slow List.add -> slow StringBuffer

[Alex Tatumizer]

Tomas,

I have no association with dart team - I'm just a random dude. Though I have a (in?)valuable collection of dart microbenchmarks, which provide me with Knowledge. Dart doesn't have microbenchmarks of its own, that's why a message like yours always comes as a surprise.

There's no "issue" open AFAIK, but based on SVN checkins, there's something afoot.

In the past, I tried to open performance issues, with mixed success (most of them are dormant).

BTW, I never got T-shirts even for accepted issues, not even a promise of T-shirt, though I hinted on that on several occasions. Now I have less motivation to submit other performance issues (derived from microbenchmarks and never reported before), especially given that Summer is almost over, and Canadian Winter doesn't predispose anyone to wearing a T-shirt. 
This all shouldn't stop you from trying though.

[tomas kulich]

Hi Alex, 

hm, that is both sad and frustrating, especially the T-shirt part. I thought you have to be part of Dart team, especially for your advanced benchmarking methods (wow, this dude can profile on the scale of nanoseconds, coooool). I'll fill an issue then, maybe it is low hanging fruit? Thanks a lot,

[Lasse R.H. Nielsen]

On Thu, Aug 28, 2014 at 7:43 PM, tomas kulich <tomas....@gmail.com> wrote:

Alex,

what is the status of this issue? Did you/someone create an issue in Dart issue tracker? If so, can you post a link to it pls.?

No issues have been created - performance issues are problematic because it's hard to say when they are "fixed" :)

I have tried doing some optimizations of List.from, addAll, setRange and toList. It's still only on bleeding edge, and I'm sure there is more that can be done.

/L

 

Thanks

Dňa utorok, 19. augusta 2014 5:52:32 UTC+2 Alex Tatumizer napísal(-a):

slow List.add -> slow StringBuffer

slow StringBuffer -> slow JSON.stringify

It was one of dart's mysteries until now.

In JSON.stringify, there's a lot of short strings added to StringBuffer.

Quote, { ,}, [, ], comma  are all added as 1-char Strings to StringBuffer, which, in turn, translates each call into List.add

The costs of these calls don't amortize if added Strings have only 1 char, or small number of chars.

--
For other discussions, see https://groups.google.com/a/dartlang.org/
 
For HOWTO questions, visit http://stackoverflow.com/tags/dart
 
To file a bug report or feature request, go to http://www.dartbug.com/new

To unsubscribe from this group and stop receiving emails from it, send an email to misc+uns...@dartlang.org.

[Srdjan Mitrovic]

Hello,

The Dart VM team is following this mailing list. However we are reluctant to react on microbenchmarks as their relevancy is occasionally doubtful. That said, I'd like to thank everybody who contributes constructively on this list!

Both the library and the VM team have done some work recently that should address performance problems in the array operations.

I have remeasured JS, Dart and Java benchmarks mentioned at the start of this thread. With the VM and dart2js from the bleeding edge the results seem to be much better than what they used to be. Tomas, could you please remeasure with bleeding edge VM and dart2js and report the latest comparisons?

Cheers,

- Srdjan

 

[Alex Tatumizer]

Srdjan,

just in case you are looking for candidates for optimization, here's the list of worst offenders:

Expando

ByteData

double.parse()

double.toString()

Map<int, anything>

noSuchMethod

(*) Stopwatch improved, but still 40 ns (sw.elapsedTicks) vs 10 ns in java's System.currentTImeMillis()

[tomas kulich]

I don't want to be a partybreaker, but:

when copying arrays in a for loop (i.e. new List.from), then the performance of 1.5.8 and 1.6.0-dev.9.7 looks totally identical; this is true for both VM and dart2js (on node). 

However, when copying arrays by sublist, bleeding edge VM is approx. 30% slower (!), than 1.5.8, guys this is not cool! (dart2js on node is approx. the same)

Dňa štvrtok, 28. augusta 2014 22:26:31 UTC+2 Srdjan Mitrovic napísal(-a):

[Vyacheslav Egorov]

Can you share precisely the benchmark you are running?

I will take a look then.

(I see one benchmark in the first message of the thread, but that doesn't seem to cover sublist)

I think it's also time we start tracking (micro)performance of some library routines to make sure we don't regress.

On a side note: if the larger code, one that you think is suffering from List copying slowness is public - then I would love to take a look on that as well.

Thanks.

[tomas kulich]

Of course, the benchmark looks like this:

main(){

  var stopwatch = new Stopwatch()..start();

  var list = new List.filled(16, 'hello world');

  for (num i=0;i<100000000;i++){

//    var copy = new List.from(list, growable: false);

    var copy = list.sublist(0);

  }

  print(stopwatch.elapsed);

}

The main reason why copying arrays is a big deal for me is

https://github.com/vacuumlabs/persistent, which is some implementation of persistent data structures in Dart. Naturally, there is a lot of copying (of short arrays) and it turned out to consume quite relevant portion of time. For more implementation details, look at  _SubMap._insertWith method therein. Although using List.sublist helped a lot, Alex suggested, that maybe slow List.add() is the root cause of slowness of such base language primitives as StringBuffer or JSON.stringify; I find these much more relevant and maybe some effort should be put to them?

Dňa utorok, 2. septembra 2014 10:48:17 UTC+2 Vyacheslav Egorov napísal(-a):

[Vyacheslav Egorov]

Thanks for the benchmarks. I will take a look at this. 

> The main reason why copying arrays is a big deal for me is https://github.com/vacuumlabs/persistent

Is my understanding correct that you mostly would like to make https://github.com/vacuumlabs/persistent/blob/master/benchmark/src/benchmark.dart faster, not copying of arrays per se? 

// Vyacheslav Egorov

[tomas kulich]

yes, exactly. However, right now, we did a few major changes and I'm not sure whether the benchmark runs correctly. If you are interested, I'll ping you, when it is more stable.

[Vyacheslav Egorov]

Yes, of course, please do. We are always interested in investigating hotspots on the real world code!

// Vyacheslav Egorov

[Paul Brauner]

Ha, a fork of persistent, nice! Don't hesitate to send me pull requests.

[Vyacheslav Egorov]

We have started to look at this, and there was in fact a regression for small arrays. 

Lasse is planning to revisit his optimizations to avoid going into runtime system for small arrays.

I am looking at making our copying code more efficient for large arrays as well. 

We will keep you updated.  

// Vyacheslav Egorov

[Vyacheslav Egorov]

We have started to look at this, and there was in fact a regression for small arrays. 

Lasse is planning to revisit his optimizations to avoid going into runtime system for small arrays.

I am looking at making our copying code more efficient for large arrays as well. 

We will keep you updated.  

// Vyacheslav Egorov

[Alex Tatumizer]

On a bright side, dev version 1.7.0 fixes long-standing problem:
https://code.google.com/p/dart/issues/detail?id=17437
Not sure there was an intention to fix it, but it appears fixed.

[Steven Roose]

Hi,

What's the status of this?

Also, I'm interested to know how typed_data classes relate to this. Would you mind running the same benchmarks on byte arrays? I don't know how you make those in JS, but Dart has Uint8List and for Java a simple byte[] array would do. (Please try both .sublist and new Uint8List.fromList().)

Uint8List is implemented as native code and should be highly optimized. I use Uint8List.fromList(someUint8List) all the time when copying bytes. If this method performs equally bad as the regular List method, I'm screwed... (Ok not screwed. But I'd seriously bother, though.)

Thanks in advance!

Steven

[Vyacheslav Egorov]

The status of this is that we are actively looking into the performance issues here and are investigating the possibilities to optimize it without penalizing Dart VM's architecture. 

Steven, if you have real world benchmarks that you think are suffering please post them here so that we can prioritize our work. 

As far as I can see from the code - typed arrays fromList performance should be fine, for small lists it ends up calling Lists.copy which is just inlined and specialized for a specific type, and for large lists it calls into runtime system that performs a memmove. In any case it should be faster then what we currently have for normal lists at the moment. 

// Vyacheslav Egorov

[Alex Tatumizer]

Let's resort to experiment.

testUint8ListFromList(size, iterations, chunk) {
  var list=new Uint8List(chunk);
  int x=0;
  int n=size~/chunk;
  for (int i=0; i<iterations; i++) {
    for (int j=0; j<n; j++) {
      var list1 = new Uint8List.fromList(list);
      x|=list1.length;
    }
  }
  return x; // just to make sure nothing gets optimized away (caller prints x).
}

I call this function with size=256, iterations=500000, by= 8, 16, 32, 64, 256 

(Notice that total number of units moved in each test is 500000*256, same for all tests)

I have similar functions for Uint16List and Uint32List

It prints time per unit (unit=byte for Uint8, 16 bits for Uint16, etc).

Results:
...
5. testUint8ListFromList/256  0.671875 nsec/unit   // /256 means calling function with chunk=256).
6. testUint8ListFromList/64  2.2109375 nsec/unit 
7. testUint8ListFromList/32  4.2421875 nsec/unit 
8. testUint8ListFromList/16  8.1875 nsec/unit 
9. testUint8ListFromList/8  5.7578125 nsec/unit 

10. testUint16ListFromList/256  0.859375 nsec/unit 
11. testUint16ListFromList/64  2.5546875 nsec/unit 
12. testUint16ListFromList/32  4.7265625 nsec/unit 
13. testUint16ListFromList/16  9.015625 nsec/unit 
14. testUint16ListFromList/8  6.34375 nsec/unit 

15. testUint32ListFromList/256  1.171875 nsec/unit 
16. testUint32ListFromList/64  2.9296875 nsec/unit 
17. testUint32ListFromList/32  5.09375 nsec/unit 
18. testUint32ListFromList/16  9.5234375 nsec/unit 
19. testUint32ListFromList/8  6.6796875 nsec/unit 

Amortized cost per unit is much higher for shorter lists. System of equations (with a fair amount of hard work!) shows that pure overhead of a single call through entire stack, including memmove ,is about 120 nanoseconds (320 cycles on my comp!). The glue is very expensive. This hurts many other optimizations in dart. Can something be done about it? 

As a side effect, copying, say, 256 uint8 takes virtually the same time as copying 256 uint16 (despite that memmove itself copies data at least 4 bytes at a time, most likely 16 bytes at a time with SIMD). 

The size on which program switches to copy by a loop (as opposed to mommove) is not 100% optimal, but close.

Nothing earth-shattering here. Except cost of glue, not much to see. 

[Alex Tatumizer]

same test in java (using byte[].clone): "glue overhead" is just 8-9 nanoseconds per call (against dart's 120).

Is it possible that dart -> C++ glue is responsible for most of dart/java performance mismatch? 

[Alex Tatumizer]

@Slava: once you are at it, setRange suffers from the same problem
testUint8ListSetRange(size, iterations, chunk) {

  var list=new Uint8List(chunk);
  int x=0;
  int n=size~/chunk;

  var list1=new Uint8List(chunk);

  for (int i=0; i<iterations; i++) {
    for (int j=0; j<n; j++) {

      list1.setRange(0, chunk, list);
      x|=list1.length;
    }
  }
  return x;
}
...
5. testUint8ListSetRange/256  0.5078125 nsec/unit
6. testUint8ListSetRange/64  1.984375 nsec/unit
7. testUint8ListSetRange/32  3.8359375 nsec/unit
8. testUint8ListSetRange/16  7.6015625 nsec/unit
9. testUint8ListSetRange/8  4.8359375 nsec/unit

Again, the road to efficient memmove is too long.

[Alex Tatumizer]

Another exciting research topic: performance of double.parse.
testDoubleParse(int size, iterations, chunk) {
  int x=0;
  var s="12345678911234567891123456789112"; // 32-char string
  String str=s.substring(0,chunk);
  int n=size~/chunk;

  for (int i=0; i<iterations; i++) {
    for (int j=0; j<n; j++) {

      x|=double.parse(str)>0?1:0;
    }
  }
  return x;
}
...
5. DoubleParse/32  7.984375 nsec/unit
6. DoubleParse/16  14.4609375 nsec/unit
7. DoubleParse/8  21.0234375 nsec/unit
8. DoubleParse/4  38.546875 nsec/unit


Let's compare chunk of 16 with chunk of 8. In the former case, there's 16 invocations of double.parse in the inner loop; in the latter - 32.
In both cases, 256 bytes get processed (size=256). So 16 extra invocations translate to (21-14.46)*256 ns, which (using google calculator) results in  1674.24ns,
so per extra invocation we get (google again) 104 nanoseconds.

This gets especially expensive for shorter values.

From common sense, it's clear that parsing of double value should take approximately the same time as parsing int - and indeed, this is the case in java.
But in dart, parsing int of size 8 takes 26 ns, but parsing double of size 8 - 160 ns - mostly because of disproportionate overhead of dart->C++ interface
(int.parse() is written in pure dart, no C++ calls there)

[Andrew Skalkin]

Let me just chime in with Alex regarding the the performance of parsing doubles. I have also ran into similar issues when parsing 100MB CSV files and did similar benchmarks with similar results. Any improvements on this front  (as well as fast operations on typed arrays) would be greatly appreciated!

[Alex Tatumizer]

Interesting thing about double.parse is that it could be made lightning fast if implemented in pure dart using SIMD.

Load 4 digits at a time into SIMD floating point register, multiply by vector [1, 10, 100, 1000], add horizontally twice.

(Same can be done for int.parse, of course).

Unfortunately, current dart library doesn't give access to horizontal add, nor to any other interesting instructions (convert to int vector, mul int vector, etc etc).

Similar improvements could be done for double.toString..

Not everything can be rewritten in pure dart though. Functions like memmove need to be intrinsified by compiler.

[Vyacheslav Egorov]

Andrew & Alex,

Lets not pile too much into this single thread, otherwise it will all fall through cracks.

If you have an performance issue, please file a bug. If your app is having performance issues - we are more than interested in fixing those for you. 

We are not that inclined to prioritize fixing performance issues based on microbenchmarks: e.g. I can easily teach LICM to hoist double.parse(str) out of the loop (as it is indeed a loop invariant) and your loop, Alex, will run in 0ms - but that will not necessarily translate into any performance improvement in the real world code. 

That said, I will take a look to make sure we are not wasting any time unnecessarily here. One problem (among others, I guess) is that doubles in Dart are boxed, so you will pay more for that (though there are things that can be done here to reduce or eliminate this cost, but they are highly specific to the .parse call site).

> as well as fast operations on typed arrays

Typed arrays operations should be fast these days (sans some stuff related to Int32/Uint32 ones, but I am working on fixing that). If you are experiencing bad performance on smth that is not Int32/Uint32 typed data please send us a mail or file a bug.

// Vyacheslav Egorov

On Thu, Sep 4, 2014 at 8:55 PM, Andrew Skalkin <ska...@gmail.com> wrote:

Let me just chime in with Alex regarding the the performance of parsing doubles. I have also ran into similar issues when parsing 100MB CSV files and did similar benchmarks with similar results. Any improvements on this front  (as well as fast operations on typed arrays) would be greatly appreciated!

--

[Lasse R.H. Nielsen]

On Thu, Sep 4, 2014 at 10:25 PM, Alex Tatumizer <tatu...@gmail.com> wrote:

Interesting thing about double.parse is that it could be made lightning fast if implemented in pure dart using SIMD.

Load 4 digits at a time into SIMD floating point register, multiply by vector [1, 10, 100, 1000], add horizontally twice.

Without checking, I'll wager that that approach will not give the correct result in all cases.

Parsing doubles *correctly* is heinously difficult. 

/L

[Alex Tatumizer]

> I can easily teach LICM to hoist double.parse(str) out of the loop (as it is indeed a loop invariant) and your loop

So what? My goal is to test performance of double.parse. If I notice compiler hoisting it (I immediately see it, because I print perf/unit, and I KNOW what reasonable timing is) - I will change the loop so that you won't be able to hoist anything.

You argument sounds like measuring performance of double.parse is a bad idea, because compiler can hoist something. How one thing relate to another? Either you want to know real performance, or you don't. If you want to know it, you will find a way around hoisting.

[Vyacheslav Egorov]

> My goal is to test performance of double.parse.

You ignored the start of my sentence: I am just trying to highlight that real application performance issues are always more important than microbenchmarks.

Real world performance is not a simple sum of micro-costs. 

If there is an application which spends XX% of time in parsing doubles - and is slow because this parsing is slow --- please file a bug.

Surely if every single thing in the system takes as little time as practically possible - then all Dart apps in the world will become faster. 

However we can't magically make every single thing optimal, we have to prioritize things based on those real world apps that experience performance issues.

That's what I was trying to say.

// Vyacheslav Egorov

[Alex Tatumizer]

There's just 20 or so basic low-level functions in any language. They have to perform well for other functions to perform well.

setRange, cloning a typed list, parsing numbers, adding element to a list - all belong to this set.

If some of these functions perform at a rate of just 1/10 of java, I think it's a problem, and it won't hurt to know about it.

Otherwise, sure, you can't fix everything at once. I was complaining about basic functions only.

It's not a life and death issue anyway, please take it easy :-)

[Alex Tatumizer]

Just for curiosity, compared performance of pure computations in dart vs java, using generator of Mendelbrot set image (1000*1000 points). See code https://gist.github.com/tatumizer/0589a2165f1812a75c6f

And what do you think? Timing of dart is *EXACTLY THE SAME* as java -approx. 4 ns per iteration.

Good news.

[Alex Tatumizer]

Used Image package (by Brendan Duncan) to generate a picture of Mandelbrot set.

Benchmarks show that even with complete generation of png image, performance of dart is on par with java.

To make things more interesting, added 2 lines in the code to produce a gorgeous area rug.

https://dl.dropboxusercontent.com/u/22697562/mandelbrot-rug.png

If dart needs a pattern for T-shirt, we can talk.

[Brian DeLacey]

Impressive results! 

That image library looks nice.

Brian

[tomas kulich]

Hi Vyacheslav and all,

we finished the implementation of persistent data structures library: https://github.com/vacuumlabs/persistent There are also some simple benchmarks - maybe useful for some overall Dart performance benchmarking?

The copying of lists isn't (probably) a deal anymore, since we replace this by using .sublist wherever possible; also https://code.google.com/p/dart/issues/detail?id=20735, hints that list.add should be quite fast now.