Author: Nicolas Truessel <[email protected]>
Branch: quad-color-gc
Changeset: r86977:e2e9fdac5cf3
Date: 2016-09-09 18:01 +0200
http://bitbucket.org/pypy/pypy/changeset/e2e9fdac5cf3/
Log: Update qcgc codebase
diff --git a/rpython/translator/c/src/qcgc/allocator.c
b/rpython/translator/c/src/qcgc/allocator.c
--- a/rpython/translator/c/src/qcgc/allocator.c
+++ b/rpython/translator/c/src/qcgc/allocator.c
@@ -29,6 +29,8 @@
qcgc_arena_bag_create(QCGC_ARENA_BAG_INIT_SIZE);
qcgc_allocator_state.free_arenas = qcgc_arena_bag_create(4); // XXX
+ qcgc_allocator_state.use_bump_allocator = true;
+
// Bump Allocator
qcgc_allocator_state.bump_state.bump_ptr = NULL;
qcgc_allocator_state.bump_state.remaining_cells = 0;
@@ -254,17 +256,22 @@
#endif
cell_t *result = NULL;
for ( ; index < QCGC_SMALL_FREE_LISTS; index++) {
- linear_free_list_t *free_list =
- qcgc_allocator_state.fit_state.small_free_list[index];
size_t list_cell_size = small_index_to_cells(index);
- while (free_list->count > 0) {
- result = free_list->items[free_list->count - 1];
- free_list =
qcgc_linear_free_list_remove_index(free_list,
- free_list->count - 1);
+ while
(qcgc_allocator_state.fit_state.small_free_list[index]->count
+ > 0) {
+ result =
qcgc_allocator_state.fit_state.small_free_list[index]->
+
items[qcgc_allocator_state.fit_state.small_free_list[index]
+ ->count - 1];
+ qcgc_allocator_state.fit_state.small_free_list[index] =
+ qcgc_linear_free_list_remove_index(
+
qcgc_allocator_state.fit_state.small_free_list[index],
+
qcgc_allocator_state.fit_state.small_free_list[index]->
+ count - 1);
// Check whether block is still valid
if (valid_block(result, list_cell_size)) {
+ // The next call might invalidate free_list,
reload!
qcgc_fit_allocator_add(result + cells,
list_cell_size - cells);
break;
} else {
@@ -272,7 +279,6 @@
}
}
- qcgc_allocator_state.fit_state.small_free_list[index] =
free_list;
if (result != NULL) {
return result;
}
@@ -285,24 +291,32 @@
assert(1u<<(index + QCGC_LARGE_FREE_LIST_FIRST_EXP) <= cells);
assert(1u<<(index + QCGC_LARGE_FREE_LIST_FIRST_EXP + 1) > cells);
#endif
- exp_free_list_t *free_list =
- qcgc_allocator_state.fit_state.large_free_list[index];
- size_t best_fit_index = free_list->count;
+ size_t best_fit_index = qcgc_allocator_state.fit_state.
+ large_free_list[index]->count;
cell_t *result = NULL;
size_t best_fit_cells = SIZE_MAX;
size_t i = 0;
- while (i < free_list->count) {
- if (valid_block(free_list->items[i].ptr,
free_list->items[i].size)) {
- if (free_list->items[i].size >= cells &&
- free_list->items[i].size <
best_fit_cells) {
- result = free_list->items[i].ptr;
- best_fit_cells = free_list->items[i].size;
+ while (i <
qcgc_allocator_state.fit_state.large_free_list[index]->count) {
+ if
(valid_block(qcgc_allocator_state.fit_state.large_free_list[index] ->
+ items[i].ptr,
+
qcgc_allocator_state.fit_state.large_free_list[index]->
+ items[i].size)) {
+ if
(qcgc_allocator_state.fit_state.large_free_list[index]->
+ items[i].size >= cells &&
+
qcgc_allocator_state.fit_state.large_free_list[index]->
+ items[i].size < best_fit_cells) {
+ result =
qcgc_allocator_state.fit_state.large_free_list[index]->
+ items[i].ptr;
+ best_fit_cells = qcgc_allocator_state.fit_state.
+ large_free_list[index]->items[i].size;
best_fit_index = i;
}
i++;
} else {
- free_list = qcgc_exp_free_list_remove_index(free_list,
i);
+ qcgc_allocator_state.fit_state.large_free_list[index] =
+
qcgc_exp_free_list_remove_index(qcgc_allocator_state.fit_state.
+ large_free_list[index], i);
// NO i++ !
}
@@ -313,14 +327,16 @@
if (result != NULL) {
// Best fit was found
- assert(best_fit_index < free_list->count);
- free_list = qcgc_exp_free_list_remove_index(free_list,
best_fit_index);
+ assert(best_fit_index < qcgc_allocator_state.fit_state.
+ large_free_list[index]->count);
+ qcgc_allocator_state.fit_state.large_free_list[index] =
+
qcgc_exp_free_list_remove_index(qcgc_allocator_state.fit_state.
+ large_free_list[index], best_fit_index);
qcgc_fit_allocator_add(result + cells, best_fit_cells - cells);
} else {
// No best fit, go for first fit
result = fit_allocator_large_first_fit(index + 1, cells);
}
- qcgc_allocator_state.fit_state.large_free_list[index] = free_list;
return result;
}
@@ -330,13 +346,17 @@
#endif
cell_t *result = NULL;
for ( ; index < QCGC_LARGE_FREE_LISTS; index++) {
- exp_free_list_t *free_list =
- qcgc_allocator_state.fit_state.large_free_list[index];
- while(free_list->count > 0) {
+
while(qcgc_allocator_state.fit_state.large_free_list[index]->count
+ > 0) {
struct exp_free_list_item_s item =
- free_list->items[free_list->count - 1];
- free_list = qcgc_exp_free_list_remove_index(free_list,
- free_list->count - 1);
+
qcgc_allocator_state.fit_state.large_free_list[index]->items[
+
qcgc_allocator_state.fit_state.large_free_list[index]->count - 1
+ ];
+ qcgc_allocator_state.fit_state.large_free_list[index] =
+ qcgc_exp_free_list_remove_index(
+
qcgc_allocator_state.fit_state.large_free_list[index],
+
qcgc_allocator_state.fit_state.large_free_list[index]->
+ count - 1);
// Check whether block is still valid
if (valid_block(item.ptr, item.size)) {
@@ -345,7 +365,6 @@
break;
}
}
- qcgc_allocator_state.fit_state.large_free_list[index] =
free_list;
if (result != NULL) {
return result;
}
diff --git a/rpython/translator/c/src/qcgc/allocator.h
b/rpython/translator/c/src/qcgc/allocator.h
--- a/rpython/translator/c/src/qcgc/allocator.h
+++ b/rpython/translator/c/src/qcgc/allocator.h
@@ -48,6 +48,7 @@
linear_free_list_t *small_free_list[QCGC_SMALL_FREE_LISTS];
exp_free_list_t *large_free_list[QCGC_LARGE_FREE_LISTS];
} fit_state;
+ bool use_bump_allocator;
} qcgc_allocator_state;
/**
diff --git a/rpython/translator/c/src/qcgc/arena.c
b/rpython/translator/c/src/qcgc/arena.c
--- a/rpython/translator/c/src/qcgc/arena.c
+++ b/rpython/translator/c/src/qcgc/arena.c
@@ -11,6 +11,7 @@
#include "allocator.h"
#include "event_logger.h"
+#include "gc_state.h"
/**
* Internal functions
@@ -178,85 +179,124 @@
// No coalescing, collector will do this
}
+bool qcgc_arena_pseudo_sweep(arena_t *arena) {
+#if CHECKED
+ assert(arena != NULL);
+ assert(qcgc_arena_is_coalesced(arena));
+ assert(qcgc_arena_addr(qcgc_allocator_state.bump_state.bump_ptr) ==
arena);
+#endif
+ // XXX: Maybe ignore free cell / largest block counting here?
+ size_t last_free_cell = 0;
+ for (size_t cell = QCGC_ARENA_FIRST_CELL_INDEX;
+ cell < QCGC_ARENA_CELLS_COUNT;
+ cell++) {
+ switch (get_blocktype(arena, cell)) {
+ case BLOCK_FREE:
+ last_free_cell = cell;
+ case BLOCK_EXTENT: // Fall through
+ break;
+ case BLOCK_BLACK:
+ set_blocktype(arena, cell, BLOCK_WHITE);
+ case BLOCK_WHITE: // Fall through
+ if (last_free_cell != 0) {
+ qcgc_state.free_cells += cell -
last_free_cell;
+ qcgc_state.largest_free_block = MAX(
+
qcgc_state.largest_free_block,
+ cell - last_free_cell);
+ last_free_cell = 0;
+ }
+ break;
+ }
+ }
+ if (last_free_cell != 0) {
+ qcgc_state.free_cells += QCGC_ARENA_CELLS_COUNT -
last_free_cell;
+ qcgc_state.largest_free_block = MAX(
+ qcgc_state.largest_free_block,
+ QCGC_ARENA_CELLS_COUNT - last_free_cell);
+ last_free_cell = 0;
+ }
+#if CHECKED
+ assert(qcgc_arena_is_coalesced(arena));
+#endif
+ return false;
+}
+
bool qcgc_arena_sweep(arena_t *arena) {
#if CHECKED
assert(arena != NULL);
assert(qcgc_arena_is_coalesced(arena));
+ //assert(qcgc_arena_addr(qcgc_allocator_state.bump_state.bump_ptr) !=
arena);
#endif
-#if DEBUG_ZERO_ON_SWEEP
- bool zero = true;
-#endif
- bool free = true;
- bool coalesce = false;
- bool add_to_free_list = false;
- size_t last_free_cell = QCGC_ARENA_FIRST_CELL_INDEX;
-
if (qcgc_arena_addr(qcgc_allocator_state.bump_state.bump_ptr) == arena)
{
- for (size_t cell = QCGC_ARENA_FIRST_CELL_INDEX;
- cell < QCGC_ARENA_CELLS_COUNT;
- cell++) {
- if (get_blocktype(arena, cell) == BLOCK_BLACK) {
- set_blocktype(arena, cell, BLOCK_WHITE);
- }
- }
- return false;
+ return qcgc_arena_pseudo_sweep(arena);
}
+ size_t last_free_cell = 0;
+ bool register_free_block = false;
+ bool free = true;
for (size_t cell = QCGC_ARENA_FIRST_CELL_INDEX;
cell < QCGC_ARENA_CELLS_COUNT;
cell++) {
switch (get_blocktype(arena, cell)) {
case BLOCK_EXTENT:
-#if DEBUG_ZERO_ON_SWEEP
- if (zero) {
- memset(&arena->cells[cell], 0,
sizeof(cell_t));
- }
-#endif
break;
case BLOCK_FREE:
- if (coalesce) {
+ if (last_free_cell != 0) {
+ // Coalesce
set_blocktype(arena, cell,
BLOCK_EXTENT);
} else {
last_free_cell = cell;
}
- coalesce = true;
-#if DEBUG_ZERO_ON_SWEEP
- zero = true;
- memset(&arena->cells[cell], 0, sizeof(cell_t));
-#endif
+ // ==> last_free_cell != 0
break;
case BLOCK_WHITE:
- if (coalesce) {
+ if (last_free_cell != 0) {
+ // Coalesce
set_blocktype(arena, cell,
BLOCK_EXTENT);
} else {
set_blocktype(arena, cell, BLOCK_FREE);
last_free_cell = cell;
}
- coalesce = true;
- add_to_free_list = true;
-#if DEBUG_ZERO_ON_SWEEP
- zero = true;
- memset(&arena->cells[cell], 0, sizeof(cell_t));
-#endif
+ // ==> last_free_cell != 0
+ register_free_block = true;
break;
case BLOCK_BLACK:
set_blocktype(arena, cell, BLOCK_WHITE);
- if (add_to_free_list) {
- qcgc_fit_allocator_add(arena->cells +
last_free_cell,
+ if (last_free_cell != 0) {
+ if (register_free_block) {
+
qcgc_fit_allocator_add(arena->cells + last_free_cell,
+ cell -
last_free_cell);
+#if DEBUG_ZERO_ON_SWEEP
+ memset(arena->cells +
last_free_cell, 0,
+ sizeof(cell_t)
* (cell - last_free_cell));
+#endif
+ }
+ qcgc_state.free_cells += cell -
last_free_cell;
+ qcgc_state.largest_free_block = MAX(
+
qcgc_state.largest_free_block,
cell - last_free_cell);
+ last_free_cell = 0;
}
+ register_free_block = false;
free = false;
- coalesce = false;
- add_to_free_list = false;
-#if DEBUG_ZERO_ON_SWEEP
- zero = false;
-#endif
+ // ==> last_free_cell == 0
break;
}
}
- if (add_to_free_list && !free) {
- qcgc_fit_allocator_add(arena->cells + last_free_cell,
- QCGC_ARENA_CELLS_COUNT
- last_free_cell);
+ if (last_free_cell != 0 && !free) {
+ if (register_free_block) {
+ qcgc_fit_allocator_add(arena->cells + last_free_cell,
+ QCGC_ARENA_CELLS_COUNT -
last_free_cell);
+#if DEBUG_ZERO_ON_SWEEP
+ memset(arena->cells + last_free_cell, 0,
+ sizeof(cell_t) *
(QCGC_ARENA_CELLS_COUNT - last_free_cell));
+#endif
+ }
+ qcgc_state.free_cells += QCGC_ARENA_CELLS_COUNT -
last_free_cell;
+ qcgc_state.largest_free_block = MAX(
+ qcgc_state.largest_free_block,
+ QCGC_ARENA_CELLS_COUNT - last_free_cell);
+ last_free_cell = 0;
}
#if CHECKED
assert(qcgc_arena_is_coalesced(arena));
@@ -284,6 +324,7 @@
return true;
}
+
bool qcgc_arena_is_coalesced(arena_t *arena) {
#if CHECKED
assert(arena != NULL);
diff --git a/rpython/translator/c/src/qcgc/arena.h
b/rpython/translator/c/src/qcgc/arena.h
--- a/rpython/translator/c/src/qcgc/arena.h
+++ b/rpython/translator/c/src/qcgc/arena.h
@@ -143,6 +143,15 @@
*/
bool qcgc_arena_sweep(arena_t *arena);
+/**
+ * Sweep given arena, but only reset black to white, no white to free
+ *
+ * @param arena Arena
+ * @return Whether arena is empty after sweeping, always false
+ */
+bool qcgc_arena_pseudo_sweep(arena_t *arena);
+
+
/*******************************************************************************
* Debug functions
*
******************************************************************************/
diff --git a/rpython/translator/c/src/qcgc/config.h
b/rpython/translator/c/src/qcgc/config.h
--- a/rpython/translator/c/src/qcgc/config.h
+++ b/rpython/translator/c/src/qcgc/config.h
@@ -1,14 +1,14 @@
#pragma once
#define CHECKED 0 //
Enable runtime sanity checks
-#define DEBUG_ZERO_ON_SWEEP 1 // Zero memory on sweep
(debug only)
+#define DEBUG_ZERO_ON_SWEEP 0 // Zero memory on sweep
(debug only)
#define QCGC_INIT_ZERO 1 // Init new
objects with zero bytes
/**
* Event logger
*/
-#define EVENT_LOG 0 //
Enable event log
+#define EVENT_LOG 1 //
Enable event log
#define LOGFILE "./qcgc_events.log" // Default logfile
#define LOG_ALLOCATION 0 // Enable
allocation log (warning:
// significant performance impact)
diff --git a/rpython/translator/c/src/qcgc/event_logger.h
b/rpython/translator/c/src/qcgc/event_logger.h
--- a/rpython/translator/c/src/qcgc/event_logger.h
+++ b/rpython/translator/c/src/qcgc/event_logger.h
@@ -21,7 +21,6 @@
EVENT_NEW_ARENA,
EVENT_MARK_START,
- EVENT_INCMARK_START,
EVENT_MARK_DONE,
};
diff --git a/rpython/translator/c/src/qcgc/gc_state.h
b/rpython/translator/c/src/qcgc/gc_state.h
--- a/rpython/translator/c/src/qcgc/gc_state.h
+++ b/rpython/translator/c/src/qcgc/gc_state.h
@@ -33,4 +33,9 @@
gc_phase_t phase;
size_t bytes_since_collection;
size_t bytes_since_incmark;
+ size_t free_cells; // Overall amount of free cells
without huge
+ // blocks and
free areans. Valid right after sweep
+ size_t largest_free_block; // Size of the largest free block.
+ // (Free arenas
don't count as free blocks)
+ // Valid right
after sweep
} qcgc_state;
diff --git a/rpython/translator/c/src/qcgc/qcgc.c
b/rpython/translator/c/src/qcgc/qcgc.c
--- a/rpython/translator/c/src/qcgc/qcgc.c
+++ b/rpython/translator/c/src/qcgc/qcgc.c
@@ -38,6 +38,8 @@
qcgc_state.phase = GC_PAUSE;
qcgc_state.bytes_since_collection = 0;
qcgc_state.bytes_since_incmark = 0;
+ qcgc_state.free_cells = 0;
+ qcgc_state.largest_free_block = 0;
qcgc_allocator_initialize();
qcgc_hbtable_initialize();
qcgc_event_logger_initialize();
@@ -145,7 +147,7 @@
if (size <= 1<<QCGC_LARGE_ALLOC_THRESHOLD_EXP) {
// Use bump / fit allocator
- if (true) { // FIXME: Implement reasonable switch
+ if (qcgc_allocator_state.use_bump_allocator) {
result = qcgc_bump_allocate(size);
} else {
result = qcgc_fit_allocate(size);
@@ -203,8 +205,17 @@
if (qcgc_state.phase == GC_COLLECT) {
return; // Fast exit when there is nothing to mark
}
- // FIXME: Log some more information
- qcgc_event_logger_log(EVENT_MARK_START, 0, NULL);
+
+ {
+ struct log_info_s {
+ bool incremental;
+ size_t gray_stack_size;
+ };
+ struct log_info_s log_info = {incremental,
qcgc_state.gray_stack_size};
+ qcgc_event_logger_log(EVENT_MARK_START, sizeof(struct
log_info_s),
+ (uint8_t *) &log_info);
+ }
+
qcgc_state.bytes_since_incmark = 0;
if (qcgc_state.phase == GC_PAUSE) {
@@ -268,8 +279,15 @@
qcgc_state.phase = GC_COLLECT;
}
- // FIXME: Log some more information
- qcgc_event_logger_log(EVENT_MARK_DONE, 0, NULL);
+ {
+ struct log_info_s {
+ bool incremental;
+ size_t gray_stack_size;
+ };
+ struct log_info_s log_info = {incremental,
qcgc_state.gray_stack_size};
+ qcgc_event_logger_log(EVENT_MARK_DONE, sizeof(struct
log_info_s),
+ (uint8_t *) &log_info);
+ }
#if CHECKED
assert(incremental || (qcgc_state.phase = GC_COLLECT));
assert(qcgc_state.phase != GC_PAUSE);
@@ -339,13 +357,17 @@
#if CHECKED
assert(qcgc_state.phase == GC_COLLECT);
#endif
- unsigned long arena_count;
- arena_count = qcgc_allocator_state.arenas->count;
- qcgc_event_logger_log(EVENT_SWEEP_START, sizeof(arena_count),
- (uint8_t *) &arena_count);
+ {
+ unsigned long arena_count;
+ arena_count = qcgc_allocator_state.arenas->count;
+ qcgc_event_logger_log(EVENT_SWEEP_START, sizeof(arena_count),
+ (uint8_t *) &arena_count);
+ }
qcgc_hbtable_sweep();
size_t i = 0;
+ qcgc_state.free_cells = 0;
+ qcgc_state.largest_free_block = 0;
while (i < qcgc_allocator_state.arenas->count) {
arena_t *arena = qcgc_allocator_state.arenas->items[i];
// The arena that contains the bump pointer is autmatically
skipped
@@ -355,7 +377,6 @@
qcgc_allocator_state.arenas, i);
qcgc_allocator_state.free_arenas = qcgc_arena_bag_add(
qcgc_allocator_state.free_arenas,
arena);
-
// NO i++
} else {
// Not free
@@ -364,8 +385,26 @@
}
qcgc_state.phase = GC_PAUSE;
- qcgc_event_logger_log(EVENT_SWEEP_DONE, 0, NULL);
+ // Determine whether fragmentation is too high
+ // Fragmenation = 1 - (largest block / total free space)
+ // Use bump allocator when fragmentation < 50%
+ qcgc_allocator_state.use_bump_allocator = qcgc_state.free_cells <
+ 2 * qcgc_state.largest_free_block;
+
update_weakrefs();
+
+ {
+ struct log_info_s {
+ size_t free_cells;
+ size_t largest_free_block;
+ };
+ struct log_info_s log_info = {
+ qcgc_state.free_cells,
+ qcgc_state.largest_free_block
+ };
+ qcgc_event_logger_log(EVENT_SWEEP_DONE, sizeof(struct
log_info_s),
+ (uint8_t *) &log_info);
+ }
}
void qcgc_collect(void) {
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
