bugfix-66

No, I mean https://www.amazon.com/Art-Computer-Programming-Combinatoria...

You don't test on the training set.

Everybody in ML (e.g., me) knows that.

But that's what we're seeing.

I'm saying: "Here's a test outside the training set."

That's right. There was no snark intended.

I seriously doubt this appeals to the modern Hacker News crowd, but it might appeal to a couple of you:

Published in October 2022, The Art of Computer Programming: Volume 4B is dazzling. It's like a guide to expressing (in non-obvious ways) all kinds of problems as some variation on Exact Cover (or Boolean Satisfiability) and using wicked tight little general-purpose backtracking solvers to solve them.

If you want a peek, watch Knuth's 2018 lecture on Dancing Links Exact Cover:

https://youtu.be/_cR9zDlvP88

The training set is full of code for these problems.

Put your query into Google and see how many thousands of answers appear.

Your tests are in the training set.

Look at how many times that program appears when you paste your question into Google.

The language model was trained on it.

Named after the two companies that promoted it.

It was trained on numerous Leetcode solutions (question/answer), which you can find on GitHub. People are proud of their Leetcode efforts: they post their solutions, as if it is an achievement.

Now tell me, how many of the BUGFIX-66 problems can it solve?

https://BUGFIX-66.com

Copilot can solve a few of the simple ones at the beginning (simple matrix multiplication, simple radix sort, etc., that appear often in the training data, and some of the harder ones whose solution appears on GitHub, e.g., the uncorrected prediction/correction compressor/decompressor whose solutions were front-page on Hacker News).

But as you go down the list, into material outside the training set, the language model won't be able to solve it.

Try it. Paste the tile, the introductory text, and the unfixed code, and see whether the omnipotent AI can solve these (quite straightforward) problems. For how many does it need the hint?

Radix sort is also very simple, e.g., https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff054...

And djb's vectorized sorting networks are pretty great: https://sorting.cr.yp.to/

Now do it for an algorithm+explanation the training set doesn't contain a million copies of, please.

For example, substitute "The Burrows-Wheeler Inverse Transform" for "bubble sort".

Look at Section 8 and Section 9 here:

http://tug.ctan.org/info/tex-nutshell/tex-nutshell.pdf

How is ChatGPT's answer wrong? The regex is matching square brackets instead of the correct OPTIONAL curly braces. Unseparated arguments aren't handled. The regex for the id is also wrong. The leading slash is correct, but other than that, the whole fucking thing is wrong!

And of course it can't handle macro calls within the macro arguments (nesting).

It's just an absolute clusterfuck, from top to bottom. The chatbot gave its user a useless piece of garbage, and Hacker News doesn't know enough to throw it away. Instead, we parade it around like some great success!

Fooled by a language model.

A different kind of programming puzzle: https://BUGFIX-66.com

The idea is that you read and understand a small piece of code (full of useful techniques) and make a small change to demonstrate understanding.

Games that require you to write the code are limited to rehashing the same old tired algorithms... reverse a string and other sequence techniques, edit distance and dp variants, optimization by binary search and evaluation, etc., the standard leetcode stuff. Basically, useless wankery you will never use. The competitive programming standards.

If you don't have to write it, just understand it, the game can cover some very interesting new algorithmic terrain. It becomes part book, part game. Like Hacker's Delight: The Game.

Similarly, you can turn off bounds-checking in Go like this:

  go build -gcflags=-B

Do your own test, and keep the results in mind next time somebody on Hacker News dismisses Go because of the "overwhelming cost of bounds checking".

43 days ago I asked this question:

https://news.ycombinator.com/item?id=33215740

This question got voted down everywhere I discussed it on Hacker News, but somehow the submission itself got 11 points. Apparently, it is an offensive question to some silent, pro-censorship part of the population here. Today I'll ask it again, and I hope somebody will respond in a useful way:

QUESTION:

I write software for parallel processors at a hardware/software company you've heard of. I am located in California but many of my coworkers are located in China (roughly half the team).

We are directly affected by the American government's severe new CPU/GPU export restrictions.

It seems to me that America is preparing for a period of cold war, or worse.

It's time to start thinking about contributing to the American war effort by writing high-performance military computing systems.

For example, SIMD particle filters for hypersonic weapons, or low-latency convolutional neural networks for battlefield devices.

So, Hacker News: What company is the best place to do this work? What team?

Does anyone here already work in this field?

It's just a fixed point instruction.

Fixed point multiply: a*m times b*m yields (a*b)*m = a*m * b*m / m

In the above, m is the fixed point 1. For example, 65536 for a 16.16 fixed point.

The instruction allows you to multiply a*m by b*m and then divide by m, renormalizing your fixed point result.

Chuck Moore thinks nobody needs floating point because fixed point is sufficient!

Look at the Green Arrays F18, the "conclusion" that Forth reached:

https://www.greenarraychips.com/home/documents/greg/PB003-11...

Here's a clear description of what each instruction does:

https://colorforth.github.io/forth.html

Hilariously, the system has no logical OR, only AND and XOR and NOT, because "Inclusive-or is rarely needed."

This system was designed by Chuck Moore, father of Forth. Here is an entertaining video of him explaining the F18A stack machine and programming system:

https://youtu.be/0PclgBd6_Zs

This is such a simple machine. I am planning to make a tiny emulator for my site. One could probably write an emulator in 80 lines of Go (one goroutine for each of the 144 cores).

This is based on Russ Cox's essay:

https://research.swtch.com/gorace

The code in Russ Cox's article does not race with the modern Go compiler.

But it's simple to fix that. Given arbitrary memory access within a Go process under Linux, can you see how to terminate the process and return 0 to the system?

Like calling os.Exit(0) when package os is unavailable.

This is based on Russ Cox's essay:

https://research.swtch.com/gorace

But, the code in Russ Cox's article does not race with the modern Go compiler.

A really tremendous varint/VLQ encoder (using a zig-zag encoding and an generalized base):

https://bugfix-66.com/2c1df73cab89ec76d6fa10caf8a27c1fbe4d16...

and the decoder:

https://bugfix-66.com/1efa93a5eb0cc12b3de7cd1dab8e471a2cc95e...

The common varint, which you see in applications everywhere (e.g., git), is just base-128 version of the above general scheme!

But base-32 or base-8 or base-64 varints can be a big win for some purposes. Remove the zig-zag encoding if negative integers don't occur.

A more challenging code puzzle game: https://BUGFIX-66.com

I have a different Hacker News account for every one of my projects. It happens that the No-AI 3-Clause License became part of the BUGFIX-66 project. I'm sorry that upsets you, but I'm sure you'll get over it. Happy Thanksgiving.

A necessary evil. You point out a cost. The benefits outweigh that cost.

Thank you. I see the Humans Only Clause is much more explicit about what is prohibited than the No-AI 3-Clause License, and furthermore directly states a licensing fee.

I'm presenting the license text in a creative and unusual way that real hackers might enjoy.

If that confused you, or you consider it "obnoxious", then you are not the target audience.

That's ok. Hacker News is not 100% hackers!

Thank you. Could you paste the Humans Only Clause here so we can read it?

Here was my attempt to write a clause prohibiting language model training/inference:

https://bugfix-66.com/7a82559a13b39c7fa404320c14f47ce0c304fa...

  3. Use in source or binary form for the construction or operation
     of predictive software generation systems is prohibited.

The Humans Only Clause adds an explicit licensing fee, and what else?

How is the clause worded?

Being able to read and understand x86-64 assembly (or PTX/SASS for an Nvidia GPU) is much more important than being able to write it. In practice, even when you're writing assembly, you're looking at reference assembly generated by a compiler from C code you wrote.

Similarly, the reality is that as a professional programmer you spend no time doing work like leetcode.

Instead, you spend a lot of time understanding and slightly modifying (fixing or enhancing/extending) code.

With the rise of language model code completion systems (e.g., Microsoft Copilot) even more time will be spent inspecting and understanding code to find problems.

With these facts in mind, I have been building a new form of leetcode:

https://BUGFIX-66.com

Most puzzles are interesting algorithms that you will learn useful techniques from, so it's never a waste of time to think about them. And even though the bugs are all quite trivial, I can see it's very challenging for many people.

It's about half-way ready to launch, needing 30 more puzzles. I am working my way through Knuth's The Art of Programming Volume 4B and today I'll see if Algorithm X (Dancing Links Exact Cover Backtracking) can be made to fit for Bugs 38 and 39 (or whether it's too complicated).

This is a "broadword matrix multiplication" as described in Knuth's The Art of Computer Programming Volume 4A (exercise 55 in section 7.1.3).

Here is a lecture where Knuth explains it:

https://youtu.be/o22BAuQj3ds?t=1h20s

It's efficient for 64-bit registers, but even larger registers could be used in the same way.

There are also interesting computational possibilities, like the broadword matrix multiplication algorithm that Knuth presents in The Art of Computer Programming Volume 4A:

https://bugfix-66.com/2d447332bf8f8c67348d520c6508b2cc7d3204...

The basic idea is that "smart memories" can be used to do make the multiplication very local and parallel.

The above code spreads matrices out within 64-bit registers, but you could generalize this to huge, multi-megabyte registers.

Explained by Don Knuth here, if you can't solve it yourself:

https://youtu.be/o22BAuQj3ds?t=37m40s

So, specifically what's wrong? It looks no-nonsense and to-the-point.

Were you unable to find the information you wanted?

Was the site confusing?

Or it was just aesthetically unpleasant?