code review 4388048: net: sort records returned by LookupMX

net: sort records returned by LookupMX

[cthom, 2011-04-11 12:50:20]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[rog, 2011-04-11 13:33:57]

http://codereview.appspot.com/4388048/diff/4001/src/pkg/net/dnsclient.go
File src/pkg/net/dnsclient.go (right):

http://codereview.appspot.com/4388048/diff/4001/src/pkg/net/dnsclient.go#newc...
src/pkg/net/dnsclient.go:415: type mxslice []*MX
YMMV, but if you wanted to implement random ordering for objects with the same
preference, you do something like:

type mxrecords struct {
  mx []*MX
  perm []int
}

func (m *mxrecords) Less(i, j int) bool {
    if m.mx[i].Pref != m.mx[i].Pref {
        return m.mx[i].Pref < m.mx[j].Pref
    }
    return m.perm[i] < m.perm[j]
}

func (m *mxrecords) Swap(i, j int) {
   m.mx[i], m.mx[j] = m.mx[j], m.mx[i]
   m.perm[i], m.perm[j] = m.mx[j], m.mx[i]
}

func LookupMX(name string) (entries []*MX, err os.Error) {
    ...
    m := &mxrecords{entries, rand.Perm(len(entries))
    sort.Sort(m)
    return
}

this is a case where it would be nice to have rand.Shuffle - you could shuffle
consecutive sequences mx records with the same Pref, avoiding the need to
allocate a permutation array.

[cthom, 2011-04-11 13:52:10]

I was just reading the RFC, didn't realize the randomness was a MUST
[sic], I would've thought the "random" order the dns server sends them
would be sufficient. I'll adjust I suppose, but it does seem silly to
invest client-side code into load-balancing for the server.

On 11 April 2011 09:33,  <rogpeppe@gmail.com> wrote:
>
> http://codereview.appspot.com/4388048/diff/4001/src/pkg/net/dnsclient.go
> File src/pkg/net/dnsclient.go (right):
>
>
http://codereview.appspot.com/4388048/diff/4001/src/pkg/net/dnsclient.go#newc...
> src/pkg/net/dnsclient.go:415: type mxslice []*MX
> YMMV, but if you wanted to implement random ordering for objects with
> the same preference, you do something like:
>
> type mxrecords struct {
>  mx []*MX
>  perm []int
> }
>
> func (m *mxrecords) Less(i, j int) bool {
>    if m.mx[i].Pref != m.mx[i].Pref {
>        return m.mx[i].Pref < m.mx[j].Pref
>    }
>    return m.perm[i] < m.perm[j]
> }
>
> func (m *mxrecords) Swap(i, j int) {
>   m.mx[i], m.mx[j] = m.mx[j], m.mx[i]
>   m.perm[i], m.perm[j] = m.mx[j], m.mx[i]
> }
>
> func LookupMX(name string) (entries []*MX, err os.Error) {
>    ...
>    m := &mxrecords{entries, rand.Perm(len(entries))
>    sort.Sort(m)
>    return
> }
>
> this is a case where it would be nice to have rand.Shuffle - you could
> shuffle consecutive sequences mx records with the same Pref, avoiding
> the need to allocate a permutation array.
>
> http://codereview.appspot.com/4388048/
>

[cthom, 2011-04-11 14:34:56]

Hello golang-dev@googlegroups.com, rog (cc: golang-dev@googlegroups.com),

Please take another look.

[cthom, 2011-04-11 14:36:04]

Hello golang-dev@googlegroups.com, rog (cc: golang-dev@googlegroups.com),

Please take another look.

[adg, 2011-04-12 01:09:09]

The code looks good, but I would like to see some simple test cases
for mxsorter.

[rsc, 2011-04-12 03:06:20]

http://codereview.appspot.com/4388048/diff/5002/src/pkg/net/dnsclient.go
File src/pkg/net/dnsclient.go (right):

http://codereview.appspot.com/4388048/diff/5002/src/pkg/net/dnsclient.go#newc...
src/pkg/net/dnsclient.go:414: // Implements sort.Interface
This is working too hard.  (I know it's not your algorithm.)

type byPref []*MX
// usual methods, now 1/3 as long

func LookupMX(...) {
    ...
    // Shuffle.
    for i := range mx {
        j := rand.Intn(i+1)
        mx[i], mx[j] = mx[j], mx[i]
    }
    // Sort by preference.
    // Stays shuffled within equal preference.
    sort.Sort(byPref(mx))
}

http://codereview.appspot.com/4388048/diff/5002/src/pkg/net/dnsclient.go#newc...
src/pkg/net/dnsclient.go:437: var records []dnsRR
While you're here,

s/records/rr/
s/entries/mx/

[cthom, 2011-04-12 13:54:51]

Changes made.

Should I also include a test of byPref in this CL? i.e.

func TestMXPref(t *testing.T) {
	var mx1, mx2, mx3 []*MX
	mx1 = []*MX{
		&MX{"a", 5},
		&MX{"b", 5},
		&MX{"c", 5},
		&MX{"d", 5},
		&MX{"e", 5},
	}
	// Copied the shuffle here
	mx2 = append(mx2, mx1...)
	for i := range mx2 {
		j := rand.Intn(i+1)
		mx2[i], mx2[j] = mx2[j], mx2[i]
	}
	sort.Sort(byPref(mx2))
	// mx2 now holds a shuffled copy to check that shuffles are random
	mx3 = append(mx3, mx1...)
	for runs := 0; runs < 20; runs++ {
		for i := range mx3 {
			j := rand.Intn(i+1)
			mx3[i], mx3[j] = mx3[j], mx3[i]
		}
		sort.Sort(byPref(mx3))
		for i := range mx3 {
			if mx3[i] != mx2[i] && mx3[i] != mx1[i] {
				return
			}
		}
		copy(mx3, mx1)
	}
	t.Errorf("MX records don't get shuffled")
}

Or something, I don't have much experience writing test functions,
especially not for randomness, but honestly this seems more like a
test of rand and sort than anything, and it will fail something like 1
in every 19 sextillion builds.

On 11 April 2011 23:06,  <rsc@golang.org> wrote:
>
> http://codereview.appspot.com/4388048/diff/5002/src/pkg/net/dnsclient.go
> File src/pkg/net/dnsclient.go (right):
>
>
http://codereview.appspot.com/4388048/diff/5002/src/pkg/net/dnsclient.go#newc...
> src/pkg/net/dnsclient.go:414: // Implements sort.Interface
> This is working too hard.  (I know it's not your algorithm.)
>
> type byPref []*MX
> // usual methods, now 1/3 as long
>
> func LookupMX(...) {
>    ...
>    // Shuffle.
>    for i := range mx {
>        j := rand.Intn(i+1)
>        mx[i], mx[j] = mx[j], mx[i]
>    }
>    // Sort by preference.
>    // Stays shuffled within equal preference.
>    sort.Sort(byPref(mx))
> }
>
>
http://codereview.appspot.com/4388048/diff/5002/src/pkg/net/dnsclient.go#newc...
> src/pkg/net/dnsclient.go:437: var records []dnsRR
> While you're here,
>
> s/records/rr/
> s/entries/mx/
>
> http://codereview.appspot.com/4388048/
>

[rsc, 2011-04-12 18:12:00]

Don't worry about a test.  We don't have testing set up
for any of the DNS code, and it's going to get some
more work done on it soon anyway.

Russ

[cthom, 2011-04-12 18:16:34]

Hello rog, adg, rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[adg, 2011-04-12 23:41:10]

LGTM

One last change.

http://codereview.appspot.com/4388048/diff/6/src/pkg/net/dnsclient.go
File src/pkg/net/dnsclient.go (right):

http://codereview.appspot.com/4388048/diff/6/src/pkg/net/dnsclient.go#newcode414
src/pkg/net/dnsclient.go:414: // Implements sort.Interface by record preference
// byPref implements sort.Interface to sort MX records by preference

[cthom, 2011-04-13 11:59:28]

Hello rog, adg, rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[adg, 2011-04-14 00:30:54]

*** Submitted as http://code.google.com/p/go/source/detail?r=b353f61b9548 ***

net: sort records returned by LookupMX

R=rog, adg, rsc
CC=golang-dev
http://codereview.appspot.com/4388048

Committer: Andrew Gerrand <adg@golang.org>