On Thu, Aug 02, 2012 at 11:47:01PM +0200, Sasha Levin wrote:
> On 08/02/2012 10:41 PM, Josh Triplett wrote:
> > On Thu, Aug 02, 2012 at 07:54:42PM +0200, Sasha Levin wrote:
> >> /* I've "preprocessed" the DEFINE macro below */
> >> union {
> >>struct hash_table table;
> >>struct {
> >>
On Thu, Aug 2, 2012 at 2:21 PM, Josh Triplett wrote:
>
> Did GCC's generated code have worse differences than an immediate
> versus a fetched value?
Oh, *way* worse.
Nobody just masks the low bits. You have more bits than the low bits,
and unless you have some cryptographic hash (seldom) you w
On 08/02/2012 10:41 PM, Josh Triplett wrote:
> On Thu, Aug 02, 2012 at 07:54:42PM +0200, Sasha Levin wrote:
>> /* I've "preprocessed" the DEFINE macro below */
>> union {
>> struct hash_table table;
>> struct {
>> size_t bits;
>> struct hlist_head buckets[32];
>>
On Thu, Aug 02, 2012 at 01:32:41PM -0700, Linus Torvalds wrote:
> On Thu, Aug 2, 2012 at 1:25 PM, Josh Triplett 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
>
On Thu, Aug 02, 2012 at 07:54:42PM +0200, Sasha Levin wrote:
> On 08/02/2012 07:44 PM, Josh Triplett wrote:
> > On Thu, Aug 02, 2012 at 06:48:07PM +0200, Sasha Levin wrote:
> >> On 08/02/2012 06:15 PM, Josh Triplett wrote:
> >>> On Thu, Aug 02, 2012 at 03:04:19PM +0200, Sasha Levin wrote:
> On
On Thu, Aug 2, 2012 at 1:25 PM, Josh Triplett 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
On Thu, Aug 02, 2012 at 11:08:06AM -0700, Linus Torvalds wrote:
> On Thu, Aug 2, 2012 at 10:59 AM, Josh Triplett wrote:
> >
> > You shouldn't have any extra indirection for the base, if it lives
> > immediately after the size.
>
> Umm. You *always* have the extra indirection. Because you have tha
On Thu, Aug 2, 2012 at 10:59 AM, Josh Triplett wrote:
>
> You shouldn't have any extra indirection for the base, if it lives
> immediately after the size.
Umm. You *always* have the extra indirection. Because you have that allocation.
So you have to follow the pointer to get the base/size, becau
On Thu, Aug 02, 2012 at 10:32:13AM -0700, Linus Torvalds wrote:
> On Thu, Aug 2, 2012 at 9:40 AM, Eric W. Biederman
> wrote:
> >
> > For a trivial hash table I don't know if the abstraction is worth it.
> > For a hash table that starts off small and grows as big as you need it
> > the incent to u
On 08/02/2012 07:44 PM, Josh Triplett wrote:
> On Thu, Aug 02, 2012 at 06:48:07PM +0200, Sasha Levin wrote:
>> On 08/02/2012 06:15 PM, Josh Triplett wrote:
>>> On Thu, Aug 02, 2012 at 03:04:19PM +0200, Sasha Levin wrote:
On 08/02/2012 01:23 PM, Sasha Levin wrote:
>> #define DEFINE_HASH_TAB
On Thu, 2012-08-02 at 10:32 -0700, Linus Torvalds wrote:
> On Thu, Aug 2, 2012 at 9:40 AM, Eric W. Biederman
> wrote:
> >
> > For a trivial hash table I don't know if the abstraction is worth it.
> > For a hash table that starts off small and grows as big as you need it
> > the incent to use a ha
On Thu, Aug 02, 2012 at 06:48:07PM +0200, Sasha Levin wrote:
> On 08/02/2012 06:15 PM, Josh Triplett wrote:
> > On Thu, Aug 02, 2012 at 03:04:19PM +0200, Sasha Levin wrote:
> >> On 08/02/2012 01:23 PM, Sasha Levin wrote:
> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = {
> >
On Thu, Aug 2, 2012 at 9:40 AM, Eric W. Biederman wrote:
>
> For a trivial hash table I don't know if the abstraction is worth it.
> For a hash table that starts off small and grows as big as you need it
> the incent to use a hash table abstraction seems a lot stronger.
I'm not sure growing hash
On 08/02/2012 06:15 PM, Josh Triplett wrote:
> On Thu, Aug 02, 2012 at 03:04:19PM +0200, Sasha Levin wrote:
>> On 08/02/2012 01:23 PM, Sasha Levin wrote:
#define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count
= length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INI
Sasha Levin writes:
> Heh, I've started working on it in April, and just returned to this. Didn't
> think about rebasing to something new.
>
> will fix - Thanks!
You might want to look at some of the work that Eric Dumazet has done in
the networking stack with rcu hashtables that can be resized
On 08/02/2012 06:03 PM, Eric W. Biederman wrote:
> Sasha Levin writes:
>> On 08/02/2012 12:32 PM, Josh Triplett wrote:
>>> What about using a C99 flexible array member? Kernel style prohibits
>>> variable-length arrays, but I don't think the same rationale applies to
>>> flexible array members.
>
On Thu, Aug 02, 2012 at 03:04:19PM +0200, Sasha Levin wrote:
> On 08/02/2012 01:23 PM, Sasha Levin wrote:
> >> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count
> >> = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }
> > The limitation of this approach is tha
Sasha Levin writes:
> On 08/02/2012 12:32 PM, Josh Triplett wrote:
>> What about using a C99 flexible array member? Kernel style prohibits
>> variable-length arrays, but I don't think the same rationale applies to
>> flexible array members.
>>
>> struct hash_table {
>> size_t count;
>> s
On 08/02/2012 01:23 PM, Sasha Levin wrote:
>> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count =
>> length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }
> The limitation of this approach is that the struct hash_table variable must
> be 'static', which is a bit
On 08/02/2012 12:32 PM, Josh Triplett wrote:
> On Thu, Aug 02, 2012 at 12:00:33PM +0200, Sasha Levin wrote:
>> On 08/02/2012 12:45 AM, Tejun Heo wrote:
>>> On Thu, Aug 02, 2012 at 12:41:56AM +0200, Sasha Levin wrote:
How would your DEFINE_HASHTABLE look like if we got for the simple
'stru
On Thu, Aug 02, 2012 at 12:00:33PM +0200, Sasha Levin wrote:
> On 08/02/2012 12:45 AM, Tejun Heo wrote:
> > On Thu, Aug 02, 2012 at 12:41:56AM +0200, Sasha Levin wrote:
> >> How would your DEFINE_HASHTABLE look like if we got for the simple
> >> 'struct hash_table' approach?
> >
> > I think defini
On 08/02/2012 12:45 AM, Tejun Heo wrote:
> On Thu, Aug 02, 2012 at 12:41:56AM +0200, Sasha Levin wrote:
>> How would your DEFINE_HASHTABLE look like if we got for the simple
>> 'struct hash_table' approach?
>
> I think defining a different enclosing anonymous struct which the
> requested number of
On Wed, Aug 01, 2012 at 11:27:49AM -0700, Tejun Heo wrote:
> On Wed, Aug 01, 2012 at 08:24:32PM +0200, Sasha Levin wrote:
> > On 08/01/2012 08:21 PM, Tejun Heo wrote:
> > > On Wed, Aug 01, 2012 at 08:19:52PM +0200, Sasha Levin wrote:
> > >> If we switch to using functions, we could no longer hide i
On Thu, Aug 02, 2012 at 12:41:56AM +0200, Sasha Levin wrote:
> How would your DEFINE_HASHTABLE look like if we got for the simple
> 'struct hash_table' approach?
I think defining a different enclosing anonymous struct which the
requested number of array entries and then aliasing the actual
hash_ta
On 08/01/2012 10:24 PM, Tejun Heo wrote:
> On Wed, Aug 01, 2012 at 09:06:50PM +0200, Sasha Levin wrote:
>> Using a struct makes the dynamic case much easier, but it complicates the
>> static case.
>>
>> Previously we could create the buckets statically.
>>
>> Consider this struct:
>>
>> struct has
On Wed, Aug 01, 2012 at 09:06:50PM +0200, Sasha Levin wrote:
> Using a struct makes the dynamic case much easier, but it complicates the
> static case.
>
> Previously we could create the buckets statically.
>
> Consider this struct:
>
> struct hash_table {
> u32 bits;
> struct hlist
On 08/01/2012 08:27 PM, Tejun Heo wrote:
> On Wed, Aug 01, 2012 at 08:24:32PM +0200, Sasha Levin wrote:
>> On 08/01/2012 08:21 PM, Tejun Heo wrote:
>>> On Wed, Aug 01, 2012 at 08:19:52PM +0200, Sasha Levin wrote:
If we switch to using functions, we could no longer hide it anywhere
(we'd n
On Wed, Aug 01, 2012 at 08:24:32PM +0200, Sasha Levin wrote:
> On 08/01/2012 08:21 PM, Tejun Heo wrote:
> > On Wed, Aug 01, 2012 at 08:19:52PM +0200, Sasha Levin wrote:
> >> If we switch to using functions, we could no longer hide it anywhere
> >> (we'd need to either turn the buckets into a struct
On 08/01/2012 08:21 PM, Tejun Heo wrote:
> On Wed, Aug 01, 2012 at 08:19:52PM +0200, Sasha Levin wrote:
>> If we switch to using functions, we could no longer hide it anywhere
>> (we'd need to either turn the buckets into a struct, or have the
>> user pass it around to all functions).
>
> Create a
On Wed, Aug 01, 2012 at 08:19:52PM +0200, Sasha Levin wrote:
> If we switch to using functions, we could no longer hide it anywhere
> (we'd need to either turn the buckets into a struct, or have the
> user pass it around to all functions).
Create an outer struct hash_table which remembers the size
On 07/31/2012 08:23 PM, Tejun Heo wrote:
> Hello, Sasha.
>
> On Tue, Jul 31, 2012 at 08:05:17PM +0200, Sasha Levin wrote:
>> +#define HASH_INIT(name)
>> \
>> +({ \
>> +int __i;
On 07/31/2012 08:23 PM, Tejun Heo wrote:
> Hello, Sasha.
>
> On Tue, Jul 31, 2012 at 08:05:17PM +0200, Sasha Levin wrote:
>> +#define HASH_INIT(name)
>> \
>> +({ \
>> +int __i;
Hello, Sasha.
On Tue, Jul 31, 2012 at 08:05:17PM +0200, Sasha Levin wrote:
> +#define HASH_INIT(name)
> \
> +({ \
> + int __i;
33 matches
Mail list logo
