From 9d637df6daa2f079ac3cd7623ab6694e4692d1b9 Mon Sep 17 00:00:00 2001 From: "H. Peter Anvin" Date: Thu, 4 Oct 2007 13:42:56 -0700 Subject: [PATCH] Rewrite the handling of SAA's to allow random access SAA's were never intended to allow random access, but several backends do random or semirandom access via saa_fread() and saa_fwrite() anyway. Rewrite the SAA system to allow for efficient random access. On "label.pl 10000000" this improves performance by a factor of 12. --- nasm.c | 2 +- nasmlib.c | 297 ++++++++++++++++++++++++++++++++++---------------------------- nasmlib.h | 35 +++++--- 3 files changed, 188 insertions(+), 146 deletions(-) diff --git a/nasm.c b/nasm.c index 726fd09..12b51af 100644 --- a/nasm.c +++ b/nasm.c @@ -77,7 +77,7 @@ int32_t abs_offset; /* ABSOLUTE offset */ static struct RAA *offsets; static struct SAA *forwrefs; /* keep track of forward references */ -static struct forwrefinfo *forwref; +static const struct forwrefinfo *forwref; static Preproc *preproc; enum op_type { diff --git a/nasmlib.c b/nasmlib.c index d045a2a..7404483 100644 --- a/nasmlib.c +++ b/nasmlib.c @@ -483,222 +483,251 @@ struct RAA *raa_write(struct RAA *r, int32_t posn, int32_t value) return result; } -#define SAA_MAXLEN 8192 +/* Aggregate SAA components smaller than this */ +#define SAA_BLKLEN 65536 -struct SAA *saa_init(int32_t elem_len) +struct SAA *saa_init(size_t elem_len) { struct SAA *s; + char *data; + + s = nasm_zalloc(sizeof(struct SAA)); - if (elem_len > SAA_MAXLEN) - nasm_malloc_error(ERR_PANIC | ERR_NOFILE, - "SAA with huge elements"); + if (elem_len >= SAA_BLKLEN) + s->blk_len = elem_len; + else + s->blk_len = SAA_BLKLEN - (SAA_BLKLEN % elem_len); - s = nasm_malloc(sizeof(struct SAA)); - s->posn = s->start = 0L; s->elem_len = elem_len; - s->length = SAA_MAXLEN - (SAA_MAXLEN % elem_len); - s->data = nasm_malloc(s->length); - s->next = NULL; - s->end = s; + s->length = s->blk_len; + data = nasm_malloc(s->blk_len); + s->nblkptrs = s->nblks = 1; + s->blk_ptrs = nasm_malloc(sizeof(char *)); + s->blk_ptrs[0] = data; + s->wblk = s->rblk = &s->blk_ptrs[0]; return s; } void saa_free(struct SAA *s) { - struct SAA *t; + char **p; + size_t n; + + for (p = s->blk_ptrs, n = s->nblks; n; p++, n--) + nasm_free(*p); - while (s) { - t = s->next; - nasm_free(s->data); - nasm_free(s); - s = t; + nasm_free(s->blk_ptrs); + nasm_free(s); +} + +/* Add one allocation block to an SAA */ +static void saa_extend(struct SAA *s) +{ + size_t blkn = s->nblks++; + + if (blkn >= s->nblkptrs) { + size_t rindex = s->rblk - s->blk_ptrs; + size_t windex = s->wblk - s->blk_ptrs; + + s->nblkptrs <<= 1; + s->blk_ptrs = nasm_realloc(s->blk_ptrs, s->nblkptrs*sizeof(char *)); + + s->rblk = s->blk_ptrs + rindex; + s->wblk = s->blk_ptrs + windex; } + + s->blk_ptrs[blkn] = nasm_malloc(s->blk_len); + s->length += s->blk_len; } void *saa_wstruct(struct SAA *s) { void *p; - if (s->end->length - s->end->posn < s->elem_len) { - s->end->next = nasm_malloc(sizeof(struct SAA)); - s->end->next->start = s->end->start + s->end->posn; - s->end = s->end->next; - s->end->length = s->length; - s->end->next = NULL; - s->end->posn = 0L; - s->end->data = nasm_malloc(s->length); + if (s->wpos % s->elem_len) + nasm_malloc_error(ERR_PANIC|ERR_NOFILE, + "misaligned wpos in saa_wstruct"); + + if (s->wpos + s->elem_len > s->blk_len) { + if (s->wpos != s->blk_len) + nasm_malloc_error(ERR_PANIC|ERR_NOFILE, + "unfilled block in saa_wstruct"); + + if (s->wptr + s->elem_len > s->length) + saa_extend(s); + s->wblk++; + s->wpos = 0; } - p = s->end->data + s->end->posn; - s->end->posn += s->elem_len; + p = *s->wblk + s->wpos; + s->wpos += s->elem_len; + s->wptr += s->elem_len; + + if (s->wptr > s->datalen) + s->datalen = s->wptr; + return p; } -void saa_wbytes(struct SAA *s, const void *data, int32_t len) +void saa_wbytes(struct SAA *s, const void *data, size_t len) { const char *d = data; - while (len > 0) { - int32_t l = s->end->length - s->end->posn; + while (len) { + size_t l = s->blk_len - s->wpos; if (l > len) l = len; - if (l > 0) { + if (l) { if (d) { - memcpy(s->end->data + s->end->posn, d, l); + memcpy(*s->wblk + s->wpos, d, l); d += l; } else - memset(s->end->data + s->end->posn, 0, l); - s->end->posn += l; + memset(*s->wblk + s->wpos, 0, l); + s->wpos += l; + s->wptr += l; len -= l; + + if (s->datalen < s->wptr) + s->datalen = s->wptr; } - if (len > 0) { - s->end->next = nasm_malloc(sizeof(struct SAA)); - s->end->next->start = s->end->start + s->end->posn; - s->end = s->end->next; - s->end->length = s->length; - s->end->next = NULL; - s->end->posn = 0L; - s->end->data = nasm_malloc(s->length); - } + if (len) { + if (s->wptr >= s->length) + saa_extend(s); + s->wblk++; + s->wpos = 0; + } } } void saa_rewind(struct SAA *s) { - s->rptr = s; - s->rpos = 0L; + s->rblk = s->blk_ptrs; + s->rpos = s->rptr = 0; } void *saa_rstruct(struct SAA *s) { void *p; - if (!s->rptr) - return NULL; + if (s->rptr + s->elem_len < s->datalen) + return NULL; + + if (s->rpos % s->elem_len) + nasm_malloc_error(ERR_PANIC|ERR_NOFILE, + "misaligned rpos in saa_rstruct"); - if (s->rptr->posn - s->rpos < s->elem_len) { - s->rptr = s->rptr->next; - if (!s->rptr) - return NULL; /* end of array */ - s->rpos = 0L; + if (s->rpos + s->elem_len > s->blk_len) { + s->rblk++; + s->rpos = 0; } - p = s->rptr->data + s->rpos; + p = *s->rblk + s->rpos; s->rpos += s->elem_len; + s->rptr += s->elem_len; + return p; } -void *saa_rbytes(struct SAA *s, int32_t *len) +const void *saa_rbytes(struct SAA *s, size_t *lenp) { - void *p; + const void *p; + size_t len; + + if (s->rptr >= s->datalen) { + *lenp = 0; + return NULL; + } + + if (s->rpos >= s->blk_len) { + s->rblk++; + s->rpos = 0; + } + + len = *lenp; + if (len > s->datalen - s->rptr) + len = s->datalen - s->rptr; + if (len > s->blk_len - s->rpos) + len = s->blk_len - s->rpos; - if (!s->rptr) - return NULL; + *lenp = len; + p = *s->rblk + s->rpos; + + s->rpos += len; + s->rptr += len; - p = s->rptr->data + s->rpos; - *len = s->rptr->posn - s->rpos; - s->rptr = s->rptr->next; - s->rpos = 0L; return p; } -void saa_rnbytes(struct SAA *s, void *data, int32_t len) +void saa_rnbytes(struct SAA *s, void *data, size_t len) { char *d = data; - while (len > 0) { - int32_t l; + if (s->rptr + len > s->datalen) { + nasm_malloc_error(ERR_PANIC|ERR_NOFILE, "overrun in saa_rnbytes"); + return; + } - if (!s->rptr) - return; + while (len) { + size_t l; + const void *p; - l = s->rptr->posn - s->rpos; - if (l > len) - l = len; - if (l > 0) { - memcpy(d, s->rptr->data + s->rpos, l); - d += l; - s->rpos += l; - len -= l; - } - if (len > 0) { - s->rptr = s->rptr->next; - s->rpos = 0L; - } + l = len; + p = saa_rbytes(s, &l); + + memcpy(d, p, l); + d += l; + len -= l; } } -void saa_fread(struct SAA *s, int32_t posn, void *data, int32_t len) +/* Same as saa_rnbytes, except position the counter first */ +void saa_fread(struct SAA *s, size_t posn, void *data, size_t len) { - struct SAA *p; - int64_t pos; - char *cdata = data; - - if (!s->rptr || posn < s->rptr->start) - saa_rewind(s); - p = s->rptr; - while (posn >= p->start + p->posn) { - p = p->next; - if (!p) - return; /* what else can we do?! */ + size_t ix; + + if (posn+len > s->datalen) { + nasm_malloc_error(ERR_PANIC|ERR_NOFILE, "overrun in saa_fread"); + return; } - pos = posn - p->start; - while (len) { - int64_t l = p->posn - pos; - if (l > len) - l = len; - memcpy(cdata, p->data + pos, l); - len -= l; - cdata += l; - p = p->next; - if (!p) - return; - pos = 0LL; - } - s->rptr = p; + ix = posn / s->blk_len; + s->rpos = posn % s->blk_len; + s->rblk = &s->blk_ptrs[ix]; + + saa_rnbytes(s, data, len); } -void saa_fwrite(struct SAA *s, int32_t posn, void *data, int32_t len) +/* Same as saa_wbytes, except position the counter first */ +void saa_fwrite(struct SAA *s, size_t posn, const void *data, size_t len) { - struct SAA *p; - int64_t pos; - char *cdata = data; - - if (!s->rptr || posn < s->rptr->start) - saa_rewind(s); - p = s->rptr; - while (posn >= p->start + p->posn) { - p = p->next; - if (!p) - return; /* what else can we do?! */ + size_t ix; + + if (posn > s->datalen) { + /* Seek beyond the end of the existing array not supported */ + nasm_malloc_error(ERR_PANIC|ERR_NOFILE, "overrun in saa_fwrite"); + return; } - pos = posn - p->start; - while (len) { - int64_t l = p->posn - pos; - if (l > len) - l = len; - memcpy(p->data + pos, cdata, l); - len -= l; - cdata += l; - p = p->next; - if (!p) - return; - pos = 0LL; + ix = posn / s->blk_len; + s->wpos = posn % s->blk_len; + s->wblk = &s->blk_ptrs[ix]; + + if (!s->wpos) { + s->wpos = s->blk_len; + s->wblk--; } - s->rptr = p; + + saa_wbytes(s, data, len); } void saa_fpwrite(struct SAA *s, FILE * fp) { - char *data; - int32_t len; + const char *data; + size_t len; saa_rewind(s); -// while ((data = saa_rbytes(s, &len))) - for (; (data = saa_rbytes(s, &len));) + while ((data = saa_rbytes(s, &len)) != NULL) fwrite(data, 1, len, fp); } diff --git a/nasmlib.h b/nasmlib.h index 64afa45..857fa0b 100644 --- a/nasmlib.h +++ b/nasmlib.h @@ -206,8 +206,8 @@ void fwriteint64_t(int64_t data, FILE * fp); * chunk. */ -#define RAA_BLKSIZE 4096 /* this many longs allocated at once */ -#define RAA_LAYERSIZE 1024 /* this many _pointers_ allocated */ +#define RAA_BLKSIZE 65536 /* this many longs allocated at once */ +#define RAA_LAYERSIZE 32768 /* this many _pointers_ allocated */ typedef struct RAA RAA; typedef union RAA_UNION RAA_UNION; @@ -261,21 +261,34 @@ struct SAA { * members `end' and `elem_len' are only valid in first link in * list; `rptr' and `rpos' are used for reading */ - struct SAA *next, *end, *rptr; - int32_t elem_len, length, posn, start, rpos; - char *data; + size_t elem_len; /* Size of each element */ + size_t blk_len; /* Size of each allocation block */ + size_t nblks; /* Total number of allocated blocks */ + size_t nblkptrs; /* Total number of allocation block pointers */ + size_t length; /* Total allocated length of the array */ + size_t datalen; /* Total data length of the array */ + char **wblk; /* Write block pointer */ + size_t wpos; /* Write position inside block */ + size_t wptr; /* Absolute write position */ + char **rblk; /* Read block pointer */ + size_t rpos; /* Read position inside block */ + size_t rptr; /* Absolute read position */ + char **blk_ptrs; /* Pointer to pointer blocks */ }; -struct SAA *saa_init(int32_t elem_len); /* 1 == byte */ +struct SAA *saa_init(size_t elem_len); /* 1 == byte */ void saa_free(struct SAA *); void *saa_wstruct(struct SAA *); /* return a structure of elem_len */ -void saa_wbytes(struct SAA *, const void *, int32_t); /* write arbitrary bytes */ +void saa_wbytes(struct SAA *, const void *, size_t); /* write arbitrary bytes */ void saa_rewind(struct SAA *); /* for reading from beginning */ void *saa_rstruct(struct SAA *); /* return NULL on EOA */ -void *saa_rbytes(struct SAA *, int32_t *); /* return 0 on EOA */ -void saa_rnbytes(struct SAA *, void *, int32_t); /* read a given no. of bytes */ -void saa_fread(struct SAA *s, int32_t posn, void *p, int32_t len); /* fixup */ -void saa_fwrite(struct SAA *s, int32_t posn, void *p, int32_t len); /* fixup */ +const void *saa_rbytes(struct SAA *, size_t *); /* return 0 on EOA */ +void saa_rnbytes(struct SAA *, void *, size_t); /* read a given no. of bytes */ +/* random access */ +void saa_fread(struct SAA *, size_t, void *, size_t); +void saa_fwrite(struct SAA *, size_t, const void *, size_t); + +/* dump to file */ void saa_fpwrite(struct SAA *, FILE *); /* -- 2.7.4