Re: [RFC 1/4] hashtable: introduce a small and naive hashtable
[Posted August 8, 2012 by jake]
| From: |
| Linus Torvalds <torvalds-AT-linux-foundation.org> |
| To: |
| Josh Triplett <josh-AT-joshtriplett.org> |
| Subject: |
| Re: [RFC 1/4] hashtable: introduce a small and naive hashtable |
| Date: |
| Thu, 2 Aug 2012 13:32:41 -0700 |
| Message-ID: |
| <CA+55aFybtRdg=AzcHv3CPm-_wx8LT2_CXaKr4K+i94QSPauZOw@mail.gmail.com> |
| Cc: |
| "Eric W. Biederman" <ebiederm-AT-xmission.com>, Sasha Levin <levinsasha928-AT-gmail.com>,
Tejun Heo <tj-AT-kernel.org>, akpm-AT-linux-foundation.org, linux-kernel-AT-vger.kernel.org,
linux-mm-AT-kvack.org, paul.gortmaker-AT-windriver.com |
| Archive‑link: | |
Article |
On Thu, Aug 2, 2012 at 1:25 PM, Josh Triplett <josh@joshtriplett.org> wrote:
>
> Sorry, I should clarify what I meant: you'll have a total of one extra
> indirection, not two.
Yes. But the hash table address generation is noticeably bigger and
slower due to the non-fixed size too.
In general, you can basically think of a dynamic hash table as always
having one extra entry in the hash chains. Sure, the base address
*may* cache well, but on the other hand, a smaller static hash table
caches better than a big one, so you lose some and you win some.
According to my numbers, you win a lot more than you lose.
> Does your two-level dcache handle eviction?
>
> Mind posting the WIP patches?
Attached. It's against an older kernel, but I suspect it still applies
cleanly. The patch is certainly simple, but note the warning (you can
*run* it, though - the race is almost entirely theoretical, so you can
get numbers without ever seeing it)
Linus
