Tom Hughes wrote:
> In message <[EMAIL PROTECTED]>
> Leopold Toetsch <[EMAIL PROTECTED]> wrote:
> I applied this to my checkout (with _intlist_new renamed to
> allocate_chunk because names starting with _ are reserved).
Ah, didn't know that - ok changed too.
> Unfortunately it doesn't test clean afterwards:
>
> dunsmere [~/src/parrot] % perl t/harness t/pmc/intlist.t
> t/pmc/intlist....NOK 3# Failed test (t/pmc/intlist.t at line 149)
> # got: ''
Ah, dumps core, aha GC, ahaaha junk_list moved. I ran the tests with my
Lea allocator in place, which doesn't suffer from this problem ;-)
Anyway here is an update, tested with CVS GC.
Additionally indexed access is simplified by a view lines.
Thanks for testing and sorry,
leo
--- parrot/intlist.c Thu Sep 26 18:30:29 2002
+++ parrot-leo/intlist.c Fri Sep 27 16:32:26 2002
@@ -70,6 +70,24 @@
* shift: read element, discard chunk and advance if necessary
* unshift: unshift a chunk if necessary, write element
*
+ * Direct aka indexed access of intlist data:
+ *
+ * The classic method would be to walk the intlist->next pointers
+ * (or optimized, the ->prev pointers if an index near the end is
+ * requested) and locate the chunk, that holds the wanted list
+ * item.
+ * To speed things up, especially for bigger lists, there are
+ * additional fields in the 'list' (the head chunk):
+ * chunk_list ... holds pointers to individual chunks
+ * collect_runs ... collect_runs counter, when chunk_list was
+ * rebuilt last.
+ * n_chunks ... used length in chunk_list
+ *
+ * If on any indexed access interpreter's collect_runs is
+ * different, the chunks might have been moved, so the chunk_list
+ * has to be rebuilt.
+ *
+ *
* History:
* Notes:
* References: */
@@ -78,9 +96,29 @@
#include "parrot/intlist.h"
static size_t rebuild_chunk_list(Interp *interpreter, IntList *list);
+static IntList* allocate_chunk(Interp *interpreter, int initial);
+static size_t rebuild_chunk_list(Interp *interpreter, IntList *list);
IntList*
-intlist_new(Interp *interpreter, int initial)
+intlist_new(Interp *interpreter) {
+ return allocate_chunk(interpreter, 1);
+}
+
+/* growth increment of chunk_list, must be a power of 2 */
+#define CL_SIZE 16
+
+/* Buffers store the used len in bytes in buflen
+ * so, the len in entries is: */
+
+#define chunk_list_size(list) \
+ (list->chunk_list.buflen / sizeof(IntList_Chunk *))
+
+/* hide the ugly cast somehow: */
+#define chunk_list_ptr(list, idx) \
+ ((IntList_Chunk**)list->chunk_list.bufstart)[idx]
+
+static IntList*
+allocate_chunk(Interp *interpreter, int initial)
{
IntList* list;
@@ -96,11 +134,8 @@
Parrot_allocate(interpreter, (Buffer*) list,
INTLIST_CHUNK_SIZE * sizeof(INTVAL));
if (initial) {
- /* XXX managed memory or custom destroy? */
- list->chunk_list = mem_sys_allocate(sizeof(IntList_Chunk *));
- list->n_chunks = 1;
- list->collect_runs = interpreter->dod_runs;
- list->chunk_list[0] = (IntList_Chunk*) list;
+ /* we have a cleared list, so no need to zero chunk_list */
+ rebuild_chunk_list(interpreter, list);
}
interpreter->DOD_block_level--;
interpreter->GC_block_level--;
@@ -115,10 +150,11 @@
buffer_lives((Buffer *) chunk);
chunk = chunk->next;
} while (chunk != (IntList_Chunk*) list);
-
+ buffer_lives(&list->chunk_list);
return last;
}
+#ifdef INTLIST_DEBUG
void
intlist_dump(FILE* fp, IntList* list, int verbose)
{
@@ -144,6 +180,7 @@
fprintf(fp, "\n");
}
+#endif
static size_t
rebuild_chunk_list(Interp *interpreter, IntList *list)
@@ -151,16 +188,25 @@
IntList_Chunk* chunk = (IntList_Chunk*) list;
IntList_Chunk* lastChunk = list->prev;
size_t len = 0;
+ /* allocate a new chunk_list buffer, old one my have moved
+ * firsr, count chunks */
while (1) {
- if (len >= list->n_chunks)
- list->chunk_list = mem_sys_realloc(list->chunk_list,
- (len + 1)* sizeof(IntList_Chunk *));
- list->chunk_list[len] = chunk;
len++;
if (chunk == lastChunk) break;
chunk = chunk->next;
}
- list->collect_runs = interpreter->dod_runs;
+ Parrot_allocate(interpreter, &list->chunk_list,
+ (len+1) * sizeof(IntList_Chunk *));
+ len = 0;
+ chunk = list;
+ /* then fill list */
+ while (1) {
+ chunk_list_ptr(list, len) = (IntList_Chunk*) chunk;
+ len++;
+ if (chunk == lastChunk) break;
+ chunk = chunk->next;
+ }
+ list->collect_runs = interpreter->collect_runs;
list->n_chunks = len;
return len;
}
@@ -172,7 +218,7 @@
if (chunk->next == list) {
/* Need to add a new chunk */
- IntList_Chunk* new_chunk = intlist_new(interpreter, 0);
+ IntList_Chunk* new_chunk = allocate_chunk(interpreter, 0);
new_chunk->next = list;
new_chunk->prev = chunk;
chunk->next = new_chunk;
@@ -190,7 +236,17 @@
add_chunk(interpreter, list);
list->prev->start = 0;
list->prev->end = 0;
+ /* optimization, add new chunk directly, if still space
+ * but only, if no collections was done in between
+ */
+ if (list->n_chunks >= chunk_list_size(list) ||
+ list->collect_runs != interpreter->collect_runs)
rebuild_chunk_list(interpreter, list);
+ else {
+ /* add the appended = last chunk = list->prev to chunk_list */
+ chunk_list_ptr(list, list->n_chunks) = list->prev;
+ list->n_chunks++;
+ }
}
static void
@@ -223,15 +279,15 @@
INTVAL length = chunk->length + 1;
INTVAL offset;
IntList_Chunk * o = chunk;
- size_t n = chunk->n_chunks;
/* Add on a new chunk if necessary */
if (chunk->start == 0) {
unshift_chunk(interpreter, *list);
chunk = chunk->prev;
*list = chunk;
+ /* move chunk_list to new list head */
(*list)->chunk_list = o->chunk_list;
- (*list)->n_chunks = n;
+ /* and rebuild it from scratch */
rebuild_chunk_list(interpreter, *list);
}
@@ -247,7 +303,6 @@
INTVAL length = chunk->length - 1;
INTVAL value;
IntList_Chunk * o = chunk;
- size_t n = chunk->n_chunks;
if (chunk->start >= chunk->end) {
internal_exception(OUT_OF_BOUNDS, "No entries on list!\n");
@@ -262,8 +317,8 @@
chunk->next->prev = chunk->prev;
chunk->prev->next = chunk;
*list = chunk->next;
+ /* like above */
(*list)->chunk_list = o->chunk_list;
- (*list)->n_chunks = n;
rebuild_chunk_list(interpreter, *list);
}
@@ -285,6 +340,7 @@
chunk->next = list;
list->prev = chunk->prev;
chunk = chunk->prev;
+ /* chunk_list hold one less valid entry now */
list->n_chunks--;
}
@@ -306,23 +362,9 @@
IntList_Chunk* chunk = list;
UNUSED(interpreter);
-#if 1
- if (list->collect_runs != interpreter->dod_runs)
+ if (list->collect_runs != interpreter->collect_runs)
rebuild_chunk_list(interpreter, list);
- idx += chunk->start;
-
- return list->chunk_list[idx / INTLIST_CHUNK_SIZE];
-#else
- /* Possible optimization: start from the closer end of the chunk list */
-
- /* Find the chunk containing the requested element */
- while (idx >= chunk->end - chunk->start) {
- idx -= chunk->end - chunk->start;
- chunk = chunk->next;
- }
-
- return chunk;
-#endif
+ return chunk_list_ptr(list, idx / INTLIST_CHUNK_SIZE);
}
INTVAL
@@ -339,13 +381,13 @@
}
if (idx < 0) idx += length;
+ idx += list->start;
chunk = find_chunk(interpreter, list, idx);
- if (idx >= list->end - list->start) idx -= list->end - list->start;
idx = idx % INTLIST_CHUNK_SIZE;
- return ((INTVAL*)chunk->buffer.bufstart)[idx + chunk->start];
+ return ((INTVAL*)chunk->buffer.bufstart)[idx];
}
static void
@@ -394,11 +436,11 @@
intlist_extend(interpreter, list, idx + 1);
}
+ idx += list->start;
chunk = find_chunk(interpreter, list, idx);
- if (idx >= list->end - list->start) idx -= list->end - list->start;
idx = idx % INTLIST_CHUNK_SIZE;
- ((INTVAL*)chunk->buffer.bufstart)[idx + chunk->start] = val;
+ ((INTVAL*)chunk->buffer.bufstart)[idx] = val;
}
/*
--- parrot/include/parrot/intlist.h Thu Sep 26 18:30:30 2002
+++ parrot-leo/include/parrot/intlist.h Fri Sep 27 12:10:47 2002
@@ -24,10 +24,12 @@
struct IntList_chunk_t {
Buffer buffer; /* This struct is a Buffer header subclass! */
- INTVAL length; /* Only valid for the "head" chunk (1) */
- size_t collect_runs; /* when chunklist was built (1) */
- IntList_Chunk ** chunk_list; /* list of chunks for fast access (1) */
- size_t n_chunks; /* number of chunks in chunk_list */
+ INTVAL length; /* number of items in list (1) */
+ size_t collect_runs; /* counter, when chunklist was built (1) */
+ Buffer chunk_list; /* holding list of chunks for fast access (1) */
+ size_t n_chunks; /* number of used chunks in chunk_list (1) */
+ /* all above items, marked (1) are only valid in the head junk
+ * s. intlist.c for a detailled description */
INTVAL start;
INTVAL end;
IntList_Chunk* next;
@@ -38,7 +40,7 @@
PMC* intlist_mark(Interp*, IntList*, PMC* last);
-IntList *intlist_new(Interp*, int initial);
+IntList *intlist_new(Interp*);
static INTVAL intlist_length(Interp* interpreter, IntList* list)
{
--- parrot/classes/intlist.pmc Thu Sep 26 18:30:30 2002
+++ parrot-leo/classes/intlist.pmc Fri Sep 27 11:55:15 2002
@@ -30,7 +30,7 @@
}
void init () {
- SELF->data = intlist_new(INTERP, 1);
+ SELF->data = intlist_new(INTERP);
SELF->cache.int_val = 0;
SELF->flags |= PMC_custom_mark_FLAG;
}
--- parrot/t/src/intlist.t Thu Sep 26 18:30:36 2002
+++ parrot-leo/t/src/intlist.t Fri Sep 27 15:42:25 2002
@@ -15,7 +15,7 @@
if (interpreter == NULL) return 1;
Parrot_init(interpreter, (void*) &interpreter);
- list = intlist_new(interpreter, 1);
+ list = intlist_new(interpreter);
if (list == NULL) return 1;
intlist_push(interpreter, list, 42);
@@ -44,7 +44,7 @@
if (interpreter == NULL) return "create interpreter";
Parrot_init(interpreter, (void*) &interpreter);
- list = intlist_new(interpreter, 1);
+ list = intlist_new(interpreter);
if (list == NULL) return "create list";
/* Push 3, then pop 2. Repeat N times. */
@@ -177,7 +177,7 @@
if (interpreter == NULL) return 1;
Parrot_init(interpreter, (void*) &interpreter);
- list = intlist_new(interpreter, 1);
+ list = intlist_new(interpreter);
if (list == NULL) return 1;
printf("Step 1: 0\n");
@@ -282,7 +282,7 @@
if (interpreter == NULL) return 1;
Parrot_init(interpreter, (void*) &interpreter);
- list = intlist_new(interpreter, 1);
+ list = intlist_new(interpreter);
if (list == NULL) return 1;
for (i = 0; i < INTLIST_CHUNK_SIZE * 2.5; i++) {
