Ok. I will postpone this.
Just for the record: I modified the implementation, and a sort
implementation based on a less and swap function instead of an
interface appears to be faster then the current interface approach.
Specifically:
Old code:
sort_test.BenchmarkSortInt1K	 10000	 285444 ns/op
sort_test.BenchmarkSortInt64K	 100	 28132250 ns/op
New code:
sort_test.BenchmarkSortNInt1K	 10000	 242571 ns/op
sort_test.BenchmarkSortNInt64K	 100	 23886690 ns/op
The difference is about 15%. More exactly, this is using SortN, a
further modification of SortBy, hinted at in my original mail:
 func SortN(less Criteria, n int)
which requires only a single closure:
 type Criteria func(i, j int, swap bool) bool
where Criteria is basically the same as Interface.Less in the existing
code, except that it also swaps if swap is set and the result is true
(i.e., a[i] < a[j]). The two functions less and swap as needed for
SortBy can be obtained as follows from Criteria:
 func (less Criteria) Less(i, j) bool { return less(i, j, false) {
and (credits to lvd who pointed this out):
 func (less Criteria) Swap(i, j int) {
 	if !less(i, j, true) {
		less(j, i, true)
	}
 }
It turns out that in some cases, Swap doesn't need to be called
anymore in the implementation, which reduces the number of upcalls.
But the extra complexity for swapping when it is needed may destroy
some of the benefit again. Nevertheless, this approach is faster than
what we have now.
And Criteria can also be created from an existing sort.Interface,
which outlines the connection between the current sort.Sort, and
sort.SortN.
func MakeCriteria(data Interface) Criteria {
	return func(i, j int, swap bool) bool {
		if data.Less(i, j) {
			if swap {
				data.Swap(i, j)
			}
			return true
		}
		return false
	}
}
To summarize:
1) The existing API can be improved, both for ease of use, and better
performance.
2) There is evidence that a closure-based approach is faster.
3) SortBy (current proposal) can be further simplified to an approach
where only a single function (Criteria) is needed; albeit at the cost
of a more complex such function.
- gri
On Thu, Jan 5, 2012 at 5:36 PM, Rob 'Commander' Pike <r@google.com> wrote:
> After consideration, I vote for leaving Sort alone and dropping this approach,
at least for now. It's merely the latest in a line of attempts to provide a
generic sorting algorithm in a non-generic language. These new suggestions are
worth discussing in the abstract but not as a check-in right before Go 1, whose
APIs should be close to fixed by now. I realize this is an addition, not a
replacement, but I am concerned about the precedent this
work-around-the-interface-model approach sets. In some cases the approach may be
more convenient but I am unconvinced it's superior enough to suggest it as a
general approach, and it also raises the issue of why only Sort gets this
treatment.
>
> If Sort needs a different API, let's take our leisurely time designing,
playing, and adapting with it, but after Go 1 is out and perhaps in a wider
context involving collation and the general topic of the future of containers
and algorithms in Go.
>
> It's likely more things will arrive in the next few weeks that will trigger a
similar reply from me (there have been others already), so let me avoid all the
explanation in those cases by establishing a shorthand:
>
> Not now.
>
> -rob
>