| Message ID | 1430434005-6143-3-git-send-email-tgraf@suug.ch |
|---|---|
| State | Changes Requested, archived |
| Delegated to: | David Miller |
| Headers | show |
Thomas Graf <tgraf@suug.ch> wrote: > Grow the table quicker than 2x in the beginning to avoid long chains > of rehashes. The effect is observable in the self-test where table > jumps are reduced to a minimum after a lot of entries have been added > in a short period of time. The iterator is able to get a consistent > view most of the time. > > Signed-off-by: Thomas Graf <tgraf@suug.ch> Wouldn't automatic shrinking immediately undo your quick growth? Cheers,
On 05/01/15 at 07:45am, Herbert Xu wrote: > Thomas Graf <tgraf@suug.ch> wrote: > > Grow the table quicker than 2x in the beginning to avoid long chains > > of rehashes. The effect is observable in the self-test where table > > jumps are reduced to a minimum after a lot of entries have been added > > in a short period of time. The iterator is able to get a consistent > > view most of the time. > > > > Signed-off-by: Thomas Graf <tgraf@suug.ch> > > Wouldn't automatic shrinking immediately undo your quick growth? Yes, that can happen. Since shrinks are ordered to the end of the chain it is often the case that enough entries have been added so the shrink is not carried out in the end. Obviously this is also not the case if no entries are actually removed. What about we apply quick growing on >100% utilization? It is a clear indication that we are growing rapidly. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, May 01, 2015 at 06:30:25AM +0200, Thomas Graf wrote: > > Yes, that can happen. Since shrinks are ordered to the end of the > chain it is often the case that enough entries have been added so the > shrink is not carried out in the end. Obviously this is also not the > case if no entries are actually removed. It's just a matter of logical consistency. At 75% if you grow by a factor of 4, you get 18.75% utilisation which is way below the 30% shrink threshold. > What about we apply quick growing on >100% utilization? It is a > clear indication that we are growing rapidly. Even at 100%, a factor of 4 leads you to 25% which is less than 30%. Perhaps we could lower the shrink thresholds? Alternatively, only grow quickly if automatic shrinking is disabled. After all, the one case that's inspring all of this, netlink really wants to grow quickly as well as only shrink at specific points in time. Cheers,
Hello. On 5/1/2015 1:46 AM, Thomas Graf wrote: > Grow the table quicker than 2x in the beginning to avoid long chains > of rehashes. The effect is observable in the self-test where table > jumps are reduced to a minimum after a lot of entries have been added > in a short period of time. The iterator is able to get a consistent > view most of the time. > Signed-off-by: Thomas Graf <tgraf@suug.ch> > --- > lib/rhashtable.c | 37 +++++++++++++++++++++++++++++++++++-- > 1 file changed, 35 insertions(+), 2 deletions(-) > diff --git a/lib/rhashtable.c b/lib/rhashtable.c > index 4936fc4..23e7f18 100644 > --- a/lib/rhashtable.c > +++ b/lib/rhashtable.c > @@ -271,6 +271,38 @@ static int rhashtable_rehash_table(struct rhashtable *ht) > return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0; > } > > +static int table_growth_log(unsigned int size) > +{ > + /* > + * Table growth: > + * 2 -> 64 > + * 4 -> 128 > + * 8 -> 128 > + * 16 -> 256 > + * 32 -> 512 > + * 64 -> 512 > + * 128 -> 1024 > + * 256 -> 2048 > + * 512 -> 2048 > + * 1024 -> 4096 > + * 2048 -> 8192 > + * 4096 -> 8192 > + */ > + int log = 5 - (ilog2(size) / 3); > + > + return log > 1 ? log : 1; max(log, 1)? [...] WBR, Sergei -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 05/01/15 at 12:37pm, Herbert Xu wrote: > On Fri, May 01, 2015 at 06:30:25AM +0200, Thomas Graf wrote: > > > > Yes, that can happen. Since shrinks are ordered to the end of the > > chain it is often the case that enough entries have been added so the > > shrink is not carried out in the end. Obviously this is also not the > > case if no entries are actually removed. > > It's just a matter of logical consistency. At 75% if you grow by > a factor of 4, you get 18.75% utilisation which is way below the > 30% shrink threshold. > > > What about we apply quick growing on >100% utilization? It is a > > clear indication that we are growing rapidly. > > Even at 100%, a factor of 4 leads you to 25% which is less than 30%. > > Perhaps we could lower the shrink thresholds? Alternatively, only > grow quickly if automatic shrinking is disabled. After all, the one > case that's inspring all of this, netlink really wants to grow > quickly as well as only shrink at specific points in time. Lowering the shrink threshold in combination with quick growth above 100% sounds good to me. The whole point of this is to detect when we are likely to see a lot of inserts with only a few or no removals. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 05/01/15 at 02:04pm, Sergei Shtylyov wrote: > >+ return log > 1 ? log : 1; > > max(log, 1)? Sure -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/lib/rhashtable.c b/lib/rhashtable.c index 4936fc4..23e7f18 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -271,6 +271,38 @@ static int rhashtable_rehash_table(struct rhashtable *ht) return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0; } +static int table_growth_log(unsigned int size) +{ + /* + * Table growth: + * 2 -> 64 + * 4 -> 128 + * 8 -> 128 + * 16 -> 256 + * 32 -> 512 + * 64 -> 512 + * 128 -> 1024 + * 256 -> 2048 + * 512 -> 2048 + * 1024 -> 4096 + * 2048 -> 8192 + * 4096 -> 8192 + */ + int log = 5 - (ilog2(size) / 3); + + return log > 1 ? log : 1; +} + +static unsigned int grow_table(struct rhashtable *ht, unsigned int old_size) +{ + unsigned int new_size; + + new_size = old_size << table_growth_log(old_size); + new_size = min(new_size, ht->p.max_size); + + return new_size; +} + /** * rhashtable_expand - Expand hash table while allowing concurrent lookups * @ht: the hash table to expand @@ -295,7 +327,8 @@ static int rhashtable_expand(struct rhashtable *ht) old_tbl = rhashtable_last_table(ht, old_tbl); - new_tbl = bucket_table_alloc(ht, old_tbl->size * 2, GFP_KERNEL); + new_tbl = bucket_table_alloc(ht, grow_table(ht, old_tbl->size), + GFP_KERNEL); if (new_tbl == NULL) return -ENOMEM; @@ -404,7 +437,7 @@ int rhashtable_insert_rehash(struct rhashtable *ht) size = tbl->size; if (rht_grow_above_75(ht, tbl)) - size *= 2; + size = grow_table(ht, size); /* Do not schedule more than one rehash */ else if (old_tbl != tbl) return -EBUSY;
Grow the table quicker than 2x in the beginning to avoid long chains of rehashes. The effect is observable in the self-test where table jumps are reduced to a minimum after a lot of entries have been added in a short period of time. The iterator is able to get a consistent view most of the time. Signed-off-by: Thomas Graf <tgraf@suug.ch> --- lib/rhashtable.c | 37 +++++++++++++++++++++++++++++++++++-- 1 file changed, 35 insertions(+), 2 deletions(-)