Proposal Details

sort.Search doesn't provide a way to exit earlier when an error happens.

This proposal suggests to add a sort.SearchWithError function, which is like Search but allows f to return an error, and exit earlier on error.

A pr is here.

Comment From: gabyhelp

Related Issues

Related Code Changes

(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)

Comment From: adonovan

How often does this need arise? It's rare for sorting to be fallible, even rarer for sorting to be such a significant hot spot that it's worth aborting the operation in the (presumably rare) case when an error is encountered. I don't see this proposal getting accepted.

You can always use panic and recover to jump out of the sort package in case of error:

func f(slice T[]) (err error) {
    type oops struct{}
    defer func() {
        if r := recover(); r != nil && r != (oops{}) {
            panic(r)
        }
    }()
    slices.SortFunc(slice, func(a, b T) int {
        if ... {
            err = ...
            panic(oops{})
        }
        return ...a...b...
    }()
    return err
}

Comment From: zhiqiangxu

I think it's quite often if each item needs to be read from database dynamically, here is an example.

panic/recover works as a workaround, but it would be more convenient if there is a standard func.

Comment From: randall77

If you sort objects whose home is in a database, then you need to load each object from the database O(lg n) times. Much better to load them from the database once into memory, and then sort in memory.

Comment From: randall77

I think it's quite often if each item needs to be read from database dynamically, here is an example.

This example is doing sort.Search, not sort.SortFunc.

Comment From: zhiqiangxu

This example is doing sort.Search, not sort.SortFunc.

Yes, this issue is talking about sort.Search, not sort.SortFunc.

Comment From: zhiqiangxu

If you sort objects whose home is in a database, then you need to load each object from the database O(lg n) times. Much better to load them from the database once into memory, and then sort in memory.

In the linked example, it's acceptable to load O(lg n) times at deterministic offsets, but not acceptable to load all data into memory.

Comment From: adonovan

Apologies, I muddled the waters by confusing Sort and Search.

Ok, so let's talk about Search. The entire algorithm is 10 lines of Go. It may be notoriously hard to write a correct version casually, but there's no reason you can't just copy the Search function, which is thoroughly debugged and documented, into your application, then replace the f(x) call with your database query. Or write a variant that deals with errors, as you originally proposed.

Comment From: randall77

Ah, sorry, Alan's example confused me. This is about search, not sort.

Then I don't quite see how you can't just have an exit-early boolean, kind of like your example uses.

var e error
idx := sort.Search(n, func(i int) bool {
    if e != nil { return false } // or true, doesn't matter
    _, err := ..some error generating operation...
    if err != nil {
        e = err
        return false
    }
})
if e != nil { ... something went wrong ... }
else { ... use idx ... }

Compared to a database lookup, the O(lg N) checks of e != nil are going to be ~free.

Comment From: zhiqiangxu

Thanks for providing two alternative approaches, I like Alan's approach better as I'm quite picky for code style. But I'm not sure if it's worth to add it into the library directly, thus created this proposal for disscussion.