[PATCH 1/3] uclient-fetch: Make request_types sorted to optimize search

[Elliott Mitchell]

On Fri, Apr 07, 2023 at 12:39:07AM +0300, Sergey Ponomarev wrote:
> Signed-off-by: Sergey Ponomarev <stokito at gmail.com>
> ---

That is a *very* short commit message.  If self-explanatory that is
enough, but I tend to be wary of patches with so little exposition.

Mostly you're sorting things, which does tend to ease maintainance.

> @@ -40,11 +40,11 @@ enum auth_type {
>  };
>  
>  enum request_type {
> +	REQ_DELETE,
>  	REQ_GET,
>  	REQ_HEAD,
>  	REQ_POST,
>  	REQ_PUT,
> -	REQ_DELETE,
>  	__REQ_MAX
>  };
>  

This is missing the comment you added below.

> @@ -57,12 +57,13 @@ enum http_state {
>  	HTTP_STATE_ERROR,
>  };
>  
> +// Must be sorted aplhabeticaly
>  static const char * const request_types[__REQ_MAX] = {
> +	[REQ_DELETE] = "DELETE",
>  	[REQ_GET] = "GET",
>  	[REQ_HEAD] = "HEAD",
>  	[REQ_POST] = "POST",
>  	[REQ_PUT] = "PUT",
> -	[REQ_DELETE] = "DELETE",
>  };
>  
>  struct uclient_http {

If you're going to add a comment like this, you should also add it to
request_type.  I'm unsure what the style standard is here, the maintainer
may want /* */ instead of //.

Also, "Must be sorted alphabetically".

Not the topic of this commit, but appears http_state should be before
request_type or else after request_types (splitting "request_type" and
"request_types" is a Bad Thing).


> @@ -991,11 +992,15 @@ uclient_http_set_request_type(struct uclient *cl, const char *type)
>  		return -1;
>  
>  	for (i = 0; i < ARRAY_SIZE(request_types); i++) {
> -		if (strcmp(request_types[i], type) != 0)
> +		int c = strcmp(request_types[i], type);
> +		if (c < 0) {
>  			continue;
> -
> -		uh->req_type = i;
> -		return 0;
> +		} else if (c == 0) {
> +			uh->req_type = i;
> +			return 0;
> +		} else {
> +			return -1;
> +		}
>  	}
>  
>  	return -1;

I am not the maintainer for this OpenWRT repository so this is strictly
an observer's opinion.

If you're truly aiming for performance, you've left a lot on the table.
There is a classic algorithm for this situation:

@@ -982,7 +984,8 @@ int
 uclient_http_set_request_type(struct uclient *cl, const char *type)
 {
 	struct uclient_http *uh = container_of(cl, struct uclient_http, uc);
-	unsigned int i;
+	unsigned lo = 0, hi = __REQ_MAX, mid;
+	int res;
 
 	if (cl->backend != &uclient_backend_http)
 		return -1;
@@ -990,15 +993,17 @@
 	if (uh->state > HTTP_STATE_INIT)
 		return -1;
 
-	for (i = 0; i < ARRAY_SIZE(request_types); i++) {
-		if (strcmp(request_types[i], type) != 0)
-			continue;
-
-		uh->req_type = i;
-		return 0;
+	while (res = strcmp(request_types[mid = (hi + lo) / 2], type)) {
+		if (res < 0)
+			hi = mid;
+		else
+			lo = mid + 1;
+		if (lo == hi)
+			return -1;
 	}
 
-	return -1;
+	uh->req_type = mid;
+	return 0;
 }
 
 int

What you've got reduces runtime by 50% on average.  The above does
log(2).  I could see the maintainer preferring:

@@ -982,7 +984,7 @@ int
 uclient_http_set_request_type(struct uclient *cl, const char *type)
 {
 	struct uclient_http *uh = container_of(cl, struct uclient_http, uc);
-	unsigned int i;
+	unsigned lo = 0, hi = __REQ_MAX;
 
 	if (cl->backend != &uclient_backend_http)
 		return -1;
@@ -990,13 +992,19 @@ uclient_http_set_request_type(struct uclient *cl, const char *type)
 	if (uh->state > HTTP_STATE_INIT)
 		return -1;
 
-	for (i = 0; i < ARRAY_SIZE(request_types); i++) {
-		if (strcmp(request_types[i], type) != 0)
-			continue;
+	do {
+		const unsigned mid = (hi + lo) / 2;
+		const int res = strcmp(request_types[mid], type);
 
-		uh->req_type = i;
-		return 0;
-	}
+		if (res < 0)
+			hi = mid;
+		else if (res > 0)
+			lo = mid + 1;
+		else {
+			uh->req_type = mid;
+			return 0;
+		}
+ 	} while (hi != lo);
 
 	return -1;
 }

I strongly prefer the former as it has all early returns as the same type
(failure) and has the end being different.  Whereas this one, one early
return is success and most are failures.

Notable request_types[ARRAY_SIZE(request_types)] is an invalid entry.
This is a presently harmless bug.

Overall not a bad idea, just some patch issues.

If you use either of the above, both are:
"Signed-off-by: Elliott Mitchell <ehem+openwrt at m5p.com>"


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \BS (    |         ehem+sigmsg at m5p.com  PGP 87145445         |    )   /
  \_CS\   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
8A19\___\_|_/58D2 7E3D DDF4 7BA6 <-PGP-> 41D1 B375 37D0 8714\_|_/___/5445