超时未触发

Question

I implemented a few sorting algorithms in Go for fun, and now I'd like to test their performance on random integers. So I wrote the following program. I followed a similar format to: https://gobyexample.com/timeouts

However, it seems like the timeout is not firing properly. Below is my code:

package main

import (
    "allanpinkerton.com/algorithms/sorting"
    "fmt"
    "math/rand"
    "os"
    "strconv"
    "time"
)

// Prints out the time elapsed since start
func timeExecution(startTime time.Time, functionName string, inputSize int) string {
    executionTime := time.Since(startTime)
    return fmt.Sprintf("%-20s took %10.4fms to sort %d elements
", functionName, float64(executionTime.Nanoseconds())/1000000, inputSize)
}

// Generates file with n random ints named integerArray + n
func generateRandomIntegers(n int, filename string) {
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = rand.Int()
    }
    f, _ := os.Create(filename)
    defer f.Close()
    for _, num := range arr {
        f.WriteString(strconv.Itoa(num) + " ")
    }
    f.WriteString("
")
    f.Sync()
    fmt.Printf("Generated " + filename + " with " + strconv.Itoa(n) + " elements.
")
}


func checkError(err error) {
    if err != nil {
        panic(err)
    }
}

func main() {

    sortingFunctions := map[string]interface{}{
        "InsertionSort":        sorting.InsertionSort,
        "QuickSortLastElement": sorting.QuickSortLastElement,
        "QuickSortRandom":      sorting.QuickSortRandom,
    }
    if len(os.Args) != 2 {
        fmt.Printf("No size specified.
")
        return
    }
    size := os.Args[1]
    sizeInt, err := strconv.Atoi(size)
    checkError(err)

    arr := make([]int, sizeInt)
    for i := 0; i < sizeInt; i++ {
        arr[i] = rand.Int()
    }
    fmt.Println("Generated " + size + " integers.")

    mainChannel := make(chan string)
    for k, v := range sortingFunctions {
        newArr := make([]int, len(arr))
        copy(newArr, arr)
        go func(name string, v interface{}) {
            start := time.Now()
            v.(func([]int))(newArr)
            result := timeExecution(start, name, len(newArr))
            mainChannel <- result
        }(k, v)
    }

    for _ = range sortingFunctions {
        select {
        case result := <-mainChannel:
            fmt.Printf(result)
        case <-time.After(time.Second):
            fmt.Println("Timeout")
        }
    }

    return
}

The top is just a bunch of helpers, but the there's something funny going on with the main function. I ran go install and ran it against 150,000 elements, and got the response below:

Generated 150000 integers.
QuickSortLastElement took    15.0037ms to sort 150000 elements
InsertionSort        took  7599.5884ms to sort 150000 elements
QuickSortRandom      took    15.1697ms to sort 150000 elements

Clearly insertion sort took over 7 seconds, but the timeout should fire after 1 second. Is there any reason for the timeout not to fire?

So I tried switching out my custom sorting program out for the sort.Ints function from the sort package by changing sortingFuncs map into:

sortingFunctions := map[string]func([]int){
    "InsertionSort":        sort.Ints,
    "QuickSortLastElement": sort.Ints,
    "QuickSortRandom":      sort.Ints,
}

And the problem was solved. So it's my custom sorting functions that are preventing the timeout from being fired. Is there something that I have to add to those functions to make them run in parallel?

Here is a concatenated version with all the code in the playground. https://play.golang.org/p/SBgDTGyUyp

Answer 1

The code you posted on the Go playground gives the following output:

Generated 90000 integers.
InsertionSort        took  4465.6230ms to sort 90000 elements
QuickSortLastElement took    11.2758ms to sort 90000 elements
QuickSortRandom      took    11.6547ms to sort 90000 elements

I suspect the fact that you are not seeing the timeout being called is due to the fact that InsertionSort does make any function calls, and thus does not allow the scheduler to switch between goroutines. Since Go by default uses only a single thread, everything else has then to wait until InsertionSort has finished.

To test this hypothesis, I tried calling the program with GOMAXPROCS=4 (allowing the Go scheduler to use 4 operating system threads): In this case I get the output

Generated 90000 integers.
QuickSortRandom      took    21.1900ms to sort 90000 elements
QuickSortLastElement took    11.4538ms to sort 90000 elements
Timeout

as expected. (Curiously, for GOMAXPROCS=2 the behaviour is not deterministic, sometimes the timeout triggers and sometimes it does not. I did not try to find out why 2 threads are not always enough here.)