orlp

This isn't true. In practice people don't use the analytical solution for efficient linear regression, they use stochastic methods.

Square error is used because it is the maximum likelihood estimator under the assumption that observation noise is normally distributed, not because it is analytical.

This is like banning quotes from your website to 'solve' SQL injection...

It is pull in the sense that an operator can call `recv().await` (the equivalent of `input.next()` in the article) at any point, which can then block the execution of the operator until more data is available.

It is push in the sense that an operator can call `send(x).await` (the equivalent of `out(x)` in the article) at any point, which can then block the execution of the operator until the data is consumed.

So it is a hybrid of both pull and push. You can, at any point, block on either pulling data or pushing data.

At Polars I developed a new query engine which uses a hybrid of push and pull. I gave a short (and not very technical) talk about the engine at our first meetup recently, which can be viewed here: https://www.youtube.com/watch?v=Ndil-eLynh4.

Each operator is a (set of) async functions which are connected to its input(s) and output(s) through capacity-1 spsc async channels. An operator pulls input by reading from a channel, and pushes output by writing into a channel. For an oversimplified example, consider a simple select operator:

    while let Ok(morsel) = input.recv().await {
        let result = select(morsel);
        if output.send(result).await.is_err() {
            break;
        }
    }

Note how it has two await points: on receive and send. The nice part about this is that Rust will automatically transform these asynchronous functions to state machines which can pause execution when either a send or receive blocks, returning control to our scheduler. In the above example the operator is able to pause both to wait for more data, or to wait until the receiver is able to consume more data. This also makes for example pausing execution in the middle of a hash join probe to send some partial results onwards in the computational graph trivial.

I'd suggest you not take readability advice from a guy who uses a red-green color scheme for their tables.

What I don't understand is why it took you 8 weeks to distinguish a timer from a transistor. That doesn't make your professor's reaction alright, I just find it puzzling.

Making it harder to pitch leads to more batters getting hit and more injuries, depending on how it's done.

The elements are completely contiguous, which can be nice for passing off (subslices) to other APIs, maximum speed iteration, etc.

I made something similar to this ~10 years ago: https://github.com/orlp/devector. I never finished it (writing proper containers in C++ is a nightmare [1] [2] [3]), although I did start a similar project in Rust a year or two ago... which I also haven't finished yet (the repo is still private). The double-ended vector is very similar to a regular vector, it can just have free space on both ends:

    <------------ cap_front ------------>
                      <------------ cap_back ------------>
    <-----------------  total_capacity  ----------------->
                      <-----  len  ----->
    <-- space_front -->                 <-- space_back -->
    [                 [    elements     ]                ]
                      ^
                      +--- ptr

In the Rust crate I store 1 pointer and three lengths: len, space_front, space_back for a total size of 32 bytes compared to the usual 24 bytes of Vec.

---

I don't think you always want to shift to the middle. Rather, I propose the following strategy (which I do in the Rust crate, unsure if I did the same in C++ implementation):

1. When a request is made for more free space on one side, check if there is already enough free space, and if not,

2. Compute an amortized growing capacity (e.g. double the current capacity), and take the maximum of that with the requested capacity. While doing this ensure you only take into account the capacity of the side you want more space on (e.g. cap_back in the above picture when growing the back),

3. Check if halving the free space on the other side is sufficient to satisfy the amortized request, if yes, do not reallocate and just shift the values internally, otherwise,

4. Allocate a new buffer with the computed capacity, plus the same amount of free space on the other side and copy over the values.

The above strategy ensures you will not exceed 3N space (with doubling space on grow) even when the double-ended vector is used in a LIFO pattern. For example a regular Vec which doubles its size has a 2N total space worst-case.

[1] https://stackoverflow.com/questions/26902006/may-the-element... [2] https://stackoverflow.com/questions/27453230/is-there-any-wa... [3] https://stackoverflow.com/questions/26744589/what-is-a-prope...

I would suggest

    fd -t f . cache -X rm --

Which reads as find "any file", "matching .", "in directory cache", then "execute rm -- followed by an argument list of all found files".

This ensures even if you have filenames starting with - they won't be interpreted as options for rm. For even more sanity of mind you may want to turn on -a for absolute paths, although I don't see an example right now where using relative paths would go wrong.

Two characters, if you do `from polars import col as c` you can simply write `c.foo`, assuming the column name is a valid Python identifier.

Disclaimer: I work for Polars Inc, but my opinions are my own.

Polars itself is FOSS and will remain FOSS.

Self-hosted/on-site Polars Cloud is something we intend on developing as there is quite a bit of demand, but it is unlikely to be FOSS. It most likely will involve licensing of some sort. Ultimately we do have to make money, and we intend on doing that through Polars Cloud, self-hosted or not (as well as other ventures such as offering training, commercial support, etc).

Disclaimer: I work for Polars Inc, but my opinions are my own.

If you have a very beefy desktop machine and no giant datasets, there isn't a strong reason to use Polars Cloud.

Are you a data scientist running a Polars data pipeline against a subsampled dataset in a notebook on your laptop? With just changing a couple lines of code you can run that same pipeline against your full dataset on a beefy cloud machine which is automatically spun up and spun down for you. If you have so much data that one machine doesn't cut it, you can start running distributed.

In a nutshell, the pitch is very similar to Dask/Ray/Spark, except that it's Polars. A lot of our users say that they came for the speed but stayed for the API, and with Polars Cloud they can use our API and semantics on the cloud. No need to translate it to Dask/Ray/Spark.

An 1.5 hour movie at 24 FPS has ~130k frames to render. As long as you have less machines than that the parallelization is essentially free.

I see, confusing multiple layers of defaults :)

One thing I found peculiar is that for the GraySort benchmark it dispatches to Polars by default to do the actual sorting, not DuckDB: https://github.com/deepseek-ai/smallpond/blob/ed112db42af4d0....

I'm very confused by the article. It's missing about two decades of modern non-cryptographic general hash development, it completely fails to mention the field of universal hashing which created formal criteria for collision probability and produced provably correct constructs to achieve those criteria...

As a self-plug for a related topic, I think going forward we should also take into account HashDoS for non-cryptographic hash functions. All of the hashes mentioned in the article are vulnerable to this, see https://orlp.net/blog/breaking-hash-functions/ for some techniques.

Yes, I meant parity-independence with speculation. Essentially you assume either you are or are not within a string at the start and do your computation based on that assumption, then throw away the result with the unsound assumption. Both assumptions can share most of their computation I believe, so I can understand one might see it from the other perspective where you'd start with calling it parity-independence rather than speculation with shared computation.

Yes, I did already propose (at the office) a parity-agnostic chunker (we only need the number of lines + a splitpoint from the chunker) that can do parallel work and only needs a small moment of synchronization to find out which of the two parities it is to lock in a final answer. There would still be a global serial dependency, but on blocks rather than on bytes.

But we only have a finite amount of time and tons and tons of work, so no one has gotten around to it yet. At least now we know that it might be worthwhile for >= ~32 core machines. PRs welcome :)

It seems from a profile that on the eager engine the serial scanner is able to feed ~32 threads worth of decoding: https://share.firefox.dev/4hS1eJa.

It might be worth speculating, or at least optimizing the serial chunker more. You could theoretically start a second serial chunker from the end working backwards but that would not be wise with our ordered streams, as the decoded data would have to be buffered for a long time.

Similarly on the new streaming engine, each thread is active ~half of the time, except the thread running the chunking task: https://share.firefox.dev/3WQV9og.

Note that in a lot of realistic workloads on the streaming engine compute can happen in between decodes, completely hiding the bottleneck. Also all of the above is with the file being completely in file cache, if fed from a slow SSD it's not a bottleneck whatsoever.

In this case "x" is 1/d where d is the unused fraction of space.

So if you leave 0.1% of your hashtable unused your x is 1000 - quite problematic. However if you leave 12.5% of your hashtable unused your x is 8 - quite reasonable, and not something logarithmic behavior would necessarily speed up, for reasonable constants.

Skimming the paper [1], the key difference they used is that their hash table insertion algorithm will probe further than the first empty slot, instead of greedily filling the first empty slot it finds. They combine this with a clever probing sequence which provably finds empty slots efficiently, even if the table is very full.

This means insertions when the hash table is less full are slower, but you avoid the worst-case scenario where you're probing for the last (few) remaining open slot(s) without any idea as to where they are.

[1]: https://arxiv.org/pdf/2501.02305

---

An interesting theoretical result but I would expect the current 'trick' of simply allocating a larger table than necessary to be the superior solution in practice. For example, Rust's hashbrown intentionally leaves 1/8th (12.5%) of the table empty, which does cost a bit more memory but makes insertions/lookups very fast with high probability.

We have a single-threaded chunker that scans serially over the file. This chunker exclusively finds unquoted newlines (using SIMD) to find clean parallelization boundaries, it doesn't do any further parsing. Those parallelization boundaries are then used to feed worker threads chunks of data to properly parse into our in-memory representation (which mostly follows Arrow).

Disclaimer: I work for Polars inc.

As a sanity check I just cloned https://github.com/h2oai/db-benchmark, ran the data generation script and ran on a 64 core AMD EPYC (AWS c7a.16xlarge):

    import polars as pl
    lf = pl.scan_csv("G1_1e9_1e2_0_0.csv")
    print(lf.select(pl.col.v1.sum()).collect())

The above script ran in 7.58 seconds.

If I change the collect() to collect(new_streaming=True) to use the new streaming engine I've been working on, it runs in 6.90 seconds.

I can't realistically time the full "read CSV to memory" with this 50 GB file on this machine as we start swapping (this machine has 128GiB memory) and/or evicting data from disk cache (this machine has a slow EC2 SSD attached to it), so we do have a blow-up of memory usage (which could be as simple as loading small integers into an 8-byte Uint64 column). I think it's likely that on K's machine the "read full CSV to memory" approach also started swapping, giving the large runtime. However, in Polars you'd typically write your query using LazyFrames, which means we don't actually have to load the full CSV into memory.

EDIT: running on a m7a.16xlarge with twice the memory (256GiB) once the CSV file is in disk cache Polars can parse the full CSV file into an in-memory dataframe in 7.68 seconds.

K's claim that it parses the full 50GB CSV in 1.6 seconds if true is very impressive regardless.

We "evolved" dog breeds in microseconds in evolutionary terms. As long as the selective pressure is high change can come fast.

All f64 bit patterns are valid.

If using data violating some ToS taints the model trained on that data, then all of OpenAI's models are tainted by the millions of ToS'es they broke.

I use the "VSCode Neovim" extension which lets me use a real Neovim instance inside VS Code, including my personalized vimrc and a lot of plugins. Not all plugins work but if they're just textual good chance they do.

If you have access to the BMI2 instruction set I can do branchless UTF-8 encoding like in the article using only 9 instructions and 73 bytes of lookup tables:

    branchless_utf8:
        mov     rax, rdi
        lzcnt   ecx, esi
        lea     rdx, [rip + .L__unnamed_1]
        movzx   ecx, byte ptr [rcx + rdx]
        lea     rdx, [rip + example::DEP_AND_OR::h78cbe1dc7fe823a9]
        pdep    esi, esi, dword ptr [rdx + 8*rcx]
        or      esi, dword ptr [rdx + 8*rcx + 4]
        movbe   dword ptr [rdi], esi
        mov     qword ptr [rdi + 8], rcx
        ret

The code:

    static DEP_AND_OR: [(u32, u32); 5] = [
        (0, 0),
        (0b01111111_00000000_00000000_00000000, 0b00000000_00000000_00000000_00000000),
        (0b00011111_00111111_00000000_00000000, 0b11000000_10000000_00000000_00000000),
        (0b00001111_00111111_00111111_00000000, 0b11100000_10000000_10000000_00000000),
        (0b00000111_00111111_00111111_00111111, 0b11110000_10000000_10000000_10000000),
    ];

    const LEN: [u8; 33] = [
        // 0-10 leading zeros: not valid.
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        // 11-15 leading zeros: 4 bytes.
        4, 4, 4, 4, 4,
        // 16-20 leading zeros: 3 bytes.
        3, 3, 3, 3, 3,
        // 21-24 leading zeros: 2 bytes.
        2, 2, 2, 2,
        // 25-32 leading zeros: 1 byte.
        1, 1, 1, 1, 1, 1, 1, 1,
    ];

    pub unsafe fn branchless_utf8(codepoint: u32) -> ([u8; 4], usize) {
        let leading_zeros = codepoint.leading_zeros() as usize;
        let bytes = LEN[leading_zeros] as usize;
        let (mask, or) = *DEP_AND_OR.get_unchecked(bytes);
        let ret = core::arch::x86_64::_pdep_u32(codepoint, mask) | or;
        (ret.swap_bytes().to_le_bytes(), bytes)
    }

Seems like LLVM knows about this quirk (note how it suddenly uses eax instead of rax for the multiply): https://rust.godbolt.org/z/8jh7YPhz4.