A diagram of C23 basic types
(wordpress.com)
This week on the C committee mailing list we had a discussion about how C’s types are organized into different categories. At the end I came up with a diagram with that organization. It basically translates the section “6.2.5 Types” of the C23 standard into a graph of inclusions.
This week on the C committee mailing list we had a discussion about how C’s types are organized into different categories. At the end I came up with a diagram with that organization. It basically translates the section “6.2.5 Types” of the C23 standard into a graph of inclusions.
Writing a tiny undo/redo stack in JavaScript
(julik.nl)
I’ve needed this before - a couple of times. Third time I figured I needed something small, nimble - yet complete. And - at the same time - wondering about how to do it in a very simple manner. I think it worked out great, so let’s dig in.
I’ve needed this before - a couple of times. Third time I figured I needed something small, nimble - yet complete. And - at the same time - wondering about how to do it in a very simple manner. I think it worked out great, so let’s dig in.
Shift-to-Middle Array: A Faster Alternative to Std:Deque?
(github.com/attilatorda)
The Shift-To-Middle Array is a dynamic array designed to optimize insertions and deletions at both ends, offering a high-performance alternative to std::deque, std::vector, and linked lists.
The Shift-To-Middle Array is a dynamic array designed to optimize insertions and deletions at both ends, offering a high-performance alternative to std::deque, std::vector, and linked lists.
Ruby, Ractors, and lock-free data structures
(iliabylich.github.io)
This story is about concurrent data structures in the context of Ruby. The goal here is to demonstrate how true parallelism can be achieved with global mutable state (which at the time of writing, is not supported by built-in Ruby primitives).
This story is about concurrent data structures in the context of Ruby. The goal here is to demonstrate how true parallelism can be achieved with global mutable state (which at the time of writing, is not supported by built-in Ruby primitives).
Undergraduate Disproves 40-Year-Old Conjecture, Invents New Kind of Hash Table
(wired.com)
A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.
A young computer scientist and two colleagues show that searches within data structures called hash tables can be much faster than previously deemed possible.
Visualising data structures and algorithms through animation
(visualgo.net)
Initially conceived in 2011 by Associate Professor Steven Halim, VisuAlgo aimed to facilitate a deeper understanding of data structures and algorithms for his students by providing a self-paced, interactive learning platform.
Initially conceived in 2011 by Associate Professor Steven Halim, VisuAlgo aimed to facilitate a deeper understanding of data structures and algorithms for his students by providing a self-paced, interactive learning platform.
How std::any Works
(fluentcpp.com)
In the previous post we’ve seen a very nice technique to use value semantics with inheritance and virtual methods, which was made possible by std::any.
In the previous post we’ve seen a very nice technique to use value semantics with inheritance and virtual methods, which was made possible by std::any.
Representing Type Lattices Compactly
(bernsteinbear.com)
The Cinder JIT compiler does some cool stuff with how they represent types so I’m going to share it with you here. The core of it is thinking about types as sets (lattices, even), and picking a compact representation. Compilers will create and manipulate types with abandon, so all operations have to be fast.
The Cinder JIT compiler does some cool stuff with how they represent types so I’m going to share it with you here. The core of it is thinking about types as sets (lattices, even), and picking a compact representation. Compilers will create and manipulate types with abandon, so all operations have to be fast.
Dmap: A C hashmap that's stupid simple and surprisingly fast
(github.com/jamesnolanverran)
Dmap is a flexible, lightweight, zero-friction dynamic hashmap implementation in C, designed to be user-friendly without sacrificing performance.
Dmap is a flexible, lightweight, zero-friction dynamic hashmap implementation in C, designed to be user-friendly without sacrificing performance.
Using Zig from Common Lisp
(jagg.github.io)
Last week I started playing with my own toy key-value store (see the previous post). At the end I got to a hashtable exposed over the network, using a protocol based on S-Expressions. For the next steps, I have two alternatives, I can work on the low level representation of the data, maybe implement B-Trees, and some storage, or I can go up instead, and see how can I make it distributed, and play with some nice algorithms.
Last week I started playing with my own toy key-value store (see the previous post). At the end I got to a hashtable exposed over the network, using a protocol based on S-Expressions. For the next steps, I have two alternatives, I can work on the low level representation of the data, maybe implement B-Trees, and some storage, or I can go up instead, and see how can I make it distributed, and play with some nice algorithms.
Optimistic Locking in B-Trees
(cedardb.com)
B-Trees are one of the few specialized data structures which truly stood the test of time, being over 50 years old.
B-Trees are one of the few specialized data structures which truly stood the test of time, being over 50 years old.
Succinct data structures
(startifact.com)
A few months ago, searching for ideas on how to make some code faster, I found myself reading a bunch of computer science papers.
A few months ago, searching for ideas on how to make some code faster, I found myself reading a bunch of computer science papers.
A Student Who Revolutionized Hash Tables and Shattered a 35-Year-Old Myth
(medium.com)
Andrew Krapivin upended the common thinking around hash tables
Andrew Krapivin upended the common thinking around hash tables
Purely Functional Sliding Window Aggregation Algorithm
(byorgey.github.io)
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.
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.
Relaxed Radix Balanced Trees (2024)
(horne-khan.com)
I’m adding immutable vectors to my language, Ivan, and needed to pick a suitable data structure to implement them.
I’m adding immutable vectors to my language, Ivan, and needed to pick a suitable data structure to implement them.
TOML [Tom's Obvious Minimal Language]
(toml.io)
TOML aims to be a minimal configuration file format that's easy to read due to obvious semantics. TOML is designed to map unambiguously to a hash table. TOML should be easy to parse into data structures in a wide variety of languages.
TOML aims to be a minimal configuration file format that's easy to read due to obvious semantics. TOML is designed to map unambiguously to a hash table. TOML should be easy to parse into data structures in a wide variety of languages.
This New Algorithm for Sorting Books or Files Is Close to Perfection
(wired.com)
Computer scientists often deal with abstract problems that are hard to comprehend, but an exciting new algorithm matters to anyone who owns books and at least one shelf.
Computer scientists often deal with abstract problems that are hard to comprehend, but an exciting new algorithm matters to anyone who owns books and at least one shelf.
Swiss Tables
(abseil.io)
Abseil provides its own family of hash tables (colloquially known as “Swiss tables”) in place of std::unordered_set and std::unordered_map. These classes are:
Abseil provides its own family of hash tables (colloquially known as “Swiss tables”) in place of std::unordered_set and std::unordered_map. These classes are:
What's in a ring buffer? And using them in Rust
(ntietz.com)
Working on my cursed MIDI project, I needed a way to store the most recent messages without risking an unbounded amount of memory usage.
Working on my cursed MIDI project, I needed a way to store the most recent messages without risking an unbounded amount of memory usage.
JesseSort: A novel sorting algorithm that is faster than Python's default sort.
(github.com/lewj85)
JesseSort is a novel sorting algorithm that introduces a new data structure called a Rainbow to efficiently organize and merge elements. It achieves a runtime of O(n log n).
JesseSort is a novel sorting algorithm that introduces a new data structure called a Rainbow to efficiently organize and merge elements. It achieves a runtime of O(n log n).
Tiny Pointers
(arxiv.org)
This paper introduces a new data-structural object that we call the tiny pointer.
This paper introduces a new data-structural object that we call the tiny pointer.
Solving the ABA Problem in Rust with Tagged Pointers
(minikin.me)
Concurrent programming is challenging, especially when designing lock-free data structures. One subtle issue that can arise is the ABA problem, leading to unexpected behavior in compare-and-swap (CAS) operations. In this post, we’ll explore the ABA problem and how to solve it in Rust using idiomatic and efficient techniques.
Concurrent programming is challenging, especially when designing lock-free data structures. One subtle issue that can arise is the ABA problem, leading to unexpected behavior in compare-and-swap (CAS) operations. In this post, we’ll explore the ABA problem and how to solve it in Rust using idiomatic and efficient techniques.
Generating Voronoi diagrams using Fortune's algorithm
(redpenguin101.github.io)
Generating Voronoi Diagrams using Fortune’s Algorithm
Generating Voronoi Diagrams using Fortune’s Algorithm
Implementation of a RingBuffer in Java with optional FIFO like semantics
(github.com/evolvedbinary)
Some extra Collection classes targetting Java 8.
Some extra Collection classes targetting Java 8.
Elastic Binary Trees (2011)
(blogspot.com)
In computer science, an elastic binary tree (or EB tree or EBtree) is a binary search tree specially optimized to very frequently store, retrieve and delete discrete integer or binary data without having to deal with memory allocation.
In computer science, an elastic binary tree (or EB tree or EBtree) is a binary search tree specially optimized to very frequently store, retrieve and delete discrete integer or binary data without having to deal with memory allocation.