Anecdote or data point

I saw that there was some argument over how much slower slot access is than struct access, so I just decided to measure it naively. I made a two slot sruct and a CLOS version of a CONS cell with car and cdr slots and I ran LTAK using regular lists, `lists' made from CLOS conses, and `lists' made from structs. Here are the results:

D:\repositories\clos-benchmark>sbcl --script run-benchmarks.lisp
Benchmark: ltak over native cons cells, CLOS my-cons nodes, and my-cons-struct nodes
Inputs: x=15 y=9 z=4 repeats=35

Scenario                   min-ms     mean-ms      max-ms      ratio
--------------------------------------------------------------------
native standard               0.129      0.146      0.186
clos standard                 1.346      1.365      1.475       9.37x
struct standard               0.172      0.175      0.179       1.20x
native optimized              0.068      0.069      0.073
clos optimized                0.411      0.414      0.419       6.04x
struct optimized              0.068      0.069      0.073       1.01x

In this naive use case, structs are same as native cons cells, but CLOS objects are one ninth the speed of a struct or cons cell if you just use it unoptimized, and one sixth the speed if optimizations are turned on.

But the CLOS instance is more functional than the cons cell in mimics. For instance, I could add a slot to the class and all the instances would be lazily updated with the new slot. I can also subclass the CLOS class and the selector functions will continue to work. Finally, I can redefine the CLOS closs while I'm developing it and all the instances will be uppdated. THe machinery to keep all this running is costing us our factor of 9.

But this might be worth the cost if we are running on a network where the bulk of the time will be transmitting the answer down the pipe once it is computed. Taking a few extra milliseconds to compute the answer might be worth the convenience features of CLOS.

Controlled Unclassified Information

Back in the day, the US government had a program called SBIR (Small Business Innovation Research) that funded small businesses to do research and development. I recall sitting in our dorm in college, reading through a giant printed catalog of SBIR grants just to amuse ourselves by brainstorming solutions over bad pizza.

.

So, I got curious the other day: what does the SBIR landscape look like now?

I can tell you right now: do not even try to read an SBIR solicitation on your local machine. You are opening yourself up to a world of absolute, unmitigated pain.

You might think, what harm could there be in simply opening a file?

Well, in the modern compliance panopticon, any manipulation of digital information that comes from the govenment has the potential to spawn CUI (Controlled Unclassified Information). CUI is basically a digital pathogen; once you download that file, *anything whatsover* derived from it, including notes and metadata, instantly becomes CUI by association. The moment you read an SBIR on your computer, you’ve infected your system, rendering you subject to a nightmare of Byzantine federal regulations.

These days, the amount of beurocratic red tape surrounding CUI is insane. To even look at the file legally, you need a dedicated, air-gapped machine completely disconnected from the internet, conforming to a massive, expensive slew of NIST standards covering everything from hardware-level encryption to strict access controls. Alternatively you could contract with a cloud company that offers a pre-certified "CUI-compliant" environment.

And assuming you actually shell out the cash and jump through the hoops to set up this digital containment zone just to read a PDF, you must meticulously audit and account for every single action you take in its presence. Under current federal auditing logic, you are explicitly assumed to be attempting to defraud the government unless you can produce a mountain of paper proving otherwise. Want to bring in a partner to bounce ideas around? You can’t just "know a guy." You have to navigate a labyrinth of federal subcontracting regulations.

I had intended on amusing myself by reading some SBIRs and daydreaming about solutions that might involve Lisp (an impossibility in the modern enterprise stack for entirely separate, depressing reasons). Instead, I quickly discovered I did not even own the physical hardware required to even read an SBIR without running afoul of federal regulations.

I wanted to read some clever and inspiring engineering proposals. I ended up reading a lot of very dry and boring compliance regulations.

Regression

Last year I wrote some Lisp related AI apps. There was a syntax highlighter that used the LLM to determine how to colorize and highlight syntax, and a prompt refiner that takes a wimpy LLM prompt and creates more elaborate prompt from them.

I took the apps down last week. They were `vibe coded' and therefore approximate and had bugs (but that's to be expected), but they had a security hole where you could hijack the LLM processing with your own prompt turning my app into an open relay using my API key. Last week I discovered that my AI spend on video creation was becoming serious. This is odd because I never create AI video. It turned out that my app was being hijacked by a proxy in Luxembourg and was generating videos on my dime.

So I shut down the apps. I knew they had the potential of being abused, and I was willing to tolerate a small amount of abuse, but it didn't occur to me that syntax highlighter could be hijacked to generate gigabytes of video at my expense. Future applications will be careful to obtain the API key from the user.

How Did I Possibly Break This?

It made no sense. My change to upgrade the Java Virtual Machine caused a number of our builds to stop working. But when I investigated, I found that the builds were failing in tsc, the TypeScript compiler. The TypeScript compiler isn't written Java. Java isn't involved in the tool chain. What was going on?

It turned out that someone pushed an update to a TypeScript library simultaneously (but purely coincidentally) with my Java upgrade. The code was written to use the latest library and our TypeScript compiler was past its prime. It barfed on the new library. Java was not involved in the least. It only looked causal because breakage happened right after I pushed the new image.

A Lot of Packets

A War Story

I once worked for a company that provided mobile data services to public safety organizations: we put PCs in police cars. Our value proposition was that we could connect the PC to the base station using off-the-shelf packet radio on the same frequency as the voice radio. This was attractive to small town police departments that could not afford to install a separate data radio system.

The company was started by a few ham-radio enthusiasts who were trying to leverage their expertise in packet radio to provide a low-cost product to the public safety market. One of the guys had written network code at DEC and wrote the network stack. This was in the days before the web and before TCP/IP was the standard protocol, so he wrote an ad-hoc protocol for the system.

I was called to one on-site installation to solve a vexing problem. The system would work for a while, but then it would hang and need to be completely reset. It only happened when a certain file was being sent. There was nothing unusual about the file, it was a text file.

The way the system worked was, let us say, imaginative. The base station had a command line interface, and the PC in the car would send commands to the base station over packet radio. It would literally type the received command into the base station's prompt. This violated all the best practices for network protocols. It was vulnerable to dropped packets, injection attacks, replay attacks, etc. It had no privacy, no integrity, and no authentication. I was horrified. But it was a working system, so I had to work with it.

After a few hours of debugging, I found that the base station was getting stuck in the packet receive loop. The cause was amusing, if pathetic. The command protocol was sloppy. About half the time, a command would be sent with one or more trailing newlines. The base station dealt with this by stripping trailing newlines, if present from the command before executing it.

The file transfer command would include the length of file in blocks. The length was sent in binary over the ascii channel.

The problem was a file that was 13 blocks long. The command would be sent as file \x0d. But the base station would recognize the \x0d as a trailing newline and strip it. The file command, expecting a length byte, would read off the end of the end of the command and get the null byte. This started the file receive loop which would pre-decrement the unsigned length (to account that first packet had been sent) and ended up with a value of 65535. It then would sit and wait for the next 65535 packets to arrive.

So the system wasn't exactly hung, it was waiting for the rest of the file.

There was no way I was going to try to repair this monstrosity. I suggested that we use a proper network protocol, like TCP/IP, but I pushed this back to the guy that wrote this mess. As a founder of the company, he wasn't about to change the perfectly good protocol that he had authored, so he came up with a workaround.

I didn't last too long at that company. I saw the writing on the wall and moved on.

DES Machine

The MIT CADR Lisp Machine had a number of static RAMs that were used in the processor for various things such as state machines and register files. The core parts of the LMI Lambda Lisp Machine were similar to the CADR (similar enough that they could run the same microcode) but technology had advanced such that the static RAM chips were typically double the size of the CADR's. The LMI Lambda thus had twice as many registers as the CADR, but because there weren't any extra bits in the instruction set, you couldn't address half of them. The extra address bit from the RAM was wired to a status register. So the LMI Lambda had, in effect, two banks of registers which you could swap between by toggling the bit in the status register. This was not normally used — the microcode would set the bit to zero and leave it there.

A friend of mine was interested in security and he had written a high performance version of the encryption algorithm used by Unix to encrypt passwords. He was experimenting with dictionary attacks against passwords and one bottleneck was the performance of the password encryption algorithm.

It occurred to me that I could store the DES S-boxes in the alternate register bank of the LMI Lambda. With some special microcode, I could turn an LMI Lambda into a DES machine that could churn through a dictionary attack at a high speed. I added a special Lisp primitive that would swap the register banks and then run several hundred rounds of the DES algorithm before swapping back and returning to Lisp. Then I wrote a Lisp program that would feed a dictionary into the DES primitives when the processor was idle.

I was able to discover a few passwords this way, but I was more interested in the proof of concept that the actual results. A microcoded DES machine would work, but you'd get better performance out of dedicated hardware.

Bloom Filter

This is the response time of the Google Mini search appliance on several thousand queries. There is an odd spike at 300 ms. A number of machines were taking exactly 300 ms to respond regardless of the query.

I soon tracked this down to the spell server. This is the microservice that puts “Did you mean foobar?” on the top of the page when you spell something wrong. The results page generator will wait up to 300 ms for the spell server to come up with its suggestions and then it will proceed without it. What appeared to be happening is that the spell server was giving a “no go” signal to the page generator at the beginning of page composition. The results page generator would then wait for the spell server to make a suggestion. The spell server would invariably take too long, so after 300 ms, the results page generator would time out and ship the page as is. This happened often enough that it showed up as a blip in the performance graph.

The spell server was based on a Bloom filter. A Bloom filter is a variation on a hash table where you only record that a bucket exists, but not its contents. A Bloom filter will quickly and reliably tell you if an entry is not in the table, but only probabilistically tell you if an entry is in the table. Bloom filters rely on having a good hash function and having a mostly empty hash table. If the hash table is mostly empty, the Bloom filter will usually end up hitting an empty bucket and returning false immediately.

A quick look at the spellserver showed that the Bloom filter was almost always getting a hit, this would send the “no go” signal and trigger a slow lookup to find the misspelled word. The problem was that the Bloom filter was too small. It had too few buckets, so most buckets had an entry. Words would always get a hit in the Bloom filter and so the search appliance thought that all words were misspelled.

I adusted the size of the Bloom filter, giving it several million buckets. Now correctly spelled words would likely hit an empty bucket and the filter would give a “go” signal to the response page generator. Problem solved, and the spike at 300 ms went away.