1932203 - Modified paper.js demo (http://paperjs.org/examples/voronoi/) spends 3minute+ , mostly around Pre/post/incremental Barrier

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, task, P3)

Description

[Mayank Bansal]

Go to http://paperjs.org/examples/voronoi/
Click on 'source' on the top-right of the demo
Once the code appears, change line number2 :
Original: var sites = generateBeeHivePoints(view.size / 200, true);
Change to: var sites = generateBeeHivePoints(view.size / 2, true);
Click "Run"

Profile: https://share.firefox.dev/3ZcLPwh

This library is old, and not very popular, and not much updated. So i dont know how important this testcase is.

Comment 2

[Iain Ireland [:iain]]

This is ~all MoveDenseElements in Array.splice. Not sure how much room there is to optimize that. The code in question looks like:

// iterate backward so we can splice safely
	while (iEdge--) {
		edge = edges[iEdge];
		// edge is removed if:
		//   it is wholly outside the bounding box
		//   it is actually a point rather than a line
		if (!this.connectEdge(edge, bbox) || !this.clipEdge(edge, bbox) || (abs_fn(edge.va.x-edge.vb.x)<1e-9 && abs_fn(edge.va.y-edge.vb.y)<1e-9)) {
			edge.va = edge.vb = null;
			edges.splice(iEdge,1);
			}
		}
	};

It's iterating backwards through an array and repeatedly removing one element, which requires us to move the rest down. That's an O(n^2) algorithm, so it's necessarily going to scale kind of poorly, and I don't think we can safely elide the barriers.

Are we significantly slower than V8 here?

Comment 3

[Mayank Bansal]

Thanks for the detailed explanation.
I checked and we are not significantly slower than V8. Closing this bug.