Dubious diff using --diff-algorithm=histogram

Commit Message

Alejandro Colomar April 4, 2023, 7:51 p.m. UTC

Hi,

I've met some strange diff with the histogram algorithm.  I know this
has a lot of magic in it, and it's probably not so trivial to improve,
and maybe my code base is so weird that it makes the histogram do crazy
stuff, but I wanted to show it to you in case there's anything that can
be improved.

So, patience is showing a better diff than histogram, which shouldn't
happen usually, and less in this case, where p++ is such a common thing
to do (although maybe this nxt_slow_path() macro is called a lot in the
file and confuses the histogram?).

Code base: <https://github.com/nginx/unit.git>

Cheers,
Alex

---

alx@asus5775:~/src/nginx/unit/space$ git diff --diff-algorithm=histogram

Comments

Alejandro Colomar April 4, 2023, 7:53 p.m. UTC | #1

On 4/4/23 21:51, Alejandro Colomar wrote:
> Hi,
> 
> I've met some strange diff with the histogram algorithm.  I know this
> has a lot of magic in it, and it's probably not so trivial to improve,
> and maybe my code base is so weird that it makes the histogram do crazy
> stuff, but I wanted to show it to you in case there's anything that can
> be improved.
> 
> So, patience is showing a better diff than histogram, which shouldn't
> happen usually, and less in this case, where p++ is such a common thing
> to do (although maybe this nxt_slow_path() macro is called a lot in the
> file and confuses the histogram?).
> 
> Code base: <https://github.com/nginx/unit.git>
> 
> Cheers,
> Alex

Now this has surprised me even more:

alx@asus5775:~/src/nginx/unit/space$ git diff --diff-algorithm=histogram 
diff --git a/src/nxt_http_parse.c b/src/nxt_http_parse.c
index 8646a6ce..3559f2e2 100644
--- a/src/nxt_http_parse.c
+++ b/src/nxt_http_parse.c
@@ -340,9 +340,9 @@ nxt_http_parse_request_line(nxt_http_request_parse_t *rp, u_char **pos,
 
 space_after_target:
 
-    if (nxt_slow_path(end - p < 10)) {
+    p++;
 
-        p++;
+    if (nxt_slow_path(end - p < 10)) {
 
         if (p == end) {
             return NXT_AGAIN;
alx@asus5775:~/src/nginx/unit/space$ git diff --diff-algorithm=patience 
diff --git a/src/nxt_http_parse.c b/src/nxt_http_parse.c
index 8646a6ce..3559f2e2 100644
--- a/src/nxt_http_parse.c
+++ b/src/nxt_http_parse.c
@@ -340,10 +340,10 @@ nxt_http_parse_request_line(nxt_http_request_parse_t *rp, u_char **pos,
 
 space_after_target:
 
+    p++;
+
     if (nxt_slow_path(end - p < 10)) {
 
-        p++;
-
         if (p == end) {
             return NXT_AGAIN;
         }

Alejandro Colomar April 28, 2023, 9:36 p.m. UTC | #2

Here's another example of a dubious diff using histogram:

@@ -50,8 +65,11 @@ .SH Examples
     nxt_unit_ctx_t   *ctx;
     nxt_unit_init_t  init;
 
-    bzero(&init, sizeof(nxt_unit_init_t));
+    if (argc == 3 && strcmp(argv[1], "-t") == 0) {
+        nthreads = atoi(argv[2]);
+    }
 
+    bzero(&init, sizeof(nxt_unit_init_t));
     init.callbacks.request_handler = &request_handler;
     init.callbacks.ready_handler = &ready_handler;
 


That call to bzero(3) is the only one in the entire file.
patience shows this instead:


@@ -50,8 +65,11 @@ .SH Examples
     nxt_unit_ctx_t   *ctx;
     nxt_unit_init_t  init;
 
+    if (argc == 3 && strcmp(argv[1], "-t") == 0) {
+        nthreads = atoi(argv[2]);
+    }
+
     bzero(&init, sizeof(nxt_unit_init_t));
-
     init.callbacks.request_handler = &request_handler;
     init.callbacks.ready_handler = &ready_handler;

Patch

diff --git a/src/nxt_http_parse.c b/src/nxt_http_parse.c
index 8646a6ce..92bdfb1f 100644
--- a/src/nxt_http_parse.c
+++ b/src/nxt_http_parse.c
@@ -340,10 +340,10 @@  nxt_http_parse_request_line(nxt_http_request_parse_t *rp, u_char **pos,
 
 space_after_target:
 
-    if (nxt_slow_path(end - p < 10)) {
-
         p++;
 
+    if (nxt_slow_path(end - p < 10)) {
+
         if (p == end) {
             return NXT_AGAIN;
         }
alx@asus5775:~/src/nginx/unit/space$ git diff --diff-algorithm=patience 
diff --git a/src/nxt_http_parse.c b/src/nxt_http_parse.c
index 8646a6ce..92bdfb1f 100644
--- a/src/nxt_http_parse.c
+++ b/src/nxt_http_parse.c
@@ -340,10 +340,10 @@  nxt_http_parse_request_line(nxt_http_request_parse_t *rp, u_char **pos,
 
 space_after_target:
 
+        p++;
+
     if (nxt_slow_path(end - p < 10)) {
 
-        p++;
-
         if (p == end) {
             return NXT_AGAIN;
         }
alx@asus5775:~/src/nginx/unit/space$ git diff --diff-algorithm=myers 
diff --git a/src/nxt_http_parse.c b/src/nxt_http_parse.c
index 8646a6ce..92bdfb1f 100644
--- a/src/nxt_http_parse.c
+++ b/src/nxt_http_parse.c
@@ -340,10 +340,10 @@  nxt_http_parse_request_line(nxt_http_request_parse_t *rp, u_char **pos,
 
 space_after_target:
 
-    if (nxt_slow_path(end - p < 10)) {
-
         p++;
 
+    if (nxt_slow_path(end - p < 10)) {
+
         if (p == end) {
             return NXT_AGAIN;
         }
alx@asus5775:~/src/nginx/unit/space$ git diff --diff-algorithm=minimal 
diff --git a/src/nxt_http_parse.c b/src/nxt_http_parse.c
index 8646a6ce..92bdfb1f 100644
--- a/src/nxt_http_parse.c
+++ b/src/nxt_http_parse.c
@@ -340,10 +340,10 @@  nxt_http_parse_request_line(nxt_http_request_parse_t *rp, u_char **pos,
 
 space_after_target:
 
-    if (nxt_slow_path(end - p < 10)) {
-
         p++;
 
+    if (nxt_slow_path(end - p < 10)) {
+
         if (p == end) {
             return NXT_AGAIN;
         }