Re: [PATCH 1/3] uclient-fetch: Make request_types sorted to optimize search
On Fri, Apr 07, 2023 at 12:39:07AM +0300, Sergey Ponomarev wrote:
> Signed-off-by: Sergey Ponomarev
> ---
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 != _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 != _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 "
--
(\___(\___(\__ --=> 8-) EHM <=-- __/)___/)___/)
\BS (| ehem+sig...@m5p.com PGP 87145445
Re: [PATCH 1/3] uclient-fetch: Make request_types sorted to optimize search
The sender domain has a DMARC Reject/Quarantine policy which disallows
sending mailing list messages using the original "From" header.
To mitigate this problem, the original message has been wrapped
automatically by the mailing list software.--- Begin Message ---
Op 06-04-2023 om 23:39 schreef Sergey Ponomarev:
Signed-off-by: Sergey Ponomarev
---
uclient-http.c | 17 +++--
1 file changed, 11 insertions(+), 6 deletions(-)
diff --git a/uclient-http.c b/uclient-http.c
index c2bba6b..80d4495 100644
--- a/uclient-http.c
+++ b/uclient-http.c
@@ -40,11 +40,11 @@ enum auth_type {
};
enum request_type {
+ REQ_DELETE,
REQ_GET,
REQ_HEAD,
REQ_POST,
REQ_PUT,
- REQ_DELETE,
__REQ_MAX
};
@@ -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 {
@@ -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;
Hi Sergey,
Seems okay, but one remark. An else branch after statements like
continue or return is not needed. Without the else the code saves
indents and becomes clearer.
So:
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;
+ }
+ if (c == 0) {
+ uh->req_type = i;
+ return 0;
+ }
+ return -1;
}
return -1;
Also it looks like the return -1 after the loop can/should be dropped as
that (iff request_types is sorted and contains > 0 elements) can never
be reached. Or the return at the end of the loop block could be dropped
as it provides a neglectible optimalisation.
Regards, Paul
--- End Message ---
___
openwrt-devel mailing list
openwrt-devel@lists.openwrt.org
https://lists.openwrt.org/mailman/listinfo/openwrt-devel
[PATCH 1/3] uclient-fetch: Make request_types sorted to optimize search
Signed-off-by: Sergey Ponomarev
---
uclient-http.c | 17 +++--
1 file changed, 11 insertions(+), 6 deletions(-)
diff --git a/uclient-http.c b/uclient-http.c
index c2bba6b..80d4495 100644
--- a/uclient-http.c
+++ b/uclient-http.c
@@ -40,11 +40,11 @@ enum auth_type {
};
enum request_type {
+ REQ_DELETE,
REQ_GET,
REQ_HEAD,
REQ_POST,
REQ_PUT,
- REQ_DELETE,
__REQ_MAX
};
@@ -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 {
@@ -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;
--
2.37.2
___
openwrt-devel mailing list
openwrt-devel@lists.openwrt.org
https://lists.openwrt.org/mailman/listinfo/openwrt-devel
