Categories
Uncategorized

Tree Encoded Bitmaps

I’ve just found the paper Tree Encoded Bitmaps, which describes a nice mechanism for comprising bitmaps, somewhat similar to Roaring. This is something I use a great deal at work, where we store bitmaps of Piper changelists.

However, reading the paper makes me realize I need to do some data analysis first. The compression scheme is highly reliant on runs of 1-bits. In Piper, approximately half the changelists are “OCLs” which are renumbered into “NCLs” at submit time. This generated a very interleaved pattern of zeros and ones. So before investing any time in implementation, I should see how many runs of one’s we actually have.

Categories
Uncategorized

External Tests

I saw Eli Bendersky’s File-driven testing in Go post, and really like it. I was using something very similar yesterday. I’ve been attempting to replace a custom parser written in Python with an ANTLR one, with the goal being to run the same parser in both Python and Go. In order to do that, we need test cases that verify the old regex-based parser and the new antlr-based parser produce the same results. In order to do this, I moved all the test cases into a textproto (which is a common answer inside Google!). The output of the parser is another protobuf message, so we can include that directly.

test_case: {
  input: "some/valid/input"
  output: { … expected proto message inline … }
  want_error: false
}
test_case: { … }
// repeat as needed

The schema is pretty simple.

message TestCase {
  string input = 1;
  MyMessage output = 2;
  bool want_error = 3;
}

message TestCases {
  repeated TestCase test_case = 1;
}

This is trivially usable in the Go code, generating a subtest for each case.

func TestParse(t *testing.T) {
  data, err := os.Read("testdata/parser_test_cases.textproto")
  if err != nil { t.Fatal(err) }

  cases := &pb.TestCases{}
  if err := proto.UnmarshalText(data); err != nil { t.Fatal(err) }

  for _, tc := range cases {
    t.Run(tc.GetInput(), func(t *testing.T) {
      got, err := Parse(tc.input)
      if gotErr := (err != nil); gotErr != tc.getWantError() {
        t.Errorf("Parse() got err? %t want err? %t (err: %v)", gotErr. tc.GetWantError(), err)
      }
      if diffs := cmp.Diff(want, got, protocmp.Transform()) {
        t.Errorf("Parse() had unexpected differences (-want +got):\n%s", diffs)
      }
    })
  }
}

This makes it really easy to add new test cases, as I develop new parts of the ANTLR parser. The Python code is very similar to the Go code (both in the ANTLR and regex case). I was pleased to discover that Python has subtests along the way!

Categories
Uncategorized

Strava results 2021

I’m pretty happy with this overall! I certainly feel better for cycling more instead of commuting…

Categories
Uncategorized

2020W41

Yet another week of doing lots … but not necessarily the things I was tasked with. Plus it was my turn to be fire-fighter, which always means a lot of ad-hoc distractions.

While I did some coding, a great deal of time was taken up investigating data issues form our customers. The amazing ability of Dremel to query enormous datasets in realtime is a real bonus. But understanding the meaning behind the results can take a lot of time. One customer was complaining about seeing a huge jump in the number of changes to their project at a certain point earlier this year. I was able to track that down to a misconfiguration that they corrected at that time. For a moment, I was worried that I’d lost data for them!

Another customer was investigating how far back in time our dataset went. Looking at some strange results there revealed a bug in how our pipeline considered some jobs to be “in production”. This was simple to fix, but it required a sequence of three chained changes, each depending on deployment of the predecessor.

Probably the most important part of the week was a meeting with our new director to go over the metrics work we do. Lots of probing questions were asked (which is good!) that made us realise we needed to better understand who’s using the metrics we produce, and why they’re helpful. This is something that it’s easy to lose sight of when you’ve been building for a very long time.

Stats: 30 changes submitted, 53 reviewed

Categories
Uncategorized

2021W40

It was quite a busy week, but with not much focus on any one thing.

On the technical front, I deleted two (seemingly) unused fields from a very common configuration protobuf schema. Naturally, I didn’t catch all the field accesses, so there was a round of rollback / rollforwards.

I spent a large amount of time with the rest of my team reviewing old bugs in our backlog. This is something we do periodically, and I find it useful (if tiring). We get review all bugs over six months old in the backlog and see if they’re still applicable. Many times the issue has been superceded and is now obsolete. Sometimes it’s even been fixed!

Stats: 19 changes submitted, 39 reviewed.

Categories
Uncategorized

2021W39

Much of my time this week was taken up with a migration. We have a library internally at Google which does exactly what the new UnixMicro() and UnixMilli() in the time package does (but was available many years prior to 1.17). Initially, I started writing a “tip of the week” article about how they can be used. This quickly morphed into a “migrate everyone to the new functions” project. Thankfully, having everyone in a large monorepo helps enormously. I’ve now submitted 96% of the migration changes a couple of days after starting (using the large-scale-change aka LSC process).

Making the initial change was surprisingly simple, using a combination of codesearch and gofmt -r. I was lucky that I didn’t need anything more involved; however, I see that Eli Bendersky has an excellent introduction, Rewriting Go source code with AST tooling which would cover more advanced needs.

codesearch -l 'unixtime\.(To|From)(Micros|Millis)'
while read filename
do
  gofmt -r 'unixtime.ToMicros(a) -> a.UnixMicro()' "$filename" |
  gofmt -r 'unixtime.FromMicros(a) -> time.UnixMicro(a)' |
  gofmt -r 'unixtime.ToMilli(a) -> a.UnixMilli()' |
  gofmt -r 'unixtime.FromMillis(a) -> time.UnixMilli(a)' |
  goimports > "$filename.tmp" &&
  mv "$filename.tmp" "$filename"
done

I ended up with a change touching around 4100 files. The LSC tools split this up into around 250 changes, and I worked with an approver to get these reviewed and submitted over a couple of days. I can’t thank my approver enough for the diligent review of such tedious minor changes!

There were a few problems…

  • The main one that cropped up was the result of the goimports call above. In some cases, there were multiple files in the package, but the goimports above was only running on a single file, so I saw some unexpected imports for names that were pulled in from a different file in the same package. These were quickly identified and fixed, as they caused test failures!
  • One problem happened twice: a local variable named time shadowed the newly added import of the time package. This was trivially fixable with a local rename. Twice out of 4100 files is OK to do by hand.
  • In a few cases I discovered areas of code that had remained on Go 1.16 (temporarily). These broke very quickly when the tests were executed. I simply reverted these changes and will revisit them in a month or two.

Overall this is a pretty positive experience. I was able to upgrade a large swathe of Google’s code with fairly little fuss. Nobody asked me to do it — and I didn’t need to ask much in the way of permission. The end result is that code inside Google is more similar to code outside.

The main downside is that I should have been working on migrating a metrics pipeline, and instead I got a bit distracted by an interesting problem. Ah well.

Stats: 267 submitted (244 were the LSC described above), 30 reviewed

Categories
Uncategorized

2021W38

I was on vacation. I caught cold, and it was not that great.

I peeked at work on Friday and caught an interesting C++ code review. Changing from this:

template <typename T>
class SomeClass {
  …
  template <typename U>
  Add(U&& item) {
    add(SomeClass(std::forward(item)));
  }
  …
}

To this:

template <typename T>
class SomeClass {
  …
  template <typename U>
  Add(U&& item) {
    add(SomeClass(std::forward<U>(item)));
  }
  …
}

It’s quite subtle, and easy to miss by accident. In this case T=std::string and U=std::string_view. The initial version has a compilation error in this case, “no matching function for call to ‘forward’”. Thankfully, clang also points out that it can’t infer the template, which is a big clue.

My read is that SomeClass(std::string) can be constructed from a std::string_view. But the compiler doesn’t know it has a std::string_view unless we correctly parameterize the call to std::forward.

Categories
Uncategorized

2021W37

Something of a mixed week. I was the oncall person, so got to deal with a bunch of interesting failing things. Most interesting was an alert that one of our databases was approaching 70% of its disk quota. We weren’t in a position to get more, so I ended up designing a solution which would migrate the blobs out of the database. We don’t have time to implement this right now. But we have a reviewed design, and enough time to implement it before it’s a crisis.

The main thing I was supposed to be working on was designing a migration for the metrics system I work on. As happens so often, I ended up going down a rabbit hole trying to understand the source data. Bugs were filed … but not a lot of progress was made.

I filed my first bug against Chrome! The right click menu on a mac has grown a “Exit Full Screen” menu item right where “Back” used to sit. This led to me being frustrated two-to-three times per hour as I spend of my time in full screen mode.

Stats: 14 changes submitted, 39 reviewed.

Categories
Uncategorized

Code Review

One of the things I enjoy most at Google is code review. I don’t think anything else has improved me so much as an engineer. What I really value is that it’s an open discussion about how to make the system better, without personal prejudice. Being exposed to other people’s ideas is one of the clearest benefits of diversity: it forces you to think about another’s views and opinions.

Google’s setup for code review works well. All code must be reviewed before before it’s submitted to the codebase. You must have at least one other person read through the code. If there’s something that makes them go “huh?” it’ll come out. This is not (usually) a rubber stamping exercise. This really matters, as it means that knowledge is distributed instead of siloed.

One thing which I think is peculiar to Google is the notion of readability. This is the idea that our code should look fairly similar, no matter which project you’re on. It makes it much easier to move between teams, or jump into another teams codebase. This is enforced through the use of readability approvals, which is an incremental process where each code review must have approval from an expert in that language in addition to the regular review from your colleague.

I participate in the Go readability approvers, and it’s been a great experience. I see code from all over Google, and I help mentor folks not only in Go, but how we write Go inside Google. Sometimes it’s really trivial stuff: use a common library for creating a time.Time from microseconds. Other times it’s more structural: if you’ve designed a public API around channels, I might discuss to see if there’s a less error prone way. Often I learn quite a lot through these discussions!

Another benefit of code review is that it provides a common point for tooling. When a review is started, many tools have already triggered, starting all kinds of analyses. When I get to a review, I can immediately see that there’s an API being misused, or some configuration is incorrect. It’s far cheaper to correct these issues before the code is submitted.

Statistics: I’ve reviewed over 15,000 changes at Google.

Anyway, reviews are one of the most enjoyable parts of my job. I get to learn, as do the people I’m working with. And it’s over of the quickest ways to help unblock my colleagues.

Categories
Uncategorized

2021W36

Most of this week was follow-on from last week’s attempt to make a data pipeline read from a Spanner database. The configuration turned out to be quite the tricky thing to make work. But at least I solved it for everyone. And the improvements are worthwhile: the pipeline runtime has halved, and we’re now able to read much more recent data, as we’re not relying on exports of database backups. The key part to making this work is that the pipeline is using a new feature to access the underlying files that the database uses, instead of having to make an online query.

Aside from that, one highlight was a pair programming exercise with a colleague in the USA who was interested in learning Go. We managed to contribute an improvement in about an hour, which is great, and he’s now looking at making changes on his own.

I spent a great deal of time with my manager writing up a summary of what I’d done over the last six months. I find it hard to present a coherent, data driven picture of this (despite the effort of writing snippets each week, so I actually have something to base this on…)

Stats: 18 changes submitted, 47 reviewed.