Steffen Daode Nurpmeso wrote [2012-02-15 14:55+0100]:
> the patch below localizes access of struct table internals to
> table.c by using the ktwalk()/ktnext() interface from proto.h
> instead of doing handcrafted table iterations.
Yes it was wrong because it didn't take the flags into account
correctly.
This new version offers an additional field in struct tstate which
defaults to DEFINED but can be overwritten by users to the desired
flags.
> Surely a useful change regardless of possibly turning over to
> a node-based hashmap approach.
I still think so.
This patch also includes the following:
ktinit() shouldn't expect pow2 size requests..
It is an implementation detail that table.array is pow2 spaced,
so let callers simply request the sizes they want, and take care
of the adjustment internally.
The diff can be applied with or without your patch already
included. It passes this:
#!/bin/sh
KSH=obj/ksh
max=24000
booogie() {
local i=0
while [[ $i -le $max ]]; do
eval X${i}=yes
i=$(($i + 1))
done
i=0
while test $i -lt $max; do
test $((i & 1)) -eq 0 && eval unset X${i}
i=$((i + 1))
done
i=0
while test $i -lt $max; do
test $((i & 1)) -eq 0 && eval X${i}=yes
i=$((i + 1))
done
i=0
while test $i -lt $max; do
test $((i & 1)) -ne 0 && eval unset X${i}
i=$((i + 1))
done
i=0
while test $i -lt $max; do
test $((i & 1)) -eq 0 && eval unset X${i}
i=$((i + 1))
done
}
time booogie
time booogie
time booogie
So sorry for the first patch, it has been sent too fast!
About the node-based hashmap.
I tell nothing new.
The problem of associative tables is of course the distribution of
the keys, which typically ends up like so:
tstats(20a601228=var.c:newblock:vars)
* Overview
- Array capacity : 4096
- Buckets (K/V pairs): 21067
- Next grow : 32768 buckets
* Stats
- Accesses : 199655
- Lookups : 199653
- Hits with !DEFINED : 21000
- Direct hits : 106478
- Bucket resorts : 40545
- Array resizes : 10
* Array index statistics
- Empty indices : 99
- Indices with multiple buckets: 3759
- Buckets per index, maximum : 12
[Don't trust the following two]
- Buckets per index average : 5 (ideal distribution)
- Buckets per index, average : 5 (real distribution)
* Index overview (index / buckets)
0/ 5 1/ 4 2/ 4 3/ 4 4/ 4 5/ 6 6/ 7
7/ 7 8/ 7 9/ 7 10/ 7 11/ 6 12/ 5 13/ 4
14/ 3 15/ 1 16/ 0 17/ 0 18/ 0 19/ 1 20/ 2
[.]
105/ 8 106/ 8 107/ 8 108/ 7 109/ 6 110/ 5 111/ 3
112/ 2 113/ 1 114/ 0 115/ 1 116/ 1 117/ 2 118/ 4
119/ 5 120/ 6 121/ 7 122/ 8 123/ 9 124/ 9 125/ 8
[.]
910/ 1 911/ 0 912/ 0 913/ 2 914/ 3 915/ 4 916/ 5
917/ 7 918/ 9 919/10 920/10 921/10 922/10 923/ 8
924/ 7 925/ 6 926/ 5 927/ 3 928/ 2 929/ 2 930/ 3
with even worser distributions for arrays of 1024 and 2048 slots;
maybe a mathematician can tell you why this is so, i'm not the one.
The problems of using non-node based, i.e., linear hashtables is
thus of course that "heaps can unite"; e.g., the indexes 919 - 922
contain 40 struct tbl* entries which in the worst case had to be
all checked to find the desired one.
And the only way to ease that problem is to reduce the load
factor, i.e., to place fewer entries in the array before that is
resized, but which necessarily enlargens the array.
And that enlargement must be power-of-two spaced:
RESIZE: old-nsize=8192, new=16384 >= 131072; new-free:11468
RESIZE: old-nsize=16384, new=32768 >= 262144; new-free:22937
Node-based hashmaps, on the other hand, split up such heaps;
you access the array once and then do a list walk.
In the above example the worst-case is thus 10 node walks.
Bucket resorting can also be a good thing, as you can see above
(without resorting there are 8910 "direct hits"), but it surely
can result in the opposite, dependent on the actual use-case.
The best thing about node-based hashmaps is however that you can
reduce the load factor; in the above log extract the map has
a load factor of 800% (32768 / 4096). E.g., whereas the linear
one requires 261144 bytes of continuous memory, the node one
"only" requires 32768.
Well and after these well-known basics some more numbers.
If i run the above test in a VM with (the below patch and Chris
Toreks hash plus applied) i get these:
2. 0m6.63s real 0m6.51s user 0m0.07s system
3. 0m6.65s real 0m6.63s user 0m0.02s system
For the node-based with 2==400% to 256 slots, then 3==800% load:
2. 0m7.46s real 0m7.32s user 0m0.11s system
3. 0m7.52s real 0m7.40s user 0m0.12s system
Ditto, 2==400% all through:
2. 0m7.08s real 0m7.01s user 0m0.06s system
3. 0m7.00s real 0m6.79s user 0m0.11s system
But now this:
1. 0m10.45s real 0m10.19s user 0m0.19s system
1. 0m24.97s real 0m24.60s user 0m0.31s system
1. 0m23.85s real 0m23.36s user 0m0.26s system
Also, it consumes _noticeable_more_ memory!
Huch! Now what the heck.
And it currently even causes an endless loop somewhere in alloc.c
(freelist-reuse) if the initial shift is 1==200% load.
So i really think it's better that i inspect this some more before
i send an invalid patch to the OpenBSD tech@ list;
that would be the forth.
--steffen
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/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 4465033..d9d468f 100644
--- a/table.c
+++ b/table.c
@@ -28,8 +28,13 @@ ktinit(struct table *tp, Area *ap, int tsize)
tp->areap = ap;
tp->tbls = NULL;
tp->size = tp->nfree = 0;
- if (tsize)
+ if (tsize) {
+ int i;
+ for (i = 3; (1 << i) < tsize; ++i)
+ ;
+ tsize = 1 << i;
texpand(tp, tsize);
+ }
}
static void
@@ -143,14 +148,16 @@ ktwalk(struct tstate *ts, struct table *tp)
{
ts->left = tp->size;
ts->next = tp->tbls;
+ ts->flag = DEFINED;
}
struct tbl *
ktnext(struct tstate *ts)
{
+ Tflag flag = ts->flag;
while (--ts->left >= 0) {
struct tbl *p = *ts->next++;
- if (p != NULL && (p->flag&DEFINED))
+ if (p != NULL && (p->flag & flag) == flag)
return p;
}
return NULL;
diff --git a/table.h b/table.h
index af2d066..beb553a 100644
--- a/table.h
+++ b/table.h
@@ -132,11 +132,11 @@ struct block {
* Used by ktwalk() and ktnext() routines.
*/
struct tstate {
- int left;
+ int left;
struct tbl **next;
+ Tflag flag; /* Desired flags (default: DEFINED) */
};
-
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..9b84c51 100644
--- a/var.c
+++ b/var.c
@@ -60,17 +60,17 @@ 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)))
+ 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 +111,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 +832,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))) {
+ 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);
}
