This is not ripe yet, but I figured I'd share it.
Since some time I find ksh(1) slow at startup. I use
HISTFILE=~/.ksh_history and HISTSIZE=20000; currently my ksh_history is
24487 lines long.
Even if you're above HISTSIZE lines, ksh will avoid truncating your
HISTFILE until it has grown by ~25%. The problem is that when you go
over HISTSIZE lines, the oldest lines in the history array are freed and
the whole array is moved. Since those lines are oldest, afree() needs
to walk to the end of the freelist. history_load() calls histsave() and
thus afree() in a loop, which is kinda expensive.
Since afree() is the worst offender I thought about making it snappier
using a RB tree, which seems to solve the slowness here. wip diff, use
at your own risk...
Index: alloc.c
===================================================================
RCS file: /d/cvs/src/bin/ksh/alloc.c,v
retrieving revision 1.16
diff -u -p -r1.16 alloc.c
--- alloc.c 29 May 2017 13:09:17 -0000 1.16
+++ alloc.c 24 Jul 2017 17:44:00 -0000
@@ -6,20 +6,35 @@
* area-based allocation built on malloc/free
*/
+#include <sys/tree.h>
#include <stdint.h>
#include <stdlib.h>
#include "sh.h"
+/* The key is the address of the node */
struct link {
- struct link *prev;
- struct link *next;
+ RB_ENTRY(link) entry;
};
+static int
+addrcmp(struct link *l1, struct link *l2)
+{
+ uintptr_t u1 = (uintptr_t)l1, u2 = (uintptr_t)l2;
+ return (u1 < u2 ? -1 : u1 > u2);
+}
+
+RB_HEAD(addrtree, link);
+RB_GENERATE_STATIC(addrtree, link, entry, addrcmp);
+
Area *
ainit(Area *ap)
{
- ap->freelist = NULL;
+ ap->tree = calloc(1, sizeof(*ap->tree));
+ if (ap->tree == NULL)
+ abort(); /* XXX */
+ RB_INIT(ap->tree);
+
return ap;
}
@@ -28,11 +43,18 @@ afreeall(Area *ap)
{
struct link *l, *l2;
- for (l = ap->freelist; l != NULL; l = l2) {
- l2 = l->next;
+ RB_FOREACH_SAFE(l, addrtree, ap->tree, l2) {
+ RB_REMOVE(addrtree, ap->tree, l);
free(l);
}
- ap->freelist = NULL;
+}
+
+void
+adestroy(Area *ap)
+{
+ afreeall(ap);
+ free(ap->tree);
+ ap->tree = NULL;
}
#define L2P(l) ( (void *)(((char *)(l)) + sizeof(struct link)) )
@@ -50,11 +72,7 @@ alloc(size_t size, Area *ap)
l = calloc(1, sizeof(struct link) + size);
if (l == NULL)
internal_errorf(1, "unable to allocate memory");
- l->next = ap->freelist;
- l->prev = NULL;
- if (ap->freelist)
- ap->freelist->prev = l;
- ap->freelist = l;
+ RB_INSERT(addrtree, ap->tree, l);
return L2P(l);
}
@@ -82,7 +100,7 @@ areallocarray(void *ptr, size_t nmemb, s
void *
aresize(void *ptr, size_t size, Area *ap)
{
- struct link *l, *l2, *lprev, *lnext;
+ struct link *l, *l2;
if (ptr == NULL)
return alloc(size, ap);
@@ -92,18 +110,11 @@ aresize(void *ptr, size_t size, Area *ap
internal_errorf(1, "unable to allocate memory");
l = P2L(ptr);
- lprev = l->prev;
- lnext = l->next;
-
+ RB_REMOVE(addrtree, ap->tree, l);
l2 = realloc(l, sizeof(struct link) + size);
if (l2 == NULL)
internal_errorf(1, "unable to allocate memory");
- if (lprev)
- lprev->next = l2;
- else
- ap->freelist = l2;
- if (lnext)
- lnext->prev = l2;
+ RB_INSERT(addrtree, ap->tree, l2);
return L2P(l2);
}
@@ -111,26 +122,12 @@ aresize(void *ptr, size_t size, Area *ap
void
afree(void *ptr, Area *ap)
{
- struct link *l, *l2;
+ struct link *l;
if (!ptr)
return;
l = P2L(ptr);
-
- for (l2 = ap->freelist; l2 != NULL; l2 = l2->next) {
- if (l == l2)
- break;
- }
- if (l2 == NULL)
- internal_errorf(1, "afree: %p not present in area %p", ptr, ap);
-
- if (l->prev)
- l->prev->next = l->next;
- else
- ap->freelist = l->next;
- if (l->next)
- l->next->prev = l->prev;
-
+ RB_REMOVE(addrtree, ap->tree, l);
free(l);
}
Index: sh.h
===================================================================
RCS file: /d/cvs/src/bin/ksh/sh.h,v
retrieving revision 1.61
diff -u -p -r1.61 sh.h
--- sh.h 4 Jul 2017 11:46:15 -0000 1.61
+++ sh.h 24 Jul 2017 17:42:03 -0000
@@ -48,7 +48,7 @@ extern char username[]; /* username for
* Area-based allocation built on malloc/free
*/
typedef struct Area {
- struct link *freelist; /* free list */
+ struct addrtree *tree; /* free list */
} Area;
extern Area aperm; /* permanent object space */
@@ -380,6 +380,7 @@ extern int x_cols; /* tty columns */
/* alloc.c */
Area * ainit(Area *);
void afreeall(Area *);
+void adestroy(Area *);
void * alloc(size_t, Area *);
void * areallocarray(void *, size_t, size_t, Area *);
void * aresize(void *, size_t, Area *);
Index: var.c
===================================================================
RCS file: /d/cvs/src/bin/ksh/var.c,v
retrieving revision 1.57
diff -u -p -r1.57 var.c
--- var.c 8 Sep 2016 15:50:50 -0000 1.57
+++ var.c 24 Jul 2017 17:39:58 -0000
@@ -79,7 +79,7 @@ popblock(void)
}
if (l->flags & BF_DOGETOPTS)
user_opt = l->getopts_state;
- afreeall(&l->area);
+ adestroy(&l->area);
afree(l, ATEMP);
}
--
jca | PGP : 0x1524E7EE / 5135 92C1 AD36 5293 2BDF DDCC 0DFA 74AE 1524 E7EE
