aho-corasick VS fd

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.)

ripgrep: A super-fast file searcher. You can install it using your system's package manager (e.g., brew install ripgrep on macOS). fd: Another blazing-fast file finder. Installation instructions can be found here: https://github.com/sharkdp/fd

hyperfine is such a great tool that it's one of the first I reach for when doing any sort of benchmarking.

I encourage anyone who's tried hyperfine and enjoyed it to also look at sharkdp's other utilities, they're all amazing in their own right with fd[1] being the one that perhaps get the most daily use for me and has totally replaced my use of find(1).

[1]: https://github.com/sharkdp/fd

You call it with `n` and get an interactive fuzzy search for your directories. If you do `n ` instead, it’ll start the find with `` already filled in (and if there’s only one match, jump to it directly). The `ls` is optional but I find that I like having the contents visible as soon as I change a directory.

I’m also including iCloud Drive but excluding the Library directory as that is too noisy. I have a separate `nl` function which searches just inside `~/Library` for when I need it, as well as other specialised `n` functions that search inside specific places that I need a lot.

¹ https://github.com/sharkdp/fd

² https://github.com/junegunn/fzf

Many (most?) of them have been overhauled with success. For find there is fd[1]. There's batcat, exa (ls), ripgrep, fzf, atuin (history), delta (diff) and many more.

Most are both backwards compatible and fresh and friendly. Your hardwon muscle memory still of good use. But there's sane flags and defaults too. It's faster, more colorful (if you wish), better integration with another (e.g. exa/eza or aware of git modifications). And, in my case, often features I never knew I needed (atuin sync!, ripgrep using gitignore).

1 https://github.com/sharkdp/fd

Descubra mais sobre o fd em: https://github.com/sharkdp/fd

AFAIK there is a find replacement with sane defaults: https://github.com/sharkdp/fd , a lot of people I know love it.

However, I already have this in my muscle memory:

fd

> without zsh globs I have to remember find syntax

My "solution" to this is using https://github.com/sharkdp/fd (even when in zsh and having glob support). I'm not sure if using a tool that's not present by default would be suitable for your use cases, but if you're considering alternate shells, I suspect you might be

Nice to see other alternatives to find. I personally use fd (https://github.com/sharkdp/fd) a lot, as I find the UX much better. There is one thing that I think could be better, around the difference between "wanting to list all files that follow a certain pattern" and "wanting to find one or a few specific files". Technically, those are the same, but an issue I'll often run into is wanting to search something in dotfiles (for example the Go tools), use the unrestricted mode, and it'll find the few files I'm looking for, alongside hundreds of files coming from some cache/backup directory somewhere. This happens even more with rg, as it'll look through the files contents.

I'm not sure if this is me not using the tool how I should, me not using Linux how I should, me using the wrong tool for this job, something missing from the tool or something else entirely. I wonder if other people have this similar "double usage issue", and I'm interested in ways to avoid it.