Before I start this post, let me preface it by saying that I’m not an experienced Rustacean by any means. The excellent foks at /r/rust gave a lot of helpful feedback and cleared up some misconceptions I had. Futher errata and corrections are appreciated. This post is aimed at helping other fledgling rust-learners avoid my mistake. First, by helping Rust learners pick good introductory projects that will fit naturally in idiomatic rust.

If you read my recent post about Postgres you may have noted that Postgres operates primarily with fixed-size blocks of memory called “pages.” By default, Postgres pages are 8KB. This number is tuned to match operating system page sizes which are tuned to match hardware cache sizes. If you were to run Postgres on hardware with different cache sizes than Postgres was tuned for, you may be able to pick a better page size.

Many software engineers use database indexes every day, but few of us really understand how they work. In this post I’ll explain: How indexing works in Postgres using B-Trees What B-Trees are Why they are a good fit for this problem Indexes in Postgres Postgres actually offers 4 different kinds of indexes for different use cases. In this post I’ll be focusing on the “normal” index, the kind you get by default when you run create index.

Finding the median in a list seems like a trivial problem, but doing so in linear time turns out to be tricky. In this post I’m going to walk through one of my favorite algorithms, the median-of-medians approach to find the median of a list in deterministic linear time. Although proving that this algorithm runs in linear time is a bit tricky, this post is targeted at readers with only a basic level of algorithmic analysis.

Few data-structures are more ubiquitous in real-world development than the hash table. Nearly every major programming features an implementation in its standard library or built into the runtime. Yet, there is no conclusive best strategy to implement one and the major programming languages diverge widely in their implementations! I did a survey of the Hash map implementations in Go, Python, Ruby, Java, C#, C++, and Scala to compare and contrast how they were implemented.

The code for this post, as well as the post itself, are on github. This post is part 3 of a 3 part series. Part 1: Parsing Part 2: Generate an NFA Part 3: Evaluate an NFA Evaluating the NFA NFAs, DFAs and Regular Expressions Recall from part 2 that there are two types of finite automata: deterministic and non-deterministic. They have one key difference: A non-deterministic finite automata can have multiple paths out of the same node for the same token as well as paths that can be pursued without consuming input.

The code for this post, as well as the post itself, are on github. This post is part 2 of a 3 part series. Part 1: Parsing Part 2: Generate an NFA Part 3: Evaluate an NFA Converting the Parse Tree to an NFA In the last post, we transformed the flat string representation of a regular expression to the hierarchical parse tree form. In this post we’ll transform the parse tree to a state machine.

The code for this post, as well as the post itself, are on github. This post is part 1 of a 3 part series. Part 1: Parsing Part 2: Generate an NFA Part 3: Evaluate an NFA Until recently, regular expressions seemed magical to me. I never understood how you could determine if a string matched a given regular expression. Now I know! Here’s how I implemented a basic regular expression engine in under 200 lines of code.

Few data-structures are more ubiquitous in real-world development than the hash table. Nearly every major programming features an implementation in its standard library or built into the runtime. Yet, there is no conclusive best strategy to implement one and the major programming languages diverge widely in their implementations! I did a survey of the Hash map implementations in Go, Python, Ruby, Java, C#, C++, and Scala to compare and contrast how they were implemented.

Few data-structures are more ubiquitous in real-world development than the hash table. Nearly every major programming features an implementation in its standard library or built into the runtime. Yet, there is no conclusive best strategy to implement one and the major programming languages diverge widely in their implementations! I did a survey of the Hash map implementations in Go, Python, Ruby, Java, C#, C++, and Scala to compare and contrast how they were implemented.

Many software engineers use database indexes every day, but few of us really understand how they work. In this post I’ll explain: How indexing works in Postgres using B-Trees What B-Trees are Why they are a good fit for this problem Indexes in Postgres Postgres actually offers 4 different kinds of indexes for different use cases. In this post I’ll be focusing on the “normal” index, the kind you get by default when you run create index.

A recent outage lead me to investigate Postgres unique constraints more deeply. Postgres implements unique constraints by creating a unique index – an index that can only contain unique values.1 It turns out that unique indices and concurrent transactions can interact in nasty and surprising ways. Before I get into the “why”, here are the implications: When two transactions insert the same value into a unique index, one transaction will wait for the other transaction to finish before proceeding.

In the last 2 months, at two separate clients, I ran into the same type of deadlock, so I figured it was worth writing about to save someone else from the same fate. In short: When you have a pool of resources, the same thread must not acquire a second resource while already holding a resource. Otherwise, multiple threads can deadlock when they have all acquired their first resource but none can acquire their second resource.

A recent outage lead me to investigate Postgres unique constraints more deeply. Postgres implements unique constraints by creating a unique index – an index that can only contain unique values.1 It turns out that unique indices and concurrent transactions can interact in nasty and surprising ways. Before I get into the “why”, here are the implications: When two transactions insert the same value into a unique index, one transaction will wait for the other transaction to finish before proceeding.

There’s a common misconception that neural networks’ recent success on a slew of problems is due to the increasing speed and decreasing cost of GPUs. In reality, that’s not the case. Modern processing power plays a critical role, but only when combined with a series of innovations in architecture and training. You can’t process million-image datasets like ImageNet without a GPU, but without Resnet you won’t be able to achieve good results.

A recent outage lead me to investigate Postgres unique constraints more deeply. Postgres implements unique constraints by creating a unique index – an index that can only contain unique values.1 It turns out that unique indices and concurrent transactions can interact in nasty and surprising ways. Before I get into the “why”, here are the implications: When two transactions insert the same value into a unique index, one transaction will wait for the other transaction to finish before proceeding.

This document is adapted from an internal document I wrote for one of my clients, LogicHub. They’ve graciously allowed me to adapt it and share it as the blog post you’re reading now. As a reviewer, your primary goal is to find bugs before code is merged. Your secondary goal is to keep the code quality as high as possible, within reason and the time constraints of the moment. Depending on the situation, code reviews can also be a valuable venue for mentorship.

Two years ago in February 2016, frustrated and not feeling motivated by the 9 to 5, I quit my job. But, living in the Bay area is expensive, so I started freelancing. It’s been a life changing experience – I have control of my schedule, I have way less stress, and coding is fun again. It’s definitely not for everyone. If you don’t mind a little uncertainty and less choice on what you work on, the benefits far outweigh the downsides.

Many seasoned engineers working in JVM based languages have seen errors like this: [error] (run-main-0) java.lang.OutOfMemoryError: unable to create native thread: [error] java.lang.OutOfMemoryError: unable to create native thread: [error] at java.base/java.lang.Thread.start0(Native Method) [error] at java.base/java.lang.Thread.start(Thread.java:813) ... [error] at java.base/java.lang.Thread.run(Thread.java:844) OutOfMemory…err…out of threads. On my laptop running Linux, this happens after a paltry 11500 threads. If you try the same thing in Go by starting Goroutines that sleep indefinitely, you get a very different result.

Few data-structures are more ubiquitous in real-world development than the hash table. Nearly every major programming features an implementation in its standard library or built into the runtime. Yet, there is no conclusive best strategy to implement one and the major programming languages diverge widely in their implementations! I did a survey of the Hash map implementations in Go, Python, Ruby, Java, C#, C++, and Scala to compare and contrast how they were implemented.

Few data-structures are more ubiquitous in real-world development than the hash table. Nearly every major programming features an implementation in its standard library or built into the runtime. Yet, there is no conclusive best strategy to implement one and the major programming languages diverge widely in their implementations! I did a survey of the Hash map implementations in Go, Python, Ruby, Java, C#, C++, and Scala to compare and contrast how they were implemented.

Somehow I made it this far without actually understanding how sudo works. For years, I’ve just typed sudo, typed my password, and revelled in my new, magical, root super powers. The other day and I finally looked into it – to be honest, the mechanism is not at all what I expected. After going through the basics, we’ll walk through creating our own version of sudo. How Sudo Works sudo is just a regular old program that essentially does 3 things:

Many seasoned engineers working in JVM based languages have seen errors like this: [error] (run-main-0) java.lang.OutOfMemoryError: unable to create native thread: [error] java.lang.OutOfMemoryError: unable to create native thread: [error] at java.base/java.lang.Thread.start0(Native Method) [error] at java.base/java.lang.Thread.start(Thread.java:813) ... [error] at java.base/java.lang.Thread.run(Thread.java:844) OutOfMemory…err…out of threads. On my laptop running Linux, this happens after a paltry 11500 threads. If you try the same thing in Go by starting Goroutines that sleep indefinitely, you get a very different result.

Few data-structures are more ubiquitous in real-world development than the hash table. Nearly every major programming features an implementation in its standard library or built into the runtime. Yet, there is no conclusive best strategy to implement one and the major programming languages diverge widely in their implementations! I did a survey of the Hash map implementations in Go, Python, Ruby, Java, C#, C++, and Scala to compare and contrast how they were implemented.

Many seasoned engineers working in JVM based languages have seen errors like this: [error] (run-main-0) java.lang.OutOfMemoryError: unable to create native thread: [error] java.lang.OutOfMemoryError: unable to create native thread: [error] at java.base/java.lang.Thread.start0(Native Method) [error] at java.base/java.lang.Thread.start(Thread.java:813) ... [error] at java.base/java.lang.Thread.run(Thread.java:844) OutOfMemory…err…out of threads. On my laptop running Linux, this happens after a paltry 11500 threads. If you try the same thing in Go by starting Goroutines that sleep indefinitely, you get a very different result.

Few data-structures are more ubiquitous in real-world development than the hash table. Nearly every major programming features an implementation in its standard library or built into the runtime. Yet, there is no conclusive best strategy to implement one and the major programming languages diverge widely in their implementations! I did a survey of the Hash map implementations in Go, Python, Ruby, Java, C#, C++, and Scala to compare and contrast how they were implemented.

As I was learning to program, Python lists seemed totally magical to me. I imagined them as being implemented by some sort of magical datastructure that was part linked-list, part array that was perfect for everything. As I grew as an engineer, it occurred that this was unlikely. I guessed (correctly) that rather than some sort of magical implementation, it was just backed by a resizable array. I decided to read the code and find out.

Somehow I made it this far without actually understanding how sudo works. For years, I’ve just typed sudo, typed my password, and revelled in my new, magical, root super powers. The other day and I finally looked into it – to be honest, the mechanism is not at all what I expected. After going through the basics, we’ll walk through creating our own version of sudo. How Sudo Works sudo is just a regular old program that essentially does 3 things:

Many software engineers use database indexes every day, but few of us really understand how they work. In this post I’ll explain: How indexing works in Postgres using B-Trees What B-Trees are Why they are a good fit for this problem Indexes in Postgres Postgres actually offers 4 different kinds of indexes for different use cases. In this post I’ll be focusing on the “normal” index, the kind you get by default when you run create index.

I always wondered how Google Authenticator style 2-factor codes worked. The process of going from QR code to rotating 6-digit pin seemed a bit magical. A few days ago, my curiosity found itself coupled with some free time. Here’s what I found: What’s in the QR Code I scanned the QR code from Github with a barcode scanning app. Here’s what’s inside: otpauth://totp/Github:rcoh?secret=onswg4tforrw6zdf&issuer=Github Not too surprising. It tells us the protocol, TOTP, who is issuing this OTP code (Github), and most importantly the secret:1

The code for this post, as well as the post itself, are on github. This post is part 3 of a 3 part series. Part 1: Parsing Part 2: Generate an NFA Part 3: Evaluate an NFA Evaluating the NFA NFAs, DFAs and Regular Expressions Recall from part 2 that there are two types of finite automata: deterministic and non-deterministic. They have one key difference: A non-deterministic finite automata can have multiple paths out of the same node for the same token as well as paths that can be pursued without consuming input.

The code for this post, as well as the post itself, are on github. This post is part 2 of a 3 part series. Part 1: Parsing Part 2: Generate an NFA Part 3: Evaluate an NFA Converting the Parse Tree to an NFA In the last post, we transformed the flat string representation of a regular expression to the hierarchical parse tree form. In this post we’ll transform the parse tree to a state machine.

The code for this post, as well as the post itself, are on github. This post is part 1 of a 3 part series. Part 1: Parsing Part 2: Generate an NFA Part 3: Evaluate an NFA Until recently, regular expressions seemed magical to me. I never understood how you could determine if a string matched a given regular expression. Now I know! Here’s how I implemented a basic regular expression engine in under 200 lines of code.

Somehow I made it this far without actually understanding how sudo works. For years, I’ve just typed sudo, typed my password, and revelled in my new, magical, root super powers. The other day and I finally looked into it – to be honest, the mechanism is not at all what I expected. After going through the basics, we’ll walk through creating our own version of sudo. How Sudo Works sudo is just a regular old program that essentially does 3 things:

If you read my recent post about Postgres you may have noted that Postgres operates primarily with fixed-size blocks of memory called “pages.” By default, Postgres pages are 8KB. This number is tuned to match operating system page sizes which are tuned to match hardware cache sizes. If you were to run Postgres on hardware with different cache sizes than Postgres was tuned for, you may be able to pick a better page size.

Many software engineers use database indexes every day, but few of us really understand how they work. In this post I’ll explain: How indexing works in Postgres using B-Trees What B-Trees are Why they are a good fit for this problem Indexes in Postgres Postgres actually offers 4 different kinds of indexes for different use cases. In this post I’ll be focusing on the “normal” index, the kind you get by default when you run create index.

A recent outage lead me to investigate Postgres unique constraints more deeply. Postgres implements unique constraints by creating a unique index – an index that can only contain unique values.1 It turns out that unique indices and concurrent transactions can interact in nasty and surprising ways. Before I get into the “why”, here are the implications: When two transactions insert the same value into a unique index, one transaction will wait for the other transaction to finish before proceeding.

To say my first foray into Rust was a frustrating struggle would be an understatement. I picked a terrible first project that left me neck deep in Rust’s trickiest areas right off the bat. I was excited to try again. A few years ago I wrote Sumoshell, a CLI App for log analysis. I’d wanted to improve it for a while, so porting it to Rust seemed like a nice way to kill two birds with one stone.

Python 2 and Python 3 provide arbitrary precision integers. This means that you don’t need to worry about overflowing or underflowing the integer datatypes, ever. 2**10000? No problem. It makes it pretty convenient to write code. Floats, however, are not arbitrary precision: >>> a = 2 ** 10000 >>> a * .1 Traceback (most recent call last): File "<stdin>", line 1, in <module> OverflowError: int too large to convert to float Luckily, float overflow throws an exception to alert you to the problem.

Finding the median in a list seems like a trivial problem, but doing so in linear time turns out to be tricky. In this post I’m going to walk through one of my favorite algorithms, the median-of-medians approach to find the median of a list in deterministic linear time. Although proving that this algorithm runs in linear time is a bit tricky, this post is targeted at readers with only a basic level of algorithmic analysis.

In the last 2 months, at two separate clients, I ran into the same type of deadlock, so I figured it was worth writing about to save someone else from the same fate. In short: When you have a pool of resources, the same thread must not acquire a second resource while already holding a resource. Otherwise, multiple threads can deadlock when they have all acquired their first resource but none can acquire their second resource.

I always wondered how Google Authenticator style 2-factor codes worked. The process of going from QR code to rotating 6-digit pin seemed a bit magical. A few days ago, my curiosity found itself coupled with some free time. Here’s what I found: What’s in the QR Code I scanned the QR code from Github with a barcode scanning app. Here’s what’s inside: otpauth://totp/Github:rcoh?secret=onswg4tforrw6zdf&issuer=Github Not too surprising. It tells us the protocol, TOTP, who is issuing this OTP code (Github), and most importantly the secret:1

Few data-structures are more ubiquitous in real-world development than the hash table. Nearly every major programming features an implementation in its standard library or built into the runtime. Yet, there is no conclusive best strategy to implement one and the major programming languages diverge widely in their implementations! I did a survey of the Hash map implementations in Go, Python, Ruby, Java, C#, C++, and Scala to compare and contrast how they were implemented.

As I was learning to program, Python lists seemed totally magical to me. I imagined them as being implemented by some sort of magical datastructure that was part linked-list, part array that was perfect for everything. As I grew as an engineer, it occurred that this was unlikely. I guessed (correctly) that rather than some sort of magical implementation, it was just backed by a resizable array. I decided to read the code and find out.

To say my first foray into Rust was a frustrating struggle would be an understatement. I picked a terrible first project that left me neck deep in Rust’s trickiest areas right off the bat. I was excited to try again. A few years ago I wrote Sumoshell, a CLI App for log analysis. I’d wanted to improve it for a while, so porting it to Rust seemed like a nice way to kill two birds with one stone.

Somehow I made it this far without actually understanding how sudo works. For years, I’ve just typed sudo, typed my password, and revelled in my new, magical, root super powers. The other day and I finally looked into it – to be honest, the mechanism is not at all what I expected. After going through the basics, we’ll walk through creating our own version of sudo. How Sudo Works sudo is just a regular old program that essentially does 3 things:

Before I start this post, let me preface it by saying that I’m not an experienced Rustacean by any means. The excellent foks at /r/rust gave a lot of helpful feedback and cleared up some misconceptions I had. Futher errata and corrections are appreciated. This post is aimed at helping other fledgling rust-learners avoid my mistake. First, by helping Rust learners pick good introductory projects that will fit naturally in idiomatic rust.

Many seasoned engineers working in JVM based languages have seen errors like this: [error] (run-main-0) java.lang.OutOfMemoryError: unable to create native thread: [error] java.lang.OutOfMemoryError: unable to create native thread: [error] at java.base/java.lang.Thread.start0(Native Method) [error] at java.base/java.lang.Thread.start(Thread.java:813) ... [error] at java.base/java.lang.Thread.run(Thread.java:844) OutOfMemory…err…out of threads. On my laptop running Linux, this happens after a paltry 11500 threads. If you try the same thing in Go by starting Goroutines that sleep indefinitely, you get a very different result.

To say my first foray into Rust was a frustrating struggle would be an understatement. I picked a terrible first project that left me neck deep in Rust’s trickiest areas right off the bat. I was excited to try again. A few years ago I wrote Sumoshell, a CLI App for log analysis. I’d wanted to improve it for a while, so porting it to Rust seemed like a nice way to kill two birds with one stone.

In the last 2 months, at two separate clients, I ran into the same type of deadlock, so I figured it was worth writing about to save someone else from the same fate. In short: When you have a pool of resources, the same thread must not acquire a second resource while already holding a resource. Otherwise, multiple threads can deadlock when they have all acquired their first resource but none can acquire their second resource.

Few data-structures are more ubiquitous in real-world development than the hash table. Nearly every major programming features an implementation in its standard library or built into the runtime. Yet, there is no conclusive best strategy to implement one and the major programming languages diverge widely in their implementations! I did a survey of the Hash map implementations in Go, Python, Ruby, Java, C#, C++, and Scala to compare and contrast how they were implemented.

The code for this post, as well as the post itself, are on github. This post is part 3 of a 3 part series. Part 1: Parsing Part 2: Generate an NFA Part 3: Evaluate an NFA Evaluating the NFA NFAs, DFAs and Regular Expressions Recall from part 2 that there are two types of finite automata: deterministic and non-deterministic. They have one key difference: A non-deterministic finite automata can have multiple paths out of the same node for the same token as well as paths that can be pursued without consuming input.

The code for this post, as well as the post itself, are on github. This post is part 2 of a 3 part series. Part 1: Parsing Part 2: Generate an NFA Part 3: Evaluate an NFA Converting the Parse Tree to an NFA In the last post, we transformed the flat string representation of a regular expression to the hierarchical parse tree form. In this post we’ll transform the parse tree to a state machine.

The code for this post, as well as the post itself, are on github. This post is part 1 of a 3 part series. Part 1: Parsing Part 2: Generate an NFA Part 3: Evaluate an NFA Until recently, regular expressions seemed magical to me. I never understood how you could determine if a string matched a given regular expression. Now I know! Here’s how I implemented a basic regular expression engine in under 200 lines of code.

Somehow I made it this far without actually understanding how sudo works. For years, I’ve just typed sudo, typed my password, and revelled in my new, magical, root super powers. The other day and I finally looked into it – to be honest, the mechanism is not at all what I expected. After going through the basics, we’ll walk through creating our own version of sudo. How Sudo Works sudo is just a regular old program that essentially does 3 things:

I always wondered how Google Authenticator style 2-factor codes worked. The process of going from QR code to rotating 6-digit pin seemed a bit magical. A few days ago, my curiosity found itself coupled with some free time. Here’s what I found: What’s in the QR Code I scanned the QR code from Github with a barcode scanning app. Here’s what’s inside: otpauth://totp/Github:rcoh?secret=onswg4tforrw6zdf&issuer=Github Not too surprising. It tells us the protocol, TOTP, who is issuing this OTP code (Github), and most importantly the secret:1

Someone recently lamented to me that try as they might, they can’t seem to instill a culture of non-manual testing in their team. This problem pervades startups, especially in those with a lot of newer developers. My theory: To foster a culture where software engineers are internally motivated to write good tests, make it harder to run your app locally and easier to write and run tests. To put it another way: rather than investing time in enabling people to run a standalone app on their laptops, invest time in making it easy to write tests.

Someone recently lamented to me that try as they might, they can’t seem to instill a culture of non-manual testing in their team. This problem pervades startups, especially in those with a lot of newer developers. My theory: To foster a culture where software engineers are internally motivated to write good tests, make it harder to run your app locally and easier to write and run tests. To put it another way: rather than investing time in enabling people to run a standalone app on their laptops, invest time in making it easy to write tests.

Even if you go to bed at 9, getting up at 5AM is hard. It’s always darker than you expect and it’s usually freezing. In any case, Calley and I crawled out of our respective vans at 5AM in the Tuolumne Meadows campground, shoveled down some cold cereal, and rolled out for the day’s objective, the West Ridge of Mount Conness. TM Herbert, legendary Tuolumne badass, described the climb as “2 Cathedrals stacked on top of each other.

After 4 days climbing long moderates in Tuolumne Meadows, Eben and I were stoked to get out of the park for the weekend and escape the crowds on some eastside alpine rock. After a few minutes of flipping through the guidebook, we settled on the North Arete on Bear Creek Spire. The granite prow of Bear Creek Spire rises to 13713’, roughly 1500’ above the scree at its base. The North Arete climbs the steep north ridge line through 10 pitches up to the summit.