Re: [PATCH 03/10] lib: dampen the percpu_counter FBC_BATCH
On Sat, 2007-04-21 at 02:55 -0700, Andrew Morton wrote: > On Fri, 20 Apr 2007 17:51:57 +0200 Peter Zijlstra <[EMAIL PROTECTED]> wrote: > > > With the current logic the percpu_counter's accuracy delta is quadric > > wrt the number of cpus in the system, reduce this to O(n ln n). > > > > Signed-off-by: Peter Zijlstra <[EMAIL PROTECTED]> > > --- > > include/linux/percpu_counter.h |7 ++- > > 1 file changed, 2 insertions(+), 5 deletions(-) > > > > Index: linux-2.6-mm/include/linux/percpu_counter.h > > === > > --- linux-2.6-mm.orig/include/linux/percpu_counter.h > > +++ linux-2.6-mm/include/linux/percpu_counter.h > > @@ -11,6 +11,7 @@ > > #include > > #include > > #include > > +#include > > > > #ifdef CONFIG_SMP > > > > @@ -20,11 +21,7 @@ struct percpu_counter { > > s32 *counters; > > }; > > > > -#if NR_CPUS >= 16 > > -#define FBC_BATCH (NR_CPUS*2) > > -#else > > -#define FBC_BATCH (NR_CPUS*4) > > -#endif > > +#define FBC_BATCH (8*ilog2(NR_CPUS)) > > > > static inline void percpu_counter_init(struct percpu_counter *fbc, s64 > > amount) > > { > > I worry that this might be too small when there are hundreds of CPUs online. > > With 1024 CPUs we go for the lock once per 80 counts. That's not much. > > If we have 1024 CPUs, each one of which is incrementing this counter at N > Hz, we have 1024/80=12 CPUs all going for the same lock at N Hz. It could > get bad. > > But I don't know what the gain is for this loss. Your changelog should > have told us. > > What problem is this patch solving? In 10/10 I introduce bdi_stat_delta() which gives the maximum error of a single counter. That is used to switch between precise (percpu_counter_sum) and imprecise (percpu_counter_read) accesses of the stats. I worried that the current quadric error would be too large; and as the ZVC counters also use a logarithmic error bound I thought it would be good to have here as well. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 03/10] lib: dampen the percpu_counter FBC_BATCH
On Fri, 20 Apr 2007 17:51:57 +0200 Peter Zijlstra <[EMAIL PROTECTED]> wrote: > With the current logic the percpu_counter's accuracy delta is quadric > wrt the number of cpus in the system, reduce this to O(n ln n). > > Signed-off-by: Peter Zijlstra <[EMAIL PROTECTED]> > --- > include/linux/percpu_counter.h |7 ++- > 1 file changed, 2 insertions(+), 5 deletions(-) > > Index: linux-2.6-mm/include/linux/percpu_counter.h > === > --- linux-2.6-mm.orig/include/linux/percpu_counter.h > +++ linux-2.6-mm/include/linux/percpu_counter.h > @@ -11,6 +11,7 @@ > #include > #include > #include > +#include > > #ifdef CONFIG_SMP > > @@ -20,11 +21,7 @@ struct percpu_counter { > s32 *counters; > }; > > -#if NR_CPUS >= 16 > -#define FBC_BATCH(NR_CPUS*2) > -#else > -#define FBC_BATCH(NR_CPUS*4) > -#endif > +#define FBC_BATCH(8*ilog2(NR_CPUS)) > > static inline void percpu_counter_init(struct percpu_counter *fbc, s64 > amount) > { I worry that this might be too small when there are hundreds of CPUs online. With 1024 CPUs we go for the lock once per 80 counts. That's not much. If we have 1024 CPUs, each one of which is incrementing this counter at N Hz, we have 1024/80=12 CPUs all going for the same lock at N Hz. It could get bad. But I don't know what the gain is for this loss. Your changelog should have told us. What problem is this patch solving? - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 03/10] lib: dampen the percpu_counter FBC_BATCH
On Fri, 20 Apr 2007 17:51:57 +0200 Peter Zijlstra [EMAIL PROTECTED] wrote: With the current logic the percpu_counter's accuracy delta is quadric wrt the number of cpus in the system, reduce this to O(n ln n). Signed-off-by: Peter Zijlstra [EMAIL PROTECTED] --- include/linux/percpu_counter.h |7 ++- 1 file changed, 2 insertions(+), 5 deletions(-) Index: linux-2.6-mm/include/linux/percpu_counter.h === --- linux-2.6-mm.orig/include/linux/percpu_counter.h +++ linux-2.6-mm/include/linux/percpu_counter.h @@ -11,6 +11,7 @@ #include linux/threads.h #include linux/percpu.h #include linux/types.h +#include linux/log2.h #ifdef CONFIG_SMP @@ -20,11 +21,7 @@ struct percpu_counter { s32 *counters; }; -#if NR_CPUS = 16 -#define FBC_BATCH(NR_CPUS*2) -#else -#define FBC_BATCH(NR_CPUS*4) -#endif +#define FBC_BATCH(8*ilog2(NR_CPUS)) static inline void percpu_counter_init(struct percpu_counter *fbc, s64 amount) { I worry that this might be too small when there are hundreds of CPUs online. With 1024 CPUs we go for the lock once per 80 counts. That's not much. If we have 1024 CPUs, each one of which is incrementing this counter at N Hz, we have 1024/80=12 CPUs all going for the same lock at N Hz. It could get bad. But I don't know what the gain is for this loss. Your changelog should have told us. What problem is this patch solving? - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 03/10] lib: dampen the percpu_counter FBC_BATCH
On Sat, 2007-04-21 at 02:55 -0700, Andrew Morton wrote: On Fri, 20 Apr 2007 17:51:57 +0200 Peter Zijlstra [EMAIL PROTECTED] wrote: With the current logic the percpu_counter's accuracy delta is quadric wrt the number of cpus in the system, reduce this to O(n ln n). Signed-off-by: Peter Zijlstra [EMAIL PROTECTED] --- include/linux/percpu_counter.h |7 ++- 1 file changed, 2 insertions(+), 5 deletions(-) Index: linux-2.6-mm/include/linux/percpu_counter.h === --- linux-2.6-mm.orig/include/linux/percpu_counter.h +++ linux-2.6-mm/include/linux/percpu_counter.h @@ -11,6 +11,7 @@ #include linux/threads.h #include linux/percpu.h #include linux/types.h +#include linux/log2.h #ifdef CONFIG_SMP @@ -20,11 +21,7 @@ struct percpu_counter { s32 *counters; }; -#if NR_CPUS = 16 -#define FBC_BATCH (NR_CPUS*2) -#else -#define FBC_BATCH (NR_CPUS*4) -#endif +#define FBC_BATCH (8*ilog2(NR_CPUS)) static inline void percpu_counter_init(struct percpu_counter *fbc, s64 amount) { I worry that this might be too small when there are hundreds of CPUs online. With 1024 CPUs we go for the lock once per 80 counts. That's not much. If we have 1024 CPUs, each one of which is incrementing this counter at N Hz, we have 1024/80=12 CPUs all going for the same lock at N Hz. It could get bad. But I don't know what the gain is for this loss. Your changelog should have told us. What problem is this patch solving? In 10/10 I introduce bdi_stat_delta() which gives the maximum error of a single counter. That is used to switch between precise (percpu_counter_sum) and imprecise (percpu_counter_read) accesses of the stats. I worried that the current quadric error would be too large; and as the ZVC counters also use a logarithmic error bound I thought it would be good to have here as well. - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/