DPDK patches and discussions
 help / color / mirror / Atom feed
From: "Mattias Rönnblom" <mattias.ronnblom@ericsson.com>
To: Jerin Jacob <jerin.jacob@caviumnetworks.com>
Cc: "Bruce Richardson" <bruce.richardson@intel.com>,
	dev@dpdk.org, "Mattias Rönnblom" <mattias.ronnblom@ericsson.com>
Subject: [dpdk-dev] [PATCH v4 08/10] event/dsw: let DSW event device sort events on dequeue
Date: Tue, 18 Sep 2018 14:45:12 +0200	[thread overview]
Message-ID: <20180918124514.10615-9-mattias.ronnblom@ericsson.com> (raw)
In-Reply-To: <20180918124514.10615-1-mattias.ronnblom@ericsson.com>

With this patch, the DSW event device will (optionally) sort the event
burst before giving it to the application. The sorting will primarily
be on queue id, and secondary on flow id.

The sorting is an attempt to optimize data and instruction cache usage
for the application, at the cost of additional event device overhead.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 drivers/event/dsw/dsw_evdev.h | 11 ++++++++
 drivers/event/dsw/dsw_event.c | 23 +++++++++++++++++
 drivers/event/dsw/dsw_sort.h  | 48 +++++++++++++++++++++++++++++++++++
 3 files changed, 82 insertions(+)
 create mode 100644 drivers/event/dsw/dsw_sort.h

diff --git a/drivers/event/dsw/dsw_evdev.h b/drivers/event/dsw/dsw_evdev.h
index 783c418bf..f6f8f0454 100644
--- a/drivers/event/dsw/dsw_evdev.h
+++ b/drivers/event/dsw/dsw_evdev.h
@@ -93,6 +93,17 @@
  */
 #define DSW_CTL_IN_RING_SIZE ((DSW_MAX_PORTS-1)*4)
 
+/* With DSW_SORT_DEQUEUED enabled, the scheduler will, at the point of
+ * dequeue(), arrange events so that events with the same flow id on
+ * the same queue forms a back-to-back "burst", and also so that such
+ * bursts of different flow ids, but on the same queue, also come
+ * consecutively. All this in an attempt to improve data and
+ * instruction cache usage for the application, at the cost of a
+ * scheduler overhead increase.
+ */
+
+/* #define DSW_SORT_DEQUEUED */
+
 struct dsw_queue_flow {
 	uint8_t queue_id;
 	uint16_t flow_hash;
diff --git a/drivers/event/dsw/dsw_event.c b/drivers/event/dsw/dsw_event.c
index f0347592d..a84b19c33 100644
--- a/drivers/event/dsw/dsw_event.c
+++ b/drivers/event/dsw/dsw_event.c
@@ -4,6 +4,10 @@
 
 #include "dsw_evdev.h"
 
+#ifdef DSW_SORT_DEQUEUED
+#include "dsw_sort.h"
+#endif
+
 #include <stdbool.h>
 #include <string.h>
 
@@ -1121,6 +1125,21 @@ dsw_port_record_seen_events(struct dsw_port *port, struct rte_event *events,
 				DSW_MAX_EVENTS_RECORDED);
 }
 
+#ifdef DSW_SORT_DEQUEUED
+
+#define DSW_EVENT_TO_INT(_event)				\
+	((int)((((_event)->queue_id)<<16)|((_event)->flow_id)))
+
+static inline int
+dsw_cmp_event(const void *v_event_a, const void *v_event_b)
+{
+	const struct rte_event *event_a = v_event_a;
+	const struct rte_event *event_b = v_event_b;
+
+	return DSW_EVENT_TO_INT(event_a) - DSW_EVENT_TO_INT(event_b);
+}
+#endif
+
 static uint16_t
 dsw_port_dequeue_burst(struct dsw_port *port, struct rte_event *events,
 		       uint16_t num)
@@ -1191,5 +1210,9 @@ dsw_event_dequeue_burst(void *port, struct rte_event *events, uint16_t num,
 	 *	0.
 	 */
 
+#ifdef DSW_SORT_DEQUEUED
+	dsw_stable_sort(events, dequeued, sizeof(events[0]), dsw_cmp_event);
+#endif
+
 	return dequeued;
 }
diff --git a/drivers/event/dsw/dsw_sort.h b/drivers/event/dsw/dsw_sort.h
new file mode 100644
index 000000000..609767fdf
--- /dev/null
+++ b/drivers/event/dsw/dsw_sort.h
@@ -0,0 +1,48 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Ericsson AB
+ */
+
+#ifndef _DSW_SORT_
+#define _DSW_SORT_
+
+#include <string.h>
+
+#include <rte_common.h>
+
+#define DSW_ARY_ELEM_PTR(_ary, _idx, _elem_size)	\
+	RTE_PTR_ADD(_ary, (_idx) * (_elem_size))
+
+#define DSW_ARY_ELEM_SWAP(_ary, _a_idx, _b_idx, _elem_size)		\
+	do {								\
+		char tmp[_elem_size];					\
+		void *_a_ptr = DSW_ARY_ELEM_PTR(_ary, _a_idx, _elem_size); \
+		void *_b_ptr = DSW_ARY_ELEM_PTR(_ary, _b_idx, _elem_size); \
+		memcpy(tmp, _a_ptr, _elem_size);			\
+		memcpy(_a_ptr, _b_ptr, _elem_size);			\
+		memcpy(_b_ptr, tmp, _elem_size);			\
+	} while (0)
+
+static inline void
+dsw_insertion_sort(void *ary, uint16_t len, uint16_t elem_size,
+		   int (*cmp_fn)(const void *, const void *))
+{
+	uint16_t i;
+
+	for (i = 1; i < len; i++) {
+		uint16_t j;
+		for (j = i; j > 0 &&
+			     cmp_fn(DSW_ARY_ELEM_PTR(ary, j-1, elem_size),
+				    DSW_ARY_ELEM_PTR(ary, j, elem_size)) > 0;
+		     j--)
+			DSW_ARY_ELEM_SWAP(ary, j, j-1, elem_size);
+	}
+}
+
+static inline void
+dsw_stable_sort(void *ary, uint16_t len, uint16_t elem_size,
+		int (*cmp_fn)(const void *, const void *))
+{
+	dsw_insertion_sort(ary, len, elem_size, cmp_fn);
+}
+
+#endif
-- 
2.17.1

  parent reply	other threads:[~2018-09-18 12:45 UTC|newest]

Thread overview: 15+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-09-18 12:45 [dpdk-dev] [PATCH v4 00/10] A Distributed Software Event Device Mattias Rönnblom
2018-09-18 12:45 ` [dpdk-dev] [PATCH v4 01/10] event/dsw: add DSW device registration and build system Mattias Rönnblom
2018-10-02 13:43   ` Ferruh Yigit
2018-10-04 11:21   ` [dpdk-dev] [PATCH v2] event/dsw: fix icc build Mattias Rönnblom
2018-10-04 14:17     ` Jerin Jacob
2018-09-18 12:45 ` [dpdk-dev] [PATCH v4 02/10] event/dsw: add DSW device and queue configuration Mattias Rönnblom
2018-09-18 12:45 ` [dpdk-dev] [PATCH v4 03/10] event/dsw: add DSW port configuration Mattias Rönnblom
2018-09-18 12:45 ` [dpdk-dev] [PATCH v4 04/10] event/dsw: add support in DSW for linking/unlinking ports Mattias Rönnblom
2018-09-18 12:45 ` [dpdk-dev] [PATCH v4 05/10] event/dsw: add DSW event scheduling and device start/stop Mattias Rönnblom
2018-09-18 12:45 ` [dpdk-dev] [PATCH v4 06/10] event/dsw: add DSW port load measurements Mattias Rönnblom
2018-09-18 12:45 ` [dpdk-dev] [PATCH v4 07/10] event/dsw: add load balancing to the DSW event device Mattias Rönnblom
2018-09-18 12:45 ` Mattias Rönnblom [this message]
2018-09-18 12:45 ` [dpdk-dev] [PATCH v4 09/10] event/dsw: implement eventdev 'xstats' counters in DSW Mattias Rönnblom
2018-09-18 12:45 ` [dpdk-dev] [PATCH v4 10/10] event/dsw: include DSW event device documentation Mattias Rönnblom
2018-09-19 11:53 ` [dpdk-dev] [PATCH v4 00/10] A Distributed Software Event Device Jerin Jacob

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20180918124514.10615-9-mattias.ronnblom@ericsson.com \
    --to=mattias.ronnblom@ericsson.com \
    --cc=bruce.richardson@intel.com \
    --cc=dev@dpdk.org \
    --cc=jerin.jacob@caviumnetworks.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).