LuaJIT Strange & Unpredictable Behavior in table.sort

A quick story about discovering where Lua’s table abstraction fails to work.

In Lua, arrays should always be initialized sequentially, and should never have a nil inserted.

(The code behind this adventure starts on line 128 in one commit, where a crazy work-around was used to get what I wanted. This was eventually fixed in commit 8b8f36b (though accidentally sorting the wrong direction at that point). I provide these links to remind myself what happened, and so that if someone more knowledgeable than me wants to figure this out, hopefully they can. I’ve also made sure those links have been archived by the Internet Archive so they remain available even if the project is gone.)

While working on a prototype, I needed to sort a list of integers so that I could count the sum of the top thousand items in an array of ~40 thousand items. This list had empty indexes (or holes) within it, so I wrote a for loop to fill them with zeros and then called table.sort. It errored from trying to compare with a nil. This was confusing because I had a well-defined length that was used to fill holes, and the way Lua works, any hole in the list should be the end of what Lua recognizes as a list. As far as I knew, standard functions don’t allow holes in lists by ending at the first hole encountered.

for i = 0, list_length do
  if not list[i] then
    list[i] = 0

I was further confused when I added debug code to check the list for nil values by iterating over it and printing every value in it: No nil values existed. The strangest part was when I passed my own sorting function to table.sort specifically to handle nil values and it created the same error. I worked around this by brute-forcing it with an incredibly inefficient thousand traversals of the entire list, removing items as I found the maximum each time. It’s a prototype, so whatever.

It didn’t sit right with me, especially because I couldn’t figure out how this was occurring. It’s incredibly rare to find an actual bug in highly used production software like programming languages, so I doubted I’d found an actual problem. Later, I realized I had added a zeroth element to this list, and Lua starts counting at 1, unlike a lot of programming languages. Removing this changed nothing, so I double-checked my assumptions and found that now nil values were showing up – and this is after no code changes except adding a for loop to print values.

I wrote a new sorting function that checks more thoroughly for nil values (I think the previous attempts at that failed because I’d made some simple error in how I was thinking about it). It worked. But then I found the loop whose code I’ve shared above, where holes are filled with zeroes. It had been a while, so I was very surprised to find what should have fixed things right there doing nothing.. somehow. I mentioned this in a group chat, and someone suggested replacing list_length with #list (the # operator returns length). The problem is that Lua stops counting at the first nil, so that should do nothing.

There’s also the possibility of an off-by-one error, those are very common, but I had assumed this would happen at some point and made sure all of my functions and loops checked one element earlier than necessary and one element later, so that if I checked too much – just extra zeroes, but I couldn’t check too little.

I wasn’t satisfied by all the nil values being there after a loop that replaces them with zero, so I tried making a loop at the top of the code that prefills a much longer list than I actually needed with zeroes. Suddenly, I didn’t need a custom sorting function. So why does filling the list with zeroes work in one place, but not another?

How Objects Work in Lua

In Lua all objects are called tables, and can contain an array-like section and arbitrary key-value pairs in a hashmap. It doesn’t really distinguish between these except as an optimization, under the hood it tries to guess how you intend to use the object and assigns values internally differently depending on what index you’re using. I thought that in practice, this means integer indexes are handled like arrays, and non-integer indexes are in the hashmap. I thought that maybe because my code was selecting integer indexes in a completely random order, it treated these as a hashmap instead, somehow leading to ignoring attempting to fill the holes – because there weren’t any holes, or the holes persisted because only part of the indexes were treated as an array.

Lua’s tables are an abstraction meant to make writing code easier, and for my years of working with them, they do that quite well, but maybe this is where the abstraction leaks? (All abstractions leak: They have some condition(s) where you end up needing to know how they work underneath, even though the point of abstraction is to not need to know how it works underneath.) Perhaps arrays are only recognized when they’re initialized sequentially, whereas my code initialized them in a random order? Either way, the error I started with manifests as “An array of integers can’t be sorted because part of it is undefined – even though every element is defined when iterated over.” which is not supposed to be possible.

There’s also the detail that in Lua there is not supposed to be difference between something having a nil value and it not existing at all. There is a difference, but it should be impossible to tell the difference or for the difference to matter in your code. It is possible that this alone is why I had this problem. Changing a value to nil inside an array table can cause all values within it to be converted to a hashmap, or some of them, or none of them. Again, this shouldn’t matter (other than a difference in speed which is usually unnoticeable), but it might matter.

I wrote a minimum test case to see if my hunch was correct, but it works when I expect it not to. I’m lost. I have an explanation that informs how I should code so that it works – and it does work, but because that explanation fails when tested, it seems incorrect. I want to know what’s really going on, but it requires a depth of understanding that I lack, and effort that I do not have the time and energy to go into.

I also learned that Lua defines this kind of behavior as “strange and unpredictable behavior” instead of undefined behavior, because undefined behavior means that an entire program can fail to function correctly do to one element with undefined behavior (even when that element is not accessed), whereas in Lua, a table exhibiting strange and unpredictable behavior doesn’t affect the rest of the program. So, if you can work around it, it’s okay.

At this point, I’m happy enough telling myself that arrays should always be initialized sequentially, and shouldn’t have nil elements ever. If I follow that, I probably won’t run into this. But.. if you’re reading this and understand what’s really going on here, please tell me.

YouTube Censorship Made Me Write a Script

YouTube’s been forcing creators to censor their works more and more, and often times after a successful publish of said content. More history and valuable information is being lost every day because a corporation controls the largest source of video content freely available.

At the same time, I’ve been running commands using yt-dlp over and over again for my own purposes, aside from this censorship. The syntax is relatively easy to forget despite being very clearly defined, so I finally made a script to handle it for me.

It’s in Lua because that’s what I prefer to use, and available on GitHub’s gists. Because it is based on yt-dlp, it works for any website supported by yt-dlp. Here’s how to use it:

  ./video-dl.lua [action] <url>
[action]: What is desired.
  video (default): Highest quality video (maximum 720p).
  backup, clone, copy: English subtitles (including automatic subtitles), thumbnail, description, highest quality video (maximum 720p).
  music, audio: Highest quality audio only.
  metadata, meta: English subtitles (including automatic subtitles), thumbnail, description.
<url>: Source. YouTube URL expected, but should work with anything yt-dlp works with.

Information wants to be free. Help it.

Generating Terrestrial Planets Pt.1

This is related to Semi-Empirical Stellar Equations. I have had some questions easily answered, and others which are difficult or impossible to get the kind of accuracy I want.

I’m going to order what I’ve learned by the order I am planning to use these equations, marking equations loosely based on empirical data with an asterisk, and double asterisks for things I’ve completely made up to simplify calculation.

  • Radius of Surface* (Rsurface):
    5500km mean, 1550km standard deviation
  • Density* [based on common rock types] (Dplanet):
    4.7g/cm3 mean, 0.55g/cm3 standard deviation
  • Volume [assumes a perfect sphere] (Vplanet):
    4/3 * π * Rsurface3
  • Mass (Mplanet):
    Dplanet * Vplanet
  • Surface Gravity (gsurface):
    6.673×10-11Nm2kg-2 * Mplanet / Rsurface2
  • Surface Area [assumes a perfect sphere]:
    4 * π * Rsurface2
  • Atmospheric Pressure Reduction Rate** (Pr):
    Pr [unit: none] = -0.00011701572 [unit: s2 / m2] * gsurface
  • Atmospheric Halving Height** (hd):
    hd [unit: m-1] = ln(2) / Pr
  • Atmospheric Volume at Constant Pressure** (Vsim):
    (4/3 * π * (Rsurface + hd)3 – Vplanet) * 2
  • Surface Atmospheric Pressure (Psurface):
    Psurface [unit: kPa] = ???
  • Lowest Safe Orbital Height** (h0):
    h0 [unit: m] = ln(1.4×10-11 / Psurface) / Pr
  • True Atmospheric Volume (Vatm):
    4/3 * π * (Rsurface + h0)3 – Vplanet

Vsim exists to support a simulation of an entire planet’s atmospheric contents using my simple fluid simulation mechanic. The magic constant used to calculated Pr is based on Earth’s atmosphere, it can be changed to set an exact “atmospheric height” while maintaining other properties of this simulation.

  • Atmospheric Pressure at Altitude** (Paltitude):
    Paltitude [unit: kPa] = Psurface * exp(Pr * maltitude) [Pr may be -Pr, I don’t remember]

This post is obviously incomplete, but it’s been a while since I posted anything here, and I felt like I should go ahead and share what I’ve been up to.

Semi-Empirical Stellar Equations

I’ve spent a lot of time trying to answer certain questions in astronomy, where I just want a rough approximation for the purpose of a simulation, and don’t need an exact answer. These are some of the equations I’ve come up with.

Yerkes Classes’ T/Mv Relations

These equations are shown as functions where x is temperature in Kelvin, and f(x) is absolute magnitude (visual). Most are valid from 2400 K to a little bit past 30000 K, the exceptions are noted. For the hypergiants and white dwarfs, the range is within an elliptical region, of which these functions define the major axis; for all others, they are a trend line along a Yerkes classification.

  • Hypergiants (0):
    f(x) = -8.9
  • Supergiants (Ia):
    f(x) = -0.00135x3 + 0.0233x2 + 0.0187x – 7.349
  • Supergiants (Ib):
    f(x) = 0.00329x3 – 0.0962x2 + 0.829x – 7.209
  • Bright Giants (II):
    f(x) = 0.00557x3 – 0.166x2 + 1.505x – 6.816
  • Giants (III):
    f(x) = 0.0135x3 – 0.373x2 + 3.019x – 7.233
  • Subgiants (IV):
    f(x) = -0.151x2 + 2.216x – 5.128 (4450-100000 K only)
  • Dwarfs (V):
    f(x) = 0.00193x5 – 0.0615x4 + 0.742x3 – 4.257x2 + 12.439x – 12.996 (note: this one is the least accurate)
  • Subdwarfs (VI):
    f(x) = 0.131x3 – 3.275x2 + 27.576x – 71.7 (3050-6000 K only)
  • White Dwarfs (VII):
    f(x) = 0.489x + 10.01 (4450-30000 K only)

Simple Conversions

  • Absolute Magnitude (visual) → Luminosity (solar luminosities):
    Lsun = 100 * exp(-0.944 * Mv)
    Accurate between 0-10 Mv. Probably continues accuracy relatively well.
  • Main Sequence Luminosity / Mass Relation:
    Lstar / Lsun = (Mstar / Msun)3.5
    Lstar = ( 3.68 * ln(Mstar) – 0.244 )e
    (The second equation applies to all stars.)
  • Mass / Lifetime Relation:
    Tyears = ( 23.4 – 2.68 * ln(Mstar) )e
    (This applies to all stars.)

Spectral filters are used to help classify stars. Ultraviolet, Blue, Visual, Red, and Infrared. Objects are listed in different indexes:

  • UV for the hottest objects (stellar remnants, galaxies)
  • BV (the majority of stars)
  • RI for the coolest (LTY “stars” and below)

Equations I no longer recommend

Provided for completeness, in case they are found to be useful.

  • Temperature (K) → Absolute Magnitude (visual):
    Mv = 35.463 * exp(-0.000353 * T)
    Roughly accurate between 2000-50000 Kelvin. Probably doesn’t continue accuracy at hotter temperatures. Previously this was at the top of this post, now I am not sure why (perhaps the simplicity). The Yerkes’ classifications are a better system.
  • B-V index (x) → Temperature (K):
    T = -772.2x3 + 3152x2 – 6893x + 9500
    Sorta accurate between 0-2. (This equation I am least comfortable with, and don’t plan to use.)

cc-pkg: A ComputerCraft Package Manager

(The latest information and a quick reference is located here.)

ComputerCraft is a Minecraft mod that adds Lua-based computers. Over time, many programs have been created, and several package managers have come and gone. As I write this, all that I have seen are gone – their original authors have moved on, and shut down the servers hosting packages.

Now it’s my turn to sell you a package manager. Unlike the others, I expect this to remain viable – even if I’m gone from the picture. If you want to skip to trying it, here’s how it’s installed (and how to ask for help):

pastebin get 9Li3u4Rc /bin/pkg
/bin/pkg help

(I’d also recommend installing the unix-like package, which adds /bin to your path, along with a few other small tweaks.)

Why is cc-pkg different?

  1. It is built on ComputerCraft’s pastebin integration.
  2. It does not require a maintainer.
  3. It is extremely simple – and flexible.

cc-pkg has the same three sub-commands of the default pastebin program: get, run, and put*. They each do exactly what you’d expect them to do, except they can use names as well as pastebin IDs. Names consist of alphanumeric characters and dashes, and there are two file types cc-pkg can recognize and utilize:

Both are plaintext lists of the form key=value. The first is called a package and has file paths (all starting with a forward slash) as keys, with names or pastebin IDs as values. This is how cc-pkg knows which files to download and where to put them. The second type is called a list, and contains names as keys, with names or pastebin IDs as values. Lists are saved to a local file cc-pkg uses to resolve package names – overwriting any existing entries with the same package name, which is how updating is done.

With just those core features, I think the system is viable.

*The put command is not implemented as of version 1.4.2 1.5.10, the latest at the time of writing finishing updating this introduction.

Command Extensions

On top of this, if a file is saved to /lib/pkg-commands/<name> and a user runs pkg <name>, that file will be run with the other arguments. This allows adding new functions, and overwriting the core functions to add additional features, if desired.

Under the Hood

cc-pkg keeps metadata through the following files:

  • /etc/pkg/names.list: The master names list. (How cc-pkg knows what to download.)
  • /etc/pkg/ids.list: Download history of cc-pkg. (An ordered list of every pastebin ID successfully downloaded.)
  • /etc/pkg/<package-name>: Each package is saved here by name, in addition to the files it specifies.

API Loadable

It uses global functions so that it can be loaded as an API to make a more advanced package management system on top of it – or just to make programs automatically download requirements using cc-pkg.

  • get(name_or_id, path): The core function that installs anything (package/list/file). (path is optional.)
  • down(id): Downloads from a pastebin ID, returning its content or throwing an error.
  • save(path, data): Write to file. (Note: This is not a binary write.)
  • append(path, data): Append to file. (Note: This is not a binary write.)
  • id(name_or_id): Recursively checks the master names list until a pastebin ID is returned. (Note: On failure, returns the last name resolved.)
  • type(data): Recognizes data as a package, list, or unknown type, and returns that type.
  • src(data): Combines this data with existing names (overwriting if duplicates exist). (If get is used, src will be called when needed automatically.)

An example of this is the pkg-search package, which adds a search command to look for specific package names within the master list.

Example Packages & Lists

  • A basic package looks like this:
    This is the multi-startup package, which makes the computer run all files in /.startup when started. It is required for several of my packages to function.
  • A package with a dependency looks like this:

    This is the unix-like package, which requires multi-startup to function, and makes the computer operate more like a UNIX computer. (Due to how cc-pkg works, specifying to download a package anywhere will install that package. By convention and for consistency, I use the location cc-pkg installs packages by default.)
  • A “meta package” (a package that only lists dependencies) looks like this:

    This is only part of the unix-meta package, which lists many packages that make a computer operate more like a UNIX computer. Packages are very flexible! They don’t even have to install anything themselves.
  • A list looks like this:

    This is the current list of pocket packages at the time of writing. (These can be added by running pkg get pocket-packages.) Remember, lists can reference other names (e.g. unix-stuff=unix-meta), allowing one to create aliases for existing packages & lists.