golang sort.Slice - limits of 'int' in function signature

December 1st at 8:51am

I had an idle question earlier today: can golang support sorting a slice with more than 2,147,483,647 or 4,294,967,295 entries (signed 32bit and unsigned 32bit max values)? Looking at the documentation for sort.Slice it specifies a comparator function with this signature: func(i, j int) bool which got me thinking about what int can represent in golang. int is signed, so is there a way to sort through a slice with a hypothetically enormous number of entries?

References

Results

Testing can be found below. The end result is that int is platform dependent in golang and is 64bit on platforms which are natively 64bit. This can be verified by compiling / running something like this:

    var integer int
    log.Println("Size of int on this platform (8==64bit signed, 4==32bit signed):", reflect.TypeOf(integer).Size())

For practical purposes, having sort.Slice use int in the comparator function signature is not a real limitation on current hardware for most current workloads. If your underlying hardware is 64 bit sort.Slice can handle a slice with up to 9,223,372,036,854,775,807 entries.

Test 1

I set about to write a sample application that would help me visualize the behavior of sort.Slice when the slice to be sorted contains a large number of entries. This is what my initial attempt produced:

func main() {
    // Setup a slice larger than a uint32
    var count uint64
    count = 4294968000      // Fill this up so it's bigger than a uint32
    var exp []uint64
    for{
        if count <= 0{ // Done loading the slice
            break
        }
        if count == 2147483644{
            log.Println("Crossed the int32 threshold.")
        }
        exp = append(exp, 1)
        count--
    }

    // Try to sort a slice larger than uint32
    sort.Slice(exp, func(i, j int) bool{
        if i > 4294967990 || j > 4294967990{
            log.Println("Sorting an index above uint32. i=", i, " - j=", j)
        }
        return exp[i] > exp[j]
    })

    log.Println("Finished?")
}

Unfortunately, I didn't seem to be getting what I expected: The program was Killed

Test 2

With a couple modifications I made it easier to track program execution. Bonus that this one wasn't killed ;)

Key changes:

  • Progress indicator
  • Changed the type of my test slice to a uint8 instead of using uint64 to reduce overall memory usage
func main() {
    var integer int
    log.Println("Size of int on this platform (8==64bit signed, 4==32bit signed):", reflect.TypeOf(integer).Size())

    // Setup a slice larger than a uint32
    var count uint64
    count = 4294968000      // Fill this up so it's bigger than a uint32
    var exp []uint8
    log.Println("Count Start:", count)
    for{
        if count % 10000000 == 0 {
            fmt.Print(".")
        }
        if count <= 0{
            break
        }
        if count == 2147483644{
            log.Println("Crossed the int32 threshold!")
        }
        exp = append(exp, 1)
        count--
    }
    log.Println("Length of slice:", len(exp))

    // Try to sort a slice larger than uint32
    log.Println("Sorting...")
    sort.Slice(exp, func(i, j int) bool{
        if i > 4294967990 || j > 4294967990{
            log.Println("Above uint32!! i=", i, " - j=", j)
        }
        return exp[i] > exp[j]
    })
    log.Println("Sorting finished")

    log.Println("Finished?")
}

Program output:

$ ./uint64-test 
2020/11/30 19:37:35 Count Start: 4294968000
.......................................................................................................................................................................................................................
2020/11/30 19:37:41 Crossed the int32 threshold!
.......................................................................................................................................................................................................................
2020/11/30 19:37:47 Count End: 0
2020/11/30 19:37:47 Length of slice: 4294968000
2020/11/30 19:37:47 Sorting...
2020/11/30 19:37:47 Above uint32!! i= 4294967999  - j= 3758096999
2020/11/30 19:37:47 Above uint32!! i= 3221225999  - j= 4294967999
2020/11/30 19:37:47 Above uint32!! i= 4294967999  - j= 0
2020/11/30 19:38:05 Above uint32!! i= 0  - j= 4294967995
2020/11/30 19:38:05 Above uint32!! i= 0  - j= 4294967996
2020/11/30 19:38:05 Above uint32!! i= 0  - j= 4294967997
2020/11/30 19:38:05 Above uint32!! i= 0  - j= 4294967998
2020/11/30 19:38:05 Above uint32!! i= 4294967998  - j= 0
2020/11/30 19:38:05 Above uint32!! i= 4294967991  - j= 0
2020/11/30 19:38:24 Sorting finished
2020/11/30 19:38:24 Finished?