Our great sponsors
-
t-digest
A new data structure for accurate on-line accumulation of rank-based statistics such as quantiles and trimmed means
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
-
pyroscope
Discontinued Continuous Profiling Platform. Debug performance issues down to a single line of code [Moved to: https://github.com/grafana/pyroscope] (by pyroscope-io)
-
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
-
-
-
RoaringBitmap
A better compressed bitset in Java: used by Apache Spark, Netflix Atlas, Apache Pinot, Tablesaw, and many others
-
-
-
AspNetCoreDiagnosticScenarios
This repository has examples of broken patterns in ASP.NET Core applications
-
-
swift
the multiparty transport protocol (aka "TCP with swarming" or "BitTorrent at the transport layer") (by gritzko)
-
-
-
-
-
multiversion-concurrency-control
Implementation of multiversion concurrency control, Raft, Left Right concurrency Hashmaps and a multi consumer multi producer Ringbuffer, concurrent and parallel load-balanced loops, parallel actors implementation in Main.java, Actor2.java and a parallel interpreter
-
hierarch_old
Hierarch: A new, blazingly fast, in-memory proof-of-concept data structure and indexing algorithm for querying on dynamic attribute/tag/type-based hierarchical data.
-
FusionCache
FusionCache is an easy to use, fast and robust cache with advanced resiliency features and an optional distributed 2nd level.
-
-
SaaSHub
SaaSHub - Software Alternatives and Reviews. SaaSHub helps you find the best software and product alternatives
How about a pinsketch:
A pinsketch is a set that takes a specified amount of memory and into which you can insert and remove set members or even add whole sets in time O(memory size). You can insert an unbounded number of entries, and at any time that it has equal or fewer entries than the size you can decode the list of members.
For an example usage, say I have a list of ten million IP addresses of people who have DOS attacked my systems recently. I want to send my list to you over an expensive iridium connection, so I don't want to just send the 40MiB list. Fortunately you've been making your own observations (and maybe have stale data from me), and we don't expect our lists to differ by more than 1000 entries. So I make and maintain a pinsketch with size 1000 which takes 4000 bytes (1000 * 4bytes because IP addresses are 32-bits). Then to send you an update I just send it over. You maintain your own pinsketch of addresses, you subtract it from the one I sent and then you decode it. If the number of entries different between us is under 1000 you're guaranteed to learn the difference (otherwise the decode will fail, or give a false decode with odds ~= 1/2^(1000)).
Bonus: We don't need to know in advance how different our sets are-- I can send the sketch in units as small as one word at a time (32-bits in this case) and stop sending once you've got enough to decode.
Here is an implementation I contributed to: https://github.com/sipa/minisketch/
There is a application related data-structure called an inverted bloom lookup table (IBLT) that accomplishes the same task. Its encoding and especially decoding is much faster, and it has asymptotically the same communications efficiency. However, the constant factors on the communications efficiency are poor so for 'small' in set difference (like the 1000 above) it has a rather high overhead factor, and it can't guarantee decoding. I think that makes it much less magical, though it may be the right tool for some applications.
IBLT also has the benefit that it the decoder is a fun bit of code golf to implement.
I am enamored by data structures in the sketch/summary/probabilistic family: t-digest[1], q-digest[2], count-min sketch[3], matrix-sketch[4], graph-sketch[5][6], Misra-Gries sketch[7], top-k/spacesaving sketch[8], &c.
What I like about them is that they give me a set of engineering tradeoffs that I typically don't have access to: accuracy-speed[9] or accuracy-space. There have been too many times that I've had to say, "I wish I could do this, but it would take too much time/space to compute." Most of these problems still work even if the accuracy is not 100%. And furthermore, many (if not all of these) can tune accuracy to by parameter adjustment anyways. They tend to have favorable combinatorial properties ie: they form monoids or semigroups under merge operations. In short, a property of data structures that gave me the ability to solve problems I couldn't before.
I hope they are as useful or intriguing to you as they are to me.
1. https://github.com/tdunning/t-digest
2. https://pdsa.readthedocs.io/en/latest/rank/qdigest.html
3. https://florian.github.io/count-min-sketch/
4. https://www.cs.yale.edu/homes/el327/papers/simpleMatrixSketc...
5. https://www.juanlopes.net/poly18/poly18-juan-lopes.pdf
6. https://courses.engr.illinois.edu/cs498abd/fa2020/slides/20-...
7. https://people.csail.mit.edu/rrw/6.045-2017/encalgs-mg.pdf
8. https://www.sciencedirect.com/science/article/abs/pii/S00200...
9. It may better be described as error-speed and error-space, but I've avoided the term error because the term for programming audiences typically evokes the idea of logic errors and what I mean is statistical error.
Tries (or prefix trees).
We use them a lot at Pyroscope for compressing strings that have common prefixes. They are also used in databases (e.g indexes in Mongo) or file formats (e.g debug symbols in macOS/iOS Mach-O format are compressed using tries).
We have an article with some animations that go into details about tries in case anyone's interested [0].
[0] https://github.com/pyroscope-io/pyroscope/blob/main/docs/sto...
I made https://github.com/mamcx/tree-flat as flattened stored tree in pre-order that allows for very fast iterations even for childs/parent queries. Is based on APL, so not that novel.
I also like a lot the relational model, is not that much represented so I making a language on top of it: https://tablam.org.
I made https://github.com/mamcx/tree-flat as flattened stored tree in pre-order that allows for very fast iterations even for childs/parent queries. Is based on APL, so not that novel.
I also like a lot the relational model, is not that much represented so I making a language on top of it: https://tablam.org.
HNSW, or Hierarchical Navigable Small World is a graph data structure for approximate nearest neighbor search of vectors.
https://arxiv.org/abs/1603.09320
The problem space of ANN is one of those really deep holes you can go down. It’s a game of balancing time and space, and it’s got plenty of fascinating algorithms and datastructures.
Check out http://ann-benchmarks.com/ for a comparison. HNSW is not “the best” but it’s easy to understand and is quite effective.
Sparse sets.
They're often used in Entity Component System architectures since you have O(1) add/remove/find, & O(n) iteration. Iterations are also packed, which is a bonus for cache efficiency.
Can be difficult to implement well, but the concept is simple and a neat example of a useful specialty data structure. Take a look at https://github.com/skypjack/entt
Ole Begemann and Chris Eidhoff wrote Advanced Swift, and, in there, described a really efficient FIFO queue.
I implemented a variant ofit, in my Generic Swift Toolbox Package[0]. It’s lightning fast.
[0] https://github.com/RiftValleySoftware/RVS_Generic_Swift_Tool...
Ole Begemann and Chris Eidhoff wrote Advanced Swift, and, in there, described a really efficient FIFO queue.
I implemented a variant ofit, in my Generic Swift Toolbox Package[0]. It’s lightning fast.
[0] https://github.com/RiftValleySoftware/RVS_Generic_Swift_Tool...
Arrays aren't efficient when you want to add/remove to the head. Deque in python exists so there is a data structure with constant time pop/push to the head. And it is in fact implemented as a doubly linked list, with various optimizations: https://github.com/python/cpython/blob/v3.8.1/Modules/_colle....
I came here to say Golomb compressed sets except now I see it's part of the question!
They are used by default in the OpenMined implementation of Private Set Intersection[1] - a multi-party computation technique.
[1] https://github.com/OpenMined/PSI/blob/master/private_set_int...
I am trying to compile a list of data structures (and algorithms and other stuff) into a kind of knowledge base: https://github.com/Dobatymo/data-algos/blob/master/data-stru.... There are few cool and obscure data structures already. Please feel free to help extend it!
Fractional Cascading. A simple and very cool way to speed up searching for the same key in multiple lists. Instead of K binary searches taking time Klog(N), you can do it in log(N) time without using asymptomatically more space.
https://en.m.wikipedia.org/wiki/Fractional_cascading
I wrote a simple demo in Rust a while back to help myself learn the language.
https://github.com/mgraczyk/fractional_cascading
I also think pairing heaps are neat.
Huet's zipper. https://en.wikipedia.org/wiki/Zipper_(data_structure).
One zipper value represents a regular tree of data, but from the perspective of the "current position". There are traversal operations that take a zipper value and return the same tree from the perspective of an element above/beside/below the current position, and there are operations that return the same structure but with the current element changed, or items deleted or inserted.
Huet's paper is an easy read if you've been exposed to OCaml or similar languages: https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced... . His "returned glove" metaphor is what made it click for me.
Clojure includes an implementation of Huet's zippers https://github.com/clojure/clojure/blob/master/src/clj/cloju... that is <300 lines of code. It's very, very clever and broadly useful for dealing with XML or other nested data structures.
Not super obscure, but I remember that one specific time when circular-linked-list made a lot of sense to use, well I wanted to use it so I used it.
I had a bunch of API keys with poor expiry documentation and implementation, so to find out if a key expired it had to be used. I put it in a main "keys.pop loop" and all methods below tried to use the key. If HTTP response was (some another obscure HTTP response code like) 505, I simply called `continue;` in the loop to jump to another, without caring at all where I was before.
https://github.com/atedja/gring
I've created an Btree version of SeqHash that also allows splitting SeqHashes in O(log(n)) called SplitHash.
See: https://github.com/odipar/spread/blob/master/src/main/scala/...
I'm thinking that the bar for "obscure" here is maybe pretty low if bloom filters pass?
Here's a few fun ones.
— ⁂ —
The Burrows-Wheeler transform is the second character of each suffix in a (cyclic) suffix array, and there turns out to be a simple algorithm to recover the original text from this transform; live demo: http://canonical.org/~kragen/sw/bwt. But the new text is very easily compressible, which is the basis for bzip2. As mentioned by Blahah and dahart, this is only one of many interesting things you can do with suffix arrays; they can also do efficient regular expression search, for example. This is more interesting since three practical linear-time and -space suffix array construction algorithms were discovered in the early 02000s.
— ⁂ —
Pentti Kanerva devised a "fully distributed representation" in the 01990s, which has some features in common with bloom filters — every association stored in an FDR record is stored to an equal extent (probabilistically) in every bit of the record, so erasing some of the bits erases none of the associations but increases the error probability for all of them. You assign a random or pseudorandom bitvector (of, say, 16384 bits) to every atomic value to be stored, represent an association of two (or more) atoms as their XOR, and then take the bitwise majority rule of all the associations to be stored as the record. To retrieve an association, you XOR the record with an atom, then compute the correlation of the XOR result with all possible atoms; the correlation with the correct atoms will be many standard deviations away from the mean, unless the number of associations stored in the record is high enough that conventional data structures wouldn't have been able to store it either.
This and some related work has blossomed into a field called "hyperdimensional computing" and "vector symbolic architectures". But the problem of finding the nearest atom or atoms seems, on its face, to make this impractical: if you have 16384 possible atoms and 16384 bits in your bitvector, you would seem to need at least 16777216 bit operations to compute all the associations.
I realized the other night that if you use the rows of a Walsh–Hadamard matrix as the "pseudorandom" atom representations, you can compute all the correlations in linearithmic time with the fast Walsh–Hadamard transform. Moreover, Cohn and Lempel's result from 01977 "on fast M-sequence transforms" is that after a simple transposition you can also use the FWHT to compute all the correlations with the complete output of a maximal LFSR (a so-called "M-sequence") in linearithmic time, so you can also use the cyclic shifts of an LFSR output for your atoms without losing efficiency. Probably someone else has already figured this out previously, but I hadn't found it in the literature.
— ⁂ —
I'm not sure if the quantities used in reduced affine arithmetic count as a "data structure"? They're a data type, at least, but they're not a container. The idea is that you execute some arbitrary numerical algorithm, not merely on floating-point numbers, or even on dual numbers as in forward-mode automatic differentiation, nor even yet on (min, max) intervals as in ordinary interval arithmetic, but on a vector of coefficients [a₀, a₁, a₂...aₙ], which represents a linear function a₀x₀ + a₁x₁ + a₂x₂ + ... aₙxₙ, where x₀ = 1 and each of the other xᵢ ∈ [-1, 1], so this function is really a representation of an interval. Then you can assign each of the xᵢ (except x₀ and xₙ) to be the unknown error in one of the input parameters to your algorithm, whose magnitude is determined by the aᵢ value in the value of that parameter; and when you introduce rounding error, you increase aₙ enough to account for it. (The non-reduced kind of affine arithmetic just increases n without limit to account for new roundoff errors.)
— ⁂ —
Reduced affine arithmetic has two advantages over the usual kind of interval arithmetic. First, it cancels errors correctly; if you calculate (y+1)(y+2)/(y+3) with interval arithmetic, with some uncertainty in the value of y, you usually get an unnecessarily loose bound on the result because interval arithmetic assumes that the uncertainties in the numerator and the denominator are uncorrelated, when in fact for many values of y they partly cancel out. (You can't apply this cancelation to aₙ, the error stemming from all the roundoffs in your algorithm, just the other aᵢ.) But the more interesting result is that RAA gives you a linear function that approximates the calculation result as a linear function of the inputs, which is pretty similar to calculating the gradient — but with error bounds on the approximation!
— ⁂ —
LSM trees are only about as "obscure" as bloom filters, since they underlie several prominent filesystems, LevelDB, and most of the world's search engines, but if you don't know about bloom filters, you might not know about LSM trees either. I wrote a tutorial explanation of LSM trees in https://github.com/kragen/500lines/tree/master/search-engine, though the name "LSM tree" hadn't yet gone mainstream.
Binary array sets, as described in https://www.nayuki.io/page/binary-array-set, are closely related to LSM trees, to the point that you could describe them as an application of LSM trees. They are a simple data structure for the exact version of the problem bloom filters solve approximately: maintaining a set S of items supporting the operations S.add(item) and S.contains?(item). Insertion (.add) is amortized constant time, and membership testing (.contains?) is O(log² N).
— ⁂ —
A different and more efficient data structure for the exact set membership problem, limited to the case where the items to be stored are up to M integers in the range [0, N), supports constant-time creation, clearing, insertion, size measurement, and membership testing, and linear-time enumeration, but I think cannot be implemented in modern standard C because of its rules about reading uninitialized data. (By allowing creation to be linear time you can implement it in standard C.) It uses two arrays, A[M] and B[N] and a variable n, and i is a member of the set iff B[i] < n ∧ A[B[i]] == i, from which it is straightforward to work out the other methods.
I don't remember what this data structure is called, but I definitely didn't invent it. I described it and some uses for it in https://dercuano.github.io/notes/constant-time-sets-for-pixe.... You can associate additional values with this structure to use it as a sparse array.
Even though a trie is pretty standard and expected (to be known) these days it was my first deep dive into more exotic data structures after an interview question about implementing T9 that stumped me many years ago.
https://github.com/Azeem112/tries-T9-Prediction
Concurrent tries with non-blocking snapshots [0]
Say that you have a dataset that needs to be ordered, easily searchable, but is also updated quite frequently. Fast accesses are a pain if you decide to use traditional read-write locks.
Ctries are entirely lock-free, thus there is no waiting for your read operations when an update is happening, i.e. you run lookups on snapshots while updates happen.
They are also a lot of fun to implement, especially if you aren't familiar with lock-free algorithms! I did learn a lot doing it myself [1]
[0] http://aleksandar-prokopec.com/resources/docs/ctries-snapsho...
[1] https://github.com/mabeledo/ctrie-java
Equality graphs (e-graphs) for theorem proving and equality saturation and other equality-related things.
They're awesome data structures that efficiently maintain a congruence relation over many expressions
> At a high level, e-graphs extend union-find to compactly represent equivalence classes of expressions while maintaining a key invariant: the equivalence relation is closed under congruence.
e.g. If I were to represent "f(x)" and "f(y)" in the e-graph, and then said "x == y" (merged "x" and "y" in the e-graph), then the e-graph, by congruence, would be able to tell me that "f(x) == f(y)"
e.g. If I were to represent "a(2/2)", in the e-graph, then say "2/2 == 1", and "x1 == x", by congruence the e-graph would know "a*(2/2) == a" !
The most recent description of e-graphs with an added insight on implementation is https://arxiv.org/pdf/2004.03082.pdf to the best of my knowledge.
P.S: I'm currently implementing them in Haskell https://github.com/alt-romes/hegg
https://github.com/davidfowl/AspNetCoreDiagnosticScenarios/b...
Somewhat along these lines, I have formed a concept forcedly called "differentially composable string", or "deposed string", or more precise "poor man's git".
The intended use case is to obtain a compact representation of all the historic text entered into an input field (notes, comments, maybe long-form): all the stages of the text, where a stage is a tuple [add/remove, start_index, text/end_index]. Once you get the stages from the deposed string as JSON, you could transform them however you want then load them into a new deposed string.
You can read more on GitHub: https://github.com/plurid/plurid-data-structures-typescript#... or play around on my note-taking app implementing deposed strings and more: https://denote.plurid.com
My favorite one that I've had the chance to use professionally is the Marisa trie[0].
Context is a data scientist had written a service that essentially was just lookups on a trie. He'd left and the service was starting to have memory problems so I dug in and swapped the implementation. Iirc swapping the trie implementation changed memory usage from 8gb to 100mb and sped everything up as well.
The actual data structure is equivalent to a trie, but cannot be modified once it's been built (I think it may be the same as a LOUDS trie, I don't remember the specifics)
[0] https://github.com/s-yata/marisa-trie
This. Roughly a year ago I got interested in efficient immutability for my write-from-scratch-in-C Lisp [0] and started to write a HAMT implementation in C [1], along with a (somewhat hacky, you have been warned) benchmarking suite [2].
The docs are only 70% done (in particular the "putting it all together" part is missing) but it has been a really interesting and enlightening journey so far and can only recommend embarking on this path to everyone.
[0]: https://github.com/mkirchner/stutter
On sketches, there is a genre of structure for estimating histogram-like statistics (median, 99th centile, etc) in fixed space, which i really like. Two examples:
t-digest https://github.com/tdunning/t-digest
DDSketch https://github.com/DataDog/sketches-java
An alternative streaming method due to Arandjelović, Pham, Venkatesh based on maximum entropy: https://ieeexplore.ieee.org/document/6971097 and implementation in C: https://github.com/dressipi/apv-median
The BK-Tree, which allows fast querying of "close" matches, such as Hamming distance (number of bits different). http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK...
I wrote a Python library implementing them a number of years ago: https://github.com/benhoyt/pybktree
Also related: Levenshtein automata - automata for words that match every word within a given Levenshtein distance. The intersection of a Levenshtein automaton of a word and a DAWG gives you an automaton of all words within the given edit distance.
I haven't done any Java in years, but I made a Java package in 2013 that supports: DAWGs, Levenshtein automata and perfect hash automata:
https://github.com/danieldk/dictomaton
https://github.com/facebook/folly/blob/main/folly/docs/Packe...
Is pretty rad.
The parent mentioned Bloom Filters, HyperLogLog-type stuff is on that family tree and also very interesting and very useful.
> Good use-case: routing. Say you have a list of 1 million IPs that are [deny listed].
Apparently, bloom filters make for lousy IP membership checks, read: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/
CritBit Trie [0] and possibly Allotment Routing Table (ART) are better suited for IPs.
[0] https://github.com/agl/critbit
[1] https://web.archive.org/web/20210720162224/https://www.harig...
Shameless plug, I also maintain an OCaml implementation of egraphs (named ego) at https://github.com/verse-lab/ego
While the most popular implementation at the moment seems to be egg in Rust, I find that OCaml serves as a much more ergonomic environment for quickly prototyping out uses of egraphs in practice. As a bonus, ego also shares the same logical interface as egg itself, so once you've finalised your designs, you shouldn't have much trouble porting them to egg if you need the performance gains.
This is clever, otherwise you have to coordinate your cache setter and your async function call between potentially many concurrent calls. There are ways to do this coordination though, one implementation I've borrowed in practice in python is modes stampede decorator: https://github.com/ask/mode/blob/master/mode/utils/futures.p...
So the self.N is the product number of the nested loops, you can increment this by 1 each time to get each product of the nested loops.
We can load balance the loops and schedule the N to not starve the outer loops.
So rather than that sequence, we can generate 000, 111, 222, 010, 230, 013 and so on.
Load balanced loops means you can progress on multiple items simultaneously, concurrently. I combined concurrent loops with parallel loops with multithreading. I plan it to be a pattern to create incredibly reactive frontends and backends with low latency to processing. Many frontends lag when encrypting, compressing or resizing images, it doesn't need to be that slow. IntelliJ doesn't need to be slow with concurrent loops and multithreading.
See https://github.com/samsquire/multiversion-concurrency-contro...
Loops are rarely first class citizens in most languages I have used and I plan to change that.
I think I can combine your inspiration of gray codes with this idea.
I think memory layout and data structure and algorithm can be 3 separate decisions. I am yet to see any developers talk of this. Most of the time the CPU is idling waiting for memory, disk or network. We can arrange and iterate data to be efficient.
So the self.N is the product number of the nested loops, you can increment this by 1 each time to get each product of the nested loops.
We can load balance the loops and schedule the N to not starve the outer loops.
So rather than that sequence, we can generate 000, 111, 222, 010, 230, 013 and so on.
Load balanced loops means you can progress on multiple items simultaneously, concurrently. I combined concurrent loops with parallel loops with multithreading. I plan it to be a pattern to create incredibly reactive frontends and backends with low latency to processing. Many frontends lag when encrypting, compressing or resizing images, it doesn't need to be that slow. IntelliJ doesn't need to be slow with concurrent loops and multithreading.
See https://github.com/samsquire/multiversion-concurrency-contro...
Loops are rarely first class citizens in most languages I have used and I plan to change that.
I think I can combine your inspiration of gray codes with this idea.
I think memory layout and data structure and algorithm can be 3 separate decisions. I am yet to see any developers talk of this. Most of the time the CPU is idling waiting for memory, disk or network. We can arrange and iterate data to be efficient.
Yeah, saves you from thundering herd problems
https://github.com/ben-manes/caffeine cache does something similar by caching the future that gets returned on look-ups if the value is still being computed
I wrote a version of this with Elixir: https://github.com/bschaeffer/til/tree/master/elixir/gen_ser...
Didn't know what to call it but PromiseMaps is nice name for it.
Years ago as part of my thesis research I created a rather obscure family of data structures called DFI Filters or DFilters for short. The work centers around indexing typed trees such as abstract syntax trees or a web browser DOM such that you can answer arbitrary queries of the form "give me the set of all descendants of node P that are of type T" in something that in practice collapses to O(1) in the number of tree nodes. There are several versions of the data structure, but the general setup is a sort of "tree of trees" where the main tree is a binary search tree organized based on the depth-first indices of the nodes in the tree being indexed, and there are links into each type-specific variant of the main tree (in other words, simplified versions of the main tree containing only one type). The key intuition behind the whole thing, and the reason I called them DFI Filters, is the fact that if you are at some particular node in a tree, and you know ahead of time the depth first indices of your node and it's siblings, you actually already know exactly how many descendents your node has based on the difference in the DFI number between your node and its depth-first successor. Then you can build a variety of indexing approaches and data structures based on this insight -- I came up with ones that do it in truly constant time but are expensive to update as an undergrad, and in grad school I was able to build a version that updates on the fly but still retains ammortized O(1) for querying and ammortized O(m) for updating where m is the size of the update.
By the way if you're curious how I can get constant time when I'm returning a set of descendants, it's because I can give you the size and pointers to the first and last elements right off the bat.
The link to the original paper seems to be down (looking into it), but you can find the master's thesis covering all variants here: https://github.com/sam0x17/hierarch_old/blob/master/Master's...
I've been working on a rust implementation lately as well. There are a number of applications for DFilters including fast file-system searching, DOM traversal, very fast static analysis on abstract syntax trees, and more.
I wrote a Swift client library for doing exactly that, though I called the trick "multiplexing" for lack of a better term. The library uses callbacks, no promises/futures (yet). It also provides caching of the results with TTL. Shameless self-promo [1]
[1] https://github.com/crontab/Multiplexer
I'm trying to create a first class citizen of loops and trying to improve software responsiveness.
There's two ideas: concurrent loops and userspace scheduling and preemption.
Nested loops can be independently scheduled. I wrote a M:N userspace scheduler[2] and it does something simple. You can interrupt a thread that is in a hot loop by changing its limit variable to the end. You don't need to slow down a hot loop by placing an if statement or checking if X number of statements executed. (Many runtimes do this to implement scheduling and you don't need to do it this way)
Golang schedules away from a goroutine by checking during stack expansion if the thread has used its timeslice.
I think this simple observation is really powerful. The critical insight is that frontend performance can be drastically improved by reducing latency from the user's perspective. Did you ever notice that the cancel button rarely cancels immediately? Or resizing an image is slow and gives no feedback or encrypting gives no feedback?
By having a watching thread interrogate the output buffer, we can create GUIs that visually do things and provide observability to what the computer is doing. Imagine watching a resize operation occur in real time. Or encryption. Or network communication.
One of my ideas of concurrent loops is "cancellation trees"[1], if you model every behaviour of a piece of software as a tree of concurrent loops that are reentrant - as in they never block and each call is a loop iteration of a different index, you can create really responsive low latency software. If you cancel a branch of the tree, you can cancel all the loops that are related to that branch. It's a bit like a tree of processes from PID 0 or loops as lightweight green threads/goroutines.
So as you're moving around in your text editor or browser, if you invalidate the current action - such as press ESCAPE while Intellisense is trying to find related code, you can interrupt all the loops that fanned out from that GUI operation.
Telling the computer to stop doing what it is doing and observability are two key weaknesses of modern computing. GUIs do not always accurately communicate what the computer is doing and you usually need to wait for the computer to finish before it shows you what it is doing. I am sure the cancellation token could be extended to follow this idea.
If you liked this comment, check out my profile to links to my ideas documents.
1: https://github.com/samsquire/ideas4/blob/main/README.md#120-...
If you are in the .NET space I suggest you to take a look at FusionCache. It has cache stampede protection built in, plus some other nice features like a fail-safe mechanism and soft/hard timeouts https://github.com/jodydonetti/ZiggyCreatures.FusionCache
Succinct Data Structures [0] [1]. It encompass many different underlying data structure types but the overarching idea is that you want small data size while still keeping "big O" run time.
In other words, data structures that effectively reach a 'practical' entropy lower bound while still keeping asymptotic run time.
[0] https://en.wikipedia.org/wiki/Succinct_data_structure
[1] https://github.com/simongog/sdsl-lite
If you enjoyed XOR filters, you might also like ribbon filters, something that I had the pleasure of working on last year. They share the basic idea of using a system of linear equations, but instead of considering 3 random positions per key, the positions to probe are narrowly concentrated along a ribbon with a typical width of 64. This makes them far more cache-efficient to construct and query.
By purposefully overloading the data structure by a few per cent and bumping those items that cannot be inserted as a result of this overloading to the next layer (making this a recursive data structure), we can achieve almost arbitrarily small space overheads: <1% is no problem for the fast configurations, and <0.1% overhead with around 50% extra runtime cost. This compares to around 10% for XOR filters and ≥ 44% for Bloom filters.
In fact, I'm going to present them at a conference on Monday - the paper is already out: https://drops.dagstuhl.de/opus/volltexte/2022/16538/pdf/LIPI... and the implementation is at https://github.com/lorenzhs/BuRR/. I hope this isn't too much self-promotion for HN, but I'm super hyped about this :)
https://github.com/tc39/proposal-function-memo
This might be relevant to this exact pattern
const getThing = (async function (arg1, arg2) {
It might be easier to think about it as a stack, rather than a tree. Each element of the stack represents a subtree -- a perfect binary tree. If you ever have two subtrees of height k, you merge them together into one subtree of height k+1. Your stack might already have another subtree of height k+1; if so, you repeat the process, until there's at most one subtree of each height.
This process is isomorphic to binary addition. Worked example: let's start with a single leaf, i.e. a subtree of height 0. Then we "add" another leaf; since we now have a pair of two equally-sized leaves, we merge them into one subtree of height 1. Then we add a third leaf; now this one doesn't have a sibling to merge with, so we just keep it. Now our "stack" contains two subtrees: one of height 1, and one of height 0.
Now the isomorphism: we start with the binary integer 1, i.e. a single bit at index 0. We add another 1 to it, and the 1s "merge" into a single 1 bit at index 1. Then we add another 1, resulting in two 1 bits at different indices: 11. If we add one more bit, we'll get 100; likewise, if we add another leaf to our BNT, we'll get a single subtree of height 2. Thus, the binary representation of the number of leaves "encodes" the structure of the BNT.
This isomorphism allows you to do some neat tricks, like calculating the size of a Merkle proof in 3 asm instructions. There's some code here if that helps: https://github.com/lukechampine/us/blob/master/merkle/stack....
You could also check out section 5.1 of the BLAKE3 paper: https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blak...