August 04, 2016

May 08, 2021


A couple of months ago, Google Cloud launched gvnic, a new paravirtual network interface for virtual machines in Google Compute Engine. gvnic offers higher performance than and new features over the prior paravirtual network interface in GCE, virtio-net.

Welcome to Ubuntu 20.04.2 LTS (GNU/Linux 5.4.0-1036-gcp x86_64)

 * Documentation:
 * Management:
 * Support:

  System information as of Sat Feb 20 03:49:30 UTC 2021

  System load:  0.08              Processes:             103
  Usage of /:   14.9% of 9.52GB   Users logged in:       0
  Memory usage: 5%                IPv4 address for ens4:
  Swap usage:   0%

1 update can be installed immediately.
0 of these updates are security updates.
To see these additional updates run: apt list --upgradable

The list of available updates is more than a week old.
To check for new updates run: sudo apt update

Last login: Sat Feb 20 03:42:19 2021 from
extrudedaluminiu@instance-2:~$ lspci -nn
00:00.0 Host bridge [0600]: Intel Corporation 440FX - 82441FX PMC [Natoma] [8086:1237] (rev 02)
00:01.0 ISA bridge [0601]: Intel Corporation 82371AB/EB/MB PIIX4 ISA [8086:7110] (rev 03)
00:01.3 Bridge [0680]: Intel Corporation 82371AB/EB/MB PIIX4 ACPI [8086:7113] (rev 03)
00:03.0 Non-VGA unclassified device [0000]: Red Hat, Inc. Virtio SCSI [1af4:1004]
00:04.0 Ethernet controller [0200]: Google, Inc. Compute Engine Virtual Ethernet [gVNIC] [1ae0:0042]
00:05.0 Unclassified device [00ff]: Red Hat, Inc. Virtio RNG [1af4:1005]
gvnic on GCE: PCI Device ID 0x42, of course

I worked on gvnic for nearly three years (though it was some time ago); It is exciting to see a new paravirtual device of this scope reach General Availability!

A new paravirtual device represents a VM guest/hypervisor ABI and requires careful attention to detail - we needed to ensure that the ABI is a good match to VM guest requirements, to a hypervisor and underlying network infrastructure properties, and is designed with forward-evolution and versioning in mind. There are tradeoffs at multiple levels - for example, VM guests and hypervisors may have different preferences for where in memory transmit or receive frames live and how they're scattered/gathered; whether receive frame headers are more efficient in-line or out-of-line; and hundreds of other decisions that impact system performance and maintainability.

Building anything is kind of like this

Congratulations to everyone involved in the design and launch of the system; and to everyone who uses it, I hope it works well for you!


February 04, 2020

Linux barriers and implementations

The Linux kernel has a family of barrier functions suitable for communicating across processors (smp_*), with DMA devices (dma_*), and for other uses (mb/rmb/wmb).

I've often found it useful to know what hardware instructions a particular barrier maps to; this table maps each Linux barrier to its corresponding implementation on x86-64 and aarch64.

smp_rmb__asm__ __volatile__("": : :"memory") [1] dmb ishld [1]
smp_wmb__asm__ __volatile__("": : :"memory") [1] dmb ishst [1]
smp_mbasm volatile("lock; addl $0,-4(%%rsp)" ::: "memory", "cc") [1] dmb ish [1]
dma_rmb__asm__ __volatile__("": : :"memory") [1] dmb oshld [1]
dma_wmb__asm__ __volatile__("": : :"memory") [1] dmb oshst [1]
mbmfence [1]dsb sy [1]
rmblfence [1] dsb ld [1]
wmbsfence [1] dsb st [1]

  1. mmiowb was formerly used to enforce partial orders of MMIO writes with respect to main memory writes. It is no longer generally used, the required ordering properties have been folded into other primitives.


July 02, 2019

Organizations I've supported in 2018 and 2019 H1

Early in 2017, I committed to support a number of nonprofits and civil society organizations, particularly focused on climate change. I wrote about the organizations I planned to support and why - Organizations I'm supporting (2017) and I wrote a follow-up of what I ended up doing - Organizations I've supported in 2017.

In 2018, I wrote an updated plan - Organizations I'm supporting in 2018. I added a number of non-proliferation and think-tank organizations in preference to direct assistance and I slightly biased in favor of local and regional organizations relative to national ones.

I'm writing to share what I've been doing / what's worked for me and highlight organizations or types of organizations worth thinking about out.

In 2018, I donated 321 individual times to 68 distinct organizations. Donations were skewed - the top 7 organizations received > 50% of all donations, the top 12 received 75%.

2018 overall
2018 Overall

2018 75+
2018 75%

2018 50
2018 50%

Top organizations -

  • Union of Concerned Scientists
  • Environmental Defense Fund
  • Pro Publica - Nonprofit investigative newsroom
  • RENEW Wisconsin
  • Natural Resources Defense Council
  • Brennan Center for Justice
  • Northwest Immigrant Rights Project ( > 50%)
  • GiveWell
  • EarthJustice
  • Ploughshares Fund - Grant-making nonprofit focused on nuclear nonproliferation
  • ACLU
  • National Immigration Law Center ( > 75% )

I’d like to highlight RENEW Wisconsin and Fresh Energy - both state-level organizations advocate for cleaner energy generation and access in Wisconsin and Minnesota respectively; I think they are high-leverage organizations given the carbon intensity of the MISO region and the possibility of state-level climate action. Both were new to the list in 2018.

In 2018 I also opened a Donor Advised Fund (DAF), presumptuously named Memorial. A Donor-Advised Fund is a designated account at a “nonprofit”, often associated with a financial services firm (I use Fidelity’s, for example); contributions to the fund are considered 501(c)3 donations and may be invested and later donated to a separate non-profit. DAF’s do have associated fees; these fees may mean they are not a good choice in all circumstances. I’ve chosen to invest in a balanced mix of US stock / US bond index funds and do not use Environmental/Sustainable/Governance (ESG) funds, though they are available.

I use a DAF for two reasons - 1) Better recordkeeping and 2) To defer year-end donations into the following calendar year, to take advantage of annual corporate donation matching.

Total direct donations in 2018 were 92% of 2017’s total; including pre-funding the Donor-Advised Fund raises that to 107%. As a percentage of my total income, this was between 11% and 14%, again depending on whether the pre-funding was included.

In 2018, I found out about the Effective Altruism (EA) community; EA aims to apply analysis to philanthropy - where can a dollar do the most good (by a common metric, years of life, quality-weighted, per intervention), with an emphasis on measuring outcomes and the good a marginal dollar can do. EA-favored nonprofits have focused on public health (ex: malaria control) and existential risks in the recent past.

I am convinced the EA approach is valuable, but the metric undervalues indirect work civil society may do, such as advocacy or informing policy.

In October 2018, I took the EA-associated Giving What We Can Pledge:

“I recognize that I can use part of my income to do a significant amount of good. Since I can live well enough on a smaller income, I pledge that for the rest of my life or until the day I retire, I shall give at least ten percent of what I earn to whichever organisations can most effectively use it to improve the lives of others, now and in the years to come. I make this pledge freely, openly, and sincerely.”

I missed this target in 2018, though I gave 3.8% overall to GiveWell, GiveDirectly, Against Malaria Foundation, Future of Life Foundation, and No Lean Season.

In 2018, I contributed to a number of state and federal election campaigns; contributions can be viewed through the FEC site but are not included above.

In 2018, I also purchased 20 metric tons of CO2e offsets, via methane flaring, from a private provider.

In the first half of 2019, I’ve donated 135 individual times to 48 distinct organizations. Once again, donations were skewed - the top 5 organizations received > 50% of all donations, the top 15 received > 75%.

2019 Overall

2019 50%

Top organizations -

  • Oregon Climate Trust - Oregon organization administering Oregon Carbon Dioxide Standard, undertaking offset programs
  • Fresh Energy - Minnesota energy transition / clean energy organization with a long track record (~1992). Was involved in the closure of the Sherco I and II (coal) generating stations in Becker, MN
  • RENEW Wisconsin - Wisconsin advocacy organization, focuses on interfacing with PUC and supporting "Focus on Energy" program
  • Union of Concerned Scientists
  • US Climate Action Network
  • Against Malaria Foundation (> 50%)
  • GiveWell
  • Pro Publica
  • Midwest Renewable Energy Association
  • Natural Resources Defense Council
  • Climate Solutions - Oregon and Washington
  • International Refugee Assistance Project
  • Northwest Immigrant Rights Project
  • Human Rights Watch
  • Center for Civilians in Conflict (> 75%)

In 2019, I've focused on state- and regional- clean energy and climate organizations (Oregon Climate Trust, Fresh Energy, Renew Wisconsin, Wind on the Wires, Midwest Renewable Energy Association, Climate Solutions...). There have been too many failures of large climate projects, from regional transmission projects, to carbon taxes (Washington has failed to pass three times), to Oregon's HB2020, to V.C. Summer's abandonment. At the same time, there have been and state- and regional-level successes; focusing on the organizations that have made them possible buys space and time and window for larger-scale projects, I think.

Total direct donations in 2019 so far have been 90% of 2018’s yearly total and 84% of 2017’s total. As a percentage of my income so far, this has been between 16% and 19%, depending on whether Donor-Advised Fund contributions or outflows are credited.

I've met roughly 10% of my Effective Altruism Giving Pledge target this year. I plan to at least meet 2018's mark, though am hoping to meet the whole target.

I haven't purchased any carbon offsets this year; I am not sure as to whether or how effective they are; I'd appreciate any thoughts about them.

I've enjoyed this three-year-long giving project; I'd appreciate any thoughts about what I could be doing better/differently and anything else I should check out. I'd appreciate any thoughts about how I might contact and chat with the non-profits I support and what sort of metrics would be appropriate for climate or civil organizations. Or any thoughts about how to present this data better!


July 16, 2018

Recurse Center - First steps w/ Queues

I am currently attending Recurse Center in New York City, where I’m studying discrete event simulation & queueing theory for the next 12 weeks. I plan to study and gain intuition about queueing theory by working through Mor Harchol-Balter’s "Performance Modeling and the Design of Computer Systems" textbook and through simulation, playing with knobs and asking “what if” questions about scenarios in the book and from outside experience. What are the boundaries of the universe of parameters and what happens at the edges?

A queue is the summation of the difference between an arrival process and a service process. A queue can appear anytime an arrival rate is higher than a service rate at a point - a short-term difference leads to a transient queue, a long-term difference leads to a standing or unbounded queue.

Imagine a road - draw a box around a stretch of the road. A fixed n cars/sec arrive at the box, a service process allows n cars/sec to leave. No queue forms, the time it takes for a single car, its service time, is only governed by its speed and the size of the box.


Now imagine a row of ducklings wanders across the eastbound lane.


The maximum service rate transiently drops and cars queue to wait patiently for the ducklings to cross. The sojurn time, the time from when a car arrives at the box until it leaves, rises to include time spent waiting.

Schematically, queueing systems are represented by interconnections of queues, processors, and switches. The road example would be -


Queueing theory seeks to understand how queues form, behave, and how they should be controlled. Queueing theory also seeks to understand and control how units of work flow and wait in systems and to maximize throughputs or minimize average/worst-case delays.

Queueing theory generally assumes a system’s long-term arrival rate is less than the long-term service rate - otherwise a system would diverge and queues could grow without bound.

Queueing theory allows arrival and service processes to be statistical ‘counting’ processes - for example, on average λ units of work/sec may arrive, but the arrivals may not be uniformly spaced in time and the inter-arrival time may follow many distributions. Units of work may also take non-uniform ‘resources’/time to service, again following some distribution.

Tero Parviainen (@teropa) wrote a fantastic interactive tool to experiment with Markov arrival processes, a common arrival process where inter-arrival times are independent - A Dash of Queueing Theory. It is worth spending some time looking at both the cumulative arrival and service processes in his examples - it is important to understand that queues can form even when average arrival and service rates are matched.

Via queueing theory, we can approach questions like - "Should we have one processor with a service rate of μ or have multiple processors N, each with a service rate μ/N?" or "When should we power on/power off additional processors to service work?" or even "When/how should a queue push back on a source to change an arrival process?"

Some of these questions may have other approaches - control theoretic approaches to ‘when to power on/off additional processors’ using the first derivative of queue depth have been fruitful, for example.

Mor Harchol-Balter’s text starts with a few design questions - I’d like to highlight two:

  • Imagine a system where work arrives at a server, following a Markov process (inter-arrival times follow exponential distribution, memoryless process); on average, 3 units of work arrive each second. The server is able to service up 5 to units/sec.

    Imagine the arrival rate doubles; how much faster do you need to make the server to maintain the average sojurn time?

    It turns out that the server needs to get less than twice as fast to maintain the average sojurn time! I found this result fairly counterintuitive.

    I wrote a simple discrete event simulator to work through this scenario, in two steps. First I started with a system where 3 units/sec arrived following a Markov process and 4 units/sec could depart. Then I turned up the service rate from 4 units/sec -> 8 units/sec; the distribution of sojurn times shifted:

    This is a stacked violin plot of the 3 units/sec // 4 units/sec scenario (blue) and the 2 units/sec // 8 units/sec scenario (orange). In a violin plot, the width of a horizontal slice represents the part of the Density Function that is at a particular y-axis value. The means and extrema are highlighted by horizontal bars.

    In both the blue and orange violins, we see most of of the PDF at ‘zero sojurn time’ (no delay). The blue distribution has substantial density at 1 and 2 units of delay, whereas the orange (faster server) distribution does not. The mean of the orange distribution is just a hair above zero; doubling the service rate has more than halved the average sojurn time.

    Let’s now double the arrival rate as well, from 3 units/sec -> 6 units/sec:

    The blue distribution is the same as the prior plot - 3 units/sec arrive, 4 units/sec service rate.

    The orange distribution is for 6 units/sec arriving, 8 units/sec service rate. The Density Function of the faster server’s sojurn time remains better than the original scenario!

    Looking at the time series of sojurn times of the initial case (3 units/sec // 4 units/sec) was crucial to understanding this result.

    Here the x-axis is job sequence #, the y axis is sojurn time.

    There is underlying structure here! If job N experiences a delay, it is more likely that job N + 1 experiences a delay. Intuitively, the system is stateful - a job can see a ‘unloaded’ or ‘loaded’ system, based on recent history.

    Doubling the service rate halves the amount of time required for a single job to be processed; it also reduces the probability that a job will see the system in a bad state.

    Combining the two effects more than halves the average sojurn time.

    (6 units/sec // 8 units/sec scenario - the x scale is different from above because a higher arrival rate results in more jobs arriving within a given time)

  • Imagine a system where work arrives following a Markov process. You can feed this work into either one server with a service rate μ or into N servers with a service rate of μ/N. Under what circumstances would you choose one server or N servers?


    Let us start with the assumption that there is sufficient work to fully utilize all N servers; if there is insufficient work, one server would be preferable - the multi-server configuration would have idle capacity.

    The result is “it depends on the variance of the job size distribution” - High variance favors multiple slower ones servers over one fast server.

    Let’s start with the simple case where there is zero variance in job size - in this case, the fast server will finish a job every 1/μ seconds, the slow servers will finish N jobs every N/μ seconds. Both configurations should perform identically.

    In the high variance case, however, we can end up with an expensive job in front of a cheap job - a classic “head of line blocking” scenario. The one server configuration will force the cheap job to wait for the expensive job whereas the N server configuration would allow the cheap job to ‘slip’ around the expensive job.

    We will come back to this configuration in future examples.

Thank you to many peers at the Recurse Center for reviewing this post


gVNIC May 08, 2021
Organizations I've supported in 2018 and 2019 H1 July 02, 2019
Recurse Center - First steps w/ Queues July 16, 2018
Organizations I'm supporting in 2018 March 21, 2018
Organizations I've supported in 2017 December 28, 2017
Detect. Transmit. March 21, 2017
Organizations I'm supporting this year February 12, 2017
4K for Cancer 2015 - Seattle, WA August 14, 2015
4K for Cancer Portland 2014 - Portland, OR August 16, 2014
A couple of days with 4K Portland 2014 July 31, 2014
4K for Cancer 2014 Sendoff & Day 1 June 08, 2014
Trust Fall June 06, 2014
4K for Cancer Seattle 2013 - Seattle, WA August 26, 2013
4K for Cancer Portland 2013 - Cannon Beach August 25, 2013
Baltimore to Portland September 29, 2012
Blink and life flies by. August 03, 2012
Day 68 -- Tillamook to August 02, 2012
Day 67 -- Corvallis to August 01, 2012
Halfway to Corvallis. After that, July 31, 2012
Before riding to Corvallis, Team July 31, 2012
Day 66 -- Eugene to July 31, 2012
Day 64 -- Rest day July 29, 2012
Crossing Country and Catching Up, part 1 July 18, 2012
In Denver, CO. Veiled mountain July 03, 2012
Something is hidden in the July 03, 2012
@4KPortland 200mi in 2 days, July 01, 2012
Welcome to Colorful Colorado! July 01, 2012
The country from Franklin, NE June 28, 2012
#4kportland Cheers from Arapahoe, NE!! June 28, 2012
#4kportland Day 33 -- To June 28, 2012
#4kportland Iowa is not flat!! June 23, 2012
#4kportland Day 28 -- Atlantic, June 23, 2012
#4kportland Day 25 -- Wheatland June 20, 2012
#4kportland Day 24 -- Iowa June 19, 2012
#4kportland Day 23 -- 120mile+ June 18, 2012
@4kportland Day 21 -- Chicago June 16, 2012
@4kportland winning June 09, 2012
#4kportland -- Cincinnati to Lexington, June 08, 2012
Intro & Twelve Days June 07, 2012
First week of #4kportland!! (@4KPortland) June 03, 2012
#4kportland Day 8 -- Canton, June 03, 2012
#4kportland at the host in June 02, 2012
#4kportland Day 7 -- Youngstown June 02, 2012
Reached host in Youngstown! _So_ June 01, 2012
#4kportland Day 6 -- Pittsburgh, June 01, 2012
#4kportland Day 4 -- Ligionier, May 30, 2012
4K day 2: Waking up May 28, 2012
@4KPortland group 4 is in May 27, 2012
My last night in Baltimore. May 27, 2012
An alumni's thoughts on 4K; May 18, 2012
IOCCC Korn 1987 August 04, 2007

May 2021
February 2020
July 2019
July 2018
March 2018
December 2017
March 2017
February 2017
August 2016
August 2015
August 2014
July 2014
June 2014
August 2013
September 2012
August 2012
July 2012
June 2012
May 2012
August 2007

Powered by
Movable Type 2.661