I’m going to try my hand at being a serious contributor to open source. This could be neat, or it could just be a one-off and fizzle. Time will tell.

I’ve contributed on-and-off to open source throughout the years – minor patches to dozens of projects, or to various repositories for work. However, I’ve never been deliberate about it. I’ve always liked writing code in my spare time, but I wouldn’t really call this “developing software”. That’s been reserved for work time.

Now that I’ve been in the industry for a decade, I’m finding myself yearning for my time spent coding to have some meaning: contribute to things other people find useful, interact with people, and build something bigger than I ever would alone.

Getting my feet wet

So the past week I opened on issue and wrote 9 pull requests across 4 repositories.

Open Location Code

google/open-location-code

• https://github.com/google/open-location-code/pull/749
• https://github.com/google/open-location-code/pull/750
• https://github.com/google/open-location-code/issues/751
• https://github.com/google/open-location-code/pull/752

Open Location Code is a multi-language library for encoding latitude/longitude locations in a format that is both human-readable and efficient for computers to search.

I’ve previously contributed some performance optimizations to the Go Encode implementation, so my first bit of work in getting back into things was contributing a performance optimization to the Decode implementation. Rather than bombard the maintainers with a single mega-optimization PR or a bunch of smaller ones at once, I’m going to do those piecemeal. So I really have about 3-4 lined up after that one, but I’ll wait for that first one to get merged to start sending the others.

The other two PRs (and issue) are addressing things I found while doing optimizations – making logic consistent across the library’s eleven(!) implementations and adding Rust to be covered in the testing instructions.

go-cmp

google/go-cmp

• https://github.com/google/go-cmp/pull/389
• https://github.com/google/go-cmp/pull/390
• https://github.com/google/go-cmp/pull/391

go-cmp is a test library for Go that provides nice quality-of-life functions for comparing objects for semantic equality and printing nice differences to aid in debugging.

My first contribution here was pretty minor – I noticed there were some calls to deprecated methods, so I updated them. That got merged very quickly (within a day!), so I decided to look around for other things that needed doing.

I found two TODOs that I could easily resolve, so I quickly wrote and sent two more PRs. They were approved, but confusingly haven’t been merged. This isn’t uncommon – much of open source maintenance is voluntary, so there’s no expectation of a fast turnaround. It’s plausible since I now have “contributor” next to my name the reviewer may have though I have merging rights. I’ll ping in a week if there’s no movement.

go-licenses

google/go-licenses

• https://github.com/google/go-licenses/pull/338

go-licenses is a license checker for Go repositories. Since open source projects can have just about any license, it’s important to make sure you only depend on projects that have licenses you’re fine with. In particular, many companies like Google use this to ensure their projects don’t depend on unapproved licenses that may cause intellectual property problems.

In looking through the library I noticed one of the subcommands of the CLI uses os.Open to check if a file exists. This potentially creates a file handler that then needs to be closed. Instead, os.Stat is better as it can be used to check for a file’s existence without opening it.

This PR is a bit of a stretch – it’s a pretty minor improvement, and following the repo’s test patterns made it pretty big for what it is. I’m curious what the response will be.

keep-sorted

google/keep-sorted

• https://github.com/google/keep-sorted/pull/122

keep-sorted is another of those tools used by a huge number of projects. It’s used across the Google and open source ecosystems to do a fairly simple – but important – task: keep lists of things sorted. Scanning a list of tens, hundreds, or (yes) thousands of items to see if something exists, or to see the changes between two lists, is difficult for humans looking at unsorted lists. Consider how much easier it is to tell which letter of the alphabet is missing from a list of letters if they are randomized versus if they are in order:

• XWKGZUYJVMSQTREFPBDIALONC
• ABCDEFGIJKLMNOPQRSTUVWXYZ

For this repo, I looked for an open issue that seemed to have maintainer support and found https://github.com/google/keep-sorted/issues/80. Basically, someone wanted to know if the feature that skips lines at the start of a list could be extended to also support skipping lines at the end. A maintainer expressed support for the idea, but hasn’t implemented it yet. So, I made a quick change that added that feature. I only did this one today and I see the project has been updated fairly recently – I’m hopeful this one will be reviewed pretty soon.

Reflecting on “Successful Repositories”

In my time within academia, part some of the work I studied was on understanding open source. I think there’s a lot that academics could learn by seriously interacting with the open source community. The past week I’ve been thinking about how the work I read measured things like “success”. I’m going to avoid citing particular papers – if I ever do something like that it’ll be in a more formal work.

I consider all four repositories I worked on to be extremely successful, but they “fail” at quite a few of the success metrics used in academic works.

A common metric for measuring success is the number of recent commits/contributors. This is usually measured as the number of times code has been merged into the main repository, or the number of unique people who have made code contributions. On the surface – this seems to make sense: shouldn’t “successful” repositories constantly be having lots of code sent to them, and by lots of different people? I’d consider go-cmp to be a hugely successful repository, but it doesn’t even have 200 commits over its almost 10 year life! The thing it’s doing – showing the difference between objects – is simple, elegant, and hugely useful. It’s used extensively. The tight scope of what the repository is trying to do (and the low reliance on volatile dependencies) means it simply rarely needs changes.

Instead, I think “success” is unique to what a repository is trying to do. Something like go-licenses is pretty simple and doing a useful thing well, and so it sees a lot of use. It’s often not even a code dependency (one where it is called as a library) – but a workflow one (it is used as a tool), messing up another common success metric! Conversely, repositories like some of the ones for Kubernetes see thousands of commits per year, and they would be unsuccessful without that. Kubernetes is a huge infrastructure project that has to integrate with an enormous number of other pieces of software and do some really complicated tasks well enough for people to trust to billions of dollars of infrastructure. And, most projects that depend on Kubernetes don’t directly rely on its code – they rely on machines running its code for them.

There is a notion of use here (all of the projects I’ve mentioned above are used by thousands of projects), but also one of self-determination. A project’s goal can tell us a lot about what it is trying to do, and whether it is achieving that. Projects differ in how they are designed to be used.

I have more thoughts (What makes a “healthy” repository? What things make a repository attractive to a newcomer? How do you get started in open source?), but they don’t fit cleanly here. I’ll have to cover them another time.

Next Time?

This was a fun week, and I’ve got the next week off from work for my move, so I’ll probably spend some of my free time doing more hacking on open source. We’ll see.

This problem is also from Cracking the Coding Interview, from Chapter 2.

Write code to remove duplicates from an unsorted linked list. How would you solve this problem if a temporary buffer is not allowed?

This is one of the classics that I’ve been very interested to see if there are significant performance improvements to be made over the naive solutions. The restriction in the second sentence of the question eliminates the potential usage of interesting data structures, but still has interesting optimization properties so I’ll handle that in a separate post.

Initial Clarifications

Linked lists don’t inherently contain information at each node, but we can reasonably infer from the problem state that in this case “duplicates” refers to two nodes with the same information.

I’ll use integers as the data type. In practice, if the data held by each node were complex, or if it were otherwise time-consuming to determine equivalence, then it would be worth considering optimizing to minimize the number of comparisons. For now I’ll just use integers as the data type since that comparison takes very little time.

For the linked list itself we don’t need anything complex. I’ve added a convenience method to compute the length of a list as it’s used in many obvious optimizations. Linked List Code.

type Node[T comparable] struct {  
  Value T  
  Next  *Node[T]  
}  

func (n *Node[T]) Length() int {  
  length := 0  
  for ; n != nil; n = n.Next {  
   length++  
  }  
  return length  
}

The Naive Map Solution

First – and the expected solution in interviews – is one that uses a map to record the set of seen integers. In the benchmark I’m assuming effectively no duplicates to make this a sort of worst-case scenario (rand.Int to produce random positive int). Test and Benchmark Code.

// RemoveDuplicatesMap removes entries from a linked list with the same value.
// Uses a map to record seen values.  
func RemoveDuplicatesMap(head *Node[int]) {  
  if head == nil {  
   return  
  }  

  seen := make(map[int]bool, head.Length())  

  for ; head != nil; head = head.Next {  
   seen[head.Value] = true  

   for head.Next != nil && seen[head.Next.Value] {  
    head.Next = head.Next.Next  
   }  
  }  
}

The Manual Hash Set Solution

Go’s maps are far more robust than is required for this problem, potentially meaning they have expensive overhead handling things like general-purpose hash functions and collision-handling logic.

So what if we create our own implementation that doesn’t do any of that? In our case, since we know integers are bitwise-random, we can use a modulus as the hash function. If we limit the map size to only powers of 2, this is equivalent to the (much faster) & operation with a bit mask. The backing array holds the seen integers, and on hash collisions we increment to find the first available slot. Finally, we make the HashSet about twice as large as we need so collisions are infrequent (so 2048 keys for lists of size 1000, not 1024). HashSet Code. Solution Code.

// HashSet is a statically sized hash set of integers which uses
// the ending bits as a hash.  
type HashSet struct {  
  mask   int  
  values []int  
}  

// NewHashSet constructs a HashSet which can contain up to 2^size entries
// and initializes it with value.  
func NewHashSet(size, value int) *HashSet {  
  result := &HashSet{  
   mask:   1<<size - 1,  
   values: make([]int, 1<<size),  
  }  
  result.values[value&result.mask] = value  

  return result  
}  

// Insert adds the value to the set.
// Returns true if the value is already present.  
// Does not handle the case where the set is full and a new value is added.  
func (m *HashSet) Insert(value int) bool {  
  idx := value & m.mask  
  for m.values[idx] != 0 {  
   if m.values[idx] == value {  
    return true  
   }  
   idx = (idx + 1) & m.mask  
  }  
  m.values[idx] = value  

  return false  
}

Comparing the two via benchmark yields dramatic results – our manual implementation of a hash set is about 4x faster! Unsurprisingly (found via the “-benchmem” flag), HashSet only has one memory allocation to Map’s 33, and uses about 10% less memory despite preemptively allocating twice the number of keys.

	Map	HashSet
List Size	ns/op	ns/op	Change
100	5,610	1,495	73.35%
1,000	52,836	9,664	81.71%
10,000	562,210	131,242	76.66%

There’s some interesting sub-linear behavior around 1,000 elements for both solutions, but I don’t have a good explanation for it. It’s nowhere near a cache size boundary and the memory requirement is too large for a single page on my machine.

Conclusion

As is generally the case, a brittle manual solution wins out over a general-purpose one. You wouldn’t want to use this HashSet implementation in production code – you’d likely want additional guardrails (such as tracking collisions to know when to automatically increase in size), which would cost additional processing power. It is still neat to see a recreation of the idea of what hash maps are doing, and it’s surprising that using maps in Go incurs so much overhead. As always, don’t try something like this unless you’ve actually benchmarked and measured that it is a problem for your use case!

This was fun, and I may explore some alternative solutions to this problem that I messed around with in the future.

This next problem also comes from Cracking the Coding Interview.

Problem 3: Given two strings, write a method to decide if one is a permutation of the other.

Easy Solution

The expected solution here is, of course, straightforward as this is meant as an easy interview question. For each string, create a map from each character in the string to the number of times the character appears. Then, compare the maps.

Naturally, the AI autocomplete gives an incomplete solution.

// Solution3A uses a straightforward solution using character counts.
// Autocompleted solution.  
func Solution3A(left, right string) bool {  
  leftCounts := make(map[rune]int)  
  for _, r := range left {  
   leftCounts[r]++  
  }  

  rightCounts := make(map[rune]int)  
  for _, r := range right {  
   rightCounts[r]++  
  }  

  // Autocomplete begins here.  
  for r, lc := range leftCounts {  
   rc, ok := rightCounts[r]  
   if !ok || lc != rc {  
    return false  
   }  
  }  

  return true  
}

While at first glance it isn’t obvious what is wrong, a careful check should reveal that this code does not handle the case where there are characters present in right which are not present in left. We can verify this bug with tests:

func TestSolution3(t *testing.T) {  
  tt := []Problem3TestCase{  
   {name: "empty", left: "", right: "", want: true},  
   {name: "left empty", left: "", right: "a", want: false},  
   {name: "right empty", left: "a", right: "", want: false},  
  }  

  for _, solution := range solution3s {  
   for _, tc := range tt {  
    if got := solution.F(tc.left, tc.right); got != tc.want {  
     t.Errorf("%s(%q, %q) = %v, want %v", solution.Name, tc.left, tc.right,
       got, tc.want)  
    }  
   }  
  }  
}

The fix is to ensure this can’t happen by checking the character sets.

// If the lengths of the character counts are unequal, then a character is
// missing from one string.  
if len(leftCounts) != len(rightCounts) {  
  return false  
}

Together, verifying the key sets are of equal size, and checking the equivalence of all counts of keys one set are equivalent to the other is sufficient to ensure the strings are permutations. (We don’t need to do a symmetric check.)

There’s an even faster possibility, though.

// Strings of different lengths cannot have the same counts of characters.  
if len(left) != len(right) {  
  return false  
}

We can exit early when strings are of unequal lengths. This covers all cases for the key set size check, is faster, and exits before we create the maps so it is obviously better.

Benchmarking

But … how much better can we do? As with any optimization problem, we should define what “normal” input looks like before committing to this. As with Problem 1, we’ll make the initial simplifying assumption that all characters are ASCII.

We need to decide how we’re going to benchmark this.

It isn’t interesting to benchmark the case of strings of unequal lengths since it’s just a string length check and there’s nothing to optimize, so for our benchmarks .

The case of nearly equal strings will look significantly different from the case where strings are completely different. So we should have one benchmark for strings we know are permutations, and one where it they aren’t (or at least, it is unlikely).

Map iteration in Go is random, so sometimes nearly equal strings will still be identified as such immediately, and for others it may take until the last iteration. We can’t really do anything about this so long as solutions involve maps, but it is a source of randomness that we should be aware of.

As we’ve seen, autocomplete does tend to get things reasonably right. In this case autocomplete did successfully figure out that I wanted to generate slices of data, incorporating functions I’d written in the same package (RandomString and RandomASCII). It just – amusingly – didn’t create a source of randomness, instead invalidly passing nil.

lengths := []int{1, 2, 5, 10, 20, 50, 100}
// Begin autocomplete
data := make([]LengthData, len(lengths))  
for j, length := range lengths {  
  data[j] = LengthData{length: length, data: make([]string, n)}  
  for i := 0; i < n; i++ {  
   data[j].data[i] = RandomString(nil, length, RandomASCII)  
  }  
}

The naive solutions are actually surprisingly slow:

BenchmarkS3Different/Solution3A2/1-16         10935601           100.3 ns/op
BenchmarkS3Different/Solution3A2/2-16          9316386           121.7 ns/op
BenchmarkS3Different/Solution3A2/5-16          5554606           209.3 ns/op
BenchmarkS3Different/Solution3A2/10-16         1032976          1103 ns/op
BenchmarkS3Different/Solution3A2/20-16          431102          2719 ns/op
BenchmarkS3Different/Solution3A2/50-16          185488          6323 ns/op
BenchmarkS3Different/Solution3A2/100-16          84954         13117 ns/op
BenchmarkS3Permutation/Solution3A2/1-16       10739696           105.8 ns/op
BenchmarkS3Permutation/Solution3A2/2-16        8149945           147.3 ns/op
BenchmarkS3Permutation/Solution3A2/5-16        3648794           321.4 ns/op
BenchmarkS3Permutation/Solution3A2/10-16        919902          1307 ns/op
BenchmarkS3Permutation/Solution3A2/20-16        379916          3124 ns/op
BenchmarkS3Permutation/Solution3A2/50-16        142298          7322 ns/op
BenchmarkS3Permutation/Solution3A2/100-16        78962         14562 ns/op

We’re taking around 100 ns to process each character, which is about 10 MB/s. So this solution could easily be a performance bottleneck in a system.

There’s also a few surprising properties the benchmarks reveal:

1. There is a huge jump from 5 character strings to 10. This is likely due to needing to reallocate the array underlying the map when it grows beyond 8 keys.
2. There isn’t a huge difference between checking strings which are permutations from strings which are not. The largest difference is at strings of length 5, a 50% increase, but is otherwise 5%-10%.

The Array Solution

Given the massive success of arrays for Problem 1, does a similar optimization here also work?

func Solution3B(left, right string) bool {  
  if len(left) != len(right) {  
   return false  
  }  

  counts := make([]int, 128)  
  for _, r := range left {  
   // Keep track of character counts.  
   counts[r]++  
  }  
  for _, r := range right {  
   // If we see a character and there isn't at least one unaccounted for,
   // we can exit immediately.  
   if counts[r] < 1 {  
    return false  
   }  
   // One instance of this character in left is now accounted for in right.  
   counts[r]--  
  }  

  return true  
}

Instead of tracking the two sets of keys and counts in separate maps, we track counts in a single array that can handle any character from 7-bit ASCII. This has the advantage of not needing to use maps, and requires a single 1kb memory allocation.

With memory allocations, what really matters is the number of times you request memory rather than the amount, when making requests smaller than a – normally 4kb – page of memory. Further, we’re only referencing a single heap-allocated object – the counts slice – rather than two maps.

These results are much better – from 5x faster for small strings to about 100x faster for long strings.

BenchmarkS3Different/Solution3B/1-16         63929632            18.74 ns/op
BenchmarkS3Different/Solution3B/2-16         59162731            19.68 ns/op
BenchmarkS3Different/Solution3B/5-16         51334929            22.14 ns/op
BenchmarkS3Different/Solution3B/10-16        39485048            27.82 ns/op
BenchmarkS3Different/Solution3B/20-16        29531452            37.35 ns/op
BenchmarkS3Different/Solution3B/50-16        14044939            82.91 ns/op
BenchmarkS3Different/Solution3B/100-16        8684762           136.2 ns/op
BenchmarkS3Permutation/Solution3B/1-16       61517580            18.67 ns/op
BenchmarkS3Permutation/Solution3B/2-16       58104522            20.36 ns/op
BenchmarkS3Permutation/Solution3B/5-16       44546454            26.14 ns/op
BenchmarkS3Permutation/Solution3B/10-16      30614641            35.46 ns/op
BenchmarkS3Permutation/Solution3B/20-16      19843489            55.30 ns/op
BenchmarkS3Permutation/Solution3B/50-16       8272191           142.4 ns/op
BenchmarkS3Permutation/Solution3B/100-16      4962151           243.1 ns/op

These results are around 1-2.5 ns/character, so we’re at a processing speed that is significantly faster than data transfer or disk reading.

I tried some other possible optimizations – such as using a raw array instead of a slice for counts, but this didn’t cause any noticeable improvement. This is unsurprising as we allocate the same amount of memory for all cases. The cpu profile also doesn’t suggest any obvious avenues of improvement:

There aren’t obvious interesting changes to make without moving to Unicode, so this seems like a good place to stop.

I’m preparing to go back on the software job market, and to sharpen my skills I’m going back through books I initially worked through as a novice. I’ve got over a decade more experience now, and so I want to approach these problems as a seasoned developer – to try and find something more interesting than just solutions to problems that could be uncovered in half an hour.

To begin, I’m starting with Cracking the Coding Interview, by Gayle Laakmann McDowell.

“Problem 1.1 Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?”

The first part of this question is straightforward to do with a hash map. In fact, it’s so straightforward that generative AI can get you most of the way towards the answer.

// Solution1A is a straightforward attempt to solve the problem with a hashmap.
func Solution1A(s string) bool {  
  seen := make(map[rune]bool)  
  for _, r := range s {  
   if seen[r] {  
    return false  
   }  
   seen[r] = true  
  }  
  return true  
}

Benchmarking

This wouldn’t be a fun exploration of the problem if we didn’t include some benchmarks. Suppose this uniqueness-detecting algorithm were in a location critical to performance. How well do we do, and can we do any better?

So we need some test data. Ideally test data for benchmarking reflects actual call patterns. Since the input data are strings, the main properties of the input that matter for performance are:

1. the distribution of string lengths,
2. the set of possible characters, and
3. the distribution of characters.

Possible length distributions:

1. All the same
2. Uniform in a range
3. Poisson distribution (English word lengths appear to have this distribution)
   1. https://www.sciencedirect.com/science/article/abs/pii/0378375886901692

Possible character sets:

1. All-caps letters (26 possibilities)
2. Upper and lowercase letters (52 possibilities)
3. All printable ASCII (95 possibilities)
4. All Unicode characters as of Unicode 16.0 (155,063 possibilities)

Possible character distributions:

1. Uniform distribution
2. Pareto distribution (similar to actual text?)

Like with any good optimization problem, different choices here may result in different optimal solutions. Some may even completely eliminate certain solutions.

To start, we’ll go with:

1. All strings are of length 12
2. All characters are printable ASCII
3. All characters are equally likely

Twelve is a nice number of characters to begin with as approximately half of all strings will have a repeated character. Using the birthday problem formula, we can see:

95!
---        x 95^12 ~= 0.484
(95-12)!

For the benchmark we’ll generate 1,024 random strings, and cycle through evaluating them.

const (  
  n     = 1 << 10  
  nMask = n - 1  
)  

func BenchmarkSolution1(b *testing.B) {  
  rng := rand.New(rand.NewSource(time.Now().UnixNano()))  

  randomStrings := make([]string, n)  
  for i := 0; i < n; i++ {  
   randomStrings[i] = RandomString(rng, 12, RandomASCII)  
  }  

  for solution, f := range solutions {  
   b.Run(solution, func(b *testing.B) {  
    for i := 0; i < b.N; i++ {  
     f(randomStrings[i&nMask])  
    }  
   })  
  }  
}

Hash Map Solution

As it turns out, while our initial solution works, it’s pretty slow for what it does:

BenchmarkSolution1/Solution1_A
BenchmarkSolution1/Solution1_A-64              1958344           602.7 ns/op

So … why is it slow? For this, we turn to the handy builtin profiler that allows is automatically enabled during testing.

go test ./chapter1/ -run=NONE -bench=BenchmarkSolution1/Solution1A -cpuprofile=cpu.out

The big things to notice here are:

1. Only 89% of the time is Solution1A running (chapter1.Solution1A)
2. 68% of the time is creating new entries in the map (runtime.mapassign_fast32)
3. 16% of the time is accessing map entries (`runtime.mapaccess1_fast32)
4. 2% of the time is unavoidable runtime calls (runtime.rand)

Note that the call to runtime.rand is not related to the benchmark setup code – you can see this for yourself if you remove the random string generation, the call is still present in the profile.

So in total, 84%/89%, or 94% of our time is spent dealing with the hash map. Even if we made all other parts of our logic free – taking zero time – at best we could save 36ns out of over 600ns. If there is an improvement, it’s either in how we’re using the hash map or just the fact that we are using a hash map.

For better ways of using the hash map – we could try reducing the size of the keys, or preallocate the map so it doesn’t ever need to be reallocated. In the first case, the idea is to reduce the size of the map’s keys, possibly saving time in memory allocation and in the runtime of the hash algorithm. For the latter we preallocate the map at size 12 (which it should never grow beyond, as strings have exactly 12 characters), saving that time. Implemented:

// Solution1A1 is a slight modification to Solution1A where runes are reduced to
// bytes as all are assumed to be ASCII.  
func Solution1A1(s string) bool {  
  seen := make(map[byte]bool)  
  for _, r := range s {  
   if seen[byte(r)] {  
    return false  
   }  
   seen[byte(r)] = true  
  }  
  return true  
}  

// Solution1A2 is a slight modification to Solution1A where maps are initialized
// to size 12 to avoid needing to reallocate the underlying array.  
func Solution1A2(s string) bool {  
  seen := make(map[rune]bool, 12)  
  for _, r := range s {  
   if seen[r] {  
    return false  
   }  
   seen[r] = true  
  }  
  return true  
}

Trying these with our benchmark:

BenchmarkSolution1/Solution1A-64              2068266           617.7 ns/op
BenchmarkSolution1/Solution1A1-64             1332189           939.7 ns/op
BenchmarkSolution1/Solution1A2-64             2088864           572.0 ns/op

We can see that there is a notable regression for converting runes to bytes, and a slight improvement for avoiding reallocating the map. (I tried other values, such as 11, and saw no further improvement)

There could be other improvements using Go’s native hash map, but I’m not aware of them.

Array Solution

Notice that we have a fairly small number of possible characters – 95. Also notice that their byte values range from 32 to 126, all under 128. Thus, if we initialized a bit array of length 128, we could store in that whether we’ve seen a character corresponding to each value.

// Solution1B is like the above but uses a bit array.
func Solution1B(s string) bool {  
  seen := make([]bool, 1<<7)  
  for _, r := range s {  
   if seen[r] {  
    return false  
   }  
   seen[r] = true  
  }  
  return true  
}

We can immediately see a drastic improvement:

BenchmarkSolution1/Solution1A-64              1892926           626.3 ns/op
BenchmarkSolution1/Solution1A1-64             1231104           948.8 ns/op
BenchmarkSolution1/Solution1A2-64             2023808           573.0 ns/op
BenchmarkSolution1/Solution1B-64             82965651            13.96 ns/op

Our bit array is about 50x faster than our hash map solution. Looking at the CPU profile, we can see that nearly all of the time is spent in the solution logic (0.94s of 0.96s) – any potential gains are likely in the code of that function.

But what gains are even possible?

One possibility is avoiding the heap allocation incurred by defining a slice instead of using an array directly.

// Solution1B1 is like the above but uses an array directly instead of a slice.
func Solution1B1(s string) bool {  
  var seen [1 << 7]bool  
  for _, r := range s {  
   if seen[r] {  
    return false  
   }  
   seen[r] = true  
  }  
  return true  
}

This results in a slight (but reliable) slowdown:

BenchmarkSolution1/Solution1B-64             89289081            13.75 ns/op
BenchmarkSolution1/Solution1B1-64            84424354            13.90 ns/op

Another possibility is to avoid allocating the slice with each call, instead copying empty data into it.

var (  
  seenC  = make([]bool, 1<<7)  
  seenC2 = make([]bool, 1<<7)  
)  

// Solution1B2 is like the above but uses an array directly instead of a slice.
func Solution1B2(s string) bool {  
  copy(seenC, seenC2)  
  for _, r := range s {  
   if seenC[r] {  
    return false  
   }  
   seenC[r] = true  
  }  
  return true  
}

This option also results in a slowdown, larger than before:

BenchmarkSolution1/Solution1B-64             89082355            13.53 ns/op
BenchmarkSolution1/Solution1B1-64            88801987            13.77 ns/op
BenchmarkSolution1/Solution1B2-64            76817073            15.82 ns/op

Alternatively, we could even hard code the number of iterations (since we know every string is of length 12). The idea here is that it avoids a quirk of how Go iterates over strings.

// Solution1B3 is like 1B but iterates a static number of times.
func Solution1B3(s string) bool {  
  seen := make([]bool, 1<<7)  
  for i := 0; i < 12; i++ {  
   r := s[i]  
   if seen[r] {  
    return false  
   }  
   seen[r] = true  
  }  
  return true  
}

This does result in a noticeable speedup, at the cost of making the code more brittle. It isn’t obvious to me why there is a speedup. It could be that creating the (index, rune) tuple is expensive, or it could have to do with how Go checks if it is done iterating.

BenchmarkSolution1/Solution1B-64             85514907            14.02 ns/op
BenchmarkSolution1/Solution1B1-64            83047393            14.11 ns/op
BenchmarkSolution1/Solution1B2-64            74333500            16.27 ns/op
BenchmarkSolution1/Solution1B3-64            97826607            12.03 ns/op

However, we don’t actually have to make the code brittle to realize the same gain.

// Solution1B4 is like 1B but uses the string length to set the number of iterations.
func Solution1B4(s string) bool {  
  seen := make([]bool, 1<<7)  
  for i := 0; i < len(s); i++ {  
   r := s[i]  
   if seen[r] {  
    return false  
   }  
   seen[r] = true  
  }  
  return true  
}

In fact, this is even faster than the hard coded length. I suspect there’s a compiler optimization, since it would seem like recalculating the length of s every iteration would take longer than just comparing to a compile-time constant.

BenchmarkSolution1/Solution1B-64             86110658            14.15 ns/op
BenchmarkSolution1/Solution1B1-64            86076312            14.01 ns/op
BenchmarkSolution1/Solution1B2-64            72450708            15.67 ns/op
BenchmarkSolution1/Solution1B3-64            99203356            11.65 ns/op
BenchmarkSolution1/Solution1B4-64            104699756           11.10 ns/op

That’s about as far as I want to take the bit array solution. What about the other part of the question – the part I’ve ignored until now?

No Additional Data Structures

“What if you cannot use additional data structures?“

For Go in particular, this is tricky as strings are immutable. This means that a natural solution – to sort the characters of the string and then check for duplicates – isn’t possible.

If you iterate through a string, you’ll notice that you get the 4-byte rune type rather than the 1-byte byte type you get by indexing a string. In this case, it doesn’t matter as for now we’re assuming all characters are ASCII. Which means we can just index the string, even though that would be problematic if the system we’re designing for might ever encounter non-ASCII.

// Solution1C avoids using other data structures by directly comarping pairs of characters.
func Solution1C(s string) bool {  
  for i := 0; i < len(s); i++ {  
   for j := i + 1; j < len(s); j++ {  
    if s[i] == s[j] {  
     return false  
    }  
   }  
  }  
  
  return true  
}

Surprisingly this solution isn’t terrible compared to the other solutions:

BenchmarkSolution1/Solution1B4-64 103588170 11.66 ns/op
BenchmarkSolution1/Solution1C-64 39652282 28.48 ns/op

In fact, this solution *always* beats the hash map solution, despite technically having O(n^2) complexity. At 100-character strings:

BenchmarkSolution1/Solution1A2-64 1279503 940.2 ns/op
BenchmarkSolution1/Solution1B4-64 84820020 13.66 ns/op
BenchmarkSolution1/Solution1C-64 31667222 37.01 ns/op

At 1,000-character strings:

BenchmarkSolution1/Solution1A2-64 1247774 958.0 ns/op
BenchmarkSolution1/Solution1B4-64 79115478 15.28 ns/op
BenchmarkSolution1/Solution1C-64 31556229 38.59 ns/op

This is because of a fundamental limit of our problem – there are at most 95 unique characters, and so despite being an O(n^2) solution, comparing every pair of characters is faster as we exit early.

Pareto Distribution

Suppose characters occur with a frequency following a Pareto distribution. There’s a lot of debate on how to model this properly, so here I’ll pick parameters that seem to fit a letter distribution chart. What matters more is seeing what happens when there’s a small number of characters that are chosen more often than others, but still a good number of the less frequent. If you’re interested in replicating, I’ve gone with X_m=3.0 and alpha=0.45, then offset the results by -3. The results aren’t too awful and result in a more long tail distribution than actual letters, which means any measurements here are likely to be overestimates.

Perhaps unsurprisingly, all solutions perform better in this case. Given that some characters are much more common, there’s a significant likelihood of a common character appearing as the first or second character, and then again later in the string – so generally the logic allowing the algorithms to exit early triggers sooner than if characters are distributed uniformly.

BenchmarkSolution1/Solution1A2-64             2115301           563.4 ns/op
BenchmarkSolution1/Solution1B4-64            106364142           11.02 ns/op
BenchmarkSolution1/Solution1C-64             38778128            29.50 ns/op
BenchmarkSolution1P/Solution1A2-64            3728235           327.9 ns/op
BenchmarkSolution1P/Solution1B4-64           193359403            5.491 ns/op
BenchmarkSolution1P/Solution1C-64            226532450            5.123 ns/op

As a surprise, the apparently O(n^2) solution is actually the fastest compared to the others when given data that better approximates actual text! This should reinforce both that:

• the time-complexity of an algorithm should not be the sole determiner of which algorithm is best, and
• measuring, especially with simulations of real world data, can change which algorithm is best for an application.

In Context

So we’re evaluating these strings for repeated characters, but where do these strings come from? At 5 or 11 ns/op, how likely is this the bottleneck?

Let’s hand wave away any sort of parsing (e.g. JSON parsing is very slow) – we’re either getting this as a raw byte stream from a connection, or we’re reading raw text from a file on disk.

Consider the slower option – uniformly distributed ASCII characters in strings of length 12, since that gives a nice 1 byte/ns processed. A quick conversion shows this is equivalent to about 1 GB/s. For comparison, a mid-range SSD reads about 500 MB/s, and a gigabit connection is only 125 MB/s. So at that speed, it’s no longer a significant bottleneck.

Considering the hash map solution – even in the more lenient case of the non-uniform distribution, we get 12 bytes / 328 ns, which is about 36.6 MB/s. This is slow enough that it could reasonably be a bottleneck if almost nothing else is happening in the application.

Conclusion

There was a lot here, just looking at this problem from the perspective of Go. The O(n^2) solution being the best for normal-looking data surprised me – it strikes me as the kind of finding that’s interesting to bring up in an interview setting.

I doubt there’s more to be gained from this particular perspective at the problem. Next time I may consider other languages (like Python or Rust), or consider what happens if the characters could be any valid Unicode 16.0. Python and Rust may allow trying the sorting algorithm approach, and Unicode likely would make the byte array solution invalid. But validating that is what benchmarking is for!

My instinctual response to rage at a system is an urge to systematically deconstruct its power.

The Scam

March 17th, 2022

While it may have begun sooner, the “look who just died” scam entered the Internet’s consciousness on March 17th, 2022 with a Reddit post on r/answers. The user reported that they received a message on Facebook Messenger claiming someone they knew died with a link to a site trying to steal their Facebook password. Users of the forum responded initially with advice for them to contact their friend to let them know their account was hacked, or to block the person if they were a stranger.

March 20th, 2022

The post then sat silent for three days before another user reported the same occurrence, having received such a message from a coworker. Unlike the initial poster, they clicked on the link and entered their login information. They soon realized their account was compromised when they saw their Facebook Messenger account had sent the same message to nearly all of their Facebook friends.

March 30th, 2022

Ten days later, another user reported their account was compromised by the same scam. They realized that not only had the scammer sent the message to all of their Facebook friends, but all of their Facebook contacts, including people they had unfriended. This the first occurrence of a user increasing their account security in response to being scammed – they enabled 2-factor authentication and revoked session cookies for active logins to be sure.To this point, there was no clear goal of the scammers. Why did they want control of people’s Facebook accounts?

April 5th, 2022

Another user reported experiencing the scam. But this time, they did not escape with only injuries to their pride. The scammers collected the payment information from this user’s account and stole $2,000 from their debit cards.Thus began a deluge of other Facebook users flocking to the Reddit post, with dozens of other reports and over a hundred total comments until July 2022.

May 9, 2022

On May 9, 2022 the online safety and fact-checking website ThatsNonsense.com reported on the scam. In the article, they point out that the message has several features which internet users should learn to look for that indicate the message is illegitimate. They also give advice for actions to take in the case a user has become a victim of the scam themselves.

(Image from snopes.com)

Days later, cable news began covering the scam, with WGAL – Lancaster/Harrisburg being one of the first to report on it. DuckDuckGo has indexed an MSN news report on the same day, but the article has since been deleted, most likely due to MSN changing the structure of its site. Broken link.

Interlude

Over the following months, dozens of news agencies reported on this scam, the money people lost, and how to spot it in the wild.

Evolution

The scam evolved into at least one other form in the coming months. Rather than reaching out via Facebook Messenger, the scammers took a screenshot of a paused video from the ABC News YouTube channel showing a wrecked car on the side of the road in Georgia, with debris scattered in the grass. They edited the metadata of the site to display a fake view count – implying that the video was highly viewed.

(screenshot by Will Beason)

To ensure the post would be prioritized in people’s feeds in the algorithm, the scammers did several things known to make sure posts appear in people’s feeds.

• They made sure that the generated link going to the malicious site had a thumbnail. Facebook prioritizes links which have valid thumbnails.
• They re-shared their own post. Facebook prioritizes “shared” posts over originals, even when a user shares their own post.
• They tagged exactly nine other people. This is a “sweet spot” where the notification of the tagging still shows up in people’s Facebook notifications, and it doesn’t trigger anti-spam measures. Further, notifications prompt people to view the post in order to get rid of the notification. While users may delete notifications without viewing the post, they have no means of knowing what they’re missing before clicking to view.
• They made the post public so that the post could potentially appear in anyone’s feed – even people they have not “friended” on Facebook.

Together, this nearly guarantees at least nine other people (those tagged) will see the post. The other measures mean the post itself is likely to be highly-ranked in all of their friends’ feeds and will likely be seen by many dozens of people. For those tagged – the friends who interact with them often are likely to see the post as this is another feature Facebook heavily weights in ranking posts to show on user feeds.

Facebook’s Responsibility

This scam has persisted for over a year despite national news coverage, many hacked accounts, and the simple, predictable nature of these interactions. In the 20 such posts above, all of them linked to the same domain and had an identical thumbnail. All of the posts in a similar period of time use identical wording. In the past few weeks, it has been “Just happened an accident” but the wording has differed over time. It would not be technically difficult to detect these posts: I am able to easily find dozens of such posts by searching for the wording-of-the-day using Facebook’s already-extant search feature. Presumably, Facebook has means of searching posts by the domain linked to and the number of people tagged, which would make identifying these posts even easier.

And yet, this scam goes on.

Reports

On August 11th, in a flurry of data collection (rage?), I conducted a search as described above, immediately finding 25 such scam posts. I went through the report process for each post:

1. Three dots -> Report post
2. Please select a problem -> Spam
3. Submit

This creates an entry in the Facebook Support Inbox tied to my account.

The message assures that Facebook will use this information to identify spam, and more information about how Facebook deals with spam content.

Response

Facebook regularly responds to reports of spam. These do not happen on a regular timeframe – it isn’t clear how these are prioritized. I’ve had reports of this scam sit in my support inbox for months, and others are answered within days.In every case for this scam I have reported where I have gotten a response (~10 so far from August 11th reports), Facebook has responded with the following.

Sometimes the message gives an option to request a “re-review” of the content. Other times, the only options available are to block the compromised account or to delete the message from my support inbox. There isn’t a clear pattern here.

Example where I was able to request a re-review:

In no cases in the several months I have reported these scams has Facebook reported that one of these posts was taken down. I’ve reported about 40 in total.
Note: It is possible that Facebook removes messages from the support inbox – I have not verified that all of my reports still have entries.

Wherefore art thou, scam?

It is clear to users that these are scam posts. On many of these posts I’ve reported, friends of the person warn others not to click the link, and tell the person that their account has been compromised. Regular news coverage reports the impact on those who have lost money from the scam. Coverage on online safety sites have detailed information about the scam: how to spot it and how to recover.

But none of that matters because Facebook decides what is, or is not, a scam on Facebook.

~~ Fin ~~

Stopping here because I’m exhausted. I’m sure there’s neat implications to write about later. I hope you enjoyed my little weekend project.

“Truth” for language transformers

Language transformers do not have a concept of whether text they’ve generated is “true” – they are designed to predict likely continuations of a piece of text. The algorithms behind this are sophisticated, but they aren’t trying to do anything but recreate textual patterns in the corpus they were trained on. What matters to the transformer is “Given the preceding text, what should come next?” To the transformer, it is immaterial whether the generated text is factual information or misinformation.

Consider these two prompts:

1. “A recent study by the Harvard Medical School found that the new Novavax vaccine _”
2. “My 2yo was never the same after she got her shot. And then she got sick anyway. Clearly, the vaccine _”

Suppose you saw two comments on the Internet one beginning with each of the prompts. What would you expect to come next, based on what you have read on the Internet? (For this exercise, rely only on your memory)

Even though you probably personally disagree with what one of the continuations says, you would not be wrong in providing contradictory continuations of these two prompts. You, taking the role of the language transformer, haven’t actually made these claims – in this exercise your goal was not to inform whoever entered the prompt; it was to continue the text. In the same way, the language transformer is not evaluating the text it is generating in this way – it isn’t “taking a side” or even, in some sense, “saying” these things.

Not-Really-Citations

Consider possible responses you may have had to the first prompt. You could have said “… was 85% effective in preventing COVID infection 2 weeks after the vaccine was administered” or “… was found to be more effective in people who had never had COVID before.” Even though neither of these is (necessarily) supported by research, they are plausible continuations. Conversely, you are unlikely to have said something like “… caused people to spontaneously grow two additional eyes.” To the language transformer, those first two continuations would be rated at a much higher likelihood than the third and so it would tend to generate responses like those.

One way an application could cite text generated by a Transformer.

Language transformers don’t reference documents at query time and then generate text based on those documents. They are trained long before, and attempt to generate text that is a continuation of whatever they’ve been supplied. After the transformer has generated text, different algorithms analyze the text, and then look for the documents “most relevant” to the related text. Similarly – you could search the Internet for reliable sources that say similar things to how you continued the first prompt, and then cite them. You – and the transformer – aren’t really “citing” where you got this information, you made a guess and then looked for documents that seemed to support your guess.

It may be possible to attempt to determine claims generated text makes, and then re-prompt the transformer if it generated incorrect information, but these are hard problems. Identifying claims a text makes is not straightforward, and determining whether two texts say the same thing is difficult – even for humans. If the transformer generates “the vaccine was very effective” but the research says “the vaccine prevented 85% of cases in adults and 75% in children”, is the generated text “factual”? The citer may reference that research, but a reasonable person may disagree that a vaccine if “very effective” if it only has a 75% effectiveness in children.

Conclusion

Together, these factors mean that applications which use transformer-generated text will be unable to reliably cite sources which back up the text. In the example at the beginning of this post – there is no TLS version 1.4. While NeevaAI cites the TLS Wikipedia Page, as of this writing the text “1.4” does not appear anywhere on that page. Most likely, the transformer generated “is widely used in applications such as email, instant messaging, and voice over IP” because this text appears verbatim in the second sentence of the Wikipedia article. The citer seems to generate one citation per sentence, and so it likely chose Wikipedia as the source for that sentence because it found a high degree of textual similarity between that sentence and the text on Wikipedia. The citer didn’t catch that the generated sentence also makes a claim about TLS 1.4 but not the Wikipedia article.

Matt Parker is wrong on the internet and someone must rise to correct him. Alas, today is my day. I shall double reverse-Derek the one and only Matt Parker.

In a recent video, Matt Parker explored a beautiful, geometric way of understanding a problem known to many RPG players. In many RPGs (such as Dungeons and Dragons), players roll a 20-sided die (also called d20, for short) to determine the outcome of an action. In some cases, the dungeon master (who interprets the rules) may decide to give a player “advantage” on a roll, allowing them two roll two d20s (written as 2d20) instead of one and taking the higher of the two. The question that Matt Parker explores is: what is the expected value of taking advantage – how much better is it than just rolling one d20?

He then extends his answer to a more general form:

And this is where he is wrong.

First, consider the case of rolling md1. That is, rolling some number of 1-sided dice. Matt’s formula incorrectly gives:

Obviously since a d1 can only ever return 1 (and so the above should simplify to 1 for all m), something is amiss.

Here I need to define some mathematical notation for clarity. Define a random variable +_md_n as the result of taking advantage when rolling m dice, each with n sides.

We can similarly check the case of rolling md2 since this is easy enough to check by hand. The probability of +_md₂ evaluating to 1 is the probability of only rolling 1s, and so we get:

This is definitely not in line with Matt’s formula. So, what is the actual formula?

The below proof relies on the fact that the calculation for the expectation of a variable can be partitioned into mutually exclusive cases. That is:

Now, suppose that we had some way of representing E(+_md_n) and we want to find E(+_md_n+1). That is, we want to increase the number of faces of our dice. As we can split our expectation, calculation, we can see:

The first term is the probability that we have no faces of value n+1 times the expected value of taking advantage with mdn. The second term is the probability of having at least one face of value n+1 times that value, as when taking advantage only the largest value is counted.

And now for md3. Trivially, the probability of obtaining zero 3s when rolling m d3s is .

This pattern is suspicious, so let’s try this general form and see if using the iteration pattern preserves it:

Therefore, the expected value of rolling advantage with mdn is:

Through symmetry, the expected value of rolling with disadvantage (taking the lowest die) is: