[ovs-dev] [RFC 3/4] dpif-netdev: Use way-associative cache

[Wang, Yipeng1]

Thanks for the comments. Reply inlined:

>-----Original Message-----
>From: Bodireddy, Bhanuprakash
>Sent: Friday, February 23, 2018 12:56 PM
>To: Wang, Yipeng1 <yipeng1.wang at intel.com>; dev at openvswitch.org; jan.scheurich at ericsson.com
>Cc: Tai, Charlie <charlie.tai at intel.com>
>Subject: RE: [ovs-dev] [RFC 3/4] dpif-netdev: Use way-associative cache
>
>Hi Yipeng,
>
>Thanks for the patch. Some high level questions/comments.
>
>(1)  Am I right in understanding that this patch *only* introduces a new cache approach in to DFC to reduce the collisions?
>
[Wang, Yipeng] Yes, including set-associative structure and the signatures.

>(2)  Why the number of entries per Bucket is set to '8'?  With this each dfc_bucket  size is 80 bytes (16 + 64).
>        If the number of entries set to '6', the dfc_bucket size will be 60 bytes and can fit in to a cache line.
>        I assume 'DFC_ENTRY_PER_BUCKET' isn't a random picked number. Was it picked due to any benchmarks?
>
[Wang, Yipeng] Next commit (4/4) will solve this issue. Without 4/4,  I agree that cache alignment is important and 6 makes more sense.

>(3) A 2 byte signature is introduced in a bucket and is used to insert or retrieve flows in to the bucket.
>        3a. Due to the introduction of 2 byte signature the size of dfc_cache increased by 2MB per PMD thread.
[Wang, Yipeng] Yes, the next commit will alleviate the memory issue.

>        3b. Every time we insert or retrieve a flow, we have to match the packet signature(upper 16 bit RSS hash) with each entry of the
>bucket. Wondering if that slow down the operations?
[Wang, Yipeng] Yes, I saw 1-4%  throughput penalty. However, the cache collision reduced a lot and performance generally improved for most cases.
https://mail.openvswitch.org/pipermail/ovs-dev/2018-January/343029.html here I shown some results.  Note that if there is only one rule, then signature does not
help but this case is less realistic.
>
>(4)  The number of buckets depends on the number of entries per bucket.  Which of this plays an important role in reducing the
>collisions?
>        i.e Would higher number of entries per bucket reduce the collisions?
>
[Wang, Yipeng] Generally yes, but there will be diminishing returns on the collision rate reduction with more than 8 entries/bucket. Also, comparing signatures will be more costly with more entries each bucket. 

>(5) What is the performance delta observed with this new Cache implementation over 1/4 approach?
>
[Wang, Yipeng]  Please check out these numbers I generated before: https://mail.openvswitch.org/pipermail/ovs-dev/2018-January/343029.html
>Some more minor comments below.
>
>>This commit uses a way-associative cache (CD) rather than a simple single
>>entry hash table for DFC. Experiments show that this design generally has
>>much higher hit rate.
>>
>>@@ -774,11 +777,13 @@ emc_cache_init(struct emc_cache *emc)  static void
>>dfc_cache_init(struct dfc_cache *flow_cache)  {
>>-    int i;
>>+    int i, j;
>>
>>     emc_cache_init(&flow_cache->emc_cache);
>>-    for (i = 0; i < ARRAY_SIZE(flow_cache->entries); i++) {
>>-        flow_cache->entries[i].flow = NULL;
>>+    for (i = 0; i < DFC_BUCKET_CNT; i++) {
>>+        for (j = 0; j < DFC_ENTRY_PER_BUCKET; j++) {
>>+            flow_cache->buckets[i].flow[j] = NULL;
>
>[BHANU] How about initializing the signature?
>
[Wang, Yipeng] Thanks for pointing out. Functionally it should be fine since I use pointer to check entry valid or not anyway. But I will do in next version.

>>     }
>> }
>>@@ -2288,10 +2302,25 @@ dfc_insert(struct dp_netdev_pmd_thread *pmd,
>>            struct dp_netdev_flow *flow)  {
>>     struct dfc_cache *cache = &pmd->flow_cache;
>>-    struct dfc_entry *current_entry;
>>
>>-    current_entry = dfc_entry_get(cache, key->hash);
>>-    dfc_change_entry(current_entry, flow);
>>+    struct dfc_bucket *bucket = &cache->buckets[key->hash & DFC_MASK];
>>+    uint16_t sig = key->hash >> 16;
>
>[BHANU]  Am I right in assuming the below logic is to replace an already existing entry in bucket?
[Wang, Yipeng] Yes, to overwrite an entry with same signature.
>
>>+    for (int i = 0; i < DFC_ENTRY_PER_BUCKET; i++) {
>>+        if(bucket->sig[i] == sig) {
>>+            dfc_change_entry(bucket, i, flow);
>>+            return;
>>+        }
>>+    }
>
>[BHANU] The below happens if inserting in to empty bucket?
>
[Wang, Yipeng] Yes, if there is empty entry we insert there.

>+    for (int i = 0; i < DFC_ENTRY_PER_BUCKET; i++) {
>+        if(bucket->flow[i] == NULL) {
>+            bucket->sig[i] = sig;
>+            dfc_change_entry(bucket, i, flow);
>+            return;
>+        }
>+    }

Thanks.