] each
] { } make ;
-: aggregate-stats-table ( stats -- table )
- [ { "Total collections:" "Total GC time:" } ] dip
- values
- [ [ collections>> ] map-sum ]
- [ [ times>> sum ] map-sum micros>string ]
- bi 2array zip ;
-
PRIVATE>
: gc-event. ( event -- )
} fancy-table. ;
: gc-stats. ( events -- )
- compute-gc-stats
- [ gc-stats-table simple-table. nl ]
- [ aggregate-stats-table simple-table. ]
- bi ;
+ compute-gc-stats gc-stats-table simple-table. ;
+
+: gc-summary. ( events -- )
+ {
+ { "Collections:" [ length commas ] }
+ { "Cards scanned:" [ [ cards-scanned>> ] map-sum commas ] }
+ { "Decks scanned:" [ [ decks-scanned>> ] map-sum commas ] }
+ { "Code blocks scanned:" [ [ code-blocks-scanned>> ] map-sum commas ] }
+ { "Total time:" [ [ total-time>> ] map-sum micros>string ] }
+ { "Card scan time:" [ [ card-scan-time>> ] map-sum micros>string ] }
+ { "Code block scan time:" [ [ code-scan-time>> ] map-sum micros>string ] }
+ { "Data heap sweep time:" [ [ data-sweep-time>> ] map-sum micros>string ] }
+ { "Code heap sweep time:" [ [ code-sweep-time>> ] map-sum micros>string ] }
+ { "Compaction time:" [ [ compaction-time>> ] map-sum micros>string ] }
+ } fancy-table. ;
: heap-sizes. ( events -- )
heap-sizes simple-table. ;
{ code-scan-time cell }
{ data-sweep-time cell }
{ code-sweep-time cell }
-{ compaction-time cell } ;
+{ compaction-time cell }
+{ temp-time cell } ;
--- /dev/null
+namespace factor
+{
+
+/* These algorithms were snarfed from various places. I did not come up with them myself */
+
+inline cell popcount(u64 x)
+{
+ u64 k1 = 0x5555555555555555ll;
+ u64 k2 = 0x3333333333333333ll;
+ u64 k4 = 0x0f0f0f0f0f0f0f0fll;
+ u64 kf = 0x0101010101010101ll;
+ x = x - ((x >> 1) & k1); // put count of each 2 bits into those 2 bits
+ x = (x & k2) + ((x >> 2) & k2); // put count of each 4 bits into those 4 bits
+ x = (x + (x >> 4)) & k4 ; // put count of each 8 bits into those 8 bits
+ x = (x * kf) >> 56; // returns 8 most significant bits of x + (x<<8) + (x<<16) + (x<<24) + ...
+
+ return (cell)x;
+}
+
+inline cell log2(u64 x)
+{
+#ifdef FACTOR_AMD64
+ cell n;
+ asm ("bsr %1, %0;":"=r"(n):"r"((cell)x));
+#else
+ cell n = 0;
+ if (x >= (u64)1 << 32) { x >>= 32; n += 32; }
+ if (x >= (u64)1 << 16) { x >>= 16; n += 16; }
+ if (x >= (u64)1 << 8) { x >>= 8; n += 8; }
+ if (x >= (u64)1 << 4) { x >>= 4; n += 4; }
+ if (x >= (u64)1 << 2) { x >>= 2; n += 2; }
+ if (x >= (u64)1 << 1) { n += 1; }
+#endif
+ return n;
+}
+
+inline cell log2(u16 x)
+{
+#if defined(FACTOR_X86) || defined(FACTOR_AMD64)
+ cell n;
+ asm ("bsr %1, %0;":"=r"(n):"r"((cell)x));
+#else
+ cell n = 0;
+ if (x >= 1 << 8) { x >>= 8; n += 8; }
+ if (x >= 1 << 4) { x >>= 4; n += 4; }
+ if (x >= 1 << 2) { x >>= 2; n += 2; }
+ if (x >= 1 << 1) { n += 1; }
+#endif
+ return n;
+}
+
+inline cell rightmost_clear_bit(u64 x)
+{
+ return log2(~x & (x + 1));
+}
+
+inline cell rightmost_set_bit(u64 x)
+{
+ return log2(x & -x);
+}
+
+inline cell rightmost_set_bit(u16 x)
+{
+ return log2((u16)(x & -x));
+}
+
+}
}
};
-struct object_start_map_updater {
- object_start_map *starts;
-
- explicit object_start_map_updater(object_start_map *starts_) : starts(starts_) {}
-
- void operator()(object *obj, cell size)
- {
- starts->record_object_start_offset(obj);
- }
-};
-
void factor_vm::collect_mark_impl(bool trace_contexts_p)
{
full_collector collector(this);
void gc_event::started_card_scan()
{
- card_scan_time = current_micros();
+ temp_time = current_micros();
}
void gc_event::ended_card_scan(cell cards_scanned_, cell decks_scanned_)
{
cards_scanned += cards_scanned_;
decks_scanned += decks_scanned_;
- card_scan_time = (current_micros() - card_scan_time);
+ card_scan_time = (current_micros() - temp_time);
}
void gc_event::started_code_scan()
{
- code_scan_time = current_micros();
+ temp_time = current_micros();
}
void gc_event::ended_code_scan(cell code_blocks_scanned_)
{
code_blocks_scanned += code_blocks_scanned_;
- code_scan_time = (current_micros() - code_scan_time);
+ code_scan_time = (current_micros() - temp_time);
}
void gc_event::started_data_sweep()
{
- data_sweep_time = current_micros();
+ temp_time = current_micros();
}
void gc_event::ended_data_sweep()
{
- data_sweep_time = (current_micros() - data_sweep_time);
+ data_sweep_time = (current_micros() - temp_time);
}
void gc_event::started_code_sweep()
{
- code_sweep_time = current_micros();
+ temp_time = current_micros();
}
void gc_event::ended_code_sweep()
{
- code_sweep_time = (current_micros() - code_sweep_time);
+ code_sweep_time = (current_micros() - temp_time);
}
void gc_event::started_compaction()
{
- compaction_time = current_micros();
+ temp_time = current_micros();
}
void gc_event::ended_compaction()
{
- compaction_time = (current_micros() - compaction_time);
+ compaction_time = (current_micros() - temp_time);
}
void gc_event::ended_gc(factor_vm *parent)
cell data_sweep_time;
cell code_sweep_time;
cell compaction_time;
+ cell temp_time;
explicit gc_event(gc_op op_, factor_vm *parent);
void started_card_scan();
set_bitmap_range(marked,address);
}
- /* From http://chessprogramming.wikispaces.com/Population+Count */
- cell popcount(u64 x)
- {
- u64 k1 = 0x5555555555555555ll;
- u64 k2 = 0x3333333333333333ll;
- u64 k4 = 0x0f0f0f0f0f0f0f0fll;
- u64 kf = 0x0101010101010101ll;
- x = x - ((x >> 1) & k1); // put count of each 2 bits into those 2 bits
- x = (x & k2) + ((x >> 2) & k2); // put count of each 4 bits into those 4 bits
- x = (x + (x >> 4)) & k4 ; // put count of each 8 bits into those 8 bits
- x = (x * kf) >> 56; // returns 8 most significant bits of x + (x<<8) + (x<<16) + (x<<24) + ...
-
- return (cell)x;
- }
-
/* The eventual destination of a block after compaction is just the number
of marked blocks before it. Live blocks must be marked on entry. */
void compute_forwarding()
return new_block;
}
- cell rightmost_clear_bit(u64 x)
- {
- cell n = 0;
- while(x & 1)
- {
- n++;
- x >>= 1;
- }
- return n;
- }
-
Block *next_unmarked_block_after(Block *original)
{
std::pair<cell,cell> position = bitmap_deref(original);
return (Block *)(this->start + this->size);
}
- cell rightmost_set_bit(u64 x)
- {
- cell n = 0;
- while(!(x & 1))
- {
- n++;
- x >>= 1;
- }
- return n;
- }
-
Block *next_marked_block_after(Block *original)
{
std::pair<cell,cell> position = bitmap_deref(original);
#include "bignum.hpp"
#include "code_block.hpp"
#include "bump_allocator.hpp"
+#include "bitwise_hacks.hpp"
#include "mark_bits.hpp"
#include "free_list.hpp"
#include "free_list_allocator.hpp"
memset(object_start_offsets,card_starts_inside_object,addr_to_card(size));
}
+void object_start_map::update_card_for_sweep(cell index, u16 mask)
+{
+ cell offset = object_start_offsets[index];
+ if(offset != card_starts_inside_object)
+ {
+ mask >>= (offset / block_granularity);
+
+ if(mask == 0)
+ {
+ /* The rest of the block after the old object start is free */
+ object_start_offsets[index] = card_starts_inside_object;
+ }
+ else
+ {
+ /* Move the object start forward if necessary */
+ object_start_offsets[index] = offset + (rightmost_set_bit(mask) * block_granularity);
+ }
+ }
+}
+
+void object_start_map::update_for_sweep(mark_bits<object> *state)
+{
+ for(cell index = 0; index < state->bits_size; index++)
+ {
+ u64 mask = state->marked[index];
+ update_card_for_sweep(index * 4, mask & 0xffff);
+ update_card_for_sweep(index * 4 + 1, (mask >> 16) & 0xffff);
+ update_card_for_sweep(index * 4 + 2, (mask >> 32) & 0xffff);
+ update_card_for_sweep(index * 4 + 3, (mask >> 48) & 0xffff);
+ }
+}
+
}
cell find_object_containing_card(cell card_index);
void record_object_start_offset(object *obj);
void clear_object_start_offsets();
+ void update_card_for_sweep(cell index, u16 mask);
+ void update_for_sweep(mark_bits<object> *state);
};
}
this->state.set_marked_p(obj);
this->mark_stack.push_back(obj);
}
+
+ void sweep()
+ {
+ free_list_allocator<object>::sweep();
+ starts.update_for_sweep(&this->state);
+ }
};
}
projects / factor.git / commitdiff