Category Archives: Useless Trivia

Friday pop quiz: the smallest buffer

bytes.Buffer is a tremendously useful type, but it’s a bit large1.

% sizeof -p bytes Buffer
Buffer 112

… and that is just the overhead, we haven’t put any data into the buffer yet.

This Friday’s2 challenge is to write a replacement for bytes.Buffer that implements io.ReadWriter and allows the caller to discover the length and capacity of the buffer.

The smallest and most creative solution wins fame, adoration, and a first run gb sticker.

Rules

  • The code must continue to be correctly formatted.
  • Points will be deducted for arguing with the judge (me).
  • Everything you need to win this challenge is in the description; think laterally.

Answers

As I hoped, most readers quickly figured out a good way to save a few lines was to declare Read and Write methods on a []byte, not a struct. This would lead to some small complications dereferencing the value rather than treating it as a struct with a buf []byte field, but everyone seemed to figure that out, which is good, as these are useful skills to have in your Go toolbelt.

A few readers also spotted the deliberate loophole I left in the wording of the question around obtaining the length and the capacity of the buffer. Declaring a new type with an underlying type of a slice gives you access to the len and cap, so finding the length of a slice requires no additional methods on the type.

type Buffer []byte

func main() {
        var b Buffer
        b.Write([]byte("howdy")
        fmt.Println(len(b))
}

Thus, the core of this challenge was to define a new slice type that had Read and Write methods, which would end up taking an overhead of 3 machine words, 24 bytes on 64bit platforms, 12 on 32bit.

One nice property of this arrangement is that if you already have a []byte slice, you can convert it into a Buffer and consume zero additional storage, as you are effectively replacing the 3 words that described the []byte with 3 words which describe your new slice type.

s := []byte{0x01, 0x02, 0x03}
buf := Buffer(s)

However, as usually happens with these quizzes, a solution arrives that wipes the smug smile from my face,

Kevin, I take my imaginary hat off to you, Sir.

For the record, here was the solution I came up with last night. It is longer than I hoped it would be because of the odd contract that the standard library bytes.Buffer tests require. I think a more liberal reading of the io.Reader contract would result in a smaller entry.

// A Buffer is a variable-sized buffer of bytes with Read and Write
// methods. The zero value for Buffer is an empty buffer ready to use.
type Buffer []byte

// Write writes len(p) bytes from p to the Buffer.
func (b *Buffer) Write(p []byte) (int, error) {
        *b = append(*b, p...)
        return len(p), nil
}

// Read reads up to len(p) bytes into p from the Buffer.
func (b *Buffer) Read(p []byte) (int, error) {
        if len(p) == 0 {
                return 0, nil
        }
        if len(*b) == 0 {
                return 0, io.EOF
        }
        n := copy(p, *b)
        *b = (*b)[n:]
        return n, nil
}

Playground link

So, prizes and glory to @rf, Ben Lubar, and @kevingillette, with special mentions to Egon Elbre, and Dan Kortschak and Douglas Clark from G+. Some of you were more correct than others, but you were all very quick, and that’s got to count for something. I’ll be in touch with your prize.

If a reader wants to debate their solution, and possibly best ours, consider this an open challenge.


  1. Where do you get the sizeof program ? Why, from Russ Cox of course, godoc.org/rsc.io/sizeof (oops, it looks like this doesn’t work with Go 1.4.2, better use tip, or try this online version)
  2. I’m sorry if it isn’t Friday where you live. I can’t help it if Australians live in the future.

Friday pop quiz: the size of things

In this program, the size of variables of type x and y in memory varies by platform.

package main

func main() {
        const n = 4
        type x [n]uint
        type y [n]int
}

By changing only one line can you ensure that variables of type x, and y always consume 16 bytes on all platforms that Go 1.4 supports ?

Rules

The code must continue to be correctly formatted.

Bonus points will be awarded for the most creative solution.

Points will be deducted for arguing with the judge (me).


Answers

The solution obviously involved setting n to 4 on 32 bit platforms, and 2 on 64 bit. There were a wide number of variations on this, involving a menagerie of subtraction, shifting and multiplication. The solution I came up with used only one operator:

const n = 4 >> (^uint(0) >> 63)

^uint(0) gives you a number whose bits are all 1, then >> 63 shifts the number 63 binary places to the right. If we’re on a 64 bit platform, this evaluates to 1, shifting 4 one place to the right leaves 2, otherwise 32 ones shifted 63 places to the right gives zero, and 4 shifted right zero times is still 4.

So I was feeling rather chuffed with myself until Paul Hankin quietly dropped this solution:

const n = ^uint(6) % 7

Paul, my hat is off to you Sir.

Minimum one liner followup

It’s a little unfair to announce winners in some kind of order as I did post the quiz at an unfriendly hour of the day for most of the planet.

With that said, Tim and William came up with a great map based solution at roughly the same time. You’ll have to split the winnings between yourselves.

Gary came an interesting solution that works for almost all the integers.

Gustavo Niemeyer takes double points for demonstrating that the first version of this problem could be defeated easily, and then proceeded to demonstrate his very mathy solution to fix Gary’s proposal. Several others also proposed some great shift tricks.

Honourable mentions go to Charlie Somerville, for playing the man and not the ball and Francesc who proved that even with two attempts I couldn’t make the problem sufficiently water tight.

Although the prohibition on adding more than one line was lost on Brendan Tracey, I think this proposal deserves to be highlighted.

So with sensible, workable, and sometimes beautiful solutions out in the open, the race was on for the bonus points for the most creative.

The first was my entry, which was the genesis for this quiz and goes to show, this why we cannot have nice things.

func f(a int, b uint) {
        var min = 0
        min = copy(make([]struct{}, a), make([]struct{}, b))
        fmt.Printf("The min of %d and %d is %d\n", a, b, min)
}

Props for figuring this out goes to Arnaud Porterie and Gustavo Niemeyer who were both good sports and deleted their answer.

I was feeling rather pleased with myself until Paul Hankin emailed me this fabulously creative effort. After that others tweaked to the loop hole that I had inadvertently left open by importing the fmt package.

Congratulations to the winners, and thank you all for contributing.

Friday pop quiz: minimum one liner

This program is incorrect

package main

import "fmt"

func f(a, b int) {
        var min = 0
        fmt.Printf("The min of %d and %d is %d\n", a, b, min)
}

func main() {
        f(9000, 314)
}

By adding only one line can you make it print the correct answer ?

The code must continue to be correctly formatted.

Bonus points will be awarded for the most creative solution.

Points will be deducted for arguing with the judge (me).

Update: thanks to Gustavo Niemeyer who pointed out the first version of the quiz made it way to easy.

Update: a few people have provided some very sound, rational solutions. Good job, give yourself a code review gold star.

The bonus points for the most creative solution are still on the table. As a hint my solution will also work for this variant of the problem.


The answer(s) will be posted tomorrow.

Paranormal trivia

Like all children who grew up in the 80’s, I was, and still am a huge fan of Ghostbusters.

While recently re watching Ivan Reitman’s homage to New York, I spotted something which has gone unnoticed on the IMDB trivia page.

Shortly after being evicted from the University, Ray Stantz (Aykroyd) and Peter Venkman (Murray) are commiserating their fall from grace, when Stantz opines:

aykroyd

In which movie did Dan Aykroyd star a year before Ghostbusters ? Continue reading

On declaring variables

Go has several ways to declare a variable. Possibly there are more ways than are strictly required but with the Go 1 contract in effect it’s not going to change.

This short post gives examples of how I decide which variable declaration syntax to use. These are just suggestions, they make sense to me, but I’m sure others have equally strong justifications for alternative arrangements.

When declaring (but not initialising) a variable consider using this syntax

var num int

As Go does not permit uninitialised variables, num will be initialised to the zero value.

Some other examples of this form might be

var things []Thing // an empty slice of Things
for t := range ThingCreator() {
        things = append(things, t)
}

var thing Thing // empty Thing struct 
json.Unmarshall(reader, &thing)

The key is that var acts as a clue that the variable has been deliberately declared as the zero value of the indicated type.

When declaring and initialising, consider using the short declaration syntax. For example

num := rand.Int()

The lack of var is a signal that this variable has been initialised. I also find that by avoiding declaring the type of the variable and infering it from the right hand side of the assignment makes re-factoring easier in the future.

Of course, with any rule of thumb, there are exceptions.

min, max := 0, 1000

But maybe in this case min and max are really constants.

var length uint32 = 0x80

Here length may be being used with a library which requires a specific numeric type and this is probably more readable than

length := uint32(0x80)

The Mythical Man-Month selection bias

There is an apocryphal story1 during World War Two, of a squadron of bombers leaving on a sortie. Time passes and finally a few bombers struggle back to their base, the crew shaken, but alive, their aircraft riddled with bullet holes.

Shocked by their losses, the reaction by Air Force was to order the areas of the air frame wounded by enemy fire be reinforced with additional armor plating to improve the success of future missions.

Fortunately for the Allies, a statistician engaged by the British raised the issue that the aircraft that had returned, although battle scared, were hit in places not crucial for flight. In comparison, their missing comrades had not fared so well. Having succumb to enemy fire, the damage their aircraft suffered could not be accounted for.

Thus, the statistician argued, the portions of the aircraft which should receive additional armor should the places which did not suffer damage. This then is a tale about Selection Bias.

Thirty years later, Frederick P Brooks, Jr wrote his seminal work, The Mythical Man-Month. Brooks’ observation that “adding manpower to a late software project makes it later” has become a rallying cry for the software development industry; one which we have had no shortage of opportunities to validate against a steady stream of prominent projects who over promised yet under delivered.

However, for all our well founded chortling, I wonder if we are not succumbing to our own selection bias. For all the attempts to throw people at a floundering project is there a percentage of teams that quietly pull it off, meet their audacious schedule and live to code another day ?

Is Brooks’ law an axiom of the software development industry, or are we simply counting the losers and drawing the wrong conclusion?


  1. If you want the real story, I suggest reading John D Cook’s post.

Evaluation order oddity

At Canonical we’re increasingly invested in gccgo. While testing various packages built with gccgo we ran across test failures which we traced to an innocent looking piece of code.

package main

import "fmt"

type T struct {
        i int
}

func (t *T) readInt32() int32 {
        t.i += 4
        return 42 // not important
}

func main() {
        var d = T{i:200}
        end := d.i - 4 + int(d.readInt32())
        fmt.Println(end)
}

So, knowing that the Go spec defines the order of evaluation of functions calls and assignments as left to right, let’s try to predict what this code will print.

200 - 4 + 42 = 238

So, is 238 the correct answer ?

% go run odd.go 
242

Wow, that is odd. Let’s see what gccgo thinks the answer is

% go run -compiler gccgo odd.go 
238

Well, at least it got the right answer, so is gc at fault or are the arguments actually evaluated in the opposite direction ?

It turns out that both compilers are correct because the evaluation order of this sort of expression is not specified. In fact, in the spec, this case is called out in an example which is strongly reminiscent of the original code.

a := 1
f := func() int { a = 2; return 3 }
x := []int{a, f()}  // x may be [1, 3] or [2, 3]: evaluation order between a and f() is not specified

The correct solution to this problem is to break the expression into two lines, removing the ambiguity about when the addition to d.i is visible.

func main() {
        var d = T{i:200}
        v := int(d.readInt32())
        end := v + d.i - 4
        fmt.Println(end) 	// prints 242
}

Stupid Go declaration tricks

This is a brief post highlighting a curious aspect of the declaration syntax in Go.

Most Go programmers know that the following of import declarations are equivalent

import "fmt"
import "math/big"

// same as
import (
        "fmt"
        "math/big"
)

The same applies to const declarations

const FORTYTWO = 42
const TRUE = 1

// same as
const (
        FORTYTWO = 42
        TRUE     = 1
)

But perhaps you didn’t know that the syntax is also valid for type declarations. For example, the following is valid syntax in Go.

type (
        B struct{ a, b int }
        C interface {
                Hello() error
        }
)

However because the func declaration has been extended to place methods on types, the following is not valid syntax

func (
        main() {
                fmt.Println("wowzers")
        }
)

Using screen for lazy dot files

I have a lot of shell accounts; on my laptops and workstations, on my ARM build boxes, on remote servers, and so on. I don’t make a lot of customisations to my login shell as the lowest common denominator of OS X, FreeBSD and various Linux distros has trained me to live with what is on the host.

I do have two exceptions, bash and screen1. Handling my screen config is easy; just scp my .screenrc file to the new host. Handling the small number of changes to my bash setup is more involved as bash has several places it looks in (.bashrc, .bash_profile, sometimes just .profile) and those files may already exist on the host.

Recently I’ve been experimenting with the idea of using screen to handle this customisation, which reduces the amount of configuration data copied to a new host to a single new file. Here is a sample .screenrc from an ARM FreeBSD build box.

startup_message off
vbell off

# Window list at the bottom.
hardstatus alwayslastline "%{wk}%-w%{Gk}[%n %t]%{wk}%+w%=%{Ck}%M%d %c%{-} %{=r} ${USER}@%H"

# who needs .bashrc ?
shell bash
setenv PS1 "\[\e]0;\u@\h: \w\a\]\h(\w) % "
setenv GOROOT /u/go                           
setenv GOPATH $HOME
# yup, screen can expand shell vars
setenv PATH $PATH:$GOROOT/bin:$GOPATH/bin 

autodetach on
term xterm-color
termcapinfo xterm ti@:te@

Combined with ssh $HOST -t -- screen -R -D, this makes setting up a new machine very simple.


1. Note to haters. I know that alternatives like zsh and tmux exist, but neither are installed by default on any mainstream distro, so until they are, I don’t care. At any rate, these suggestions probably apply equally well to your chosen shell and screen multiplexer.