aho-corasick VS rfcs

You can't build the contiguous variant directly from a sequence of patterns. You need some kind of intermediate data structure to incrementally build a trie in memory. The contiguous NFA needs to know the complete picture of each state in order to compress it into memory. It makes decisions like, "if the number of transitions of this state is less than N, then use this representation" or "use the most significant N bits of the state pointer to indicate its representation." It is difficult to do this in an online fashion, and likely impossible to do without some sort of compromise. For example, you don't know how many transitions each state has until you've completed construction of the trie. But how do you build the trie if the state representation needs to know the number of transitions?

Note that the conversion from a non-contiguous NFA to a contiguous NFA is, relatively speaking, pretty cheap. The only real reason to not use a contiguous NFA is that it can't represent as many patterns as a non-contiguous NFA. (Because of the compression tricks it uses.)

The interesting bits start here: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...

Right. I pointed it out because it isn't just about having portable SIMD that makes SIMD optimizations possible. Therefore, the lack of one in Rust doesn't have much explanatory power for why Rust's standard library doesn't contain SIMD. (It does have some.) It's good enough for things like memchr (well, kinda, NEON doesn't have `movemask`[1,2]), but not for things like Teddy that do multi-substring search. When you do want to write SIMD across platforms, it's not too hard to define your own bespoke portable API[3].

I'm basically just pointing out that a portable API is somewhat oversold, because it's not uncommon to need to abandon it, especially for string related ops that make creative use of ISA extensions. And additionally, that Rust unfortunately has other reasons for why std doesn't make as much use of SIMD as it probably should (the core/alloc/std split).

[1]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf...

[2]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf...

[3]: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...

Oh I see. Yes, that's what is commonly used in academic publications. But I've yet to see it used in the wild.

I mentioned exactly that paper (I believe) in my write-up on Teddy: https://github.com/BurntSushi/aho-corasick/tree/master/src/p...

The byte offset (or equivalently in this case, the UTF-8 code unit offset) is almost certainly what you want. See: https://github.com/BurntSushi/aho-corasick/issues/72

This is an implementation of the algorithm in Rust as well if someone is curious. Though this code is written for production and not teaching.

A similar fix for the aho-corasick Rust crate was made in response

Teddy is a SIMD accelerated multiple substring matching algorithm. There's a nice description of Teddy here: https://github.com/BurntSushi/aho-corasick/tree/f9d633f970bb...

It's used in the aho-corasick and regex crates. It now supports SIMD acceleration on aarch64 (including Apple's M1 and M2). There are some nice benchmarks included in the PR demonstrating 2-10x speedups for some searches!

Even putting aside all of that, it might be really hard to add some of the improvements ripgrep has to their engine. The single substring search is probably the lowest hanging fruit, because you can probably isolate that code path pretty well. The multi-substring search is next, but the algorithm is very complicated and not formally described anywhere. The best description of it, Teddy, is probably my own. (I did not invent it.)

RFC: Add large language models to Rust

https://github.com/rust-lang/rfcs/pull/3603

Man, SO and family has really gone downhill. That top answer is absolutely terrible. In fact, if you care, you can literally look at the RFC discussion here to see the actual debate: https://github.com/rust-lang/rfcs/pull/582

Basically, `for x in y` is kind of redundant, already sorta-kinda supported by itertools, and there's also a ton of macros that sorta-kinda do it already. It would just be language bloat at this point.

Literally has nothing to do with memory management.

Congrats!

> Similarly, uv does not yet generate a platform-agnostic lockfile. This matches pip-tools, but differs from Poetry and PDM, making uv a better fit for projects built around the pip and pip-tools workflows.

Do you expect to make the higher level workflow independent of requirements.txt / support a platform-agnostic lockfile? Being attached to Rye makes me think "no".

Without being platform agnostic, to me this is dead-on-arrival and unable to meet the "Cargo for Python" aim.

> uv supports alternate resolution strategies. By default, uv follows the standard Python dependency resolution strategy of preferring the latest compatible version of each package. But by passing --resolution=lowest, library authors can test their packages against the lowest-compatible version of their dependencies. (This is similar to Go's Minimal version selection.)

> uv allows for resolutions against arbitrary target Python versions. While pip and pip-tools always resolve against the currently-installed Python version (generating, e.g., a Python 3.12-compatible resolution when running under Python 3.12), uv accepts a --python-version parameter, enabling you to generate, e.g., Python 3.7-compatible resolutions even when running under newer versions.

This is great to see though!

I can understand it being a flag on these lower level, directly invoked dependency resolution operations.

While you aren't onto the higher level operations yet, I think it'd be useful to see if there is any cross-ecosystem learning we can do for my MSRV RFC: https://github.com/rust-lang/rfcs/pull/3537

How are you handling pre-releases in you resolution? Unsure how much of that is specified in PEPs. Its something that Cargo is weak in today but we're slowly improving.

In the early days of Rust there was a debate about whether to support "green threads" and in doing that require runtime support. It was actually implemented and included for a time but it creates problems when trying to do library or embedded code. At the time Go for example chose to go that route, and it was both nice (goroutines are nice to write and well supported) and expensive (effectively requires GC etc). I don't remember the details but there is a Rust RFC from when they removed green threads:

https://github.com/rust-lang/rfcs/blob/0806be4f282144cfcd55b...

I did some more digging. By RFC 899, I believe Alex Crichton meant PR 899 in this repo:

https://github.com/rust-lang/rfcs/pull/899

Still, no real discussion of why unbuffered stderr.

Rust has had a stable SIMD vector API[1] for a long time. But, it's architecture specific. The portable API[2] isn't stable yet, but you probably can't use the portable API for some of the more exotic uses of SIMD anyway. Indeed, that's true in .NET's case too[3].

Rust does all this SIMD too. It just isn't in the standard library. But the regex crate does it. Indeed, this is where .NET got its SIMD approach for multiple substring search from in the first place[4]. ;-)

You're right that Rust's standard library is conservatively vectorized though[5]. The main thing blocking this isn't the lack of SIMD availability. It's more about how the standard library is internally structured, and the fact that things like substring search are not actually defined in `std` directly, but rather, in `core`. There are plans to fix this[6].

[1]: https://doc.rust-lang.org/std/arch/index.html

[2]: https://doc.rust-lang.org/std/simd/index.html

[3]: https://github.com/dotnet/runtime/blob/72fae0073b35a404f03c3...

[4]: https://github.com/dotnet/runtime/pull/88394#issuecomment-16...

[5]: https://github.com/BurntSushi/memchr#why-is-the-standard-lib...

[6]: https://github.com/rust-lang/rfcs/pull/3469