How much memory do 10 million bools take up?

Short answer

10MB. This is 8x as large as the number of bits that I actually care about.

Details

In Go all elements of a slice are addressable. The smallest addressable unit being the byte, a slice of bools looks in memory like a contiguous sequence of bytes, containing only 1 useful bit per byte.

Image for post
Image for post
Memory representation of a large slice

The slice header itself (1 pointer + 2 integers) is negligible: its memory occupancy is dwarfed by the size of the backing array.

I suspected that on my 64-bit computer, the minimal addressable unit would be a 64-bit word, incurring a 64x overhead for each useful bit! …


Some data is best modeled as a bit set. For example, the essential information about which students successfully passed a test, out of 3000 students, consists in 3000 bits (375 bytes only).

Image for post
Image for post
3000 bits ≡ 375 byte ≡ 750 hex digits

It turns out that Go doesn’t have a Bitset type in the standard library!

Abstract type: interface

First, let’s say that a Bitset can be any type that implements these 3 methods:

type Bitset interface {
GetBit(i int) bool
SetBit(i int, value bool)
Len() int
}

It is not necessary in general to start with an interface type. …


Yesterday I opened the Logs page of my App Engine Standard application in the Google Cloud console to check a specific log, only to discover much more traffic than I expected.

Image for post
Image for post
Unexpected logs: many requests per second

Confirmation in the App Engine “Summary” dashboard:


Have you ever tried to design an algorithm to solve a problem on an input of arbitrary length n, and nailed it in only O(n) running time?

Sometimes it’s easy, like “Find the minimum in the following list of n integers”

Image for post
Image for post
A decorative asymptote

The inconvenient truth

Most of the time you actually don’t end up with a true O(n), but rather with O(n log n).

Think about it : whenever you can’t simply “look at an item and immediatly throw it away”, you’re pretty doomed. You need a random access to the n data, or at least be able to refer to each item individually. In order to refer to n elements, you need indexes or pointers of size (log n). …


gofmt is not only about formatting

TL;DR

$ gofmt -w -r 'strings.Index(a, b) >= 0 -> strings.Contains(a, b)' .

What I was trying to achieve

Until recently, Javascript didn’t have the includes method to test if a string b is a substring of a string a. The idiomatic way to test this was

if (a.indexOf(b) !== -1) {
// b is a substring of a
} else {
// a does not contain b
}

This doesn’t apply to Go, as we’ve always had string.Contains. However, it’s still possible to find the aforementioned JS idiom in a Go codebase:

    if strings.Index(s, "-") >= 0 {
// ...
}

Now I’d like to replace all occurrences of this form by the idiomatic call to strings.Contains. …


This story relates events that happened on September 26th, 2019. They are all true. A website that I built, “Programming Idioms”, hit the first page of the “orange site” (aka Hacker News). My cloud provider monitoring console let me find out if the sudden traffic had caused an outage or not. And the invoice a few days later taught me that running a service in the cloud is not a free meal.

Disclaimer 1: I currently work for Google Cloud. However, I had designed and deployed the website Programming Idioms before joining Google.

Disclaimer 2: This is a faithful report of my specific experience. It obviously doesn’t apply to any unrelated similar cloud projects. …


The Beta support for Go 1.11 on Google Cloud Functions has been announced last week. Here are a few details about the Dancing Gopher factory function that I tweeted about.

Image for post
Image for post

First, it’s easier to have some code already working on my local machine, before throwing it to GCF. A single source file is enough for a small sample like this one.

My program does basically 4 things:

  • Read a GIF file
  • Change the fur color
  • Add a caption inside each frame
  • Write the updated GIF file

I can start with a command-line Go program (gist):


TL;DR migrating to the new runtime is a good idea, give it a try!

I’ve been running a website on the App Engine standard go runtime for years (since ~2013), and I’ve always been thankful for how well it is managed by the cloud provider:

  • What I deploy simply keeps running.
  • I never care about OS security patches or database upgrades.
  • Scaling up and down is automatic.
  • The traffic (~6000 sessions/month) mainly fits within the generous free tier. I pay nothing for the server instances, for the Datastore and Memcache, and that’s basically all I need.

Serverless, before “serverless” was even a word! …


In this article about the Go race detector, I emphasize that violating the Memory model with unprotected concurrent accesses is a serious error.

I must add that fixing the data races doesn’t make a program execution trace deterministic. There can still be “races” in the sense of “first goroutine that takes a lock accesses first”, in an order that can’t be predicted.

Consider this program:

The race detector doesn’t emit any warning during its execution, as the write accesses to a are properly serialized thanks to the mutex mu.

$ go run -race not-racy.go
33

However, 2 goroutines are effectively racing to access the shared variable a. The lock guarantees that one of the accesses will always happen-before the other access. The specific order of the accesses may change the next time the program is executed. …


TL;DR: it detects the data race conditions when they occur.

The Data Race Detector is a grand, invaluable feature of the go tooling. Today I want to clarify its investigation power.

Image for post
Image for post

What is a data race?

A data race occurs when two goroutines access the same variable concurrently and at least one of the accesses is a write.

Data races exist in go

It is possible to write incorrectly synchronized code and compile it. The compiler regards it as valid and doesn’t emit any warnings or errors for data race bugs.

However, these bugs are real and lead to undefined behavior, which can be a crash, or a silent incorrect behavior, or the silent correct behavior “by chance”. …

About

Val Deleplace

Engineer on cloudy things @Google. Opinions my own. Twitter @val_deleplace

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store