[dpdk-dev] [PATCH v2] mempool: improve cache search

[Bruce Richardson]

On Tue, Jul 07, 2015 at 06:17:05PM +0100, Zoltan Kiss wrote:
> 
> 
> On 02/07/15 18:07, Ananyev, Konstantin wrote:
> >
> >
> >>-----Original Message-----
> >>From: dev [mailto:dev-bounces at dpdk.org] On Behalf Of Zoltan Kiss
> >>Sent: Wednesday, July 01, 2015 10:04 AM
> >>To: dev at dpdk.org
> >>Subject: [dpdk-dev] [PATCH v2] mempool: improve cache search
> >>
> >>The current way has a few problems:
> >>
> >>- if cache->len < n, we copy our elements into the cache first, then
> >>   into obj_table, that's unnecessary
> >>- if n >= cache_size (or the backfill fails), and we can't fulfil the
> >>   request from the ring alone, we don't try to combine with the cache
> >>- if refill fails, we don't return anything, even if the ring has enough
> >>   for our request
> >>
> >>This patch rewrites it severely:
> >>- at the first part of the function we only try the cache if cache->len < n
> >>- otherwise take our elements straight from the ring
> >>- if that fails but we have something in the cache, try to combine them
> >>- the refill happens at the end, and its failure doesn't modify our return
> >>   value
> >>
> >>Signed-off-by: Zoltan Kiss <zoltan.kiss at linaro.org>
> >>---
> >>v2:
> >>- fix subject
> >>- add unlikely for branch where request is fulfilled both from cache and ring
> >>
> >>  lib/librte_mempool/rte_mempool.h | 63 +++++++++++++++++++++++++---------------
> >>  1 file changed, 39 insertions(+), 24 deletions(-)
> >>
> >>diff --git a/lib/librte_mempool/rte_mempool.h b/lib/librte_mempool/rte_mempool.h
> >>index 6d4ce9a..1e96f03 100644
> >>--- a/lib/librte_mempool/rte_mempool.h
> >>+++ b/lib/librte_mempool/rte_mempool.h
> >>@@ -947,34 +947,14 @@ __mempool_get_bulk(struct rte_mempool *mp, void **obj_table,
> >>  	unsigned lcore_id = rte_lcore_id();
> >>  	uint32_t cache_size = mp->cache_size;
> >>
> >>-	/* cache is not enabled or single consumer */
> >>+	cache = &mp->local_cache[lcore_id];
> >>+	/* cache is not enabled or single consumer or not enough */
> >>  	if (unlikely(cache_size == 0 || is_mc == 0 ||
> >>-		     n >= cache_size || lcore_id >= RTE_MAX_LCORE))
> >>+		     cache->len < n || lcore_id >= RTE_MAX_LCORE))
> >>  		goto ring_dequeue;
> >>
> >>-	cache = &mp->local_cache[lcore_id];
> >>  	cache_objs = cache->objs;
> >>
> >>-	/* Can this be satisfied from the cache? */
> >>-	if (cache->len < n) {
> >>-		/* No. Backfill the cache first, and then fill from it */
> >>-		uint32_t req = n + (cache_size - cache->len);
> >>-
> >>-		/* How many do we require i.e. number to fill the cache + the request */
> >>-		ret = rte_ring_mc_dequeue_bulk(mp->ring, &cache->objs[cache->len], req);
> >>-		if (unlikely(ret < 0)) {
> >>-			/*
> >>-			 * In the offchance that we are buffer constrained,
> >>-			 * where we are not able to allocate cache + n, go to
> >>-			 * the ring directly. If that fails, we are truly out of
> >>-			 * buffers.
> >>-			 */
> >>-			goto ring_dequeue;
> >>-		}
> >>-
> >>-		cache->len += req;
> >>-	}
> >>-
> >>  	/* Now fill in the response ... */
> >>  	for (index = 0, len = cache->len - 1; index < n; ++index, len--, obj_table++)
> >>  		*obj_table = cache_objs[len];
> >>@@ -983,7 +963,8 @@ __mempool_get_bulk(struct rte_mempool *mp, void **obj_table,
> >>
> >>  	__MEMPOOL_STAT_ADD(mp, get_success, n);
> >>
> >>-	return 0;
> >>+	ret = 0;
> >>+	goto cache_refill;
> >>
> >>  ring_dequeue:
> >>  #endif /* RTE_MEMPOOL_CACHE_MAX_SIZE > 0 */
> >>@@ -994,11 +975,45 @@ ring_dequeue:
> >>  	else
> >>  		ret = rte_ring_sc_dequeue_bulk(mp->ring, obj_table, n);
> >>
> >>+#if RTE_MEMPOOL_CACHE_MAX_SIZE > 0
> >>+	if (unlikely(ret < 0 && is_mc == 1 && cache->len > 0)) {
> >>+		uint32_t req = n - cache->len;
> >>+
> >>+		ret = rte_ring_mc_dequeue_bulk(mp->ring, obj_table, req);
> >>+		if (ret == 0) {
> >>+			cache_objs = cache->objs;
> >>+			obj_table += req;
> >>+			for (index = 0; index < cache->len;
> >>+			     ++index, ++obj_table)
> >>+				*obj_table = cache_objs[index];
> >>+			cache->len = 0;
> >>+		}
> >>+	}
> >>+#endif /* RTE_MEMPOOL_CACHE_MAX_SIZE > 0 */
> >>+
> >>  	if (ret < 0)
> >>  		__MEMPOOL_STAT_ADD(mp, get_fail, n);
> >>  	else
> >>  		__MEMPOOL_STAT_ADD(mp, get_success, n);
> >>
> >>+#if RTE_MEMPOOL_CACHE_MAX_SIZE > 0
> >>+cache_refill:
> >
> >Ok, so if I get things right: if the lcore runs out of entries in cache,
> >then on next __mempool_get_bulk() it has to do ring_dequeue() twice:
> >1. to satisfy user request
> >2. to refill the cache.
> >Right?
> Yes.
> 
> >If that so, then I think the current approach:
> >ring_dequeue() once to refill the cache, then copy entries from the cache to the user
> >is a cheaper(faster) one for many cases.
> But then you can't return anything if the refill fails, even if there would
> be enough in the ring (or ring+cache combined). Unless you retry with just
> n.
> __rte_ring_mc_do_dequeue is inlined, as far as I see the overhead of calling
> twice is:
> - check the number of entries in the ring, and atomic cmpset of cons.head
> again. This can loop if an other dequeue preceded us while doing that
> subtraction, but as that's a very short interval, I think it's not very
> likely
> - an extra rte_compiler_barrier()
> - wait for preceding dequeues to finish, and set cons.tail to the new value.
> I think this can happen often when 'n' has a big variation, so the previous
> dequeue can be easily much bigger
> - statistics update
> 
> I guess if there is no contention on the ring the extra memcpy outweighs
> these easily. And my gut feeling says that contention around the two while
> loop should not be high unless, but I don't have hard facts.
> An another argument for doing two dequeue because we can do burst dequeue
> for the cache refill, which is better than only accepting the full amount.
> 
> How about the following?
> If the cache can't satisfy the request, we do a dequeue from the ring to the
> cache for n + cache_size, but with rte_ring_mc_dequeue_burst. So it takes as
> many as it can, but doesn't fail if it can't take the whole.
> Then we copy from cache to obj_table, if there is enough.
> It makes sure we utilize as much as possible, with one ring dequeue.
> 

That sounds like an approach that may work better. The cost of doing the
cmpset in the dequeue is likely to be the most expensive part of the whole operation
so we should try and minimise dequeues if at all possible.

/Bruce