I've finally finished these 2 scripts and would like to get some feedback.
- Seeking feedback on a modernized ULID (Universally Unique Lexicographically Sortable Identifier) generator in Javascript.
- Reduced size compared to examples on GitHub.
- Code includes functions for encoding BigInt as Base32, decoding timestamps, and generating ULIDs.
- Looking for code review and optimization suggestions if it isn't already compliant.
As you can see, Monotonic fills the Set almost twice as fast from sheer uniqueness.
See you later UUID?
Test Results - randomULID()
- Processor.....: Intel Xeon W-1390P @ 3.5GHz 32GB RAM
- Duration......: 2.7 sec @ 366,032/s @ 366/ms
- Iterations....: 1,000,000
- Collisions....: 0
- Set Bytes.....: 26,000,000 bytes
- Set Kilobytes.: 25,391 Kilobytes
- Set Megabytes.: 25 Megabytes
- Collision Test complete!
Test Results - randomMULID()
- Processor.....: Intel Xeon W-1390P @ 3.5GHz 32GB RAM
- Duration......: 1.9 sec @ 531,350/s @ 531/ms
- Iterations....: 1,000,000
- Collisions....: 0
- Set Bytes.....: 26,000,000 bytes
- Set Kilobytes.: 25,391 Kilobytes
- Set Megabytes.: 25 Megabytes
- Collision Test complete!
ULID.js
"use strict";
/**
* Global variables to keep track of the last generated timestamp and random value.
*/
let lastTimestamp = 0n; // Initialize a variable to store the last used timestamp.
let lastRandomValue = 0n; // Initialize a variable to store the last used random value.
/**
* Crockford's Base32 alphabet for encoding.
*/
const alphabet = "0123456789ABCDEFGHJKMNPQRSTVWXYZ";
/**
* Encodes a given BigInt number into a Base32 string.
* @param {bigint} number - The BigInt number to encode.
* @param {number} length - The length of the encoded string.
* @returns {string} The Base32 encoded string.
*/
function encodeBase32(number, length) {
// Initialize an empty string to hold the Base32 output.
let output = "";
// Loop `length` times to create the Base32 string.
for (let i = 0; i < length; i++) {
// Mask the last 5 bits of `number`, find the corresponding alphabet, and prepend to `output`.
output = alphabet[Number(number & 0x1fn)] + output;
// Right-shift `number` by 5 bits, effectively removing the bits that were just processed.
number >>= 5n;
}
// Return the Base32-encoded string.
return output;
}
/**
* Decodes the timestamp from a given ULID string.
* The function decodeTimestamp takes a ULID string ulid and returns a
* JavaScript Date object representing the timestamp encoded in the first
* 10 characters (48 bits) of the ULID.
* @param {string} ulid - The ULID string to decode.
* @returns {Date} The decoded timestamp as a JavaScript Date object.
*/
function decodeTimestamp(ulid) {
// 01HAYR6EKZ QDS8N9Y9PPBVG7EQ
// Extract the first 10 characters (48 bits) from the ULID string, representing the timestamp.
const timePart = ulid.slice(0, 10);
// Initialize a BigInt to hold the decoded timestamp.
let timestamp = 0n;
// Loop through each character in the time part of the ULID.
for (const char of timePart) {
// Left-shift `timestamp` by 5 bits and OR it with the index of `char` in the alphabet, converted to BigInt.
timestamp = (timestamp << 5n) | BigInt(alphabet.indexOf(char));
}
// Convert the BigInt timestamp to Number and return it as a JavaScript Date object.
return new Date(Number(timestamp));
}
/**
* Generates a ULID (Universally Unique Lexicographically Sortable Identifier).
* @returns {Promise<string>} A promise that resolves to a ULID string.
*
* - The function `randomULID` asynchronously generates a ULID string by
* combining a 48-bit timestamp and 80 bits of cryptographically secure
* random data. It returns a Promise that resolves to this ULID string.
*/
async function randomULID() {
// Get the current timestamp as a BigInt.
const timestamp = BigInt(Date.now());
// Create a buffer to hold 10 bytes of random data.
const randomBuffer = new Uint8Array(10);
// Populate the buffer with Web Crypto API cryptographically secure random values.
crypto.getRandomValues(randomBuffer);
// Initialize a BigInt to hold the random value.
let randomValue = 0n;
// Loop through the random buffer.
for (const byte of randomBuffer) {
// Left-shift `randomValue` by 8 bits and OR it with each byte, converted to BigInt.
randomValue = (randomValue << 8n) | BigInt(byte);
}
// Encode the timestamp using the encodeBase32 function, 10 characters long.
const timePart = encodeBase32(timestamp, 10);
// Encode the random value using the encodeBase32 function, 16 characters long.
const randomPart = encodeBase32(randomValue, 16);
// Concatenate the time and random parts to form the ULID, and return it.
return timePart + randomPart;
}
/**
* Generates a monotonic MULID (Monotonic Universally Unique Lexicographically Sortable Identifier).
* @returns {Promise<string>} A promise that resolves to a MULID string.
*
* - The function `randomMULID` asynchronously generates a "Monotonic"
* MULID string by combining a 48-bit timestamp and 80 bits of
* cryptographically secure random data. It ensures that ULIDs generated
* in the same millisecond are still unique by incrementing lastRandomValue.
* It returns a Promise that resolves to this MULID string.
*
*/
async function randomMULID() {
// Get the current timestamp as a BigInt.
const currentTimestamp = BigInt(Date.now());
// If the current timestamp equals the last used timestamp,
if (currentTimestamp === lastTimestamp) {
// Increment the last random value to ensure uniqueness.
lastRandomValue++;
} else {
// Update the last used timestamp.
lastTimestamp = currentTimestamp;
// Create a buffer to hold 10 bytes of random data.
const randomBuffer = new Uint8Array(10);
// Populate the buffer with cryptographically secure random values.
crypto.getRandomValues(randomBuffer);
// Reset the last used random value.
lastRandomValue = 0n;
// Loop through the random buffer.
for (const byte of randomBuffer) {
// Left-shift `lastRandomValue` by 8 bits and OR it with each byte, converted to BigInt.
lastRandomValue = (lastRandomValue << 8n) | BigInt(byte);
}
}
// Encode the last used timestamp using encodeBase32 function, 10 characters long.
const timePart = encodeBase32(lastTimestamp, 10);
// Encode the last used random value using encodeBase32 function, 16 characters long.
const randomPart = encodeBase32(lastRandomValue, 16);
// Concatenate the time and random parts to form the ULID, and return it.
return timePart + randomPart;
}
/**
* Performs a collision test for a given ID generator function.
*
* @async
* @param {number} _iterations - The number of iterations to perform.
* @param {() => Promise<string>} generator - The generator function for producing IDs.
* @returns {Promise<string>} A string containing various metrics and results of the test.
*/
async function collisionTest(_iterations, generator) {
const idSet = new Set();
let collisions = 0;
const start = Date.now();
for (let i = 0; i < _iterations; i++) {
const newId = await generator();
if (idSet.has(newId)) {
collisions++;
} else {
idSet.add(newId);
}
}
const end = Date.now();
// Calculate the duration of the test in milliseconds
const _durationMiliSecond = (end - start);
// Calculate the rate of ULID generation per millisecond
const _idPerMiliSecond = (_iterations / _durationMiliSecond);
// Calculate the duration of the test in seconds
const _durationSecond = ((end - start) / 1000);
// Calculate the rate of ULID generation per second
const _idPerSecond = (_iterations / _durationSecond);
// Format the duration in milliseconds to a string with 1 decimal point
const _durationMiliSecondFormatted = (_durationMiliSecond).toLocaleString('en-US', {
maximumFractionDigits: 1
});
// Format the duration in seconds to a string with 1 decimal point
const _durationSecondFormatted = (_durationSecond).toLocaleString('en-US', {
maximumFractionDigits: 1
});
// Format the rate per millisecond to a string with 0 decimal points
const _rateMiliSecondFormatted = (_idPerMiliSecond).toLocaleString('en-US', {
maximumFractionDigits: 0
});
// Format the rate per second to a string with 0 decimal points
const _ratePerSecondFormatted = (_idPerSecond).toLocaleString('en-US', {
maximumFractionDigits: 0
});
// Format the number of iterations to a string with 0 decimal points
const _iterationsFormatted = _iterations.toLocaleString('en-US', {
maximumFractionDigits: 0
});
// Define the byte length of a single ULID for use in size calculations
const ID_FIXED_BYTE_LENGTH = 26;
// Calculate the total byte length of all the ULIDs stored in the Set
const _setByteLength = idSet.size * ID_FIXED_BYTE_LENGTH;
// Format the total byte length to a string with 0 decimal points
const _setByteLengthFormatted = (_setByteLength).toLocaleString('en-US', {
maximumFractionDigits: 0
});
// Convert the total byte length to kilobytes
const _setKilobyteLength = _setByteLength / 1024;
// Format the total kilobyte length to a string with 0 decimal points
const _setKilobyteLengthFormatted = (_setKilobyteLength).toLocaleString('en-US', {
maximumFractionDigits: 0
});
// Convert the total kilobyte length to megabytes
const _setMegabyteLength = _setKilobyteLength / 1024;
// Format the total megabyte length to a string with 0 decimal points
const _setMegabyteLengthFormatted = (_setMegabyteLength).toLocaleString('en-US', {
maximumFractionDigits: 0
});
// Clear/Remove all ULIDs from this set (Free Memory)
idSet.clear();
// The return statement assembles the formatted test results.
return `
Test Results - ${generator.name}()
- Processor.....: Intel Xeon W-1390P @ 3.5GHz 32GB RAM
- Duration......: ${_durationSecondFormatted} sec @ ${_ratePerSecondFormatted}/s @ ${_rateMiliSecondFormatted}/ms
- Iterations....: ${_iterationsFormatted}
- Collisions....: ${collisions}
- Set Bytes.....: ${_setByteLengthFormatted} bytes
- Set Kilobytes.: ${_setKilobyteLengthFormatted} Kilobytes
- Set Megabytes.: ${_setMegabyteLengthFormatted} Megabytes
- Collision Test complete!`;
}
// Initialize Collision Tests
(async () => {
const ulidTestResults = await collisionTest(1000000, randomULID);
console.log(ulidTestResults);
const mulidTestResults = await collisionTest(1000000, randomMULID);
console.log(mulidTestResults);
})();
