On Thu, Jul 06, 2023 at 08:42:00PM +0600, NRK wrote:
> 1. use `unsigned int` to store the codepoints, this avoids waste on
> common case where `long` is 64bits. and POSIX guarantees `int` to be
> at least 32bits so there's no risk of truncation.
> 2. since switching to `unsigned int` cuts down the memory requirement by
> half, double the cache size from 64 to 128.
> 3. instead of a linear search, use a simple hash-table for O(1) lookups.
> ---
> dmenu.c | 1 -
> drw.c | 22 +++++++++++-----------
> util.h | 1 +
> 3 files changed, 12 insertions(+), 12 deletions(-)
>
> diff --git a/dmenu.c b/dmenu.c
> index 62f1089..40f93e0 100644
> --- a/dmenu.c
> +++ b/dmenu.c
> @@ -22,7 +22,6 @@
> /* macros */
> #define INTERSECT(x,y,w,h,r) (MAX(0, MIN((x)+(w),(r).x_org+(r).width) -
> MAX((x),(r).x_org)) \
> * MAX(0, MIN((y)+(h),(r).y_org+(r).height) -
> MAX((y),(r).y_org)))
> -#define LENGTH(X) (sizeof X / sizeof X[0])
> #define TEXTW(X) (drw_fontset_getwidth(drw, (X)) + lrpad)
>
> /* enums */
> diff --git a/drw.c b/drw.c
> index a58a2b4..00a6112 100644
> --- a/drw.c
> +++ b/drw.c
> @@ -238,8 +238,8 @@ drw_rect(Drw *drw, int x, int y, unsigned int w, unsigned
> int h, int filled, int
> int
> drw_text(Drw *drw, int x, int y, unsigned int w, unsigned int h, unsigned
> int lpad, const char *text, int invert)
> {
> - int i, ty, ellipsis_x = 0;
> - unsigned int tmpw, ew, ellipsis_w = 0, ellipsis_len;
> + int ty, ellipsis_x = 0;
> + unsigned int tmpw, ew, ellipsis_w = 0, ellipsis_len, hash;
> XftDraw *d = NULL;
> Fnt *usedfont, *curfont, *nextfont;
> int utf8strlen, utf8charlen, render = x || y || w || h;
> @@ -251,9 +251,7 @@ drw_text(Drw *drw, int x, int y, unsigned int w, unsigned
> int h, unsigned int lp
> XftResult result;
> int charexists = 0, overflow = 0;
> /* keep track of a couple codepoints for which we have no match. */
> - enum { nomatches_len = 64 };
> - static struct { long codepoint[nomatches_len]; unsigned int idx; }
> nomatches;
> - static unsigned int ellipsis_width = 0;
> + static unsigned int nomatches[128], ellipsis_width;
>
> if (!drw || (render && (!drw->scheme || !w)) || !text || !drw->fonts)
> return 0;
> @@ -338,11 +336,13 @@ drw_text(Drw *drw, int x, int y, unsigned int w,
> unsigned int h, unsigned int lp
> * character must be drawn. */
> charexists = 1;
>
> - for (i = 0; i < nomatches_len; ++i) {
> - /* avoid calling XftFontMatch if we know we
> won't find a match */
> - if (utf8codepoint == nomatches.codepoint[i])
> - goto no_match;
> - }
> + hash = (unsigned int)utf8codepoint;
> + hash = ((hash >> 16) ^ hash) * 0x21F0AAAD;
> + hash = ((hash >> 15) ^ hash) * 0xD35A2D97;
> + hash = ((hash >> 15) ^ hash) % LENGTH(nomatches);
> + /* avoid expensive XftFontMatch call when we know we
> won't find a match */
> + if (nomatches[hash] == utf8codepoint)
> + goto no_match;
>
> fccharset = FcCharSetCreate();
> FcCharSetAddChar(fccharset, utf8codepoint);
> @@ -371,7 +371,7 @@ drw_text(Drw *drw, int x, int y, unsigned int w, unsigned
> int h, unsigned int lp
> curfont->next = usedfont;
> } else {
> xfont_free(usedfont);
> - nomatches.codepoint[++nomatches.idx %
> nomatches_len] = utf8codepoint;
> + nomatches[hash] = utf8codepoint;
> no_match:
> usedfont = drw->fonts;
> }
> diff --git a/util.h b/util.h
> index f633b51..c0a50d4 100644
> --- a/util.h
> +++ b/util.h
> @@ -3,6 +3,7 @@
> #define MAX(A, B) ((A) > (B) ? (A) : (B))
> #define MIN(A, B) ((A) < (B) ? (A) : (B))
> #define BETWEEN(X, A, B) ((A) <= (X) && (X) <= (B))
> +#define LENGTH(X) (sizeof (X) / sizeof (X)[0])
>
> void die(const char *fmt, ...);
> void *ecalloc(size_t nmemb, size_t size);
> --
> 2.41.0
>
>
Hi,
A few questions and notes.
What hash algorithm is this exactly, it looks interesting? I've found it at:
https://github.com/skeeto/hash-prospector
Is that the one?
What's the measured performance improvement and wouldn't it increase collisions
vs a simple linear search?
I'm not sure we should change the assumption for ints to POSIX in dmenu in all
cases and assume 32-bit int (although a lot of software in practise does). But
this is very pedantic :)
Bit off-topic: recently I tested some software on MS-DOS with the OpenWatcom
compiler. It had 16-bit int and caught a bug in my code (lower-level parser
stuff).
--
Kind regards,
Hiltjo
