SIMD-friendly algorithms for substring searching
Introduction Popular programming languages provide methods or functions which locate a substring in a given string. In C it is the function strstr, the C++ class std::string has the method find, Python's string has methods pos and index, and so on, so forth. All these APIs were designed for one-shot searches. During past decades several algorithms to solve this problem were designed, an excellent
runtime: green tea garbage collector · Issue #73581 · golang/go
Green Tea 🍵 Garbage Collector Authors: Michael Knyszek, Austin Clements Updated: 2 May 2025 This issue tracks the design and implementation of the Green Tea garbage collector. As of the last update to this issue, development of Green Tea is still active. We'll produce more detailed design document once we're ready to commit to a design. For now, Green Tea is available as an experiment at tip-of-t
Lock-Free Rust: How to Build a Rollercoaster While It’s on Fire
Lock-Free Rust: How to Build a Rollercoaster While It’s on Fire. “Every stitch in that flag was a commitment to thread safety without locks. std::atomic was the needle.” — Betsy Ross, Federalist Papers, Draft 29 (suppressed), 1782 Buckle your seatbelts, grab a helmet, and say goodbye to your loved ones because over the next few minutes, I am going to teach you more about lock-free data structures
How Austral’s Linear Type Checker Works
What I cannot create, I do not understand. — Richard Feynman Austral is a new programming language featuring linear types and capability-based security. Linear types give you compile-time memory and resource safety, capability-based security allows you to constrain the kind of side effects a program can do. In my last post, I introduced the language and went over what linear types are, how they wo
Succinct data structures
Succinct data structures By Martijn Faassen • 2025-02-28 • Tags: computer science, xml, rust Introduction A few months ago, searching for ideas on how to make some code faster, I found myself reading a bunch of computer science papers. I don't pretend to be good at this - but I don't mind some confusion or being overwhelmed, and I'm okay to admit my ignorance. 1. I ran into this 15 year old paper
Solving the ABA Problem in Rust with Tagged Pointers
Introduction 📺 Series Overview 👨🔬 What Is the ABA Problem? 🏷️ Tagged Pointers with Versioning ⚙️ Key Mechanism 🧐 Pros and Cons 🧪 Tests and Benchmarks Tests Module Benchmarks Module 🔗 Resources 🤔 Final Thoughts Introduction Concurrent programming is challenging, especially when designing lock-free data structures. One subtle issue that can arise is the ABA problem, leading to unexpected be
Generalized Dijkstra in Haskell
This years’ Advent of Code has loads of 2D grids, and makes you traverse them all to find paths of various kinds. At some point I had to implement Dijkstra’s algorithm, in Haskell. In trying to make my implementation reusable for the following days, I realized that Dijkstra’s algorithm is actually way more general than I remembered (or was taught)! In short, weights don’t have to be real-valued! I
blog :: Brent -> [String] - Competitive Programming in Haskell: stacks, queues, and monoidal sliding windows
Competitive Programming in Haskell: stacks, queues, and monoidal sliding windows Suppose we have a list of items of length \(n\), and we want to consider windows (i.e. contiguous subsequences) of width \(w\) within the list. ⊕A list of numbers, with contiguous size-3 windows highlighted We can compute the sum of each window by brute force in \(O(nw)\) time, by simply generating the list of all the
Rope Optimizations, Part 1 - Zed Blog
A couple of weeks ago I came across one of Antonio's PRs, titled "Speed up point translation in the Rope" — now who doesn't stop to take a closer look at a PR with that title? The description already lives up to the title. It contains benchmark results telling me that a method on our Rope named point_to_offset is now up to 70% faster. 70%! Throughput increased by 250%. (I can't remember but I'm su
Designing A Fast Concurrent Hash Table
I recently released papaya, a fast and feature-complete concurrent hash table for Rust. In this post I want to dive into the design and research that went into creating it, as well as why you might consider using it over existing solutions. If you're looking for an overview of papaya, you might find it more useful to consult the documentation. Philosophy Concurrent hash tables are a well explored
ざっくり理解するPaxos - 小野マトペの納豆ペペロンチーノ日記
ゴールデンウィーク中、Appleがオープンソースとしてリリースした分散データベース FoundationDB のドキュメントを読んでいました。なかなか面白いデータベースだと思うのでこれについては別途書きたいですが、それはそれとしてFoundationDBでは、分散環境下でACIDトランザクションを実現するために、分散合意プロトコルとして有名なPaxosを採用しているようでした。 PaxosはGoogleのChubbyやCassandraのLight Weight Transactionなどで使われていますが、僕はいまだにPaxosがどのように動作するのかあまりよく分かっていませんでした。良い機会だと思い、FoundationDBの技術を理解するためにも連休の後半でLeslie LamportによるPaxosの論文の一つ Paxos Made Simple を読み、何となくわかった気持ちにな
Taming Floating-Point Sums | orlp.net
Suppose you have an array of floating-point numbers, and wish to sum them. You might naively think you can simply add them, e.g. in Rust: fn naive_sum(arr: &[f32]) -> f32 { let mut out = 0.0; for x in arr { out += *x; } out } This however can easily result in an arbitrarily large accumulated error. Let’s try it out: naive_sum(&vec![1.0; 1_000_000]) = 1000000.0 naive_sum(&vec![1.0; 10_000_000]) = 1
Rope & SumTree - Zed Blog
For this second post in Zed Decoded, our blog & video series in which we're taking a closer look at how Zed is built, I've talked to Zed's three co-founders — Nathan, Max, Antonio — about the data structure at the heart of Zed: the rope. This post comes with a 1hr companion video, in which Thorsten, Nathan, Antonio, and Max use Zed to look at how Zed uses the Rope and SumTree types. It's a loose c
An Interactive Intro to CRDTs | jakelazaroff.com
Have you heard about CRDTs and wondered what they are? Maybe you’ve looked into them a bit, but ran into a wall of academic papers and math jargon? That was me before I started my Recurse Center The Recurse Center The Recurse Center is a self-directed, community-driven educational retreat for programmers in New York City. www.recurse.com/ batch. But I’ve spent the past month or so doing research a
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Optimizing with Novel Calendrical Algorithms
blog :: Brent -> [String] - Competitive Programming in Haskell: Union-Find
Integer Compression
K-Means Image Compression
https://www.cc.u-tokyo.ac.jp/events/lectures/X01/shiryou-1.pdf
Knuth–Morris–Pratt illustrated | Journal of Functional Programming | Cambridge Core
