Support for alternative ID generation methods

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, …)

Author: Fantashit

7 thoughts on “Support for alternative ID generation methods

  1. 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…

  2. 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;
    		}
    	}
    } );
  3. So, let me share my optimization (including @kchapelier approach) here

    var _Math = {
    
    	generateUUID: function () {
    
    		// http://www.broofa.com/Tools/Math.uuid.htm
    
    		var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'.split( '' );
    		var uuid = new Array( 36 );
    		var rnd = 0, r;
    
    		return function generateUUID() {
    
    			for ( var i = 0; i < 36; i ++ ) {
    
    				if ( i === 8 || i === 13 || i === 18 || i === 23 ) {
    
    					uuid[ i ] = '-';
    
    				} else if ( i === 14 ) {
    
    					uuid[ i ] = '4';
    
    				} else {
    
    					if ( rnd <= 0x02 ) rnd = 0x2000000 + ( Math.random() * 0x1000000 ) | 0;
    					r = rnd & 0xf;
    					rnd = rnd >> 4;
    					uuid[ i ] = chars[ ( i === 19 ) ? ( r & 0x3 ) | 0x8 : r ];
    
    				}
    
    			}
    
    			return uuid.join( '' );
    
    		};
    
    	}(),
    
    	generateUUID2: function () {
    
    		// Replace .join with string concatenation
    
    		var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'.split( '' );
    		var rnd = 0, r;
    
    		return function generateUUID2() {
    
    			var uuid = '';
    
    			for ( var i = 0; i < 36; i ++ ) {
    
    				if ( i === 8 || i === 13 || i === 18 || i === 23 ) {
    
    					uuid += '-';
    
    				} else if ( i === 14 ) {
    
    					uuid += '4';
    
    				} else {
    
    					if ( rnd <= 0x02 ) rnd = 0x2000000 + ( Math.random() * 0x1000000 ) | 0;
    					r = rnd & 0xf;
    					rnd = rnd >> 4;
    					uuid += chars[ ( i === 19 ) ? ( r & 0x3 ) | 0x8 : r ];
    
    				}
    
    			}
    
    			return uuid;
    
    		};
    
    	}(),
    
    	generateUUID3: function () {
    
    		// String concatenation each 2 characters
    
    		var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'.split( '' );
    		var rnd = 0, r;
    
    		var table = [];
    
    		for ( var i = 0; i < 256; i ++ ) {
    
    			table[ i ] = chars[ i >> 4 ] + chars[ i & 0xF ];
    
    		}
    
    		var flags = [
    			false, true, false, true,
    			false, true, false, true,
    			false,
    			false, true, false, true,
    			false,
    			false, true, false, true,
    			false,
    			false, true, false, true,
    			false,
    			false, true, false, true,
    			false, true, false, true,
    			false, true, false, true
    		];
    
    		return function generateUUID3() {
    
    			var uuid = '';
    			var tmp = 0;
    			var value = 0;
    
    			for ( var i = 0; i < 36; i ++ ) {
    
    				if ( i === 8 || i === 13 || i === 18 || i === 23 ) {
    
    					uuid += '-';
    
    				} else if ( i === 14 ) {
    
    					tmp = 4;
    
    				} else {
    
    					if ( rnd <= 0x02 ) rnd = 0x2000000 + ( Math.random() * 0x1000000 ) | 0;
    					r = rnd & 0xf;
    					rnd = rnd >> 4;
    
    					value = ( i === 19 ) ? ( r & 0x3 ) | 0x8 : r;
    
    					if ( flags[ i ] === true ) {
    
    						uuid += table[ ( tmp << 4 ) | value ];
    
    					} else {
    
    						tmp = value;
    
    					}
    
    				}
    
    			}
    
    			return uuid;
    
    		};
    
    	}(),
    
    	generateUUID4: function () {
    
    		// String concatenation each 2 characters including '-'
    
    		var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'.split( '' );
    		var rnd = 0, r;
    
    		var table = [];
    
    		for ( var i = 0; i < 289; i ++ ) {
    
    			var index1 = ( i / 17 ) | 0;
    			var index2 = i %% 17;
    			var c1 = index1 === 16 ? '-' : chars[ index1 ];
    			var c2 = index2 === 16 ? '-' : chars[ index2 ];
    			table[ i ] = c1 + c2;
    
    		}
    
    		return function generateUUID4() {
    
    			var uuid = '';
    			var tmp = 0;
    			var value = 0;
    
    			for ( var i = 0; i < 36; i ++ ) {
    
    				if ( i === 8 || i === 13 || i === 18 || i === 23 ) {
    
    					value = 16;
    
    				} else if ( i === 14 ) {
    
    					value = 4;
    
    				} else {
    
    					if ( rnd <= 0x02 ) rnd = 0x2000000 + ( Math.random() * 0x1000000 ) | 0;
    					r = rnd & 0xf;
    					rnd = rnd >> 4;
    
    					value = ( i === 19 ) ? ( r & 0x3 ) | 0x8 : r;
    
    				}
    
    				if ( ( i %% 2 ) === 0 ) {
    
    					tmp = value;
    
    				} else {
    
    					uuid += table[ ( tmp * 17 ) + value ];
    
    				}
    
    			}
    
    			return uuid;
    
    		};
    
    	}(),
    
    	generateUUID5: function () {
    
    		// Remove hardcode characters (@kchapelier 's idea)
    
    		var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'.split( '' );
    		var uuid = new Array( 31 );
    		var rnd = 0, r;
    
    		return function generateUUID5 () {
    
    			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( '' );
    
    		};
    
    	}(),
    
    	generateUUID6: function () {
    
    		// Remove hardcode characters from generateUUID4
    
    		var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'.split( '' );
    		var rnd = 0, r;
    
    		var table = [];
    
    		for ( var i = 0; i < 256; i ++ ) {
    
    			table[ i ] = chars[ i >> 4 ] + chars[ i & 0xF ];
    
    		}
    
    		return function generateUUID6() {
    
    			var uuid = '';
    			var tmp = 0;
    			var value = 0;
    
    			for ( var i = 0; i < 31; i ++ ) {
    
    				if ( rnd <= 0x02 ) rnd = 0x2000000 + ( Math.random() * 0x1000000 ) | 0;
    				r = rnd & 0xf;
    				rnd = rnd >> 4;
    				value = ( i === 15 ) ? ( r & 0x3 ) | 0x8 : r;
    
    				if ( ( i %% 2 ) === 0 ) {
    
    					tmp = value;
    
    				} else {
    
    					uuid += table[ ( tmp << 4 ) | value ];
    
    				}
    
    			}
    
    			uuid += chars[ tmp ];
    
    			return uuid;
    
    		};
    
    	}()
    
    };
    
    function run( func ) {
    
    	var loop = 0x100000;
    
    	var startTime = performance.now();
    
    	for ( var i = 0; i < loop; i ++ ) {
    
    		func();
    
    	}
    
    	var endTime = performance.now();
    
    	console.log( ( endTime - startTime ).toFixed( 2 ) + 'ms, loop=' + loop );
    
    }
    
    run(_Math.generateUUID);
    run(_Math.generateUUID);
    run(_Math.generateUUID2);
    run(_Math.generateUUID2);
    run(_Math.generateUUID3);
    run(_Math.generateUUID3);
    run(_Math.generateUUID4);
    run(_Math.generateUUID4);
    run(_Math.generateUUID5);
    run(_Math.generateUUID5);
    run(_Math.generateUUID6);
    run(_Math.generateUUID6);

    I don’t change the randomness.

    On my Windows10 + Chrome, generateUUID4 optimization makes 3x faster.
    But just 1.12x improvement on my FireFox Nightly.

    I’ll explain more detail later.
    I just woke up now and it’s breakfast time!

  4. That looks good. I’d say it’d be more optimized and readable generateUUID4().

    It’s 2.3x faster than generateUUID2() (current Math.generateUUID) on my both Chrome and FireFox nightly.

  5. You can add .toUpperCase() here to get upper-case uuids.

    var lut = []; for (var i=0; i<256; i++) { lut[i] = (i<16?'0':'')+(i).toString(16).toUpperCase(); }
    
  6. On my system…

    Function Chrome Mac Firefox Mac Safari
    generateUUID (r87) 1134.28ms 1292.97ms 774.10ms
    generateUUID2 (r88) 691.54ms 1568.22ms 464.10ms
    generateUUID7 (dev)  220.39ms 820.51ms 181.80ms

Comments are closed.