Complex computation slower than JavaScript

[hjlld]

Hello, I'm working on solve a problem that compute the minimum distance between two geometries in 3D space. I choose a brutal force algorithm, it's a complexity O(nm) for nm distances computed.

It only relies on + - * / and Mathf.sqrt(), Mathf.abs() computation, all numbers are f32.

Any way I realized it by Javascript( compiled from Typescript ), then I use the same Typescript code to compile it to wasm by AssemblyScript's compiler.

The wasm way also works, but seems even slower than JS.

For example, same two geometries, in JS cost 83 seconds, but in wasm / web worker, need 445 seconds.

Any one could help me to provide any idea or possible reason?

BTW, I use wasm in web workers, but all typedarray are transferable with their buffer, like Worker.postMessage( typedarray, [ typedarray.buffer ] ) , so i don't think the data transfer between main thread and worker thread is the key.

[MaxGraey]

so i don't think the data transfer between main thread and worker thread is the key.

Probably interop between wasm and js is a key. Without full source of code and benchmark hard to tell what's wrong. Are you use -O3 and --noAssert flags?

[hjlld]

No, i don't use any flags, the code for passing typedarray to wasm please see this gist:

https://gist.github.com/hjlld/db8f3856fb9b8724814c2f3ef722e1d7

and in AS i exported relative type id by:

export const Uint32Array_ID = idof<Uint32Array>();

export const ArrayUint32Array_ID = idof<Array<Uint32Array>>();

export const Float32Array_ID = idof<Float32Array>();

export const ArrayFloat32Array_ID = idof<Array<Float32Array>>();

[MaxGraey]

And you measure this.wasmModule.CalDistanceOfTwoMeshArray method? Could you show CalDistanceOfTwoMeshArray source code body?

[hjlld]

the two geometries i mentioned before, each one have 28052 f32 numbers, which means totally 28052 * 2 numbers passed from JS to wasm make the computation.

@MaxGraey the full computation code is updated in the same gist:

https://gist.github.com/hjlld/db8f3856fb9b8724814c2f3ef722e1d7#file-caldistanceoftwomesharray-ts

in which:

Mesh is a simple class has nothing than three properties, like a neat simple object in JS.

Min is a function wrapped from Mathf.min() for comparing not only 2 numbers but more.

Vector3 is a vector3 class, has two methods below:

    public fromArray( array: Float32Array, offset: i32 ): Vector3 {

		this.x = array[ offset ];
		this.y = array[ offset + 1 ];
        this.z = array[ offset + 2 ];
        
        return this;

    }

    public applyMatrix4( e: Float32Array ): Vector3 {

        let x = this.x, y = this.y, z = this.z;

		let w: f32 = 1.0 / ( e[ 3 ] * x + e[ 7 ] * y + e[ 11 ] * z + e[ 15 ] ) ;

		this.x =  (  e[ 0 ] * x +  e[ 4 ] * y +  e[ 8 ] * z +  e[ 12 ] ) * w ;
		this.y =  (  e[ 1 ] * x +  e[ 5 ] * y +  e[ 9 ] * z +  e[ 13 ] ) * w ;
		this.z =  (  e[ 2 ] * x +  e[ 6 ] * y +  e[ 10 ] * z +  e[ 14 ] ) * w ;

		return this;

    }

[MaxGraey]

Several suggestions:

• I saw this Min([distance1, distance2, distance3]). Better use Min(distance1, distance2, distance3) without creation array, so function looks like:

@inline
function Min(a: f32, b: f32, c: f32): f32 {
  return Mathf.min(a, Mathf.min(b, c));
}

• inline (@inline decorator) any small util functions
• use -O3 and --noAssert compiler flags
• cache array.length like:

let ilen = meshes1.length;
let jlen = meshes2.length;
for (let i = 0; i < ilen; i ++ ) {
        for ( let j = 0; j < jlen; j ++ ) {
            ...
        }
}

• use unchecked() like:

let mesh = new Mesh( unchecked(positions2[ i ]), unchecked(indices2[ i ]), unchecked(matrices2[ i ] ));

and for set index accessors:

unchecked(vertex1Array[ i ] = 100.0f)

• instead:

if( distance < distanceMin ) {
  distanceMin = distance;
}

use

distanceMin = Mathf.min(distanceMin, distance);

[MaxGraey]

How you measure?

[MaxGraey]

I mean how you measured performance? Is it performance.now which measured CalDistanceOfTwoMeshArray only function or it was whole MeasureNearestDistanceByWASM function?

[hjlld]

I use performance.now() before and after MeasureNearestDistanceByWASM function in JS

[MaxGraey]

Got it. So you measure also a lot of array's creation and interops which not exists on JS side. You should optimize MeasureNearestDistanceByWASM glue code first. This is huge bottleneck

[hjlld]

thanks a lot , i'll fix the code and try again.

[hjlld]

should every array[ index ] be wrapped by unchecked() ?

[MaxGraey]

Yes, this skip bounds check. But until this PR which fix some missing unchecked methods for typed arrays is not landed in dist files this unchecked hints just ignored. But in next AS update this changes will take effect

[hjlld]

i'll close this, try to implement a new algorithm. Thanks @MaxGraey a lot!