Messages in this thread | | | Date | Tue, 14 Jan 2014 23:39:35 +0100 | From | Hannes Frederic Sowa <> | Subject | Re: [PATCH RFC] reciprocal_divide: correction/update of the algorithm |
| |
On Tue, Jan 14, 2014 at 10:07:05AM -0800, Eric Dumazet wrote: > On Mon, 2014-01-13 at 22:42 +0100, Hannes Frederic Sowa wrote: > > This patch is a RFC and part of a series Daniel Borkmann and me want to > > do when introducing prandom_u32_range{,_ro} and prandom_u32_max{,_ro} > > helpers later this week. > > > -static inline u32 reciprocal_divide(u32 A, u32 R) > > +struct reciprocal_value reciprocal_value(u32 d); > > + > > +static inline u32 reciprocal_divide(u32 a, struct reciprocal_value R) > > { > > - return (u32)(((u64)A * R) >> 32); > > + u32 t = (u32)(((u64)a * R.m) >> 32); > > + return (t + ((a - t) >> R.sh1)) >> R.sh2; > > } > > I would rather introduce new helpers and convert users that really need > them. > > For instance, just use a divide in BPF, because doing this on JIT might > be too complex for the gains. Strangely, libpcap doesn't seem to > optimize any divide, like divides by a power of two... > > Reciprocal were added 7 years ago, for very specific uses, but current > cpus have reasonably fast dividers.
Agreed. The new algorithm would need to change the size of struct sock_filter, which is exported to user space. We will leave BPF as-is for the time being and check that later.
Greetings,
Hannes
| |