Optimising (or just avoiding madly slow things) in JS mode

Oolong

Hi, I'm working a physics-based project that runs very nicely in Java mode, okay in JavaScript on my main machine until there are too many objects on the screen, but hopelessly slow when viewing the JS version on a tablet.

I wondered if anyone had any general advice on optimising JS Processing code, or functions I should really just avoid? I'm using ArrayLists, for example, where I could just have a fixed-length array from the beginning that's big enough to hold everything I could feasibly need - I know ArrayList is slower in general, but is it so bad in JS that it's better to have massively over-sized arrays in most circumstances?

I've seen things that look just as complex as my app with a hundred-odd objects, but running much faster, so I figure I could probably sort mine out too, but optimising JavaScript is not in me realm of experience at all so far...

GoToLoop

JS's arrays are very powerful & flexible. Got more features than Java's LinkedList:
http://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html

But that comes w/ a hefty price: When it's resized, it got serious trouble to get back a contiguous block of memory for all of its values! So it's better treat them as if they were fixed-size, like Java's. 8-X

If you got any big dynamic-sized arrays, you should consider instantiate them as big enough to comfortably store everything they may need. Then use another variable to control their logical length.

Dunno how good ArrayList was implemented in Processing.JS framework.
Whether it's able to resize its internal array from time to time rather than every time! :-??

GoToLoop

Doing a search for ArrayList inside "processing.js", found out how its add() method is implemented:

this.add = function() {
if (arguments.length === 1) array.push(arguments[0]);

It's just a slow JS's push()! It doesn't try to pre-resize its internal array like Java's ArrayList smartly does! :-w

And let's not talk about its remove() method:

this.remove = function(item) {
  if (typeof item === "number") return array.splice(item, 1)[0];

It's a slow as snail splice()! Indeed, avoid "processing.js"' ArrayList's implementation! :-&

Oolong

So, wait, actually, can we talk about its remove() method? Specifically, if I'm replacing ArrayList with arrays, what's a good substitute for it?

mbraendle

Hmm, I don't think that the ArrayList methods are the time-limiting step.

I think it's the calculation of the physics. I use Traer's library for simulation of particles and have no problems to simulate hundreds of interactions (attractions, repulsions) in JavaScript mode without too much slowdown.

Oolong

I'm pretty sure it is faster after I've replaced all the ArrayLists with standard arrays, for what it's worth. It also has a new bug where all the particles occasionally disappear suddenly for no obvious reason, but I still call that progress. ;)

I haven't looked at Traer's library much. I see it looks flexible enough to allow things like a force that's inversely proportional to the sixth power of distance. Any thoughts about why it might be faster?

GoToLoop

In order to understand why "Processing.JS"'s ArrayList is slow, let's read about Java's own implementation 1st:
http://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity() operation. This may reduce the amount of incremental reallocation.

In short, when we use add(), it doesn't necessarily mean the ArrayList's internal array gonna grow every time.
It 1st checks out whether it still got room to add() the element. Only when there's none, it instantiates another array, generally double the size of the predecessor, copy everything to it, and then add() the element!

So it smartly manages the internal array's capacity, avoiding resizing as much as possible!
And when we remove() from it, it never changes the internal array either! We gotta use trimToSize() for it! :-j

Oolong

Thanks for that. I'm still struggling with the replacement of remove(), though. I'm not sure how I'd remove an array element without splice() - and actually, I'm not sure how I do it with, either. I thought this would work, but apparently not:

  for (int i = nucleonCount-1; i >= 0; i--) {  
    if (nucleons[i].particleIndex == this.particleIndex) {              
      splice(nucleons,i, 1);                
      nucleonCount--;
      printIfDebugging("nucleonCount--="+nucleonCount);
    }
  }

(After I do this it crashes because it finds a null element in the array...)

GoToLoop

And as aforementioned, "Processing.JS"'s ArrayList is merely a cheap simulacrum of Java's! b-(
Its add() relies on JS's push(). It means the internal array increases its size "every" time rather than "some" times as it is w/ Java's own smarter implementation! [-(

But why increasing an array's length is slow? B/c for best index search performance, it gotta store its elements in a contiguous chunk of RAM. When its size is increased, it gotta find and allocate another contiguous RAM block or suffer fragmentation; in which case, its elements would be spread everywhere like a LinkedList!

All that "find, allocate and copy content" process is slow, especially when its length is already too big! :-SS
That's why we should avoid changing array sizes all the time! Better yet, never change it! :D
And in order to fix "Processing.JS"'s implementation, it gotta be rewritten! #:-S

Oolong

I'm stuck, though. I need to take particles out of my array of particles when they leave play. That's easy with ArrayList, and disappointingly difficult without (right now I'm not even sure why my kludge isn't working). :-/

SiriusCG

[EDITED] GoToLoop pretty much explained it. No need for me to expand on it.

Cheers.

Oolong

Yeah, I get you.

I wish I knew how to remove an element from an array cleanly, though. :(

GoToLoop

Processing's splice() implementation doesn't modify the original array passed to it.
It instantiates another 1 w/ a different bigger length, 2 arrayCopy()s, inserts element(s), and returns new array:
http://processing.org/reference/splice_.html

static final public Object splice(Object list, Object value, int index) {
  Class<?> type = list.getClass().getComponentType();
  Object outgoing = null;
  int length = Array.getLength(list);

  // check whether item being spliced in is an array
  if (value.getClass().getName().charAt(0) == '[') {
    int vlength = Array.getLength(value);
    outgoing = Array.newInstance(type, length + vlength);
    System.arraycopy(list, 0, outgoing, 0, index);
    System.arraycopy(value, 0, outgoing, index, vlength);
    System.arraycopy(list, index, outgoing, index + vlength, length - index);

  } else {
    outgoing = Array.newInstance(type, length + 1);
    System.arraycopy(list, 0, outgoing, 0, index);
    Array.set(outgoing, index, value);
    System.arraycopy(list, index, outgoing, index + 1, length - index);
  }

  return outgoing;
}

Processing.JS does the same but relies on JS's splice():

p.splice = function(array, value, index) {
  if (value.length === 0) return array;

  if (value instanceof Array)
    for (var i = 0, j = index; i < value.length; j++, i++)  array.splice(j, 0, value[i]);
  else array.splice(index, 0, value);

  return array
};

But here's another problem: those implementations got nothing to do w/ removing of elements!
Instead they're about adding elements from a specified index! @-)
It's barely related to JS's original splice() own implementation:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice

You're gonna need to combine subset() + splice() in order to emulate an ArrayList's** remove()**:
http://processing.org/reference/subset_.html

I don't need to tell you that it's slow besides being complicated! :-S

GoToLoop

My advise is, if you need to remove() an arbitrary indexed element, you gotta stick w/ ArrayList.
There are many other alternative solutions nonetheless:

• You could create your own ArrayList version for the Processing.JS framework (JS Mode).
  Which would more closely follow Java's actual high-performance implementation!

• You could re-write your sketch in CoffeeScript mode, which still uses Processing.JS framework,
  but you would use JS native arrays, along w/ its true splice() method.
  W/ an added bonus: Diff. from JS prototypes, CS got actual class syntax very similar to Java's!

• And finally, you could re-write it in http://p5js.org, which is another Processing-based framework for JS.
  Obvious problem is that you'd have to convert all your classes to JS prototyped "classes"! :o3

Oolong

Blech. Well removing things really doesn't come up all that much - I could live with a momentary pause for each removal, if it comes to it.

Or maybe I should just go back to ArrayList. Bah. :(

When I try to install CoffeeScript mode (in Processing 2.1.1) it says 'Could not find a mode in the downloaded file'.

GoToLoop

• The utmost performance-wise solution is have classes w/ an additional boolean field which signals it's "dead/inactive"!
• In such implementation, rather than remove() an object, we'd turn that off.
• When the time comes to create another such object, it 1st checks out whether there's a "dormant" object available. If positive, it reinitializes their fields & turn it on.
• An "inactive" object simply immediately returns from its action methods. So it plays "dead".
• In such implementation, the array holding those objects only add() and never remove() its elements.
• There will come a time that its maximum size reaches a plateau and stabilizes.
  Becoming a "fixed-size" data-structure eventually.

Here's an online example relying on just that:
http://studio.processingtogether.com/sp/pad/export/ro.91kLmk61vAOZp/latest

GoToLoop

When I try to install CoffeeScript mode (in Processing 2.1.1) it says 'Could not find a mode in the downloaded file'.

Besides having many tips for CS Mode, it also teaches how to install it manually:
https://github.com/fjenett/coffeescript-mode-processing

Oolong

I like your thinking, though I guess it's going to be a bit of a pain to implement, since it means looping over a larger number of entries than would otherwise be necessary, and checking every time that they're active.

Hmm.

Still, seems feasible...

GoToLoop

... since it means looping over a larger number of entries than would otherwise be necessary...

Yea I know! But since it returns very early: if (isInactive) return false;, it's not that bad! O:-)

It recovers ground by never removing, avoid creation of objects when there are others inactive lying around and reaching a plateau fixed-size eventually! \m/

Actually, rather than using an ArrayList, we can use a regular array w/ some big enough length to comfortably accommodate its plateau size.

Fill that array up w/ "dead" objects. Then there'll be no add() nor remove() at any time.
Only turning them on & off w/ maximum performance! >:/

Oolong

Yeah, fair enough - and I've implemented your suggestion now! Seems to work okay, touch wood - I'll need to do a bit of testing yet though.

Cheers! Any other thoughts about JS optimisation? I'm open to switching to a physics library, but I'd like to know why it might be faster, if it is...

GoToLoop

... and I've implemented your suggestion now!

It doesn't seem it's present in your GitHub yet? :-??

Any other thoughts about JS optimization?

None for now. But for Java, you should definitely declare constants as final! :P
JS got a const keyword too. But only for P5.JS or CS Mode! B-)

Oolong

It doesn't seem it's present in your GitHub yet?

Erm... it doesn't?

Is it likely to bring me significant performance gains if I switch to one of the other JS-based modes? P5.js launched just after I started this project, and I've never really looked at CoffeeScript very much...

GoToLoop

Erm... it doesn't?

Well, when I looked there was no clue that anything like object on & off state was there!
It says latest pull commit happened about 14 hours ago! Perhaps I was too early? :-?

GoToLoop

Is it likely to bring me significant performance gains if I switch to one of the other JS-based modes?

In your case, the only stumbling block in JavaScript Mode is its ArrayList poor low-quality implementation!
If only we had a good quality ArrayList in Processing.JS's framework, no language change'd be necessary! :-<

Only gain you'd get for moving to either CoffeeScript Mode or P5.JS is direct use of JS's own array w/ all of its native methods w/o Java syntax getting in the way! :-@

GoToLoop

There's an important performance hit inside your classes' constructors:
You loadImage() the same picture files all the time. Even inside the super parent class, it loads an image and then it is all discarded inside subclass' constructor! 3:-O

Resources should be loaded in setup() and kept for future use.
Rather than loading resources, classes should receive them from the main class instantiating it! *-:)

GoToLoop

2 sketches written in all 3 languages: :bz

• http://forum.processing.org/two/discussion/5615/coding-noob-needs-help-how-do-i-draw-an-expanding-circle-that-triggers-with-a-mouse-click

• http://forum.processing.org/two/discussion/7294/why-doesnt-my-sketch-run-in-javascript-mode

Oolong

...oh. The Processing IDE seems to have lost everything after line 102, and GitHub now reflects that. I should probably have pushed more intermediate changes. I thought I'd pushed changes successfully because the file on GitHub had been updated, my local git said it was up-to-date, and the file I had open and was saving in the IDE was working okay.

Since I restarted the IDE it now shows that half of the local file has disappeared, like on GitHub.

Drat.

Oolong

Okay, at least this is working in Java again now. Something seems to have gone horribly wrong with the JS version in the meantime, but hey... still progress.

Oolong

Fixed it! And I think the image optimisation made a big difference, thanks for that @GoToLoop! Now online for beta testing. :D