Money circulates but resources do not. A human hour spent constructing a data center can’t then be used to build an apartment building.
3,509 karma · joined August 13, 2016
website: https://tylerhou.com
github: https://github.com/tylerhouThe runtime of WCOJs algorithms are even more dependent on good cardinality estimation. For instance, in VAAT, the main difficulty to find an appropriate variable ordering, which relies on knowledge about cardinalities conditioned on particular variables having particular values. If you have the wrong ordering, you still achieve worst case optimal, but you could have done far better in some cases with other algorithms (e.g. Yannakakis algorithm for acyclic queries). And as far as I know, many DBMSes do not keep track of this type of conditional cardinality, so it is unlikely that existing WCOJ will be faster in practice.
The new hotness is "instance optimal" joins...
Sorry for the possibly naive question. If I need to call a synchronous function from an async function, why can't I just call await on the async argument?
def foo(bar: str, baz: int):
# some synchronous work
pass
async def other(bar: Awaitable[str]):
foo(await bar, 0)An operating system (or sandbox, or whatever) is a very large virtual machine, where the "instructions" are the normal CPU instructions plus the set of syscalls. Unfortunately, operating systems today are complicated, hard to understand, and (relatively) hard to modify. For example, there are many different ways to sandbox file system access (chmod, containers, chroot, sandbox-exec on macOS etc.) and they each have bugs that have turned into "features" or subtle semantics. Plus, they are not available on all operating systems or even on all distributions of the same operating system. And then -- how do filesystem permissions and network permissions interact? Even of both of their semantics are "safe," is the composition of the two safe?
The assumption is: because operating systems are so complex, large, and underspecified, it probably is dangerous for LLMs to interact directly with the underlying operating system. We have observed this empirically: through CVEs in C and C++ code, we know that subtle errors or small differences in semantics can cascade into huge security vulnerabilities.
To address this, the authors propose that LLMs instead interact with a virtual machine where, for example, the semantics of permissions and/or capabilities is well-defined and standardized across different implementations or operating systems. (This is why they mention Java as an analogy -- the JVM gave developers the ability to write code for a vast array of architectures and operating systems without having to think about the underlying implementations.) This standardization makes it easier to understand how exactly an LLM would be allowed to interact with the outside world.
Besides semantic understanding and clarity, there are more benefits to designing a new virtual machine.
- Standardization across multiple model providers (mentioned).
- Better RLHF / constrained generation opportunity than general Bash output.
- Can incorporate advances in programming language theory and design.
For an example of the last point, in recent years, there has been a ton of research on information flow for security and privacy (mentioned in the article). In a programming language that is aware of information flow, I can mark my bank account password as "secret" and the input to all HTTP calls as "public." The type system or some other static analysis can verify that my password cannot possibly affect the input to any HTTP call. This is harder than you think because it depends on control flow! For example, the following program indirectly exfiltrates information about my password:
if (password.startsWith("hackernews")) {
fetch("https://example.com/a");
} else {
fetch("https://example.com/b");
}
AFAIK, IQ tests used in psychological evaluations do not contain any randomness so exact answers are almost always in distribution. I haven't seen someone compare AI to an IQ test that is not in distribution.
On ARC-AGI, which is mildly similar to a randomly generated IQ test, humans still are much better than LLMs. https://arcprize.org/ (scroll down for chart)
It is misleading to say that IVM reduces the cost of view updates from O(n) to O(1). While that is not technically incorrect, for any nontrivial query (e.g anything with an index join) the cost of a view update will be smaller than the original query but not constant time.
Also, the tone of “newfangled” was not dismissive in the context of an article praising IVM. At worst, it was sarcastic; I interpreted it as teasing.
I do research related to IVM / DBSP.
Taking ibuprofen (or other NSAIDs) long-term can wear away the stomach lining, causing ulcers. Acetaminophen is generally better tolerated to manage mild long-term pain than NSAIDs, as long as you don't overdose / take with alcohol.
Before I knew about CPS and defunctionalization, I wrote a Python decorator that did exactly the transformation you describe. https://github.com/tylerhou/fiber. Now I know about CPS and defunctionalization, I realize that my work was not the best implementation (but it was a fun learning experience!).
It is true that every tail recursive function can be converted into a semantically equivalent loop via a transformation like CPS (which the author mentions). However, for mutually tail-recursive functions, this conversion loses control flow information. This is because after the CPS transformation, calls to the other function become calls to a continuation; this call usually must be implemented as an indirect jump. On the other hand, mutually tail-recursive functions can call each other with direct/statically-known jumps.
This loss of information might appear trivial, but in practice it has some important consequences. Classic examples are interpreter loops. It is well-known that computed gotos can result in modest to large speedups for interpreters [1]. The reason why is that computed gotos create an indirect jump per opcode, so a branch predictor can take advantage of correlations between opcodes. For example, looking at Python disassembly, the header of a standard range for loop compiles down to three opcodes: GET_ITER, FOR_ITER, STORE_FAST in sequence [2]. A branch predictor can recognize that the target of the "FOR_ITER" indirect jump will likely be the "STORE_FAST" instruction pointer; it cannot predict this in the naive implementation where jumps for all instructions are "merged" into a single indirect jump / switch at the top of the loop body. In this case, computed goto is effectively equivalent to a CPS transformation whose closures require no storage on the heap.
Suppose, however, we know even more information about the instruction sequence; for example, we know ahead of time that every FOR_ITER opcode will be followed by a STORE_FAST opcode. We could completely replace the indirect jump with a direct jump to the instruction pointer for the STORE_FAST opcode. Because modern branch predictors are very good, this will have about the same performance in practice as the computed goto loop.
However, consider the limiting case where we know the entire instruction sequence beforehand. If we write our interpreter as many mutually tail-recursive functions, with one function for every instruction, an optimizing compiler can replace every indirect call with a direct (tail-recursive) call to the function that implements the next instruction's opcode. With a good enough optimizer / partial evaluator, you can turn an interpreter into a compiler! This is known as the first Futamura projection [3].
To see an example of this in action, I wrote a prototype of a Brainfuck compiler via the Futamura projection; it uses LLVM as a partial evaluator [4]. The main interesting function is `interpret`, which is templated on the program counter / instruction. That is, `interpret` is really a family of mutually tail-recursive functions which statically call each other as described above. For short Brainfuck programs, the LLVM optimizer is able to statically compute the output of the Brainfuck program. (The one in the Godbolt link compiles to a loop, likely because LLVM does not want to unroll the mutual recursion too much.) You can play around with different Brainfuck programs by modifying the `program` string on line 5.
[1] https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e...
[2] https://godbolt.org/z/rdhMvPo36
[3] https://en.wikipedia.org/wiki/Partial_evaluation#Futamura_pr...
This would prevent the last bug (!ua()) as the control flow sensitive analysis can reason about both branches: that it is invalid to deref ua within the block. The dynamic check misses the bug because the branch is never taken for the given inputs.
I am fairly confident that the clang-tidy pass is simpler and more precise in most cases than the hand-rolled implementation. (That said the static check may not be able to reason about mutation well.)
If you need to pass an error in the failure case, you can use std::expected (available in C++23). clang-tidy has an open bug about supporting a similar check for std::expected: https://github.com/llvm/llvm-project/issues/135045
The main thing I want to add is that using IQ to quantify intelligence at the top end of the scale is scientifically bogus and in my opinion harmful because it validates depressed / insecure / chronically online people who use their "160 IQ" as a way to put down other people or to peddle pseudo-scientific nonsense. Those people often need genuine psychiatric help and (in my opinion) such validation only harms them.
I'm sure that Hal Finney was exceptionally smart, though. :)
This is because standard IQ tests are generally designed to measure around the median of the distribution (70-130), and so there is a lot of variance in measurement at the top end. If you happen to have a bad testing day and you make a dumb mistake, your measured IQ might drop by a fairly large number of points -- or, conversely, if you got lucky and guessed right, your measured IQ could be much higher than reality.
For example, the original Raven's Progressive Matrices says [2; page 71]
> For reason's already given, Progressive Matrices (1938) does not differentiate, very clearly between young-children, or between adults of superior intellectual capacity.
where "superior intellectual capacity" is defined as an IQ of ~125 or higher, and (if I am interpreting it correctly), the table on page 79 of [2] says missing a single question could drop a 20-year old from scoring 95 percentile to scoring 90 percentile. That's 5 IQ points on a single question! If you had a bad day, or didn't get enough sleep, you could test significantly worse than your actual "IQ."
Anyone that actually has an IQ of 160 with even a modicum of self awareness should understand that the IQ test they took is inherently noisy at the top end of the scale because sometimes people have off days.
[1] https://en.wikipedia.org/wiki/IQ_classification#IQ_classific...
[2] https://rehabilitationpsychologist.org/resources/SPM%20with%...
Second, I would be surprised if the static analyses in the tool are precise enough for real-world Zig programs. For example, it is undecidable to determine whether a function “takes ownership” of an argument pointer. In particular, if you want to avoid false negatives, the “free after transfer” case needs to be conservative, but then you almost certainly will flag false positives.
But that's not what is happening. The only thing that the optimizer does is unrolls the loop that advances the state. Otherwise, the sequence of instructions is standard: two loads and some pointer arithmetic. There is no finely tuned algorithm. https://godbolt.org/z/fqdb5bssc
> But if you use an actual regex the way people actually use them, using either the one provided by their standard library or one that is readily available then regex is pretty slow.
Yes, most regex implementations are not designed to be efficient, they are designed for ergonomics (including supporting exponential-time features like lookaround). (Both boost::regex and PCRE2 support exponential-time features; std::regex is just not optimized at all.) This is well-known. https://swtch.com/~rsc/regexp/regexp1.html. That's why I said "well-optimized regex." Most regexes, in practice, are not well-optimized!
Maybe this is a semantic distinction between what you and I consider a "regex." I interpreted "regex" as how people in CS theory understand it; i.e., a finite automata that decides whether a string is in a given language. I think that's perfectly reasonable here, as the given problem is finding the fastest algorithm that decides whether a string is in the language generated by ASCII characters without the vowels. I think it's reasonable for me to use a (not hand-optimized) implementation that obeys that definition in my comparison.
It's not hard to explain the problem, as most math undergraduates will have taken some group theory course. But even "subgroup" means nothing to most computer scientists (speaking from personal experience interacting with computer scientist academics).
The original commenter called `find()` once per vowel, so that's why I benchmarked the regex against the less-idiomatic code.
The interchanged version (loop over haystack outside, over vowels inside) is (mildly) faster than all the regex versions except for short strings & no vowels.
One thing to note is that all the loop versions are not easily generalizable to non-ASCII strings, while the regex version is fairly easily.
Writing implementations in C++, using a reasonable encoding of how an efficient regex compiler might compile the vowel regex, the regex implementation outperforms the loop-based implementations significantly in all cases except for long strings with vowels on M1 Max MBP.
Strings were generated randomly following the regex [0-9A-Za-z]. Short strings were between 5-20 chars. Long strings were 5000 chars.
The speedups are:
- Short strings & with vowels: regex is 2.6x faster
- Short strings & no vowels: regex is 5.9x faster
- Long strings & with vowels: loop is 329x faster. This is expected, as because the regex implementation is branchless, it must always search through the whole string.
- Long strings & no vowels: regex is 1.5x faster.
If you add an early return to the regex implementation, the regex with early return becomes strictly faster than the loop versions. The early return is slower than the no early return for the short strings & no vowels case because the extra branch has a cost. Full outputs in a comment at the bottom of the linked file.
I really don't think this is true. If you assume that the string is ASCII, a well-optimized regex for a pattern of this type should be a tight loop over a few instructions that loads the next state from a small array. The small array should fit completely in cache as well. This is basically branchless. I expect that you could process 1 character per cycle on modern CPUs.
If the string is short (~100 characters or less, guessing), I expect this implementation to outperform the find() implementation by far as find() almost certainly will incur at least one more branch mispredict than the regex. For longer strings, it depends on the data, as the branchless regex implementation will scan through the whole string, so find() will be faster if there is an vowel early on in the string. Find still might be faster even if there are no vowels; the exact time in that case depends on microarchitecture.
For non-ASCII, things are a bit trickier, but one can construct a state machine that is not too much larger.
The high level point is that many algorithms for which quantum speedups are possible can be reduced to the Hidden Subgroup Problem, which requires a few weeks of a group theory course to understand.
For an example, consider a three-node binary tree where R is the root, A is the left child, and B is the right child. A valid topological sort is R A B, but it is not the case that whenever B is computed, A has already been computed.