Ask HN: What are some cool but obscure data structures you know about? • Hacker News Board

Re: Ask HN: What are some cool but obscure data structures you know about?

#341

Post by mijoharas » Fri, Jul 22, 2022, 8:07 AM UTC

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

Re: Ask HN: What are some cool but obscure data structures you know about?

#342

Post by sgtnoodle » Fri, Jul 22, 2022, 8:07 AM UTC

xxs wrote: post #310

sgtnoodle wrote: post #30

Disruptor queues are also fun. They are lock free multi-producer multi-consumer circular buffers. I figured out the basics on my own in a vacuum out of need, then discovered a relevant white paper. I used one to implement a fast shared memory pub-sub message bus for communicating across dozens of processes in a simulation framework.

I don't quite see how's that obscure; it's a standard circular buffer. The fast/low latency communication part comes from the busy wait (and L3 cache communication).

A standard circular buffer is only single-producer single-consumer. The producer manipulates the head and the consumer manipulates the tail.

Extending a circular buffer to allow multiple consumers is relatively straight forward; you just give each consumer its own tail and accept the loss of back pressure.

Extending it to allow multiple producers without introducing locks is where the complexity shoots up drastically.

But yes, the reason why you would want something like this is to have the semantics of message passing with the performance of direct IPC between userspace processes without going through the kernel.

Re: Ask HN: What are some cool but obscure data structures you know about?

#343

Post by phkahler » Fri, Jul 22, 2022, 8:10 AM UTC

trebcon wrote: post #105

vvanders wrote: post #42

Earlier quoted context omitted.

Realtime collision detection[1] has a fantastic chapter in this with some really good practical examples if I remember right. Great book, I used to refer to it as 3D "data structures" book which is very much in theme with this thread. [1] https://www.amazon.com/Real-Time-Collision-Detection-Interac...

The implicit grid data structure from there is a personal favorite of mine. I used it in a game once and it performed incredibly well for our use case. It's a bit too complicated to totally summarize here, but it uses a bit per object in the scene. Then bit-wise operations are used to perform quick set operations on objects. This data structure got me generally interested in algorithms that use bits for set operation…

I spent a lot of time optimizing an octree for ray tracing. It is my favorite "spatial index" because it's the only one I know that can be dynamically updated and always results in the same structure for given object placement.

Re: Ask HN: What are some cool but obscure data structures you know about?

#344

Post by FnuGk » Fri, Jul 22, 2022, 8:11 AM UTC

romes wrote: post #331

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 re…

Isnt that the building blocks of logic based programming languages like Prolog?

Re: Ask HN: What are some cool but obscure data structures you know about?

#345

Post by Shorel » Fri, Jul 22, 2022, 8:13 AM UTC

skrebbel wrote: post #297

Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript. When caching the result of an expensive computation or a network call, don't actually cache the result, but cache the promise that awaits the result. Ie don't make a Map but a Map > This way, if a new, uncached key gets requested twice…

I know this as memoization with lazy evaluation, nothing new, but at the same time very useful, and I would argue, it is very CS.

Re: Ask HN: What are some cool but obscure data structures you know about?

#346

Post by Fiahil » Fri, Jul 22, 2022, 8:14 AM UTC

Append-Log. A grow-only linked list where you can only append elements to it.

Good use-case: Lock-free concurrent reads are allowed, because there is no way committed content could change. Writes need to be Linearizable (so locking is required). Given this property, this data structure provides faster reads than a Mutex> and similar write perfs.

Bonus section: Provides broadcast broadcast capabilities if used as channel.

Re: Ask HN: What are some cool but obscure data structures you know about?

#347

Post by robertsdionne » Fri, Jul 22, 2022, 8:16 AM UTC

tialaramex wrote: post #52

Hazard Pointers are an interesting concurrent data structure. Suppose we've got a lot of Doodads, let's say there's a Graph of ten million Doodads, and a whole bunch (dozens? hundreds?) of threads are poking around in this same graph, maybe looking at Doodads and sometimes (but not often) removing them from the Graph. What happens if my thread is looking at a Doodad, and meanwhile a different thread removes it from t…

Seems to me to be quite similar to the virtual pages in Bw-Trees: https://www.microsoft.com/en-us/research/publication/the-bw-...

Re: Ask HN: What are some cool but obscure data structures you know about?

#348

Post by bruce343434 » Fri, Jul 22, 2022, 8:18 AM UTC

jfim wrote: post #139

jiggawatts wrote: post #131

Earlier quoted context omitted.

To an extent, the B-Tree data structure (and its variants) are cache oblivious. They smoothly improve in performance with more and more cache memory, and can scale down to just megabytes of cache over terabytes of disk. The issue is that the last tree level tends to break this model because with some caching models it is "all or nothing" and is the biggest chunk of the data by far. There are workarounds which make it…

There are also Judy arrays: https://en.wikipedia.org/wiki/Judy_array

This sounded promising but then I saw a performance benchmark [1] that was done on a pentium(!) with a very suboptimal hash table design compared to [2] and [3].

The Judy site itself [4] is full of phrases like "may be out of date", when the entire site was last updated in 2004. If it was already out of date in 2004...

It seems that Judy arrays are just kind of a forgotten datastructure, and it doesn't look promising enough for me to put in effort to revive it. Maybe someone else will?

[1] http://www.nothings.org/computer/judy/

[2] https://probablydance.com/2017/02/26/i-wrote-the-fastest-has...

[3] https://probablydance.com/2018/05/28/a-new-fast-hash-table-i...

[4] http://judy.sourceforge.net/

Re: Ask HN: What are some cool but obscure data structures you know about?

#349

Post by withinboredom » Fri, Jul 22, 2022, 8:18 AM UTC

ralusek wrote: post #312

skrebbel wrote: post #297

Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript. When caching the result of an expensive computation or a network call, don't actually cache the result, but cache the promise that awaits the result. Ie don't make a Map but a Map > This way, if a new, uncached key gets requested twice…

I have written many tools that do something like this, very useful. Just gotta be careful with memory leaks, so (for a TS example) you might want to do something like this: const promiseMap > = new Map(); async function keyedDebounce (key: string, fn: () => R) { const existingPromise = promiseMap.get(key); if (existingPromise) return existingPromise; const promise = new Promise(async (resolve) => { const result = awa…

Won’t JS garbage collect orphaned references? Why is this necessary?

Re: Ask HN: What are some cool but obscure data structures you know about?

#350

Post by xigoi » Fri, Jul 22, 2022, 8:24 AM UTC

physicsguy wrote: post #256

jiggawatts wrote: post #25

Cache-Oblivious Data Structures: https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency/cost of data access as the data size grows. This can't be ignored, no matter how much we would like to hand-wave it away, because physics gets in the way. A way to think about it is that a CPU core is like a…

I spent a long time looking at an algorithm for long range force calculations called the Fast Multipole Method which is O(N) and found that practically it couldn't compete against an O(N log N) method we used that involved FFTs because the coefficient was so large that you'd need to simulate systems way bigger than is feasible in order for it to pay off because of cache locality, etc.

https://en.wikipedia.org/wiki/Galactic_algorithm