search

mourner / icomesh

Fast JavaScript icosphere mesh generation library for WebGL visualizations
https://observablehq.com/@mourner/fast-icosphere-mesh
ISC License
55 stars 4 forks source link

Speed improvments #1

Closed MaxGraey closed 5 years ago

MaxGraey commented 5 years ago

Before:

Generated 0-order icosphere (12 vertices / 20 triangles) in 0.426ms.
Generated 1-order icosphere (42 vertices / 80 triangles) in 0.16ms.
Generated 2-order icosphere (162 vertices / 320 triangles) in 0.261ms.
Generated 3-order icosphere (642 vertices / 1280 triangles) in 1.149ms.
Generated 4-order icosphere (2562 vertices / 5120 triangles) in 8.532ms.
Generated 5-order icosphere (10242 vertices / 20480 triangles) in 9.831ms.
Generated 6-order icosphere (40962 vertices / 81920 triangles) in 40.313ms.
Generated 7-order icosphere (163842 vertices / 327680 triangles) in 104.385ms.
Generated 8-order icosphere (655362 vertices / 1310720 triangles) in 246.576ms.
Generated 9-order icosphere (2621442 vertices / 5242880 triangles) in 1,056.284ms.
Generated 10-order icosphere (10485762 vertices / 20971520 triangles) in 4,345.416ms.

After:

Generated 0-order icosphere (12 vertices / 20 triangles) in 0.289ms.
Generated 1-order icosphere (42 vertices / 80 triangles) in 0.168ms.
Generated 2-order icosphere (162 vertices / 320 triangles) in 0.256ms.
Generated 3-order icosphere (642 vertices / 1280 triangles) in 1ms.
Generated 4-order icosphere (2562 vertices / 5120 triangles) in 5.527ms.
Generated 5-order icosphere (10242 vertices / 20480 triangles) in 8.63ms.
Generated 6-order icosphere (40962 vertices / 81920 triangles) in 36.263ms.
Generated 7-order icosphere (163842 vertices / 327680 triangles) in 58.615ms.
Generated 8-order icosphere (655362 vertices / 1310720 triangles) in 158.19ms.
Generated 9-order icosphere (2621442 vertices / 5242880 triangles) in 688.847ms.
Generated 10-order icosphere (10485762 vertices / 20971520 triangles) in 2,923.715ms.
MaxGraey commented 5 years ago

@mourner Also I tried new alternative pairing function:

const key = (Math.exp(b * 0.6931471805599453) * (2 * a + 1) - 1) | 0; // 2 ** b (2a + 1) - 1

And this do even better results but I afraid it could be incorrect. Without tests hard to say is it necessary or not. Anyway results pretty interesting:

Generated 0-order icosphere (12 vertices / 20 triangles) in 0.246ms.
Generated 1-order icosphere (42 vertices / 80 triangles) in 0.222ms.
Generated 2-order icosphere (162 vertices / 320 triangles) in 1.687ms.
Generated 3-order icosphere (642 vertices / 1280 triangles) in 0.786ms.
Generated 4-order icosphere (2562 vertices / 5120 triangles) in 4.234ms.
Generated 5-order icosphere (10242 vertices / 20480 triangles) in 8.39ms.
Generated 6-order icosphere (40962 vertices / 81920 triangles) in 36.666ms.
Generated 7-order icosphere (163842 vertices / 327680 triangles) in 49.946ms.
Generated 8-order icosphere (655362 vertices / 1310720 triangles) in 92.709ms.
Generated 9-order icosphere (2621442 vertices / 5242880 triangles) in 268.256ms.
mourner commented 5 years ago

@MaxGraey interesting but not correct unfortunately — add this line at the end to validate:

if (midCache && midCache.size !== (T - 1) * 10) throw new Error('Collision in midCache.');

Also unfortunately the biggest optimization in the PR (| 0 in the key) breaks the cache for orders 8+ because 2 ** 31 | 0 overflows.

mourner commented 5 years ago

@MaxGraey hitting some v8 bug maybe? Or platform differences (mac vs etc.)? "120,752.467ms" definitely looks unreasonable.

I probably mixed up my Node versions — just reran making sure I'm on the right ones:

Node v10

# before
Generated 9-order icosphere (2621442 vertices / 5242880 triangles) in 2,277.313ms.
Generated 10-order icosphere (10485762 vertices / 20971520 triangles) in 10,597.528ms.

# after
Generated 9-order icosphere (2621442 vertices / 5242880 triangles) in 2,618.91ms.
Generated 10-order icosphere (10485762 vertices / 20971520 triangles) in 17,687.592ms.

Node 12

# before
Generated 9-order icosphere (2621442 vertices / 5242880 triangles) in 2,150.844ms.
Generated 10-order icosphere (10485762 vertices / 20971520 triangles) in 22,334.221ms.

# after
Generated 9-order icosphere (2621442 vertices / 5242880 triangles) in 2,794.588ms.
Generated 10-order icosphere (10485762 vertices / 20971520 triangles) in 11,552.395ms.

So the PR is significantly improving high-order perf for Node v12 while significantly slowing it down for Node v10. Weird! Perhaps we should report this to the v8 team. @RReverser do you perhaps happen to know what black magic is going on here or refer to the right person to ask?

MaxGraey commented 5 years ago

I updated results with your latest x3 speed improvement