Support for alternative ID generation methods

[nkrisztian89]

Description of the problem

We are parsing large data files which can contain up to tens of thousands of objects that we create ThreeJS (buffer)geometries for and finally merge them for efficient rendering. Profiling shows that the most costly part of loading (taking 25% of time in Chrome, somewhat less in Firefox) is actually generating the UUIDs for all the ThreeJS objects (the generateUUID() method from Math.js, due to the cost of string operations). In our case we do not need any of the serialization features and therefore don't really need the UUIDs either. Indeed, after swapping that function for a simple step ID implementation instead:

THREE.Math.generateUUID = function () {
  var _id = 0;
  return function generateStepID() {
    return (_id++).toString();
  };
}();

loading takes 25% less time (that can mean several seconds) and everything works as before.

This made me think if there could be a way to add functionality to select another ID generation method in case the application does not require UUIDs. Such as having a "THREE.Math.setIDGeneratorFunction()" or similar that could accept custom functions (or maybe also strings such as "UUID", "stepID" to choose from default implementation options).

This way there would be no need to manually overwrite an internally used ThreeJS function for better performance and others with similar needs could benefit if they find it in the docs. I would be happy to prepare a pull request for this. However, for robustness I think it would involve changing the "uuid" property of items to "id" to avoid the false implication it is a UUID in all cases, and also adding errors if UUID-reliant functions are attempted to be used with a non-UUID implementation. So maybe I am taking a wrong/overly complex approach to this?

Three.js version

• Dev
• r87

Browser

• All of them
• Chrome
• Firefox
• Internet Explorer

OS

• All of them
• Windows
• macOS
• Linux
• Android
• iOS

Hardware Requirements (graphics card, VR Device, ...)

[looeee]

I've ran into the exact same issue about a year back - creating many (a couple of 100,000) individual buffer geometries then merging them for rendering. The biggest bottleneck was the UUID function.

Is there a reason we need such a complex UUID in the first place rather than just a simple incrementing ID? An incrementing ID can also guarantee uniqueness, at least within a single app.

[Usnul]

Having a pluggable id generator would be nice. Generating a spec complaint non-random UUID might also be possible. Lastly, it might be worth it to make id generation lazy.

[takahirox]

Personally I prefer having only one uuid generating function because it's much simpler.
Having alternative/pluggable generator could cause problems, especially it generates non-unique id, when objects go across multiple apps.

So, I prefer simply optimizing uuid generator (or replacing with faster one).
I'm trying optimization and achieved 2x performance on my Chrome by replacing .join with string concatenation, but it makes a bit slower on FireFox nightly.

I'll try some other optimizations and share the result later...

[nkrisztian89]

Optimizing the existing generator could certainly be a good idea, but if we stick to the UUID format it only goes so far. We'll require all those characters and somehow assembling them into a string, which are sadly slow operations in JS (trying concatenation was also my first bet when I met this problem a few months ago, it did not change performance in my tests in then-current Chrome).

But even if the UUID format is kept and generation remains slow (if somewhat faster), I do like the idea to make it lazy (as in only do the actual generation when a UUID is to be used), so all those use cases which don't require UUIDs but use lots of objects will become automatically faster.

[mrdoob]

I vote for trying to optimise the current code.

Otherwise, it would have to look something like this:

Object.defineProperties( Object3D.prototype, {
	_uuid: {
		value: undefined,
	},
	uuid: {
		get: function () {
			if ( this._uuid === undefined ) {
				this._uuid = _Math.generateUUID();
			}
			return this._uuid;
		},
		set: function ( value ) {
			this._uuid = value;
		}
	}
} );

[takahirox]

I think Lazy UUID generation is a good approach to solve this issue. Then I made PR #12437.

I still think optimizing UUID generation is also worth even if we merge laze UUID generation.
I'll share my evaluation later.

[Usnul]

Sir. Doob, there is another option. Rewrite the property of the object after generation. Though that is not very fast in my experience.

[tentone]

@takahirox I dont think lazy generation its a good solution i would prefer to move to a more simple generator keeping the same ######-####-####-####-###### structure.

Or better lets make it lazy but still update it to be faster

[tentone]

This is what i have come up with, the existing one is already really good, nice work @mrdoob.

20~40% improvement in both firefox and chrome.

var chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".split("");
var uuid = "------------------------------------".split("");

function generateUUID()
{
	var rnd = Math.random() * 0xffffffff;

	for(var i = 0; i < 36; i++)
	{	
		if(i === 8 || i === 13 || i === 18 || i === 23)
		{
			continue;
		}

		rnd >>= 1;
		uuid[i] = chars[rnd & 0xf];
	}

	return uuid.join("");
}

[kchapelier]

@tentone Be wary that this id generation algorithm tends to generate more collisions than the original code. On my computer on Chrome for 1.000.000 ids generated there are more than 100 collisions, where the current algorithms generates none.

// simple collision tester
var o = {};
var num = 1000000;
for (var i = 0; i < num; i++) {
  o[generateUUID()] = true;
}
console.log(num - Object.keys(o).length, 'collisions');

[tentone]

@kchapelier Just noticed that wasnt supposed to happen this should have same number as collisions as using the Math.random() method by itself.

I was experimenting and noticed that for high values by shifting 0 we can actually change the value for some reason, hmmm

EDIT: Shifts in JS are 32bit only http://ecma-international.org/ecma-262/5.1/#sec-11.7.1

[takahirox]

Why lazy generation isn't good?

Or better lets make it lazy but still update it to be faster

This's what I mentioned

[mrdoob]

Just adding here @kchapelier optimisation...

function () {

	var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'.split( '' );
	var uuid = new Array( 31 );
	var rnd = 0, r;

	return function generateUUID() {

		for ( var i = 0; i < 31; i ++ ) {
			if ( rnd <= 0x02 ) rnd = 0x2000000 + ( Math.random() * 0x1000000 ) | 0;
			r = rnd & 0xf;
			rnd = rnd >> 4;
			uuid[ i ] = chars[ ( i === 15 ) ? ( r & 0x3 ) | 0x8 : r ];
		}

		return uuid.join( '' );

	};

}()