* [PATCH] trace-cmd: remove ununsed knuth_hash*() routines
@ 2019-06-26 6:01 Greg Thelen
2019-06-26 19:34 ` Steven Rostedt
0 siblings, 1 reply; 8+ messages in thread
From: Greg Thelen @ 2019-06-26 6:01 UTC (permalink / raw)
To: Steven Rostedt; +Cc: linux-trace-devel, Greg Thelen
Neither knuth_hash16() nor knuth_hash() are used.
Delete them.
Signed-off-by: Greg Thelen <gthelen@google.com>
---
lib/trace-cmd/trace-filter-hash.c | 20 --------------------
1 file changed, 20 deletions(-)
diff --git a/lib/trace-cmd/trace-filter-hash.c b/lib/trace-cmd/trace-filter-hash.c
index 39b28790e0bc..c56628f69ff0 100644
--- a/lib/trace-cmd/trace-filter-hash.c
+++ b/lib/trace-cmd/trace-filter-hash.c
@@ -29,26 +29,6 @@ static inline uint8_t knuth_hash8(uint32_t val)
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)
-{
- /*
- * Multiplicative hashing function.
- * Multiplication by the Prime number, closest to the golden
- * ratio of 2^32.
- */
- return val * UINT32_C(2654435761);
-}
-
struct tracecmd_filter_id_item *
tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id)
{
--
2.22.0.410.gd8fdbe21b5-goog
^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: [PATCH] trace-cmd: remove ununsed knuth_hash*() routines
2019-06-26 6:01 [PATCH] trace-cmd: remove ununsed knuth_hash*() routines Greg Thelen
@ 2019-06-26 19:34 ` Steven Rostedt
2019-06-27 15:40 ` Yordan Karadzhov (VMware)
0 siblings, 1 reply; 8+ messages in thread
From: Steven Rostedt @ 2019-06-26 19:34 UTC (permalink / raw)
To: Greg Thelen; +Cc: linux-trace-devel, Yordan Karadzhov
On Tue, 25 Jun 2019 23:01:01 -0700
Greg Thelen <gthelen@google.com> wrote:
> Neither knuth_hash16() nor knuth_hash() are used.
> Delete them.
>
Yordan,
Do you foresee that we will be using the other two versions of the hash?
-- Steve
> Signed-off-by: Greg Thelen <gthelen@google.com>
> ---
> lib/trace-cmd/trace-filter-hash.c | 20 --------------------
> 1 file changed, 20 deletions(-)
>
> diff --git a/lib/trace-cmd/trace-filter-hash.c b/lib/trace-cmd/trace-filter-hash.c
> index 39b28790e0bc..c56628f69ff0 100644
> --- a/lib/trace-cmd/trace-filter-hash.c
> +++ b/lib/trace-cmd/trace-filter-hash.c
> @@ -29,26 +29,6 @@ static inline uint8_t knuth_hash8(uint32_t val)
> 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)
> -{
> - /*
> - * Multiplicative hashing function.
> - * Multiplication by the Prime number, closest to the golden
> - * ratio of 2^32.
> - */
> - return val * UINT32_C(2654435761);
> -}
> -
> struct tracecmd_filter_id_item *
> tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id)
> {
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] trace-cmd: remove ununsed knuth_hash*() routines
2019-06-26 19:34 ` Steven Rostedt
@ 2019-06-27 15:40 ` Yordan Karadzhov (VMware)
2019-06-27 16:15 ` Steven Rostedt
0 siblings, 1 reply; 8+ messages in thread
From: Yordan Karadzhov (VMware) @ 2019-06-27 15:40 UTC (permalink / raw)
To: Steven Rostedt, Greg Thelen; +Cc: linux-trace-devel
On 26.06.19 г. 22:34 ч., Steven Rostedt wrote:
> On Tue, 25 Jun 2019 23:01:01 -0700
> Greg Thelen <gthelen@google.com> wrote:
>
>> Neither knuth_hash16() nor knuth_hash() are used.
>> Delete them.
>>
>
> Yordan,
>
> Do you foresee that we will be using the other two versions of the hash?
>
> -- Steve
>
Hi Greg,
Thanks for the fix!
I agree that we have to remove the unused hashing functions, but may I
ask you to do a little bit of extra work here.
I think that if we are going to keep only one hashing function this
function can be called simply knuth_has (not knuth_has8).
Also the comment on top which refers to the TAOCP book must be modified
stating that the original idea from the book (32 bit hash) was adapted
in order to be used for small tables.
cheers,
Yordan
PS: I just saw couple of new patches coming from you and I want to say
that your help is more than welcome.
>> Signed-off-by: Greg Thelen <gthelen@google.com>
>> ---
>> lib/trace-cmd/trace-filter-hash.c | 20 --------------------
>> 1 file changed, 20 deletions(-)
>>
>> diff --git a/lib/trace-cmd/trace-filter-hash.c b/lib/trace-cmd/trace-filter-hash.c
>> index 39b28790e0bc..c56628f69ff0 100644
>> --- a/lib/trace-cmd/trace-filter-hash.c
>> +++ b/lib/trace-cmd/trace-filter-hash.c
>> @@ -29,26 +29,6 @@ static inline uint8_t knuth_hash8(uint32_t val)
>> 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)
>> -{
>> - /*
>> - * Multiplicative hashing function.
>> - * Multiplication by the Prime number, closest to the golden
>> - * ratio of 2^32.
>> - */
>> - return val * UINT32_C(2654435761);
>> -}
>> -
>> struct tracecmd_filter_id_item *
>> tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id)
>> {
>
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] trace-cmd: remove ununsed knuth_hash*() routines
2019-06-27 15:40 ` Yordan Karadzhov (VMware)
@ 2019-06-27 16:15 ` Steven Rostedt
2019-06-28 15:55 ` Greg Thelen
2019-06-29 6:27 ` [PATCH v2] " Greg Thelen
0 siblings, 2 replies; 8+ messages in thread
From: Steven Rostedt @ 2019-06-27 16:15 UTC (permalink / raw)
To: Yordan Karadzhov (VMware); +Cc: Greg Thelen, linux-trace-devel
On Thu, 27 Jun 2019 18:40:27 +0300
"Yordan Karadzhov (VMware)" <y.karadz@gmail.com> wrote:
> Hi Greg,
>
> Thanks for the fix!
>
> I agree that we have to remove the unused hashing functions, but may I
> ask you to do a little bit of extra work here.
> I think that if we are going to keep only one hashing function this
> function can be called simply knuth_has (not knuth_has8).
Hi Yordan,
Small nit. I think you meant "knuth_hash" not "knuth_has", even though
I'm sure knuth has a lot ;-)
>
> Also the comment on top which refers to the TAOCP book must be modified
> stating that the original idea from the book (32 bit hash) was adapted
> in order to be used for small tables.
Ack.
-- Steve
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] trace-cmd: remove ununsed knuth_hash*() routines
2019-06-27 16:15 ` Steven Rostedt
@ 2019-06-28 15:55 ` Greg Thelen
2019-06-29 6:27 ` [PATCH v2] " Greg Thelen
1 sibling, 0 replies; 8+ messages in thread
From: Greg Thelen @ 2019-06-28 15:55 UTC (permalink / raw)
To: Steven Rostedt; +Cc: Yordan Karadzhov (VMware), linux-trace-devel
On Thu, Jun 27, 2019 at 9:15 AM Steven Rostedt <rostedt@goodmis.org> wrote:
>
> On Thu, 27 Jun 2019 18:40:27 +0300
> "Yordan Karadzhov (VMware)" <y.karadz@gmail.com> wrote:
>
>
> > Hi Greg,
> >
> > Thanks for the fix!
> >
> > I agree that we have to remove the unused hashing functions, but may I
> > ask you to do a little bit of extra work here.
> > I think that if we are going to keep only one hashing function this
> > function can be called simply knuth_has (not knuth_has8).
>
> Hi Yordan,
>
> Small nit. I think you meant "knuth_hash" not "knuth_has", even though
> I'm sure knuth has a lot ;-)
>
> >
> > Also the comment on top which refers to the TAOCP book must be modified
> > stating that the original idea from the book (32 bit hash) was adapted
> > in order to be used for small tables.
>
> Ack.
>
> -- Steve
Nod. I'll make these changes and post a patch in a day or so.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH v2] trace-cmd: remove ununsed knuth_hash*() routines
2019-06-27 16:15 ` Steven Rostedt
2019-06-28 15:55 ` Greg Thelen
@ 2019-06-29 6:27 ` Greg Thelen
2019-07-01 12:23 ` Yordan Karadzhov (VMware)
2019-07-05 13:31 ` Steven Rostedt
1 sibling, 2 replies; 8+ messages in thread
From: Greg Thelen @ 2019-06-29 6:27 UTC (permalink / raw)
To: Steven Rostedt, Yordan Karadzhov (VMware); +Cc: linux-trace-devel, Greg Thelen
Neither 16-bit knuth_hash16() nor the 32-bit knuth_hash() are used.
Delete them both.
And rename the remaining function: knuth_hash8() => knuth_hash()
Signed-off-by: Greg Thelen <gthelen@google.com>
---
kernel-shark/src/libkshark.c | 12 +++++-----
lib/trace-cmd/trace-filter-hash.c | 40 +++++++------------------------
2 files changed, 14 insertions(+), 38 deletions(-)
diff --git a/kernel-shark/src/libkshark.c b/kernel-shark/src/libkshark.c
index 0f0a1bab4d5c..d2764e813194 100644
--- a/kernel-shark/src/libkshark.c
+++ b/kernel-shark/src/libkshark.c
@@ -252,13 +252,13 @@ void kshark_free(struct kshark_context *kshark_ctx)
free(kshark_ctx);
}
-static inline uint8_t knuth_hash8(uint32_t val)
+static inline uint8_t knuth_hash(uint32_t val)
{
/*
- * Hashing functions, based on Donald E. Knuth's Multiplicative
- * hashing. See The Art of Computer Programming (TAOCP).
- * Multiplication by the Prime number, closest to the golden
- * ratio of 2^8.
+ * Small table hashing function adapted from Donald E. Knuth's 32 bit
+ * multiplicative hash. See The Art of Computer Programming (TAOCP).
+ * Multiplication by the Prime number, closest to the golden ratio of
+ * 2^8.
*/
return UINT8_C(val) * UINT8_C(157);
}
@@ -282,7 +282,7 @@ kshark_add_task(struct kshark_context *kshark_ctx, int pid)
struct kshark_task_list *list;
uint8_t key;
- key = knuth_hash8(pid);
+ key = knuth_hash(pid);
list = kshark_find_task(kshark_ctx, key, pid);
if (list)
return list;
diff --git a/lib/trace-cmd/trace-filter-hash.c b/lib/trace-cmd/trace-filter-hash.c
index 39b28790e0bc..45ca68c2959e 100644
--- a/lib/trace-cmd/trace-filter-hash.c
+++ b/lib/trace-cmd/trace-filter-hash.c
@@ -14,45 +14,21 @@
#define FILTER_HASH_SIZE 256
-/*
- * 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)
+static inline uint8_t knuth_hash(uint32_t val)
{
/*
- * Multiplicative hashing function.
- * Multiplication by the Prime number, closest to the golden
- * ratio of 2^8.
+ * Small table hashing function adapted from Donald E. Knuth's 32 bit
+ * multiplicative hash. See The Art of Computer Programming (TAOCP).
+ * 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)
-{
- /*
- * Multiplicative hashing function.
- * Multiplication by the Prime number, closest to the golden
- * ratio of 2^32.
- */
- return val * UINT32_C(2654435761);
-}
-
struct tracecmd_filter_id_item *
tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id)
{
- int key = knuth_hash8(id);
+ int key = knuth_hash(id);
struct tracecmd_filter_id_item *item = hash->hash[key];
while (item) {
@@ -66,7 +42,7 @@ tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id)
void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id)
{
- int key = knuth_hash8(id);
+ int key = knuth_hash(id);
struct tracecmd_filter_id_item *item;
item = calloc(1, sizeof(*item));
@@ -81,7 +57,7 @@ void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id)
void tracecmd_filter_id_remove(struct tracecmd_filter_id *hash, int id)
{
- int key = knuth_hash8(id);
+ int key = knuth_hash(id);
struct tracecmd_filter_id_item **next = &hash->hash[key];
struct tracecmd_filter_id_item *item;
--
2.22.0.410.gd8fdbe21b5-goog
^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: [PATCH v2] trace-cmd: remove ununsed knuth_hash*() routines
2019-06-29 6:27 ` [PATCH v2] " Greg Thelen
@ 2019-07-01 12:23 ` Yordan Karadzhov (VMware)
2019-07-05 13:31 ` Steven Rostedt
1 sibling, 0 replies; 8+ messages in thread
From: Yordan Karadzhov (VMware) @ 2019-07-01 12:23 UTC (permalink / raw)
To: Greg Thelen, Steven Rostedt; +Cc: linux-trace-devel
On 29.06.19 г. 9:27 ч., Greg Thelen wrote:
> Neither 16-bit knuth_hash16() nor the 32-bit knuth_hash() are used.
> Delete them both.
>
> And rename the remaining function: knuth_hash8() => knuth_hash()
>
Thanks!
Reviewed-by: Yordan Karadzhov (VMware) <y.karadz@gmail.com>
> Signed-off-by: Greg Thelen <gthelen@google.com>
> ---
> kernel-shark/src/libkshark.c | 12 +++++-----
> lib/trace-cmd/trace-filter-hash.c | 40 +++++++------------------------
> 2 files changed, 14 insertions(+), 38 deletions(-)
>
> diff --git a/kernel-shark/src/libkshark.c b/kernel-shark/src/libkshark.c
> index 0f0a1bab4d5c..d2764e813194 100644
> --- a/kernel-shark/src/libkshark.c
> +++ b/kernel-shark/src/libkshark.c
> @@ -252,13 +252,13 @@ void kshark_free(struct kshark_context *kshark_ctx)
> free(kshark_ctx);
> }
>
> -static inline uint8_t knuth_hash8(uint32_t val)
> +static inline uint8_t knuth_hash(uint32_t val)
> {
> /*
> - * Hashing functions, based on Donald E. Knuth's Multiplicative
> - * hashing. See The Art of Computer Programming (TAOCP).
> - * Multiplication by the Prime number, closest to the golden
> - * ratio of 2^8.
> + * Small table hashing function adapted from Donald E. Knuth's 32 bit
> + * multiplicative hash. See The Art of Computer Programming (TAOCP).
> + * Multiplication by the Prime number, closest to the golden ratio of
> + * 2^8.
> */
> return UINT8_C(val) * UINT8_C(157);
> }
> @@ -282,7 +282,7 @@ kshark_add_task(struct kshark_context *kshark_ctx, int pid)
> struct kshark_task_list *list;
> uint8_t key;
>
> - key = knuth_hash8(pid);
> + key = knuth_hash(pid);
> list = kshark_find_task(kshark_ctx, key, pid);
> if (list)
> return list;
> diff --git a/lib/trace-cmd/trace-filter-hash.c b/lib/trace-cmd/trace-filter-hash.c
> index 39b28790e0bc..45ca68c2959e 100644
> --- a/lib/trace-cmd/trace-filter-hash.c
> +++ b/lib/trace-cmd/trace-filter-hash.c
> @@ -14,45 +14,21 @@
>
> #define FILTER_HASH_SIZE 256
>
> -/*
> - * 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)
> +static inline uint8_t knuth_hash(uint32_t val)
> {
> /*
> - * Multiplicative hashing function.
> - * Multiplication by the Prime number, closest to the golden
> - * ratio of 2^8.
> + * Small table hashing function adapted from Donald E. Knuth's 32 bit
> + * multiplicative hash. See The Art of Computer Programming (TAOCP).
> + * 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)
> -{
> - /*
> - * Multiplicative hashing function.
> - * Multiplication by the Prime number, closest to the golden
> - * ratio of 2^32.
> - */
> - return val * UINT32_C(2654435761);
> -}
> -
> struct tracecmd_filter_id_item *
> tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id)
> {
> - int key = knuth_hash8(id);
> + int key = knuth_hash(id);
> struct tracecmd_filter_id_item *item = hash->hash[key];
>
> while (item) {
> @@ -66,7 +42,7 @@ tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id)
>
> void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id)
> {
> - int key = knuth_hash8(id);
> + int key = knuth_hash(id);
> struct tracecmd_filter_id_item *item;
>
> item = calloc(1, sizeof(*item));
> @@ -81,7 +57,7 @@ void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id)
>
> void tracecmd_filter_id_remove(struct tracecmd_filter_id *hash, int id)
> {
> - int key = knuth_hash8(id);
> + int key = knuth_hash(id);
> struct tracecmd_filter_id_item **next = &hash->hash[key];
> struct tracecmd_filter_id_item *item;
>
>
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH v2] trace-cmd: remove ununsed knuth_hash*() routines
2019-06-29 6:27 ` [PATCH v2] " Greg Thelen
2019-07-01 12:23 ` Yordan Karadzhov (VMware)
@ 2019-07-05 13:31 ` Steven Rostedt
1 sibling, 0 replies; 8+ messages in thread
From: Steven Rostedt @ 2019-07-05 13:31 UTC (permalink / raw)
To: Greg Thelen; +Cc: Yordan Karadzhov (VMware), linux-trace-devel
On Fri, 28 Jun 2019 23:27:52 -0700
Greg Thelen <gthelen@google.com> wrote:
> Neither 16-bit knuth_hash16() nor the 32-bit knuth_hash() are used.
> Delete them both.
>
> And rename the remaining function: knuth_hash8() => knuth_hash()
>
> Signed-off-by: Greg Thelen <gthelen@google.com>
>
Thanks Greg, I applied this.
Note, when sending a v2 patch, it is best to start a new thread, as
some maintainer's patch maintenance systems (including mine) have
trouble dealing with patches within threads. That is, they tend to get
lost easier.
Thanks!
-- Steve
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2019-07-05 13:31 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-06-26 6:01 [PATCH] trace-cmd: remove ununsed knuth_hash*() routines Greg Thelen
2019-06-26 19:34 ` Steven Rostedt
2019-06-27 15:40 ` Yordan Karadzhov (VMware)
2019-06-27 16:15 ` Steven Rostedt
2019-06-28 15:55 ` Greg Thelen
2019-06-29 6:27 ` [PATCH v2] " Greg Thelen
2019-07-01 12:23 ` Yordan Karadzhov (VMware)
2019-07-05 13:31 ` Steven Rostedt
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.