Wanted or not, here is the promised big diff which does the
following:
1. Encapsulate struct table iteration usage
(*All* direct accesses encapsulated with struct tstate.)
2. ktinit() shouldn't expect pow2 size requests..
(It's really better that way.)
3. Turn struct table over to node-based approach
(Tight and sultry - or do you prefer Route 66.)
4. Use a hashmap for struct Area managed allocs..
(Blow my little white ass right off the map!
And turn the mentioned endless loop into something that is
supersafe and of at least acceptable performance.)
1, 2 and 3 survived a week of work (including one kernel
compilation, and one "make build"-alike).
4 is from friday evening.
--steffen
diff --git a/alloc.c b/alloc.c
index 7e41c2c..7e986a0 100644
--- a/alloc.c
+++ b/alloc.c
@@ -30,28 +30,35 @@
#include "sh.h"
+#define ALLOCIDX(AP,P) ((size_t)(P) % NELEM((AP)->allocs))
+
struct link {
- struct link *prev;
struct link *next;
};
Area *
ainit(Area *ap)
{
- ap->freelist = NULL;
- return ap;
+ bzero(ap->allocs, sizeof(ap->allocs));
+ return (ap);
}
void
afreeall(Area *ap)
{
- struct link *l, *l2;
+ size_t i;
+
+ for (i = NELEM(ap->allocs); i-- != 0;) {
+ struct link *l = ap->allocs[i];
+ ap->allocs[i] = NULL;
- for (l = ap->freelist; l != NULL; l = l2) {
- l2 = l->next;
- free(l);
+ while (l != NULL) {
+ struct link *l2 = l;
+ l = l->next;
+ free(l2);
+ }
}
- ap->freelist = NULL;
+ return;
}
#define L2P(l) ( (void *)(((char *)(l)) + sizeof(struct link)) )
@@ -60,68 +67,72 @@ afreeall(Area *ap)
void *
alloc(size_t size, Area *ap)
{
- struct link *l;
+ struct link *l, **arr;
l = malloc(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;
- return L2P(l);
+ arr = ap->allocs + ALLOCIDX(ap, l);
+ l->next = *arr;
+ *arr = l;
+
+ return (L2P(l));
}
void *
aresize(void *ptr, size_t size, Area *ap)
{
- struct link *l, *l2, *lprev, *lnext;
+ struct link *l, **arr;
if (ptr == NULL)
return alloc(size, ap);
l = P2L(ptr);
- lprev = l->prev;
- lnext = l->next;
- l2 = realloc(l, sizeof(struct link) + size);
- if (l2 == NULL)
+ arr = ap->allocs + ALLOCIDX(ap, l);
+ if (*arr == l)
+ *arr = l->next;
+ else {
+ struct link *p = *arr;
+ while (p->next != l)
+ p = p->next;
+ p->next = l->next;
+ }
+
+ l = realloc(l, sizeof(struct link) + size);
+ if (l == NULL)
internal_errorf(1, "unable to allocate memory");
- if (lprev)
- lprev->next = l2;
- else
- ap->freelist = l2;
- if (lnext)
- lnext->prev = l2;
-
- return L2P(l2);
+
+ arr = ap->allocs + ALLOCIDX(ap, l);
+ l->next = *arr;
+ *arr = l;
+
+ return (L2P(l));
}
void
afree(void *ptr, Area *ap)
{
- struct link *l, *l2;
+ struct link *l, **arr;
if (!ptr)
return;
-
l = P2L(ptr);
- for (l2 = ap->freelist; l2 != NULL; l2 = l2->next) {
- if (l == l2)
- break;
+ arr = ap->allocs + ALLOCIDX(ap, l);
+ if (*arr == l)
+ *arr = l->next;
+ else {
+ struct link *p = *arr;
+ while (p != NULL && p->next != l)
+ p = p->next;
+ if (p == NULL)
+ internal_errorf(1, "afree: %p not present in area %p",
+ ptr, (void*)ap);
+ p->next = l->next;
}
- 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;
free(l);
+ return;
}
diff --git a/exec.c b/exec.c
index 1c144fa..fb1e5bb 100644
--- a/exec.c
+++ b/exec.c
@@ -920,11 +920,14 @@ flushcom(int all) /* just relative or all */
struct tbl *tp;
struct tstate ts;
- for (ktwalk(&ts, &taliases); (tp = ktnext(&ts)) != NULL; )
- if ((tp->flag&ISSET) && (all || tp->val.s[0] != '/')) {
+ ktwalk(&ts, &taliases);
+ ts.flag |= ISSET;
+ while ((tp = ktnext(&ts)) != NULL)
+ if (all || tp->val.s[0] != '/') {
if (tp->flag&ALLOC) {
tp->flag &= ~(ALLOC|ISSET);
afree(tp->val.s, APERM);
+ continue;
}
tp->flag &= ~ISSET;
}
diff --git a/main.c b/main.c
index 0718a63..6a44cbd 100644
--- a/main.c
+++ b/main.c
@@ -119,7 +119,7 @@ main(int argc, char *argv[])
initkeywords();
/* define built-in commands */
- ktinit(&builtins, APERM, 64); /* must be 2^n (currently 40 builtins) */
+ ktinit(&builtins, APERM, 40); /* Currently 40 builtins */
for (i = 0; shbuiltins[i].name != NULL; i++)
builtin(shbuiltins[i].name, shbuiltins[i].func);
for (i = 0; kshbuiltins[i].name != NULL; i++)
diff --git a/proto.h b/proto.h
index bbd1327..758e47a 100644
--- a/proto.h
+++ b/proto.h
@@ -213,6 +213,9 @@ void ktdelete(struct tbl *);
void ktwalk(struct tstate *, struct table *);
struct tbl * ktnext(struct tstate *);
struct tbl ** ktsort(struct table *);
+#ifdef KSH_TABLE_DEBUG
+void ktstats(struct table *);
+#endif
/* trace.c */
/* trap.c */
void inittraps(void);
diff --git a/sh.h b/sh.h
index e4e8807..af4bac3 100644
--- a/sh.h
+++ b/sh.h
@@ -83,7 +83,7 @@ EXTERN char username[]; /* username for \u
prompt expansion */
* Area-based allocation built on malloc/free
*/
typedef struct Area {
- struct link *freelist; /* free list */
+ struct link *allocs[5]; /* Hashmap of alloc nodes */
} Area;
EXTERN Area aperm; /* permanent object space */
diff --git a/syn.c b/syn.c
index 9b7451a..6b73aea 100644
--- a/syn.c
+++ b/syn.c
@@ -666,7 +666,7 @@ initkeywords(void)
struct tokeninfo const *tt;
struct tbl *p;
- ktinit(&keywords, APERM, 32); /* must be 2^n (currently 20 keywords) */
+ ktinit(&keywords, APERM, 20); /* Currently 20 keywords */
for (tt = tokentab; tt->name; tt++) {
if (tt->reserved) {
p = ktenter(&keywords, tt->name, hash(tt->name));
diff --git a/table.c b/table.c
index 74d1684..5c7ebef 100644
--- a/table.c
+++ b/table.c
@@ -1,16 +1,238 @@
/* $OpenBSD: table.c,v 1.15 2012/02/19 07:52:30 otto Exp $ */
/*
- * dynamic hashed associative table for commands and variables
+ * Dynamic hashed associative table for commands and variables
*/
#include "sh.h"
-#define INIT_TBLS 8 /* initial table size (power of 2) */
+/* Global statistics atexit(3), plus */
+/*#define KSH_TABLE_STATS*/
-static void texpand(struct table *, int);
-static int tnamecmp(const void *, const void *);
+/* Minimum array capacity */
+#define TABLE_MIN_SHIFT 3
+#define TABLE_MIN_CAP (1 << TABLE_MIN_SHIFT)
+/* Treshold shift: count-of-buckets >= (array-capacity << treshold-shift) */
+#define TABLE_TRESHOLD1 1 /* Used if capacity <=
TRESHOLD1_MAX */
+#define TABLE_TRESHOLD1_MAX 128
+#define TABLE_TRESHOLD2 3 /* Used for larger tables */
+
+/* Maximum count of struct tbl* managed in a single struct table, including;
+ * must fit in 31 bit; it is handled if the system ENOMEMs before, though it
+ * will result in "out of memory" not "too many vars" error, say */
+#define VAR_MAX_COUNT (INT_MAX / 2)
+
+/* Should in-bucket list resorting take place? */
+#define BUCKET_RESORT 1
+
+/* Should KSH_TABLE_STATS track only global statistics? */
+#define ONLY_GLOBAL_STATS 1
+
+/* Should KSH_TABLE_STATS ktstats() include a (lengthy) bucket overview? */
+#define BUCKET_OVERVIEW 0
+
+#ifdef KSH_TABLE_STATS
+# define GINJECT(X) X
+# if ! ONLY_GLOBAL_STATS
+# define OINJECT(X) X
+# endif
+# ifndef MAX
+# define MAX(X,Y) (((X) > (Y)) ? (X) : (Y))
+# endif
+#endif
+#ifndef GINJECT
+# define GINJECT(X)
+#endif
+#ifndef OINJECT
+# define OINJECT(X)
+#endif
+
+#ifdef KSH_TABLE_STATS
+struct ostats {
+ unsigned long accesses; /* Overall callee accesses */
+ unsigned long inserts;
+ unsigned long removals;
+ unsigned long lookups;
+ unsigned long undef_hits; /* Hits of !DEFINED */
+ unsigned long head_hits; /* Lookup hit directly */
+ unsigned long resizes; /* Of .array */
+ unsigned long resorts; /* BUCKET_RESORT: lookup didn't hit
+ * head, resorted slot */
+};
+
+struct gstats {
+ struct ostats ostats;
+ unsigned long ktinits;
+ unsigned long real_ktinits; /* Objects with actual content */
+ unsigned long ktsorts;
+};
+#endif
+
+/* Because many instances of struct table end up "unused", partition the load
+ * into a structure which is stored at the bottom of the arrays' memchunk */
+struct thmap {
+ int32_t grow_cut; /* Grow on overflow */
+ int32_t shrink_cut; /* xxx No shrinking yet */
+ int32_t capacity; /* 0 or real capacity of .array - 1 */
+ int32_t count; /* Of struct tbl* in .array */
+ OINJECT( struct ostats ostats; )
+ struct tbl *array[1]; /* Variable size indeed */
+};
+
+/* Dump global statistics on program exit */
+#ifdef KSH_TABLE_STATS
+static int dump_gstats_installed;
+static struct gstats gstats;
+#endif
+
+static int tnamecmp(const void *, const void *);
+/* If ncap!=0 it may not necessarily be a power of two, adjust it first */
+static struct table *resize_array(struct table *tp, int32_t ncap);
+static struct tbl *lookup(struct table *tp, int ndefok, const char *name,
+ unsigned int name_hash);
+/* At EOF for the sake of readability */
+#ifdef KSH_TABLE_STATS
+static void dump_gstats(void);
+void ktstats(struct table *);
+#endif
+
+static int
+tnamecmp(const void *p1, const void *p2)
+{
+ char *name1 = (*(struct tbl **)p1)->name;
+ char *name2 = (*(struct tbl **)p2)->name;
+ return (strcmp(name1, name2));
+}
+
+static struct table *
+resize_array(struct table *tp, int32_t ncap)
+{
+ struct thmap *othm, *thm;
+ size_t i;
+
+#ifdef KSH_TABLE_STATS
+ if (! dump_gstats_installed) {
+ dump_gstats_installed = 1;
+ atexit(&dump_gstats);
+ }
+ if (tp->thmap == NULL)
+ ++gstats.real_ktinits;
+#endif
+
+ othm = tp->thmap;
+ if (othm != NULL && othm->count >= VAR_MAX_COUNT)
+ internal_errorf(1, "too many vars");
+
+ /* Simply grow - or got a fixed target line? */
+ if (ncap != 0) {
+ for (i = TABLE_MIN_SHIFT; ncap > (1 << i); ++i)
+ ;
+ ncap = 1 << i;
+ } else {
+ ncap = (othm != NULL) ? othm->capacity + 1 : TABLE_MIN_CAP / 2;
+ ncap <<= 1;
+ }
+
+ i = offsetof(struct thmap, array[0]) + sizeofN(struct tbl*, ncap);
+ thm = (struct thmap*)alloc(i, tp->areap);
+ bzero(thm, i);
+
+ /*
+ * VAR_MAX_COUNT isn't excessed, the allocation succeeded, so no more
+ * internal_errorf() are to be excepted: we're safe to do housekeeping
+ */
+ tp->thmap = thm;
+
+ thm->grow_cut = ncap << ((ncap < TABLE_TRESHOLD1_MAX)
+ ? TABLE_TRESHOLD1 : TABLE_TRESHOLD2);
+ thm->shrink_cut = ncap >> 1;
+ thm->capacity = --ncap;
+
+#ifdef KSH_TABLE_STATS
+# if ! ONLY_GLOBAL_STATS
+ if (othm != NULL)
+ memcpy(&thm->ostats, &othm->ostats, sizeof(struct ostats));
+ ++thm->ostats.resizes;
+# endif
+ ++gstats.ostats.resizes;
+#endif
+
+ /* Copy over the tbl*s to the new array, filter along the way */
+ if (othm != NULL) {
+ struct tbl **oarr;
+ for (oarr = othm->array, i = othm->count; i > 0; ++oarr) {
+ struct tbl *ot;
+ for (ot = *oarr; ot != NULL; --i) {
+ struct tbl *t = ot;
+ ot = ot->table_next;
+
+ if (t->flag & DEFINED) {
+ struct tbl **pos = (thm->array +
+ (hash(t->name) & ncap));
+ t->table_next = *pos;
+ *pos = t;
+ ++thm->count;
+ continue;
+ }
+
+ if (! (t->flag & FINUSE))
+ afree((void*)t, tp->areap);
+ }
+ }
+
+ afree((void*)othm, tp->areap);
+ }
+
+ return (tp);
+}
+
+static struct tbl *
+lookup(struct table *tp, int ndefok, const char *name, unsigned int name_hash)
+{
+ struct tbl *t = NULL, *ot;
+ struct thmap *thm;
+ char nc1;
+
+ thm = tp->thmap;
+ if (thm == NULL || thm->count == 0)
+ goto jleave;
+
+ nc1 = *name++;
+ name_hash &= thm->capacity;
+
+ for (ot = NULL, t = thm->array[name_hash]; t != NULL;
+ ot = t, t = t->table_next) {
+ const char *n = t->name;
+ if (nc1 != *n || (nc1 && strcmp(++n, name) != 0))
+ continue;
+ if (! (t->flag & DEFINED)) {
+ OINJECT( ++thm->ostats.undef_hits; )
+ GINJECT( ++gstats.ostats.undef_hits; )
+ if (! ndefok)
+ continue;
+ }
+
+ if (ot != NULL) {
+#if BUCKET_RESORT
+ OINJECT( ++thm->ostats.resorts; )
+ GINJECT( ++gstats.ostats.resorts; )
+ ot->table_next = t->table_next;
+ t->table_next = thm->array[name_hash];
+ thm->array[name_hash] = t;
+#endif
+ }
+#ifdef KSH_TABLE_STATS
+ else {
+ OINJECT( ++thm->ostats.head_hits; )
+ ++gstats.ostats.head_hits;
+ }
+#endif
+ break;
+ }
+
+jleave: return (t);
+}
unsigned int
hash(const char *n)
@@ -19,213 +241,288 @@ hash(const char *n)
while (*n != '\0')
h = 33*h + (unsigned char)(*n++);
- return h;
+ return (h);
}
void
ktinit(struct table *tp, Area *ap, int tsize)
{
+ GINJECT( ++gstats.ktinits; )
tp->areap = ap;
- tp->tbls = NULL;
- tp->size = tp->nfree = 0;
- if (tsize)
- texpand(tp, tsize);
-}
-
-static void
-texpand(struct table *tp, int nsize)
-{
- int i;
- struct tbl *tblp, **p;
- struct tbl **ntblp, **otblp = tp->tbls;
- int osize = tp->size;
-
- ntblp = (struct tbl**) alloc(sizeofN(struct tbl *, nsize), tp->areap);
- for (i = 0; i < nsize; i++)
- ntblp[i] = NULL;
- tp->size = nsize;
- tp->nfree = 7*nsize/10; /* table can get 70% full */
- tp->tbls = ntblp;
- if (otblp == NULL)
- return;
- for (i = 0; i < osize; i++)
- if ((tblp = otblp[i]) != NULL) {
- if ((tblp->flag&DEFINED)) {
- for (p = &ntblp[hash(tblp->name) &
- (tp->size-1)]; *p != NULL; p--)
- if (p == ntblp) /* wrap */
- p += tp->size;
- *p = tblp;
- tp->nfree--;
- } else if (!(tblp->flag & FINUSE)) {
- afree((void*)tblp, tp->areap);
- }
- }
- afree((void*)otblp, tp->areap);
+ tp->thmap = NULL;
+ if (tsize > 0)
+ (void)resize_array(tp, tsize);
+ return;
}
-/* table */
-/* name to enter */
-/* hash(n) */
struct tbl *
-ktsearch(struct table *tp, const char *n, unsigned int h)
+ktsearch(struct table *tp, const char *name, unsigned int name_hash)
{
- struct tbl **pp, *p;
-
- if (tp->size == 0)
- return NULL;
-
- /* search for name in hashed table */
- for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
- if (*p->name == *n && strcmp(p->name, n) == 0 &&
- (p->flag&DEFINED))
- return p;
- if (pp == tp->tbls) /* wrap */
- pp += tp->size;
+#ifdef KSH_TABLE_STATS
+# if ! ONLY_GLOBAL_STATS
+ if (tp->thmap != NULL) {
+ ++tp->thmap->ostats.accesses;
+ ++tp->thmap->ostats.lookups;
}
+# endif
+ ++gstats.ostats.accesses;
+ ++gstats.ostats.lookups;
+#endif
- return NULL;
+ return (lookup(tp, 0, name, name_hash));
}
-/* table */
-/* name to enter */
-/* hash(n) */
struct tbl *
-ktenter(struct table *tp, const char *n, unsigned int h)
+ktenter(struct table *tp, const char *name, unsigned int name_hash)
{
- struct tbl **pp, *p;
- int len;
-
- if (tp->size == 0)
- texpand(tp, INIT_TBLS);
- Search:
- /* search for name in hashed table */
- for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp) != NULL; pp--) {
- if (*p->name == *n && strcmp(p->name, n) == 0)
- return p; /* found */
- if (pp == tp->tbls) /* wrap */
- pp += tp->size;
+ struct tbl *t;
+ struct thmap *thm;
+ size_t len;
+
+#ifdef KSH_TABLE_STATS
+# if ! ONLY_GLOBAL_STATS
+ if (tp->thmap != NULL) {
+ ++tp->thmap->ostats.accesses;
+ ++tp->thmap->ostats.inserts;
}
+# endif
+ ++gstats.ostats.accesses;
+ ++gstats.ostats.inserts;
+#endif
+
+ if ((t = lookup(tp, 1, name, name_hash)) != NULL)
+ goto jleave;
- if (tp->nfree <= 0) { /* too full */
- if (tp->size <= INT_MAX/2)
- texpand(tp, 2*tp->size);
- else
- internal_errorf(1, "too many vars");
- goto Search;
+ /* New tbl entry */
+ thm = tp->thmap;
+ if (thm == NULL || thm->count >= thm->grow_cut) {
+ tp = resize_array(tp, 0);
+ OINJECT( if (thm == NULL) ++tp->thmap->ostats.accesses; )
+ thm = tp->thmap;
}
- /* create new tbl entry */
- len = strlen(n) + 1;
- p = (struct tbl *) alloc(offsetof(struct tbl, name[0]) + len,
- tp->areap);
- p->flag = 0;
- p->type = 0;
- p->areap = tp->areap;
- p->u2.field = 0;
- p->u.array = (struct tbl *)0;
- memcpy(p->name, n, len);
-
- /* enter in tp->tbls */
- tp->nfree--;
- *pp = p;
- return p;
+ len = strlen(name) + 1;
+ t = (struct tbl*)alloc(offsetof(struct tbl, name[0]) + len, tp->areap);
+ memcpy(t->name, name, len);
+
+ t->flag = 0;
+ t->type = 0;
+ t->areap = tp->areap;
+ t->u2.field = 0;
+ t->u.array = (struct tbl*)NULL;
+
+ name_hash &= thm->capacity;
+ ++thm->count;
+ t->table_next = thm->array[name_hash];
+ thm->array[name_hash] = t;
+
+jleave: return (t);
}
void
-ktdelete(struct tbl *p)
+ktdelete(struct tbl *t)
{
- p->flag = 0;
+ GINJECT( ++gstats.ostats.removals; )
+ t->flag = 0;
+ return;
}
void
ktwalk(struct tstate *ts, struct table *tp)
{
- ts->left = tp->size;
- ts->next = tp->tbls;
+ struct thmap *thm;
+
+ ts->tbl = NULL;
+ ts->flag = DEFINED;
+ ts->count = 0;
+ if ((thm = tp->thmap) != NULL) {
+ ts->array = thm->array;
+ ts->count = thm->count;
+ OINJECT( ++thm->ostats.accesses; )
+ GINJECT( ++gstats.ostats.accesses; )
+ }
+ return;
}
struct tbl *
ktnext(struct tstate *ts)
{
- while (--ts->left >= 0) {
- struct tbl *p = *ts->next++;
- if (p != NULL && (p->flag&DEFINED))
- return p;
+ struct tbl **arr, *t;
+ int32_t c;
+ Tflag flag;
+
+ arr = ts->array;
+ t = ts->tbl;
+ c = ts->count;
+ flag = ts->flag;
+ if (--c < 0) {
+ t = NULL;
+ goto jleave;
}
- return NULL;
-}
-static int
-tnamecmp(const void *p1, const void *p2)
-{
- char *name1 = (*(struct tbl **)p1)->name;
- char *name2 = (*(struct tbl **)p2)->name;
- return strcmp(name1, name2);
+ if (t == NULL || (t = t->table_next) == NULL)
+jnext_slot: while ((t = *arr++) == NULL)
+ ;
+
+ while ((t->flag & flag) != flag) {
+ if (--c < 0) {
+ t = NULL;
+ break;
+ }
+ if ((t = t->table_next) == NULL)
+ goto jnext_slot;
+ }
+
+jleave: ts->array = arr;
+ ts->tbl = t;
+ ts->count = c;
+ return (t);
}
struct tbl **
ktsort(struct table *tp)
{
- int i;
- struct tbl **p, **sp, **dp;
-
- p = (struct tbl **)alloc(sizeofN(struct tbl *, tp->size+1), ATEMP);
- sp = tp->tbls; /* source */
- dp = p; /* dest */
- for (i = 0; i < tp->size; i++)
- if ((*dp = *sp++) != NULL && (((*dp)->flag&DEFINED) ||
- ((*dp)->flag&ARRAY)))
- dp++;
- i = dp - p;
- qsortp((void**)p, (size_t)i, tnamecmp);
- p[i] = NULL;
- return p;
+ struct thmap *thm;
+ struct tbl **base_arr, **arr, *t;
+ size_t slots;
+ struct tstate ts;
+
+ GINJECT( ++gstats.ktsorts; )
+
+ thm = tp->thmap;
+ if (thm != NULL) {
+ OINJECT( ++thm->ostats.accesses; )
+ GINJECT( ++gstats.ostats.accesses; )
+ slots = thm->count;
+ } else
+ slots = 0;
+
+ base_arr = (struct tbl**)alloc(sizeofN(struct tbl*,slots + 1), ATEMP);
+
+ ktwalk(&ts, tp);
+ ts.flag = 0;
+ for (arr = base_arr; (t = ktnext(&ts)) != NULL;)
+ if ((t->flag & (DEFINED | ARRAY)) != 0)
+ *arr++ = t;
+
+ slots = (size_t)(arr - base_arr);
+ base_arr[slots] = NULL;
+
+ qsortp((void**)base_arr, slots, &tnamecmp);
+
+ return (base_arr);
}
-#ifdef PERF_DEBUG /* performance debugging */
+#ifdef KSH_TABLE_STATS
+static void
+dump_gstats(void)
+{
+ shellf(
+ "table.c:dump_gstats():\n"
+ "\t* Overview\n"
+ "\t\t- szof(struct table): %10u\n"
+ "\t\t- szof(struct thmap): %10u\n"
+ "\t\t- szof(struct tbl) : %10u\n"
+ "\t* Stats\n"
+ "\t\t- ktinit()s : %10lu\n"
+ "\t\t- .. ever used : %10lu\n"
+ "\t\t- Accesses : %10lu\n"
+ "\t\t- Inserts/Removals : %10lu / %10lu\n"
+ "\t\t- Array resizes : %10lu\n"
+ "\t\t- Lookups : %10lu\n"
+ "\t\t- Direct hits : %10lu\n"
+ "\t\t- Bucket resorts : %10lu\n"
+ "\t\t- Hits of ! DEFINED : %10lu\n"
+ "\t\t- ktsort()s : %10lu\n",
+ (uint32_t)sizeof(struct table), (uint32_t)sizeof(struct thmap),
+ (uint32_t)sizeof(struct tbl),
+ gstats.ktinits, gstats.real_ktinits, gstats.ostats.accesses,
+ gstats.ostats.inserts, gstats.ostats.removals,
+ gstats.ostats.resizes, gstats.ostats.lookups,
+ gstats.ostats.head_hits, gstats.ostats.resorts,
+ gstats.ostats.undef_hits, gstats.ktsorts);
-void tprintinfo(struct table *tp);
+ return;
+}
void
-tprintinfo(struct table *tp)
+ktstats(struct table *tp)
{
- struct tbl *te;
- char *n;
- unsigned int h;
- int ncmp;
- int totncmp = 0, maxncmp = 0;
- int nentries = 0;
- struct tstate ts;
+# if ONLY_GLOBAL_STATS
+ (void)tp;
+ return;
+# else
+ uint32_t empties = 0, undefs = 0, multis = 0, maxper = 0, real_av = 0,
+ cap, i, j;
+ struct thmap *thm;
- shellf("table size %d, nfree %d\n", tp->size, tp->nfree);
- shellf(" Ncmp name\n");
- ktwalk(&ts, tp);
- while ((te = ktnext(&ts))) {
- struct tbl **pp, *p;
-
- h = hash(n = te->name);
- ncmp = 0;
-
- /* taken from ktsearch() and added counter */
- for (pp = &tp->tbls[h & (tp->size-1)]; (p = *pp); pp--) {
- ncmp++;
- if (*p->name == *n && strcmp(p->name, n) == 0 &&
- (p->flag&DEFINED))
- break; /* return p; */
- if (pp == tp->tbls) /* wrap */
- pp += tp->size;
+ thm = tp->thmap;
+ shellf("ktstats(%p): thmap:%p\n", (void*)tp, (void*)thm);
+ if (thm == NULL)
+ goto jleave;
+
+ cap = thm->capacity + 1;
+
+ for (i = 0; i < cap; ++i) {
+ struct tbl *t;
+ for (j = 0, t = thm->array[i]; t != NULL; t = t->table_next) {
+ ++j;
+ if (! (t->flag & DEFINED))
+ ++undefs;
+ }
+ if (j == 0)
+ ++empties;
+ else {
+ if (j > 1)
+ ++multis;
+ maxper = MAX(maxper, j);
}
- shellf(" %4d %s\n", ncmp, n);
- totncmp += ncmp;
- nentries++;
- if (ncmp > maxncmp)
- maxncmp = ncmp;
}
- if (nentries)
- shellf(" %d entries, worst ncmp %d, avg ncmp %d.%02d\n",
- nentries, maxncmp,
- totncmp / nentries,
- (totncmp % nentries) * 100 / nentries);
+
+ real_av = cap - empties;
+ if (real_av != 0)
+ real_av = thm->count / real_av;
+
+ shellf(
+ "\t* Overview\n"
+ "\t\t- Array capacity : %10u\n"
+ "\t\t- Count (! DEFINED): %10d (%10d)\n"
+ "\t\t- Next grow/shrink : %10d / %10d\n"
+ "\t* Stats\n"
+ "\t\t- Accesses : %10lu\n"
+ "\t\t- Inserts/Removals : %10lu / %10lu\n"
+ "\t\t- Array resizes : %10lu\n"
+ "\t\t- Lookups : %10lu\n"
+ "\t\t- Direct hits : %10lu\n"
+ "\t\t- Bucket resorts : %10lu\n"
+ "\t\t- Hits of ! DEFINED: %10lu\n"
+ "\t* Array index statistics\n"
+ "\t\t- Empty : %10u\n"
+ "\t\t- Multiple entries : %10u\n"
+ "\t\t- Entries/idx, max.: %10u\n"
+ "\t\t- .. ideal average : %10u\n"
+ "\t\t- .. real average : %10u\n",
+ cap, thm->count, undefs, thm->grow_cut, thm->shrink_cut,
+ thm->ostats.accesses, thm->ostats.inserts, thm->ostats.removals,
+ thm->ostats.resizes, thm->ostats.lookups, thm->ostats.head_hits,
+ thm->ostats.resorts, thm->ostats.undef_hits,
+ empties, multis, maxper, (uint32_t)(cap ? thm->count / cap : 0),
+ real_av);
+
+# if BUCKET_OVERVIEW
+ shellf("\t* Index overview (index / buckets)\n\t");
+ for (i = 0; i < cap;) {
+ struct tbl *t;
+ for (j = 0, t = thm->array[i]; t != NULL; t = t->table_next)
+ ++j;
+ shellf("%5d/%2d ", i, j);
+ if (++i % 7 == 0)
+ shellf("\n\t");
+ }
+ shellf("\n");
+# endif
+
+jleave: return;
+# endif /* ! ONLY_GLOBAL_STATS */
}
-#endif /* PERF_DEBUG */
+#endif /* KSH_TABLE_STATS */
diff --git a/table.h b/table.h
index 3fe35eb..fde6853 100644
--- a/table.h
+++ b/table.h
@@ -7,9 +7,8 @@
*/
struct table {
- Area *areap; /* area to allocate entries */
- int size, nfree; /* hash size (always 2^^n), free entries */
- struct tbl **tbls; /* hashed table items */
+ Area *areap; /* Area to allocate entries from */
+ struct thmap *thmap; /* If any entries, actual hashmap */
};
struct tbl { /* table item */
@@ -17,6 +16,7 @@ struct tbl { /* table item */
int type; /* command type (see below), base (if INTEGER),
* or offset from val.s of value (if EXPORT) */
Area *areap; /* area to allocate from */
+ struct tbl *table_next; /* struct table: bucket list */
union {
char *s; /* string */
long i; /* integer */
@@ -32,7 +32,7 @@ struct tbl { /* table item */
struct tbl *array; /* array values */
char *fpath; /* temporary path to undef function */
} u;
- char name[4]; /* name -- variable length */
+ char name[sizeof(void*)]; /* name -- variable length */
};
/* common flag bits */
@@ -132,11 +132,13 @@ struct block {
* Used by ktwalk() and ktnext() routines.
*/
struct tstate {
- int left;
- struct tbl **next;
+ struct tbl *tbl;
+ struct tbl **array;
+ int32_t count;
+ Tflag flag; /* ktnext(): flags to compare against,
+ * default: DEFINED; 0: each */
};
-
EXTERN struct table taliases; /* tracked aliases */
EXTERN struct table builtins; /* built-in commands */
EXTERN struct table aliases; /* aliases */
diff --git a/var.c b/var.c
index 77d3969..bfdb149 100644
--- a/var.c
+++ b/var.c
@@ -60,17 +60,18 @@ void
popblock(void)
{
struct block *l = e->loc;
- struct tbl *vp, **vpp = l->vars.tbls, *vq;
- int i;
+ struct tbl *vp;
+ struct tstate ts;
e->loc = l->next; /* pop block */
- for (i = l->vars.size; --i >= 0; )
- if ((vp = *vpp++) != NULL && (vp->flag&SPECIAL)) {
- if ((vq = global(vp->name))->flag & ISSET)
- setspec(vq);
- else
- unsetspec(vq);
- }
+ ktwalk(&ts, &l->vars);
+ ts.flag = SPECIAL;
+ while ((vp = ktnext(&ts)) != NULL) {
+ if ((vp = global(vp->name))->flag & ISSET)
+ setspec(vp);
+ else
+ unsetspec(vp);
+ }
if (l->flags & BF_DOGETOPTS)
user_opt = l->getopts_state;
afreeall(&l->area);
@@ -111,7 +112,7 @@ initvar(void)
int i;
struct tbl *tp;
- ktinit(&specials, APERM, 32); /* must be 2^n (currently 17 specials) */
+ ktinit(&specials, APERM, 17); /* Currently 17 specials */
for (i = 0; names[i].name; i++) {
tp = ktenter(&specials, names[i].name, hash(names[i].name));
tp->flag = DEFINED|ISSET;
@@ -832,34 +833,35 @@ makenv(void)
{
struct block *l = e->loc;
XPtrV env;
- struct tbl *vp, **vpp;
- int i;
+ struct tbl *vp;
+ struct tstate ts;
XPinit(env, 64);
- for (l = e->loc; l != NULL; l = l->next)
- for (vpp = l->vars.tbls, i = l->vars.size; --i >= 0; )
- if ((vp = *vpp++) != NULL &&
- (vp->flag&(ISSET|EXPORT)) == (ISSET|EXPORT)) {
- struct block *l2;
- struct tbl *vp2;
- unsigned int h = hash(vp->name);
-
- /* unexport any redefined instances */
- for (l2 = l->next; l2 != NULL; l2 = l2->next) {
- vp2 = ktsearch(&l2->vars, vp->name, h);
- if (vp2 != NULL)
- vp2->flag &= ~EXPORT;
- }
- if ((vp->flag&INTEGER)) {
- /* integer to string */
- char *val;
- val = str_val(vp);
- vp->flag &= ~(INTEGER|RDONLY);
- /* setstr can't fail here */
- setstr(vp, val, KSH_RETURN_ERROR);
- }
- XPput(env, vp->val.s);
+ for (l = e->loc; l != NULL; l = l->next) {
+ ktwalk(&ts, &l->vars);
+ ts.flag = ISSET | EXPORT;
+ while ((vp = ktnext(&ts)) != NULL) {
+ struct block *l2;
+ struct tbl *vp2;
+ unsigned int h = hash(vp->name);
+
+ /* unexport any redefined instances */
+ for (l2 = l->next; l2 != NULL; l2 = l2->next) {
+ vp2 = ktsearch(&l2->vars, vp->name, h);
+ if (vp2 != NULL)
+ vp2->flag &= ~EXPORT;
}
+ if ((vp->flag&INTEGER)) {
+ /* integer to string */
+ char *val;
+ val = str_val(vp);
+ vp->flag &= ~(INTEGER|RDONLY);
+ /* setstr can't fail here */
+ setstr(vp, val, KSH_RETURN_ERROR);
+ }
+ XPput(env, vp->val.s);
+ }
+ }
XPput(env, NULL);
return (char **) XPclose(env);
}
