# New Ticket Created by Leopold Toetsch
# Please include the string: [perl #17621]
# in the subject line of all future correspondence about this issue.
# <URL: http://rt.perl.org/rt2/Ticket/Display.html?id=17621 >
This patch contains:
- removal of the initial parameter from intlist_new - no need for it in
the public interface (thanks Tom)
- junk_list is now a Buffer, which gets collected
- some macros to hide this
- more docs on indexed access/junk_list
- overall cleanup for junk_list
- rebuild_junk_list is forced after collection
Please apply & TIA
leo
-- attachment 1 ------------------------------------------------------
url: http://rt.perl.org/rt2/attach/38739/31468/1bd0a4/intlist-3.patch
--- parrot/intlist.c Thu Sep 26 18:30:29 2002
+++ parrot-leo/intlist.c Fri Sep 27 13:08:57 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* _intlist_new(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 _intlist_new(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*
+_intlist_new(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)
@@ -152,15 +189,18 @@
IntList_Chunk* lastChunk = list->prev;
size_t len = 0;
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;
+ /* IMHO no need to shrink chunk_list, its only one pointer per
+ * chunk */
+ if (len >= chunk_list_size(list)) {
+ Parrot_reallocate(interpreter, &list->chunk_list,
+ ((len + CL_SIZE) & ~(CL_SIZE-1)) * sizeof(IntList_Chunk *));
+ }
+ chunk_list_ptr(list, len) = (IntList_Chunk*) chunk;
len++;
if (chunk == lastChunk) break;
chunk = chunk->next;
}
- list->collect_runs = interpreter->dod_runs;
+ list->collect_runs = interpreter->collect_runs;
list->n_chunks = len;
return len;
}
@@ -172,7 +212,7 @@
if (chunk->next == list) {
/* Need to add a new chunk */
- IntList_Chunk* new_chunk = intlist_new(interpreter, 0);
+ IntList_Chunk* new_chunk = _intlist_new(interpreter, 0);
new_chunk->next = list;
new_chunk->prev = chunk;
chunk->next = new_chunk;
@@ -190,7 +230,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 +273,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 +297,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 +311,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 +334,7 @@
chunk->next = list;
list->prev = chunk->prev;
chunk = chunk->prev;
+ /* chunk_list hold one less valid entry now */
list->n_chunks--;
}
@@ -307,11 +357,11 @@
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];
+ return chunk_list_ptr(list, idx / INTLIST_CHUNK_SIZE);
#else
/* Possible optimization: start from the closer end of the chunk list */
--- 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 11:55:03 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++) {
