Is there a way to order types quickly in Go?

I have a package which has to order Go types, quickly.

Currently I use reflect.Types, get their name with Name(), and order the names as strings:

if type1.Name() < type2.Name() { ...

However, it uses a string comparison. It works, but I am looking for a more quick solution.

How exactly this comparison works, is not an important thing to me - only what I need,

1. the result of the comparison should be same in the life of process.
2. it should be non-equal for different types, but equal for the same type.

Comparing the reflect.Type variables directly with < doesn't work, as this operation is not defined for reflect.Types in Go.

It would be possible to generate a hash of the type names to 64- or 128 bit integers, and then compare these integers. It is a possibility, however I am looking for a yet quicker solution.

Another possibility would be to compare the reflect.Type variables by their unsafe pointers (casted to int64), but as far I know, there is no guarantee in Go that the unsafe pointer addresses won't change in the life cycle of the process. Thus, I would lose my (1) requirement.

Using Type.Name() is bad

Using Type.Name() for comparison is a really bad idea as there are many anonymous types where Type.Name() returns the empty string such as []int, *int etc. Also the name returned by Type.Name() does not include the package name, so for example names of time.Time and foo.Time will be "Time" and therefore considered equal. No more is needed to be said. Check out https://stackoverflow.com/questions/36310538/identify-non-builtin-types-using-reflect/37292523#37292523 for more details.

With an internal registry

An easy and fast way would be to assign a single integer (e.g. an int value) to all types that need to be compared, and then you don't need any string comparison nor hashing, just compare the assigned int values.

Only question left is how to assign and remember these int values. The assigned values may simply be continuous values, starting with 1, then 2, 3 etc. This assignment and lookup may be automatic (hidden from our eyes).

Essentially we want a function something like this:

// Compare compares 2 types, returns a negative number
// if t1 < t2, a positive number if t1 > t2, and 0 otherwise.
func Compare(t1, t2 reflect.Type) int {
}

And the implementation is very simple / compact:

var (
	registry = map[reflect.Type]int{}
	max      int
)

func value(t reflect.Type) int {
	v := registry[t]
	if v == 0 {
		max++
		v, registry[t] = max, max
	}
	return v
}

// Compare compares 2 types, returns a negative number
// if t1 < t2, a positive number if t1 > t2, and 0 otherwise.
func Compare(t1, t2 reflect.Type) int {
	v1, v2 := value(t1), value(t2)
	return v1 - v2
}

Testing it:

tstring := reflect.TypeOf("")
tint := reflect.TypeOf(int(1))
ttime := reflect.TypeOf(time.Time{})

fmt.Println(Compare(tstring, tstring)) // 0
fmt.Println(Compare(tint, ttime))      // -1, tint gets registered first
fmt.Println(Compare(ttime, tint))      // 1
fmt.Println(Compare(tint, tint))       // 0
fmt.Println(Compare(tstring, ttime))   // -2
fmt.Println(Compare(ttime, tstring))   // 2

Output (try it on the Go Playground):

0
-1
1
0
-2
2

Making it safe for concurrent use

One weakness though: the implementation is not safe for concurrent use (by multiple goroutines). If we need safety for concurrent use, access to the registry map (and to the max variable) must be synchronized:

var mu sync.RWMutex

func value(t reflect.Type) int {
    mu.RLock()
    v := registry[t]
    mu.RUnlock()
    if v == 0 {
        mu.Lock()
        max++
        v, registry[t] = max, max
        mu.Unlock()
    }
    return v
}

The rest is unchanged. The output is the same. Try this one on the Go Playground.

Under the hood (looking closer)

Now this Compare() implies using a lock under the hood. Also in order to get the assigned integer value of a type, we have to index a map. The type of the key in this map is reflect.Type which is an interface type. Current implementation of reflect.Type is *reflect.rtype which is a pointer, so it is still fast enough as only a pointer is hashed and then looked for in a bucket (the builtin map is a hashmap implementation).

The fastest solution (getting rid of locks and map indexing)

Now this Compare() implies using a lock under the hood (and indexing a map), so that may still be an unacceptable "burden" if you really seek the fastest solution. You can easily get rid of using those all the time when comparison is needed if you acquire the internal int value assigned for the type, and use that, even directly to compare to another type's value.

For this, all you need to do is "publish" (export) the value() function:

func Value(t reflect.Type) int {
    // ...
}

And Compare() may even be removed. So libraries that need this kind of type comparison can query the integer value assigned to a type, and they can "cache" this value to avoid having to call it again (as it won't change during the lifetime of a process), and it can be compared to other values obtained by this Value() function.

For example:

vstring := Value(reflect.TypeOf(""))
vint := Value(reflect.TypeOf(int(1)))
vtime := Value(reflect.TypeOf(time.Time{}))

fmt.Println(vstring - vstring) // 0
fmt.Println(vint - vtime)      // -1, tint gets registered first
fmt.Println(vtime - vint)      // 1
fmt.Println(vint - vint)       // 0
fmt.Println(vstring - vtime)   // -2
fmt.Println(vtime - vstring)   // 2

Try this one on the Go Playground.