DPDK patches and discussions
 help / color / mirror / Atom feed
* [dpdk-dev] [PATCH 0/3] lib/hash: perf improvements for lock-free
@ 2019-06-25 21:15 Honnappa Nagarahalli
  2019-06-25 21:15 ` [dpdk-dev] [PATCH 1/3] lib/hash: use ordered loads only if signature matches Honnappa Nagarahalli
                   ` (3 more replies)
  0 siblings, 4 replies; 23+ messages in thread
From: Honnappa Nagarahalli @ 2019-06-25 21:15 UTC (permalink / raw)
  To: yipeng1.wang, sameh.gobriel, bruce.richardson,
	pablo.de.lara.guarch, honnappa.nagarahalli
  Cc: gavin.hu, ruifeng.wang, dev, nd

While using the rte_hash library, there are 2 sets of stores that
happen.

1) The application writes its data to memory (whose address
is provided in rte_hash_add_key_with_hash_data API (or NULL))
2) The rte_hash library writes to its own internal data structures;
key store entry and the hash table.

The data from both of these stores is available to the readers only
after the index of the key store entry (key_index) is written in the
hash buckets by the library. So, key_index can act as the guard variable
for both of these writes.

When rte_hash_add_key_with_hash_data is called to update an existing entry,
the key_index is not written. But, the store to the application data
must complete before the address of the application data (pData) is
updated in the key store entry. So, pData alone acts as the guard variable
for this case.

However, it should be noted that there are no ordering requirements
between 1) and 2), except for one requirement - the store to the
application data must complete before the store to key_index.
In other words, there are no ordering requirements between the stores to
the key store entry/signature and store to application data. So, the
synchronization point for application data can be any point between
the 'store to application data' and 'store to the key_index'.

The first patch in this series moves the signature comparison before the
load-acquire of the key_index. This does not result in any issues because
of the full key comparison which is done after the load-acquire of
the key_index.
Performance improvements:
Lookup Hit: 6.16%
Lookup Miss: 8.54%

The second patch in this series, moves the store-release of pData
before the store to any hash internal data structures. This is not
necessary, but just helps to show the non-dependency between application
data and hash table data. On the reader side, the pData is loaded
only if the keys match, this provides performance benefits.
Performance improvements (with patch 1):
Lookup Hit: 6.25%
Lookup Miss: 13.97%

The third patch moves the table change counter to the beginning of
the cache line as it is one of the first fields accessed in the lookup
function. Further work is required to adjust rte_hash structure
to gain more performance.
Performance improvements (with patch 1 and patch 2):
Lookup Hit: 2.13%
Lookup Miss: 1.56%

Honnappa Nagarahalli (3):
  lib/hash: use ordered loads only if signature matches
  lib/hash: load pData after full key compare
  lib/hash: adjust tbl_chng_cnt position

 lib/librte_hash/rte_cuckoo_hash.c | 96 ++++++++++++++++---------------
 lib/librte_hash/rte_cuckoo_hash.h |  6 +-
 2 files changed, 53 insertions(+), 49 deletions(-)

-- 
2.17.1


^ permalink raw reply	[flat|nested] 23+ messages in thread

end of thread, other threads:[~2019-07-08 18:10 UTC | newest]

Thread overview: 23+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-06-25 21:15 [dpdk-dev] [PATCH 0/3] lib/hash: perf improvements for lock-free Honnappa Nagarahalli
2019-06-25 21:15 ` [dpdk-dev] [PATCH 1/3] lib/hash: use ordered loads only if signature matches Honnappa Nagarahalli
2019-06-28 18:04   ` Wang, Yipeng1
2019-06-25 21:15 ` [dpdk-dev] [PATCH 2/3] lib/hash: load pData after full key compare Honnappa Nagarahalli
2019-06-28 18:40   ` Wang, Yipeng1
2019-07-02  4:35     ` Honnappa Nagarahalli
2019-07-04  0:39       ` Wang, Yipeng1
2019-07-05  5:33         ` Honnappa Nagarahalli
2019-07-08 16:44           ` Wang, Yipeng1
2019-06-25 21:15 ` [dpdk-dev] [PATCH 3/3] lib/hash: adjust tbl_chng_cnt position Honnappa Nagarahalli
2019-06-28 18:50   ` Wang, Yipeng1
2019-07-02 17:23     ` Honnappa Nagarahalli
2019-07-04  0:52       ` Wang, Yipeng1
2019-07-02 21:16 ` [dpdk-dev] [PATCH v2 0/2] lib/hash: perf improvements for lock-free Honnappa Nagarahalli
2019-07-02 21:16   ` [dpdk-dev] [PATCH v2 1/2] lib/hash: use ordered loads only if signature matches Honnappa Nagarahalli
2019-07-02 21:16   ` [dpdk-dev] [PATCH v2 2/2] lib/hash: load pData after full key compare Honnappa Nagarahalli
2019-07-04 11:13   ` [dpdk-dev] [PATCH v2 0/2] lib/hash: perf improvements for lock-free Jerin Jacob Kollanukkaran
2019-07-05  6:08     ` Honnappa Nagarahalli
2019-07-04 16:09   ` Thomas Monjalon
2019-07-05  6:14     ` Honnappa Nagarahalli
2019-07-05  6:29       ` Thomas Monjalon
2019-07-08 16:51     ` Wang, Yipeng1
2019-07-08 18:10       ` Thomas Monjalon

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).