Changeset: d84ad1a28059 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=d84ad1a28059
Modified Files:
monetdb5/mal/mal_namespace.c
Branch: Jun2016
Log Message:
Namespace implementation updated.
Get rid of ehash: we can append to a linked list after having searched
it without extra cost without the need for an extra pointer.
Declare hash as an array instead of a pointer to an array that has to
be allocated.
Reduce the size of identifiers to IDLENGTH (64) from MAXIDENTLEN
(1024).
Allocate name records from a big chunk of memory to reduce malloc
overhead and potential memory fragmentation.
Hopefully all of this reduces the problems described in bug 4009.
diffs (230 lines):
diff --git a/monetdb5/mal/mal_namespace.c b/monetdb5/mal/mal_namespace.c
--- a/monetdb5/mal/mal_namespace.c
+++ b/monetdb5/mal/mal_namespace.c
@@ -19,38 +19,36 @@
#define HASHMASK 4095
/* taken from gdk_atoms */
-#define NME_HASH(x,y,K) \
- do { \
- const char *_key = (const char *) (x); \
- size_t _i; \
- for (_i = y = 0; K-- && _key[_i]; _i++) { \
- y += _key[_i]; \
- y += (y << 10); \
- y ^= (y >> 6); \
- } \
- y += (y << 3); \
- y ^= (y >> 11); \
- y += (y << 15); \
- y = y & HASHMASK; \
+#define NME_HASH(_key,y,K)
\
+ do {
\
+ size_t _i;
\
+ for (_i = y = 0; _i < K && _key[_i]; _i++) { \
+ y += _key[_i];
\
+ y += (y << 10);
\
+ y ^= (y >> 6);
\
+ }
\
+ y += (y << 3);
\
+ y ^= (y >> 11);
\
+ y += (y << 15);
\
+ y = y & HASHMASK;
\
} while (0)
typedef struct NAME{
- size_t length;
struct NAME *next;
- char nme[FLEXIBLE_ARRAY_MEMBER];
+ char nme[IDLENGTH + 1];
+ unsigned short length;
} *NamePtr;
-static NamePtr *hash= NULL, *ehash = NULL;
+static NamePtr hash[MAXIDENTIFIERS];
+
+static struct namespace {
+ struct namespace *next;
+ int count;
+ struct NAME data[4096];
+} *namespace;
void initNamespace(void) {
- if(hash == NULL) hash= (NamePtr *) GDKzalloc(sizeof(NamePtr) *
MAXIDENTIFIERS);
- if(ehash == NULL) ehash= (NamePtr *) GDKzalloc(sizeof(NamePtr) *
MAXIDENTIFIERS);
- if ( hash == NULL || ehash == NULL){
- /* absolute an error we can not recover from */
- showException(GDKout, MAL,"initNamespace",MAL_MALLOC_FAIL);
- mal_exit();
- }
}
void mal_namespace_reset(void) {
@@ -59,17 +57,13 @@ void mal_namespace_reset(void) {
/* assume we are at the end of the server session */
MT_lock_set(&mal_namespaceLock);
- for ( i =0; i < HASHMASK; i++){
- n = hash[i];
- hash[i] = ehash[i] = 0;
- for( ; n; n = m){
+ for ( i =0; i < MAXIDENTIFIERS; i++){
+ for(n = hash[i]; n; n = m){
m = n->next;
GDKfree(n);
}
+ hash[i] = 0;
}
- GDKfree(hash);
- GDKfree(ehash);
- hash = ehash = 0;
MT_lock_unset(&mal_namespaceLock);
}
@@ -80,29 +74,76 @@ void mal_namespace_reset(void) {
* is conflict free.
*/
+static str findName(const char *nme, size_t len, int allocate)
+{
+ NamePtr *n, m;
+ size_t key;
+
+ assert(len == 0 || nme != NULL);
+ if (len == 0 || nme == NULL)
+ return NULL;
+ if (len > IDLENGTH) {
+ len = IDLENGTH;
+ }
+ NME_HASH(nme, key, len);
+ MT_lock_set(&mal_namespaceLock);
+ for (n = &hash[key]; *n; n = &(*n)->next) {
+#ifdef KEEP_SORTED
+ /* keep each list sorted on length, then name */
+ if (len < (*n)->length)
+ continue;
+ if (len == (*n)->length) {
+ int c;
+ if ((c = strncmp(nme, (*n)->nme, len)) < 0)
+ continue;
+ if (c == 0) {
+ MT_lock_unset(&mal_namespaceLock);
+ return (*n)->nme;
+ }
+ break;
+ }
+ break;
+#else
+ /* append entries to list */
+ if (len == (*n)->length && strncmp(nme, (*n)->nme, len) == 0) {
+ MT_lock_unset(&mal_namespaceLock);
+ return (*n)->nme;
+ }
+#endif
+ }
+ /* item not found */
+ if (!allocate) {
+ MT_lock_unset(&mal_namespaceLock);
+ return NULL;
+ }
+ if (namespace == NULL || namespace->count == 4096) {
+ struct namespace *ns = GDKmalloc(sizeof(struct namespace));
+ if (ns == NULL) {
+ /* error we cannot recover from */
+ showException(GDKout, MAL, "findName", MAL_MALLOC_FAIL);
+ mal_exit();
+ }
+ ns->next = namespace;
+ ns->count = 0;
+ namespace = ns;
+ }
+ m = &namespace->data[namespace->count++];
+ strncpy(m->nme, nme, len);
+ m->nme[len] = 0;
+ m->length = (unsigned short) len;
+ m->next = *n;
+ *n = m;
+ MT_lock_unset(&mal_namespaceLock);
+ return (*n)->nme;
+}
+
str getName(const char *nme) {
- return getNameLen(nme, strlen(nme));
+ return findName(nme, strlen(nme), 0);
}
str getNameLen(const char *nme, size_t len)
{
- NamePtr n;
- size_t l = len, key;
-
- if(len == 0 || nme== NULL || *nme==0)
- return NULL;
- if(len>=MAXIDENTLEN)
- len = MAXIDENTLEN - 1;
- NME_HASH(nme, key, l);
- if ( ( n = hash[(int)key]) == 0)
- return NULL;
-
- do {
- if (len == n->length && strncmp(nme,n->nme,len)==0)
- return n->nme;
- n = n->next;
- } while (n);
- return NULL;
+ return findName(nme, len, 0);
}
/*
* Name deletion from the namespace is tricky, because there may
@@ -121,48 +162,10 @@ void delName(const char *nme, size_t len
}
str putName(const char *nme) {
- return putNameLen(nme, strlen(nme));
+ return findName(nme, strlen(nme), 1);
}
str putNameLen(const char *nme, size_t len)
{
- size_t l,k;
- int key;
- str fnd;
- NamePtr n;
-
- fnd = getNameLen(nme,len);
- if ( fnd )
- return fnd;
-
- if( nme == NULL || len == 0)
- return NULL;
-
- /* construct a new entry */
- if(len>=MAXIDENTLEN)
- len = MAXIDENTLEN - 1;
- n = GDKmalloc(offsetof(struct NAME, nme) + len + 1);
- if ( n == NULL) {
- /* absolute an error we can not recover from */
- showException(GDKout, MAL,"initNamespace",MAL_MALLOC_FAIL);
- mal_exit();
- }
- memcpy(n->nme, nme, len);
- n->nme[len]=0;
- n->length = len;
- n->next = NULL;
- l = len;
- NME_HASH(nme, k, l);
- key = (int) k;
-
- MT_lock_set(&mal_namespaceLock);
- /* add new elements to the end of the list */
- if ( ehash[key] == 0)
- hash[key] = ehash[key] = n;
- else {
- ehash[key]->next = n;
- ehash[key] = n;
- }
- MT_lock_unset(&mal_namespaceLock);
- return putNameLen(nme, len); /* just to be sure */
+ return findName(nme, len, 1);
}
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list
