big bug: not sortable

[ABOB9]

var list = make([]string, 0)
var busy = make(chan bool, 1)

func AddXidToList(i string) {
busy <- true
id := xid.New()
list = append(list, id.String()+" "+i)
<-busy
}

func Test_test6(t *testing.T) {
wg := sync.WaitGroup{}
wg.Add(2)
go func() {
for i := 0; i < 1000000; i++ {
AddXidToList("1")
}
wg.Done()
}()
go func() {
for i := 0; i < 1000000; i++ {
AddXidToList("2")
}
wg.Done()
}()
wg.Wait()
for i := 0; i < len(list); i++ {
if i+1 < len(list) && list[i] > list[i+1] {
//1820049 cdiebmnlt656j2nvvvvg 2 cdiebmnlt656j2g00000 1
fmt.Println(i, list[i], list[i+1])
t.Error("big bug")
}
}
if list[len(list)-2] > list[len(list)-1] {
t.Error("big bug2")
fmt.Println(list[len(list)-2], list[len(list)-1])
}
fmt.Println("END")
}
func Test_test7(t *testing.T) {
i := 0
for {
i++
Test_test6(t)
if i == 10 {
break
}
}
}

run the method Test_test7, it print following:
1969577 cdj6vqvlt652mmnvvvvg 1 cdj6vqvlt652mmg00000 1
id_test.go:177: big bug

[chedom]

@ABOB9 i have detected the same issue:

func Test_Counter(t *testing.T) {
	prev := xid.New()

	for i := 0; i < 122992080; i++ {
		cur := xid.New()

		if prev.String() > cur.String() {
			fmt.Println(prev.String(), cur.String())

			fmt.Printf("previous: time: %s, pid: %d, counter: %d\n", prev.Time(), prev.Pid(), prev.Counter())
			fmt.Printf("current: time: %s, pid: %d, counter: %d\n", cur.Time(), cur.Pid(), cur.Counter())
			break
		}

		prev = cur
	}
}

The output will be the next (the part that is responsible for time will be changed every execution):

cge7lre9ldlvinfvvvvg cge7lre9ldlvin800000
previous: time: 2023-03-23 18:14:37 +0200 EET, pid: 63837, counter: 16777215
current: time: 2023-03-23 18:14:37 +0200 EET, pid: 63837, counter: 0

The reason is objectIDCounter, the last 3 bytes of the ID.
Here is how the objectIDCounter is incorporated in the ID

// Increment, 3 bytes, big endian
i := atomic.AddUint32(&objectIDCounter, 1)
id[9] = byte(i >> 16)
id[10] = byte(i >> 8)
id[11] = byte(i)

After objectIDCounter 16777216 the last 3 bytes of the ID will be reseted:

func Test_ObjectCounter(t *testing.T) {
	vals := []uint32{16777215, 16777216, 16777217}

	for _, v := range vals {
		var id [3]byte

		id[0] = byte(v >> 16)
		id[1] = byte(v >> 8)
		id[2] = byte(v)

		fmt.Println(">>>", id)
	}
}

The output will be the next:

>>> [255 255 255]
>>> [0 0 0]
>>> [0 0 1]

Summary:
If two calls of the xid.New occur during the same second (xid include 4 bytes of the timestamp (include seconds)) and the objectIDCounter is 16777216 during the first call, the second ID will be smaller.

Update:

K-ordered is specified in a list of features, that's why it's definitely is not a bug.