following the post "5 years trying to add recursion to lychee" https://shaarli.lyokolux.space/shaare/STTHtQ

The key takeaway is: they didn’t find a clever trick we missed. They were built as crawlers from the very first commit, and I initially built lychee as a stream.

Why it's still hard and not solved

• the other projects started as crawlers; lychee started as a stream
• the frontier and the rate-limiter must be different objects
• single-threaded runtimes get dedup for free.

it’s a harder problem than just “copy what they do,” because most link checkers didn’t start with uncompromising performance as their top goal.

So the other projects "made it a part of the architecture from the beginning, and they leaned on a runtime (providing conveniences like a WaitGroup, a joinable queue, an idle promise) that solved termination without solving “distributed termination detection.”

instead of letting the call stack implicitly control what happens next (as recursion does), store the pending work in an explicit data structure such as a stack, queue, or heap. This turns control flow into ordinary data that can be inspected, paused, modified, or resumed.

Explicit stacks makes interruptions, limits, cancellation or interleaving work easier to work with. It's more adaptable to real-world constraints and test.

A stack (LIFO) produces depth-first search behavior.
A queue (FIFO) produces breadth-first search behavior.

A Finite State Transducer seems to be the best algorithm instead of a full index search.
The data don't need to be stored in a database indeed. They only need to be searched as text.

This data structure seems efficient and interesting

So, other than Dual_EC_DRBG, NIST's cryptography may not be backdoored, but maybe backdoors aren't needed when the standardized cryptography is far from the state of the art and full of holes that weaken too many projects. Maybe the lack of secure-by-design cryptography is a feature for some, not a bug. Or maybe there are legitimate reasons for promoting legacy algorithms, who knows.

The thing is, modern and secureby-design cryptography exists, notably from D. J. Bernstein:

• ChaCha20 for secure and fast encryption
• X25519 for key exchange
• Ed25519 for signatures
• BLAKE3 for hashing, key derivation, and symmetric signatures (MAC) (BLAKE3 is based on a slightly modified core of the ChaCha20 function)
• The Safe Curve list

Chacha20 can sue 192-bit nonces with a 256-bit key. A single function returns the key, the authentication key and the nonce.

The name changes in order to avoid arguing why ChaCha12 is as secure as ChaCha20, because the implementation is compatible with it.

The final specification https://kerkour.com/chacha20-blake3 and the research used https://kerkour.com/chacha20-blake3 can be helpful.

Optimizations that don't need Rust:

• HTTP range requests for metadata
• Parallel downloads
• Global cache with hardlinks
• Python-free resolution
• PubGrub resolver algorithm

Rust has benefits though:

• zero-copy deserialization
• Thread-level parallelism
• No interpreter startup
• compact version representation: uv packs version into u64 integers. The micro-optimization compounds across millions of comparisons

uv is possible because of many PEP that came since 2016 (so too soon for me): PEP 518, 517, 621, and 658. There are the low-handing fruits: static metadata, no code execution to discover dependencies, and the ability to resolve everything upfront before downloading

It can be useful later on in case of need.

A small data structure crate

A great page about it

Typically, optimization involves choosing the best overall algorithms and data structures. Frequently, algorithmic improvements can cause performance improvements of several orders of magnitude instead of micro-optimizations, which rarely improve performance by more than a few percent. If one waits to optimize until the end of the development cycle, then changing the algorithm could require a significant rewrite.

It's absolutely possible to beat even the best sort implementations with domain specific knowledge, careful benchmarking and an understanding of CPU micro-architectures. At the same time, assumptions will become invalid, mistakes can creep in silently and good sort implementations can be surprisingly fast even without prior domain knowledge. If you have access to a high-quality sort implementation, think twice about replacing it with something home-grown.

Thoughts on ratelimiting, which can be implemented in different ways depending of the needs.

Tuned sorting > Thuned hash table > Baseline sorting > baselinehash table.

Note sorting wins, but it depends of the data size. Tuned sorting is more efficient for bigger data sizes than 256KiB.

The quicksort sorts spread-out data more efficiently than radix sort. Radix sort is more efficient for random data.
Using a faster hash algorithm combined with radix sort performs better than quicksort though: hash with MulSwapMul, then radix sort using diverting LSD radix sort.

Hashed radix sort is more restrictive than hash tables though. Where batching is viable, hashed radix sorts are typically viable.

Understanding the O notation for software complexity.

Bloom filters are excellent data structures to check if an element can be in a set.

Examples can be found on Wikipedia

A piece of engineering to "display" every UUIDs on one page: https://everyuuid.com/

Modern cryptography

Hashing: BLAKE3, Keccak-based functions (SHA-3, SHAKE256) or BLAKE2b.

Encryption: XChaCha20-Poly1305, ChaCah20-BLAKE3, or, I would like to see keccak-based AEAD constructions.

Key Exchange: X25519, X448

Digital Signatures: Ed25519, Ed448

Password Hashing / Key Derivation: Argon2id

When I got started in computers, you had to do low-level bit twiddling to get anything very interesting done, so you pretty much couldn’t avoid learning about XOR. But these days, to a high-level programmer, it’s much more of an optional thing, and you can perfectly well not know much about it.

So I collected some thoughts together and gave a lecture on XOR. Slightly to my own surprise, I was able to spend a full hour talking about it – and then over the course of the next couple of weeks I remembered several other things I could usefully have mentioned.

All of it is available on this page.