[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
GC: cons sweeping
|
From: |
Dmitry Antipov |
|
Subject: |
GC: cons sweeping |
|
Date: |
Mon, 02 Jul 2007 19:01:53 +0400 |
|
User-agent: |
Thunderbird 1.5.0.7 (X11/20061008) |
For the most common usage patterns, it was observed that from 50% to near 80%
of allocated cons blocks are full (for the dumped Emacs). Other blocks may
contains a free cons cells, and, when Emacs lifetime grows, the fragmentation
for
such blocks usually increases (this is a weakness of all non-copying GCs we
can't avoid).
Anyway, the number of full blocks is quite large, and some of non-full blocks
may
contains large full subareas. This means that we may try to check the whole
word of
the cons block bitmap first - if all appropriate conses are marked, it will be
-1,
and, since there is nothing to link into free list from there, all mark bits
might be
just cleared at once by setting this word to 0. Otherwise, we should scan over
each bit of this word and link non-marked conses to a free list.
Here is an implementation of a such sweeping scheme. It's a bit more complicated
than described because a) first cons block may be used partially and b) number
of
bits in a cons block bitmap is not a multiple of a number of bits per word, so
last word of the bitmap might be scanned as usual. This patch also saves an old
sweeping code under #if and provides a simple timing of both sweeping methods
in order to compare the speed of them.
Finally, there are typical results of simple benchmarks I've performed.
Everything is started from 'src' subdirectory of the source tree. Cons sweeping
time (in us) for the original code is 2nd column, for the modified - 3rd.
Since the number of usecs is absolute and highly depends on your hardware,
only the difference (or ratio) between them makes sense.
1. Run 'emacs *.[ch]', then exit immediately:
GC0 612 514
GC1 692 578
GC2 814 674
GC3 741 522
GC4 778 534
GC5 776 505
GC6 779 490
GC7 856 543
GC8 912 590
GC9 941 611
GC10 971 597
GC11 1000 610
GC12 1031 620
GC13 1104 661
GC14 1099 664
GC15 1134 684
GC16 1149 679
GC17 1199 719
GC18 1215 717
GC19 1243 733
GC20 1277 780
GC21 1316 774
GC22 1422 802
GC23 1381 803
GC24 1400 823
GC25 1430 1009
GC26 1474 834
GC27 1497 840
GC28 1512 849
GC29 1536 866
GC30 1574 968
GC31 1595 954
GC32 1606 893
GC33 1671 921
GC34 1693 924
GC35 1727 937
GC36 1759 994
GC37 1856 987
GC38 1809 998
GC39 1831 987
2. Run 'emacs -batch -f batch-byte-compile ../lisp/textmodes/org.el':
GC0 602 504
GC1 561 383
GC2 613 438
GC3 650 451
GC4 676 412
GC5 696 411
GC6 712 457
GC7 799 509
GC8 825 526
GC9 850 515
GC10 914 556
GC11 893 500
GC12 1002 584
GC13 1052 619
GC14 1145 711
GC15 1340 909
GC16 1520 930
GC17 1333 894
GC18 1376 951
GC19 1402 992
GC20 1331 920
GC21 1381 1008
GC22 1382 970
GC23 1376 998
GC24 1441 1037
GC25 1384 991
GC26 1442 1065
GC27 1430 1060
GC28 1400 1017
GC29 1400 991
GC30 1521 1072
GC31 1427 1014
3. Run 'emacs ChangeLog', then '(replace-string "a" "__A__")' and exit
without saving the modified buffer:
GC0 607 510
GC1 697 593
GC2 809 670
GC3 757 537
GC4 736 599
GC5 863 679
GC6 937 661
GC7 1023 702
GC8 1144 753
GC9 1195 802
GC10 1308 829
GC11 1359 851
GC12 1509 900
GC13 1641 912
GC14 1648 969
GC15 1728 1004
GC16 1929 1047
GC17 2100 1146
GC18 2141 1175
GC19 2133 1249
GC20 2373 1317
GC21 2440 1369
GC22 2633 1464
GC23 2775 1521
GC24 2834 1615
GC25 3088 1703
GC26 3189 1823
GC27 3399 1915
GC28 3563 2143
GC29 3854 2163
GC30 4133 2262
GC31 4225 2373
GC32 4519 2580
GC33 4653 2605
GC34 4922 2768
GC35 5414 2910
Waiting for feedback,
Dmitry
Index: alloc.c
===================================================================
RCS file: /sources/emacs/emacs/src/alloc.c,v
retrieving revision 1.410
diff -u -r1.410 alloc.c
--- alloc.c 8 Jun 2007 19:59:46 -0000 1.410
+++ alloc.c 2 Jul 2007 14:54:46 -0000
@@ -5950,6 +5950,9 @@
static void
gc_sweep ()
{
+ EMACS_TIME beg, end, total;
+ char *sweep_type;
+
/* Remove or mark entries in weak hash tables.
This must be done before any object is unmarked. */
sweep_weak_hash_tables ();
@@ -5961,6 +5964,11 @@
#endif
/* Put all unmarked conses on free list */
+
+ EMACS_GET_TIME (beg);
+
+#if 0 /* Old straightforward sweep */
+
{
register struct cons_block *cblk;
struct cons_block **cprev = &cons_block;
@@ -5968,6 +5976,7 @@
register int num_free = 0, num_used = 0;
cons_free_list = 0;
+ sweep_type = "old";
for (cblk = cons_block; cblk; cblk = *cprev)
{
@@ -5991,6 +6000,88 @@
lim = CONS_BLOCK_SIZE;
/* If this block contains only free conses and we have already
seen more than two blocks worth of free conses then deallocate
+ this block. */
+ if (this_free == CONS_BLOCK_SIZE && num_free > CONS_BLOCK_SIZE)
+ {
+ *cprev = cblk->next;
+ /* Unhook from the free list. */
+ cons_free_list = cblk->conses[0].u.chain;
+ lisp_align_free (cblk);
+ n_cons_blocks--;
+ }
+ else
+ {
+ num_free += this_free;
+ cprev = &cblk->next;
+ }
+ }
+ total_conses = num_used;
+ total_free_conses = num_free;
+ }
+
+#else /* New, more compilcated, but hopefully faster, sweep */
+
+ {
+ register struct cons_block *cblk;
+ struct cons_block **cprev = &cons_block;
+ register int lim = cons_block_index;
+ register int num_free = 0, num_used = 0;
+
+ cons_free_list = 0;
+ sweep_type = "new";
+
+ for (cblk = cons_block; cblk; cblk = *cprev)
+ {
+ register int i = 0;
+ int this_free = 0;
+
+ while (1)
+ {
+ if (cblk->gcmarkbits[i] == -1)
+ {
+ /* Fast path - everything is marked. */
+ cblk->gcmarkbits[i++] = 0;
+ num_used += BITS_PER_INT;
+ }
+ else
+ {
+ /* Slow path - scan over each bit, from the beginning
+ of current word to 'min (word boundary, LIM)'. */
+ int start, stop;
+
+ start = i * BITS_PER_INT;
+ stop = lim - start;
+ if (stop > BITS_PER_INT)
+ stop = BITS_PER_INT;
+ stop += start;
+
+ while (start < stop)
+ {
+ if (!CONS_MARKED_P (&cblk->conses[start]))
+ {
+ this_free++;
+ cblk->conses[start].u.chain = cons_free_list;
+ cons_free_list = &cblk->conses[start];
+#if GC_MARK_STACK
+ cons_free_list->car = Vdead;
+#endif
+ }
+ else
+ {
+ num_used++;
+ CONS_UNMARK (&cblk->conses[start]);
+ }
+ start++;
+ }
+ if (stop < (++i) * BITS_PER_INT)
+ /* Whole bitmap is scanned or LIM is reached. */
+ break;
+ }
+ }
+
+ lim = CONS_BLOCK_SIZE;
+ /* If this block contains only free conses and we have already
+ seen more than two blocks worth of free conses then deallocate
this block. */
if (this_free == CONS_BLOCK_SIZE && num_free > CONS_BLOCK_SIZE)
{
@@ -6010,6 +6101,13 @@
total_free_conses = num_free;
}
+#endif /* Sweep types */
+
+ EMACS_GET_TIME (end);
+ EMACS_SUB_TIME (total, end, beg);
+ fprintf (stderr, "GC%u [%s sweep]: %u us\n", gcs_done,
+ sweep_type, EMACS_USECS (total));
+
/* Put all unmarked floats on free list */
{
register struct float_block *fblk;
- GC: cons sweeping,
Dmitry Antipov <=