Subject: Re: [httpwg/http-extensions] [cache digests] Eliminate requirement that the digest size is a power of 2 (#607)

From: HTTP issue updates <[email-masked]>
Date: Thu, 03 May 2018 15:19:10 -0700

@yoavweiss Thank you for noticing and raising the issue.

I think the proposed solution is plausible. OTOH, I am not sure if we need the flexibility.

I'd assume that a client would not resize the hash every time it adds / removes an entry. I'd rather expect it to resize it based on exponential backoff. That means that in the average case, we will not be transferring a optimally-sized Cuckoo hash anyways. Considering that, I fear having 1-bit overhead for every entry might actually lead us to seeing a bigger hash in practice.

Note also that allowing a table size other than power-of-two increases the CPU cost since it means that we cannot rely on bit operations for calculating modulo.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/607#issuecomment-386454262

---

From: HTTP issue updates <[email-masked]>
Date: Fri, 04 May 2018 03:07:12 -0700

This is not about resizing the table, but about finding an alternative index in case of a collision.

Alternatively to my approach which adds an extra bit, @bdupras and @beala have an alternative [approach](https://github.com/bdupras/guava-probably/blob/10a738234de3830c8bb0dd8d1617e0df123607cf/src/main/java/com/duprasville/guava/probably/CuckooStrategyMurmurBealDupras32.java#L134-L169) for Guava-Probably, which seems to be providing the same benefits without the overhead.

Essentially (IIUC), they calculate a predicable but randomly distributed number from the fingerprint and use that as an offset from the original index. They make sure that it doesn't fall on the original index by requiring that the offset is odd and that the size of the digest is even.

> Note also that allowing a table size other than power-of-two increases the CPU cost since it means that we cannot rely on bit operations for calculating modulo.

That's a good point, and implementations can choose to stick with power-of-two digest sizes. But figuring out a way to remove that as a requirement seems like a win. (especially if we don't have to pay the "extra bit per fingerprint" tax after all)

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/607#issuecomment-386557574

---

From: HTTP issue updates <[email-masked]>
Date: Sat, 05 May 2018 12:06:52 +0000 (UTC)

I'm curious, what digest sizes are you anticipating from implementations?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/607#issuecomment-386800978

---

From: HTTP issue updates <[email-masked]>
Date: Sat, 05 May 2018 16:10:27 +0000 (UTC)

I thought it might be useful to post a plain english explanation of the indexing strategy @bdupras and I proposed:

The property that we need to maintain is that the primary and secondary indices can be calculated in terms of each other (ie, the only info we have available is their position in the table, and the fingerprint). We maintain this property in the following way. 

First, we calculate an offset, which is based on the fingerprint. Crucially, this offset is always odd: `offset = makeOdd(hash(fingerprint))`. 

This offset is then either subtracted or added to the current position to get the other index. If the current index is odd, it's added. If it's even, it's subtracted. Since the offset is always the same, this jumps between the two possible indices. Further, because adding or subtracting an odd number always flips the evenness or oddness of a number, this guarantees that one position is always even and one is always odd. 

In pseudo code, it looks like this:

```
makeOdd(x) = x    [if x is odd]
             x+1  [if x is even]

flipIndex(currentIndex) = currentIndex + makeOdd(hash(fingerprint))   [if index is odd]
                          currentIndex - makeOdd(hash(fingerprint))   [if index is even]
```

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/607#issuecomment-386816198

---

From: HTTP issue updates <[email-masked]>
Date: Tue, 08 May 2018 22:46:27 -0700

@bdupras 
> I'm curious, what digest sizes are you anticipating from implementations?

The anticipation is that we would have typically up to hundreds (but not thousands) of entries. Please refer to https://github.com/httpwg/wg-materials/blob/gh-pages/ietf100/cache-digest.pdf.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/607#issuecomment-387626902

---

From: HTTP issue updates <[email-masked]>
Date: Tue, 08 May 2018 22:55:38 -0700

@beala That's interesting. Thank you for the explanation.

OTOH, I am not sure if it is actually optimal compared to using XOR for a table having a size of power-of-two.

The approach you described distributes the secondary index to N / 2 entries where N is the size of the table. IMO, it is essentially the same as omitting the last bit of the fingerprint (and hard-coding it as `1` instead) when we use XOR-based approach.

What I am trying to state here is that while I can understand the potential benefit of using the approach for tables that do not have the size of power-of-two, I do not see a benefit for the cache-digest use-case adopting that approach, under the assumption that the clients would resize the table using exponential backoff.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/httpwg/http-extensions/issues/607#issuecomment-387628389