suyash / ulid Goto Github PK

View Code? Open in Web Editor NEW

94.0 6.0 22.0 278 KB

ulids in C++, Header Only

Home Page: https://suy.io/ulid/

License: MIT License

C++ 97.79% Starlark 2.21%

ulid header-only

ulid's Introduction

ulid

C++ port of oklog/ulid and alizain/ulid.

There are 2 implementations, the first in ulid_uint128.hh uses a __uint128_t to represent a ULID.

The second in ulid_struct.hh encapsulates a 16 byte array in a struct, and uses that to represent a ULID

ulid.hh essentially (tries to) see if __uint128_t exists, in which case it imports the definition in ulid_uint128.hh, otherwise it imports the implementation in ulid_struct.hh.

The __uint128_t version seems to be faster, some benchmarks below and more extensive ones on travis.

Usage
API
Benchmarks

Usage

#include <ulid.hh>

...

ulid::ULID ulid = ulid::Create(1484581420, []() { return 4; });
std::string str = ulid::Marshal(ulid);
std::cout << str << '\n'; // 0001C7STHC0G2081040G208104

API

ulid::ULID

The wrapper type for a __uint128_t / 16 byte array representing a ULID.

void ulid::EncodeTime(time_t, ULID&)

encodes passed time in first 6 bytes of a ULID.

void ulid::EncodeTimeNow(ULID&)

encodes std::time(nullptr) as time.

void ulid::EncodeTimeSystemClockNow(ULID&)

encodes std::chrono::system_clock::now() by taking the timestamp in milliseconds.

void ulid::EncodeEntropy(const std::function<uint8_t()>&, ULID&)

sets the last 10 bytes as the values generated using the passed random byte generator.

void ulid::EncodeEntropyRand(ULID&)

sets the entropy using std::rand.

void ulid::EncodeEntropyMt19937(std::mt19937& generator, ULID& ulid)

sets the entropy by generating values from a std::mt19937 generator, initializes a std::uniform_int_distribution on each invocation.

void ulid::Encode(time_t, const std::function<uint8_t()>&, ULID&)

EncodeTime + EncodeEntropy

void ulid::EncodeNowRand(time_t, const std::function<uint8_t()>&, ULID&)

EncodeTimeNow + EncodeEntropyRand

ulid::ULID ulid::Create(time_t, const std::function<uint8_t()>&)

creates a fresh ULID using the passed timestamp and generator.

void ulid::CreateNowRand()

Create:Encode::CreateNowRand:EncodeNowRand

void ulid::MarshalTo(const ULID&, char[26])

Marshals the ulid into the passed character array.

std::string ulid::Marshal(const ULID&)

Marshals and generates std::string.

void ulid::MarshalBinaryTo(const ULID&, uint8_t[16])

Marshals the ulid into the passed byte array.

std::vector<uint8_t> ulid::MarshalBinary(const ULID&)

Marshals and generates std::vector<uint8_t>.

void ulid::UnmarshalFrom(const char[26], ULID&)

Unmarshals the passed character array into the ulid.

ULID ulid::Unmarshal(const std::string&)

Creates a new ULID by Unmarshaling the passed string.

void ulid::UnmarshalBinaryFrom(const uint8_t[26], ULID&)

Unmarshals the passed byte array into the ulid.

ULID ulid::UnmarshalBinary(const std::vector<uint8_t>&)

Creates a new ULID by Unmarshaling the passed vector.

time_t ulid::Time(const ULID&)

Extracts the timestamp used to create the ULID.

Benchmarks

Ubuntu Xenial (16.04), clang++-8

From https://travis-ci.org/suyash/ulid/jobs/475187043

ulid_uint128

./ulid_uint128_bench.out --benchmark_out_format=console
2019-01-04 07:11:24
Running ./ulid_uint128_bench.out
Run on (2 X 2500 MHz CPU s)
CPU Caches:
  L1 Data 32K (x1)
  L1 Instruction 32K (x1)
  L2 Unified 256K (x1)
  L3 Unified 30720K (x1)
Load Average: 0.98, 0.51, 0.21
--------------------------------------------------------------------
Benchmark                         Time             CPU   Iterations
--------------------------------------------------------------------
EncodeTime                     23.2 ns         23.2 ns     30323833
EncodeTimeNow                  26.8 ns         26.7 ns     25925285
EncodeTimeSystemClockNow       96.4 ns         96.4 ns      7366207
EncodeEntropy                   209 ns          209 ns      3363959
EncodeEntropyRand               100 ns          100 ns      6875073
EncodeEntropyMt19937            470 ns          469 ns      1481254
Encode                          231 ns          231 ns      3022655
EncodeNowRand                   128 ns          128 ns      5346738
Create                          238 ns          238 ns      2970710
CreateNowRand                   133 ns          133 ns      5384520
MarshalTo                      37.5 ns         37.5 ns     18655071
Marshal                        83.7 ns         83.7 ns      8261322
MarshalBinaryTo                16.7 ns         16.7 ns     41790384
MarshalBinary                   157 ns          157 ns      4464307
UnmarshalFrom                  64.0 ns         63.9 ns     10822292
Unmarshal                       113 ns          113 ns      6146163
UnmarshalBinaryFrom            64.8 ns         64.8 ns     10942429
UnmarshalBinary                 248 ns          248 ns      2832217
Time                           15.0 ns         15.0 ns     46389021
CompareULIDs                   8.44 ns         8.44 ns     83106152

ulid_struct

./ulid_struct_bench.out --benchmark_out_format=console
2019-01-04 07:11:43
Running ./ulid_struct_bench.out
Run on (2 X 2500 MHz CPU s)
CPU Caches:
  L1 Data 32K (x1)
  L1 Instruction 32K (x1)
  L2 Unified 256K (x1)
  L3 Unified 30720K (x1)
Load Average: 0.99, 0.54, 0.22
--------------------------------------------------------------------
Benchmark                         Time             CPU   Iterations
--------------------------------------------------------------------
EncodeTime                     9.14 ns         9.13 ns     76851483
EncodeTimeNow                  12.6 ns         12.6 ns     55315496
EncodeTimeSystemClockNow       73.5 ns         73.5 ns      9515669
EncodeEntropy                   201 ns          201 ns      3480980
EncodeEntropyRand               196 ns          195 ns      3602452
EncodeEntropyMt19937            449 ns          449 ns      1560469
Encode                          211 ns          211 ns      3352107
EncodeNowRand                   204 ns          204 ns      3493016
Create                          217 ns          217 ns      3214903
CreateNowRand                   213 ns          213 ns      3271363
MarshalTo                      34.1 ns         34.1 ns     20540465
Marshal                        80.6 ns         80.5 ns      8743422
MarshalBinaryTo                17.6 ns         17.6 ns     39780449
MarshalBinary                   154 ns          154 ns      4503322
UnmarshalFrom                  33.3 ns         33.3 ns     20997275
Unmarshal                      88.5 ns         88.4 ns      7957903
UnmarshalBinaryFrom            17.0 ns         17.0 ns     41314026
UnmarshalBinary                 198 ns          198 ns      3541637
Time                           14.9 ns         14.9 ns     46747210
CompareULIDs                   20.6 ns         20.6 ns     34150306

For a comparison across latest 3 versions of g++ and clang++ on linux and clang++ on mac, see https://travis-ci.org/suyash/ulid/builds/475187039

Hacking

The library uses googletest for tests and benchmark as benchmarks, which are built as submodules. In order to get those dependencies, clone recursively, i.e.

git clone -r https://github.com/suyash/ulid

ulid's People

Contributors

Stargazers

Watchers

ulid's Issues

Timestamp is in seconds instead of ms for several API calls, also broken on 32 bit systems

Problem Description

Per the ULID spec, the timestamp portion of the ULID is supposed to be the Unix epoch time in ms. The current implementation has several API calls that encode the time in seconds, not milliseconds. time_t stores the time in seconds, and the following calls use it:

void EncodeTime(time_t timestamp, ULID& ulid)
void EncodeTimeNow(ULID& ulid)
void Encode(time_t timestamp, const std::function<uint8_t()>& rng, ULID& ulid)
void EncodeNowRand(ULID& ulid)
ULID Create(time_t timestamp, const std::function<uint8_t()>& rng)
ULID CreateNowRand()

The exception to this is EncodeTimeSystemClockNow, which properly encodes ms timestamps.

The second problem around this is that time_t is only 4 bytes on 32 bit systems (noted in #9), so a call to time_t Time(const ULID& ulid) on those systems will not work correctly past a certain time.

Potential Fix

I think we should internally fix the API so that it encodes in ms, and ensure that the API only allows encoding the time as ms (using chrony data types can enforce this). We also shouldn't use time_t as a data type when we need 8 bytes of space to do operations.

Randomness Component is Broken in Struct Header

Issue Description

As mentioned in b93d569#r43494808, the changes to EncodeEntropyRand in #7 cause the random component to be 0 when the function is called on a ulid. The problem occurs with how casting is happening here:

inline void EncodeEntropyRand(ULID& ulid) {
	ulid.data[6] = (uint8_t)(std::rand() * 255ull) / RAND_MAX;

In C++ order of operations, a c style cast happens before multiplication or division. That means this expression is resolved:

 (std::rand() * 255ull)

then cast as a uint8_t before the division by RAND_MAX occurs. Thus, you end up with a number always less than 0 (since a unint8_t can only hold up to 255, and RAND_MAX (on 32 bit platforms) is 2147483647).

Fix

A fix was proposed in #9. However, I think that only capturing the last 0xFF part of the output of rand() may be suboptimal (see std::rand() notes here).

Another fix would be to force the correct order of operations and cast the entire expression. I've tested that this is working.

_MSC_VER macro is specific to IDE

Using this library in a linux application, compiled with g++:

/home/xxxx/percona-server-8.0.32-24/plugin/ulid/ulid/src/ulid_uint128.hh:11:5: warning: "_MSC_VER" is not defined, evaluates to 0 [-Wundef]
 #if _MSC_VER > 0
     ^~~~~~~~

A quick google says _MSC_VER is something specific to Visual Studio Code. Please add an #ifdef before checking the value so that other IDEs/compilers don't complain.

Monotonic sort order

Could you clarify please is there monotonic sort order implemented?

using namespace std;

map<string, bool> values;

mt19937 rng;
rng.seed(random_device()());
uniform_int_distribution<mt19937::result_type> dist(1, 100000);

for (auto i = 0; i < 10; ++i) {
    auto msec   = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
//        auto sec    = chrono::duration_cast<chrono::seconds>(chrono::system_clock::now().time_since_epoch()).count();

    auto ulid = ulid::Create(msec, [&]() {
        return dist(rng);
    });

    auto marshal = ulid::Marshal(ulid);
    cout << "ULID: " << marshal << " TIME:" << msec << endl;
    values.insert(pair<string, bool> (marshal, true));
}

cout << endl;

for (auto it = values.begin(); it != values.end(); ++it) {
    cout << (*it).first << endl;
}

As result:

ULID: 01F0Q46HRRM8TN2DYE2QAYFBCV TIME:1615683864344
ULID: 01F0Q46HRRHEHPZY95X06GF250 TIME:1615683864344
ULID: 01F0Q46HRRD7QSH5481ED4NJDV TIME:1615683864344
ULID: 01F0Q46HRRE4QDCAK58JQJA1CF TIME:1615683864344
ULID: 01F0Q46HRRDTW2XXMN28B54888 TIME:1615683864344
ULID: 01F0Q46HRRC0QVB15CHGRB8DVS TIME:1615683864344
ULID: 01F0Q46HRR6WJFE1YM6BEB8XNZ TIME:1615683864344
ULID: 01F0Q46HRR8J4MS9DYW2F7QKBD TIME:1615683864344
ULID: 01F0Q46HRRNMS141PFKDGA2TY6 TIME:1615683864344
ULID: 01F0Q46HRR9P6D9ZZYJCV5MX9E TIME:1615683864344

01F0Q46HRR6WJFE1YM6BEB8XNZ
01F0Q46HRR8J4MS9DYW2F7QKBD
01F0Q46HRR9P6D9ZZYJCV5MX9E
01F0Q46HRRC0QVB15CHGRB8DVS
01F0Q46HRRD7QSH5481ED4NJDV
01F0Q46HRRDTW2XXMN28B54888
01F0Q46HRRE4QDCAK58JQJA1CF
01F0Q46HRRHEHPZY95X06GF250
01F0Q46HRRM8TN2DYE2QAYFBCV
01F0Q46HRRNMS141PFKDGA2TY6

You can see that the selected value is not in the same order as it should be. I understand that map-container keeps values sorted and they are not even in reverse order. As we can see their time is the same.
I also compared how it works in PHP (https://github.com/rorecek/laravel-ulid and https://github.com/ulid/javascript).
Here is console output:


>>> $values = [];
=> []
>>> for($i = 0; $i < 10; ++$i) { $ulid = ulid(); $values[] = $ulid; echo $ulid . PHP_EOL;}
01F0Q59G42ZHN51J4AYR6F2XHV
01F0Q59G43CKCHAPCFWRXQEJHX
01F0Q59G44D1QHZGS9ZSZGQ78H
01F0Q59G45AG3KXAZMZ5JQ9B30
01F0Q59G46ZZZ616T9YE2TQ2E8
01F0Q59G47XB98SAJETRMG659C
01F0Q59G48MZXWAXK4APFQG90A
01F0Q59G49CFSP07JXWQ9ADF1E
01F0Q59G4AVC3D99EFCG7SYGA0
01F0Q59G4BHDJY7W2HERNG7EGB
>>> asort($values);
=> true
>>> print_r($values);
Array
(
    [0] => 01F0Q59G42ZHN51J4AYR6F2XHV
    [1] => 01F0Q59G43CKCHAPCFWRXQEJHX
    [2] => 01F0Q59G44D1QHZGS9ZSZGQ78H
    [3] => 01F0Q59G45AG3KXAZMZ5JQ9B30
    [4] => 01F0Q59G46ZZZ616T9YE2TQ2E8
    [5] => 01F0Q59G47XB98SAJETRMG659C
    [6] => 01F0Q59G48MZXWAXK4APFQG90A
    [7] => 01F0Q59G49CFSP07JXWQ9ADF1E
    [8] => 01F0Q59G4AVC3D99EFCG7SYGA0
    [9] => 01F0Q59G4BHDJY7W2HERNG7EGB
)

As you can see after the sorting we have the same order as it was in loop during generation.
Sorry if I maybe misunderstood how to use this lib. Is there a way to get that monotonic sort order (Ulid spec https://github.com/ulid/spec)?