This is a valid Atom 1.0 feed.
This feed is valid, but interoperability with the widest range of feed readers could be improved by implementing the following recommendations.
<link rel='self' href='https://www.tbray.org/ongoing/ongoing.atom' />
^
<p>To set the stage, consider this regexp: <nobr><code>A?B?C?X</code></n ...
^
<?xml version='1.0' encoding='UTF-8'?>
<feed xmlns='http://www.w3.org/2005/Atom'
xmlns:thr='http://purl.org/syndication/thread/1.0'
xml:lang='en-us'>
<title>ongoing by Tim Bray</title>
<link rel='hub' href='http://pubsubhubbub.appspot.com/' />
<id>https://www.tbray.org/ongoing/</id>
<link href='https://www.tbray.org/ongoing/' />
<link rel='self' href='https://www.tbray.org/ongoing/ongoing.atom' />
<link rel='replies' thr:count='101' href='https://www.tbray.org/ongoing/comments.atom' />
<logo>rsslogo.jpg</logo>
<icon>/favicon.ico</icon>
<updated>2025-08-30T12:59:15-07:00</updated>
<author><name>Tim Bray</name></author>
<subtitle>ongoing fragmented essay by Tim Bray</subtitle>
<rights>All content written by Tim Bray and photos by Tim Bray Copyright Tim Bray, some rights reserved, see /ongoing/misc/Copyright</rights>
<generator uri='/misc/Colophon'>Generated from XML source code using Perl, Expat, Emacs, Mysql, Ruby, and ImageMagick. Industrial-strength technology, baby.</generator>
<entry>
<title>Maritime Birds and Bees</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/08/30/Maritime-Wildlife' />
<link rel='replies' thr:count='0' type='application/xhtml+xml' href='/ongoing/When/202x/2025/08/30/Maritime-Wildlife#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/08/30/Maritime-Wildlife</id>
<published>2025-08-30T12:00:00-07:00</published>
<updated>2025-08-30T12:59:04-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='The World/Places/Maritimes' />
<category scheme='https://www.tbray.org/ongoing/What/' term='The World' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Places' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Maritimes' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>Nova Scotia and New Brunswick each have plenty of wilderness; PEI not so much. So pictures of bears and cougars and so on would be plausible, as would marine mammals. But no. Herewith, from our <a href='/ongoing/When/202x/2025/08/27/Maritime-Vacation'>recent vacation</a>, birds and bees, with a little lens-geek side trip</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>Nova Scotia and New Brunswick each have plenty of wilderness; PEI not so much. So pictures of bears and cougars and so on
would be plausible, as would marine mammals. But no. Herewith, from our
<a href="/ongoing/When/202x/2025/08/27/Maritime-Vacation">recent vacation</a>, birds and bees, with a little
lens-geek side trip.</p>
<h2 id='p-1'>Birds</h2>
<p>Having touristed around Charlottetown, we drove down a series of smaller and smaller back roads and ended up
at Canceaux Cove near Rocky Point, which I thought might present a nice vista of the city. It did, but the city looks boring.
By way of consolation, there were these cute little birds running around on the beach and then flying loops in formation over the
water.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/30/TXT55982.png" alt="Small birds on a beach" />
<div class='caption'><p>Pretty sure these are
<a href="https://en.wikipedia.org/wiki/Semipalmated_plover">Semipalmated plovers</a>.</p></div>
<p>I wanted to get a picture of them in the air so I sauntered down the beach, assuming
they’d fly away picturesquely. They studiously ignored me and eventually I had to jump and down and wave my arms and even then
they took off grudgingly.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/30/TXT55984.png" alt="small birds flying over the ocean" />
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/30/TXT55987.png" alt="small birds flying over the ocean" />
<p>They were graceful and did this mysterious thing that birds can do, staying in formation with no obvious leader.
I’ve had the pleasure, very occasionally, of being in engineering teams like that.</p>
<h2 id='p-2'>Bees</h2>
<p>We went to
<a href="https://en.wikipedia.org/wiki/Annapolis_Royal">Annapolis Royal</a> because of its
<a href="https://historicgardens.wordpress.com">Historic Gardens</a> and wow, what a treat. I think even those who don’t see
themselves as garden fans would enjoy an hour or more sauntering around in there. I like taking pictures of flowers and a lot
of these flowers had bees in them.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/30/TXT56034-2.png" alt="Three orange flowers, one with bee" />
<p>This one was cute enough to reward a close-up.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/30/TXT56034.png" alt="Close-up of bee in orange flower." />
<div class='caption'><p>Aren’t her wings cute?</p></div>
<p>And I ask, what could be better than a cute bee in a pretty flower? Obviously, <em>two</em> bees.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/30/TXT56040.png" alt="Two bees in an orange flower" />
<p>And again, a closer look.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/30/TXT56040-2.png" alt="Two bees in an orange flower, close-up" />
<p>Bees are admirable creatures and I don’t want to make fun of them, but this surprised-looking little citizen makes me
laugh. (She’s just navigating from one blossom to the next.)</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/30/TXT56045.png" alt="bee caught in flight among the blossoms" />
<h2 id='p-3'>Lens</h2>
<p>All of these are shot with Fujifilm’s
<a href="https://www.fujifilm-x.com/en-ca/products/lenses/xf55-200mmf35-48-r-lm-ois/">55-200mm</a> lens, which I’ve had for at
least eleven years. Up till now, I’ve always pointed it at faraway things, but wow, I think I’ll be taking this to more gardens
in future.</p>
<p>I mention this partly so I can link to this
<a href="https://www.lensrentals.com/blog/2016/02/the-long-awaited-scary-and-amazing-fuji-lens-teardown/?srsltid=AfmBOorQfgob6drIXwtTJ9xuixBbnSvZE2F8x7Jba0AA3U60uoFAB3gY">awesome
(and funny) teardown piece</a> from Lensrentals.</p>
<p>And, on the way out, let’s let that lens show off with a couple of roses.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/30/TXT56057.png" alt="Yellow rose and bud" />
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/30/TXT56058.png" alt="Pink roses, black background" />
<p>Remember, pink and black are the colors of rock & roll.
And if you’re anywhere near Annapolis Royal, stop and visit that garden.</p>
</div></content></entry>
<entry>
<title>Maritime Vacation</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/08/27/Maritime-Vacation' />
<link rel='replies' thr:count='0' type='application/xhtml+xml' href='/ongoing/When/202x/2025/08/27/Maritime-Vacation#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/08/27/Maritime-Vacation</id>
<published>2025-08-27T12:00:00-07:00</published>
<updated>2025-08-28T12:36:15-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='The World/Places/Maritimes' />
<category scheme='https://www.tbray.org/ongoing/What/' term='The World' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Places' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Maritimes' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>The sound of the wind surging through birchy Eastern woods isn’t like the same coastal gusts in my own Pacific rain forest; around you not above you, alto not baritone. The colors differ too: Forests, houses, soil, and sea. And everywhere little white churches, each with its cemetery. A scattering of forts, far too many cannons. And everything faces the sea</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>The sound of the wind surging through birchy Eastern woods isn’t like the same coastal gusts in my own Pacific rain
forest; around you not above you, alto not baritone. The colors differ too: Forests, houses, soil, and sea. And everywhere
little white churches, each with its cemetery. A scattering of forts, far too many cannons. And everything faces the sea.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/27/PXL_20250814_142523016.png" alt="Cape Breton forest" />
<div class='caption'><p>Birchy Cape Breton forest.</p></div>
<p>For the first time since Covid and, more important, since Lauren’s 2½-year battle with Long Covid, we went on the road for
pleasure; Lauren and I and our dear friend Sally from Warragul, Australia. To my shame, all my decades’ travel had never taken
me to Canada east of Montreal, so we spent a couple of weeks poking around Nova Scotia and Prince Edward Island, plus a bit of
New Brunswick. I took many pictures and it’ll take a few blog pieces to share those that I think deserve it.</p>
<p>No part of Canada’s settler culture is old by European or Asian standards, but ten generations of white people
lived and died here before the first rough town organized itself near what’s now Vancouver. They had to be buried someplace, thus the
graveyards everywhere you go. These were captured near Whycocomagh.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/27/TXT55871.png" alt="Gravestone of Lillian S. DeWolfe, 1876-1958" />
<div class='caption'><p>Lillian S. DeWolfe, Oct 1876 Sept 1958.</p></div>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/27/TXT55874.png" alt="A simple grave marker saying only “sleeping”" />
<p>How long will it still matter that my hometown is one of the world’s youngest big cities?</p>
<p>Many graveyards are church attachments, but many more greet you at a random turn in the road; always framed by forest.
The density of churches is remarkable; all built of wood, mostly white, mostly well-kept. This one was attached to the graves
above and is untypically faded (but lovely inside).</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/27/TXT55869.png" alt="Square white wooden church, it needs a paint job" />
<p>Some of the churches have become boutiques and breweries, but those that haven’t still occur more densely than in any other
New World jurisdiction I’ve seen. Why should faith hold stronger down East?</p>
<p>Another church, St Dunstan’s Basilica in Charlottetown, offered perhaps the most intense experience of the whole trip,
because a singer and organist were practicing elaborate hymn treatments. Both were great, the organ is a magnificent Casavant,
and parish organist
<a href="https://en.wikipedia.org/wiki/Leo_Marchildon">Leo Marchildon</a> was having fun, putting lots of wind through those
pipes including the 32’ bass monsters. My ears and I were smiling when we left.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/27/TXT55925.png" alt="Stained glass in St. Dunstan’s Basilica, Charlottetown" />
<div class='caption'><p>The stained glass is nothing special<br/>but I liked the opened panes at the bottom.</p></div>
<p>Forts and cannons, I said; the Maritimes’ messy history included repeated captures and recaptures by the forces of France and
Britain and the USA, and quite a few of the forts had been put to their intended use, repelling or falling to one invader or
another.</p>
<p>The locals, at least the ones who set things up for tourists, seem to take their history seriously; I don’t pretend
expertise or even much interest in it, but I have to say that some cannons have good typography.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/27/PXL_20250824_214613137.png" alt="Engraving on metal: Crown and “VR”" />
<div class='caption'><p>“VR” is Victoria Regina of course,<br/>so sometime in the second half of the 19<sup>th</sup>
century.</p></div>
<p>The colors are different, and an entry later in this series will dip in gleefully and give me a platform for camera geekery.
One expects changes in houses and vegetation when you travel four timezones away, but nothing prepared
me for the shockingly red soil in Prince Edward Island (hereinafter PEI).</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/27/TXT55937.png" alt="red and blue see, red soil, wind turbines" />
<div class='caption'><p>Past Tignish at PEI’s northern extremity,<br/>well off the paved-roads part.</p></div>
<p>I opened with words about everything facing the sea. Not entirely true, sometimes you’re looking at a lake.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/27/PXL_20250823_162017189.png" alt="Kids in a large calm lake, circular ripples" />
<div class='caption'><p>Those kids don’t know how lucky they are.</p></div>
<p>This is in the wonderful Kejimkujik National Park in central Nova Scotia, mostly closed due to extreme wildfire peril.</p>
<p>All across the Maritimes, drought was in effect; crops failing, forest trails closed. Which reminds me; near that lake there was a
birch-bark-canoe workshop. I asked the guy making the canoe how long it took. He said “My great-grandpa could do it in seven days,
because back then there were birch trees big enough that you could make the whole hull out of a single piece.” It’s very
difficult to find any aspect of life on earth that isn’t exhibiting Anthropocene damage.</p>
<p>Usually, it’s the sea that you’re looking at.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/27/TXT56066.png" alt="Nova Scotia coastline near Annapolis Royal" />
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/27/PXL_20250822_223613924.png" alt="rocky beach at low tide" />
<div class='caption'><p>Above, coastline near Annapolis Royal.<br/>Below, low tide near Chipman Brook.</p></div>
<p>From one end of Canada to the other; to me, the surprise was not so much the difference in the landscapes but the similarity
of the people; they spoke my accent, shopped in my stores, obeyed my road signs. More on that later. For now, this.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/08/27/PXL_20250825_141305938.png" alt="Trees frame the seawater and a couple of oceanfront houses" />
<div class='caption'><p>On Bell Island, among the LaHaves.</p></div>
</div></content></entry>
<entry>
<title>RFC 9839 and Bad Unicode</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/08/14/RFC9839' />
<link rel='replies' thr:count='2' type='application/xhtml+xml' href='/ongoing/When/202x/2025/08/14/RFC9839#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/08/14/RFC9839</id>
<published>2025-08-14T12:00:00-07:00</published>
<updated>2025-08-23T03:17:06-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/Text' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Text' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>Unicode is good. If you’re designing a data structure or protocol that has text fields, they should contain Unicode characters encoded in UTF-8. There’s another question, though: “<em>Which</em> Unicode characters?” The answer is “Not all of them, please exclude some.”</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>Unicode is good. If you’re designing a data structure or protocol that has text fields, they should contain
Unicode characters encoded in UTF-8. There’s another question, though:
“<em>Which</em> Unicode characters?” The
answer is “Not all of them, please exclude some.”</p>
<p>This issue keeps coming up, so Paul Hoffman and I put together an individual-submission draft
to the IETF and now (where by “now” I mean “two years later”) it’s been published as
<a href="https://www.rfc-editor.org/rfc/rfc9839.html">RFC 9839</a>. It explains which characters are bad, and why, then offers
three plausible less-bad subsets that you might want to use.
Herewith a bit of background, but…</p>
<h2 id='p-2'>Please</h2>
<p>If you’re actually working on something new that will have text fields, please read the RFC. It’s only ten pages long, and that’s
with all the IETF boilerplate. It’s written specifically for software and networking people.</p>
<h2 id='p-3'>The smoking gun</h2>
<p>The badness that 9839 focuses on is “problematic characters”, so let’s start with a painful example of what that means.
Suppose you’re designing a protocol that uses JSON and one of your constructs has a <code>username</code> field.
Suppose you get this message (I omit all the non-<code>username</code> fields). It’s
a perfectly legal JSON text:</p>
<div class="highlight"><pre><span></span><span class="p">{</span>
<span class="w"> </span><span class="nt">"username"</span><span class="p">:</span><span class="w"> </span><span class="s2">"\u0000\u0089\uDEAD\uD9BF\uDFFF"</span>
<span class="p">}</span> </pre></div>
<p>Unpacking all the JSON escaping gibberish reveals that the value of the <code>username</code> field contains four
numeric “code points” identifying Unicode characters:</p>
<ol>
<li><p>The first code point is zero, in Unicode jargon <code>U+0000</code>. In human-readable text it
has no meaning, but it will interfere with the operation of certain programming languages.</p></li>
<li><p>Next is Unicode <code>U+0089</code>, official name “CHARACTER TABULATION WITH JUSTIFICATION”. It’s what Unicode calls a
<a href="https://en.wikipedia.org/wiki/C0_and_C1_control_codes">C1
control code</a>, inherited from ISO/IEC 6429:1992, adopted from
<a href="https://www.ecma-international.org/wp-content/uploads/ECMA-48_5th_edition_june_1991.pdf">ECMA 48</a> (1991), which calls it
“HTJ” and says: <i>HTJ causes the contents of the active field (the field in the presentation component that contains the
active presentation position) to be shifted forward so that it ends at the character position preceding the
following character tabulation stop. The active presentation position is moved to that following character
tabulation stop. The character positions which precede the beginning of the shifted string are put into the
erased state.</i></p>
<p>Good luck with that.</p></li>
<li><p>The third code point, <code>U+DEAD</code>, in Unicode lingo, is an “unpaired surrogate”. To understand,
you’d have to learn how Unicode’s much-detested
<a href="https://en.wikipedia.org/wiki/UTF-16">UTF-16</a> encoding works.
I recommend not bothering.</p>
<p>All you need to know is that surrogates are only meaningful when they come in pairs in UTF-16 encoded text. There is
effectively no such text on the wire and thus no excuse for tolerating surrogates in your data. In fact, the UTF-8 specification
says that you mustn’t use UTF-8 to encode surrogates. But the real problem is that different libraries in different
programming languages don’t always do the same things when they encounter this sort of fœtid interloper.</p> </li>
<li><p>Finally, <code>\uD9BF\uDFFF</code> is JSON for the code point <code>U+7FFFF</code>.
Unicode has a category called “noncharacter”, containing a few dozen code points that, for a variety of
reasons, some good,
don’t represent anything and must not be interchanged on the wire. <code>U+7FFFF</code> is one of those.</p></li>
</ol>
<p>The four code points in the example are all clearly problematic.
The just-arrived RFC 9839 formalizes the notion of “problematic” and
offers easy-to-cite language saying which of these problematic types you want to
exclude from your text fields. Which, if you’re going to use JSON, you should probably do.</p>
<h2 id='p-6'>Don’t blame Doug</h2>
<p>Doug Crockford I mean, the inventor of JSON. If he (or I or really anyone careful) were inventing JSON now that Unicode is
mature, he’d have been fussier about its character repertoire. Having said that, we’re stuck with JSON-as-it-is forever, so we
need a good way to say which of the problematic characters we’re going to exclude even if JSON allows them.</p>
<h2 id='p-5'>PRECISion</h2>
<p>You may find yourself wondering why the IETF waited until 2025 to provide help with Bad Unicode.
It didn’t; here’s
<a href="https://www.rfc-editor.org/rfc/rfc8264.html">RFC 8264</a>: <cite>PRECIS Framework: Preparation, Enforcement, and
Comparison of Internationalized Strings in Application Protocols</cite>; the first PRECIS predecessor was published in 2002.
8264 is 43 pages long, containing a <em>very</em>
thorough discussion of many more potential Bad Unicode issues than 9839 does.</p>
<p>Like 9839, PRECIS specifies subsets of the Unicode character repertoire and goes further, providing a mechanism for defining
more.</p>
<p>Having said that, PRECIS doesn’t seem to be very widely used by people who are defining new data structures and protocols. My
personal opinion is that there are two problems which make it hard to adopt. First, it’s large and
complex, with many moving parts, and requires careful study to understand. Developers are (for good reason) lazy.</p>
<p>Second, using PRECIS ties you to a specific version of Unicode. In particular, it forbids the use of the (nearly a million)
unassigned code points. Since each release of Unicode includes new code point assignments, that means that a sender and receiver
need to agree on exactly which version of Unicode they’re both going to use if they want reliably interoperable behavior. This
makes life difficult for anyone writing a general-purpose code designed to be used in lots of different applications.</p>
<p>I personally think that the only version of Unicode anybody wants to use is “as recent as possible”, so they can be confident
of having all the latest emojis.</p>
<p>Anyhow, 9839 is simpler and dumber than PRECIS. But I think some people will find it useful and now the IETF agrees.</p>
<h2 id='p-7'>Source code</h2>
<p>I’ve written a little Go-language library to validate incoming text fields against each of the three subsets that 9839
specifies,
<a href="https://github.com/timbray/RFC9839">here</a>. I don’t claim it’s optimal, but it is well-tested.</p>
<p>It doesn’t have a version number or release just yet, I’ll wait till a few folk have had a chance to spot any dumb mistakes I
probably made.</p>
<h2 id='p-9'>Details</h2>
<p>Here’s a compact summary of the world of problematic Unicode code points and data formats and standards.</p>
<table>
<tr valign="top" align="center"><td class="empty"></td><th colspan="3">Problematic classes excluded?</th></tr>
<tr valign="top"><td class="empty"></td><th>Surrogates</th><th>Legacy controls</th><th>Noncharacters</th></tr>
<tr align="center"><td>CBOR</td><td class="happy">yes</td><td class="unhappy">no</td><td class="unhappy">no</td></tr>
<tr align="center"><td>I-JSON</td><td class="happy">yes</td><td class="unhappy">no</td><td class="happy">yes</td></tr>
<tr align="center"><td>JSON</td><td class="unhappy">no</td><td class="unhappy">no</td><td class="unhappy">no</td></tr>
<tr align="center"><td>Protobufs</td><td class="unhappy">no</td><td class="unhappy">no</td><td class="unhappy">no</td></tr>
<tr align="center"><td>TOML</td><td class="happy">yes</td><td class="unhappy">no</td><td class="unhappy">no</td></tr>
<tr align="center"><td>XML</td><td class="happy">yes</td><td class="neutral">partial [1]</td><td class="neutral">partial [2]</td></tr>
<tr align="center"><td>YAML</td><td class="happy">yes</td><td class="neutral">mostly [3]</td><td class="neutral">partial [2]</td></tr>
<tr valign="top" align="center"><td class="empty"></td><th colspan="3">RFC 9839 Subsets</th></tr>
<tr align="center"><td>Scalars</td><td class="happy">yes</td><td class="unhappy">no</td><td class="unhappy">no</td></tr>
<tr align="center"><td>XML</td><td class="happy">yes</td><td class="neutral">partial</td><td class="neutral">partial</td></tr>
<tr align="center"><td>Assignables</td><td class="happy">yes</td><td class="happy">yes</td><td class="happy">yes</td></tr>
</table>
<p>Notes:</p>
<p><b>[1]</b> XML allows C1 controls.</p>
<p><b>[2]</b> XML and YAML don’t exclude the noncharacters outside the Basic Multilingual Pane.</p>
<p><b>[3]</b> YAML excludes all the legacy controls except for the mostly-harmless <code>U+0085</code>, another version of
<code>\n</code> used in IBM mainframe documents.</p>
<h2 id='p-8'>Thanks!</h2>
<p>9839 is not a solo production. It received an extraordinary amount of discussion and improvement from a lot of smart and
well-informed people
and the published version, 15 draft revisions later, is immensely better than my initial draft. My sincere thanks go to my
co-editor Paul Hoffman and to all those mentioned in the RFC’s “Acknowledgements” section.</p>
<h2 id='p-4'>On individual submissions</h2>
<p>9839 is the second “individual submission” RFC I’ve pushed through the IETF (the other is
<a href="https://datatracker.ietf.org/doc/html/rfc7725">RFC 7725</a>, which registers the HTTP 451 status code). While it’s nice
to decide something is worth standardizing and eventually have that happen, it’s really a lot of work. Some of that work is
annoying.</p>
<p>I’ve been involved in
other efforts as Working-Group member, WG chair, and WG specification editor, and I can report authoritatively that creating an
RFC the traditional way, through a Working Group, is easier and better.</p>
<p>I feel discomfort advising others not to follow in my footsteps, but in this case I think it’s the right advice.</p>
</div></content></entry>
<entry>
<title>Long Links</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/08/04/Long-Links' />
<link rel='replies' thr:count='1' type='application/xhtml+xml' href='/ongoing/When/202x/2025/08/04/Long-Links#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/08/04/Long-Links</id>
<published>2025-08-04T12:00:00-07:00</published>
<updated>2025-08-07T11:14:33-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='The World' />
<category scheme='https://www.tbray.org/ongoing/What/' term='The World' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>All of these <cite>Long Links</cite> pieces have begun with more or less the same words, so why stop now? This is an annotated parade of links to long-form pieces. Most people won’t have the time (nor the weird assortment of interests) to consume them all, but I hope that most readers will find one or two reward a visit</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>All of these <cite>Long Links</cite> pieces have begun with more or less the same words, so why
stop now? This is an annotated parade of links to long-form pieces. Most people won’t have the time
(nor the weird assortment of interests) to consume them all, but I hope that most readers will find one
or two
reward a visit.</p>
<h2 id='p-2'>Radisson (and Groseilliers)</h2>
<p>I don’t know if it is still the case, but in my youth, Canadian elementary education included several overexcited units
about the
<a href="https://en.wikipedia.org/wiki/Coureur_des_bois"><i>Coureurs des bois</i></a>, early European settlers
in “New France” (now Québec) who ventured, by foot and canoe, far to the north and west, mostly engaged in trading with the
indigenous peoples: trinkets (and later, serious hardware including guns) for furs.</p>
<p>The names I remembered were Radisson and Groseilliers, but I don’t recall learning much about who they were and what
they did. Then I ran across the 2019 book
<a href="https://www.biblioasis.com/shop/non-fiction/bush-runner-the-life-and-times-of-pierre-esprit-radisson/">Bush Runner:
The Adventures of Pierre-Esprit Radisson</a> and, wow… The writing is pedestrian but who cares because what a
story! Radisson lived an absolutely astonishing life. He went as deep into the bush as anyone of his era, interacted intensely
with the indigenous people as business partner, friend, and foe, worked for Charles of England and Louis of France (changing
sides several times), in 1670 founded the Hudson’s Bay Company (recently, 355 years later, deceased), and fortunately took
notes, a copy of which was preserved by Samuel Pepys.</p>
<p>I learned more from this book’s pages about the early history of Upper and Lower Canada than all those elementary-school
units had to offer, and had loads of fun doing so. I guess this is a fairly Canadian-specific Long Link, but I think anyone
interested in the early history of Europeans in North America would find much to enjoy.</p>
<h2 id='p-4'>Music</h2>
<p>It’s rare these days that I discover interesting new musicians, but here are two of those rarities.</p>
<p><a href="https://luciehorsch.com">Lucie Horsch</a> plays recorder, you know, the cheap plastic thing they use to introduce
second-graders to music. It’s actually a lovely instrument and I wish we would switch to its German name,
“Blockflöte”, which to my ear sounds a bit like the instrument does. Anyhow, check out this YouTube entitled only
<a href="https://www.youtube.com/watch?v=LJyl2D16PZY&list=RDLJyl2D16PZY&start_radio=1">Lucie Horsch - Bach</a>,
annoyingly omitting any mention of <em>which</em> Bach. Annoyance aside, it’s a pretty great performance, Ms Horsch is the real
deal, full of virtuosity and grace.</p>
<p>I got an unusual mid-week message from Qobuz, all excited about
<a href="https://transgressiverecords.com/artist/the-new-eves/">The New Eves’</a> new record <cite>The New Eve Is
Rising</cite>. So I played it in the car on a long crosstown drive and now I’m all excited too. The New Eves are
talented, musically surprising, and above all, insanely brave.</p>
<p>Their music doesn’t sound like anything else and
flies in the face of all conventional wisdom concerning popular music. They take absurd chances and yeah, the album has klunkers
amid the bangers, but when I got to its end I went back and started at the beginning again. I found myself
smiling ear-to-ear over and over. Maybe I’m being a bit over-the-top here, but check them out:
<a href="https://www.youtube.com/watch?v=l9Q9ge6j_O4&list=RDl9Q9ge6j_O4&start_radio=1">Mother</a> is live.
<a href="https://www.youtube.com/watch?v=MovNWuNPXXE&list=RDMovNWuNPXXE&start_radio=1">Cow Song</a> is off the new
album and strong albeit with forgettable video.</p>
<h2 id='p-3'>Life online</h2>
<p>Every Long Links has hardcore-geek threads and there is no harder core imaginable than Filippo Valsordi’s
<a href="https://words.filippo.io/assembly-mutation/">Go Assembly Mutation Testing</a>. I have always admired (but never
actually used) mutation testing, and Filippo offers a convincing argument that it moves catching certain classes of bug from
nearly impossible to pretty easy. Good stuff!</p>
<p>And of course we can’t ignore genAI and programming. Most of you are likely aware of
<a href="https://metr.org/blog/2025-07-10-early-2025-ai-experienced-os-dev-study/">Measuring the Impact of Early-2025 AI on
Experienced Open-Source Developer Productivity</a>, but I’m linking again to boost its visibility, because hard
quantitative research on methodology is damn rare in our profession. I will confess to being a little (but just a little)
surprised at the conclusions.</p>
<p>It is apparently quite possible that Intel will exit the business of making high-end chips, leaving TSMC with a global
monopoly:
<a href="https://d2d.substack.com/p/d2d-contd-intel-and-the-wide-open">Intel and the Wide Open Barn Doors</a>.
This is an unsettling prospect.
Not, I have to say, surprising though. I’ve sneered at Intel leadership cluelessness for years and years, see
<a href="/ongoing/When/200x/2006/01/14/On-Intel">here</a> and
<a href="/ongoing/When/200x/2006/02/16/Viiv-Jive">here</a>.</p>
<p>Finally, here’s the charmingly-titled
<a href="https://www.raptitude.com/2025/06/how-to-surf-the-web-in-2025-and-why-you-should/">How to Surf the Web in 2025, and
Why You Should</a>. I love this piece.</p>
<h2 id='p-1'>Class Reductionism</h2>
<p>The news keeps making me want to build something around the <code>classreductionist.org</code> domain name I’ve owned for
years.</p>
<p>The tl;dr on Class Reductionism is something like “In the best possible world it’ll take generations to disassemble the
global tangle of intersectional oppression, but we could treat the symptoms effectively <em>right now this year</em> by sending
money to the poor. I’m talking about Universal Basic Income or suchlike. I wrote a
<a href="/ongoing/When/202x/2023/01/16/Class-Reductionism">couple thousand words</a> on the subject back in 2023, and there are
complexities, and I probably won’t put up that site. But I still do maintain that a very high proportion of our societal pain is
rooted in the egregious inequality, and consequent poverty, that seems a baked-in feature of Late Capitalism.</p>
<p>Let’s start with Nobelist Paul Krugman, who’s been writing an “Understanding Inequality” series on his paywalled newsletter
and then republishing a gratis version, start
<a href="https://stonecenter.gc.cuny.edu/tag/focus-inequality/">here</a>. Very data-dense and educational.
Hmm, that site is slow; there’s a livelier table of contents
<a href="https://paulkrugman.substack.com/p/i-coulda-made-a-better-deal">here</a>.</p>
<p>Don’t kid yourself that this is just an American problem, see
<a href="https://www.nytimes.com/2025/06/23/business/china-upward-mobility-inequality.html?unlocked_article_code=1.cE8.Ptfc.XicZ0XVgHPsJ&smid=url-share">‘The Better Life Is Out of Reach’: The Chinese Dream Is Slipping Away</a>.</p>
<p>Let’s pull the impersonal veil of facts and figures aside and focus on the human experience of what we used to call Class Struggle.
<a href="https://macleans.ca/society/confessions-of-the-working-poor/">Confessions of the Working Poor</a> is beautifully
written and opened my eyes to lifestyle choices that I didn’t even know some people have to make.</p>
<p>But hey, there are people who are just fine with this:
<a href="https://finance.yahoo.com/news/deltas-premium-play-is-taking-advantage-of-the-growing-economic-split-100044776.html">Delta's
premium play is taking advantage of the growing economic split</a>.</p>
<p>Look, being class-determinist-adjacent doesn’t mean you should ignore intersectional awfulness:
<a href="https://www.newyorker.com/magazine/2025/08/04/the-plunder-of-black-america-calvin-schermerhorn-book-review">What We
Miss When We Talk About the Racial Wealth Gap</a>.</p>
<h2 id='p-5'>No more sections</h2>
<p>The remaining Long Links refused to be organized so I had to turn them loose; call it the Long Tail.</p>
<p><a href="https://articles.c-a-s-t.com/the-venetian-origins-of-roman-type-a856eb3f0cb">The Venetian origins of roman
type</a>. You might think you don’t care about typography but still enjoy the pictures and descriptions here.</p>
<!--
<p><a href="https://www.newyorker.com/magazine/2025/07/28/mary-had-schizophrenia-then-suddenly-she-didnt">Mary Had
Schizophrenia—Then Suddenly She Didn’t</a></p>-->
<p>This guy is a full-time
<a href="https://urbancoyoteresearch.com/researcher/stanley-d-gehrt-phd">Coyote researcher</a>. What a great gig! I’m an admirer
of those animals and how they’ve carved themselves a comfy niche in most of North America’s big cities. (Even if it means that
you better not let your cat out at night.) They’re also remarkably attractive.</p>
<p>Here’s another long list of Long Links, and many of you will wonder why anyone would choose to browse it:
<a href="https://petapixel.com/2025/07/18/the-best-camera-stores-in-tokyo-the-ultimate-guide/">The Best Camera Stores in
Tokyo: The Ultimate Guide</a>. Some of the interiors are remarkable.</p>
<p>Oh, while we’re on the subject of photography:
<a href="https://petapixel.com/2025/07/22/a-photojournalist-took-a-fujifilm-instax-camera-to-a-cartel-wedding/">A
Photojournalist Took a Fujifilm Instax Camera to a Mexican Cartel Wedding</a>.</p>
<p>GLP-1’s (i.e. Ozempic and friends) would probably dominate a large section of the news if weren’t for all the political
craziness. Here’s one small example:
<a href="https://www.glp1digest.com/p/how-glp-1s-are-breaking-life-insurance">How GLP-1s Are Breaking Life Insurance</a>.</p>
<p>Science is hard. There are lots of largely-unsolved areas, and “gap-map.org” tries to organize them:
<a href="https://www.gap-map.org/?sort=rank&utm_source=substack&utm_medium=email&fields=astrophysics">Fundamental
Development Gap Map v1.0</a>. The UI is a little klunky but the thing still sucked me right in.</p>
<p>I’m going to give the last word to Laurie Penny. I don’t know what we’d do without her.
<a href="https://lauriepenny.substack.com/p/in-a-time-of-monsters-do-we-have">In a time of monsters: do we have any ideas for
surviving the zombie apocalypse that aren’t nightmare patriarchy?</a></p>
</div></content></entry>
<entry>
<title>De-Google Project Update</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/07/29/DeGoogling' />
<link rel='replies' thr:count='19' type='application/xhtml+xml' href='/ongoing/When/202x/2025/07/29/DeGoogling#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/07/29/DeGoogling</id>
<published>2025-07-29T12:00:00-07:00</published>
<updated>2025-07-31T12:06:18-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='The World/Life Online/De-Google' />
<category scheme='https://www.tbray.org/ongoing/What/' term='The World' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Life Online' />
<category scheme='https://www.tbray.org/ongoing/What/' term='De-Google' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>I <a href='/ongoing/When/202x/2024/03/09/DeGoogling'>introduced this family project</a> in the spring of 2024. I won’t reproduce those arguments for why we’re working on this, but in the current climate I feel like I hardly need to. Since that post, our aversion to Google dependency has only grown stronger. Progress has been non-zero but not fast</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>I
<a href="/ongoing/When/202x/2024/03/09/DeGoogling">introduced this family project</a> in the spring of 2024.
I won’t reproduce those arguments for why we’re working on this, but in the current climate I feel like I hardly need to.
Since that post, our aversion to Google dependency has only grown stronger. Progress has been non-zero but not fast.</p>
<p>Here’s the table, with progress notes below.</p>
<table>
<tr valign="top"><th>Need</th><th>Supplier</th><th>Alternatives</th></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-3">Office</a></td>
<td class="unhappy">Google Workspace</td>
<td>Proton?</td>
</tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-17">Data sharing</a></td>
<td class="happy">Dropbox</td>
<td></td></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-17">Photos</a></td>
<td class="unhappy">Google Photos</td>
<td>Dropbox?</td></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-16">Video meetings</a></td>
<td class="unhappy">Google
Meet</td>
<td>Jitsi, Signal?</td></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-10">Maps</a></td>
<td class="unhappy">Google Maps</td>
<td>Magic Earth, Here, something OSM-based?</td></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-4">Browser</a></td>
<td class="happy">Safari, Firefox, Vivaldi, LibreWolf</td>
<td></td></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-12">Search</a></td>
<td class="unhappy">Google</td>
<td>Bing-based options, Kagi?</td></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-5">Chat</a></td>
<td class="happy">Signal</td>
<td></td></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-6">Photo editing</a></td>
<td class="neutral">Adobe
Lightroom & Nik</td>
<td>Capture One, Darktable, ?</td></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-7">In-car interface</a></td>
<td class="neutral">Google Android Auto</td>
<td>Automaker software</td></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-8">Play my music</a></td>
<td class="happy">Plex, USB</td>
<td></td></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-9">Discover music</a></td>
<td class="happy">Qobuz</td>
<td></td></tr>
<tr valign="top">
<td><a href="/ongoing/When/202x/2024/03/09/DeGoogling#p-13">TV</a></td>
<td class="neutral">Roku, Apple, migration</td>
<td></td></tr>
</table>
<p>Pink indicates a strong desire to get off the incumbent service, green means we’re happy-ish with what we’re using, and blue
means that, happy or not, it’s not near the top of the priority list.</p>
<p>I’ll reproduce the metrics we care about when looking to replace Google products, some combination of:</p>
<ol>
<li><p>Not ad-supported</p></li>
<li><p>Not VC-funded</p></li>
<li><p>Not Google, Microsoft, or Amazon</p></li>
</ol>
<p>The list used to include “Open Source” but I decided that while that’s good, it’s less important than the other three criteria.</p>
<p>Now let’s walk down the chart.</p>
<h2 id='p-3'>Office</h2>
<p>This is going to be a wrenching transition; we’ve been running the family on Google stuff forever, and I anticipate
muscle-memory pain. But increasingly, using Google apps feels like being in enemy territory. And, as I said last time, I
will not be sorry to shake the dust of Google Drive and Docs from my heels, I find them clumsy and am
always having trouble finding something that I know is in there.</p>
<p>While I haven’t dug in seriously yet, I keep hearing reasonably-positive things about Proton, and nothing substantive to
scare me away. Wish us luck.</p>
<h2 id='p-17'>Data sharing (progress!)</h2>
<p>Dropbox is, eh, OK. It doesn’t seem actively evil, there’s no advertising, and the price is low.</p>
<h2 id='p-21'>Photos</h2>
<p>We’re a four-Android family including a couple of prolific photographers, and everything just gets pumped into Google and
then it fills up and then they want more money. If we could configure the phones to skip Google and go straight to Dropbox,
that would be a step forward.</p>
<h2 id='p-16'>Video meetings</h2>
<p>Google meet isn’t painful but I totally suspect it of data-mining what should be private conversations. I’m getting the
feeling that the technical difficulty of videoconferencing is going steadily down, so I’m reasonably optimistic that
something a little less evil will come along with a fair price.</p>
<h2 id='p-10'>Maps</h2>
<p>The fear and loathing that
<a href="/ongoing/When/201x/2017/06/29/Fear-Google-Reviews">I started feeling in 2017</a> grows only stronger. But replacements
aren’t obvious.
It’s a pity, maps
and directions and reviews feel like a natural monopoly that should be a public utility or something, rather than a corporate moat.</p>
<h2 id='p-4'>Browser (progress!)</h2>
<p>Chrome has seriously started making my flesh crawl; once again, enemy territory. Fortunately, there are lots of good options.
Even people like us who have multiple lives we need to keep separate can find enough better browsers out there.</p>
<p>Maybe I’ll have a look at one of the new genAI-company browsers ha ha just kidding.</p>
<h2 id='p-12'>Search</h2>
<p>The reports on Kagi keep being positive and giving it a try is definitely on the To-Do list.</p>
<h2 id='p-5'>Chat</h2>
<p>Signal is the only sane choice at this point in history for personal use.</p>
<h2 id='p-6'>Photo editing</h2>
<p>Adobe’s products are good, and I’m proficient and happy with Lightroom, but they are definitely suffering from bad genAI
craziness. Also the price is becoming unreasonable.</p>
<p>I’ve had a few Lightroom software failures in recent months and if that
becomes a trend, looking seriously at the alternatives will move to the top of the priority list.</p>
<h2 id='p-7'>In-car interface</h2>
<p>It’s tough, Android Auto is a truly great product. I think I’m stuck here for now, particularly given that I plan to be
driving a <a href="/ongoing/What/The%20World/Jaguar%20Diary/">2019-model-year car</a> for the foreseeable future. Also, it
supports my music apps.</p>
<h2 id='p-9'>Discover music and play mine (progress!)</h2>
<p>Progress here. I’ve almost completely stopped using YouTube Music in favor of Plex and Qobuz. Really no downside; YTM has
more or less completely lost the ability to suggest good new stuff.</p>
<h2 id='p-13'>TV</h2>
<p>Video continues morphing itself into Cable TV redux. We have an old Roku box that works fine and I think I’ve managed to find
its don’t-spy-on-us settings. We’ll keep subscribing to Apple+ as long as they keep shipping great shows. I have zero regrets
about having
<a href="/ongoing/When/202x/2025/03/06/Canceled-Prime">left Prime behind</a>.</p>
<p>As for the rest, we’ve become migrants,
exclusively month-at-a-time subscriptions for the purpose of watching some serial or sports league, unsubscribe after the season
finale or championship game. The good news is that I
haven’t encountered much friction in unsubscribing, just a certain amount of earnest pleading.</p>
<h2 id='p-20'>Looking forward</h2>
<p>I have yet to confront any of the really hard parts of this project, but the sense of urgency is increasing. Let’s see.</p>
</div></content></entry>
<entry>
<title>QRS: Finite-state Struggles</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/07/21/Automaton-merge-war' />
<link rel='replies' thr:count='2' type='application/xhtml+xml' href='/ongoing/When/202x/2025/07/21/Automaton-merge-war#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/07/21/Automaton-merge-war</id>
<published>2025-07-21T12:00:00-07:00</published>
<updated>2025-07-22T09:10:25-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/Quamina Diary' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Quamina Diary' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/Software' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Software' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>I just posted a big <a href='https://github.com/timbray/quamina'>Quamina</a> PR representing months of work, brought on by the addition of a small basic regular-expression feature. This ramble doesn’t exactly have a smooth story arc but I’m posting it anyhow because I know there are people out there interested in state-machine engineering and they are my people</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>I just posted a big
<a href="https://github.com/timbray/quamina">Quamina</a> PR representing months of work, brought on
by the addition of a small basic regular-expression feature. This ramble doesn’t exactly have a smooth story arc but I’m
posting it anyhow because I know there are people
out there interested in state-machine engineering and they are my people.</p>
<p>As far as I can tell, a couple of the problems I’m trying to solve
haven’t been addressed before, at least not by anyone who published their findings.
Partly because of that, I’m starting to wonder if all
<a href="/ongoing/What/Technology/Quamina%20Diary/">these disorderly Quamina postings</a> might
be worked into a small book or monograph or something. State machines are really freaking useful software constructs!
So yeah, this is a war story not an essay, but if you like finite automata you’ll likely be interested in bits of it.</p>
<h2 id='p-1'>The story thus far</h2>
<p>Prior to beginning work on Regular Expressions, I’d already wired shell-style “<code>*</code>” wildcards into Quamina, which
forced me to start working with NFAs and ε-transitions. The implementation wasn’t crushingly difficult, and
the performance was… OK-ish.</p>
<p>Which leads me to The Benchmark From Hell.
I wondered how the wildcard functionality would work under heavy stress, so I pulled in a list of 12,959 five-letter strings
from the Wordle source code, and inserted a “<code>*</code>” at a random position in each. Here are the first ten:</p>
<blockquote><pre><code>aalii*
*aargh
aar*ti
abaca*
a*baci
a*back
ab*acs
ab*aft
abak*a</code></pre></blockquote>
<p>I created an NFA for each and merged them together
<a href="/ongoing/When/202x/2024/07/28/Union-of-Finite-Automata">as described here</a>. Building and merging the automata were
plenty fast enough, and the merged NFA had 46,424 states, which felt reasonable.
Matching strings against it ran at under ten thousand per second, which is pretty poor given that Quamina can do a million or
two per second on patterns encoded in a DFA.</p>
<p>But, I thought, still reasonably usable.</p>
<h2 id='p-2'>The cursed “<code>?</code>”</h2>
<p>Last year, my
<a href="/ongoing/When/202x/2024/12/12/Quamina-Regular-Expression-Series">slow grind through the regexp features</a> had led me
to the zero-or-one quantifier “<code>?</code>”. The state machine for these things is not rocket science; there’s a discussion
with pictures in my recent
<a href="/ongoing/When/202x/2025/07/07/Epsilon-Wrangling#p-3">Epsilon Wrangling</a>.</p>
<p>So I implemented that and fired off the unit tests, most of which
<a href="/ongoing/When/202x/2024/12/12/QRS-Parsing-Regular-Expressions#p-1">I didn’t have to write</a>, and they all failed.
Not a surprise I guess.</p>
<p>It turned out that the way I’d implemented ε-transitions for the wildcards
<a href="/ongoing/When/202x/2024/07/28/Union-of-Finite-Automata#p-9">was partially wrong</a>, as in it worked for the tight-loop
state-to-itself ε-transitions, but not for more general-purpose things like “<code>?</code>” requires.</p>
<p>In fact, it turns out that merging NFAs is hard (DFAs are easy), and I found precious little help online.
<a href="https://en.wikipedia.org/wiki/Thompson%27s_construction">Thompson’s construction</a> does give an answer: Make an
otherwise-empty state with two ε-transitions, one to each of the automata, and it’ll do the right thing. Let’s call that
a “splice state”. It’s easy to implement, so I did. Splicing is hardly “merging” in the Quamina sense, but still.</p>
<p>Unfortunately, the performance was hideously bad, just a few matches per second while pegging the CPU.
A glance at the final NFA was sobering; endless chains of splice states, some thousands long.</p>
<p>At this point
I became very unhappy and got stalled for months dealing with real-life issues while this problem lurked at the back
of my mind, growling for attention occasionally.</p>
<p>Eventually I let the growler out of the cave and started to think through approaches. But first…</p>
<h2 id='p-4'>Worth solving?</h2>
<p>Is it, really? What sane person is going to want to search for the union of thousands of regular expressions in general or
wild-carded strings in particular?</p>
<p>I didn’t think about this problem at all, because of my experience with Quamina’s parent,
<a href="https://github.com/aws/event-ruler">Ruler</a>. When it became popular among several AWS and Amazon teams, people
sometimes found it useful to match the union of not just thousands but a million or more different patterns. When you write
software that anyone actually uses, don’t expect the people using it to share your opinions on what is and isn’t
reasonable. So I wasn’t going to get any mental peace until I cracked this nut.</p>
<p>I eventually decided that three approaches were worth trying:</p>
<ol>
<li><p>Figure out a way really to merge, not just splice, the wildcarded patterns, to produce a simpler automaton.</p></li>
<li><p>Optimize the NFA-traversal code path.</p></li>
<li><p>Any NFA can be transformed into a DFA, says computer-science theory. So do that, because Quamina is really fast at
DFA-based matching.</p></li>
</ol>
<h2 id='p-5'>Nfa2Dfa</h2>
<p>I ended up doing all of these things and haven’t entirely given up on any of them.
The most intellectually-elegant was the transform-to-DFA approach, because if I did that, I could remove the fairly-complex
NFA-traversal logic from Quamina.</p>
<p>It turns out that the Net is rich with textbook extracts and YouTubes and slide-shows about how to do the NFA-to-DFA
conversion. It ended up being quite a pleasing little chunk of code, only a couple hundred lines.</p>
<p>The bad news: Converting each individual wildcard NFA to a DFA was amazingly fast, but then as I merged them in one by one,
the number of automaton states started increasing explosively and the process slowed down so much that I never had the patience
to let it finish. Finite-automata theory warns that this can happen, but it’s hard to characterize the cases where it does.
I guess this one of them.</p>
<p>Having said that, I haven’t discarded the <code>nfa2Dfa</code> code, because perhaps I ought to offer a Quamina option to
apply this if you have some collection of patterns that you want to run really super fast and are willing to wait for a while
for the transformation process to complete. Also, I may have missed opportunities to optimize the conversion; maybe it’s making
more states than it needs to?</p>
<h2 id='p-6'>Faster NFA traversal</h2>
<p>Recently in
<a href="/ongoing/When/202x/2025/07/07/Epsilon-Wrangling">Epsilon wrangling</a> I described how NFA traversal has to work,
relying heavily on implementing a thing called an ε-closure.</p>
<p>So I profiled the traversal process and discovered, unsurprisingly, that most of the time was going into memory allocation
while computing those ε-closures. So now Quamina has an ε-closure cache and will only compute each one once.</p>
<p>This helped a lot but not nearly enough, and the profiler was still telling me the pain was in Go’s allocation and
garbage-collection machinery. Whittling away at this kind of stuff is not rocket science. The standard Go trick I’ve seen over
and over is to keep all your data in slices, keep re-using them then chopping them back to <code>[:0]</code>
for each request. After a while they’ll have grown to the
point where all the operations are just copying bytes around, no allocation required.</p>
<p>Which also helped, but the speed wasn’t close to what I wanted.</p>
<h2 id='p-7'>Merging wildcard automata</h2>
<p>I coded multiple ways to do this, and they kept failing. But I eventually found a way to build those
automata so that any two of them, or any one of them and a DFA, can merged and generate dramatically
fewer ε-transition chains. I’m not going to write this up here for two reasons: First of all, it’s not <em>that</em>
interesting, and second, I worry that I may have to change the approach further as I go on implementing new regxp operators.</p>
<p>In particular, at one point I was looking at the code while it wasn’t working, and I could see that if I added a particular
conditional it would work, but I couldn’t think of a principled reason to do it. Obviously I’ll have to sort this out
eventually. In the meantime, if you’re the sort of um special person who is now burning with curiosity, check out my branch from
that PR and have a look at the <code>spinout</code> type.</p>
<p>Anyhow, I added that conditional even though it puzzled me a bit, and now you can add wildcard patterns to Quamina at 80K/second,
and my 12.9K wildcards generate an NFA with with almost 70K states, which can scan events at almost 400K/second. And that’s good
enough to ship the <code>“?”</code> feature.</p>
<p>By the way, I tried feeding that 70K-state automaton to the DFA converter, and gave up after it’d burned an hour of CPU and
grown to occupy many GB of RAM.</p>
<h2 id='p-8'>Next steps</h2>
<p>Add “<code>+</code>” and “<code>*</code>”, and really hope I don’t have to redesign the NFA machinery again.</p>
<p>Also, figure out the explanation for that puzzling <code>if</code> statement.</p>
<h2 id='p-9'>And I should say…</h2>
<p>Despite the very narrow not to say obsessive focus of this series, I’ve gotten a few bits and pieces of positive feedback. So
there are a few people out there who care about this stuff. To all of you, thanks.</p>
</div></content></entry>
<entry>
<title>Memory in Saskatchewan</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/07/09/Saskatchewan' />
<link rel='replies' thr:count='9' type='application/xhtml+xml' href='/ongoing/When/202x/2025/07/09/Saskatchewan#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/07/09/Saskatchewan</id>
<published>2025-07-09T12:00:00-07:00</published>
<updated>2025-07-16T10:11:34-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='The World/Places/Saskatchewan' />
<category scheme='https://www.tbray.org/ongoing/What/' term='The World' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Places' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Saskatchewan' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Arts/Photos' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Arts' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Photos' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>I just came back from Canada’s <a href='https://en.wikipedia.org/wiki/Saskatchewan'>only rectangular province</a>. I was there to help out my 95-year-old mother while her main caregiver took vacation. It’s an unhappiness that my family has splashed itself across Canada in such a way that we have to get on an airplane (or take drives measured in days) to see each other, but that’s where we are. I came back with pictures and stories</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>I just came back from Canada’s
<a href="https://en.wikipedia.org/wiki/Saskatchewan">only rectangular province</a>. I was there to help out my 95-year-old
mother while her main
caregiver took vacation. It’s an unhappiness that my family has splashed itself across Canada in such a way that we have to get
on an airplane (or take drives measured in days) to see each other, but that’s where we are. I came back with pictures and
stories.</p>
<p>Let me set the stage with a couple of photos. Everyone knows that Saskatchewan is flat and brown and empty, right?</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/09/TXT55665.png" alt="Flowers, intensely colored in near-black purple and yellow" />
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/09/TXT55710.png" alt="Trees and lawns, behind a still body of water and somewhat reflected in it" />
<p>Mom lives in
<a href="https://en.wikipedia.org/wiki/Regina,_Saskatchewan">Regina</a>, the provincial capital, a city built round a huge
park that contains the Legislature (the flowers are from its front lawn), a sizeable lake, and an artificial
mini-mountain (the water and trees are from its tip).
Have no fear, I’ll get to some no-kidding prairie landscapes.</p>
<h2 id='p-1'>Health-care drama</h2>
<p>The night I arrived, after my Mom went to bed she got up again, tripped on something and fell hard. Her right arm was
swollen, bruised, and painful. The skin and adjacent blood vessels of very old people become thin and fragile; her whole
forearm was a bruise. I tried to get her to go to Emergency but she wasn’t having any of it: “You wait for hours and then they
give you a pain-killer, which is constipating.” Since she could twist her wrist and wiggle her fingers and give my hand a firm
grasp, I didn’t push too hard.</p>
<p>A couple days later on Saturday she got her regular twice-a-week visit from the public
<a href="https://www.saskatchewan.ca/residents/health/accessing-health-care-services/care-at-home-and-outside-the-hospital/home-care">HomeCare</a>
nurse, a friendly and highly competent Nigerian immigrant, to check her meds and
general condition.
She looked at Mom’s wrist and said “Get her an appointment with her doctor, they’ll probably want an X-Ray.”</p>
<p>I called up her doctor at opening time Monday. The guy who answered the phone said
“Don’t have any appointments for a couple weeks but come on over, we’ll squeeze her in.” So we went in after morning coffee and
waited less than an hour.
The doctor looked at her arm for 45 seconds and said “I’m writing a prescription for an X-Ray” and there was a
radiologist around the corner and she was in ten minutes later. The doctor called me back that afternoon and said “Your
mother’s got a broken wrist, I got her an 8AM appointment tomorrow at Regina General’s Cast Clinic.”</p>
<p>The doctor at the clinic looked at her wrist for another 45 seconds and said “Yeah, put on a cast” so they did and we were
home by ten. I’d pessimistically overpaid a couple bucks for hospital parking.</p>
<p>The reason I’m including this is because I notice that this space has plenty of American readers. Did you notice that the
story entirely omits insurance companies and money (except parking)? In Canada your health-care comes with your taxes (granted,
higher than Americans’) and while the system is far from perfect, it can fix up an old lady’s broken wrist pretty damn fucking
quick without any bureaucratic bullshit. Also, Canada spends a huge amount less per head on health-care than the US does.</p>
<p>And Mom told me not to forget that Saskatchewan is the birthplace of Canadian single-payer universal healthcare.
<a href="https://en.wikipedia.org/wiki/Tommy_Douglas">Tommy Douglas</a>, the Social Democrat who made that happen, has been
named
<a href="https://en.wikipedia.org/wiki/The_Greatest_Canadian">The Greatest Canadian</a>.</p>
<h2 id='p-2'>Gentle surface</h2>
<p>Oh, did I say “flat and brown and empty”? Wrong, wrong, and wrong. The Prairies, in Canada and the US too, have textures and
colors and hills and valleys, it’s just that the slopes are gentle. There are really flat parts and they make farmers’ lives easier, but
more or less every square inch that’s not a town or a park is farmed.
I took Mom for a drive out in the country southeast of Regina, from whence these views:</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/09/TXT55698.png" alt="A road leading slightly uphill, brilliant yellow canola on both sides" />
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/09/TXT55700.png" alt="Yellow canola flowers under a blue sky" />
<div class='caption'><p>Note that in both shots we’re looking up a gentle slope. In the second, there’s farm infrastructure on
the distant horizon.<br/>Also consider the color of the sky.</p></div>
<p>In Canada that yellow-flowering crop is called “Canola”, which Wikipedia claims refers to a particular cultivar of
<i>Brassica napus</i>, commonly known as rapeseed or just rape, so you can see why when Canada’s
agribiz sector wanted to position its oil as the thing to use while cooking they went for the cultivar not the species
name. I’m old enough to remember when farmers still said just “rapeseed”. Hmm, Wikipedia also claims that the OED claims this:
The term “rape” derives from the Latin word for turnip, <i>rāpa</i> or <i>rāpum</i>, cognate with the Greek word ῥάφη,
<i>rhaphe</i>.</p>
<p>Let’s stick with canola.</p>
<h2 id='p-4'>Pixelated color</h2>
<p>After I’d taken those two canola-field shots I pulled out my Pixel and took another, but I’m not gonna share it because the
Pixel decided to turn the sky from what I thought was a complex and interesting hue into its opinion of “what a blue sky looks
like” only this sky didn’t.</p>
<p>Maybe it’s just me, but I think Google’s camera app is becoming increasingly opinionated about color, and not in a good
way. There are plenty of alternative camera apps, I should check them out.</p>
<p>In case it’s not obvious, I love photographing Saskatchewan and think it generally looks pretty great, especially when you
look up. On the province’s license plates it says “Land of living skies”, and no kidding.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/09/PXL_20250704_032320050.png" alt="Saskatchewan’s living skies" />
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/09/PXL_20250704_032334240.png" alt="Saskatchewan’s living skies" />
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/09/TXT55717.png" alt="Saskatchewan’s living skies"/>
<div class='caption'><p>The first two are from the park behind Mom’s place,<br/>the third from that mini-mountain mentioned
above.</p></div>
<h2 id='p-6'>Experience and memory</h2>
<p>My Mom’s doing well for a nonagenerian. She’s smart. When I visited early last fall and we talked about the US election I was
bullish on Kamala Harris’s chances. She laughed at me and said “The Americans won’t elect a woman.” Well then.</p>
<p>But she’s forgetful in the short term. I took her to the Legislature’s
garden and to the top of the mini-mountain and for a drive out in the country and another adventure we’ll get to; she
enjoyed them all. But maybe she won’t remember them.</p>
<p>“Make memories” they say, but what if you show someone you love a good time and maybe they won’t remember it the
next day? I’m gonna say it’s still worthwhile and has a lesson to teach about what matters. There endeth the lesson.</p>
<h2 id='p-5'>The gallery</h2>
<p>Indigenous people make up 17% of Regina’s population, the highest share in any significant Canadian city. By “indigenous” I
mean the people that my ancestors stole the land from. It’s personal with me; Around 1900, my Dad’s family, Norwegian
immigrants, took over some pretty
great farmland southeast of Edmonton by virtue of “homesteading”, such a <em>nice</em> word isn’t it?</p>
<p>Regina tries to honor its indigenous heritage and my favorite expression of that is its
<a href="https://mackenzie.art">Mackenzie Art Gallery</a>, a lovely welcoming space in the
<a href="https://www.saskatchewan.ca/government/directory?ou=a8e54600-77d6-4b7e-9702-f07a3dac1b47">T.C.Douglas building</a> (for
“T.C.” read “Tommy”. (Did I mention him?) Mom and I walked around it and had lunch in its very decent café.</p>
<p>Every time I’ve been there the big exhibitions in the big rooms have been indigenous-centered, and generally excellent.
I try to go every time I visit and I’ve never been disappointed.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/09/PXL_20250708_172437441.png" alt="Indigenous art at Regina’s Mackenzie Gallery" />
<p>In 2025, anything I have to say about this piece would be superfluous.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/09/PXL_20250708_173041377.png" alt="Every American Flag Is A Warning Sign" />
<p>I love modern-art galleries, especially with big rooms full of big pieces, even if I don’t like all the art.
Because it feels good to be in the presence of the work of people who are pouring out
what they have to offer, especially at large scale. If the task wasn’t hard enough that failures
are common then it wouldn’t be worthwhile, would it?</p>
<p>They’re especially great when there’s someone I love there enjoying it with me. Here’s Mom.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/09/PXL_20250708_172836385.png" alt="Jean Bray considers indigenous art" />
<p>These days, any visit might be the last. I hope this wasn’t.</p>
</div></content></entry>
<entry>
<title>QRS: Epsilon Wrangling</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/07/07/Epsilon-Wrangling' />
<link rel='replies' thr:count='0' type='application/xhtml+xml' href='/ongoing/When/202x/2025/07/07/Epsilon-Wrangling#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/07/07/Epsilon-Wrangling</id>
<published>2025-07-07T12:00:00-07:00</published>
<updated>2025-07-09T19:41:00-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/Quamina Diary' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Quamina Diary' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/Software' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Software' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>I haven’t shipped any new features for <a href='https://github.com/timbray/quamina'>Quamina</a> in many months, partly due to a flow of real-life distractions, but also I’m up against tough performance problems in implementing <a href='/ongoing/When/202x/2024/12/12/Quamina-Regular-Expression-Series'>Regular Expressions at massive scale</a>. I’m still looking for a breakthrough, but have learned things about building and executing finite automata that I think are worth sharing. This piece has to do with <a href='https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton#NFA_with_ε-moves'>epsilons</a>; anyone who has studied finite automata will know about them already, but I’ll offer background for those people to skip</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>I haven’t shipped any new features for
<a href="https://github.com/timbray/quamina">Quamina</a> in many months, partly due to a flow of real-life distractions, but
also I’m up against tough performance problems in implementing
<a href="/ongoing/When/202x/2024/12/12/Quamina-Regular-Expression-Series">Regular Expressions at massive scale</a>.
I’m still looking for a breakthrough, but have learned things about building and executing finite automata
that I think are worth sharing. This piece has to do with
<a href="https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton#NFA_with_ε-moves">epsilons</a>; anyone who has studied
finite automata will know about them already, but I’ll offer background for those people to skip.</p>
<p>I’ve written about this before in
<a href="/ongoing/When/202x/2024/06/17/Epsilon-Love">Epsilon Love</a>. A commenter pointed out that the definition of “epsilon”
in that piece is not quite right per standard finite-automata theory, but it’s still a useful in that it describes how
epsilons support constructs like the shell-style “<code>*</code>”.</p>
<h2 id='p-2'>Background</h2>
<p>Finite automata come in two flavors: Deterministic (DFA) and Nondeterministic (NFA). DFAs move from state to state one input
symbol at a time: it’s simple and easy to understand and to implement.
NFAs have two distinguishing characteristics: First, when you’re in a
state and an input symbol arrives, you can transfer to more than one other state. Second, a state can have “epsilon transitions”
(let’s say “ε” for epsilon), which can happen any time at all while you’re in that state, input or no input.</p>
<p>NFAs are more complicated to traverse (will discuss below) but you need them if you want to
implement regular expressions with <code>.</code> and <code>?</code> and <code>*</code> and so on. You can turn any NFA into a
DFA, and I’ll come back to that subject in a future piece.</p>
<p>For implementing NFAs, I’ve been using
<a href="https://en.wikipedia.org/wiki/Thompson%27s_construction">Thompson's construction</a>, where
“Thompson” is
<a href="https://en.wikipedia.org/wiki/Ken_Thompson">Ken Thompson</a>, co-parent of Unix. This technique is also nicely
described by Russ Cox in
<a href="https://swtch.com/~rsc/regexp/regexp1.html">Regular Expression Matching Can Be Simple And Fast</a>. You don’t need to
learn it to understand this piece, but I’ll justify design
choices by saying “per Thompson”.</p>
<p>I’m going to discuss two specific issues today, ε-closures and a simpler NFA definition.</p>
<h2 id='p-3'>ε-closures</h2>
<p>To set the stage, consider this regexp: <nobr><code>A?B?C?X</code></nobr></p>
<p>It should match “X” and “BX” and “ACX” and so on, but not “CAX” or “XX”.
Thompson says that you implement <code>A?</code> with a
transition to the next state on “A” and another ε-transition to that next state; because if you see an “A” you should transition,
but then you can transition anyhow even if you don’t.</p>
<p>The resulting NFA looks like this:</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/07/AcmBcmCcmX.png" alt="NFA matching A?B?C?X" />
<p> In finite-automaton
math, states are usually represented by the letter “q” followed by a number (usually italicized and subscripted, like
<i>q<sub>0</sub></i>, but not here, sorry). Note <code>q4</code>’s double circle which means it’s
a goal state, i.e. if we get here we’ve matched the regexp.
I should add that this was produced with
<a href="https://draw.io">draw.io</a>, which seems to make this sort of thing easy.
</p>
<h2 id='p-5'>Back to that NFA</h2>
<p>So, here’s a challenge: Sketch out the traversal code in your head. Think about the input strings “AX” and “BCX” and just “X”
and how you’d get through the NFA to the Q4 goal state.</p>
<p>The trick is what’s called the ε-closure. When you get to a state, before you look at the next input symbol, you have to set
up to process it. In this case, you need to be able to transition on an A or B or C. So what you do is pull together the
start state <code>q0</code> and also any other states you can reach from there through ε-transitions. In this case, the ε-closure
for the start state is <code>{q0, q1, q2, q3}</code>.</p>
<p>Suppose, then, that you see a “B” input symbol. You apply it to all the states in the ε-closure. Only <code>q1</code> matches,
transitioning you to
<code>q2</code>. Before you look at the next input symbol, you compute the ε-closure for <code>q2</code>, which turns
out to be <code>{q2, q3}</code>. With this ε-closure, you can match “C” or “X”. If you get a “C”, you”ll step to
<code>q3</code>, whose ε-closure is just itself, because “X” is the only path forward.</p>
<p>So your NFA-traversal algorithm for one step becomes something like:</p>
<ol>
<li><p>Start with a list of states.</p></li>
<li><p>Compute the ε-closure of that list.</p></li>
<li><p>Read an input symbol.</p></li>
<li><p>For each state in the ε-closure, see if you can traverse to another state.</p></li>
<li><p>If so, add it to your output list of states.</p></li>
<li><p>When you’re done, your output list of states is the input to this algorithm for the next step.</p></li>
</ol>
<h2 id='p-6'>Computation issues</h2>
<p>Suppose your regular expression is <code>(A+BC?)+</code>. I’m not going to sketch out the NFA, but just looking at it tells
you that it has to have loopbacks; once you’ve matched the parenthetized chunk you need to go back to a state where you can
recognize another occurrence.
For this regexp’s NFA, computing the ε-closures can lead you into an infinite loop. (Should be obvious, but I didn’t realize it until
after the first time it happened.)</p>
<p>You can have loops and you can also have dupes. In practice, it’s not that uncommon for a state to have more than one
ε-transition, and for the targets of these transitions to overlap.</p>
<p>So you need to watch for loops and to dedupe your output. I think the only way to avoid this is with a cookie-crumbs
“where I’ve been” trail, either as a list or a hash table.</p>
<p>Both of these are problematic because they require allocating memory, and that’s something you really don’t want to do when
you’re trying to match patterns to events at Quamina’s historic rate of millions per second.</p>
<p>I’ll dig into this problem in a future Quamina-Diary outing, but obviously, caching computed
epsilon closures would avoid re-doing this computation.</p>
<p>Anyhow, bear ε-closures in mind, because they’ll keep coming up as this series goes on.</p>
<h2 id='p-7'>And finally, simplifying “NFA”</h2>
<p>At the top of this piece, I offered the standard definition of NFAs: First, when you’re in a
state and an input symbol arrives, you can transfer to more than one other state. Second, you can have ε-transitions.
Based on my recent work, I think this definition is redundant. Because if you need to transfer to two different states on some
input symbol, you can do that with ε-transitions.</p>
<p>Here’s a mini-NFA that transfers from state <code>q0</code> on “A” to both <code>q1</code> and <code>q2</code>.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/07/Splice-1.png" alt="An NFA transferring to two different states on an input symbol" />
<p>And here’s how you can achieve the same effect with ε-transitions:</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/07/07/Splice-2.png" alt="Transferring to two destinations using ε-transitions" />
<p>In that NFA, in <code>qS</code> the “S” stands for “splice”, because it’s a state that exists to connect
two threads of finite-automaton traversal.</p>
<p>I’m pretty sure that this is more than just a mathematical equivalence. In my regexp implementation, so far at least,
I’ve never encountered a need to do that first kind of dual transition. Furthermore, the “splice” structure is how Thompson
implements the regular-expression “<code>|</code>” operator.</p>
<p>So if you’re building an NFA, all the traversal stuff you need in a state is a simple map from input symbol to next state,
and a list of ε-transitions.</p>
<h2 id='p-8'>Next up</h2>
<p>How my own implementation of NFA traversal collided head-on into the Benchmark From Hell and still hasn’t recovered.</p>
</div></content></entry>
<entry>
<title>The Real GenAI Issue</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/07/06/AI-Manifesto' />
<link rel='replies' thr:count='10' type='application/xhtml+xml' href='/ongoing/When/202x/2025/07/06/AI-Manifesto#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/07/06/AI-Manifesto</id>
<published>2025-07-06T12:00:00-07:00</published>
<updated>2025-07-06T12:06:43-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/AI' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology' />
<category scheme='https://www.tbray.org/ongoing/What/' term='AI' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>Last week I published a <a href='/ongoing/When/202x/2025/07/01/First-AI-Code'>featherweight narrative</a> about applying GenAI in a real-world context, to a tiny programming problem. Now I’m regretting that piece because I totally ignored the two central issues with AI: What it’s meant to do, and how much it really costs</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>Last week I published a
<a href="/ongoing/When/202x/2025/07/01/First-AI-Code">featherweight narrative</a> about applying GenAI in a real-world context, to
a tiny programming problem. Now I’m regretting that piece because I totally ignored the two central issues with
AI: What it’s meant to do, and how much it really costs.</p>
<h2 id='p-1'>What genAI is for</h2>
<p>The most important fact about genAI in the real world is that there’ve been literally
<a href="https://finance.yahoo.com/news/how-nvidia-played-a-central-role-in-the-306-billion-ai-startup-boom-195741749.html?guccounter=1">hundreds
of billions</a> of dollars invested in it; that link is just startups, and ignores a comparable torrent of cash pouring out of Big
Tech.</p>
<p>The business leaders pumping all this money of course don’t understand the technology. They’re doing this for exactly one
reason: They think they can discard armies of employees and replace them with LLM services, at the cost of
shipping shittier products. Do you think your management would spend that kind of money to help you with a quicker first draft or
a summarized inbox?</p>
<p>Adobe said the quiet part out loud:
<a href="https://petapixel.com/2024/05/03/adobe-throws-photographers-under-the-bus-again-skip-the-photoshoot/">Skip the
Photoshoot</a>. </p>
<p>At this point someone will point out that previous technology waves have generated as much employment as they’ve eliminated.
Maybe so, but that’s not what business leaders think they’re buying. They think they’re buying smaller payrolls.</p>
<p>Maybe I’m overly sensitive, but thinking about these truths leads to a mental stench that makes me want to stay away from
it.</p>
<h2 id='p-2'>How much does genAI cost?</h2>
<p>Well, I already mentioned all those hundreds of billions. But that’s pocket change. The investment community in general and
Venture Capital in particular will whine and moan, but the people who are losing the money are people who can afford to.</p>
<p>The first real cost is hypothetical: What if those business leaders are correct and they can gleefully dispose of millions of
employees? If you think we’re already suffering from egregious levels of inequality, what happens when a big chunk of the
middle class suddenly becomes professionally superfluous? I’m no economist so I’ll stop there, but you don’t have to be a
rocket scientist to predict severe economic pain.</p>
<p>Then there’s the other thing that nobody talks about, the massive greenhouse-gas load that all those data centers are going
to be pumping out. This at a time when we we blow past one atmospheric-carbon metric after another and David Suzuki says
<a href="https://www.ipolitics.ca/2025/07/02/its-too-late-david-suzuki-says-the-fight-against-climate-change-is-lost/">the
fight against climate change is lost</a>, that we need to hunker down and work on survival at the local level.</p>
<h2 id='p-3'>The real problem</h2>
<p>It’s the people who are pushing it. Their business goals are quite likely, as a side-effect, to make
the world a worse place, and they don’t give a fuck. Their technology will inevitably worsen the onrushing climate catastrophe,
and they don’t give a fuck.</p>
<p>It’s probably not as simple as “They’re just shitty people”<span class='dashes'> —</span> it’s not exactly easy to escape the
exigencies of modern capitalism. But they are people who are doing shitty things.</p>
<h2 id='p-4'>Is genAI useful?</h2>
<p>Sorry, I’m having trouble even thinking about that now.</p>
</div></content></entry>
<entry>
<title>My First GenAI Code</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/07/01/First-AI-Code' />
<link rel='replies' thr:count='3' type='application/xhtml+xml' href='/ongoing/When/202x/2025/07/01/First-AI-Code#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/07/01/First-AI-Code</id>
<published>2025-07-01T12:00:00-07:00</published>
<updated>2025-07-01T11:38:00-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/AI' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology' />
<category scheme='https://www.tbray.org/ongoing/What/' term='AI' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/Software' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Software' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>At the moment, we have no idea what the impact of genAI on software development is going to be. The impact of <em>anything</em> on coding is hard to measure systematically, so we rely on anecdata and the community’s eventual consensus. So, here’s my anecdata. Tl;dr: The AI was not useless</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>At the moment, we have no idea what the impact of genAI on software development is going to be. The impact of
<em>anything</em> on coding
is hard to measure systematically, so we rely on anecdata and the community’s eventual consensus.
So, here’s my anecdata. Tl;dr: The AI was not useless.</p>
<h2 id='p-1'>The problem</h2>
<p>My current work on
<a href="/ongoing/What/Technology/Quamina%20Diary/">Quamina</a> involves dealing with collections of finite-automata states,
which, in the Go programming language, are represented as slices of pointers to state instances:</p>
<blockquote><p><code>[]*faState</code></p></blockquote>
<p>The problem I was facing was deduping them, so that there would be only one instance corresponding to any particular
collection. This is what, in Java, the <code>intern()</code> call does with strings.</p>
<p>The algorithm isn’t rocket science:</p>
<ol>
<li><p>Dedupe the states, i.e. turn the collection into a set.</p></li>
<li><p>For each set of states, generate a key.</p></li>
<li><p>Keep a hash table of sets around, and use the key to see whether you’ve already got such a set, and if so return
it. Otherwise, make a new entry in the hash table and return that.</p></li>
</ol>
<p>I’m out of touch with the undergrad CS curriculum, but this feels like a second-year assignment or thereabouts? Third?</p>
<h2 id='p-2'>Enter Claude</h2>
<p>So I prompted Claude thus:</p>
<blockquote><p>I need Go code to provide a "intern"-like function for lists of pointers. For example, if I have several
different []*int arrays, which may contain duplicates, I want to call intern() on each of them and get back a single canonical
pointer which is de-duplicated and thus a set.</p></blockquote>
<p>Claude did pretty well. It got the algorithm right, the code was idiomatic and usefully commented, and it also provided a
decent unit test (but in a <code>main()</code> stanza rather than a proper Go test file).
I didn’t try actually running it.</p>
<p>The interesting part was the key computation. I, being lazy, had just done a Go <code>fmt.Sprintf("%p")</code>
incantation to get a hex string representing each state’s address, sorted them, joined them, and that was the key.</p>
<p>Claude worked with the pointers more directly.</p>
<pre><code> // Sort by pointer address for consistent ordering
sort.Slice(unique, func(i, j int) bool {
return uintptr(unsafe.Pointer(unique[i])) < uintptr(unsafe.Pointer(unique[j]))
})</code></pre>
<p>Then it concatenated the raw bytes of the map addresses and lied to Go by claiming it was a string.</p>
<pre><code> // Create key from pointer addresses
key := make([]byte, 0, len(slice)*8)
for _, ptr := range slice {
addr := uintptr(unsafe.Pointer(ptr))
// Convert address to bytes
for i := 0; i < 8; i++ {
key = append(key, byte(addr>>(i*8)))
}
}
return string(key)</code></pre>
<p>This is an improvement in that the keys will be half the size of my string version.
I didn’t copy-paste Claude’s code wholesale, just replaced ten or so lines of key construction.</p>
<h2 id='p-3'>Take-away</h2>
<p>I dunno. I thought the quality of the code was fine, wouldn’t have decomposed the functions in the same way but wouldn’t have
objected on review. I was pleased with the algorithm, but then I would be since it was the same one I’d written, and, having
said that, quite possibly that’s the only algorithm that anyone has used. It will be <em>super</em> interesting if someone
responds to this write-up saying “You and Claude are fools, here’s a much better way.”</p>
<p>Was it worth fifteen minutes of my time to ask Claude and get a slightly better key computation?
Only if this ever turns out
to be a hot code path and I don’t think anybody’s smart enough to know that in advance.</p>
<p>Would I have saved time by asking Claude first? Tough to tell; Quamina’s data structures are a bit non-obvious and I would
have had to go to a lot of prompting work to get it to emit code I could use directly.
Also, since Quamina is low-level performance-critical infrastructure code, I’d be nervous about having any volume of code
that I didn’t really <em>really</em> understand.</p>
<p>I guess my take-away was that in this case, Claude knew the Go idioms and APIs better than I did; I’d never looked at the
<a href="https://pkg.go.dev/unsafe">unsafe</a> package.</p>
<p>Which reinforces my
suspicion that genAI is going to be especially useful at helping generate code to talk to big complicated
APIs that are hard to remember all of. Here’s an example: Any moderately competent Android developer could add a feature to an
app where it strobes the flash and surges the vibration in sync with how fast you’re shaking the device back and forth,
probably in an afternoon. But it would require a couple of dozen calls into the dense forest of Android APIs, and I suspect a
genAI might get you there a lot faster by just filling the calls in as prompted.</p>
<p>Reminder: This is just anecdata.</p>
</div></content></entry>
<entry>
<title>Qobuz and Mac</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/06/22/Qobuz-and-Others' />
<link rel='replies' thr:count='0' type='application/xhtml+xml' href='/ongoing/When/202x/2025/06/22/Qobuz-and-Others#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/06/22/Qobuz-and-Others</id>
<published>2025-06-22T12:00:00-07:00</published>
<updated>2025-06-26T13:13:08-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='Arts/Music' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Arts' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Music' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>Back in March I offered <a href='/ongoing/When/202x/2025/03/27/Music-Plus-Qobuz'>Latest Music (feat. Qobuz)</a>, describing all the ways I listen to music (Tl;dr: YouTube Music, Plex, Qobuz, record player). I stand by my opinions there but wanted to write more on two subjects: First Qobuz, because it suddenly got a lot better. And a recommendation, for people with fancy A/V setups, that you include a cheap Mac Mini</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>Back in March I offered
<a href="/ongoing/When/202x/2025/03/27/Music-Plus-Qobuz">Latest Music (feat. Qobuz)</a>, describing all the ways I listen to
music (Tl;dr: YouTube Music, Plex, Qobuz, record player). I stand by my opinions there but wanted to write more on two subjects:
First Qobuz, because it suddenly got a lot better. And a recommendation, for people with fancy A/V setups, that you include a cheap
Mac Mini.</p>
<h2 id='p-1'>Qobuz</h2>
<p>That other piece had a list of the reasons to use Qobuz, but times have changed, so let’s revise it:</p>
<ol>
<li><p>It pays artists more per stream than any other service, by a wide margin.</p></li>
<li><p>It seems to have as much music as anyone else.</p></li>
<li><p>It’s album-oriented, and I appreciate artists curating their own music.</p></li>
<li><p>Classical music is a first-class citizen.</p></li>
<li><p>It’s actively curated; they highlight new
music regularly, and pick a “record of the week”. To get a feel, check out
<a href="https://www.qobuz.com/ca-en/magazine">Qobuz Magazine</a>; you don’t have to be a subscriber.</p></li>
<li><p>It gives evidence of being built by people who love music.</p></li>
<li><p>They’re obsessive about sound quality, which is great, but only makes a difference if you’re listening through quality
speakers.</p></li>
<li><p>A few weeks ago, the mobile app quality switched from adequate to
excellent.</p></li>
</ol>
<h2 id='p-2'>That app</h2>
<p>I want to side-trip a bit here, starting with a question. How long has it been since an app you use has added a feature that
was genuinely excellent and let you do stuff you couldn’t before and didn’t get in your way and created no suspicion that it was
strip-mining your life for profit? I’m here to tell you that this can still happen, and it’s a crushing criticism
of my profession that it so rarely does.</p>
<p>I’m talking about
<a href="https://www.qobuz.com/ca-en/connect">Qobuz Connect</a>. I believe there are other music apps that can do this sort of
stuff, but it feels like magic to me.</p>
<p>It’s like this. I listen to music at home on an audiophile system with big speakers, in
<a href="/ongoing/What/The%20World/Jaguar%20Diary/">our car</a>, and on
<a href="/ongoing/When/201x/2019/08/06/Jeanneau-795">our boat</a>. The only app I touch is the
<a href="https://play.google.com/store/apps/details?id=com.qobuz.music">Qobuz Android app</a>. The only time it’s actually
receiving and playing the music itself is in the car, with the help of Android Auto. In the other scenarios it’s talking to
Qobuz running on a Mac, which actually fetches the music and routes it to the audio system.
Usually it figures out what player I want it to control automatically, although there’ve been a couple
times when I drove away in the car and it got confused about where to send the music. Generally, it works great.</p>
<p>The app’s music experience is rich and involving.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/06/22/Screenshot_20250622-230116.png" alt="Qobuz Android app screenshot" />
<p>It has New Releases and curated playlists and a personalized stream for
me and a competent search function for those times I absolutely must listen to Deep Purple or Hania Rani or
whoever.</p>
<p>I get a chatty not-too-long email from Qobuz every Friday, plugging a few of the week’s new releases, with sideways and
backward looks too. (This week: A Brian Wilson stream.) The app has so much stuff, especially among the themed streams, that I
sometimes get lost. But somehow it’s not irritating; what’s on the screen remains musically interesting and you can always hit
the app’s Home button.</p>
<p>Qobuz has its own musical tastes that guide its curation. They’re not always compatible with
mine<span class='dashes'> —</span> my tolerance for EDM and mainstream Hip-hop remains low. And I wish they were
stronger on Americana. But the intersection is broad enough to provide plenty of enjoyable new-artist experiences. Let me share
one with you:
<a href="https://kwashibu.bandcamp.com/album/love-warrior-s-anthem">Kwashibu Area Band</a>, from Ghana.</p>
<p>Oh, one complaint: Qobuz was eating my Pixel’s battery. So I poked around online and it’s a known problem; you have to use the
Android preferences to stop it from running in the background. Huh? What was it doing in the background anyhow?! But it seems to
work fine even when it’s not doing it.</p>
<h2 id='p-3'>A Mac, you say?</h2>
<p>The music you’re listening to is going to be stored on disk, or incoming from a streaming service. Maybe you want to serve
some of the stored music out to listen to it in the car or wherever. There are a variety of audio products in the
“Streamer” category that do some of these things in various combinations. A lot of them make fanciful claims about the
technology inside and are thus expensive, you can easily spend thousands.</p>
<p>But any reasonably modern computer can do all these things and more, plus it also can drive a big-screen display, plus it will
probably run the software behind whatever next year’s New Audio Hotness is.</p>
<p>At this point the harder-core geeks will adopt a superior tone of voice to say “I do all that stuff with FreeBSD and a bunch of
open-source packages running on a potato!”</p>
<p>More power to ’em. But I recommend a basic Apple Silicon based Mac Mini, M1 is fine, which you can get for like $300 used on
eBay. And if you own a lot of music and video you can plug in a 5T USB drive for a few more peanuts. This will run Plex and
Qobuz and almost any other imaginable streaming software. Plus you can plug it into your home-theater screen and it has a modern
Web browser so you can also play anything from anywhere on the Web.</p>
<p>I’ve been doing this for a while but I had one big gripe. When I wanted to stream music from the Mac, I needed to use a
keyboard and mouse, so I keep one of each, Bluetooth-flavored, nearby. But since I got Qobuz running that’s become a very rare
occurrence.</p>
<h2 id='p-4'>You’re forgetting something</h2>
<p>Oh, and yeah, there’s the record player. Playing it requires essentially no software at all, isn’t that great?</p>
</div></content></entry>
<entry>
<title>Long Links</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/06/21/Long-Links' />
<link rel='replies' thr:count='6' type='application/xhtml+xml' href='/ongoing/When/202x/2025/06/21/Long-Links#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/06/21/Long-Links</id>
<published>2025-06-21T12:00:00-07:00</published>
<updated>2025-06-21T11:56:27-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='The World' />
<category scheme='https://www.tbray.org/ongoing/What/' term='The World' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>“Wow, Tim, didn’t you do a <a href='/ongoing/When/202x/2025/05/06/Long-Links'>Long Links</a> just last month? Been spending too much time doomscrolling, have we?” Maybe. There sure are a lot of tabs jostling each other along the top of that browser. Many are hosting works that are both long and good. So here they are; you probably don’t have time for all of ’em but my hope is that one or two might reward your visit</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>“Wow, Tim, didn’t you do a
<a href="/ongoing/When/202x/2025/05/06/Long-Links">Long Links</a> just last month? Been spending too much time doomscrolling,
have we?” Maybe. There sure are a lot of tabs jostling each other along the top of that browser. Many
are hosting works that are both long and good. So here they are; you probably don’t have time for all of ’em but my hope
is that one or two might reward your visit.</p>
<p>Let’s start with a really important subject: Population growth oh actually these days it’s population shrinkage.
For a short-sharp-shock-flavored introduction I recommend
<a href="https://www.youtube.com/watch?v=Ufmu1WD2TSk">South Korea Is Over</a>
which explains the brick wall societies with fertility rates way below the replacement rate of 2.1 children per woman per
lifetime are hurtling toward. South Korea, of course, being the canonical example. But also Japan and Taiwan and Italy and Spain
and so on.</p>
<p>And, of course, the USA, where the numbers aren’t <em>that</em> much higher:
<a href="https://www.macrotrends.net/global-metrics/countries/usa/united-states/fertility-rate">U.S. Fertility Rate
(1950-2025)</a>. Even so, the population still grows (because of immigration), albeit at less than 1% per annum:
<a href="https://www.macrotrends.net/global-metrics/countries/usa/united-states/population-growth-rate">U.S. Population Growth
Rate</a>. If the MAGAs get their way and eventually stop all non-white immigration, the US will be in South Korea
territory within a generation or two. </p>
<p>A reasonable person might ask why. It’s not really complicated, as you can read here:
<a href="https://www.nytimes.com/2025/06/15/opinion/birth-rate-parenting-natalism.html?unlocked_article_code=1.Pk8.OBam.dOi0UpP-8-DV&smid=url-share">A Bold Idea to Raise the Birthrate: Make Parenting Less Torturous</a>.
From which I quote: “To date, no government policies have significantly improved their nation’s birthrates for a sustained
period.” The essay argues convincingly that it’s down to two problems: Capitalism and sexism. Neither of which offers an easy
fix. </p>
<p>Speaking of the travails of late capitalism, here’s how bad it’s getting:
<a href="https://www.nytimes.com/2025/03/01/opinion/crisis-working-homeless.html?unlocked_article_code=1.Qk8.jsTO.aUBSAMHw7Op2&smid=url-share">America
Is Pushing Its Workers Into Homelessness</a>.</p>
<p>For a refreshingly different take on the business world, here’s Avery Pennarun, CEO of Tailscale:
<a href="https://apenwarr.ca/log/20250530">The evasive evitability of enshittification</a>. Not sure I buy what he’s saying, but
still worth reading.</p>
<p>Most people who visit these pages are geeks or geek-adjacent. If you’re one of those, and especially if you enjoy the small
but vibrant genre of Comical Tech War Stories, I recommend
<a href="https://yeet.cx/blog/lock-free-rust/">Lock-Free Rust: How to Build a Rollercoaster
While It’s on Fire</a></p>
<p>And here’s write-up on an AWS product which has one of the best explanations I’ve ever read of the different flavors modern
databases come in: <a href="https://www.redshift-observatory.ch/white_papers/downloads/introduction_to_the_fundamentals_of_amazon_redshift.html">Introduction to the Fundamentals of Amazon Redshift</a></p>
<p>Of course, the geek conversation these days is much taken up with the the impact of genAI as in “vibe coding”. To
summarize the conversation: A few people, not obviously fools, are saying “This stuff seems to help me” and many others, also
apparently sensible, are shouting back “You’re lying to yourself, it can’t be helping!” Here is some of the testimony:
Kellan on <a href="https://laughingmeme.org//2025/05/25/vibe-coding-for-teams.html">Vibe
coding for teams, thoughts to date</a>, Armin Ronacher on
<a href="https://lucumr.pocoo.org/2025/6/12/agentic-coding/">Agentic Coding Recommendations</a>,
Harper on <a href="https://harper.blog/2025/05/08/basic-claude-code/">Basic Claude Code</a>, and
Klabnik on
<a href="https://steveklabnik.com/writing/a-tale-of-two-claudes/">A tale of two Claudes</a></p>
<p>I lean to believing narratives of personal experience, but on the other hand the skeptics make good points. Another
random piece of evidence: Because I’m lazy, I tend to resist adopting technologies that have steep learning curves, which genAI
currently does. On many occasions, this has worked out well because those technologies have turned out not to pay off very
well. Am I a canary in the coal mine?</p>
<h2 id='p-2'>*cough*</h2>
<p>Since I introduced myself into the narrative, I’ll note that today is my 70th birthday. I am told that this means
that my wisdom has now been maximized, so you’re safe in believing whatever you read in this space. I don’t have anything
special to say to commemorate the occasion,
so here’s a picture of my neighborhood’s network infrastructure, which outlines the form of a
cathedral’s nave. I’m sure there’s a powerful metaphor lurking in there.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/06/21/TXT55659.png" alt="Many electrical and data wires festoon a back alley" />
<p>Oh, and here’s a photography Long Link: <a href="https://www.lux.camera/what-is-hdr/">What is HDR, anyway?</a>
It’s actually a pitch for a nice-looking mobile camera app, but it offers real value on things that can
affect the quality of your pictures.</p>
<p>Regular readers will know that I’m fascinated by the many unsolved issues and open questions in cosmology, which are by
definition the largest problems facing human consciousness. The ΛCDM-vs-MOND controversy, i.e. “Is there really dark
matter or does gravity get weird starting at the outer edges of galaxies?”, offers great entertainment value. And, there is
news!</p>
<p>First of all, here’s a nice overview on the controversy:
<a href="https://arxiv.org/pdf/2505.21638v1">Modified Newtonian Dynamics: Observational Successes and Failures</a>.</p>
<p>Which points out that the behavior of “wide binary” star systems ought to help resolve the issue, but that people who
study it keep coming up with contradictory findings. Here’s the latest, from Korean researchers: Press release
<a href="http://www.sejongpr.ac.kr/sejongnewspaperview.do?currentPage=1&searchField=&searchValue=&boardType=3&pkid=73549&utm_source=beehiiv&utm_medium=newsletter&utm_campaign=mediamobilize&_bhlid=3e40dce99e536f4015a1dd2c6afd193a465d17ea">New method of measuring gravity with 3D velocities of wide binary stars is developed and confirms modified gravity</a>
and peer-reviewed paper:
<a href="https://iopscience.iop.org/article/10.3847/1538-4357/adce09">Low-acceleration Gravitational Anomaly
from Bayesian 3D Modeling of Wide Binary Orbits: Methodology and Results with Gaia Data Release 3</a>.
Spoiler: They think the gravity gets weird. I have a math degree but cosmology math is generally way over my head. Having said
that, I think those South Koreans may be a bit out over their skis; I generally distrust heroic statistical methods. We’ll
see.</p>
<p>Let’s do politics. It turns out that the barbaric junta which oppresses the people of China does not limit its barbarism
to its own geography:
<a href="https://www.cbc.ca/news/politics/china-targets-dissidents-canada-1.7543745?cmp=rss">Followed, threatened and smeared
— attacks by China against its critics in Canada are on the rise</a>.</p>
<p>More politics: The MAGAs are always railing against “elites”. Here are two discussions of what they mean:
<a href="https://www.theatlantic.com/ideas/archive/2025/04/class-money-finances/682301/">What the Comfort Class Doesn’t
Get</a> and <a href="https://siderea.dreamwidth.org/1865048.html">When They Say Elites, They Mean Us</a>.</p>
<p>The world’s biggest political issue <em>should</em> be the onrushing climate crisis. When Trump and his toadies
are justly condemned and ridiculed by future historians, it is their malevolent cluelessness on this subject that
may burn the hottest. Who knows, maybe they’ll pay attention to this:
<a href="https://www.bloomberg.com/news/newsletters/2025-06-18/insurers-want-businesses-to-wake-up-to-costs-of-extreme-heat">Insurers Want Businesses to Wake Up to Costs of Extreme Heat</a>.</p>
<h2 id='p-1'>The list of Long Links is too long</h2>
<p>So I’ll try to end cheerfully.</p>
<p>A graceful essay about an old camera and a dreamy picture:
<a href="https://petapixel.com/2025/05/27/a-bridge-across-time-for-sebastiao-salgado/">A Bridge Across Time: For
Sebastião Salgado</a></p>
<p>Latin Wikipedia has 140,000 articles; consider the delightful discussion of
<a href="https://la.wikipedia.org/wiki/Equus_asinus"><cite>Equus asinus</cite></a>.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/06/21/equus-asinus.png" alt="Asinus in opere tesselato Byzantino" />
<div class='caption'><p>Asinus in opere tesselato Byzantino</p></div>
<p>Here’s a lovely little song from TORRES and Julien Baker:
<a href="https://www.youtube.com/watch?v=TurU_Jn-LEg">The Only Marble I’ve Got Left</a>.</p>
<p>Finally, a clear-eyed if lengthy essay on why and how to think:
<a href="https://www.newyorker.com/culture/open-questions/should-you-question-everything">Should You Question
Everything?</a></p>
</div></content></entry>
<entry>
<title>June 2025 C2PA News</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/06/17/More-C2PA' />
<link rel='replies' thr:count='1' type='application/xhtml+xml' href='/ongoing/When/202x/2025/06/17/More-C2PA#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/06/17/More-C2PA</id>
<published>2025-06-17T12:00:00-07:00</published>
<updated>2025-06-19T09:20:16-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/Identity' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Identity' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>Things are happening in the C2PA world; here are a couple of useful steps forward, plus cheers and boos for Adobe. Plus a live working C2PA demo you can try out</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>Things are happening in the C2PA world; here are a couple of useful steps forward, plus cheers and boos for Adobe.
Plus a live working C2PA demo you can try out.</p>
<p>Refresher: The
<a href="https://c2pa.org/">C2PA</a> technology is driven by the
<a href="https://contentauthenticity.org/">Content Authenticity Initiative</a> and usually marketed as “Content Credentials”.
I’ve written before about it, an
<a href="/ongoing/When/202x/2023/10/28/C2PA-Workflows">introduction in 2023</a> and a
<a href="/ongoing/When/202x/2024/10/29/Lane-Provenance">progress report</a> last October.</p>
<p>Let’s start with a picture.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/06/17/TXT55648.png" alt="A dark picture full of vague swirls and jiggly lights" />
<div class='caption'><p>I was standing with the camera by the ocean at dusk and accidentally left it in the “B” long-exposure
setting, so this isn’t really a picture <em>of</em> anything but I thought it was kinda pretty.</p></div>
<h2 id='p-1'>Validating Content Credentials</h2>
<p>As I write this, there are now at least two C2PA-validator Chrome extensions: the
<a href="https://chromewebstore.google.com/detail/contentlens-c2pa-validato/gdejpnjeepoffhkbcgnjdbkgpohdhmln?hl=en">ContentLens
C2PA Validator</a> from
<a href="https://www.contentlens.ai/">ContentLens</a> and
<a href="https://chromewebstore.google.com/detail/c2pa-content-credentials/mjkaocdlpjmphfkjndocehcdhbigaafp?hl=en">C2PA Content
Credentials</a> from
<a href="https://www.digimarc.com/">Digimarc</a>.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/06/17/cc-readout.png" alt="C2PA verifier display" class="inline" />
<img src="https://www.tbray.org/ongoing/When/202x/2025/06/17/cc2-readout.png" alt="C2PA verifier display" class="inline" />
<p>If you install either of them, and then you click on that picture just above in Chrome to get the larger version, then you
right-click on the larger picture, the menu will offer Content-Credentials validation.</p>
<p>Doing this will produce a little
“CR” logo at the top right corner, meaning that the C2PA data has been
verified as being present and signed by a trusted certificate issuer, in this case Adobe.</p>
<p>Then there’s a popup; the two extensions’ are on the right. They’re different, in interesting ways. Let’s walk through the
second one.</p>
<p>The little thumbnail at the top of the popup is what the image looked like when the C2PA was added. Not provided by the other
verifier.</p>
<p>The paragraph beginning “Displaying credentials…” says that the C2PA manifest was embedded in the JPG as opposed to stored
out on the
cloud; The cloud works fine, and is perhaps a good idea because the C2PA manifest can be quite large. I’m not clear on what the
“watermark” is about.</p>
<p>“Issued by Adobe” means that the Chrome extension verified the embedded C2PA against Adobe’s public key and can be
confident that yes, this was really signed by them.</p>
<p>“<b>Produced by</b> Timothy Bray” is interesting. How can it know? Well, it turns out that it used LinkedIn’s API to verify
that I am
<a href="https://www.linkedin.com/in/timbraysoftwareguy/">timbraysoftwareguy</a> over on LinkedIn. But it goes further; LinkedIn
has an integration with
<a href="https://www.clearme.com">Clear</a>, the airport-oriented identity provider. To get a Clear account you have to upload
government-issued ID, it’s not trivial.</p>
<p>So this short sentence expands to (take a deep breath) “The validator extension verified that Adobe said that
LinkedIn said that Clear said that the government ID of the person who posted this says that he’s named Timothy Bray.”</p>
<p>Note that the first extension’s popup also tells you that Adobe has verified what my LinkedIn and Instagram accounts
are. This seems super-useful and I wonder why the other omits it.</p>
<p>“<b>App or device used</b>…” is simple enough, but I’m not actually sure how it works; I guess Adobe has embedded a keypair
in my Lightroom installation? If I’d taken the picture with a C2PA-equipped camera this is where that history would be
displayed.</p>
<p>“<b>AI tool used</b> None”. Interesting and useful, since Adobe provides plenty of genAI-powered tools. Of course, this
relies on Lightroom telling the truth, but still.</p>
<p>The “View More” button doesn’t currently work; it takes you to the interactive
<a href="https://contentcredentials.org/verify/">contentcredentials.org/verify</a> page,
which seems to fail in retrieving the JPG. If you download the picture then upload it into the verify page (go ahead, it’s
free)
that seems to work fine. In addition to the info on the popup, the verify page will tell you (nontechically i.e. vaguely) what I
did to the picture with Lightroom.</p>
<h2 id='p-3'>What’s good about this?</h2>
<p>Well, it’s here and it works! There’s all this hype about how cool it will be when the C2PA includes info about what model
of camera and lens it used and what the shutter speed was and so on, but eh, who cares really? What matters to me (and
should matter to the world) is <em>provenance</em>: Who posted this thing?</p>
<p>As I write this, supporters of Israel and Iran are
<a href="https://www.404media.co/the-ai-slop-fight-between-iran-and-israel/?ref=daily-stories-newsletter">having an AI Slop
Fight</a> with fake war photos and videos.
In a C2PA-rich world, you could check; If some clip doesn’t have Content Credentials you should
probably be suspicious, and if it does, it matters whether it was uploaded by someone at
<a href="https://www.idf.il/en/">IDF.il</a> versus
<a href="https://www.bbc.com">BBC.co.uk</a>.</p>
<h2 id='p-2'>What’s wrong with this?</h2>
<p>Look, I hate to nitpick. I’m overwhelmingly positive on this news, it’s an existence proof that C2PA can be made to work in
the wild.
My impression is that most of the money and muscle comes from Adobe; good on ’em.
But there are things that would make it more useful, and usable by more Web sites. These are not listed in
any particular order.</p>
<h2 id='p-7'>Identity!</h2>
<p>Adobe, it’s nice that you let me establish my identity with LinkedIn, Instagram, and Clear. But what I’d
<em>really</em> like is if you could also verify and sign my Fediverse and Bluesky handles. And, Fediverse and ATProto
developers, would you please, first of all, stop stripping C2PA manifests from uploaded photo EXIF, and secondly, add your own
link to the C2PA chain saying something like “Originally posted by @timbray@cosocial.ca.”</p>
<p>Because having verifiable media provenance in the world of social media would be a strong tool against disinformation
and slop.</p>
<p>Oh, and another note to Adobe: When I export a photo, the embed-manifest also offers me the opportunity, under the heading
“Web3”, to allow the image “be used for NFT creative attribution on supported marketplaces” where the supported marketplaces are
Phantom and MetaMask. Seriously, folks, in 2025? Please get this scammy cryptoslime out of my face.</p>
<h2 id='p-4'>Browsers please…</h2>
<p>This was done with Chrome extensions. There are people working on extensions for Firefox and
Safari, but they’re not here yet. Annoyingly, the extensions also don’t seem to work in mobile Chrome, which is where most
people look at most media.</p>
<p>I would love it if this were done directly and automatically by the browser.
The major browsers aren’t perfect, but their creators are known to take security seriously, and I’d be much happier trusting
one of them, rather than an extension from a company I’d never previously heard of.</p>
<h2 id='p-8'>… or maybe JavaScript?</h2>
<p>The next-best solution would be a nice JS package that just Does The Right
Thing. It should work like the way I do fonts: If you look in the source for the page you are now reading, the splodge of JS at
the top includes a couple of lines
that mention “typekit.com”. Typekit (since acquired by Adobe) offers access to a huge selection of excellent fonts.
Those JS invocations result in the text you are now reading being displayed in
<a href="/ongoing/When/201x/2011/07/17/Tisa">FF Tisa Web Pro</a>.</p>
<p>Which<span class='dashes'> —</span> this is important<span class='dashes'> —</span> is not free. And to be clear, I am
willing to pay to get Content Credentials for the pictures on this blog. It feels exactly like paying a small fee for access to
a professionally-managed font library.
Operating a Content-Credentials service wouldn’t be free, it’d require running a
server and wrangling certs. At scale, though, it should be pretty cheap.</p>
<p>So here’s an offer: If someone launches a service that allows me to straightforwardly include the
fact that this picture was sourced from tbray.org in my Content Credentials, my wallet is (modestly) open.</p>
<p>By the way, the core JavaScript code is already under construction; here’s
<a href="https://github.com/microsoft/c2pa-extension-validator">Microsoft</a> and the
<a href="https://opensource.contentauthenticity.org/docs/introduction">Content Authority Initiative</a> itself.
There’s also a Rust crate for server-side use, and a “c2patool” command-line utility based on it..</p>
<h2 id='p-6'>Open-Source issues</h2>
<p>You’ll notice that the right-click-for-Content-Credentials doesn’t work on the smaller version of the picture embedded in the
text you are now reading; just the larger one. This is because the decades-old Perl-based <span class='o'>ongoing</span>
publishing software runs the main-page pictures through
<a href="https://imagemagick.org/index.php">ImageMagick</a>, which doesn’t do C2PA. I should find a way to route around this.</p>
<p>In fact, it wouldn’t be rocket science for ImageMagick (or open-source packages generally) to write C2PA manifests and insert
them in the media files they create. But how should they sign them? As noted, that requires a server that provides cert-based
signatures, something that nobody would expect from even well-maintained open-source packages.</p>
<p>I dunno, maybe someone should provide a managed-ImageMagick service that (for a small fee) offers signed-C2PA-manifest
embedding?</p>
<h2 id='p-9'>What’s next?</h2>
<p>The work that needs to be done is nontrivial but, frankly, not that taxing. And the rewards would be high.
Because it feels like a no-brainer that knowing who posted something is a big deal. Also the inverse: Knowing that you
<em>don’t</em> know who posted it.</p>
<p>Where is it an especially big deal? On social media, obviously. It’s really time for those guys to start climbing on board.</p>
</div></content></entry>
<entry>
<title>AI Angst</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/06/06/My-AI-Angst' />
<link rel='replies' thr:count='13' type='application/xhtml+xml' href='/ongoing/When/202x/2025/06/06/My-AI-Angst#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/06/06/My-AI-Angst</id>
<published>2025-06-06T12:00:00-07:00</published>
<updated>2025-06-08T15:39:49-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/AI' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology' />
<category scheme='https://www.tbray.org/ongoing/What/' term='AI' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>My input stream is full of it: Fear and loathing and cheerleading and prognosticating on what generative AI means and whether it’s Good or Bad and what we should be doing. All the channels: Blogs and peer-reviewed papers and social-media posts and business-news stories. So there’s lots of AI angst out there, but this is mine. I think the following is a bit unique because it focuses on cost, working backward from there. As for the genAI tech itself, I guess I’m a moderate; there is a there there, it’s not all slop. But first…</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>My input stream is full of it: Fear and loathing and cheerleading and prognosticating on what generative AI means and whether
it’s Good or Bad and what we should be doing. All the channels: Blogs and peer-reviewed papers and social-media posts and
business-news stories. So there’s lots of AI angst out there, but this is mine.
I think the following is a bit unique because it focuses on cost, working backward from there. As for the
genAI tech itself, I guess I’m a moderate; there is a there there, it’s not all slop. But first…</p>
<h2 id='p-5'>The rent is too damn high</h2>
<p>I promise I’ll talk about genAI applications but let’s start with money. <em>Lots</em> of money, big numbers! For example,
venture-cap startup money pouring into AI, which as of now apparently adds up to
<a href="https://finance.yahoo.com/news/how-nvidia-played-a-central-role-in-the-306-billion-ai-startup-boom-195741749.html">$306
billion</a>. And that’s just startups; Among the giants, Google alone
<a href="https://www.ciodive.com/news/google-cloud-generative-ai-data-center-capacity-buildouts/739357/">apparently plans
$75B</a> in capital expenditure on AI
infrastructure, and they represent maybe a quarter at most of cloud capex. You think those are big numbers? McKinsey offers
<a href="https://www.mckinsey.com/industries/technology-media-and-telecommunications/our-insights/the-cost-of-compute-a-7-trillion-dollar-race-to-scale-data-centers">The cost of compute: A $7 trillion race to scale data centers</a>.</p>
<p>Obviously, lots of people are
wondering when and where the revenue will be to pay for it all. There’s one thing we know for sure:
The pro-genAI voices are fueled by hundreds of billions of dollars worth of fear and desire; fear that it’ll
never pay off and desire for a piece of the money. Can you begin to imagine the pressure for revenue that investors and
executives and middle managers are under?</p>
<p><a href="https://cosocial.ca/@timbray/114572118905328515">Here’s an example</a> of the kind of debate that ensues.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/06/06/Anil-MCP.png" alt="Anil Dash on Mastodon, on MCP vs the Fediverse" />
<div class='caption'><p>“MCP” is
<a href="https://en.wikipedia.org/wiki/Model_Context_Protocol">Model Context Protocol</a>, used for communicating between LLM
software and other systems and services.<br/>I have no opinion as to its quality or utility.</p></div>
<p>I suggest that when you’re getting a pitch for genAI technology, you should have that greed and
fear in the back of your mind. Or maybe at the front.</p>
<h2 id='p-7'>And that’s just the money</h2>
<p>For some reason, I don’t hear much any more about the environmental cost of genAI, the gigatons of carbon pouring out of the
system, imperilling my children’s future. Let’s please not ignore that; let’s read things like
<a href="https://www.eesi.org/articles/view/data-center-energy-needs-are-upending-power-grids-and-threatening-the-climate">Data
Center Energy Needs Could Upend Power Grids and Threaten the Climate</a> and let’s make sure every freaking conversation about
genAI acknowledges this grievous cost.</p>
<p>Now let’s look at a few sectors where genAI is said to be a big deal: Coding, teaching, and professional
communication. To keep things balanced, I’ll start in a space where I have kind things to say.</p>
<h2 id='p-2'>Coding</h2>
<p>Wow, is my tribe ever melting down. The pro- and anti-genAI factions are hurling polemical thunderbolts at each
other, and I mean extra hot and pointy ones. For example, here are 5600 words entitled
<a href="https://blog.glyph.im/2025/06/i-think-im-done-thinking-about-genai-for-now.html">I Think I’m Done Thinking About genAI
For Now</a>. Well-written words, too.</p>
<p>But, while I have a lot of sympathy for the contras and am sickened by some of the promoters, at the moment
I’m mostly in tune with Thomas Ptacek’s
<a href="https://fly.io/blog/youre-all-nuts/">My AI Skeptic Friends Are All Nuts</a>. It’s long and (fortunately) well-written
and I (mostly) find it hard to disagree with.</p>
<p>it’s as simple as this: I keep hearing talented programmers
whose integrity I trust tell me “Yeah, LLMs are helping me get shit done.” The probability that they’re all lying or being
fooled seems very low.</p>
<p>Just to be clear, I note an absence of concern for cost and carbon in these conversations. Which is unacceptable. But let’s
move on.</p>
<p>It’s worth noting that I learned two useful things from Ptacek’s essay that I hadn’t really understood. First, the “agentic”
architecture of programming tools: You ask the agent to create code and it asks the LLM, which will sometimes
hallucinate; the agent will observe that it doesn’t compile or makes all the unit tests fail, discards it, and re-prompts. If
it takes the agent module 25 prompts to generate code that while imperfect is at least correct, who cares?</p>
<p>Second lesson, and to be fair this is just anecdata: It feels like the Go programming language is especially well-suited to
LLM-driven automation. It’s small, has a large standard library, and a culture that has strong shared idioms for doing almost
anything. Anyhow, we’ll find out if this early impression stands up to longer and wider industry experience.</p>
<p>Turning our attention back to cost, let’s assume that eventually all or most developers become somewhat LLM-assisted. Are
there enough of them, and will they pay enough, to cover all that investment? Especially given that models that are both
open-source and excellent are certain to proliferate? Seems dubious.</p>
<p>Suppose that, as Ptacek suggests, LLMs/agents allow us to automate the tedious low-intellectual-effort parts of our
job. Should we be concerned about how junior developers learn to get past that “easy stuff” and on the way to senior skills?
That seems a very good question, so…</p>
<h2 id='p-10'>Learning</h2>
<p>Quite likely you’ve already seen Jason Koebler’s
<a href="https://www.404media.co/teachers-are-not-ok-ai-chatgpt/?ref=daily-stories-newsletter">Teachers Are Not OK</a>, a
frankly horrifying survey of genAI’s impact on secondary and tertiary education. It is a tale of unrelieved grief and pain
and wreckage. Since genAI isn’t going to go away and students aren’t going to stop being lazy,
it seems like we’re going to re-invent the way people teach and learn.</p>
<p>The stories of students furiously deploying genAI to avoid the effort of actually, you know,
learning, are sad. Even sadder are those of genAI-crazed administrators leaning on faculty to become more efficient and
“businesslike” by using it.</p>
<p>I really don’t think there’s a coherent pro-genAI case to be made in the education context.</p>
<h2 id='p-11'>Professional communication</h2>
<p>If you want to use LLMs to automate communication with your family or friends or lovers, there’s nothing I can say that will
help you. So let’s restrict this to conversation and reporting around work and private projects and voluntarism and so on.</p>
<p>I’m
pretty sure this is where the people who think they’re going to make big money with AI think it’s going to come from.
If you’re interested in that thinking,
<a href="https://docs.google.com/presentation/d/1Der8WWGeVxdOWx37bMV_nj9N1tUAVcvSSRa6qxKx75g/edit?slide=id.p1#slide=id.p1">here’s
a sample</a>; a slide deck by a Keith Riegert for the book-publishing business which, granted, is a bit stagnant and a whole lot
overconcentrated these days. I suspect scrolling through it will produce a strong emotional reaction for quite a few readers here.
It’s also useful in that it talks specifically about costs.</p>
<p>That is for corporate-branded output. What about personal or internal professional communication; by which I mean emails and
sales reports and committee drafts and project pitches and so on? I’m pretty negative about this. If your email or pitch
doc or whatever needs to be summarized, or if it has the colorless affectless error-prone polish of 2025’s LLMs, I would
probably discard it unread.
I already found the switch to turn off Gmail’s attempts to summarize my emails.</p>
<p>What’s the genAI world’s equivalent of “Tl;dr”? I’m thinking “TA;dr” (A for AI)
or “Tg;dr” (g for genAI) or just “LLM:dr”.</p>
<p>And this vision of everyone using genAI to amplify their output and everyone else using it to summarize and filter
their input feels simply perverse.</p>
<p>Here’s what I think is
<a href="https://infosec.exchange/@codinghorror/114606355212363074">an important finding</a>, ably summarized by Jeff Atwood:</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/06/06/Dare-Jeff.png" alt="Dare Obasanjo and Jeff Atwood on how to survive AI" />
<p>Seriously, since LLMs by design emit streams that are optimized for plausibility and for harmony with the model’s
training base, in an AI-centric world there’s a powerful incentive to say things that are implausible, that are out of tune,
that are, bluntly, weird. So there’s one upside.</p>
<p>And let’s go back to cost. Are the prices in Riegert’s slide deck going to pay for trillions in capex?
Another example: My family has a Google workplace account, and the price just went up from $6/user/month to
$7. The announcement from Google emphasized that this was related to the added value provided by Gemini. Is $1/user/month gonna
make this tech make business sense?</p>
<h2 id='p-13'>What I can and can’t buy</h2>
<p>I can sorta buy the premise that there are genAI productivity boosts to be had in the code space and maybe some other
specialized domains. I can’t buy for a second that genAI is anything but toxic for anything education-related. On the
business-communications side, it’s damn well gonna be tried because billions of dollars and many management careers depend on
it paying off. We’ll see but I’m skeptical.</p>
<p>On the money side? I don’t see how the math and the capex work. And all the time, I think about the carbon that’s poisoning
the planet my children have to live on.</p>
<p>I think that the best we can hope for is the eventual financial meltdown leaving a few useful islands of things that
are actually useful at prices that make sense.</p>
<p>And in a decade or so, I can see business-section stories about all the big data center shells that were never filled in,
standing there empty, looking for another use. It’s gonna be tough, what can you do with buildings that have no windows?</p>
</div></content></entry>
<entry>
<title>Union of Finite Automata</title>
<link href='https://www.tbray.org/ongoing/When/202x/2024/07/28/Union-of-Finite-Automata' />
<link rel='replies' thr:count='0' type='application/xhtml+xml' href='/ongoing/When/202x/2024/07/28/Union-of-Finite-Automata#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2024/07/28/Union-of-Finite-Automata</id>
<published>2024-07-28T12:00:00-07:00</published>
<updated>2025-06-02T11:49:20-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/Quamina Diary' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Quamina Diary' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>In building Quamina, I needed to compute the union of two finite automata (FAs). I remembered from some university course 100 years ago that this was possible in theory, so I went looking for the algorithm, but was left unhappy. The descriptions I found tended to be hyper-academic, loaded with mathematical notation that I found unhelpful, and didn’t describe an approach that I thought a reasonable programmer would reasonably take. The purpose of this <span class="o">ongoing</span> entry is to present a programmer-friendly description of the problem and of the algorithm I adopted, with the hope that some future developer, facing the same problem, will have a more satisfying search experience.<br/> <i>[Important update: There’s a serious error halfway through; see <a href='#p-9'>here</a>.]</i></div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>In building Quamina, I needed to compute the union of two finite automata (FAs). I remembered from some university course 100 years
ago that this was possible in theory, so I went looking for the algorithm, but was left unhappy.
The descriptions I found tended to be hyper-academic, loaded with mathematical notation that I found unhelpful, and
didn’t describe an approach that I thought a reasonable programmer would reasonably take. The purpose of this <span
class='o'>ongoing</span> entry is to present a
programmer-friendly description of the problem and of the algorithm I adopted, with the hope that some future developer, facing
the same problem, will have a more satisfying search experience.<br/>
<i>[Important update: There’s a serious error halfway through; see <a href="#p-9">here</a>.]</i></p>
<p>There is very little math in this discussion (a few subscripts), and no
circles-and-arrows pictures. But it does have working Go code.</p>
<h2 id='p-1'>Finite automata?</h2>
<p>I’m not going to rehash the theory of FAs (often called state machines). In practice the purpose of an FA is to match (or
fail to match) some
input against some pattern. What the software does when the input matches the pattern (or doesn’t) isn’t relevant to
our discussion today.
Usually the inputs are strings and the patterns are regular expressions or equivalent. In practice, you compile a pattern
into an FA, and then you go through the input, character by character, trying to traverse the FA to find out whether it matches
the input.</p>
<p>An FA has a bunch of states, and for each state
there can be a list of input symbols that lead to transitions to other states. What exactly I mean by “input symbol” turns out to be
interesting and affects your choice of algorithm, but let’s ignore that for now.</p>
<p>The following statements apply:</p>
<ol>
<li><p>One state is designated as the “start state” because, well, that’s where you start.</p></li>
<li><p>Some states are called “final”, and reaching them means you’ve matched one or more patterns. In Quamina’s FAs, each
state has an extra field (usually empty) saying “if you got here you matched P*, yay!”, where P* is a list of labels for the
(possibly more than one) patterns you matched.</p></li>
<li><p>It is possible that you’re in a state and for some particular input, you transition to more than one other state. If
this is true, your FA is <em>nondeterministic</em>, abbreviated NFA.</p></li>
<li><p>It is possible that a state can have one or more “epsilon transitions”, ones that you can just take any time, not requiring
any particular input. (I wrote about this in
<a href="/ongoing/When/202x/2024/06/17/Epsilon-Love">Epsilon Love</a>.)
Once again, if this is true, you’ve got an NFA. If neither this statement nor the previous are true, it’s
a <em>deterministic</em> finite automaton, DFA.</p></li>
</ol>
<p>The discussion here works for NFAs, but lots of interesting problems can be solved with DFAs, which are simpler and faster,
and this algorithm works there too.</p>
<h2 id='p-2'>Union?</h2>
<p>If I have <code>FA1</code> that matches “foo” and <code>FA2</code> that matches “bar”, then their union,
<code>FA1 ∪ FA2</code>, matches both “foo”
and “bar”. In practice Quamina often computes the union of a large number of FAs, but it does so a pair at a time, so we’re
only going to worry about the union of two FAs.</p>
<h2 id='p-3'>The academic approach</h2>
<p>There are plenty of Web pages and YouTubes covering this. Most of them are full of Greek characters and math symbols. They go
like this:</p>
<ol>
<li><p>You have two FAs, call them <code>A</code> and <code>B</code>. <code>A</code> has states <code>A<sub>1</sub></code>, …
<code>A<sub>maxA</sub></code>, <code>B</code> has <code>B<sub>1</sub></code>, … <code>B<sub>maxB</sub></code></p></li>
<li><p>The union contains all the states in <code>A</code>, all the states in <code>B</code>, and the “product” of
<code>A</code> and <code>B</code>, which is to say states you could call <code>A<sub>1</sub>B<sub>1</sub></code>,
<code>A<sub>1</sub>B<sub>2</sub></code>, <code>A<sub>2</sub>B<sub>1</sub></code>, <code>A<sub>2</sub>B<sub>2</sub></code>,
… <code>A<sub>maxA</sub>B<sub>maxB</sub></code>.</p></li>
<li><p>For each state <code>A<sub>X</sub>B<sub>Y</sub></code>, you work out its transitions by looking at the transitions of
the two states being combined. For some input symbol, if <code>A<sub>X</sub></code> has a transition to
<code>A<sub>XX</sub></code> but <code>B<sub>Y</sub></code> has no transition, then the combined state just has the A
transition. The reverse for an input where <code>B<sub>Y</sub></code> has a transition but <code>A<sub>X</sub></code>
doesn’t. And if <code>A<sub>X</sub></code> transitions to <code>A<sub>XX</sub></code> and <code>B<sub>Y</sub></code> transitions to
<code>B<sub>YY</sub></code>, then the transition is to <code>A<sub>XX</sub>B<sub>YY</sub></code>.</p></li>
<li><p>Now you’ll have a lot of states, and it usually turns out that many of them aren’t reachable. But there are plenty of
algorithms to filter those out. You’re done, you’ve computed the union and <code>A<sub>1</sub>B<sub>1</sub></code> is its
start state!</p></li>
</ol>
<h2 id='p-4'>Programmer-think</h2>
<p>If you’re like me, the idea of computing all the states, then throwing out the unreachable ones, feels wrong. So here’s
what I suggest, and has worked well in practice for Quamina:</p>
<ol>
<li><p>First, merge <code>A<sub>1</sub></code> and <code>B<sub>1</sub></code> to make your new start state
<code>A<sub>1</sub>B<sub>1</sub></code>. Here’s how:</p></li>
<li><p>If an input symbol causes no transitions in either <code>A<sub>1</sub></code> or <code>B<sub>1</sub></code>, it also
doesn’t cause any in <code>A<sub>1</sub>B<sub>1</sub></code>.</p></li>
<li><p>If an input symbol causes a transition in <code>A<sub>1</sub></code> to <code>A<sub>X</sub></code> but no transition
in <code>B<sub>1</sub></code>, then you adopt <code>A<sub>X</sub></code> into the union, and any other <code>A</code> states
it points to, and any they point to, and so on.</p></li>
<li><p>And of course if <code>B<sub>1</sub></code> has a transition to <code>B<sub>Y</sub></code> but
<code>A<sub>1</sub></code> doesn’t transition, you flip it the other way, adopting <code>B<sub>Y</sub></code> and its
descendents.</p></li>
<li><p>And if <code>A<sub>1</sub></code> transitions to <code>A<sub>X</sub></code> and <code>B<sub>1</sub></code> transitions
to <code>B<sub>Y</sub></code>, then you adopt a new state <code>A<sub>X</sub>B<sub>Y</sub></code>, which you compute
recursively the way you just did for <code>A<sub>1</sub>B<sub>1</sub></code>. So you’ll never compute anything that’s not
reachable.</p></li>
</ol>
<p>I could stop there. I think that’s enough for a competent developers to get the idea? But it turns out there
are a few details, some of them interesting. So, let’s dig in.</p>
<h2 id='p-5'>“Input symbol”?</h2>
<p>The academic discussion of FAs is very abstract on this subject, which is fair enough, because when you’re talking about how
to build, or traverse, or compute the union of FAs, the algorithm doesn’t depend very much on what the symbols actually are. But
when you’re writing code, it turns out to matter a lot.</p>
<p>In practice, I’ve done a lot of work with FAs over the years, and I’ve only ever seen four things used as input symbols
to drive them. They are:</p>
<ul>
<li><p>Unicode “characters” represented by code points, integers in the range 0…1,114,111 inclusive.</p></li>
<li><p>UTF-8 bytes, which have values in the range 0…244 inclusive.</p></li>
<li><p>UTF-16 values, unsigned 16-bit integers. I’ve only ever seen this used in Java programs because that’s what
its native <code>char</code> type is. You probably don’t want to do this.</p></li>
<li><p>Enum values, small integers with names, which tend to come in small collections.</p></li>
</ul>
<p>As I said, this is all I’ve seen, but 100% of the FAs that I’ve seen automatically generated and subject to
set-arithmetic operations like Union are based on UTF-8. And that’s what Quamina uses, so that’s what I’m going to use in the
rest of this discussion.</p>
<h2 id='p-7'>Code starts here</h2>
<p>This comes from Quamina’s
<a href="https://github.com/timbray/quamina/blob/main/nfa.go">nfa.go</a>. We’re going to look at the function
<code>mergeFAStates</code>, which implements the merge-two-states logic described above.</p>
<p>Lesson: This process can lead to a lot of wasteful work. Particularly if either or both of the states transition on ranges of
values like <code>0…9</code> or <code>a…z</code>. So we only want to do the work merging any pair of states once, and we want
there only to be one merged value. Thus we start with a straightforward memo-ization.</p>
<div class="tbc"><pre>
<span class="kd">func</span><span class="w"> </span><span class="nx">mergeFAStates</span><span class="p">(</span><span class="nx">state1</span><span class="p">,</span><span class="w"> </span><span class="nx">state2</span><span class="w"> </span><span class="o">*</span><span class="nx">faState</span><span class="p">,</span><span class="w"> </span><span class="nx">keyMemo</span><span class="w"> </span><span class="kd">map</span><span class="p">[</span><span class="nx">faStepKey</span><span class="p">]</span><span class="o">*</span><span class="nx">faState</span><span class="p">)</span><span class="w"> </span><span class="o">*</span><span class="nx">faState</span><span class="w"> </span><span class="p">{</span>
<span class="w"> </span><span class="c1">// try to memo-ize</span>
<span class="w"> </span><span class="nx">mKey</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">faStepKey</span><span class="p">{</span><span class="nx">state1</span><span class="p">,</span><span class="w"> </span><span class="nx">state2</span><span class="p">}</span>
<span class="w"> </span><span class="nx">combined</span><span class="p">,</span><span class="w"> </span><span class="nx">ok</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">keyMemo</span><span class="p">[</span><span class="nx">mKey</span><span class="p">]</span>
<span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="nx">ok</span><span class="w"> </span><span class="p">{</span>
<span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nx">combined</span>
<span class="w"> </span><span class="p">}</span>
</pre>
<p>Now some housekeeping. Remember, I noted above that any state might contain a signal saying that arriving here
means you’ve matched pattern(s). This is called <code>fieldTransitions</code>, and the merged state obviously has to
match all the things that either of the merged states match. Of course, in the vast majority of cases neither merged state
matched anything and so this is a no-op.</p>
<pre>
<span class="w"> </span><span class="nx">fieldTransitions</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nb">append</span><span class="p">(</span><span class="nx">state1</span><span class="p">.</span><span class="nx">fieldTransitions</span><span class="p">,</span><span class="w"> </span><span class="nx">state2</span><span class="p">.</span><span class="nx">fieldTransitions</span><span class="o">...</span><span class="p">)</span></pre>
<p>Since our memo-ization attempt came up empty, we have to allocate an empty structure for the new merged state, and add it to the
memo-izer.</p>
<pre>
<span class="w"> </span><span class="nx">combined</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="o">&</span><span class="nx">faState</span><span class="p">{</span><span class="nx">table</span><span class="p">:</span><span class="w"> </span><span class="nx">newSmallTable</span><span class="p">(),</span><span class="w"> </span><span class="nx">fieldTransitions</span><span class="p">:</span><span class="w"> </span><span class="nx">fieldTransitions</span><span class="p">}</span>
<span class="w"> </span><span class="nx">keyMemo</span><span class="p">[</span><span class="nx">mKey</span><span class="p">]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">combined</span></pre>
<p>Here’s where it gets interesting. The algorithm talks about looking at the inputs that cause transitions in the states we’re
merging. How do you find them? Well, in the case where you’re transitioning on UTF-8 bytes, since there are only 244 values,
why not do the simplest thing that could possibly work and just check each byte value?</p>
<p>Every Quamina state contains a table that encodes the byte transitions, which operates like the Go construct
<code>map[byte]state</code>. Those tables are implemented in
<a href="/ongoing/When/202x/2022/06/25/Small-Tables">a compact data structure optimized for fast traversal</a>. But for doing this
kind of work, it’s easy to “unpack” them into a fixed-sized table; in Go, <code>[244]state</code>. Let’s do that for the states
we’re merging and for the new table we’re building.</p>
<pre><span class="w"> </span><span class="nx">u1</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">unpackTable</span><span class="p">(</span><span class="nx">state1</span><span class="p">.</span><span class="nx">table</span><span class="p">)</span>
<span class="w"> </span><span class="nx">u2</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="nx">unpackTable</span><span class="p">(</span><span class="nx">state2</span><span class="p">.</span><span class="nx">table</span><span class="p">)</span>
<span class="w"> </span><span class="kd">var</span><span class="w"> </span><span class="nx">uComb</span><span class="w"> </span><span class="nx">unpackedTable</span></pre>
<p><code>uComb</code> is where we’ll fill in the merged transitions.</p>
<p>Now we’ll run through all the possible input values; <code>i</code> is the byte value, <code>next1</code> and <code>next2</code>
are the transitions on that value. In practice, <code>next1</code> and <code>next2</code> are going to be null most of the time.</p>
<pre><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="nx">i</span><span class="p">,</span><span class="w"> </span><span class="nx">next1</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">u1</span><span class="w"> </span><span class="p">{</span>
<span class="w"> </span><span class="nx">next2</span><span class="w"> </span><span class="o">:=</span><span class="w"></span><span class="nx"> u2</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span></pre>
<p>Here’s where we start building up the new transitions in the unpacked array <code>uComb</code>.</p>
<p>For many values of <code>i</code>, you can avoid actually merging the states to create a new one. If the transition is the
same in both input FAs, or if either of them are null, or if the transitions for this value of <code>i</code> are the same as
for the last value. This is all about avoiding unnecessary work and the <code>switch</code>/<code>case</code> structure is the
result of a bunch of profiling and optimization.</p>
<pre><span class="w"> </span><span class="k">switch</span><span class="w"> </span><span class="p">{</span>
<span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="nx">next1</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="nx">next2</span><span class="p">:</span><span class="w"> </span><span class="c1">// no need to merge</span>
<span class="w"> </span><span class="nx">uComb</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">next1</span>
<span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="nx">next2</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="kc">nil</span><span class="p">:</span><span class="w"> </span><span class="c1">// u1 must be non-nil</span>
<span class="w"> </span><span class="nx">uComb</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">next1</span>
<span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="nx">next1</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="kc">nil</span><span class="p">:</span><span class="w"> </span><span class="c1">// u2 must be non-nil</span>
<span class="w"> </span><span class="nx">uComb</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">next2</span>
<span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="nx">i</span><span class="w"> </span><span class="p">></span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="o">&&</span><span class="w"> </span><span class="nx">next1</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="nx">u1</span><span class="p">[</span><span class="nx">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="w"> </span><span class="o">&&</span><span class="w"> </span><span class="nx">next2</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="nx">u2</span><span class="p">[</span><span class="nx">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]:</span><span class="w"> </span><span class="c1">// dupe of previous step - happens a lot</span>
<span class="w"> </span><span class="nx">uComb</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nx">uComb</span><span class="p">[</span><span class="nx">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span></pre>
<p>If none of these work, we haven’t been able to avoid merging the two states. We do that by a recursive call to invoke
all the logic we just discussed.</p>
<p>There is a complication. The automaton might be nondeterministic, which means that there might be more than one transition
for some byte value. So the data structure actually behaves like <code>map[byte]*faNext</code>, where <code>faNext</code> is a
wrapper for a list of states you can transition to.</p>
<p>So here we’ve got a nested loop to recurse for each possible combination of transitioned-to states that can occur on this
byte value. In a high proportion of cases the FA is deterministic, so there’s only one state from each FA being merged and this
nested loop collapses to a single recursive call.</p>
<pre><span class="w"> </span><span class="k">default</span><span class="p">:</span><span class="w"> </span><span class="c1">// have to recurse & merge</span>
<span class="w"> </span><span class="kd">var</span><span class="w"> </span><span class="nx">comboNext</span><span class="w"> </span><span class="p">[]</span><span class="o">*</span><span class="nx">faState</span>
<span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="nx">_</span><span class="p">,</span><span class="w"> </span><span class="nx">nextStep1</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">next1</span><span class="p">.</span><span class="nx">states</span><span class="w"> </span><span class="p">{</span>
<span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="nx">_</span><span class="p">,</span><span class="w"> </span><span class="nx">nextStep2</span><span class="w"> </span><span class="o">:=</span><span class="w"> </span><span class="k">range</span><span class="w"> </span><span class="nx">next2</span><span class="p">.</span><span class="nx">states</span><span class="w"> </span><span class="p">{</span>
<span class="w"> </span><span class="nx">comboNext</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nb">append</span><span class="p">(</span><span class="nx">comboNext</span><span class="p">,</span><span class="w"> </span><span class="nx">mergeFAStates</span><span class="p">(</span><span class="nx">nextStep1</span><span class="p">,</span><span class="w"> </span><span class="nx">nextStep2</span><span class="p">,</span><span class="w"> </span><span class="nx">keyMemo</span><span class="p">))</span>
<span class="w"> </span><span class="p">}</span>
<span class="w"> </span><span class="p">}</span>
<span class="w"> </span><span class="nx">uComb</span><span class="p">[</span><span class="nx">i</span><span class="p">]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="o">&</span><span class="nx">faNext</span><span class="p">{</span><span class="nx">states</span><span class="p">:</span><span class="w"> </span><span class="nx">comboNext</span><span class="p">}</span>
<span class="w"> </span><span class="p">}</span>
<span class="w"> </span><span class="p">}</span></pre>
<p>We’ve filled up the unpacked state-transition table, so we’re almost done. First, we have to compress it into its
optimized-for-traversal form.</p>
<pre><span class="w"> </span><span class="nx">combined</span><span class="p">.</span><span class="nx">table</span><span class="p">.</span><span class="nx">pack</span><span class="p">(</span><span class="o">&</span><span class="nx">uComb</span><span class="p">)</span></pre>
<p>Remember, if the FA is nondeterministic, each state can have “epsilon” transitions which you can follow any time without
requiring any particular input. The merged state needs to contain all the epsilon transitions from each input state.</p>
<pre><span class="w"> </span><span class="nx">combined</span><span class="p">.</span><span class="nx">table</span><span class="p">.</span><span class="nx">epsilon</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="nb">append</span><span class="p">(</span><span class="nx">state1</span><span class="p">.</span><span class="nx">table</span><span class="p">.</span><span class="nx">epsilon</span><span class="p">,</span><span class="w"> </span><span class="nx">state2</span><span class="p">.</span><span class="nx">table</span><span class="p">.</span><span class="nx">epsilon</span><span class="o">...</span><span class="p">)</span>
<span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="nx">combined</span>
<span class="p">}</span></pre>
</div>
<p>And, we’re done. I mean, we are once all those recursive calls have finished crawling through the states being merged.</p>
<h2 id='p-9'>Oops</h2>
<p>The discussion of epsilons above is wrong, in a way that’s harder to reproduce than you might think.
The discussion is still
correct for DFA’s and (weirdly) (I think) (not sure why yet) the shell-style “wildcard” <code>*</code> operator, which means
<code>.*</code> in a regular expression.</p>
<p>It’s not clear that in general there’s a way to merge (Quamina-style) two NFA states when either or both of them have epsilon transitions.
Per the
academic literature, the right way to get the union of two NFAs is to have an empty branch state with two epsilon transitions,
one to each NFA. So you traverse the two in parallel.</p>
<p>It took me a a whole lot of pain to figure this out and I haven’t entirely worked out the best implementation. I promise more
regular-expressions-at-scale walls of text and code in this space when I do.</p>
<p>I write this because when you type “merge nondeterministic finite automata” into Web search, the blog you are now reading is
dangerously high in the search results.</p>
<h2 id='p-8'>Is that efficient?</h2>
<p>As I said above, this is an example of a “simplest thing that could possibly work” design. Both the recursion and the
unpack/pack sequence are kind of code smells, suggesting that this could be a pool of performance quicksand.</p>
<p>But apparently not. I ran a benchmark where I added 4,000 patterns synthesized from the Wordle
word-list; each of them looked like this:</p>
<p><code>{"allis": { "biggy": [ "ceils", "daisy", "elpee", "fumet", "junta", … </code> (195 more).</p>
<p>This produced a <em>huge</em> deterministic FA with about 4.4 million states, with the addition of these hideous worst-case
patterns running at 500/second. Good enough for rock ’n’ roll.</p>
<p>How about nondeterministic FAs? I went back to that Wordle source and, for each of its 12,959 words, added a pattern with a
random wildcard; here are three of them:</p>
<p><code>{"x": [ {"shellstyle": "f*ouls" } ] }<br/>
{"x": [ {"shellstyle": "pa*sta" } ] }<br/>
{"x": [ {"shellstyle": "utter*" } ] }</code></p>
<p>This produced an NFA with 46K states, the addition process ran at 70K patterns/second.
</p>
<p>Sometimes the simplest thing that could possibly work, works.</p>
</div></content></entry>
<entry>
<title>Perfectly Different Colors</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/05/31/Colors' />
<link rel='replies' thr:count='3' type='application/xhtml+xml' href='/ongoing/When/202x/2025/05/31/Colors#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/05/31/Colors</id>
<published>2025-05-31T12:00:00-07:00</published>
<updated>2025-06-02T08:51:38-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='Arts/Photos' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Arts' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Photos' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Arts/Photos/Cameras' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Cameras' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>This considers how two modern cameras handle a difficult color challenge, illustrated by photos of a perfect rose and a piano</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>This considers how two modern cameras handle a difficult color challenge, illustrated by photos of a perfect rose and a piano.</p>
<p>We moved into our former place in January 1997 and, that summer, discovered the property included this slender little rose
that only had a couple blossoms every year, but they were perfection, beautifully shaped and in a unique shade of red I’d
never seen anywhere else (and still haven’t). Having no idea of its species, we’ve always called it “our perfect rose”.</p>
<p>So when
<a href="/ongoing/When/202x/2025/02/28/Moved">we moved</a> last year, we took the rose with us. It seems to
like the new joint, has a blossom out and two more on the way and it’s still May.</p>
<p>I was looking at it this morning and it occurred to me that its color might be an interesting challenge to the two fine cameras I use
regularly, namely a Google Pixel 7 and a Fujifilm X-T5.</p>
<p>First the pictures.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/05/31/PXL_20250531_185139866.png" alt="The “perfect” rose." />
<img src="https://www.tbray.org/ongoing/When/202x/2025/05/31/TXT55657.png" alt="The “perfect” rose" />
<h2 id='p-2'>Limitations</h2>
<p>First of all, let’s agree that this comparison is horribly flawed. To start with, by the time the pixels have made it from
the camera to your screen, they’ve been through Lightroom, possibly a social-media-software uploader and renderer, and then
your browser (or mobile app) and screen contribute their opinions.
Thus the colors are likely to vary a lot depending where you are and what you’re using.</p>
<p>Also, it’s hard to get really comparable shots out of the Pixel and Fuji; their lenses and processors and underlying
architectures are really different. I was going to disclose the reported shutter speeds, aperture, and ISO values, but they are
so totally non-comparable that I decided that’d be actively harmful. I’ll just say that I tried to let each do its best.</p>
<p>I post-processed both, but limited that to cropping; nothing about the color or exposure was touched.</p>
<p>And having said all that, I think the exercise retains interest.</p>
<h2 id='p-1'>Which?</h2>
<p>The Pixel is above, the Fuji below.</p>
<p>The Pixel is wrong. The Fuji is… not bad. The blossom’s actual color, to my eye, has a little more orange than I see in the
photo; but only a little. The Pixel subtracts the orange and introduces a suggestion of violet that the blossom, to
my eye, entirely lacks.</p>
<p>Also, the Pixel is artificially sharpening up the petals; in reality, the contrast was low and the shading nuanced; just as
presented by the X-T5.</p>
<p>Is the Pixel’s rendering a consequence of whatever its sensor is? Or of the copious amount of processing that
contributes to Google’s widely-admired (by me too) “computational photography”? I certainly have no idea. And in fact,
most of the pictures I share come from my Android because the best camera (this is always true) is the one you have with
you. For example…</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/05/31/PXL_20250531_032232026.png" alt="Grand piano by itself in an old church" />
<div class='caption'><p>That same evening we took in a concert put on by the local Chopin Society featuring 89-year-old
<a href="MikhailVoskresensky">Mikhail Voskresensky</a>, who plays really fast and loud in an old super-romantic style, just the
thing for the music: Very decent Beethoven and Mozart, kind of aimless Grieg, and the highlight, a lovely take on Chopin’s
Op. 58 Sonata, then a <cite>Nocturne</cite> in the encores.</p>
<p>Anyhow, I think the Camera I Had With Me did fine. This is
<a href="https://www.thecathedral.ca/programs/architecture-heritage">Vancouver’s oldest still-standing
building</a>, Christ Church Cathedral, an exquisite space for the eyes and ears.</p></div>
<p>Maybe I’ll do a bit more conscious color-correction on the Pixel shots in future (although I didn’t on the piano). Doesn’t
mean it’s not a great camera.</p>
</div></content></entry>
<entry>
<title>Comparing Numbers Badly</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/05/30/Number-Comparison-Representation' />
<link rel='replies' thr:count='4' type='application/xhtml+xml' href='/ongoing/When/202x/2025/05/30/Number-Comparison-Representation#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/05/30/Number-Comparison-Representation</id>
<published>2025-05-30T12:00:00-07:00</published>
<updated>2025-05-30T16:15:25-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='Language' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Language' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology/Math' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Technology' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Math' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>This is just a gripe about two differently bad ways to compare numbers. They share a good alternative</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>This is just a gripe about two differently bad ways to compare numbers. They share a good alternative.</p>
<h2 id='p-1'>“Order of magnitude”</h2>
<p>Typically sloppy usages: “AI increases productivity by an order of magnitude”, “Revenue from recorded music is orders of
magnitude smaller than back in the Eighties”.</p>
<p>Everyone reading this probably already knows that “order of magnitude” has a precise meeting: Multiply or divide by
ten. But clearly, the people who write news stories and marketing spiels either don’t, or are consciously using the idioms to
lie. In particular, they are trying to say “more than” or “less than” in a dramatic and impressive-sounding way.</p>
<p>Consider that first example. It is saying that AI delivers a ten-times gain in productivity. If they’d actually said “ten
times” people would be more inclined to ask “What units?” and “How did you measure?” This phrase makes me think that its author
is probably lying.</p>
<p>The second example is even more pernicious. Since “orders” is plural, they are claiming at least two orders of magnitude,
i.e. that revenue is down by <em>at least</em> a factor of a hundred. The difference between two, three, and four orders of
magnitude is huge! I’d probably argue that the phrase “order<b>s</b> of magnitude” should probably
never be used. In this case, I highly doubt that the speaker has any data, and that they’re just trying to say that the
revenue is down really a lot.</p>
<p>The solution is simple: Say “by a factor of ten” or “ten times as high” or “at least 100 times less.” Assuming your claim is
valid, it will be easily understood; Almost everyone has a decent intuitive understanding of what a ten-times or hundred-times
difference feels like.</p>
<h2 id='p-2'>“Percent”</h2>
<p>What actually got me started reading this was reading a claim that some business’s “revenue increased by 250%.”
Let’s see. If the revenue were one million and it increased by 10%, it’d be 1.1 million. If it increased by 100% it’d be two
million. 200% is three million. So what they meant by 250% is that the revenue increased by a factor of 3.5. It is <em>so
much</em> easier to understand “3.5 times” than 250%. Furthermore, I bet a lot of people intuitively feel that 250% means “2.5
times”, which is just wrong.</p>
<p>I think quoting percentages is clear and useful for values less than 100. There is nothing wrong with talking about a 20%
increase or 75% decrease.</p>
<p>So, same solution: For percentages past 100, don’t use them, just say “by a factor of X”. Once again, people have an instant
(and usually correct) gut feel for what a 3.5-times increase feels like.</p>
<h2 id='p-3'>“But English is a living language!”</h2>
<p>Not just living, but also squirmy and slutty, open to both one-night stands and permanent relationships with neologisms no
matter how ugly and
imports from other dialects no matter how sketchy. Which is to say, there’s nothing I can do to keep “orders of magnitude” from
being used to mean “really a lot”.</p>
<p>In fact, it’s only a problem when you’re trying to communicate a numeric difference. But that’s an important application of
human language.</p>
<p>Perversely, I guess you could argue that these
bad idioms are useful in helping you detect statements that are probably either ignorant or just lies. Anyhow, now you know that
when I hear them, I hear patterns that make me inclined to disbelieve. And I bet I’m not the only one.</p>
</div></content></entry>
<entry>
<title>CL XLVI: Happy Colors</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/05/27/Happy-Colors' />
<link rel='replies' thr:count='0' type='application/xhtml+xml' href='/ongoing/When/202x/2025/05/27/Happy-Colors#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/05/27/Happy-Colors</id>
<published>2025-05-27T12:00:00-07:00</published>
<updated>2025-05-28T21:58:08-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='The World/Cottage Life' />
<category scheme='https://www.tbray.org/ongoing/What/' term='The World' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Cottage Life' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>Last weekend we were at our cabin on <a href='https://en.wikipedia.org/wiki/Keats_Island_(British_Columbia)'>Keats Island</a> and I came away with two <a href='/ongoing/What/The%20World/Cottage%20Life/'>cottage-life</a> pictures I wanted to write about. To write cheery stuff actually, a rare pleasure in these dark days. Both have a story but this first one’s simple</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>Last weekend we were at our cabin on
<a href="https://en.wikipedia.org/wiki/Keats_Island_(British_Columbia)">Keats Island</a> and I came away with two
<a href="/ongoing/What/The%20World/Cottage%20Life/">cottage-life</a> pictures I
wanted to write about. To write cheery stuff actually, a rare pleasure in these dark days. Both have a story but this first one’s
simple.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/05/27/PXL_20250525_212106021.png" alt="Evergreen branches in spring with the new life showing" />
<p>It’s just an ordinary evergreen tree, not very tall, nothing special about it. But spring’s here! So at the end of each branch
there’s a space where the needles are new and shout their youth in light green, a fragile color as compared to the soberly rich
shade of the middle-aged needles further up the branch. Probably a metaphor for something complicated but I just see a tree
getting on with the springtime business of tree-ness. Good on it.</p>
<p>Now a longer story.
What happened was, we had an extra-low tide. Tide is a big deal, we get 17 vertical feet at the extremes which can cause
problems for boats and docks and if you happen to arrive with several days worth of supplies at low tide well it sucks to be
you, because you’re gonna be toting everything up that much further.</p>
<p>But I digress.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/05/27/PXL_20250525_172750708.png" alt="Purple sea stars hide among dark rocks" />
<p>I went for a walk at low tide because you see things that are usually mostly hidden. For example these
<a href="https://en.wikipedia.org/wiki/Starfish">starfish</a>, also known as sea stars or even “asteroids”. No, really, check
that link.</p>
<p>These are
<a href="https://en.wikipedia.org/wiki/Pisaster_ochraceus"><i>Pisaster ochraceus</i></a>, distinguished by that pleasing violet color.
Have a close look. They’re intertidal creatures hiding from the unaccustomed light and air. The important thing is that
they’re more or less whole, which is to say free of
<a href="https://en.wikipedia.org/wiki/Sea_star_wasting_disease">wasting disease</a>, of which there’s been a major epizootic in
recent years. The disease isn’t subtle, it makes their arms melt away into purple goo; extremely gross.</p>
<p>Plus, ecologies being what they are, there are downstream effects. Sea stars predate on sea urchins only recently they
haven’t been because wasting disease. It turns out that sea urchins eat the kelp that baby shrimp trying to grow up hide in.
Fewer stars, more urchins, less prawns. Which means that the commercial prawn-fishers have been coming up
empty and going out of business.</p>
<p>Anyhow, seeing a cluster of disease-free stars is nice, whether you’re in the seafood business or you just like
the stars for their own sake, as I do.</p>
<p>And light-green needles too. And spring. Enjoy it while you can.</p>
</div></content></entry>
<entry>
<title>The Lens of Spring</title>
<link href='https://www.tbray.org/ongoing/When/202x/2025/05/17/Springtime-Lens' />
<link rel='replies' thr:count='3' type='application/xhtml+xml' href='/ongoing/When/202x/2025/05/17/Springtime-Lens#comments' />
<id>https://www.tbray.org/ongoing/When/202x/2025/05/17/Springtime-Lens</id>
<published>2025-05-17T12:00:00-07:00</published>
<updated>2025-05-18T11:53:07-07:00</updated>
<category scheme='https://www.tbray.org/ongoing/What/' term='The World/Economics' />
<category scheme='https://www.tbray.org/ongoing/What/' term='The World' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Economics' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Arts/Photos/Cameras' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Arts' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Photos' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Cameras' />
<category scheme='https://www.tbray.org/ongoing/What/' term='Arts/Photos' />
<summary type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>Back in the early days of this blog, I used to publish posts that were mostly pictures of plants and flowers. Especially at this time of year. I think that energy went into Twitter and now the Fediverse, where it’s so easy to take a picture and post it right then. This week I got a freshly-repaired lens back from the shop and it put me in the mood to get closer to the botanical frenzy springing at us from every direction. Herewith four pix of two plants, one of a lens, and more thoughts on a familiar subject: Whether it’s better to repair than to replace</div></summary>
<content type='xhtml'><div xmlns='http://www.w3.org/1999/xhtml'>
<p>Back in the early days of this blog, I used to publish posts that were mostly pictures of plants and flowers. Especially at this
time of year. I think that energy went into Twitter and now the Fediverse, where it’s so easy to take a picture and post it
right then. This week I got a freshly-repaired lens back from the shop and it put me in the mood to get closer to the
botanical frenzy springing at us from every direction. Herewith four pix of two plants, one of a lens, and more thoughts on a
familiar subject: Whether it’s better to repair than to replace.</p>
<p>The lens, by the way, was the
<a href="https://www.fujifilm-x.com/en-ca/products/lenses/xf18-55mmf28-4-r-lm-ois/">Fuji 18-55</a> oops its full name is
“Fujinon XF18-55mmF2.8-4 R LM OIS” so there. I
<a href="/ongoing/When/201x/2013/03/06/Fuji-X-E1-in-Tokyo">bought it</a> in March of 2013 and have dropped it more than once; I
have retained 1,432 pictures taken with it over the years. But then it stopped working.</p>
<p>More words on that later, but pictures first.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/05/17/TXT55621.png" alt="A yellow Fru Dagmar Hastrup rose blossom" />
<div class='caption'><p>Roses have names and this one is “Fru Dagmar Hastrup”. Therein
<a href="/ongoing/When/200x/2008/06/26/Yellow-Rugosa">lies a tale</a> that is either 17 or 111 years old, depending how you
count.</p></div>
<p>That’s the first picture I took with the repaired 18-55. But then I thought that the whole point of this basic zoom was that
you could go wide to capture big things, or long to, well, zoom in on ’em. So I went out front.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/05/17/TXT55626.png" alt="Looking up into the branches of a large deciduous tree" />
<div class='caption'><p>Trees have names too. This is a
<a href="https://en.wikipedia.org/wiki/Fraxinus_americana">White Ash</a> (<i>Fraxinus americana</i>).</p></div>
<p>That ash is one of the trees lining the street we
<a href="/ongoing/When/202x/2025/02/28/Moved">moved onto last October</a>. It’s really immense. Let’s crank the zoom way wide and
capture most of it. Doing this reveals really great geometry, so let’s subtract the color and add some
<a href="https://nikcollection.dxo.com/nik-silver-efex/">Silver Efex</a> sizzle.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/05/17/TXT55625-Edit.png" alt="Black and white rendition of the spreading branches of a large tree" />
<p>And then we can zoom back in.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/05/17/TXT55628.png" alt="The first fork in the trunk of a large tree, with moss and outgrowths" />
<p>The closer you get, the better it looks.</p>
<h2 id='p-1'>Fixing that lens</h2>
<p>I like quirky fast compact opinionated prime lenses just as much as the next photoenthusiast, but a decent midrange zoom
is just too useful not to have. I could’ve replaced this one with the new-fangled
<a href="https://www.fujifilm-x.com/en-ca/products/lenses/xf16-50mmf28-48-r-lm-wr/">16-50mm</a> (also has a long complicated
Real Name but never mind). That would cost me extra money and
<a href="https://www.youtube.com/watch?v=1rLcCkilADY&t=3s">might not even be better</a>.</p>
<p>So I poked around on the Fujifilm Web site and sure enough, they offer repair as a service, just package it up and mail it
in. A few days after doing so I got an email quoting me a price and asking for approval, which I granted.
You shouldn’t be surprised. Way back in 2011 I wrote
<a href="/ongoing/When/201x/2011/10/20/Worth-Repairing">Worth Fixing</a>, the exemplar of which was a different excellent lens.
And then just last year my
<a href="/ongoing/When/202x/2024/06/01/Parable-of-the-Sofa">Parable of the Sofa</a> touched a few
nerves. So I didn’t think very hard about it.</p>
<p>But then I realized I hadn’t even checked whether the price was reasonable. So I
<a href="https://www.ebay.com/sch/i.html?_nkw=xf18-55">turned to eBay</a> and, well, I could have got a mint-condition
secondhand 18-55 for less than the cost of the repair. Not a lot less, but still. Oh well. If it were reasonable to care
about a single instance of a standardized commercial product, I’d care about that lens.</p>
<p>Anyhow, it works pretty well. Showing its age, but still reasonably handsome.</p>
<img src="https://www.tbray.org/ongoing/When/202x/2025/05/17/PXL_20250518_040716981.png" alt="Fujifilm x-T5 camera with the 18-55mm lens attached" />
<p>If I live long enough maybe I’ll take another thousand pictures with it.</p>
</div></content></entry>
</feed>
If you would like to create a banner that links to this page (i.e. this validation result), do the following:
Download the "valid Atom 1.0" banner.
Upload the image to your own server. (This step is important. Please do not link directly to the image on this server.)
Add this HTML to your page (change the image src
attribute if necessary):
If you would like to create a text link instead, here is the URL you can use:
http://www.feedvalidator.org/check.cgi?url=http%3A//www.tbray.org/ongoing/ongoing.atom