* [musl] [PATCH] improve strerror speed
@ 2020-03-03 21:33 Timo Teräs
2020-03-04 9:06 ` Alexander Monakov
0 siblings, 1 reply; 4+ messages in thread
From: Timo Teräs @ 2020-03-03 21:33 UTC (permalink / raw)
To: musl; +Cc: Timo Teräs
change the current O(n) lookup to O(1) based on the machinery
described in "How To Write Shared Libraries" (Appendix B).
---
src/errno/__strerror.h | 13 ++++++-------
src/errno/strerror.c | 41 ++++++++++++++++++++++++++---------------
2 files changed, 32 insertions(+), 22 deletions(-)
diff --git a/src/errno/__strerror.h b/src/errno/__strerror.h
index 2f04d400..ec6044e6 100644
--- a/src/errno/__strerror.h
+++ b/src/errno/__strerror.h
@@ -1,8 +1,9 @@
-/* This file is sorted such that 'errors' which represent exceptional
- * conditions under which a correct program may fail come first, followed
- * by messages that indicate an incorrect program or system failure. The
- * macro E() along with double-inclusion is used to ensure that ordering
- * of the strings remains synchronized. */
+/* The first '0' mapping will be used for error codes that
+ * are not explicitly mentioned here.
+ * This file is included multiple times to generate struct
+ * populate it's content and create a fast lookup index to it. */
+
+E(0, "No error information")
E(EILSEQ, "Illegal byte sequence")
E(EDOM, "Domain error")
@@ -101,5 +102,3 @@ E(EDQUOT, "Quota exceeded")
E(ENOMEDIUM, "No medium found")
E(EMEDIUMTYPE, "Wrong medium type")
E(EMULTIHOP, "Multihop attempted")
-
-E(0, "No error information")
diff --git a/src/errno/strerror.c b/src/errno/strerror.c
index e3ed771a..54a9191e 100644
--- a/src/errno/strerror.c
+++ b/src/errno/strerror.c
@@ -1,30 +1,41 @@
#include <errno.h>
+#include <stddef.h>
#include <string.h>
#include "locale_impl.h"
-#define E(a,b) ((unsigned char)a),
-static const unsigned char errid[] = {
+/* mips has one error code outside of the 8-bit range due to a
+ * historical typo, so we just remap it. */
+#if EDQUOT==1133
+#define EDQUOT_ORIG 1133
+#undef EDQUOT
+#define EDQUOT 109
+#endif
+
+static const struct errmsgstr_t {
+#define E(n, s) char str##n[sizeof(s)];
+#include "__strerror.h"
+#undef E
+} errmsgstr = {
+#define E(n, s) s,
#include "__strerror.h"
+#undef E
};
-#undef E
-#define E(a,b) b "\0"
-static const char errmsg[] =
+static const unsigned short errmsgidx[] = {
+#define E(n, s) [n] = offsetof(struct errmsgstr_t, str##n),
#include "__strerror.h"
-;
+#undef E
+};
char *__strerror_l(int e, locale_t loc)
{
const char *s;
- int i;
- /* mips has one error code outside of the 8-bit range due to a
- * historical typo, so we just remap it. */
- if (EDQUOT==1133) {
- if (e==109) e=-1;
- else if (e==EDQUOT) e=109;
- }
- for (i=0; errid[i] && errid[i] != e; i++);
- for (s=errmsg; i; s++, i--) for (; *s; s++);
+#ifdef EDQUOT_ORIG
+ if (e==EDQUOT) e=0;
+ else if (e==EDQUOT_ORIG) e=EDQUOT;
+#endif
+ if (e < 0 || e >= sizeof(errmsgidx)/sizeof(errmsgidx[0])) e = 0;
+ s = (char *)&errmsgstr + errmsgidx[e];
return (char *)LCTRANS(s, LC_MESSAGES, loc);
}
--
2.25.1
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [musl] [PATCH] improve strerror speed
2020-03-03 21:33 [musl] [PATCH] improve strerror speed Timo Teräs
@ 2020-03-04 9:06 ` Alexander Monakov
2020-03-04 9:17 ` Timo Teras
2020-03-04 9:27 ` [musl] [PATCH v2] " Timo Teräs
0 siblings, 2 replies; 4+ messages in thread
From: Alexander Monakov @ 2020-03-04 9:06 UTC (permalink / raw)
To: musl; +Cc: Timo Teräs
[-- Attachment #1: Type: text/plain, Size: 1596 bytes --]
Hi,
On Tue, 3 Mar 2020, Timo Teräs wrote:
> change the current O(n) lookup to O(1) based on the machinery
> described in "How To Write Shared Libraries" (Appendix B).
I'm curious about the background of this change, did the inefficiency
came up in practice?
> --- a/src/errno/__strerror.h
> +++ b/src/errno/__strerror.h
> @@ -1,8 +1,9 @@
> -/* This file is sorted such that 'errors' which represent exceptional
> - * conditions under which a correct program may fail come first, followed
> - * by messages that indicate an incorrect program or system failure. The
> - * macro E() along with double-inclusion is used to ensure that ordering
> - * of the strings remains synchronized. */
> +/* The first '0' mapping will be used for error codes that
> + * are not explicitly mentioned here.
> + * This file is included multiple times to generate struct
> + * populate it's content and create a fast lookup index to it. */
The last sentence seems to have typos ("a struct,", "its").
I would write the comment like this:
/* The first entry is a catch-all for codes not enumerated here.
* This file is included multiple times to declare and define a structure
* with messages, and then to define a lookup table translating error codes
* to offsets of corresponding fields in the structure. */
> + if (e < 0 || e >= sizeof(errmsgidx)/sizeof(errmsgidx[0])) e = 0;
I think usually in musl such range checks are written in an easier-to-optimize
form that tests the argument in an unsigned type, e.g. like this:
if ((size_t)e >= sizeof errmsgidx / sizeof *errmsgidx) e = 0;
Thanks.
Alexander
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [musl] [PATCH] improve strerror speed
2020-03-04 9:06 ` Alexander Monakov
@ 2020-03-04 9:17 ` Timo Teras
2020-03-04 9:27 ` [musl] [PATCH v2] " Timo Teräs
1 sibling, 0 replies; 4+ messages in thread
From: Timo Teras @ 2020-03-04 9:17 UTC (permalink / raw)
To: Alexander Monakov; +Cc: musl
On Wed, 4 Mar 2020 12:06:21 +0300 (MSK)
Alexander Monakov <amonakov@ispras.ru> wrote:
> Hi,
>
> On Tue, 3 Mar 2020, Timo Teräs wrote:
>
> > change the current O(n) lookup to O(1) based on the machinery
> > described in "How To Write Shared Libraries" (Appendix B).
>
> I'm curious about the background of this change, did the inefficiency
> came up in practice?
Yes, it's the openssl querying all possible strerrors:
https://github.com/openssl/openssl/blob/master/crypto/err/err.c#L181
That makes it up to valgrind --tool=callgrind to peak the strerror_l in
performance analysis on short running programs:
673,622 /data/aports/main/musl/src/musl-1.1.24/src/errno/strerror.c:strerror_l [/lib/ld-musl-x86_64.so.1]
This change completely removes strerror from there.
> > --- a/src/errno/__strerror.h
> > +++ b/src/errno/__strerror.h
> > @@ -1,8 +1,9 @@
> > -/* This file is sorted such that 'errors' which represent
> > exceptional
> > - * conditions under which a correct program may fail come first,
> > followed
> > - * by messages that indicate an incorrect program or system
> > failure. The
> > - * macro E() along with double-inclusion is used to ensure that
> > ordering
> > - * of the strings remains synchronized. */
> > +/* The first '0' mapping will be used for error codes that
> > + * are not explicitly mentioned here.
> > + * This file is included multiple times to generate struct
> > + * populate it's content and create a fast lookup index to it. */
>
> The last sentence seems to have typos ("a struct,", "its").
> I would write the comment like this:
>
> /* The first entry is a catch-all for codes not enumerated here.
> * This file is included multiple times to declare and define a
> structure
> * with messages, and then to define a lookup table translating error
> codes
> * to offsets of corresponding fields in the structure. */
>
> > + if (e < 0 || e >= sizeof(errmsgidx)/sizeof(errmsgidx[0]))
> > e = 0;
>
> I think usually in musl such range checks are written in an
> easier-to-optimize form that tests the argument in an unsigned type,
> e.g. like this:
>
> if ((size_t)e >= sizeof errmsgidx / sizeof *errmsgidx) e = 0;
Thanks, will update and resend.
Timo
^ permalink raw reply [flat|nested] 4+ messages in thread
* [musl] [PATCH v2] improve strerror speed
2020-03-04 9:06 ` Alexander Monakov
2020-03-04 9:17 ` Timo Teras
@ 2020-03-04 9:27 ` Timo Teräs
1 sibling, 0 replies; 4+ messages in thread
From: Timo Teräs @ 2020-03-04 9:27 UTC (permalink / raw)
To: musl; +Cc: Timo Teräs
change the current O(n) lookup to O(1) based on the machinery
described in "How To Write Shared Libraries" (Appendix B).
---
src/errno/__strerror.h | 13 ++++++-------
src/errno/strerror.c | 41 ++++++++++++++++++++++++++---------------
2 files changed, 32 insertions(+), 22 deletions(-)
diff --git a/src/errno/__strerror.h b/src/errno/__strerror.h
index 2f04d400..2d992da5 100644
--- a/src/errno/__strerror.h
+++ b/src/errno/__strerror.h
@@ -1,8 +1,9 @@
-/* This file is sorted such that 'errors' which represent exceptional
- * conditions under which a correct program may fail come first, followed
- * by messages that indicate an incorrect program or system failure. The
- * macro E() along with double-inclusion is used to ensure that ordering
- * of the strings remains synchronized. */
+/* The first entry is a catch-all for codes not enumerated here.
+ * This file is included multiple times to declare and define a structure
+ * with these messages, and then to define a lookup table translating
+ * error codes to offsets of corresponding fields in the structure. */
+
+E(0, "No error information")
E(EILSEQ, "Illegal byte sequence")
E(EDOM, "Domain error")
@@ -101,5 +102,3 @@ E(EDQUOT, "Quota exceeded")
E(ENOMEDIUM, "No medium found")
E(EMEDIUMTYPE, "Wrong medium type")
E(EMULTIHOP, "Multihop attempted")
-
-E(0, "No error information")
diff --git a/src/errno/strerror.c b/src/errno/strerror.c
index e3ed771a..918fbce9 100644
--- a/src/errno/strerror.c
+++ b/src/errno/strerror.c
@@ -1,30 +1,41 @@
#include <errno.h>
+#include <stddef.h>
#include <string.h>
#include "locale_impl.h"
-#define E(a,b) ((unsigned char)a),
-static const unsigned char errid[] = {
+/* mips has one error code outside of the 8-bit range due to a
+ * historical typo, so we just remap it. */
+#if EDQUOT==1133
+#define EDQUOT_ORIG 1133
+#undef EDQUOT
+#define EDQUOT 109
+#endif
+
+static const struct errmsgstr_t {
+#define E(n, s) char str##n[sizeof(s)];
+#include "__strerror.h"
+#undef E
+} errmsgstr = {
+#define E(n, s) s,
#include "__strerror.h"
+#undef E
};
-#undef E
-#define E(a,b) b "\0"
-static const char errmsg[] =
+static const unsigned short errmsgidx[] = {
+#define E(n, s) [n] = offsetof(struct errmsgstr_t, str##n),
#include "__strerror.h"
-;
+#undef E
+};
char *__strerror_l(int e, locale_t loc)
{
const char *s;
- int i;
- /* mips has one error code outside of the 8-bit range due to a
- * historical typo, so we just remap it. */
- if (EDQUOT==1133) {
- if (e==109) e=-1;
- else if (e==EDQUOT) e=109;
- }
- for (i=0; errid[i] && errid[i] != e; i++);
- for (s=errmsg; i; s++, i--) for (; *s; s++);
+#ifdef EDQUOT_ORIG
+ if (e==EDQUOT) e=0;
+ else if (e==EDQUOT_ORIG) e=EDQUOT;
+#endif
+ if ((size_t)e >= sizeof errmsgidx / sizeof *errmsgidx) e = 0;
+ s = (char *)&errmsgstr + errmsgidx[e];
return (char *)LCTRANS(s, LC_MESSAGES, loc);
}
--
2.25.1
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2020-03-04 9:27 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-03-03 21:33 [musl] [PATCH] improve strerror speed Timo Teräs
2020-03-04 9:06 ` Alexander Monakov
2020-03-04 9:17 ` Timo Teras
2020-03-04 9:27 ` [musl] [PATCH v2] " Timo Teräs
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).