ucx
ucx copied to clipboard
openucx
UCS: adding multi-dimensional hash tables
@shamisp afraid not, and I don't expect it'll be resolved soon. I'm posting stuff I plan to upstream once it does - I just don't seem to have permissions to put the "CLA missing" label...
how is it different from using regular khash with a custom key type that contains multiple values?
how is it different from using regular khash with a custom key type that contains multiple values?
This is the result of some research, and the paper is still in progress, but the gist is the difference in iteration. A multi-dimensional hash-table would only access the keys matching the query vector in every dimension (Figure 1), whereas this implementation has a special way to iterate over neighboring vectors (Figure 2) in order to locate the nearest neighbor. I plan to use this as an advanced form of caching (in a separate commit).
IIUC, the expected lookup performance of the special multi-dim implementation should be better than default khash with a vector key?
IIUC, the expected lookup performance of the special multi-dim implementation should be better than default khash with a vector key?
No, I'm afraid the lookup is not faster, just different (and in fact typically slower). For example, if both dimensions fall into bin #1 in the figures above, the default khash with vector keys will check V3 and V4, whereas this special 2D khash will check V3 - V8. The only advantage (and purpose) of this special multi-dimensional khash-based data-structure is a fast nearest-neighbor lookup.
@alex--m Can you give a bit more details how it will be used ? AKA how we will benefit from nearest neighbor lookup speedup.
@alex--m Can you give a bit more details how it will be used ? AKA how we will benefit from nearest neighbor lookup speedup.
Sure. The basic Idea is this: caches tend to be all-or-nothing matches, so if you're looking up, say, a past request, you only get identical past requests. In such case, the nearest-neighbor lookup allow you to find a "similar" past request and modify it, rather than creating a brand new request (which is presumably more expensive, otherwise this makes little sense). The speedup primarily comes from (a) re-using similar past objects rather than creating new ones, and secondarily from the reduced memory consumption which is the result of this recycling. Now this begs the question: what objects are so hard to create, justifying all this? one answer is QPs, but there are others.
@alex--m Sounds like some cache approximation. Can you please give us a bit more specific what is the follow up patch and how it will be useful for UCX.