Issue 58550043: code review 58550043: sort: add type-specific internal versions of Sort() and...
Descriptionsort: add type-specific internal versions of Sort() and Stable()
This change replaces the existing "virtual all the way down" mechanism with a type switch and dispatch to type specific versions of the Sort() and Stable() routines. No change is made to the sorting algorithms, the purpose is to remove needless type discovery. There is also no change to
the API. The result is a 3x-4x speedup when sorting any of the built-in styles: []int, []float64, and []string. Could be easily extended to other standard types if desired. Also made a few spelling fixes in comments.
Patch Set 1 #Patch Set 2 : diff -r 96b485225cef https://code.google.com/p/go #Patch Set 3 : diff -r 96b485225cef https://code.google.com/p/go #MessagesTotal messages: 11
Hello golang-codereviews@googlegroups.com, I'd like you to review this change to https://code.google.com/p/go
Sign in to reply to this message.
Sadness. If the compiler did this behind the scenes, I'd take the code size hit for that speed-up. But man it's gross seeing it expanded manually like this. That means a user clicking through the docs doesn't see something nice like http://golang.org/src/pkg/sort/sort.go?s=6884:6908#L266 now. :-/ On Thu, Jan 30, 2014 at 8:02 AM, <michael.jones@gmail.com> wrote: > Reviewers: golang-codereviews, > > Message: > Hello golang-codereviews@googlegroups.com, > > I'd like you to review this change to > https://code.google.com/p/go > > > Description: > sort: add type-specific internal versions of Sort() and Stable() > > This change replaces the existing "virtual all the way down" mechanism > with a type switch and dispatch to type specific versions of the Sort() > and Stable() routines. No change is made to the sorting algorithms, the > purpose is to remove needless type discovery. There is also no change to > the API. The result is a 3x-4x speedup when sorting any of the built-in > tyles: []int, []float64, and []string. Could be easily extended to other > standard types if desired. Also made a few spelling fixes in comments. > > Please review this at https://codereview.appspot.com/58550043/ > > Affected files (+796, -8 lines): > M src/pkg/sort/sort.go > > > -- > You received this message because you are subscribed to the Google Groups > "golang-codereviews" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-codereviews+unsubscribe@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. >
Sign in to reply to this message.
Well, I don't want to be off-topic, but this is why people agitate for a mechanism to support generic/parametric types. If people go for my code, and then they ask for byte, int8, uint8, int16, uint16, int32, uint32, int64, uint64, and float32 versions then the would be grosser. It is not hard, though, and only took me an hour or two of pleasant time while listening to music. In the olden days I would have done this with CPP, or m4. In C++ one could do it directly, and much more nicely, since the Less() et al could be inlines that even make the various versions look clean yet give best performance. Back on topic, I suggest we adopt my code for this reason: It shows how interfaces and Go abstraction can be full-performance. The question of any abstraction is "when does it become concrete?" In Smalltalk, never. That is, only at hardware instruction dispatch. In Go, it is up to you. The existing code for Sort() and Stable() keep the datatype abstract all the way down. This is necessary for user types. But, it is easy to recognize some (or all) built-in types and dispatch once for those. That's happening here in the top-level type switch and that teaches the performance-oriented notion that you might do the concretization at the highest level where it makes sense. I agree that the code you link is pretty. You'll notice that I left it in my version as a comment intended to help the understanding of the reader. "This is what we could be doing, but we take this specific path because we know enough to do so." On Thu, Jan 30, 2014 at 1:09 AM, Brad Fitzpatrick <bradfitz@golang.org>wrote: > Sadness. > > If the compiler did this behind the scenes, I'd take the code size hit for > that speed-up. But man it's gross seeing it expanded manually like this. > That means a user clicking through the docs doesn't see something nice > like http://golang.org/src/pkg/sort/sort.go?s=6884:6908#L266 now. :-/ > > > > On Thu, Jan 30, 2014 at 8:02 AM, <michael.jones@gmail.com> wrote: > >> Reviewers: golang-codereviews, >> >> Message: >> Hello golang-codereviews@googlegroups.com, >> >> I'd like you to review this change to >> https://code.google.com/p/go >> >> >> Description: >> sort: add type-specific internal versions of Sort() and Stable() >> >> This change replaces the existing "virtual all the way down" mechanism >> with a type switch and dispatch to type specific versions of the Sort() >> and Stable() routines. No change is made to the sorting algorithms, the >> purpose is to remove needless type discovery. There is also no change to >> the API. The result is a 3x-4x speedup when sorting any of the built-in >> tyles: []int, []float64, and []string. Could be easily extended to other >> standard types if desired. Also made a few spelling fixes in comments. >> >> Please review this at https://codereview.appspot.com/58550043/ >> >> Affected files (+796, -8 lines): >> M src/pkg/sort/sort.go >> >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "golang-codereviews" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to golang-codereviews+unsubscribe@googlegroups.com. >> For more options, visit https://groups.google.com/groups/opt_out. >> > > -- Michael T. Jones michael.jones@gmail.com http://www.google.com/profiles/michael.jones
Sign in to reply to this message.
On 2014/01/30 19:13:03, mtj wrote: > Well, I don't want to be off-topic, but this is why people agitate for a > mechanism to support generic/parametric types. If people go for my code, > and then they ask for byte, int8, uint8, int16, uint16, int32, uint32, > int64, uint64, and float32 versions then the would be grosser. It is not > hard, though, and only took me an hour or two of pleasant time while > listening to music. In the olden days I would have done this with CPP, or > m4. In C++ one could do it directly, and much more nicely, since the Less() > et al could be inlines that even make the various versions look clean yet > give best performance. > > Back on topic, I suggest we adopt my code for this reason: It shows how > interfaces and Go abstraction can be full-performance. The question of any > abstraction is "when does it become concrete?" In Smalltalk, never. That > is, only at hardware instruction dispatch. In Go, it is up to you. The > existing code for Sort() and Stable() keep the datatype abstract all the > way down. This is necessary for user types. But, it is easy to recognize > some (or all) built-in types and dispatch once for those. That's happening > here in the top-level type switch and that teaches the performance-oriented > notion that you might do the concretization at the highest level where it > makes sense. > > I agree that the code you link is pretty. You'll notice that I left it in > my version as a comment intended to help the understanding of the reader. > "This is what we could be doing, but we take this specific path because we > know enough to do so." > > > On Thu, Jan 30, 2014 at 1:09 AM, Brad Fitzpatrick <mailto:bradfitz@golang.org>wrote: > > > Sadness. > > > > If the compiler did this behind the scenes, I'd take the code size hit for > > that speed-up. But man it's gross seeing it expanded manually like this. > > That means a user clicking through the docs doesn't see something nice > > like http://golang.org/src/pkg/sort/sort.go?s=6884:6908#L266 now. :-/ > > > > > > > > On Thu, Jan 30, 2014 at 8:02 AM, <mailto:michael.jones@gmail.com> wrote: > > > >> Reviewers: golang-codereviews, > >> > >> Message: > >> Hello mailto:golang-codereviews@googlegroups.com, > >> > >> I'd like you to review this change to > >> https://code.google.com/p/go > >> > >> > >> Description: > >> sort: add type-specific internal versions of Sort() and Stable() > >> > >> This change replaces the existing "virtual all the way down" mechanism > >> with a type switch and dispatch to type specific versions of the Sort() > >> and Stable() routines. No change is made to the sorting algorithms, the > >> purpose is to remove needless type discovery. There is also no change to > >> the API. The result is a 3x-4x speedup when sorting any of the built-in > >> tyles: []int, []float64, and []string. Could be easily extended to other > >> standard types if desired. Also made a few spelling fixes in comments. > >> > >> Please review this at https://codereview.appspot.com/58550043/ > >> > >> Affected files (+796, -8 lines): > >> M src/pkg/sort/sort.go > >> > >> > >> > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "golang-codereviews" group. > >> To unsubscribe from this group and stop receiving emails from it, send an > >> email to mailto:golang-codereviews+unsubscribe@googlegroups.com. > >> For more options, visit https://groups.google.com/groups/opt_out. > >> > > > > > > > -- > Michael T. Jones > mailto:michael.jones@gmail.com > http://www.google.com/profiles/michael.jones ping
Sign in to reply to this message.
Please no. The speed advantages are undeniable, but I don't think this is the way to go, so to speak. Happy to listen to others, for diverging opinions. At the very least, if this is how we solve the problem for sort, the various versions should be generated from a template so that we don't maintain n versions of essentially the same code (albeit we don't have direct build support for such a mechanism at the moment). This is a place where genericity of sorts would be useful, but also only if the resulting code ended up being a customization (and thus duplication) for the specific types at hand. - gri
Sign in to reply to this message.
Can I check in an m4 template and a shell script? On Feb 17, 2014 2:07 PM, <gri@golang.org> wrote: > Please no. > > The speed advantages are undeniable, but I don't think this is the way > to go, so to speak. Happy to listen to others, for diverging opinions. > > At the very least, if this is how we solve the problem for sort, the > various versions should be generated from a template so that we don't > maintain n versions of essentially the same code (albeit we don't have > direct build support for such a mechanism at the moment). > > This is a place where genericity of sorts would be useful, but also only > if the resulting code ended up being a customization (and thus > duplication) for the specific types at hand. > > - gri > > https://codereview.appspot.com/58550043/ >
Sign in to reply to this message.
Things we need more of in the tree: Perl, awk, shell, and m4. On Feb 17, 2014 2:57 PM, "Michael Jones" <michael.jones@gmail.com> wrote: > Can I check in an m4 template and a shell script? > On Feb 17, 2014 2:07 PM, <gri@golang.org> wrote: > >> Please no. >> >> The speed advantages are undeniable, but I don't think this is the way >> to go, so to speak. Happy to listen to others, for diverging opinions. >> >> At the very least, if this is how we solve the problem for sort, the >> various versions should be generated from a template so that we don't >> maintain n versions of essentially the same code (albeit we don't have >> direct build support for such a mechanism at the moment). >> >> This is a place where genericity of sorts would be useful, but also only >> if the resulting code ended up being a customization (and thus >> duplication) for the specific types at hand. >> >> - gri >> >> https://codereview.appspot.com/58550043/ >> >
Sign in to reply to this message.
Actually what we need less of is the oft quoted diatribe against macros and generics. It is a thing of beauty more than substance, arguably serving as a thought-terminating cliché<http://en.wikipedia.org/wiki/Thought-terminating_clich%C3%A9#Thought-terminating_clich.C3.A9> in the world of Go. The type-specific sort/stable functions come in two genres, one for integers and one floats. These two are simple versions of each other, the Less() in the integer case being just "<" and the same for floats being a careful test about NaNs first and then "<" later. Other than that, the code is identical. I can generate it all from a template using any one of: sed, m4, awk, vi, cpp, pearl, python, echo in sh, or a small Go program, perhaps using trendy templates. I understand the pain of those with a Clockwork Orange type aversion to metaprogramming tools, but I feel that this needs to be done in some way and now is as good a time as any to dip our toe into the water. Here's a proposal: I write a test that generates these only when run with something like "go test -run=GenerateSortFunctions" or some such, and run them once and check in all the resultant code. From a tree builder's point of view, it is just code. From a maintainer's POV, it is one Go-lang templated or "StringsReplace" roll-your-own-sed function to examine and just the single version of the template code to maintain. On Mon, Feb 17, 2014 at 3:06 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote: > Things we need more of in the tree: Perl, awk, shell, and m4. > On Feb 17, 2014 2:57 PM, "Michael Jones" <michael.jones@gmail.com> wrote: > >> Can I check in an m4 template and a shell script? >> On Feb 17, 2014 2:07 PM, <gri@golang.org> wrote: >> >>> Please no. >>> >>> The speed advantages are undeniable, but I don't think this is the way >>> to go, so to speak. Happy to listen to others, for diverging opinions. >>> >>> At the very least, if this is how we solve the problem for sort, the >>> various versions should be generated from a template so that we don't >>> maintain n versions of essentially the same code (albeit we don't have >>> direct build support for such a mechanism at the moment). >>> >>> This is a place where genericity of sorts would be useful, but also only >>> if the resulting code ended up being a customization (and thus >>> duplication) for the specific types at hand. >>> >>> - gri >>> >>> https://codereview.appspot.com/58550043/ >>> >> -- > You received this message because you are subscribed to the Google Groups > "golang-codereviews" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-codereviews+unsubscribe@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > -- *Michael T. Jones | Chief Technology Advocate | mtj@google.com <mtj@google.com> | +1 650-335-5765*
Sign in to reply to this message.
I have nothing against programs generating programs. But the trend in the Go tree has been towards moving non-Go things to Go. Adding m4 is a step backwards. (We'd like our friends on Windows to be able to contribute easily) On Mon, Feb 17, 2014 at 6:07 PM, Michael Jones <mtj@google.com> wrote: > Actually what we need less of is the oft quoted diatribe against macros > and generics. It is a thing of beauty more than substance, arguably serving > as a thought-terminating cliché<http://en.wikipedia.org/wiki/Thought-terminating_clich%C3%A9#Thought-terminating_clich.C3.A9> in > the world of Go. > > The type-specific sort/stable functions come in two genres, one for > integers and one floats. These two are simple versions of each other, the > Less() in the integer case being just "<" and the same for floats being a > careful test about NaNs first and then "<" later. Other than that, the code > is identical. > > I can generate it all from a template using any one of: sed, m4, awk, vi, > cpp, pearl, python, echo in sh, or a small Go program, perhaps using trendy > templates. I understand the pain of those with a Clockwork Orange type > aversion to metaprogramming tools, but I feel that this needs to be done in > some way and now is as good a time as any to dip our toe into the water. > Here's a proposal: > > I write a test that generates these only when run with something like "go > test -run=GenerateSortFunctions" or some such, and run them once and check > in all the resultant code. From a tree builder's point of view, it is just > code. From a maintainer's POV, it is one Go-lang templated or > "StringsReplace" roll-your-own-sed function to examine and just the single > version of the template code to maintain. > > > On Mon, Feb 17, 2014 at 3:06 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote: > >> Things we need more of in the tree: Perl, awk, shell, and m4. >> On Feb 17, 2014 2:57 PM, "Michael Jones" <michael.jones@gmail.com> >> wrote: >> >>> Can I check in an m4 template and a shell script? >>> On Feb 17, 2014 2:07 PM, <gri@golang.org> wrote: >>> >>>> Please no. >>>> >>>> The speed advantages are undeniable, but I don't think this is the way >>>> to go, so to speak. Happy to listen to others, for diverging opinions. >>>> >>>> At the very least, if this is how we solve the problem for sort, the >>>> various versions should be generated from a template so that we don't >>>> maintain n versions of essentially the same code (albeit we don't have >>>> direct build support for such a mechanism at the moment). >>>> >>>> This is a place where genericity of sorts would be useful, but also only >>>> if the resulting code ended up being a customization (and thus >>>> duplication) for the specific types at hand. >>>> >>>> - gri >>>> >>>> https://codereview.appspot.com/58550043/ >>>> >>> -- >> You received this message because you are subscribed to the Google Groups >> "golang-codereviews" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to golang-codereviews+unsubscribe@googlegroups.com. >> >> For more options, visit https://groups.google.com/groups/opt_out. >> > > > > -- > *Michael T. Jones | Chief Technology Advocate | mtj@google.com > <mtj@google.com> | +1 650-335-5765 <%2B1%20650-335-5765>* >
Sign in to reply to this message.
I played with this today on the plane (SFO->IAD) and as a test only, not
for real, I can generate them with something like:
#define SUFFIX ""
#define SUFFICES ""
#define TYPE Interface
#define LENGTH(SLICE) SLICE.Len()
#define SWAP(SLICE, I, J) SLICE.Swap(I, J)
#define LESS(SLICE, I, J) SLICE.Less(I, J)
#define TYPESWITCH(FUNCTION) `switch d := data.(type) {
case IntSlice:
FUNCTION##Int([]int(d))
return
case Float64Slice:
FUNCTION##Float64([]float64(d))
return
case StringSlice:
FUNCTION##String([]string(d))
return
}
`
#define SUFFIX Int
#define SUFFICES Ints
#define TYPE []int
#define LENGTH(SLICE) len(SLICE)
#define SWAP(SLICE, I, J) SLICE[I],SLICE[J] = SLICE[J],SLICE[I]
#define LESS(SLICE, I, J) (SLICE[I] < SLICE[J])
#define TYPESWITCH ""
#define SUFFIX String
#define SUFFICES Strings
#define TYPE []string
#define LENGTH(SLICE) len(SLICE)
#define SWAP(SLICE, I, J) SLICE[I],SLICE[J] = SLICE[J],SLICE[I]
#define LESS(SLICE, I, J) (SLICE[I] < SLICE[J])
#define TYPESWITCH ""
#define SUFFIX Float64
#define SUFFICES Float64s
#define TYPE []float64
#define LENGTH(SLICE) len(SLICE)
#define SWAP(SLICE, I, J) SLICE[I],SLICE[J] = SLICE[J],SLICE[I]
#define LESS(SLICE, I, J) ((SLICE[I] < SLICE[J]) || (isNaN(SLICE[I]) &&
!isNaN(SLICE[J])))
#define TYPESWITCH ""
Not that is is the way to do it, but it makes clear the amount of variance
in the source code beteen various data types. Here's what the exemplars
become:
func heapSort##SUFFIX(data TYPE, a, b int) {
first := a
lo := 0
hi := b - a
// Build heap with greatest element at top.
for i := (hi - 1) / 2; i >= 0; i-- {
siftDown##SUFFIX(data, i, hi, first)
}
// Pop elements, largest first, into end of data.
for i := hi - 1; i >= 0; i-- {
SWAP(data, first, first+i)
siftDown##SUFFIX(data, lo, i, first)
}
}
// Quicksort, following Bentley and McIlroy,
// ``Engineering a Sort Function,'' SP&E November 1993.
// medianOfThree moves the median of the three values data[a], data[b],
data[c] into data[a].
func medianOfThree##SUFFIX(data TYPE, a, b, c int) {
m0 := b
m1 := a
m2 := c
// bubble sort on 3 elements
if LESS(data, m1, m0) {
SWAP(data, m1, m0)
}
if LESS(data, m2, m1) {
SWAP(data, m2, m1)
}
if LESS(data, m1, m0) {
SWAP(data, m1, m0)
}
// now data[m0] <= data[m1] <= data[m2]
}
func swapRange##SUFFIX(data TYPE, a, b, n int) {
for i := 0; i < n; i++ {
SWAP(data, a+i, b+i)
}
}
I'm not entirely pleased with this, but it's not horrible either. I'm going
to try a go template version to see how that works...
On Tue, Feb 18, 2014 at 2:11 PM, Brad Fitzpatrick <bradfitz@golang.org>wrote:
> I have nothing against programs generating programs.
>
> But the trend in the Go tree has been towards moving non-Go things to Go.
> Adding m4 is a step backwards. (We'd like our friends on Windows to be
> able to contribute easily)
>
>
>
> On Mon, Feb 17, 2014 at 6:07 PM, Michael Jones <mtj@google.com> wrote:
>
>> Actually what we need less of is the oft quoted diatribe against macros
>> and generics. It is a thing of beauty more than substance, arguably serving
>> as a thought-terminating
cliché<http://en.wikipedia.org/wiki/Thought-terminating_clich%C3%A9#Thought-terminating_clich.C3.A9>
in
>> the world of Go.
>>
>> The type-specific sort/stable functions come in two genres, one for
>> integers and one floats. These two are simple versions of each other, the
>> Less() in the integer case being just "<" and the same for floats being a
>> careful test about NaNs first and then "<" later. Other than that, the code
>> is identical.
>>
>> I can generate it all from a template using any one of: sed, m4, awk, vi,
>> cpp, pearl, python, echo in sh, or a small Go program, perhaps using trendy
>> templates. I understand the pain of those with a Clockwork Orange type
>> aversion to metaprogramming tools, but I feel that this needs to be done in
>> some way and now is as good a time as any to dip our toe into the water.
>> Here's a proposal:
>>
>> I write a test that generates these only when run with something like "go
>> test -run=GenerateSortFunctions" or some such, and run them once and check
>> in all the resultant code. From a tree builder's point of view, it is just
>> code. From a maintainer's POV, it is one Go-lang templated or
>> "StringsReplace" roll-your-own-sed function to examine and just the single
>> version of the template code to maintain.
>>
>>
>> On Mon, Feb 17, 2014 at 3:06 PM, Brad Fitzpatrick
<bradfitz@golang.org>wrote:
>>
>>> Things we need more of in the tree: Perl, awk, shell, and m4.
>>> On Feb 17, 2014 2:57 PM, "Michael Jones" <michael.jones@gmail.com>
>>> wrote:
>>>
>>>> Can I check in an m4 template and a shell script?
>>>> On Feb 17, 2014 2:07 PM, <gri@golang.org> wrote:
>>>>
>>>>> Please no.
>>>>>
>>>>> The speed advantages are undeniable, but I don't think this is the way
>>>>> to go, so to speak. Happy to listen to others, for diverging opinions.
>>>>>
>>>>> At the very least, if this is how we solve the problem for sort, the
>>>>> various versions should be generated from a template so that we don't
>>>>> maintain n versions of essentially the same code (albeit we don't have
>>>>> direct build support for such a mechanism at the moment).
>>>>>
>>>>> This is a place where genericity of sorts would be useful, but also
>>>>> only
>>>>> if the resulting code ended up being a customization (and thus
>>>>> duplication) for the specific types at hand.
>>>>>
>>>>> - gri
>>>>>
>>>>> https://codereview.appspot.com/58550043/
>>>>>
>>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "golang-codereviews" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to golang-codereviews+unsubscribe@googlegroups.com.
>>>
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>
>>
>>
>> --
>> *Michael T. Jones | Chief Technology Advocate | mtj@google.com
>> <mtj@google.com> | +1 650-335-5765 <%2B1%20650-335-5765>*
>>
>
>
--
*Michael T. Jones | Chief Technology Advocate | mtj@google.com
<mtj@google.com> | +1 650-335-5765*
Sign in to reply to this message.
not lgtm R=close We know that you can make this faster by macro expansion. We'd rather not. I've resorted to custom sorts in some of my code too (and then if you're doing that you can make them even faster, such as by using radix sort in some cases).
Sign in to reply to this message.
|
