Monthly Archives: April 2017

If a map isn’t a reference variable, what is it?

In my previous post I showed that Go maps are not reference variables, and are not passed by reference. This leaves the question, if maps are not references variables, what are they?

For the impatient, the answer is:

A map value is a pointer to a runtime.hmap structure.

If you’re not satisfied with this explanation, read on.

What is the type of a map value?

When you write the statement

m := make(map[int]int)

The compiler replaces it with a call to runtime.makemap, which has the signature

// makemap implements a Go map creation make(map[k]v, hint)
// If the compiler has determined that the map or the first bucket
// can be created on the stack, h and/or bucket may be non-nil.
// If h != nil, the map can be created directly in h.
// If bucket != nil, bucket can be used as the first bucket.
func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap

As you see, the type of the value returned from runtime.makemap is a pointer to a runtime.hmap structure. We cannot see this from normal Go code, but we can confirm that a map value is the same size as a uintptr–one machine word.

package main

import (
	"fmt"
	"unsafe"
)

func main() {
	var m map[int]int
	var p uintptr
	fmt.Println(unsafe.Sizeof(m), unsafe.Sizeof(p)) // 8 8 (linux/amd64)
}

If maps are pointers, shouldn’t they be *map[key]value?

It’s a good question that if maps are pointer values, why does the expression make(map[int]int) return a value with the type map[int]int. Shouldn’t it return a *map[int]int? Ian Taylor answered this recently in a golang-nuts thread1.

In the very early days what we call maps now were written as pointers, so you wrote *map[int]int. We moved away from that when we realized that no one ever wrote `map` without writing `*map`.

Arguably renaming the type from *map[int]int to map[int]int, while confusing because the type does not look like a pointer, was less confusing than a pointer shaped value which cannot be dereferenced.

Conclusion

Maps, like channels, but unlike slices, are just pointers to runtime types. As you saw above, a map is just a pointer to a runtime.hmap structure.

Maps have the same pointer semantics as any other pointer value in a Go program. There is no magic save the rewriting of map syntax by the compiler into calls to functions in runtime/hmap.go.

Notes

  1. If you look far enough back in the history of Go repository, you can find examples of maps created with the new operator.

There is no pass-by-reference in Go

My post on pointers provoked a lot of debate about maps and pass by reference semantics. This post is a response to those debates.

To be clear, Go does not have reference variables, so Go does not have pass-by-reference function call semantics.

What is a reference variable?

In languages like C++ you can declare an alias, or an alternate name to an existing variable. This is called a reference variable.

#include <stdio.h>

int main() {
        int a = 10;
        int &b = a;
        int &c = b;

        printf("%p %p %p\n", &a, &b, &c); // 0x7ffe114f0b14 0x7ffe114f0b14 0x7ffe114f0b14
        return 0;
}

You can see that a, b, and c all refer to the same memory location. A write to a will alter the contents of b and c. This is useful when you want to declare reference variables in different scopes–namely function calls.

Go does not have reference variables

Unlike C++, each variable defined in a Go program occupies a unique memory location.

package main

import "fmt"

func main() {
        var a, b, c int
        fmt.Println(&a, &b, &c) // 0x1040a124 0x1040a128 0x1040a12c
}

It is not possible to create a Go program where two variables share the same storage location in memory. It is possible to create two variables whose contents point to the same storage location, but that is not the same thing as two variables who share the same storage location.

package main

import "fmt"

func main() {
        var a int
        var b, c = &a, &a
        fmt.Println(b, c)   // 0x1040a124 0x1040a124
        fmt.Println(&b, &c) // 0x1040c108 0x1040c110
}

In this example, b and c hold the same value–the address of a–however, b and c themselves are stored in unique locations. Updating the contents of b would have no effect on c.

But maps and channels are references, right?

Wrong. Maps and channels are not references. If they were this program would print false.

package main

import "fmt"

func fn(m map[int]int) {
        m = make(map[int]int)
}

func main() {
        var m map[int]int
        fn(m)
        fmt.Println(m == nil)
}

If the map m was a C++ style reference variable, the m declared in main and the m declared in fn would occupy the same storage location in memory. But, because the assignment to m inside fn has no effect on the value of m in main, we can see that maps are not reference variables.

Conclusion

Go does not have pass-by-reference semantics because Go does not have reference variables.

Next: If a map isn’t a reference variable, what is it?

Understand Go pointers in less than 800 words or your money back

This post is for programmers coming to Go who are unfamiliar with the idea of pointers or a pointer type in Go.

What is a pointer?

Simply put, a pointer is a value which points to the address of another. This is the textbook explanation, but if you’re coming from a language that doesn’t let you talk about address of a variable, it could very well be written in Cuneiform.

Let’s break this down.

What is memory?

Computer memory, RAM, can be thought of as a sequence of boxes, placed one after another in a line. Each box, or cell, is labeled with a unique number, which increments sequentially; this is the address of the cell, its memory location.

Each cell holds a single value. If you know the memory address of a cell, you can go to that cell and read its contents. You can place a value in that cell; replacing anything that was in there previously.

That’s all there is to know about memory. Everything the CPU does is expressed as fetching and depositing values into memory cells.

What is a variable?

To write a program that retrieves the value stored in memory location 200, multiples it by 3 and deposits the result into memory location 201, we could write something like this in pseudocode:

  • retrieve the value stored in address 200 and place it in the CPU.
  • multiple the value stored in the CPU by 3.
  • deposit the value stored in the CPU into memory location 201.


This is exactly how early programs were written; programmers would keep a list of memory locations, who used it, when, and what the value stored there represented.

Obviously this was tedious and error prone, and meant every possible value stored in memory had to be assigned an address during the construction of the program. Worse, this arrangement made it difficult to allocate storage to variables dynamically as the program ran– just imagine if you had to write large programs using only global variables.

To address this, the notion of a variable was created. A variable is just a convenient, alphanumeric pseudonym for a memory location; a label, or nickname.

Now, rather than talking about memory locations, we can talk about variables, which are convenient names we give to memory locations. The previous program can now be expressed as:

  • Retrieve the value stored in variable a and place it in the CPU.
  • multiple it by 3
  • deposit the value into the variable b.

This is the same program, with one crucial improvement–because we no longer need to talk about memory locations directly, we no longer need to keep track of them–that drudgery is left to the compiler.

Now we can write a program like

var a = 6
var b = a * 3

And the compiler will make sure that the variables a and b are assigned unique memory locations to hold their value for as long as needed.

What is a pointer?

Now that we know that memory is just a series of numbered cells, and variables are just nicknames for a memory location assigned by the compiler, what is a pointer?

A pointer is a value that points to the memory address of another variable.

The pointer points to memory address of a variable, just as a variable represents the memory address of value.

Let’s have a look at this program fragment

func main() {
        a := 200
        b := &a
        *b++
        fmt.Println(a)
}

On the first line of main we declare a new variable a and assign it the value 200.

Next we declare a variable b and assign it the address a. Remember that we don’t know the exact memory location where a is stored, but we can still store a‘s address in b.

The third line is probably the most confusing, because of the strongly typed nature of Go. b contains the address of variable a, but we want to increment the value stored in a. To do this we must dereference b, follow the pointer from b to a.

Then we add one the value, and store it back in the memory location stored in b.

The final line prints the value of a, showing that it has increased to 201.

Conclusion

If you are coming from a language with no notion of pointers, or where every variable is implicitly a pointer don’t panic, forming a mental model of how variables and pointers relate takes time and practice. Just remember this rule:

A pointer is a value that points to the memory address of another variable.

Next: There is no pass-by-reference in Go

Why Slack is inappropriate for open source communications

Full disclosure: my employer makes a Slack alternative. All my concerns about the use of Slack type chat services apply equally to its competitors, including my employer’s.

I’ve tweeted a few times about my frustration with the movement of open source projects from open, asynchronous, communication tools like forums, mailing lists, and issue trackers, to closed, synchronous communication services like Slack. This post is a long form version of my gripe.

The text of this post is also available in Russian (thank you Softdroid).

What is Slack good for?

Before I stick the boot in, let’s talk about the good things about synchronous chat applications like Slack, HipChat, and so on.

In a work context, chat applications take the place of @staff email blasts about fire system testing, broken lifts, and spontaneous availability of baked goods. This is a good thing as this kind of company spam is often impossible to unsubscribe from.

In the context of an open source project, Slack, HipChat, Gitter, etc, provide a forum for advocacy, gossip, informal discussion, and support. My complaints start when Slack and friends are promoted as the recommended way to communicate with the project.

Why is Slack bad for open source communication?

My complaint about the growing use of chat services like Slack, HipChat, and so on, for communication by open source projects is that these services are not open. As I see it there are two issues:

  1. Slack, et al, are paid services with closed memberships. Sure, there are lots of little apps running on Heroku dyno’s that automate the “send me an invite” process, but fundamentally these are closed systems.

    This means that the content inside those systems is closed. I cannot link to a discussion in a Slack channel in a tweet. I cannot refer to it in an issue report, and I cannot cite it in a presentation. Knowledge is silo’d to those who have the time and ability to participate in chat services in real time.

  2. Slack, et al, are based on synchronous communication, which discriminate against those who do not or can not take part of the conversation in real time. For example, real time chat discriminates against those who aren’t in the same time zone–you can’t participate fully in an open source project if all the discussion happens while you’re asleep.

    Even if you are in the same time zone, real time chat assumes a privilege that you have the spare time–or an employer who doesn’t mind you being constantly distracted–to be virtually present in a chat room. Online chat clients are resource hogs, and presume the availability of a fast computer and ample, always on, internet connection, again raising the bar for participation.

In my view these issues are inseparable. Calls to use IRC instead, miss the point that IRC is similarly real-time, just as efforts to create a post facto log of a Slack channel miss the fact that this is a record of a conversation which others cannot contribute equally. There is no solution for equitable open source communication that does not address both simultaneously.

Prefer asynchronous communication for open source projects

Instead of closed, synchronous, systems I recommend open source projects stick to asynchronous communication tools that leave a publicly linkable, searchable, url. The tools that fit this requirement best are; mailing list, issue trackers, and forums.

RC2017/4: Introducing Arudino6502

This weekend I polished up my Arduino Day project and published it to GitHub for Retrochallenge 2017/04.

Introducing Arduino6502

https://github.com/davecheney/arduino6502

The repository contains an Arduino sketch that can be loaded on Arduino Mega boards (Arduino Uno’s can be accommodated by lowering the RAMSIZE value).

The sketch includes ROM images for AppleSoft Lite and Krusader symbolic assembler.

To run AppleSoft BASIC, enter

\
E000R

And you will be dropped into the BASIC prompt

>

Remember that the Apple 1 was an upper case only machine, so you should enter all letters in upper case.

Krusader is available at $F000

\
F000R

What’s next?

The project currently targets the 8 bit Atmel chips due to the tight coupling between the Atmega 2560’s hardware serial port and the simulated 6821 PIA. The mapping is good enough that, as long as you insert a delay of 200ms or greater between newlines, you can paste HEX files into the Woz monitor and run the resulting program.

However, while the Apple 1 came with 4k or 8k of RAM, modern recreations like the Replica 1 assume at least 32k of RAM, making most of the software written for these nouveau Apple 1’s out of reach of this project.

To overcome this my next effort will be to port the project to run on Cortex-M platforms like the Teensy 3.x or Arduino Due to get access to more SRAM.

Retrochallenge 2017/04: 6502 on Arduino

This is my late entry for the 2017/04 retrochallenge. Notwithstanding my 2015 failure to launch, I plan to work on Arduino based emulators for various 6502 computers.

A few years ago I built an Arduino shield to host a real 6502 using the Arduino as RAM, PIA, and  glue logic. To some extent the software that this project ran was an afterthought, as it turned out the Apple 1 Woz monitor was perfect a proof of concept.

For the recent Arduino Day I brushed off my old code and reworked it to use an emulated CPU core so the sketch can run on an unadorned Arduino Uno or Mega.

For retrochallenge 2017/04 I plan to continue this work.

Roadmap

  • Clean up my sketch and publish the code to GitHub. I plan to target the Arduino Uno and Arduino Mega natively.
  • Hopefully add support for other monitors like Microsoft 8k BASIC.
  • Stretch goal: Rockwell made a 6502 variant called the R65F11 which was a 6502 with FORTH built into on chip ROM. Details are sketchy, but I found this pdf online and maybe if the ROM can be uncovered I can emulate that system.