From: Andrew Morton <akpm@linux-foundation.org>
To: Felix Kuehling <Felix.Kuehling@amd.com>
Cc: linux-kernel@vger.kernel.org, amd-gfx@lists.freedesktop.org
Subject: Re: [PATCH] lib: Closed hash table with low overhead
Date: Fri, 15 Sep 2017 14:14:56 -0700 [thread overview]
Message-ID: <20170915141456.4382d7ffae7ec8a9a86c8cf9@linux-foundation.org> (raw)
In-Reply-To: <1503971590-15963-1-git-send-email-Felix.Kuehling@amd.com>
On Mon, 28 Aug 2017 21:53:10 -0400 Felix Kuehling <Felix.Kuehling@amd.com> wrote:
> This adds a statically sized closed hash table implementation with
> low memory and CPU overhead. The API is inspired by kfifo.
>
> Storing, retrieving and deleting data does not involve any dynamic
> memory management, which makes it ideal for use in interrupt context.
> Static memory usage per entry comprises a 32 or 64 bit hash key, two
> bits for occupancy tracking and the value size stored in the table.
> No list heads or pointers are needed. Therefore this data structure
> should be quite cache-friendly, too.
>
> It uses linear probing and lazy deletion. During lookups free space
> is reclaimed and entries relocated to speed up future lookups.
I haven't looked at the implementation (yet), but I'm wondering if you
have identified hash table users (or implementations) elsewhere in the
kernel which might be migrated to use this? If so, such conversions
can be used to determine/demonstrate the desirability of the patch.
next prev parent reply other threads:[~2017-09-15 21:14 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-08-29 1:53 Felix Kuehling
2017-09-15 21:14 ` Andrew Morton [this message]
2017-09-19 1:33 ` Felix Kuehling
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=20170915141456.4382d7ffae7ec8a9a86c8cf9@linux-foundation.org \
--to=akpm@linux-foundation.org \
--cc=Felix.Kuehling@amd.com \
--cc=amd-gfx@lists.freedesktop.org \
--cc=linux-kernel@vger.kernel.org \
/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
Powered by JetHome