Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

601–610 of 772 posts

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

#601

Post by polyrand »

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…

This is only tangentially related to:

> you avoid computing/fetching the same value twice

But this problem comes up in reverse proxies too. In Nginx, you can set the `proxy_cache_lock`[0] directive to achieve the same effect (avoiding double requests).

[0]: https://nginx.org/en/docs/http/ngx_http_proxy_module.html#pr...

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

#602

Post by PartiallyTyped »

hansvm wrote: post #578

Succinct data structures in general are interesting. They use close to the information theoretic bound for a given problem and still support fast operations -- a decent mental model is that they're able to jump to a roughly correct place and (de)compress the data locally. A good example is a wavelet tree. Suppose you have a text of length N comprised of an alphabet with C characters and wish to execute full-text patt…

Another example is distance oracles. A distance oracle is a two stage object, in one stage creates a cache of distances, and in the other it allows us to query the cache. The oracle gives an approximate solution to the distance between any two nodes while avoiding the quadratic memory requirement to something in order of nlogk with k query steps.

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

#603

Post by cpburns2009 »

cauthon wrote: post #600
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…

What is a promise in this context?

A promise is an object representing an asynchronous result. Some languages, such as Python, call them futures. A promise object will typically have methods for determining if result is available, getting the result if it is, and registering callback functions to be called with the result when it's available.

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

#604

Post by sgtnoodle »

xxs wrote: post #356
sgtnoodle wrote: post #342

Earlier quoted context omitted.

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…

>Extending it to allow multiple producers without introducing locks is where the complexity shoots up drastically. You can have a single tail with an atomic add, and that's pretty much it. The consumer needs to know, if the data is available, so there has to be a serialization point that with each producer has to wait - effectively a locking mechanism... or the consumer has to check all the producers progress. It doe…

> You can have a single tail with an atomic add, and that's pretty much it.

That's the primary difference. In a disruptor queue, there's two tails. The first one is used for producers to allocate space in the buffer to write to, and the second one is used to commit it so that it's available to consumers.

It's true that there is a small amount of necessary synchronization across producers, because a producer can't commit its data before a concurrent producer earlier in the buffer does, and can end up spinning on an atomic compare-and-exchange. They can both independently write to their allocated parts of the buffer freely before that point, though, so in practice it's not a contention point.

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

#605

Post by 3wolf »

A minor quibble with your use-case explanation: The advantage of a bloom filter isn't strictly time complexity. For example, a hash table would also have constant lookup time (best case), and would give a definitive answer on set membership. However, to store 1 million IPv6 addresses would take 16 MB. You can see very quickly that this would not scale very well to, say, a billion addresses stored in-memory on a laptop. With a bloom filter, we can shrink the amount of storage space required* while maintaining an acceptable, calculable false positive rate.

* IP addresses actually aren't a great use case for basic bloom filters, as they're fairly storage efficient to begin with, as opposed to a url for example. Taking your example, say we need to store 1 million IP addresses in our bloom filter and we're okay with a ~1% false positive rate. Well then, if we use a bloom filter with 2^23 bits (1 MB), the optimal number of hash functions is (2^23)/(10^6)*ln(2) = 6, yielding a false positive rate of (1 - exp(-6* 10^6 /2^23))^6 = ~1.8%. So we're using 6% of the storage space, but with a nearly 2% false positive rate.

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

#606

Post by Fiahil »

charleslmunger wrote: post #567
Fiahil wrote: post #346

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

I think this can be done completely lock free with almost same number of memory barriers as a mutex when writing - read the tail pointer (acquire), append your node using CAS(release), then update the tail pointer with CAS (release). For reads, start with an acquire read of the tail pointer, which will make all preceding writes to the list visible to you. Then you can read the list all you want up until you hit the n…

> read the tail pointer (acquire)

> append your node using CAS(release)

> update the tail pointer with CAS (release).

I thought as well, but, when I wrote that impl there was no way to shortcut the 2 releases into a single atomic operation. That ended up creating forks or loosing blocks.

I tested that model and a few variations with loom (https://docs.rs/loom/latest/loom/), so I'm confident that it didn't work. However, I also think that a working design might exist. I just haven't found it yet :)

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

#607

Post by samsquire »

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-...

2: https://github.com/samsquire/preemptible-thread

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

#608

Post by talos2110 »

polyrand wrote: post #601
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…

This is only tangentially related to: > you avoid computing/fetching the same value twice But this problem comes up in reverse proxies too. In Nginx, you can set the `proxy_cache_lock`[0] directive to achieve the same effect (avoiding double requests). [0]: https://nginx.org/en/docs/http/ngx_http_proxy_module.html#pr...

That right there is Cache Stampede[0] prevention.

[0]: https://en.wikipedia.org/wiki/Cache_stampede

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

#609

Post by jcadam »

How about the R-Tree, used for accessing/searching spatial data: https://en.wikipedia.org/wiki/R-tree

Maybe not so obscure if you've worked in the geospatial realm.

I actually had a job interview once that asked me to implement an R-Tree from scratch in C++ as a homework assignment - I didn't get that job :)

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

#610

Post by fumblebee »

MichaelMoser123 wrote: post #478
jtolmar wrote: post #171

The union-find data structure / algorithm is useful and a lot of fun. The goal is a data structure where you can perform operations like "a and b are in the same set", "b and c are in the same set" and then get answers to questions like "are a and c in the same set?" (yes, in this example.) The implementation starts out pretty obvious - a tree where every element either points at itself or some thing it was merged wi…

Can you give some examples where union-find is applied to great benefit?

A while back I had to perform an entity resolution task on several million entities.

We arrived at a point in the algorithm where we had a long list of connected components by ids that needed to be reduced into a mutually independent set of components, e.g. ({112, 531, 25}, {25, 238, 39, 901}, {43, 111}, ...)

After much head banging about working out way to do this that wouldn't lead to an out-of-memory error, we found the Disjoint Set Forest Data Structure and our prayers were answered.

I was very grateful for it!

Post reply on HN