fovc

Impressive recall, but not novel reasoning

There are basic features we’ve held off on implementing for fear that it will lead to a million little bugs.

The Delta format is the best thing about Quill by far. But I’d advise anyone looking for more than bold/underline/italics to use prose mirror.

Imagine if they weren’t lazy!

My other reaction was that this sounds scary:

> a token with no caveats restricts nothing. It’s a god-mode token. Don’t honor it.

I guess it's technically "fail closed" but seems kind of brittle

But agree that geometry was obviously going to be first. From what I’ve gathered here, it’s not “brute forcing” in terms of relying on algebraic geometry, vectors, or complex number solutions, but it is brute force in that it’s exhaustively looking for “interesting” constructions.

Geometry was always my worst subject, but even so I felt like if given the right construction the problem was much easier. Unfortunately I never developed the intuition to hit on those constructions quickly. It seems this AI doesn’t either, but it can churn through them much faster — There are only so many perpendiculars and parallels and bisectors you can construct which you can more or less mechanically evaluate (map out all angles and ratios, try power of a point, etc.)

While this is incredibly impressive, it seems like Deep Mind:Kasparov::AlphaGeo:Terry Tao in the “engine vs AI” sense.

I agree Algebra is likely next. Like geometry, more often than not you “just” need a clever substitution or 3, of which there are only so many options to choose from.

Some combinatorics problems I think would also be amenable to this search strategy (e.g., finding things to count 2 ways), but that seems like a bridge further away, and only gets you a subset of problems.

Number theory would be my guess for the final frontier before a perfect 42.

Not to split hairs, but that’s just the “unfreed” memory overhead.

If you have 2^n+1 elements, you’ve provisioned 2^(n+1) slots and leaked ~2^(n+1) on top, making the actual overhead there closer to 4x.

I think that means the average overhead is more like 3x (sometimes 4x, sometimes 2x).

I know when using realloc the old buffer is recycled unlike with this arena, but that seems like more of an arena vs. Malloc distinction, no?

In contrast the hash map discussion was more interesting to me because it’s a different data structure that’s explicitly arena friendly

    #include <stdint.h>
    #include <math.h>
    #include <stdbool.h>

    #define BASE_PAGE_BITS 14
    #define MAX_PAGES 22

    struct KeyValue { keytype key; valtype val; bool inUse; };
    uint32_t hash(keytype key);
    int equals(keytype key1, keytype key2);

    struct HashTable {
        struct KeyValue pages[MAX_PAGES][];
        uint8_t usedPages;
    };
    typedef struct HashTable HashTable;

    struct KeyValue* lookup(HashTable* table, keytype key) {
        uint32_t hashed = hash(key);
        uint32_t lowerBits = hashed & ((1 << (BASE_PAGE_BITS + table->usedPages)) - 1);
        uint32_t pageIndex = (lowerBits == 0) ? 0 : (uint32_t)(log2(lowerBits >> BASE_PAGE_BITS) + 1);
        uint32_t entryIndex;
        
        for (;;) {
            uint32_t entryIndexRange = (pageIndex == 0) ? (1 << BASE_PAGE_BITS) : (1 << (pageIndex + BASE_PAGE_BITS - 1));
            
            for (; entryIndex < entryIndexRange; entryIndex++) {
                struct KeyValue* page = table->pages[pageIndex];
                if (!page[entryIndex].inUse) return &page[entryIndex];
                if (equals(page[entryIndex].key, key)) return &page[entryIndex];
            }
            
            pageIndex = (pageIndex + 1) % table->usedPages;
            entryIndex = 0;
        }
    }

The original series of articles had me thinking about how to implement the normal hash table without leaking. I think it’s possible:

First consider a hash table using linear probing with a dedicated arena (restriction will be lifted later). That means memory can grow for free. However, resizing is still tricky because we need to rehash in place while ensuring we don’t “strand” any entries. This can be accomplished by iterating through the hash table entries in order, but starting at an empty entry and looping around. (Proof left as an exercise for the reader)

So now we have a hash table that can use realloc to grow. How to generalize for arenas? The key is that the HT will maintain a page map of sorts. The first page is of size M, the second is of size M, and thereafter they’ll be of size 2^n * M. Basically on each resize we double the total capacity by adding a new page. Since the pages are of variable width, though, how to map indexes to pages quickly? The key is to use ffs or ctz to get a rounded log2.

> A natural monopoly is a monopoly in an industry in which high infrastructural costs and other barriers to entry relative to the size of the market give the largest supplier in an industry, often the first supplier in a market, an overwhelming advantage over potential competitors. Specifically, an industry is a natural monopoly if the total cost of one firm, producing the total output, is lower than the total cost of two or more firms producing the entire production.

In theory pricing/output in economics is always “quality adjusted” (which is one of the hard things in inflation series)

Yes, traditionally a natural monopoly is one where if you split them, costs go up. With Google, GP is saying if you split them up quality goes down. Either way there’s “consumer harm”. (I guess very directly if the time to search goes up, the economic price of using Google goes up too)

Does anyone know if there’s an RSS feed?

Because I usually don’t own those books and don’t have a university library

> Often there are papers like '[topic] simplified' etc, and they can be quite useful.

Yes! This is adding heuristics on top of the basic algorithm, of which there are many useful ones. (Figure out who the field luminaries are, what the best journals/conferences were, etc.)

1. Pick a paper in the field ~at random.

1b. If it’s basic enough for you, you’re done

2. Read the first few paragraphs and find the most basic statement that is cited

3. Find the cited paper

4. Go back to step 1b

Occasionally you’ll hit a book as the citation, in which case you must backtrack to take a different branch of the tree and try again.

In theory this is worst-case exponential, but in practice most searches end quickly

(Excuse the pun)

> TRUNCATE is not MVCC-safe. After truncation, the table will appear empty to concurrent transactions, if they are using a snapshot taken before the truncation occurred. See Section 13.6 for more details.

> TRUNCATE is transaction-safe with respect to the data in the tables: the truncation will be safely rolled back if the surrounding transaction does not commit.

I’m often worrying about locks in migrations that could be long running, so executing the query to figure out the locks defeats the purpose. Or at least I need to know to use a test DB.

Dead easy to run and no long-held locks