Deno.KV - Modernized TypeScript randomULID() Generator - Smaller and Optimized

[suchislife801]

Modernized Javascript randomULID() Generator - Smaller and Optimized

[lino-levan]

ulid has been added to the standard library. If you have a rewrite that is better than that implementation we'd love to take a look!

[lino-levan]

What is the advantage of this implementation over the one in https://deno.land/std/ulid ? I feel like I am misunderstanding. Is it faster? I'd love to get a benchmark there.

[iuioiua]

The ULID implementation in the Standard Library is up to 58% faster and easier to understand.

Script:

import { ulid } from "https://deno.land/std@0.202.0/ulid/mod.ts";

Deno.bench("ulid()", { baseline: true }, () => { ulid() });
Deno.bench("randomULID()", () => { randomULID() })

Results (consistent with other runs):

cpu: Apple M2
runtime: deno 1.37.0 (aarch64-apple-darwin)

file:///Users/asher/Desktop/x.ts
benchmark         time (avg)        iter/s             (min … max)       p75       p99      p995
------------------------------------------------------------------ -----------------------------
ulid()           783.36 ns/iter   1,276,552.5 (745.37 ns … 837.99 ns) 786.48 ns 837.99 ns 837.99 ns
randomULID()       1.24 µs/iter     808,566.3     (1.21 µs … 1.28 µs)   1.24 µs   1.28 µs   1.28 µs

summary
  ulid()
   1.58x faster than randomULID()

However, once you remove BigInts, just using numbers, randomULID() becomes 28% faster than the Standard Library implementation. Why are BigInts used instead of numbers?

Results (consistent with other runs and swapping baseline benchmarks):

cpu: Apple M2
runtime: deno 1.37.0 (aarch64-apple-darwin)

file:///Users/asher/Desktop/x.ts
benchmark         time (avg)        iter/s             (min … max)       p75       p99      p995
------------------------------------------------------------------ -----------------------------
ulid()           783.25 ns/iter   1,276,730.8 (755.51 ns … 841.45 ns) 788.45 ns 841.45 ns 841.45 ns
randomULID()     611.92 ns/iter   1,634,208.4  (517.4 ns … 662.48 ns) 625.33 ns 662.48 ns 662.48 ns

summary
  randomULID()
   1.28x faster than ulid()

Really, the Standard Library implementation is still bloody quick. I can't see it being a bottleneck and, therefore, needing further performance optimisation. Either way, it'd be best to submit a PR to https://github.com/denoland/deno_std with these ULID tweaks, and we can go from there. This issue should be moved there too. While related to Deno KV, the ULID implementation lives there 🙂

[kt3k]

@suchislife801 We significantly reduced the API surface when adopting ULID to deno_std. See https://github.com/denoland/deno_std/pull/3582

Our version is much simpler than the reference implementation at https://github.com/ulid/javascript

Also we use crypto.getRandomValues() by default, and doesn't allow replacement. Cryptographic concern shouldn't apply to our implementation https://github.com/denoland/deno_std/blob/28840333898d71aaca58c44ef43506dfbde85157/ulid/_util.ts#L34

[lino-levan]

The issue with not using the factory function in the case of us having a factory function is that we need to test the implementation. It's pretty hard to test with stubbing the randomness of the implementation. If you could show a proper way to test your proposed implementation that was simpler I'd love to take a look.

[lino-levan]

Let's try to be respectful here. When I'm talking about testing, I am referring to unit testing. The code you posted, while cool, is definitely closer to "fuzzing" than "testing". Properly testing things like MULID requires more than just fuzzing, unfortunately. That being said, any reasonably correct ULID implementation will essentially never get a collision, so I see the value in testing that. If you would like, you could PR your collision test file into the ulid module.

[lino-levan]

Sure, thanks for opening an issue. I'd love to chat more if you are interested.

[suchislife801]

I am interested in deleting this entire issue but that is also not possible.