Re: [PATCH v2 2/2] trace-filter: Change the hashing function used when filtering

[Yordan Karadzhov <y.karadz@xxxxxxxxx>]

On 20.06.2018 18:21, Steven Rostedt wrote:
> On Tue, 19 Jun 2018 16:22:59 +0300
> "Yordan Karadzhov (VMware)" <y.karadz@xxxxxxxxx> wrote:
>
> > diff --git a/kernel-shark/include/trace-filter-hash.h b/kernel-shark/include/trace-filter-hash.h
> > index 5cc39dc..98c9ab3 100644
> > --- a/kernel-shark/include/trace-filter-hash.h
> > +++ b/kernel-shark/include/trace-filter-hash.h
> > @@ -20,7 +20,7 @@
> >   #ifndef _TRACE_FILTER_HASH_H
> >   #define _TRACE_FILTER_HASH_H
> >   
> > -#include "trace-hash-local.h"
> > +#include <stdint.h>
> >   
> >   struct filter_id_item {
> >   	struct filter_id_item	*next;
> > @@ -47,4 +47,39 @@ static inline int filter_task_count(struct filter_id *hash)
> >   	return hash->count;
> >   }
> >   
> > +/*
> > + * Hashing functions, based on Donald E. Knuth's Multiplicative hashing.
> > + * See The Art of Computer Programming (TAOCP).
> > + */
> > +
> > +static inline uint8_t knuth_hash8(uint32_t val)
> > +{
> > +	/*
> > +	 * Multiplicative hashing function.
> > +	 * Multiplication by the Prime number, closest to the golden
> > +	 * ratio of 2^8.
> > +	 */
> > +	return UINT8_C(val) * UINT8_C(157);
> > +}
> > +
> > +static inline uint16_t knuth_hash16(uint32_t val)
> > +{
> > +	/*
> > +	 * Multiplicative hashing function.
> > +	 * Multiplication by the Prime number, closest to the golden
> > +	 * ratio of 2^16.
> > +	 */
> > +	return UINT16_C(val) * UINT16_C(40507);
> > +}
> > +
> > +static inline uint32_t knuth_hash(uint32_t val)
> BTW, is there any reason to have these in the header file? Shouldn't
> they be in a C file?
>
> The reason I ask is because this is going to be in a more public file,
> and I need to rename the functions for namespace reasons. These are
> someone out of place for a library header.


My only reason for having the hash functions in the header is to make sure
that the user will be aware that those are cheap and fast functions, but 
using
those functions makes sense only in the case when we have relatively small
number of items in the hash table. Nevertheless, If you prefer the 
implementation
to be in the .c file this is OK.

Yordan


> -- Steve
>
>
> > +{
> > +	/*
> > +	 * Multiplicative hashing function.
> > +	 * Multiplication by the Prime number, closest to the golden
> > +	 * ratio of 2^32.
> > +	 */
> > +	return val * UINT32_C(2654435761);
> > +}
> > +