{"thread":{"id":"61085","subject":"[GSoC][PATCH 0/1] add zero count optimization in ewah_bitmap.c","startedAt":"2024-03-10T16:26:19Z","lastAt":"2024-03-18T15:43:12Z","messageCount":8,"participants":["Aryan Gupta","Junio C Hamano","Karthik Nayak"],"isPatch":true,"patchVersion":1,"patchTotal":1},"messages":[{"id":"490325","messageId":"20240310162614.62691-1-garyan447@gmail.com","threadId":"61085","inReplyTo":null,"subject":"[GSoC][PATCH 0/1] add zero count optimization in ewah_bitmap.c","fromName":"Aryan Gupta","fromEmail":"garyan447@gmail.com","sentAt":"2024-03-10T16:26:13Z","receivedAt":"2024-03-10T16:26:19Z","isPatch":true,"sender":{"key":"garyan447@gmail.com","avatar":"https://avatars.githubusercontent.com/u/87857234?v=4"},"body":"Hey everyone\n\nI hope you are doing great. I came across a \"todo\" in the code base \nwhich was based on zero count optimization. I tried to fix do it but\nI am not sure if this was the required this or not. I would love your \nguidance on this. \n\nThank you. Have a nice day!\n\nRegards\nAryan Gupta\n\n\nAryan Gupta (1):\n add zero count optimization in ewah_bitmap.c\n\n ewah/ewah_bitmap.c | 9 +++++----\n 1 file changed, 5 insertions(+), 4 deletions(-)\n\n-- \n2.25.1\n\n"},{"id":"490326","messageId":"20240310162614.62691-2-garyan447@gmail.com","threadId":"61085","inReplyTo":"20240310162614.62691-1-garyan447@gmail.com","subject":"[GSoC][PATCH 1/1] add zero count optimization in ewah_bitmap.c","fromName":"Aryan Gupta","fromEmail":"garyan447@gmail.com","sentAt":"2024-03-10T16:26:14Z","receivedAt":"2024-03-10T16:26:21Z","isPatch":true,"sender":{"key":"garyan447@gmail.com","avatar":"https://avatars.githubusercontent.com/u/87857234?v=4"},"body":"Signed-off-by: Aryan Gupta \n---\n ewah/ewah_bitmap.c | 9 +++++----\n 1 file changed, 5 insertions(+), 4 deletions(-)\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex 8785cbc54a..9056829572 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -257,10 +257,11 @@ void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), vo\n \t\tfor (k = 0; k < rlw_get_literal_words(word); ++k) {\n \t\t\tint c;\n \n-\t\t\t/* todo: zero count optimization */\n-\t\t\tfor (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {\n-\t\t\t\tif ((self->buffer[pointer] & ((eword_t)1 << c)) != 0)\n-\t\t\t\t\tcallback(pos, payload);\n+\t\t\tif(self->buffer[pointer]) {\n+\t\t\t\tfor (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {\n+\t\t\t\t\tif (((eword_t)1 << c) != 0)\n+\t\t\t\t\t\tcallback(pos, payload);\n+\t\t\t\t}\n \t\t\t}\n \n \t\t\t++pointer;\n-- \n2.25.1\n\n"},{"id":"490360","messageId":"xmqqedcgvjik.fsf@gitster.g","threadId":"61085","inReplyTo":"20240310162614.62691-1-garyan447@gmail.com","subject":"Re: [GSoC][PATCH 0/1] add zero count optimization in ewah_bitmap.c","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-03-11T16:08:19Z","receivedAt":"2024-03-11T16:08:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Aryan Gupta writes:\n\n> Hey everyone\n>\n> I hope you are doing great. I came across a \"todo\" in the code base \n> which was based on zero count optimization. I tried to fix do it but\n> I am not sure if this was the required this or not.\n\nDo you mean that you are not sure if the improvement you made is\nwhat Vicent Marti meant by \"zero count optimization\" when e1273106\n(ewah: compressed bitmap implementation, 2013-11-14) was written?\n\nUnfortunatelly, \"what is \"zero count optimization\" in computer\nprogramming?\" does not produce great hits, and you are probably\nbetter off to ask who wrote that comment (Cc'ed).\n\nA few general pieces of advice:\n\n * We usually don't do a cover letter for a single patch (instead we\n write extra explanation after the three-dash line).\n\n * An optimization patch usually is expected to come with\n performance measurement, just like a bugfix patch is expected to\n come with tests that show existing breakages that change the\n behaviour for the better with the fix.\n\n * Pay attention to coding style, as deviating from existing style\n distracts reviewers and causes them to miss obvious bugs.\n\nThanks.\n"},{"id":"490361","messageId":"xmqqzfv4u4nd.fsf@gitster.g","threadId":"61085","inReplyTo":"20240310162614.62691-2-garyan447@gmail.com","subject":"Re: [GSoC][PATCH 1/1] add zero count optimization in ewah_bitmap.c","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-03-11T16:14:46Z","receivedAt":"2024-03-11T16:14:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Aryan Gupta writes:\n\n> Signed-off-by: Aryan Gupta \n> ---\n> ewah/ewah_bitmap.c | 9 +++++----\n> 1 file changed, 5 insertions(+), 4 deletions(-)\n>\n> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\n> index 8785cbc54a..9056829572 100644\n> --- a/ewah/ewah_bitmap.c\n> +++ b/ewah/ewah_bitmap.c\n> @@ -257,10 +257,11 @@ void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), vo\n> \t\tfor (k = 0; k < rlw_get_literal_words(word); ++k) {\n> \t\t\tint c;\n> \n> -\t\t\t/* todo: zero count optimization */\n> -\t\t\tfor (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {\n> -\t\t\t\tif ((self->buffer[pointer] & ((eword_t)1 << c)) != 0)\n> -\t\t\t\t\tcallback(pos, payload);\n> +\t\t\tif(self->buffer[pointer]) {\n> +\t\t\t\tfor (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {\n> +\t\t\t\t\tif (((eword_t)1 << c) != 0)\n> +\t\t\t\t\t\tcallback(pos, payload);\n> +\t\t\t\t}\n> \t\t\t}\n\nWhen self->buffer[pointer] (let's call it the eword) is zero, both\nyour rewritten version and the original version does the same thing\nand will not call the callback at all, but in all other cases,\ndoesn't your rewrite change the behavior?\n\nImagine the eword is 01. The original starts the loop with c==0,\nnotices that the LSB is on by masking the eword in the bitmap with\n((eword_t)1< wrote:\n>\n> Aryan Gupta writes:\n>\n> > Hey everyone\n> >\n> > I hope you are doing great. I came across a \"todo\" in the code base\n> > which was based on zero count optimization. I tried to fix do it but\n> > I am not sure if this was the required this or not.\n>\n> Do you mean that you are not sure if the improvement you made is\n> what Vicent Marti meant by \"zero count optimization\" when e1273106\n> (ewah: compressed bitmap implementation, 2013-11-14) was written?\n>\nYes.\n> Unfortunatelly, \"what is \"zero count optimization\" in computer\n> programming?\" does not produce great hits, and you are probably\n> better off to ask who wrote that comment (Cc'ed).\n>\nSure.\n> A few general pieces of advice:\n>\n> * We usually don't do a cover letter for a single patch (instead we\n> write extra explanation after the three-dash line).\n>\n> * An optimization patch usually is expected to come with\n> performance measurement, just like a bugfix patch is expected to\n> come with tests that show existing breakages that change the\n> behaviour for the better with the fix.\n>\n> * Pay attention to coding style, as deviating from existing style\n> distracts reviewers and causes them to miss obvious bugs.\n>\n> Thanks.\n\nOkay will take care of this. Thanks a lot.\n"},{"id":"490589","messageId":"20240313223751.50816-1-garyan447@gmail.com","threadId":"61085","inReplyTo":"20240310162614.62691-1-garyan447@gmail.com","subject":"[GSoC][PATCH v2] Optimize ewah_bitmap.c for efficiency using trailing zeros for set bit iteration","fromName":"Aryan Gupta","fromEmail":"garyan447@gmail.com","sentAt":"2024-03-13T22:37:51Z","receivedAt":"2024-03-13T22:38:01Z","isPatch":true,"sender":{"key":"garyan447@gmail.com","avatar":"https://avatars.githubusercontent.com/u/87857234?v=4"},"body":"Signed-off-by: Aryan Gupta \n---\n\nThank you Vicent for the guidance. I am still not sure how \nto do the performance measurement for this improvement. Any \nguidance would be appreciated. \n\n ewah/ewah_bitmap.c | 13 ++++++++-----\n 1 file changed, 8 insertions(+), 5 deletions(-)\n\ndiff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\nindex 8785cbc54a..1a75f50682 100644\n--- a/ewah/ewah_bitmap.c\n+++ b/ewah/ewah_bitmap.c\n@@ -257,12 +257,15 @@ void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), vo\n \t\tfor (k = 0; k < rlw_get_literal_words(word); ++k) {\n \t\t\tint c;\n \n-\t\t\t/* todo: zero count optimization */\n-\t\t\tfor (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {\n-\t\t\t\tif ((self->buffer[pointer] & ((eword_t)1 << c)) != 0)\n-\t\t\t\t\tcallback(pos, payload);\n+\t\t\teword_t bitset = self->buffer[pointer]; \n+\t\t\twhile(bitset != 0) {\n+\t\t\t\teword_t t = bitset & -bitset; \n+\t\t\t\tint r = __builtin_ctzl(bitset); \n+\t\t\t\tbitset ^= t; \n+\t\t\t\tcallback(pos+r, payload);\n \t\t\t}\n-\n+\t\t\t\n+\t\t\tpos += BITS_IN_EWORD;\n \t\t\t++pointer;\n \t\t}\n \t}\n-- \n2.25.1\n\n"},{"id":"490827","messageId":"CAOLa=ZSijjnfa8UEEWPi8Cb7Q1hLbgrez7VX-LxshmUhNM29DQ@mail.gmail.com","threadId":"61085","inReplyTo":"20240313223751.50816-1-garyan447@gmail.com","subject":"Re: [GSoC][PATCH v2] Optimize ewah_bitmap.c for efficiency using trailing zeros for set bit iteration","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-03-18T03:08:41Z","receivedAt":"2024-03-18T03:08:43Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Aryan Gupta writes:\n\nHello,\n\n> Signed-off-by: Aryan Gupta \n> ---\n>\n> Thank you Vicent for the guidance. I am still not sure how\n> to do the performance measurement for this improvement. Any\n> guidance would be appreciated.\n>\n\nI guess there is some off-list discussion here. That along with the fact\nthat the commit message is missing makes it really hard to understand\nhow this is better than what was here already.\n\nThe guidelines ('Documentation/SubmittingPatches') also state how to\ndraft the commit message. This patch only seems to have a title, it is\nrecommend to add a description as to why this change is being made.\n\n>\n> ewah/ewah_bitmap.c | 13 ++++++++-----\n> 1 file changed, 8 insertions(+), 5 deletions(-)\n>\n> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\n> index 8785cbc54a..1a75f50682 100644\n> --- a/ewah/ewah_bitmap.c\n> +++ b/ewah/ewah_bitmap.c\n> @@ -257,12 +257,15 @@ void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), vo\n> \t\tfor (k = 0; k < rlw_get_literal_words(word); ++k) {\n> \t\t\tint c;\n>\n> -\t\t\t/* todo: zero count optimization */\n> -\t\t\tfor (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {\n> -\t\t\t\tif ((self->buffer[pointer] & ((eword_t)1 << c)) != 0)\n> -\t\t\t\t\tcallback(pos, payload);\n> +\t\t\teword_t bitset = self->buffer[pointer];\n> +\t\t\twhile(bitset != 0) {\n> +\t\t\t\teword_t t = bitset & -bitset;\n> +\t\t\t\tint r = __builtin_ctzl(bitset);\n> +\t\t\t\tbitset ^= t;\n> +\t\t\t\tcallback(pos+r, payload);\n> \t\t\t}\n> -\n> +\t\t\t\n> +\t\t\tpos += BITS_IN_EWORD;\n> \t\t\t++pointer;\n> \t\t}\n> \t}\n\nThe bit manipulation done here is slightly hard to comprehend, it would\nbe nice if you could also add some comments as to what is being done\nhere and why.\n"},{"id":"490875","messageId":"xmqqr0g7k0lj.fsf@gitster.g","threadId":"61085","inReplyTo":"CAOLa=ZSijjnfa8UEEWPi8Cb7Q1hLbgrez7VX-LxshmUhNM29DQ@mail.gmail.com","subject":"Re: [GSoC][PATCH v2] Optimize ewah_bitmap.c for efficiency using trailing zeros for set bit iteration","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-03-18T15:42:48Z","receivedAt":"2024-03-18T15:43:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karthik Nayak writes:\n\n> Aryan Gupta writes:\n>\n> Hello,\n>\n>> Signed-off-by: Aryan Gupta \n>> ---\n>>\n>> Thank you Vicent for the guidance. I am still not sure how\n>> to do the performance measurement for this improvement. Any\n>> guidance would be appreciated.\n>>\n>\n> I guess there is some off-list discussion here. That along with the fact\n> that the commit message is missing makes it really hard to understand\n> how this is better than what was here already.\n>\n> The guidelines ('Documentation/SubmittingPatches') also state how to\n> draft the commit message. This patch only seems to have a title, it is\n> recommend to add a description as to why this change is being made.\n\nYes.\n\n>> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c\n>> index 8785cbc54a..1a75f50682 100644\n>> --- a/ewah/ewah_bitmap.c\n>> +++ b/ewah/ewah_bitmap.c\n>> @@ -257,12 +257,15 @@ void ewah_each_bit(struct ewah_bitmap *self, void (*callback)(size_t, void*), vo\n>> \t\tfor (k = 0; k < rlw_get_literal_words(word); ++k) {\n>> \t\t\tint c;\n>>\n>> -\t\t\t/* todo: zero count optimization */\n>> -\t\t\tfor (c = 0; c < BITS_IN_EWORD; ++c, ++pos) {\n>> -\t\t\t\tif ((self->buffer[pointer] & ((eword_t)1 << c)) != 0)\n>> -\t\t\t\t\tcallback(pos, payload);\n>> +\t\t\teword_t bitset = self->buffer[pointer];\n>> +\t\t\twhile(bitset != 0) {\n>> +\t\t\t\teword_t t = bitset & -bitset;\n>> +\t\t\t\tint r = __builtin_ctzl(bitset);\n>> +\t\t\t\tbitset ^= t;\n>> +\t\t\t\tcallback(pos+r, payload);\n>> \t\t\t}\n>> -\n>> +\t\t\t\n>> +\t\t\tpos += BITS_IN_EWORD;\n>> \t\t\t++pointer;\n>> \t\t}\n>> \t}\n>\n> The bit manipulation done here is slightly hard to comprehend, it would\n> be nice if you could also add some comments as to what is being done\n> here and why.\n\nIn addition, this patch assumes that __builtin_ctzl() function is\nalways available no matter what environment the code is built on,\nwhich I am not sure is a safe. Quite honestory, I suspect that the\nwhole of \"todo\" is to seamlessly detect the presense of the builtin\nsupport to count the top zero bit, use it only when it is there, and\ngiving a fallback implementation when it does not exist. The code\nitself to use the builtin is only 20% of that effort ;-)\n\nAnd of course, there is benchmark. To show how much better\nperformance gets for people with that function, and more importantly\nto show that the performance does not degrade for those who are\nwithout.\n\nThanks.\n"}]}